Optimised Maintenance of Datalog Materialisations
This addresses the materialisation update problem for datalog systems, which is incremental as it builds on existing algorithms to improve performance.
The paper tackles the problem of efficiently updating materialised consequences in datalog systems when input facts change, presenting hybrid algorithms that combine DRed and B/F with Counting to reduce backward rule evaluation, resulting in significant speed improvements, sometimes by orders of magnitude.
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.