Incremental update of datalog materialisation: the backward/forward algorithm

Conference item

Datalog-based systems often materialise all consequences of a datalog program and the data, allowing users' queries to be evaluated directly in the materialisation. This process, however, can be computationally intensive, so most systems update the materialisation incrementally when input data changes. We argue that existing solutions, such as the well-known Delete/Rederive (DRed) algorithm, can be inefficient in cases when facts have many alternate derivations. As a possible remedy, we propose a novel Backward/Forward (B/F) algorithm that tries to reduce the amount of work by a combination of backward and forward chaining. In our evaluation, the B/F algorithm was several orders of magnitude more efficient than the DRed algorithm on some inputs, and it was never significantly less efficient.

Authors: Motik, B; Nenov, Y; Piro, R; Horrocks, I

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: AAAI Press
• Host title: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference, January 25–30, 2015, Austin, Texas, USA
• Pages: 1560-1568
• Publication date: 2015-01-01
• EISSN: 2374-3468
• ISSN: 2159-5399
• ISBN: 9781577356981
• Keywords: Deletion; Materialisation; Datalog; RDF; Incremental