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

[AK90]

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

[AK89]

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

[AB88]

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

[AC89]

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

[AV88]

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

[AV89]

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

[AV91]

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

[BIS88]

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

[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

[CH80]

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

[CH82a]

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

[CH82b]

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

[Ch81]

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

[CSV84]

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

[Co64]

...

[C85]

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

[CM87]

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

[CK85]

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

[DW]

...

[HS89a]

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

[HS89b]

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

[HS88]

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

[Imm87]

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

[Imm82]

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

[Imm82b]

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

[Imm88]

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

[IL89]

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

[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

[Q89]

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

[SS89]

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

[Va82]

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

[VS90]

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