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},
editor = {Catriel Beeri},
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, USA},
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}
}
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 ...
Printed Edition
Catriel Beeri (Ed.):
Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC, USA.
ACM Press 1993, ISBN 0-89791-593-3
Contents 
[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)
References
- [AB87]
- Serge Abiteboul, Catriel Beeri:
The Power of Languages for the Manipulation of Complex Values.
VLDB J. 4(4): 727-794(1995)
- [AFS89]
- ...
- [Alb91]
- Joseph Albert:
Algebraic Properties of Bag Data Types.
VLDB 1991: 211-219
- [BK90]
- Catriel Beeri, Yoram Kornatzky:
Algebraic Optimization of Object-Oriented Query Languages.
ICDT 1990: 72-88
- [BM92]
- Catriel Beeri, Tova Milo:
Functional and Predicative Programming in OODB's.
PODS 1992: 176-190
- [BM93]
- Catriel Beeri, Tova Milo:
On the Power of Algebras with Recursion.
SIGMOD Conference 1993: 377-386
- [BP91]
- Jan Van den Bussche, Jan Paredaens:
The Expressive Power of Structured Values in Pure OODB's.
PODS 1991: 291-299
- [BTS91]
- Val Tannen, Ramesh Subrahmanyam:
Logical and Computational Aspects of Programming with Sets/Bags/Lists.
ICALP 1991: 60-75
- [CDV88]
- Michael J. Carey, David J. DeWitt, Scott L. Vandenberg:
A Data Model and Query Language for EXODUS.
SIGMOD Conference 1988: 413-423
- [CH80]
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases.
J. Comput. Syst. Sci. 21(2): 156-178(1980)
- [DGK82]
- Umeshwar Dayal, Nathan Goodman, Randy H. Katz:
An Extended Relational Algebra with Control over Duplicate Elimination.
PODS 1982: 117-123
- [Fag75]
- ...
- [FGT93]
- Guy Fayolle, Stéphane Grumbach, Christophe Tollu:
Asymptotic Probabilities of Languages with Generalized Quantifiers.
LICS 1993: 199-207
- [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)
- [GT82]
- Stéphane Grumbach, Christophe Tollu:
Query Languages with Counters.
ICDT 1992: 124-139
- [GV90]
- Stéphane Grumbach, Victor Vianu:
Playing Games with Objects.
ICDT 1990: 25-38
- [GV91]
- Stéphane Grumbach, Victor Vianu:
Tractable Query Languages for Complex Object Databases.
PODS 1991: 315-327
- [HM81]
- Michael Hammer, Dennis McLeod:
Database Description with SDM: A Semantic Database Model.
ACM Trans. Database Syst. 6(3): 351-386(1981)
- [HS88]
- Richard Hull, Jianwen Su:
On the Expressive Power of Database Queries with Intermediate Types.
PODS 1988: 39-51
- [HS89]
- Richard Hull, Jianwen Su:
Untyped Sets, Invention, and Computable Queries.
PODS 1989: 347-359
- [IL90]
- ...
- [KG85]
- Aviel Klausner, Nathan Goodman:
Multirelations - Semantice and Languages.
VLDB 1985: 251-258
- [KV92]
- Phokion G. Kolaitis, Jouko A. Väänänen:
Generalized Quantifiers and Pebble Games on Finite Structures.
LICS 1992: 348-359
- [MD86]
- Frank Manola, Umeshwar Dayal:
PDM: An Object-Oriented Data Model.
OODBS 1986: 18-25
- [Mum90]
- Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan:
The Magic of Duplicates and Aggregates.
VLDB 1990: 264-277
- [PvG88]
- Jan Paredaens, Dirk Van Gucht:
Possibilities and Limitations of Using Flat Operators in Nested Algebra Expressions.
PODS 1988: 29-38
Referenced by
- Tok Wang Ling, Ye Liu:
An Efficient View Maintenance Algorithm for Data Warehousing.
ER Workshops 1998: 169-180
- Latha S. Colby, Leonid Libkin:
Tractable Iteration Mechanisms for Bag Languages.
ICDT 1997: 461-475
- Leonid Libkin, Rona Machlin, Limsoon Wong:
A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.
SIGMOD Conference 1996: 228-239
- Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey:
Algorithms for Deferred View Maintenance.
SIGMOD Conference 1996: 469-480
- Timothy Griffin, Leonid Libkin:
Incremental Maintenance of Views with Duplicates.
SIGMOD Conference 1995: 328-339
- Leonid Libkin:
Normalizing Incomplete Databases.
PODS 1995: 219-230
- Stéphane Grumbach, Tova Milo:
An Algebra for Pomsets.
ICDT 1995: 191-207
- Leonid Libkin:
Query Language Primitives for Programming with Incomplete Databases.
DBPL 1995: 6
- Val Tannen:
Tutorial: Languages for Collection Types.
PODS 1994: 150-154
- Leonid Libkin, Limsoon Wong:
New Techniques for Studying Set Languages, Bag Languages and Aggregate Functions.
PODS 1994: 155-166
- Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht:
A Query Language for List-Based Complex Objects.
PODS 1994: 179-189
- Catriel Beeri, Tova Milo:
On the Power of Algebras with Recursion.
SIGMOD Conference 1993: 377-386
- Leonid Libkin, Limsoon Wong:
Some Properties of Query Languages for Bags.
DBPL 1993: 97-114
- Stéphane Grumbach, Tova Milo, Yoram Kornatzky:
Calculi for Bags and their Complexity.
DBPL 1993: 65-79
Last update Fri May 25 08:32:46 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
