Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries

Document Type

Book Chapter

Publication Date

1-1995

Find in a Library

Catalog Record

Abstract

Given a recursive (datalog) query, the nonrecursive incremental evaluation approach uses nonrecursive (datalog) programs to compute the difference of the answers to the query against successive databases between updates. The mechanism used in this approach is called a “First-Order Incremental Evaluation System” (FOIES). We show that for two large classes of datalog queries, called “generalized (weakly) regular queries”, FOIES always exist. We also define “increment boundedness” and its variations, which generalize boundedness. Increment bounded queries are shown to have FOIES of certain forms. We also relate increment boundedness to structural recursion, which was proposed for bulk data types. We characterize increment boundedness using the “insertion idempotency”, “insertion commutativity”, and “determinism” properties of structural recursion. Finally, we show that the increment boundedness notions are undecidable and a decidable sufficient condition is given.

Comments

Presented at the International Conference on Database Theory, Prague, Czech Republic, January 11-13, 1995.

DOI

10.1007/3-540-58907-4_30

Catalog Record

Share

COinS