Towards tractable algebras for bags

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.

REFERENCES

• AB87: Papers from the Workshop ``Theory and Applications of Nested Relations and Complex Objects' on Nested Relations and Complex Objects, April 1987
• AFS89: S. Abiteboul , P. C. Fischer , H. -J. Schek, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• Alb91: Joseph Albert, Algebraic Properties of Bag Data Types, Proceedings of the 17th International Conference on Very Large Data Bases, p.211-219, September 03-06, 1991
• BK90: Catriel Beeri , Yoram Kornatzky, Algebraic optimization of object-oriented query languages, Proceedings of the third international conference on database theory on Database theory, p.72-88, November 1990, Paris, France
• BM92: Catriel Beeri , Tova Milo, Functional and predictive programming in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.176-190, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137863]
• BM93: Catriel Beeri , Tova Milo, On the power of algebras with recursion, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.377-387, May 25-28, 1993, Washington, D.C., United States
• BP91: Jan Van den Bussche , Jan Paredaens, The expressive power structured values in pure OODB's (extended abstract), Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.291-299, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113440]
• BTS91: Val Breazu-Tannen , Ramesh Subrahmanyam, Logical and computational aspects of programming with sets/bags/lists, Proceedings of the 18th international colloquium on Automata, languages and programming, p.60-75, June 1991, Madrid, Spain
• CDV88: Michael J. Carey , David J. DeWitt, A data model and query language for EXODUS, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.413-423, June 01-03, 1988, Chicago, Illinois, United States
• CH80: A. Chandra and D. Harel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences, 21(2):156- 178, Oct. 1980.
• DGK82: Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
• Fag75: R. Fagin. Monadic generalized spectra. Zeitschrift fur Mathematische Logik and Grand. der Math., 21:89-96, 1975.
• FGT93: G. Fayolle, S. Grumbach, and C. Tollu. Asymptotic probabilities of languages with generalized quantifiers. In Proc. IEEE Syrup. of Logic in Computer Science, Montreal, June 1993.
• Fis87: D.H. Fishman. et al. Iris: An object oriented database management system. In A CM Trans. Office Information Systems, 5:1, 1987.
• GT92: Stéphane Grumbach , Christophe Tollu, Query Languages with Counters, Proceedings of the 4th International Conference on Database Theory, p.124-139, October 14-16, 1992
• GV90: Stéphane Grumbach , Victor Vianu, Playing games with objects, Proceedings of the third international conference on database theory on Database theory, p.25-38, November 1990, Paris, France
• GV91: Stéphane Grumbach , Victor Vianu, Tractable query languages for complex object databases, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.315-327, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113442]
• HM81: Michael Hammer , Dennis Mc Leod, Database description with SDM: a semantic database model, ACM Transactions on Database Systems (TODS), v.6 n.3, p.351-386, Sept. 1981 [doi>10.1145/319587.319588]
• HS88: Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.39-51, March 1988, Austin, Texas, United States [doi>10.1145/308386.308409]
• HS89: R. Hull , J. Su, Untyped sets, invention, and computable queries, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.347-359, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73755]
• IL90: N. Immerman and E. Lander. Complexity Theory Retrospective, chapter Describing Graphs : A First-Order Approach to Graph Canonization, pages 59-81. Springer Verlag, Ed. A. Selman, 1990.
• KG85: A. Klausner and N. Goodman. Multirelations semantics and languages. In Proc. 11th Intl. Conf. on Very Large Databases, Stockholm, Sweden, 1985.
• KV92: P. Kolaitis and J.A. V#in#nen. Generalized quantifiers and pebble games on finite structures. In Proc. 7th Syrup. of Logic in Computer Science, 1992.
• MD86: Frank Manola , Umeshwar Dayal, PDM: an object-oriented data model, Proceedings on the 1986 international workshop on Object-oriented database systems, p.18-25, September 23-26, 1986, Pacific Grove, California, United States
• Mum90: Inderpal Singh Mumick , Hamid Pirahesh , Raghu Ramakrishnan, The magic of duplicates and aggregates, Proceedings of the sixteenth international conference on Very large databases, p.264-277, September 1990, Brisbane, Australia
• PvG88: Jan Paredaens , Dirk Van Gucht, Possibilities and limitations of using flat operators in nested algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.29-38, March 1988, Austin, Texas, United States [doi>10.1145/308386.308402]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Data manipulation languages (DML)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema; Data models

General Terms:
Design, Languages, Theory, Verification