Modular Materialisation of Datalog Programs
This work addresses efficiency bottlenecks in datalog reasoning systems, which is important for applications in databases and knowledge representation, though it appears incremental in nature.
The authors tackled the problem of efficiently materializing all consequences of arbitrary datalog programs by proposing a modular framework that splits programs into modules handled by specialized algorithms, with remaining rules processed using the seminaïve algorithm. They demonstrated empirically that their approach outperforms existing methods, often by orders of magnitude.
The seminaïve algorithm can materialise all consequences of arbitrary datalog rules, and it also forms the basis for incremental algorithms that update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algorithms. To integrate such algorithms into a general reasoning approach that can handle arbitrary rules, we propose a modular framework for materialisation computation and its maintenance. We split a datalog program into modules that can be handled using specialised algorithms, and handle the remaining rules using the seminaïve algorithm. We also present two algorithms for computing the transitive and the symmetric-transitive closure of a relation that can be used within our framework. Finally, we show empirically that our framework can handle arbitrary datalog programs while outperforming existing approaches, often by orders of magnitude.