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

Normal Forms and Conservative Properties for Query Languages over Collection Types.

Limsoon Wong: Normal Forms and Conservative Properties for Query Languages over Collection Types. PODS 1993: 26-36
@inproceedings{DBLP:conf/pods/Wong93,
  author    = {Limsoon Wong},
  title     = {Normal Forms and Conservative Properties for Query Languages
               over Collection Types},
  booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 25-28, 1993, Washington,
               DC},
  publisher = {ACM Press},
  year      = {1993},
  isbn      = {0-89791-593-3},
  pages     = {26-36},
  ee        = {http://doi.acm.org/10.1145/153850.153853, db/conf/pods/Wong93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Strong normalization results are obtained for a general language for collection types. An induced normal form for sets and bags is then used to show that the class of functions whose input has height (that is, the maximal depth of nestings of sets/bags/lists in the complex object) at most i and output has height at most o definable in a nested relational query language without powerset operator is independent of the height of intermediate expressions used. Our proof holds regardless of whether the language is used for querying sets, bags, or lists, even in the presence of variant types. Moreover, the normal forms are useful in a general approach to query optimization. Paredaens and Van Gucht proved a similar result for the special case when i = o = 1. Their result is complemented by Hull and Su who demonstrated the failure of independence when powerset operator is present and i = o = 1. The theorem of Hull and Su was generalized to all i and o by Grumbach and Vianu. Our result generalizes Paredaens and Van Gucht's to all i and o, providing a counterpart to the theorem of Grumbach and Vianu.

Copyright © 1993 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 Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC. ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX

Online Edition: ACM Digital Library

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

Journal Version

Limsoon Wong: Normal Forms and Conservative Extension Properties for Query Languages over Collection Types. J. Comput. Syst. Sci. 52(3): 495-505(1996) BibTeX

References

[1]
Serge Abiteboul, Catriel Beeri, Marc Gyssens, Dirk Van Gucht: An Introduction to the Completeness of Languages for Complex Objects and Nested Relations. NF² 1987: 117-138 BibTeX
[2]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[3]
Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX
[4]
Val Tannen, Peter Buneman, Shamim A. Naqvi: Structural Recursion as a Query Language. DBPL 1991: 9-19 BibTeX
[5]
Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX
[6]
Val Tannen, Peter Buneman, Limsoon Wong: Naturally Embedded Query Languages. ICDT 1992: 140-154 BibTeX
[7]
Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38 BibTeX
[8]
...
[9]
Marc Gyssens, Dirk Van Gucht: A Comparison between Algebraic Query Languages for Flat and Nested Databases. Theor. Comput. Sci. 87(2): 263-286(1991) BibTeX
[10]
...
[11]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
[12]
Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984) BibTeX
[13]
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
[14]
Eugenio Moggi: Notions of Computation and Monads. Inf. Comput. 93(1): 55-92(1991) BibTeX
[15]
Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX
[16]
Jan Paredaens, Dirk Van Gucht: Converting Nested Algebra Expressions into Flat Algebra Expressions. ACM Trans. Database Syst. 17(1): 65-93(1992) BibTeX
[17]
...
[18]
...
[19]
Philip W. Trinder: Comprehensions, a Query Notation for DBPLs. DBPL 1991: 55-68 BibTeX
[20]
...
[21]
...
[22]
...
[23]
...
[24]
...
[25]
...
[26]
...
[27]
...

Referenced by

  1. Peter Buneman, Sanjeev Khanna, Wang Chiew Tan: Why and Where: A Characterization of Data Provenance. ICDT 2001: 316-330
  2. Leonidas Fegaras: Query Unnesting in Object-Oriented Databases. SIGMOD Conference 1998: 49-60
  3. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  4. Catriel Beeri, Tova Milo, Paula Ta-Shma: Towards a Language for the Fully Generic Queries. DBPL 1997: 239-259
  5. Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16
  6. Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995)
  7. Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
  8. Dan Suciu, Limsoon Wong: On Two Forms of Structural Recursion. ICDT 1995: 111-124
  9. Leonidas Fegaras, David Maier: An Algebraic Framework for Physical OODB Design. DBPL 1995: 9
  10. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  11. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  12. Dan Suciu, Val Tannen: A Query Language for NC. PODS 1994: 167-178
  13. Dan Suciu, Jan Paredaens: Any Algorithm in the Complex Object Algebra with Powerset Needs Exponential Space to Compute Transitive Closure. PODS 1994: 201-209
  14. Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
  15. Gerd G. Hillebrand, Paris C. Kanellakis: Functional Database Query Languages as Typed Lambda Calculi of Fixed Order. PODS 1994: 222-231
  16. Dan Suciu: Bounded Fixpoints for Complex Objects. DBPL 1993: 263-281
  17. Leonid Libkin, Limsoon Wong: Aggregate Functions, Conservative Extensions, and Linear Orders. DBPL 1993: 282-294
  18. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
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:07 2009