Abstract rewriting approach to solve datalog programs

Fernando Tarin Morales, Fuyuki Isihikawa, Shinichi Honiden

研究成果: Conference contribution


Over the past decade, we have seen a resurgence in the Datalog language in different computing areas for solving a number of nontrivial problems. In this paper we introduce a novel resolution approach to solve Datalog programs. We present a version of the technique that works on plain Datalog programs. We have developed an abstract rewriting formalism to create a functional resolution process for Datalog. The resolution approach translates the Datalog resolution strategy into a fix-point abstract rewriting equation 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 memoization 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 orders of magnitude better than modern Prolog solvers like YAP or XSB and usually one order of magnitude faster than state-of-the-art Datalog solvers such as BDDBDDB and DLV.

ホスト出版物のタイトルDBPL 2015 - Proceedings of the 15th Symposium on Database Programming Languages
編集者Thomas Neumann, James Cheney
出版社Association for Computing Machinery, Inc
出版ステータスPublished - 2015 10月 27
イベント15th Symposium on Database Programming Languages, DBPL 2015 - Pittsburgh, United States
継続期間: 2015 10月 27 → …


名前DBPL 2015 - Proceedings of the 15th Symposium on Database Programming Languages


Other15th Symposium on Database Programming Languages, DBPL 2015
国/地域United States
Period15/10/27 → …

ASJC Scopus subject areas

  • コンピュータ サイエンスの応用