Incremental Evaluation of Datalog Queries

Document Type

Book Chapter

Publication Date

1999

Find in a Library

Catalog Record

Abstract

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.

Comments

An earlier version of this chapter was presented at the Fourth International Conference of Database Theory, Berlin, Germany, October 14-16, 1992. A copy of the earlier iteration can be found at http://dx.doi.org/10.1007/3-540-56039-4_48.

Catalog Record

Share

COinS