Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure.

@inproceedings{DBLP:conf/pods/SuciuP94,
  author    = {Dan Suciu and
               Jan Paredaens},
  title     = {Any Algorithm in the Complex Object Algebra with Powerset Needs
               Exponential Space to Compute Transitive Closure},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
               Minnesota},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {201-209},
  ee        = {http://doi.acm.org/10.1145/182591.182613, db/conf/pods/pods94-201.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1994 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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Journal Edition

References

[AB88]

Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX

[AU79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[AV91]

Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX

[BBW92]

Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX

[BIS90]

David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX

[Bol79]

...

[HS91]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX

[HU79]

John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX

[Imm87]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[Imm89]

Neil Immerman: Expressibility and Parallel Complexity. SIAM J. Comput. 18(3): 625-638(1989) BibTeX

[Kah87]

Gilles Kahn: Natural Semantics. STACS 1987: 22-39 BibTeX

[KV93]

Gabriel M. Kuper, Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. Theor. Comput. Sci. 116(1&2): 33-57(1993) BibTeX

[PG88]

Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX

[PG92]

Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX

[Rob69]

...

[SBT94]

Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178 BibTeX

[SS86]

Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX

[TF86]

...

[Won93]

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

Referenced by

1. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
2. Leonid Libkin: Normalizing Incomplete Databases. PODS 1995: 219-230
3. Dan Suciu, Limsoon Wong: On Two Forms of Structural Recursion. ICDT 1995: 111-124
4. Serge Abiteboul, Gerd G. Hillebrand: Space Usage in Functional Query Languages. ICDT 1995: 439-454
5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
   Contents
6. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154