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

A Query Language for List-Based Complex Objects.

Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189
@inproceedings{DBLP:conf/pods/ColbyRSG94,
  author    = {Latha S. Colby and
               Edward L. Robertson and
               Lawrence V. Saxton and
               Dirk Van Gucht},
  title     = {A Query Language for List-Based Complex Objects},
  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     = {179-189},
  ee        = {http://doi.acm.org/10.1145/182591.182611, db/conf/pods/pods94-179.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a language for querying list-based complex objects. The language is shown to express precisely the polynomial-time generic list-object functions. The iteration mechanism of the language is based on a new approach wherein, in addition to the list over which the iteration is performed, a second list is used to control the number of iteration steps. During the iteration, the intermediate results can be moved to the output list as well as re-inserted into the list being iterated over. A simple syntactic constraint allows the growth rate of the intermediate results to be tightly controlled which, in turn, restricts the expressiveness of the language to PTIME.

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 ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

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

References

[AB87]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV90]
Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AV91]
Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BC92]
Stephen Bellantoni, Stephen A. Cook: A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract). STOC 1992: 283-293 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BTBN91]
Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BTBW92]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha81]
Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CSV93]
...
[CSV94]
...
[GM93]
Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GV88]
Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GW92]
Seymour Ginsburg, Xiaoyang Sean Wang: Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. PODS 1992: 293-300 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HKM93]
Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson: Database Query Languages Embedded in the Typed Lambda Calculus. LICS 1993: 332-343 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS89]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS91]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HS93]
Richard Hull, Jianwen Su: Algebraic and Calculus Query Languages for Recursively Typed Complex Objects. J. Comput. Syst. Sci. 47(1): 121-156(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IPS91a]
...
[IPS91b]
Neil Immerman, Sushant Patnaik, David W. Stemple: The Expressiveness of a Family of Finite Set Languages. PODS 1991: 37-52 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LM93]
Daniel Leivant, Jean-Yves Marion: Lambda Calculus Characterizations of Poly-Time. Fundam. Inform. 19(1/2): 167-184(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LW93]
Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MV93]
David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PSV92]
Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez: SVP: A Model Capturing Sets, Lists, Streams, and Parallelism. VLDB 1992: 115-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Suc93]
Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tri91]
Philip W. Trinder: Comprehensions, a Query Notation for DBPLs. DBPL 1991: 55-68 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Evgeny Dantsin, Andrei Voronkov: Expressive Power and Data Complexity of Query Languages for Trees and Lists. PODS 2000: 157-165
  2. Paolo Atzeni, Giansalvatore Mecca: Cut & Paste. PODS 1997: 144-153
  3. Latha S. Colby, Leonid Libkin: Tractable Iteration Mechanisms for Bag Languages. ICDT 1997: 461-475
  4. Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35
  5. H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
  6. Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207
  7. Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12

Copyright © Mon Nov 2 21:04:25 2009 by Michael Ley (ley@uni-trier.de)