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

Authors
Citation
Gz. Dong et Jw. Su, Arity bounds in first-order incremental evaluation and definition of polynomial time database queries, J COMPUT SY, 57(3), 1998, pp. 289-308
Citations number
33
Categorie Soggetti
Computer Science & Engineering
Journal title
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
ISSN journal
00220000 → ACNP
Volume
57
Issue
3
Year of publication
1998
Pages
289 - 308
Database
ISI
SICI code
0022-0000(199812)57:3<289:ABIFIE>2.0.ZU;2-M
Abstract
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.