Containment and Minimization of Positive Conjunctive Queries in OODB's.

Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211
  author    = {Edward P. F. Chan},
  title     = {Containment and Minimization of Positive Conjunctive Queries
               in OODB's},
  booktitle = {Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 2-4, 1992, San Diego,
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {202-211},
  ee        = {db/conf/pods/Chan92.html,},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP,}


With the availability of high-level declarative query languages in an object-oriented database system (OODB), the burden of choosing an efficient execution plan for a query is transferred from the user to the database system. A natural first step is to use the typing constraints imposed by the schema to transform a query into an equivalent one that logically accesses a minimal set of objects. We propose a class of queries called conjunctive queries for OODB's. A conjunctive query can be expressed as an equivalent union of queries in a special form called terminal conjunctive queries. We first characterize the containment, and hence equivalence, conditions for the class of terminal conjunctive queries. We then study a subclass of conjunctive queries called positive conjunctive queries. We characterize the containment and equivalence conditions, as well as derive an algorithm for finding an exact minimization for the class of positive conjunctive queries. The equivalent minimized query is expressed as a union of terminal positive conjunctive queries with the property that the variable search space is minimal among all the unions of postivie conjunctive queries.

Copyright © 1992 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 Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California. ACM Press 1992, ISBN 0-89791-519-4
Contents BibTeX

Online Edition

Citation Page BibTeX


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
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX
François Bancilhon: Object-Oriented Database Systems. PODS 1988: 152-162 BibTeX
François Bancilhon, Sophie Cluet, Claude Delobel: A Query Language for the O2 Object-Oriented Database System. DBPL 1989: 122-138 BibTeX
Jay Banerjee, Won Kim, Kyung-Chang Kim: Queries in Object-Oriented Databases. ICDE 1988: 31-38 BibTeX
Catriel Beeri, Yoram Kornatzky: Algebraic Optimization of Object-Oriented Query Languages. ICDT 1990: 72-88 BibTeX
Alexander Borgida: Type Systems for Querying Class Hierarchies with Non-strict Inheritance. PODS 1989: 394-400 BibTeX
Michael J. Carey, David J. DeWitt, Scott L. Vandenberg: A Data Model and Query Language for EXODUS. SIGMOD Conference 1988: 413-423 BibTeX
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX
Sophie Cluet, Claude Delobel, Christophe Lécluse, Philippe Richard: Reloop, an Algebra Based Query Language for an Object-Oriented Database System. DOOD 1989: 313-332 BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
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
Goetz Graefe, David Maier: Query Optimization in Object-Oriented Database Systems: A Prospectus. OODBS 1988: 358-363 BibTeX
Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468 BibTeX
Richard Hull, Masatoshi Yoshikawa: On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991: 328-340 BibTeX
Michael Kifer, Georg Lausen, James Wu: Logical Foundations of Object-Oriented and Frame-Based Languages. J. ACM 42(4): 741-843(1995) BibTeX
Won Kim: A Model of Queries for Object-Oriented Databases. VLDB 1989: 423-432 BibTeX
Henry F. Korth: Optimization of Object-Retrieval Queries. OODBS 1988: 352-357 BibTeX
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) BibTeX
Christophe Lécluse, Philippe Richard: Manipulation of Structured Values in Object-Oriented Databases. DBPL 1989: 113-121 BibTeX
David Maier, Jacob Stein, Allen Otis, Alan Purdy: Development of an Object-Oriented DBMS. OOPSLA 1986: 472-482 BibTeX
Sylvia L. Osborn: Identity, Equality and Query Optimization. OODBS 1988: 346-351 BibTeX
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX
Gail M. Shaw, Stanley B. Zdonik: Object-Oriented Queries: Equivalence and Optimization. DOOD 1989: 281-295 BibTeX
Gail M. Shaw, Stanley B. Zdonik: An Object-Oriented Query Algebra. DBPL 1989: 103-112 BibTeX
Jeffrey D. Ullman: Database Theory: Past and Future. PODS 1987: 1-10 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

Referenced by

  1. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
  2. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
  3. Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31
  4. Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche: Applying an Update Method to a Set of Receivers. PODS 1995: 208-218
  5. Martin Buchheit, Manfred A. Jeusfeld, Werner Nutt, Martin Staudt: Subsumption between Queries to Object-Oriented Databases. EDBT 1994: 15-22
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:34:06 2009