First-Order Incremental Evaluation of Datalog Queries

Document Type

Book Chapter

Publication Date


Find in a Library

Catalog Record


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 first-order (i.e., nonrecursive) queries to compute the differences, and call this process first-order incremental query evaluation.

After formalizing the notion of a first-order incremental query evaluation system (FOIES), we present an earlier result that every regular chain query (which are associated with chain Datalog programs) has a FOIES. We then extend this result to the situations (1) where regular chain queries are augmented with binary conjunctive queries with unions, defining nonrecursive predicates, that have “cartesian-closed increment” (CCI), and (2) where insertions for regular queries are unbounded but “cartesian-closed” sets. The notion of CCI is essential in proving (1). We also studied the decision problem for CCI. It is shown that the CCI property is decidable for binary conjunctive queries with unions but undecidable for recursive queries and for relational calculus queries. We also consider a subclass of FOIES, “space-free” FOIES, which use no additional facts in the incremental evaluation. We show that there are queries which have FOIES but not space-free FOIES and that it is undecidable if a Datalog query has a space-free FOIES. Finally, many questions remain open. For example, does there exist a Datalog query which does not have any FOIES?


Presented at the Fourth International Workshop on Database Programming Languages, Manhattan, NY, August 20-September 1, 1993.



Catalog Record