Space Bounded FOIES

Guozhu Dong, The University of Melbourne

Jianwen Su, University of California, Santa Barbara


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.


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.