Title: Optimised Maintenance of Datalog Materialisations,
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.