Modular Materialisation of Datalog Programs

The seminaı̈ve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally 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 computing and maintaining a materialisation. We split a datalog program into modules that can be handled using specialised algorithms, and we 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.

Authors

• Pan Hu School of Electronic Information and Electrical Engineering, Shanghai Jiao Tong University, China
• Boris Motik
• Ian Horrocks University of Oxford

Keywords

No keywords are indexed for this paper.