Efficient computation and maintenance of datalog materialisations

Thesis

Datalog is a prominent knowledge representation language whose popularity is mainly due to its ability to express recursive definitions. Datalog applications typically require efficient reasoning over datalog programs and facts. To support this, datalog systems often materialise all consequences of a datalog program so that all queries can later be evaluated directly over the materialisation. This style of reasoning is usually complemented with an incremental maintenance algorithm that updates the materialisation whenever the input facts change. Existing solutions to the incremental maintenance problem either handle only nonrecursive rules or 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, and we present two hybrid approaches that reduce or even eliminate “backwards” rule evaluation while still handling arbitrary datalog programs. Moreover, we observe that for both materialisation and incremental maintenance, certain (combinations of) rules 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 evaluation strategy as in most existing solutions. 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 the proposed solutions are usually significantly faster than existing approaches, sometimes by orders of magnitude.

Authors: Hu, P

• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English