Space Bounded FOIES
Guozhu Dong, The University of Melbourne
Jianwen Su, University of California, Santa Barbara
Status
Preliminary result in Proceednings of
ACM Symposium on Principles of Database Systems,
pages 139-150, May 1995.
Full paper to be submitted to Journal of Computer and System Sciences.
Abstract
After inserting (or deleting) a tuple into (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-Fraiss\'e 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.