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

Towards Tractable Algebras for Bags.

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58
@inproceedings{DBLP:conf/pods/GrumbachM93,
  author    = {St{\'e}phane Grumbach and
               Tova Milo},
  title     = {Towards Tractable Algebras for Bags},
  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     = {49-58},
  ee        = {http://doi.acm.org/10.1145/153850.153855, db/conf/pods/GrumbachM93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Bags, i.e. sets with duplicates, are often used to implement relations in database systems. In this paper we study the expressive power of algebras for manipulating bags. The algebra we present is a simple extension of the nested relation algebra. Our aim is to investigate how the use of bags in the language extends its expressive power, and increases its complexity. We consider two main issues, namely (i) the relationship between the depth of bag nesting and the expressive power, and (ii) the relationship between the algebraic operations, and their complexity and expressive power. We show that the bag algebra is more expressive than the nested relation algebra (at all levels of nesting), and that the difference may be subtle. We establish a hierarchy based on the structure of algebra expressions. This hierarchy is shown to be highly related to the properties of the powerset operator.

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, 997 KB]

Journal Version

Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. J. Comput. Syst. Sci. 52(3): 570-588(1996) BibTeX

References

[AB87]
Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
[AFS89]
...
[Alb91]
Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219 BibTeX
[BK90]
Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88 BibTeX
[BM92]
Catriel Beeri, Tova Milo: Functional and Predicative Programming in OODB's. PODS 1992: 176-190 BibTeX
[BM93]
Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386 BibTeX
[BP91]
Jan Van den Bussche, Jan Paredaens: The Expressive Power of Structured Values in Pure OODB's. PODS 1991: 291-299 BibTeX
[BTS91]
Val Tannen, Ramesh Subrahmanyam: Logical and Computational Aspects of Programming with Sets/Bags/Lists. ICALP 1991: 60-75 BibTeX
[CDV88]
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 BibTeX
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[DGK82]
Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123 BibTeX
[Fag75]
...
[FGT93]
Guy Fayolle, Stéphane Grumbach, Christophe Tollu: Asymptotic Probabilities of Languages with Generalized Quantifiers. LICS 1993: 199-207 BibTeX
[Fis87]
Daniel H. Fishman, David Beech, H. P. Cate, E. C. Chow, Tim Connors, J. W. Davis, Nigel Derrett, C. G. Hoch, William Kent, Peter Lyngbæk, Brom Mahbod, Marie-Anne Neimat, T. A. Ryan, Ming-Chien Shan: Iris: An Object-Oriented Database Management System. ACM Trans. Inf. Syst. 5(1): 48-69(1987) BibTeX
[GT82]
Stéphane Grumbach, Christophe Tollu: Query Languages with Counters. ICDT 1992: 124-139 BibTeX
[GV90]
Stéphane Grumbach, Victor Vianu: Playing Games with Objects. ICDT 1990: 25-38 BibTeX
[GV91]
Stéphane Grumbach, Victor Vianu: Tractable Query Languages for Complex Object Databases. PODS 1991: 315-327 BibTeX
[HM81]
Michael Hammer, Dennis McLeod: Database Description with SDM: A Semantic Database Model. ACM Trans. Database Syst. 6(3): 351-386(1981) BibTeX
[HS88]
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. PODS 1988: 39-51 BibTeX
[HS89]
Richard Hull, Jianwen Su: Untyped Sets, Invention, and Computable Queries. PODS 1989: 347-359 BibTeX
[IL90]
...
[KG85]
Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258 BibTeX
[KV92]
Phokion G. Kolaitis, Jouko A. Väänänen: Generalized Quantifiers and Pebble Games on Finite Structures. LICS 1992: 348-359 BibTeX
[MD86]
Frank Manola, Umeshwar Dayal: PDM: An Object-Oriented Data Model. OODBS 1986: 18-25 BibTeX
[Mum90]
Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277 BibTeX
[PvG88]
Jan Paredaens, Dirk Van Gucht: Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions. PODS 1988: 29-38 BibTeX

Referenced by

  1. Tok Wang Ling, Ye Liu: An Efficient View Maintenance Algorithm for Data Warehousing. ER Workshops 1998: 169-180
  2. Latha S. Colby, Leonid Libkin: Tractable Iteration Mechanisms for Bag Languages. ICDT 1997: 461-475
  3. Leonid Libkin, Rona Machlin, Limsoon Wong: A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conference 1996: 228-239
  4. Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480
  5. Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339
  6. Leonid Libkin: Normalizing Incomplete Databases. PODS 1995: 219-230
  7. Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207
  8. Leonid Libkin: Query Language Primitives for Programming with Incomplete Databases. DBPL 1995: 6
  9. Val Tannen: Tutorial: Languages for Collection Types. PODS 1994: 150-154
  10. Leonid Libkin, Limsoon Wong: New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions. PODS 1994: 155-166
  11. Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189
  12. Catriel Beeri, Tova Milo: On the Power of Algebras with Recursion. SIGMOD Conference 1993: 377-386
  13. Leonid Libkin, Limsoon Wong: Some Properties of Query Languages for Bags. DBPL 1993: 97-114
  14. Stéphane Grumbach, Tova Milo, Yoram Kornatzky: Calculi for Bags and their Complexity. DBPL 1993: 65-79
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