Guozhu Dong, The University of Melbourne
Jianwen Su, University of California, Santa Barbara
Rodney Topor, Griffith University
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.