Home      Publications      C++ Code      Translator      Abstract Machine      Benchmark Results      Links

Bottom-Up Evaluation with the "Push Method"

Overview

Current State:

We have a prototype implementation which can execute some of the benchmarks of the OpenRuleBench benchmark suite (see also OpenRuleBench Download). Current restrictions of our implementation are that it does not support structured terms (only constants and variables), no negation, and no aggregation. It is intended only to demonstrate the performance possibilities of the approach, not as a real system which can be used for practical applications.

• Publications
• C++ Code (Library with Index Structures, Benchmark Code)
• Translator from Datalog to C++ (written by Heike Stephan)
• Benchmark Results
• Links to Related Work

Motivation:

Database application programs usually consist of queries, written in a declarative language (typically SQL), and surrounding program code, written in a procedural language (like PHP or Java). The goal of deductive databases is to write a larger part of the application (ideally the entire program) in a declarative language based on Prolog/Datalog. This has many aspects, e.g. the invention of new language constructs for declarative output (see our work on Datalog with Ordered Facts).

However, the classic task of improving the speed of query/program evaluation is still important. The amount of data to be processed is ever growing. Furthermore, people who are sceptical about the usefulness of declarative programming tend to ask about efficiency as one of their first questions. Developing a fast main-memory deductive database system is the overall goal of this research project.

To this end, we are testing a method that does bottom-up evaluation (i.e. applies the rules from body to head), but immediately "pushes" a derived fact to rules where it matches a body literal. In contrast, classical bottom-up evaluation would first apply a rule completely, which requires intermediate storage for the result. The name "push method" was chosen in contrast to a method where the consumer of the derived facts "pulls" the next fact. In the "push method" the producer has the control. The three versions (classical/materialization, pull, and push) have been compared in previous work on bottom-up evaluation). However, in the meantime we have improved the push method. Furthermore, the previous work did not consider index structures and real data (to be loaded from files) in its preformance tests.

Our approach is to translate a given Datalog program to C++ code, which is then compiled with a standard compiler to native code. While the rules defining derived predicates are known in this step (i.e. at "compile time"), the real data (the facts for the database predicates including user input) are only known at runtime. Therefore, the time needed for the transformation and the compilation can be amortized over many executions of the resulting program. However, often even a single execution suffices, since the data are usually much bigger than the program. Translating to a standard programming language also has the advantage that a combination with hand-written procedural code is simpler. Of course, in the long run, we hope that this will be necessary only very seldom.

Stefan Brass (brass@informatik.uni-halle.de), May 10, 2016

Original URL: http://www.informatik.uni-halle.de/~brass/push/   [XHTML 1.0]   [CSS]   [Links]   [Legal Info]