ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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},
  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},
  publisher = {ACM Press},
  year      = {1995},
  isbn      = {0-89791-730-8},
  pages     = {139-150},
  ee        = {http://doi.acm.org/10.1145/212433.220204, db/conf/pods/DongS95.html},
  crossref  = {DBLP:conf/pods/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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 ... BibTeX

Printed Edition

Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California. ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX

Online Edition: ACM Digital Library

[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 BibTeX
[AP87]
Krzysztof R. Apt, Jean-Marc Pugin: Maintenance of Stratified Databases Viewed as a Belief Revision System. PODS 1987: 136-145 BibTeX
[BLT86]
José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71 BibTeX
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[DS93a]
Guozhu Dong, Jianwen Su: Incremental and Decremental Evaluation of Transitive Closure by First-Order Queries. Inf. Comput. 120(1): 101-106(1995) BibTeX
[DS93b]
Guozhu Dong, Jianwen Su: First-Order Incremental Evaluation of Datalog Queries. DBPL 1993: 295-308 BibTeX
[DS95]
Guozhu Dong, Jianwen Su: Increment Boundedness and Nonrecursive Incremental Evaluation of Datalog Queries. ICDT 1995: 397-410 BibTeX
[DST93]
...
[DT92]
Guozhu Dong, Rodney W. Topor: Incremental Evaluation of Datalog Queries. ICDT 1992: 282-296 BibTeX
[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) BibTeX
[GMS93]
Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166 BibTeX
[GS94]
Stéphane Grumbach, Jianwen Su: Finitely Representable Databases. PODS 1994: 289-300 BibTeX
[Küc91]
Volker Küchenhoff: On the Efficient Computation of the Difference Between Concecutive Database States. DOOD 1991: 478-502 BibTeX
[MSVT94]
Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, Roberto Tamassia: Complexity Models for Incremental Computation. Theor. Comput. Sci. 130(1): 203-236(1994) BibTeX
[PI94]
Sushant Patnaik, Neil Immerman: Dyn-FO: A Parallel, Dynamic Complexity Class. PODS 1994: 210-221 BibTeX
[RRSS94]
Raghu Ramakrishnan, Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Efficient Incremental Evaluation of Queries with Aggregation. SLP 1994: 204-218 BibTeX
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[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 BibTeX

Referenced by

  1. Guozhu Dong, Jianwen Su: Incremental Maintenance of Recursive Views Using Relational Calculus/SQL. SIGMOD Record 29(1): 44-51(2000)
  2. Chaoyi Pang, Kotagiri Ramamohanarao, Guozhu Dong: Incremental FO(+, <) Maintenance of All-Pairs Shortest Paths for Undirected Graphs after Insertions and Deletions. ICDT 1999: 365-382
  3. Kousha Etessami: Dynamic Tree Isomorphism via First-Order Updates. PODS 1998: 235-243
  4. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
  5. Leonid Libkin, Limsoon Wong: Incremental Recomputation of Recursive Queries with Nested Sets and Aggregate Functions. DBPL 1997: 222-238
  6. Guozhu Dong, Leonid Libkin, Limsoon Wong: On Impossibility of Decremental Recomputation of Recursive Queries in Relational Calculus and SQL. DBPL 1995: 7
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:12 2009