Abstract Rewriting Approach to Solve Datalog Programs
Over the past decade, we have seen a resurgence in the Datalog language in different computing areas for solving a number of non- trivial problems. In this paper we introduce a novel resolution ap- proach to solve Datalog programs. We have developed an abstract rewriting formalism to create a functional resolution process for Datalog. The resolution approach translates the Datalog resolu- tion strategy into a fix-point abstract rewriting equation system. Be- ing an abstract rewriting formalism, every equation of the system can be viewed as a function. Based on this fact, we also developed an optimization process that improves the initial rewriting equa- tion system. The optimization process generates an equation sys- tem that computes the solutions much more efficiently. Well known optimizations such as strength reduction or memoization have been used. We also developed a prototype compiler that encodes the opti- mized equation system into a solver. Experimental results obtained with the solver suggest execution times several orders of magnitude better than modern Prolog solvers like Y AP or X SB and usually one order of magnitude faster than state-of-the-art Datalog solvers such as BDDBDDB and DLV.
Tue 27 Oct Times are displayed in time zone: (GMT-04:00) Eastern Time (US & Canada) change
|10:30 - 11:00|
|11:00 - 11:30|
|11:30 - 12:00|