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

New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions.

Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
@inproceedings{DBLP:conf/pods/LibkinW94,
  author    = {Leonid Libkin and
               Limsoon Wong},
  title     = {New Techniques for Studying Set Languages, Bag Languages and
               Aggregate Functions},
  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     = {155-166},
  ee        = {http://doi.acm.org/10.1145/182591.182609, db/conf/pods/pods94-155.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We provide new techniques for the analysis of the expressive power of query languages for nested collections. These languages may use set or bag semantics and may be further complicated by the presence of aggregate functions. We exhibit certain classes of graphs and prove that the properties of these graphs that can be tested in such languages are either finite or cofinite. This result settles the conjectures of Grumbach, Milo, and Paredaens that parity test, transitive closure, and balanced binary tree test are not expressible in bag languages like the PTIME fragment of BALG of Grumbach and Milo and BQL of Libkin and Wong. Moreover, it implies that many recursive queries, including simple ones like the test for a chain, cannot be expressed in a nested relational language even when aggregate functions are available. In an attempt to generalize the finite-cofiniteness result, we study the bounded degree property which says that the number of distinct in- and out-degrees in the output of a graph query does not depend on the size of the input if the input is ``simple.'' We show that such a property implies a number of inexpressibility results in a uniform fashion. We then prove the bounded degree property for the nested relational language.

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.

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 Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 1118 KB]

Journal Edition

Leonid Libkin, Limsoon Wong: Query Languages for Bags and Aggregate Functions. J. Comput. Syst. Sci. 55(2): 241-272(1997) BibTeX

References

[AK90]
Serge Abiteboul, Paris C. Kanellakis: Database Theory Column: Query Languages for Complex Object Databases. SIGACT News 21(3): 9-18(1990) BibTeX
[BBW92]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[Col90]
Latha S. Colby: A recursive algebra for nested relations. Inf. Syst. 15(5): 567-582(1990) BibTeX
[CV93]
Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70 BibTeX
[CM93]
Mariano P. Consens, Alberto O. Mendelzon: Low Complexity Aggregation in GraphLog and Datalog. Theor. Comput. Sci. 116(1&2): 95-116(1993) BibTeX
[Fag93]
Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993) BibTeX
[FSV93]
...
[FSS84]
Merrick L. Furst, James B. Saxe, Michael Sipser: Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory 17(1): 13-27(1984) BibTeX
[Gai82]
...
[GM93]
Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 BibTeX
[Imm87]
Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX
[IPS91]
Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 BibTeX
[Joh90]
...
[LW94a]
Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 BibTeX
[LW94b]
Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294 BibTeX
[LW94c]
Leonid Libkin, Limsoon Wong: Conservativity of Nested Relational Calculi with Internal Generic Functions. Inf. Process. Lett. 49(6): 273-280(1994) BibTeX
[Par93]
...
[PG92]
Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX
[SS86]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[ST94]
Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178 BibTeX
[TF86]
...
[Won93]
Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36 BibTeX

Referenced by

  1. Luca Cabibbo, Riccardo Torlone: A Framework for the Investigation of Aggregate Functions in Database Queries. ICDT 1999: 383-397
  2. Guozhu Dong, Leonid Libkin, Limsoon Wong: Local Properties of Query Languages. ICDT 1997: 140-154
  3. Michael Benedikt, H. Jerome Keisler: Expressive Power of Unary Counters. ICDT 1997: 291-305
  4. Leonid Libkin, Rona Machlin, Limsoon Wong: A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conference 1996: 228-239
  5. Michael Benedikt, Timothy Griffin, Leonid Libkin: Verifiable Properties of Database Transactions. PODS 1996: 117-127
  6. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
  7. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
  8. Leonid Libkin: Normalizing Incomplete Databases. PODS 1995: 219-230
  9. Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207
  10. Leonid Libkin: Query Language Primitives for Programming with Incomplete Databases. DBPL 1995: 6
  11. 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:10 2009