The Expressiveness of a Family of Finite Set Languages.

Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52
  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        = {, db/conf/pods/ImmermanPS91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP,}


In this paper we characterise exactly the complexity of a set based database language called SRL, which presents a unified framework for queries and updates. By imposing simple syntactic restrictions on it, we are able to express exactly the classes, P and LOGSPACE. We also discuss the role of ordering in database query languages and show that the hom operator of Machiavelli language in [OBB89] does not capture all the order-independent properties.

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.

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 Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1388 KB]


Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
Serge Abiteboul, Paris C. Kanellakis: Database Theory Column: Query Languages for Complex Object Databases. SIGACT News 21(3): 9-18(1990) BibTeX
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
Foto N. Afrati, Stavros S. Cosmadakis: Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989: 113-126 BibTeX
Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250 BibTeX
Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 BibTeX
David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306(1990) BibTeX
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
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
Ashok K. Chandra, David Harel: Horn Clauses and the Fixpoint Query Hierarchy. PODS 1982: 158-163 BibTeX
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 BibTeX
Ashok K. Chandra, Larry J. Stockmeyer, Uzi Vishkin: Constant Depth Reducibility. SIAM J. Comput. 13(2): 423-439(1984) BibTeX
Stephen A. Cook: A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64(1-3): 2-21(1985) BibTeX
Stephen A. Cook, Pierre McKenzie: Problems Complete for Deterministic Logarithmic Space. J. Algorithms 8(3): 385-394(1987) BibTeX
Stavros S. Cosmadakis, Paris C. Kanellakis: Parallel Evaluation of Recursive Rule Queries. PODS 1986: 280-293 BibTeX
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
Richard Hull, Jianwen Su: On Bulk Data type Constructors and Manipulation Primitives: A Framework for Analyzing Power and Complexity. DBPL 1989: 396-410 BibTeX
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX
Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX
Neil Immerman: Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5): 935-938(1988) BibTeX
Neil Immerman, Susan Landau: The Complexity of Iterated Multiplication. Inf. Comput. 116(1): 103-116(1995) BibTeX
Atsushi Ohori, Peter Buneman, Val Tannen: Database Programming in Machiavelli - a Polymorphic Language with Static Type Inference. SIGMOD Conference 1989: 46-57 BibTeX
Xiaolei Qian: On the Expressive Power of the Bounded Iteration Construct. DBPL 1989: 411-421 BibTeX
Tim Sheard, David W. Stemple: Automatic Verification of Database Transaction Safety. ACM Trans. Database Syst. 14(3): 322-368(1989) BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:02 2009