dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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
@inproceedings{DBLP:conf/pods/Chan92,
  author    = {Edward P. F. Chan},
  editor    = {Moshe Y. Vardi and
               Paris C. Kanellakis},
  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,
               California, USA},
  publisher = {ACM Press},
  year      = {1992},
  isbn      = {0-89791-519-4},
  pages     = {202-211},
  ee        = {db/conf/pods/Chan92.html, http://doi.acm.org/10.1145/137097.137869},
  crossref  = {DBLP:conf/pods/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 ...

Printed Edition

Moshe Y. Vardi, Paris C. Kanellakis (Eds.): Proceedings of the Eleventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 2-4, 1992, San Diego, California, USA. ACM Press 1992, ISBN 0-89791-519-4
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition

Citation Page

References

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

Last update Fri Sep 14 17:28:31 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page