Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.

Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167
  author    = {Scott L. Vandenberg and
               David J. DeWitt},
  editor    = {James Clifford and
               Roger King},
  title     = {Algebraic Support for Complex Objects with Arrays, Identity,
               and Inheritance},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {158-167},
  ee        = {, db/conf/sigmod/VandenbergD91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP,}


Algebraic query processing and optimization for relational databases is a proven and reasonably well-understood technology. Recently the algebraic approach has been extended to more advanced data models (nested relations, complex objects, object-oriented systems). Here we continue this evolution by presenting novel algebraic operators and transformations supporting grouping, arrays, references, and multisets. We also propose a new approach to processing and optimizing overridden methods in the presence of multiple inheritance. The utility of both the algebraic operators and the transformation rules is demonstrated with examples. Object identity is incorporated into the algebraic domains, giving an original, intuitive set-theoretic semantics for the domains of object identifiers in the presence of multiple inheritance. We prove that the algebra is equripollent to the QUEL-like user-level query language and discuss some other expressiveness issues.

Copyright © 1991 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

James Clifford, Roger King (Eds.): Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991. ACM Press 1991 BibTeX , SIGMOD Record 20(2), June 1991

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1133 KB]


Serge Abiteboul, Catriel Beeri: The Power of Languages for the Manipulation of Complex Values. VLDB J. 4(4): 727-794(1995) BibTeX
Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173 BibTeX
Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Won Kim, Darrell Woelk, Nat Ballou, Hyoung-Joo Kim: Data Model Issues for Object-Oriented Applications. ACM Trans. Inf. Syst. 5(1): 3-26(1987) BibTeX
Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88 BibTeX
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123 BibTeX
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 BibTeX
Ralf Hartmut Güting, Roberto Zicari, David M. Choy: An Algebra for Structured Office Documents. ACM Trans. Inf. Syst. 7(2): 123-157(1989) BibTeX
Marc Gyssens, Dirk Van Gucht: The Powerset Algebra as a Result of Adding Programming Constructs to the Nested Relational Algebra. SIGMOD Conference 1988: 225-232 BibTeX
Abraham Silberschatz, Henry F. Korth: Database System Concepts, 1st Edition. McGraw-Hill Book Company 1986, ISBN 0-07-100529-3
Sylvia L. Osborn: Identity, Equality and Query Optimization. OODBS 1988: 346-351 BibTeX
Joan Peckham, Fred J. Maryanski: Semantic Data Models. ACM Comput. Surv. 20(3): 153-189(1988) BibTeX
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
Marc H. Scholl: Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations. ICDT 1986: 380-396 BibTeX
Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX
Eugene J. Shekita, Michael J. Carey: Performance Enhancement Through Replication in an Object-Oriented DBMS. SIGMOD Conference 1989: 325-336 BibTeX
Abdullah Uz Tansel, Lucy Garnett: Nested Historical Relations. SIGMOD Conference 1989: 284-294 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Stefan Deßloch, Theo Härder, Nelson Mendonça Mattos, Bernhard Mitschang, Joachim Thomas: Advanced Data Processing in KRISYS: Modeling Concepts, Implementation Techniques, and Client/Server Issues. VLDB J. 7(2): 79-95(1998)
  2. Staffan Flodin, Kjell Orsborn, Tore Risch: Using Queries with Multi-Directional Functions for Numerical Database Applications. ADBIS 1998: 58-70
  3. Alexandra Poulovassilis, Carol Small: Algebraic Query Optimisation for Database Programming Languages. VLDB J. 5(2): 119-132(1996)
  4. Dan Suciu: Implementation and Analysis of a Parallel Collection Query Language. VLDB 1996: 366-377
  5. Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: The Design and Implementation of a Sequence Database System. VLDB 1996: 99-110
  6. Leonid Libkin, Rona Machlin, Limsoon Wong: A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques. SIGMOD Conference 1996: 228-239
  7. Mitch Cherniack, Stanley B. Zdonik: Rule Languages and Internal Algebras for Rule-Based Optimizers. SIGMOD Conference 1996: 401-412
  8. Dave D. Straube, M. Tamer Özsu: Query Optimization and Execution Plan Generation in Object-Oriented Data Management Systems. IEEE Trans. Knowl. Data Eng. 7(2): 210-227(1995)
  9. Staffan Flodin, Tore Risch: Processing Object-Oriented Queries with Invertible Late Bound Functions. VLDB 1995: 335-344
  10. Leonidas Fegaras, David Maier: Towards an Effective Calculus for Object Query Languages. SIGMOD Conference 1995: 47-58
  11. Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35
  12. Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases. ICDE 1995: 80-89
  13. Martin Gogolla: A Declarative Query Approach to Object Identification. OOER 1995: 65-76
  14. Peter Baumann: Management of Multidimensional Discrete Data. VLDB J. 3(4): 401-444(1994)
  15. Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533
  16. Alexandra Poulovassilis, Carol Small: Investigation of Algebraic Query Optimisation Techniques for Database Programming Languages. VLDB 1994: 415-426
  17. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  18. Joachim Thomas, Stefan Deßloch: A Plan-Operator Concept for Client-Based Knowledge Progressing. VLDB 1993: 555-566
  19. Ralf Hartmut Güting: Second-Order Signature: A Tool for Specifying Data Models, Query Processing, and Optimization. SIGMOD Conference 1993: 277-286
  20. José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296
  21. David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16
  22. Vijay M. Sarathy, Lawrence V. Saxton, Dirk Van Gucht: Algebraic Foundation and Optimization for Object Based Query Languages. ICDE 1993: 81-90
  23. Goetz Graefe, William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993: 209-218
  24. Reda Alhajj, M. Erol Arkun: A Query Model for Object-Oriented Databases. ICDE 1993: 163-172
  25. Moira C. Norrie: An Extended Entity-Relationship Approach to Data Management in Object-Oriented Systems. ER 1993: 390-401
  26. Janet L. Wiener, Yannis E. Ioannidis: A Moose and a Fox Can Aid Scientists with Data Management Problems. DBPL 1993: 376-398
  27. Bennet Vance: An Abstract Object-Oriented Query Execution Language. DBPL 1993: 176-199
  28. Bharathi Subramanian, Stanley B. Zdonik, Theodore W. Leung, Scott L. Vandenberg: Ordered Types in the AQUA Data Model. DBPL 1993: 115-135
  29. Theodore W. Leung, Gail Mitchell, Bharathi Subramanian, Bennet Vance, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Data Model and Algebra. DBPL 1993: 157-175
  30. Sophie Cluet, Guido Moerkotte: Nested Queries in Object Bases. DBPL 1993: 226-242
  31. Minoru Ito, Michio Nakanishi: On Deriving Specialization Constraints over Complex Objects. DASFAA 1993: 335-342
  32. Joel E. Richardson: Supporting Lists in a Data Model (A Timely Approach). VLDB 1992: 127-138
  33. Seymour Ginsburg, Xiaoyang Sean Wang: Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. PODS 1992: 293-300
  34. Catriel Beeri: New Data Models and Languages - the Challenge. PODS 1992: 1-15
  35. L. Edwin McKenzie, Richard T. Snodgrass: Evaluation of Relational Algebras Incorporating the Time Dimension in Databases. ACM Comput. Surv. 23(4): 501-543(1991)
  36. Joseph Albert: Algebraic Properties of Bag Data Types. VLDB 1991: 211-219
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:40:05 2009