Optimised Maintenance of Datalog Materialisations

Authors

  • Pan Hu University of Oxford
  • Boris Motik University of Oxford
  • Ian Horrocks University of Oxford

Keywords:

Datalog, Materialisation, Incremental, Deletion

Abstract

To efficiently answer queries, datalog systems often materialise all consequences of a datalog program, so the materialisation must be updated whenever the input facts change. Several solutions to the materialisation update problem have been proposed. The Delete/Rederive (DRed) and the Backward/Forward (B/F) algorithms solve this problem for general datalog, but both contain steps that evaluate rules "backwards" by matching their heads to a fact and evaluating the partially instantiated rule bodies as queries. We show that this can be a considerable source of overhead even on very small updates. In contrast, the Counting algorithm does not evaluate the rules "backwards," but it can handle only nonrecursive rules. We present two hybrid approaches that combine DRed and B/F with Counting so as to reduce or even eliminate "backward" rule evaluation while still handling arbitrary datalog programs. We show empirically that our hybrid algorithms are usually significantly faster than existing approaches, sometimes by orders of magnitude.

Downloads

Published

2018-04-25

How to Cite

Hu, P., Motik, B., & Horrocks, I. (2018). Optimised Maintenance of Datalog Materialisations. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11554

Issue

Section

AAAI Technical Track: Knowledge Representation and Reasoning