Abstract rewriting Approach to solve Datalog programs
Fernando Tarín Morales, Fuyuki Ishikawa, Shinichi Honiden · 2015
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 present a version of the technique that works on plain Datalog programs. We have devel- oped an abstract rewriting formalism to create a functional reso- lution process for Datalog. The resolution approach translates the Datalog resolution strategy into a fix-point abstract rewriting equa- tion system. Being 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 equation system. The optimization process generates an equation system that computes the solutions much more efficiently. Well known optimizations such as strength reduction or memoiza- tion have been used. We also developed a prototype compiler that encodes the optimized equation system into a solver. Experimental results obtained with the solver suggest execution times several or- ders 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 B DDBDDB and DLV.