First-Order Incremental Evaluation of Datalog Queries

Guozhu Dong, The University of Melbourne

Jianwen Su, University of California, Santa Barbara

Rodney Topor, Griffith University


Annals of Mathematics and Artificial Intelligence, 14(1995) 187-223. Preliminary results presented at the 1992 International Conference on Database Theory, and the 1993 International Workshop on Database Programming Languages.


We consider the problem of repeatedly evaluating the same (computationally expensive) query to a database that is being updated between successive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to the query in one state to reduce the cost of evaluating the query in the next state. We use nonrecursive Datalog (which are unions of conjunctive queries) to compute the differences, and call this process ``incremental query evaluation using conjunctive queries.''

After formalizing the notion of incremental query evaluation using conjunctive queries, we give an algorithm that constructs, for each regular chain query (including transitive closure as a special case), a nonrecursive Datalog program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakly regular queries, which are regular chain programs augmented with conjunctive queries having the so-called cartesian-closed increment property, and to the case of unbounded-set insertions where the sets are binary cartesian products. Finally, we show that the class of conjunctive queries with the cartesian-closed increment property is decidable.