Pipelined Bottom-Up Evaluation of Datalog Programs: The Push Method

In this paper, we present a method for bottom-up evaluation of Datalog programs in deductive databases that “pushes” derived facts immediately to other rules where they are used for deriving more facts. In this way, the materialization of derived relations is avoided as far as possible. Derived facts are represented by values in variables and a location in the program, and not as explicitly constructed tuples. This helps to avoid copying operations and to keep the actively used memory small to make better use of modern processors. The method can be quite easily explained by translating Datalog to functions in a standard programming language like C++ and then using optimizations of the C++ compiler like inlining. First performance tests with benchmarks from the OpenRuleBench collection give good results. This is interesting because systems based on SLD-resolution with tabling such as XSB have beaten older deductive database implementations based on bottom-up evaluation. Now it seems that bottom-up evaluation can be done in a very competitive way.