NONRECURSIVE INCREMENTAL EVALUATION OF DATALOG QUERIES

We consider the problem of repeatedly evaluating the same (computation ally expensive) query to a database that is being updated between succ essive query requests. In this situation, it should be possible to use the difference between successive database states and the answer to t he query in one state to reduce the cost of evaluating the query in th e next state. We use nonrecursive Datalog (which are unions of conjunc tive queries) to compute the differences, and call this process ''incr emental query evaluation using conjunctive queries''. After formalizin g 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 Datalo g program to compute the difference between the answer after an update and the answer before the update. We then extend this result to weakl y regular queries, which are regular chain programs augmented with con junctive queries having the so-called Cartesian-closed increment prope rty, and to the case of unbounded-set insertions where the sets are bi nary Cartesian products. Finally, we show that the class of conjunctiv e queries with the Cartesian-closed increment property is decidable.