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

An Extended Relational Algebra with Control over Duplicate Elimination.

Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123
@inproceedings{DBLP:conf/pods/DayalGK82,
  author    = {Umeshwar Dayal and
               Nathan Goodman and
               Randy H. Katz},
  title     = {An Extended Relational Algebra with Control over Duplicate Elimination},
  booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
               March 29-31, 1982, Los Angeles, California},
  publisher = {ACM},
  year      = {1982},
  pages     = {117-123},
  ee        = {http://doi.acm.org/10.1145/588111.588132, db/conf/pods/DayalGK82.html},
  crossref  = {DBLP:conf/pods/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In the pure relational model, duplicate tuples are automatically eliminated. Some real world languages such as DAPLEX, however, give users control over duplicate elimination. This paper extends the relational model to include multiset relations, i.e., relations with duplicate tuples. It considers three formalisms for expressing queries in this model: extended relational algebra, tableaux, and DAPLEX. It shows that, as in the original algebra, the equivalence problem for conjunctive expressions in the extended algebra can be solved using tableaux, and is NP-complete. Finally, it demonstrates that the extended algebra and DAPLEX have essentially the same expressiveness relative to conjunctive expressions.

Copyright © 1982 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 ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California. ACM 1982
Contents BibTeX

Online Edition: ACM Digital Library

References

[ASU1]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
[ASU2]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX
[Cham]
...
[Chen]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[HSW]
...
[Ship]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

Referenced by

  1. Praveen Seshadri, Joseph M. Hellerstein, Hamid Pirahesh, T. Y. Cliff Leung, Raghu Ramakrishnan, Divesh Srivastava, Peter J. Stuckey, S. Sudarshan: Cost-Based Optimization for Magic: Algebra and Implementation. SIGMOD Conference 1996: 435-446
  2. Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995)
  3. Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
  4. Surajit Chaudhuri, Kyuseok Shim: Including Group-By in Query Optimization. VLDB 1994: 354-366
  5. Stéphane Grumbach, Tova Milo: Towards Tractable Algebras for Bags. PODS 1993: 49-58
  6. Surajit Chaudhuri, Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993: 59-70
  7. Stéphane Grumbach, Tova Milo, Yoram Kornatzky: Calculi for Bags and their Complexity. DBPL 1993: 65-79
  8. Umeshwar Dayal, Gene T. J. Wuu: A Uniform Approach to Processing Temporal Queries. VLDB 1992: 407-418
  9. Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219
  10. Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167
  11. Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
  12. D. Jagannathan, R. L. Guck, B. L. Fritchman, J. P. Thompson, D. M. Tolbert: SIM: A Database System Based on the Semantic Data Model. SIGMOD Conference 1988: 46-55
  13. Kazimierz Subieta, Wiktor Rzeczkowski: Query Optimization by Stored Queries. VLDB 1987: 369-380
  14. Umeshwar Dayal: Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers. VLDB 1987: 197-208
  15. Fred J. Friedman, Arthur M. Keller, John Salasin, Gio Wiederhold, Murray R. Berkowitz, David L. Spooner: Reference Model for Ada Interfaces to Database Management Systems. ICDE 1986: 492-506
  16. Kazimierz Subieta, Marek Missala: Semantics of Query Languages for the Entity-Relationship Model. ER 1986: 197-216
  17. Aviel Klausner, Nathan Goodman: Multirelations - Semantice and Languages. VLDB 1985: 251-258
  18. Christine Parent, Stefano Spaccapietra: An Entity-Relationship Algebra. ICDE 1984: 500-507
  19. Stefano Ceri, Giuseppe Pelagatti: Correctness of Query Execution Strategies in Distributed Databases. ACM Trans. Database Syst. 8(4): 577-607(1983)
  20. Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353
  21. Umeshwar Dayal, Nathan Goodman: Query Optimization for CODASYL Database Systems. SIGMOD Conference 1982: 138-150
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:33:39 2009