Edward P. F. Chan
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.
- 1.Abiteboul, S. and Beeri, C., "On the Power of Languages for the Manipulation of Complex Objects," Technical Report 846, INRIA, May 1988.Google Scholar
- 2.Abiteboul, S. and Kanellakis, P., "Object Identity as a Query Language Primitive," Proceedzngs of 1989 A CM SIGMOD, Portland, Oregon, pp. 159-173. Also appears as Technical Report 1022, INRIA, April 1989. Google Scholar
- 3.Aho, A.V., Sagiv, Y. and Ullman, J.D., "Equivalence of Relational Expressions," SIAM J. of Computing 8(2), 1979, pp. 218-246.Google ScholarDigital Library
- 4.Bancilhon, F., "Object-Oriented Database Systems," Proceedings of the 7th A CM Symposium on Principles of Database Systems, Austin, Texas, 1988, pp. 152-162. Google ScholarDigital Library
- 5.Bancilhon, F., Cluet, S. and Delobel, C., "A Query Language for the 02 Object-Oriented Database System," Proceedings of the 2th International Workshop on Database Programming Languages (Hull, R., Morrison, R. and Stemple, D., Eds.), Morgan Kaufmann Publishers Inc., San Mateo, Cal., 1990, pp. 122-138. Google ScholarDigital Library
- 6.Banerjee, J., Kim, W., and Kim, K.C., "Queries in Object-Oriented Databases," Proceedings of the #th International Conference on Data Engineering, Feb. 1988, pp. 31-38. Google ScholarDigital Library
- 7.Beeri, C. and Kornatzky, Y, "Algebraic Optimization of Object-Oriented Query Languages," Proceedings of the 3th International Conference on Database Theory, Paris, France, Lecture Notes in Computer Science 470, December 1990, Springer-Verlag, pp. 72-88. Google ScholarDigital Library
- 8.Borgida, A. "Type Systems for Querying Class Hierarchies with Non Strict Inheritance" Proceedings of the 8th A CM Sympos,um on Principles of Database Systems, Philadelphia, Penn- #ylvanla, 1989, pp. 394-401. Google ScholarDigital Library
- 9.Carey, M.J., DeWitt, D.J. and Vandenberg, S.L., "A Data Model and Query Language for EXODUS," Proceedings of the ACM SIGMOD, Chicago, 1988, pp. 413-423. Google ScholarDigital Library
- 10.Chan, E.P.F., "Testing Satisfiability of a Class of Object-Oriented Conjunctive Queries," Department of Computer Science, University of Waterloo, Technical Report, 1992.Google Scholar
- 11.Chandra, A. and Merlin, P.M., "Optimal Implementation of Conjunctive Queries in Relational Databases," Proceedings of the 9th A CM Symposium on Theory of Computing, 1977, pp. 77-90. Google ScholarDigital Library
- 12.Cluet, S., Delobel, C., Lecluse, C. and Richard, P., "Reloop, an Algebra Based Query Language," Proceedings of the 1st International Conference on Deductive and Object-Oriented Databases (Kim. W., Nicolas, J-M and Nishio, S., Eds), Kyoto, Japan, December 1989, pp. 294- 313.Google Scholar
- 13.Codd, E.F., "Extending the Data Base Relational Model to Capture More Meaning," A CM Transactions on Database Systems, #(#), December 1979, pp. 397-434. Google ScholarDigital Library
- 14.Fisher, D.H., Beech, D., Care, H.P., Chow, E.C., Connors, T., Davis, J.W., Derrette, N., Hoch, C.G., Kent, W., Lyngbaek, P., Mahbod, B., Neimat, M.A., Ryan, T.A., and Shah, M.C., "IRIS" An Object-Oriented Database Management System," A CM Transactzons on Office Informat,on Systems, 1(5), January 1987, pp. 48- 69.Google Scholar
- 15.Graefe, G and Maier, D., "Query Optimization in Object-Oriented Database Systesm: A Prospectus," Advances in Object-Oriented Database Systems (K.R. Dittrich, Ed.), Lecture Notes in Computer Science 334, 1988, Springer- Verlag, pp. 358-362. Google ScholarDigital Library
- 16.Hull, R., "A Survey of Theoretical Research on Typed Complex Database Objects," Dalabases (J. Paredaens, Ed.), Academic Press, London, UK., 1987, pp. 193-256. Google ScholarDigital Library
- 17.Hull, R. and Yoshikawa, M., "ILOG" Declarative Creation and Manipulation of Object Identifiers (Extended Abstract)," Proceedings of 16th lurernational Conference on Very Large Data Bases, Morgan Kaufmann, Los Altos, CA, 1990, pp. 455-468. Google ScholarDigital Library
- 18.Hull, R. and Yo#hikawa, M., "On the Equivalence of Database Restructurings Involving Object Identifiers (Extended Abstract)," Proceedings of the l Oth A CM Symposium on Prznczples of Dalabase Systems, Denver, Colorado, 1991, pp. 328-340. Google ScholarDigital Library
- 19.Kifer, M., Lausen, G. and Wu, J., "Logical Foundations of Object-Oriented and Frame-based Languages," Technical Report 90/14 (revised), SUNY at Stony Brook, June 1990. To appear in JA CM.Google Scholar
- 20.Kim, W., "A Model of Queries for Object- Oriented Databases," Proceedzngs of the 15th International Conference on Very Large Data Bases (Apers &# Wiederhold Eds), August 1989, Amsterdam, the Netherlands, Morgan Kauffman, CA. Google ScholarDigital Library
- 21.Kim, W., Introduction lo Object-Omented Databases, MIT Press, Cambridge, Massachusetts, 1990. Google ScholarDigital Library
- 22.Korth, H.F., "Optimization of Object-Retreival Query," Advances in Object-Oriented Database Systems (K.R. Dittrich, Ed.) Lecture Notes in Computer Science 334, 1988, Springer-Verlag, pp. 352-357. Google ScholarDigital Library
- 23.Lamb, C., Landis, G., Orenstein, J. and Weinfeb, D., "The ObjectStore Database System," CACM 34(10), October 1991, pp. 50-63. Google ScholarDigital Library
- 24.Lecluse, C., Richard, P., "Manipulation of Structured Values in Object-Oriented Database System," Proceedings of #he 2th International Workshop on Database Programming Languages (Hull, R., Morrison, R. and Stemple, D., Eds.), Morgan Kaufmann Publishers Inc., San Mateo, Cal., 1990, pp. 113-121. Google ScholarDigital Library
- 25.Maier, D., Stein, J.C., Otis, A. and Purdy, A., "Development of an Object-Oriented DBMS," Proceedings of OOPSLA '86, Portland, Oregan, Sept. 1986, pp. 472-482, ACM, New York. Google ScholarDigital Library
- 26.Ontos Object Database Programmer's Guide, Ontologic, Inc., Burlington, MA, 1989.Google Scholar
- 27.The 02 Programmer Manual, 02 Technology, 1991.Google Scholar
- 28.Osborn, S.L., "Identity, Equality and Query Optimization," Advances in Object-Omcnted Database Systems (K.R. Dittrich, Ed.), Lecture Notes in Computer Science 334, 1988, Springer- Verlag, pp. 346-351. Google ScholarDigital Library
- 29.Sagiv, Y. and Yannakakis, M., "Equivalence Among Relational Expressions with the Union and Difference Operators," JACM 27(#), October 1980, pp. 633-655. Google ScholarDigital Library
- 30.Shaw, G. and Zdonik, S., "OO queries: Equivalence and Optimization," Proceedings of #he 1st International Conference on Deductive and Object-Omented Databases, (Kim. W., Nicolas, J-M and Nishio, S., Eds), Kyoto, japan, December 1989, pp. 264-278.Google Scholar
- 31.Shaw, G.M. and Zdonik, S.B., "An Object- Oriented Query Algebra," Proceedings of the 2th Internal,onal Workshop on Database Programming Languages, (Hull, R., Morrison, R. and Stemple, D., Eds.), Morgan Kaufmann Publishers Inc., San Mateo, Cal., 1990, pp. 103-112. Google ScholarDigital Library
- 32.Ullman, J.D., "Database Theory-Past and Future," Proceedings of the 5th A CM Symposium on Principles of Database Systems, San Diego, CA, 1987, pp.l-10. Google ScholarDigital Library
- 33.Ullman, J.D., Princzples of Database and Knowledge-base Systems, Vol. I, Computer Science Press, l#ockville, Maryland, 1988. Google ScholarDigital Library
Index Terms
- Containment and minimization of positive conjunctive queries in OODB's
Recommendations
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Containment and Optimization of Object-Preserving Conjunctive Queries
In the optimization of queries in an object-oriented database (OODB) 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 ...
Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation
Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing ...
Comments