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},
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},
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}
}
BibTeX
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 ...
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
References
- [1]
- Serge Abiteboul, Catriel Beeri:
The Power of Languages for the Manipulation of Complex Values.
VLDB J. 4(4): 727-794(1995) BibTeX
- [2]
- Serge Abiteboul, Paris C. Kanellakis:
Object Identity as a Query Language Primitive.
SIGMOD Conference 1989: 159-173 BibTeX
- [3]
- Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979) BibTeX
- [4]
- François Bancilhon:
Object-Oriented Database Systems.
PODS 1988: 152-162 BibTeX
- [5]
- François Bancilhon, Sophie Cluet, Claude Delobel:
A Query Language for the O2 Object-Oriented Database System.
DBPL 1989: 122-138 BibTeX
- [6]
- Jay Banerjee, Won Kim, Kyung-Chang Kim:
Queries in Object-Oriented Databases.
ICDE 1988: 31-38 BibTeX
- [7]
- Catriel Beeri, Yoram Kornatzky:
Algebraic Optimization of Object-Oriented Query Languages.
ICDT 1990: 72-88 BibTeX
- [8]
- Alexander Borgida:
Type Systems for Querying Class Hierarchies with Non-strict Inheritance.
PODS 1989: 394-400 BibTeX
- [9]
- Michael J. Carey, David J. DeWitt, Scott L. Vandenberg:
A Data Model and Query Language for EXODUS.
SIGMOD Conference 1988: 413-423 BibTeX
- [10]
- ...
- [11]
- Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90 BibTeX
- [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 BibTeX
- [13]
- E. F. Codd:
Extending the Database Relational Model to Capture More Meaning.
ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
- [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) BibTeX
- [15]
- Goetz Graefe, David Maier:
Query Optimization in Object-Oriented Database Systems: A Prospectus.
OODBS 1988: 358-363 BibTeX
- [16]
- ...
- [17]
- Richard Hull, Masatoshi Yoshikawa:
ILOG: Declarative Creation and Manipulation of Object Identifiers.
VLDB 1990: 455-468 BibTeX
- [18]
- Richard Hull, Masatoshi Yoshikawa:
On the Equivalence of Database Restructurings Involving Object Identifiers.
PODS 1991: 328-340 BibTeX
- [19]
- Michael Kifer, Georg Lausen, James Wu:
Logical Foundations of Object-Oriented and Frame-Based Languages.
J. ACM 42(4): 741-843(1995) BibTeX
- [20]
- Won Kim:
A Model of Queries for Object-Oriented Databases.
VLDB 1989: 423-432 BibTeX
- [21]
- ...
- [22]
- Henry F. Korth:
Optimization of Object-Retrieval Queries.
OODBS 1988: 352-357 BibTeX
- [23]
- Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb:
The ObjectStore Database System.
Commun. ACM 34(10): 50-63(1991) BibTeX
- [24]
- Christophe Lécluse, Philippe Richard:
Manipulation of Structured Values in Object-Oriented Databases.
DBPL 1989: 113-121 BibTeX
- [25]
- David Maier, Jacob Stein, Allen Otis, Alan Purdy:
Development of an Object-Oriented DBMS.
OOPSLA 1986: 472-482 BibTeX
- [26]
- ...
- [27]
- ...
- [28]
- Sylvia L. Osborn:
Identity, Equality and Query Optimization.
OODBS 1988: 346-351 BibTeX
- [29]
- Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
J. ACM 27(4): 633-655(1980) BibTeX
- [30]
- Gail M. Shaw, Stanley B. Zdonik:
Object-Oriented Queries: Equivalence and Optimization.
DOOD 1989: 281-295 BibTeX
- [31]
- Gail M. Shaw, Stanley B. Zdonik:
An Object-Oriented Query Algebra.
DBPL 1989: 103-112 BibTeX
- [32]
- Jeffrey D. Ullman:
Database Theory: Past and Future.
PODS 1987: 1-10 BibTeX
- [33]
- 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
- Yannis Papakonstantinou, Vasilis Vassalos:
Query Rewriting for Semistructured Data.
SIGMOD Conference 1999: 455-466
- Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini:
On the Decidability of Query Containment under Constraints.
PODS 1998: 149-158
- Alon Y. Levy, Dan Suciu:
Deciding Containment for Queries with Complex Objects.
PODS 1997: 20-31
- Marc Andries, Luca Cabibbo, Jan Paredaens, Jan Van den Bussche:
Applying an Update Method to a Set of Receivers.
PODS 1995: 208-218
- Martin Buchheit, Manfred A. Jeusfeld, Werner Nutt, Martin Staudt:
Subsumption between Queries to Object-Oriented Databases.
EDBT 1994: 15-22
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:34:06 2009