An Abstract Machine for Push Bottom-Up Evaluation of Datalog

The Push Method for Bottom-Up Evaluation in deductive databases was previously defined as a translation from Datalog to C++. Performance tests on some benchmarks from the OpenRuleBench collection gave very encouraging results. However, most of the systems used for comparison compile the query into code of an abstract machine and then use an emulator for this code. Therefore, runtimes cannot be directly compared. In this paper, we propose an abstract machine for bottom-up evaluation of Datalog based on the Push Method. This also helps to clarify some optimizations we previously expected from the C++ compiler. First tests have shown that the code running in the emulator of the abstract machine is only 1.5 times slower than the native code generated by the C++ compiler. This is better compared to the case for Prolog.