Arity bounds in first-order incremental evaluation and definition of polynomial time database queries

After inserting a tuple into or deleting a tuple from a database, a first-o rder incremental evaluation system (or a "foies") for a database query deri ves the new query answer by using a first-order query on the new database, the old answer, and perhaps some stored auxiliary relations. Moreover, the auxiliary relations must also be maintained similarly using first-order que ries. In this paper we measure the space needed by foies in terms of the maximal arity of the auxiliary relations and present results on the existence and n onexistence of such space-restricted foies for a variety of graph queries, including counting and transitive closure. We construct space efficient foi es for these queries and show that the arity bounds are tight using Ehrenfe ucht-Fraisse games. In particular, for transitive closure over undirected g raphs, the minimum arity bound of its foies is shown to be exactly two; thi s resolves an open problem raised by Patnaik and Immerman in 1994. For the general case, we show that the arity-based hierarchy is strict for all arit ies. The strictness proof uses queries with input relations having arities much larger than the auxiliary relations. It is still open whether the hier archy remains strict for arities two or greater when the input relations of queries have arities bounded by a fixed number, such as two, or by the ari ties of the auxiliary relations. Finally, we consider a variation of foies where the cost of storing the ans wer to the query is also "charged." We show that the arity hierarchy in thi s case is also strict. The positions of queries in the two arity-based hier archies can differ; we give the positions in this hierarchy of the queries considered for the other arity hierarchy. (C) 1998 Academic Press.