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.

本研究提出了两种将 Delete/Rederive 算法和 Backward/Forward 算法与 Counting 算法相结合的混合算法，以减少甚至消除对于逆向规则评估的瓶颈，从而有效优化对于非递归 datalog 程序的更新速度。