Space-Bounded FOIES.
Guozhu Dong, Jianwen Su:
Space-Bounded FOIES.
PODS 1995: 139-150@inproceedings{DBLP:conf/pods/DongS95,
author = {Guozhu Dong and
Jianwen Su},
editor = {Mihalis Yannakakis},
title = {Space-Bounded FOIES},
booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 22-25, 1995, San Jose,
California, USA},
publisher = {ACM Press},
year = {1995},
isbn = {0-89791-730-8},
pages = {139-150},
ee = {http://doi.acm.org/10.1145/212433.220204},
crossref = {DBLP:conf/pods/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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-Fraissé 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.
Copyright © 1995 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
Printed Edition
Mihalis Yannakakis (Ed.):
Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California, USA.
ACM Press 1995, ISBN 0-89791-730-8
Contents 
[Index Terms]
[Full Text in PDF Format, 1151 KB]
Journal Version
to appear in Journal of Computer and System Sciences:
"Arity Bounds in First-Order Incremental Evaluation and Definition of
Polynomial Time Database Queries"
References
- [AF90]
- ...
- [AHV94]
- Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents - [AP87]
- Krzysztof R. Apt, Jean-Marc Pugin:
Maintenance of Stratified Databases Viewed as a Belief Revision System.
PODS 1987: 136-145
- [BLT86]
- José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa:
Efficiently Updating Materialized Views.
SIGMOD Conference 1986: 61-71
- [CH80]
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases.
J. Comput. Syst. Sci. 21(2): 156-178(1980)
- [DS93a]
- Guozhu Dong, Jianwen Su:
Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries.
Inf. Comput. 120(1): 101-106(1995)
- [DS93b]
- Guozhu Dong, Jianwen Su:
First-Order Incremental Evaluation of Datalog Queries.
DBPL 1993: 295-308
- [DS95]
- Guozhu Dong, Jianwen Su:
Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries.
ICDT 1995: 397-410
- [DST93]
- ...
- [DT92]
- Guozhu Dong, Rodney W. Topor:
Incremental Evaluation of Datalog Queries.
ICDT 1992: 282-296
- [Ehr61]
- ...
- [Fag75]
- ...
- [Fra54]
- ...
- [FSV94]
- Ronald Fagin, Larry J. Stockmeyer, Moshe Y. Vardi:
On Monadic NP vs. Monadic co-NP.
Inf. Comput. 120(1): 78-92(1995)
- [GMS93]
- Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian:
Maintaining Views Incrementally.
SIGMOD Conference 1993: 157-166
- [GS94]
- Stéphane Grumbach, Jianwen Su:
Finitely Representable Databases.
PODS 1994: 289-300
- [Küc91]
- Volker Küchenhoff:
On the Efficient Computation of the Difference Between Concecutive Database States.
DOOD 1991: 478-502
- [MSVT94]
- Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia:
Complexity Models for Incremental Computation.
Theor. Comput. Sci. 130(1): 203-236(1994)
- [PI94]
- Sushant Patnaik, Neil Immerman:
Dyn-FO: A Parallel, Dynamic Complexity Class.
PODS 1994: 210-221
- [RRSS94]
- Raghu Ramakrishnan, Kenneth A. Ross, Divesh Srivastava, S. Sudarshan:
Efficient Incremental Evaluation of Queries with Aggregation.
SLP 1994: 204-218
- [Ull88]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents - [WDSY91]
- Ouri Wolfson, Hasanat M. Dewan, Salvatore J. Stolfo, Yechiam Yemini:
Incremental Evaluation of Rules and its Relationship to Parallelism.
SIGMOD Conference 1991: 78-87
Last update Thu May 24 04:40:30 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
