Institut für Informatik Deductive Databases
Prof. Dr. Stefan Brass Push Method



Bottom-Up Evaluation with the "Push Method"

C++ Source Code for Library and Benchmarks


This is the version from May 27. It has a more uniform management of tests and benchmarks (a few tests from main.cpp still have to be migrated). The new version prints some help if called with the option "-h" and a list of available benchmarks if called with the option "-l". It permits much more control on the quantity of output.

The DBLP Benchmark Version 2 is the first with a cursor interface, which makes answers really accessible (previously, we only counted the answers within the generator). (The other systems also use anonymous variables in the query.) Interestingly, the runtime has not significantly changed. The same is true also for the transitive closure benchmark tc(X,Y): There is also no significant runtime difference between the old version (static method with local variables) and the new version (object with cursor interface for the query results, with all variables in attribute). In case of the transitive closure benchmark, there is also no significant runtime difference between the hand-crafted loader and the general, table-based loader. So we will soon eliminate the hand-crafted loaders. We still do some more performance checks with the old relation data structures before eliminating them.

Note: This is only a research prototype under construction. It is not intended for real applications where bugs could do harm.


Project Management:


Basic Definitions and Programming Support:


Memory Management:


Main Memory Relations:


Input, Scanner, Data Loader:


Test Support I:


Performance Tests (Benchmarks):


Test Support II and Main Program:



Unpack the archive with the source files and just type "make". This should generate an executable program called "ydb". The compilation should also work with Microsoft Visual Studio 2015, Express Edition. If the compilation does not work, please contact The makefile also knows about the following goals:


Data Files:

The data files are taken from the OpenRuleBench Benchmark Suite, see OpenRuleBench Download. Our test program expects that the necessary data files are available in a subdirectory "data" of the directory, in which the program "ydb" is executed. Since some of the data files are randomly generated by OpenRuleBench scripts, we publish them here (to make everything reproducible). You will also need "" (in the directory "large-joins/data" of the OpenRuleBench archive) and "wine_data.P" (in the directory "recursion/data"). All files are in the XSB syntax (standard Datalog facts), which our loader can read.


Using the Program:

The program has compiled in a number of tests and benchmarks. The test/benchmark can be selected with a command line argument. A list of tests is printed if the program is called with the option -l. The most important benchmarks are:

The program is called in the form ydb <Options> <Test/Benchmark IDs>. It understands the following options:

Note: The current version writes a file "alert" with error messages and object dumps (in debug mode). I will soon add an option to suppress this. For the time being, one needs write permission for the directory in which one executes ydb because of this error log file (which is opened even if there are no errors).


Stefan Brass (, May 27, 2016

Original URL:   [XHTML 1.0]   [CSS]   [Links]   [Legal Info]