The Expressiveness of a Family of Finite Set Languages.

@inproceedings{DBLP:conf/pods/ImmermanPS91,
  author    = {Neil Immerman and
               Sushant Patnaik and
               David W. Stemple},
  title     = {The Expressiveness of a Family of Finite Set Languages},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {37-52},
  ee        = {http://doi.acm.org/10.1145/113413.113417, db/conf/pods/ImmermanPS91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 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

References

[AU79]

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

[AK90]

Serge Abiteboul, Paris C. Kanellakis: Database Theory Column: Query Languages for Complex Object Databases. SIGACT News 21(3): 9-18(1990) BibTeX

[AK89]

Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX

[AB88]

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

[AC89]

Foto N. Afrati, Stavros S. Cosmadakis: Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989: 113-126 BibTeX

[AV88]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX

[AV89]

Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX

[AV91]

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

[BIS88]

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

[BM]

...

[CFI89]

Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617 BibTeX

[CH80]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX

[CH82a]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[CH82b]

Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX

[Ch81]

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX

[CSV84]

Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin: Constant Depth Reducibility. SIAM J. Comput. 13(2): 423-439(1984) BibTeX

[Co64]

...

[C85]

Stephen A. Cook: A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1-3): 2-21(1985) BibTeX

[CM87]

Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394(1987) BibTeX

[CK85]

Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX

[DW]

...

[HS89a]

Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX

[HS89b]

Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410 BibTeX

[HS88]

Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX

[Imm87]

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

[Imm82]

Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX

[Imm82b]

Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX

[Imm88]

Neil Immerman: Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5): 935-938(1988) BibTeX

[IL89]

Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. Inf. Comput. 116(1): 103-116(1995) BibTeX

[IL90]

...

[IPS91]

...

[K88]

...

[OBB89]

Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57 BibTeX

[Q89]

Xiaolei Qian: On the Expressive Power of the Bounded Iteration Construct. DBPL 1989: 411-421 BibTeX

[SS89]

Tim Sheard, David W. Stemple: Automatic Verification of Database Transaction Safety. ACM Trans. Database Syst. 14(3): 322-368(1989) BibTeX

[Va82]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[VS90]

Jeffrey Scott Vitter, Elizabeth A. M. Shriver: Optimal Disk I/O with Parallel Block Transfer (Extended Abstract). STOC 1990: 159-169 BibTeX

Referenced by

1. Peter Buneman, Atsushi Ohori: Polymorphism and Type Inference in Database Programming. ACM Trans. Database Syst. 21(1): 30-76(1996)
2. Michael Benedikt, Timothy Griffin, Leonid Libkin: Verifiable Properties of Database Transactions. PODS 1996: 117-127
3. Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
4. Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35
5. Vladimir Yu. Sazonov, Alexei Lisitsa: Delta-Languages for Sets and sub-PTIME Graphs Transformers. ICDT 1995: 125-138
6. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
7. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
8. Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
9. Gerd G. Hillebrand, Paris C. Kanellakis: Functional Database Query Languages as Typed Lambda Calculi of Fixed Order. PODS 1994: 222-231
10. Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189
11. Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
12. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
13. Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190
14. Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15
15. Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154
16. Natraj Arni, Sergio Greco, Domenico Saccà: Set-Term Matching in Logic Programming. ICDT 1992: 436-449
17. Leonidas Fegaras, David W. Stemple: Using Type Transformation in Database Implementation. DBPL 1991: 337-353