Space-Bounded FOIES

Document Type

Conference Proceeding

Publication Date

5-1995

Find in a Library

Catalog Record

Abstract

After inserting a tuple into (or deleting a tuple from) a database, a “first-order incremental evaluation system” (or “foies”) for a database query derives the new query answer by using a non recursive or first-order query on the new database, the old answer, and perhaps some (stored) auxiliary relations. Furthermore, the auxiliary relations must also be maintained in the same manner, i.e., derived using first-order queries. In this paper we measure the space needed by foies in terms of the maximal arity of the auxiliary relations and present results on existence and nonexistence of space restricted foies for a variety of conventional queries. We construct space efficient foies for these queries, and show that the space bounds are tight using a variation of Ehrenfeucht- Fraiss6 games. In particular, we show that, for transitive closure over undirected graphs, the minimum space bound of its foies is exactly 2; this resolves an open problem raised by Patnaik and Immerman in PODS ’94.

Comments

Presented at the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Jose, CA, May 22-25, 1995.

DOI

10.1145/212433.220204

Catalog Record

Share

COinS