Abstract
It is clearly crucial for the success of object—oriented databases to find efficient implementations that improve on the performance of relational systems, rather than being powerful in terms of modeling and features, but just too slow to be used. This paper describes the mapping of COCOON to DASDBS, a nested relational database kernel system, as an example OODBMS mapping to a complex storage system. We describe 1) choices for physical designs that make use of the complex storage model and 2) the generation of efficient, set—oriented execution plans for object—oriented database queries, using rule—based query optimization techniques. We use hierarchical clustering and embedded (sets of) object references, and show how to explore them for efficient path traversals expressed in queries involving complex objects. Prototypes of both, a physical design tool and a query optimizer have been implemented. Preliminary results show feasibility, and execution time improvements of an order of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
O. Deux et al., “The 02 System”, CACM, vol. 34, no. 10, p. 34, October 1991.
C. Beeri, “Formal Models for Object Oriented Databases”, Proc. DOOD, Kyoto, 1989.
E. Bertino, “Optimization of Queries using Nested Indices”, in Proc. EDBT, LNCS, vol. 416, pp. 44–59, Springer 1990.
E. Bertino and W. Kim, “Indexing Techniques for Queries on Nested Objects”, IEEE Trans. on Knowledge and Data Eng., vol. 1, no. 2, p. 196, June 1989.
S. Cluet and C. Delobel, “A General Framework for the Optimization of Object—Oriented Queries”, Proc. SIGMOD, p. 383, San Diego, California., June 1992.
S. Dessloch, T Härder, F.—J. Leick, N.M. Mattos, C. Laasch, C. Rich, M.H. Scholl, and H.—J. Schek, “COCOON and KRISYS: A Comparison”, in Objektbanken far Experten, ed. R. Bayer, T Harder, and P.C. Lockemann, Informatik Aktuell, Springer Verlag, 1992.
G. Graefe, “Volcano, An Extensible and Parallel Dataflow Query Processing System”, July 1990, to appear in IEEE Trans. Knowledge and Data Engineering.
G. Graefe and D.J. DeWitt, “The EXODUS Optimizer Generator”, Proc. ACM SIGMOD, pp. 160–171, San Francisco, CA., May 1987.
J. Hofmann, “Evaluierung eines COOL—Anfrageoptimierers”, Semesterarbeit, ETH Zurich, Departement Informatik, Zurich, 1992.
A. Kemper, C. Kilger, and G. Moerkotte, “Function Materialization in Object Bases”, Proc. ACM SIGMOD, p. 258, Denver, CO, May 1991.
A. Kemper and G. Moerkotte, “Advanced Query Processing in Object Bases Using Access Support Relations”, Proc. VLDB, p. 290, Brisbane, Australia, 1990.
A. Kemper and G. Moerkotte, “Access Support in Object Bases”, Proc. ACM SIGMOD, p. 364, Atlantic City, NJ, May 1990.
U. Kessler and P Dadam, “Auswertung komplexer Anfragen an hierarchisch strukturierte Objekte mittels Pfadindexen”, Proc. BTW, Kaiserslautern, Germany, March 1991.
W. Kim, “On Optimizing an SQL-like Nested Query”,ACM TODS, vol. 7, no. 3, September 1982.
T Laes, “Generierung and Evaluierung eines Anfrageoptimierers”, Diplomarbeit, ETH Zurich, Departement Informatik, Zurich, 1991.
R. Lanzelotte, P Valduriez, and M. Zait, “Optimization of Object-Oriented Recursive Queries Using Cost-Controlled Strategies”, Proc. ACM SIGMOD, San Diego, California., June 1992.
R. Lanzelotte, P. Valduriez, M. Ziane, and J.J. Cheiney, “Optimization of Nonrecursive Queries in OODBs”, Proc. DOOD-2, Munich, Germany, December 1991.
D. Maier and J. Stein, “Indexing in an Object-Oriented DBMS”, Proc. Int’l Workshop on Object-Oriented Database Systems, p. 171, Pacific Grove, CA, September 1986.
O. Mayer, “Abbildung and Integration von COOL-DDL auf NF2”, Semesterarbeit, ETH Zurich, Departement Informatik, Zurich, 1992.
K. Ono and G.M. Lohman, “Extensible Enumeration of Feasible Joins for Relational Query Optimization”, IBM Research Report, RJ 6625 (63936), San Jose, CA, December 1988.
G. Pathak and J.A. Blakeley, “Query Optimization in Object-Oriented Databases”, Proc. Workshop on Database Query Optimization, OGC, CS Technical Report 89–005, Beaverton, OR., May 1989.
H.B. Paul, H.J. Schck, M.H. Scholl, G. Weikum, and U. Deppisch, “Architecture and Implementation of the Darmstadt Database Kernel System”, Proc. ACM SIGMOD, p. 196, San Francisco, CA, May 1987.
H. Pirahesh, W. Hasan, and J. Hcllerstein, “Extensible/Rule Based Query Rewrite Optimization in Starburst”, Proc. ACM SIGMOD, p. 39, San Diego, California., June 1992.
C. Rich, “Query Rewrite and Plan Optimization in COCOON, using Hierarchical Algebra Transformations”, University of Ulm, Dept. of Computer Science, Technical Report, 1992 (in Preparation).
A. Rosenthal, C. Rich, and M.H. Scholl, “Reducing Duplicate Work in Relational Join(s): A Unified Approach”, Submitted for publication, also Technical Report NR:172, ETH Zurich, Dept. of Computer Science, 1992.
H.J. Schek, H.B. Paul, M.H. Scholl, and G. Weikum, “The DASDBS Project: Objectives, Experiences, and Future Prospects”, IEEE Trans. on Knowledge and Data Eng., vol. 2, no. 1, March 1990.
M.H. Scholl, H.B. Paul, and H.J. Schek, “Supporting Flat Relations by a Nested Relational Kernel”, Proc. VLDB, p. 137, Brighton, England, August 1987.
M.H. Scholl, “The Nested Relational Model - - - Efficient Support for a Relational Database Interface”, Ph.D. Thesis, Dept. of Computer Science, TU Darmstadt, 1988. (in German)
M.H. Scholl, “Theoretical Foundation of Algebraic Optimization Utilizing Unnormalized Relations”, in Proc. ICDT, LNCS, vol. 243, pp. 380–396, Springer, Rome, Italy, September 1986.
M.H. Scholl, “Physical Database Design for an Object Oriented Database System”, in Query Processing for Advanced Database Applications, ed. J.C. Freytag, G. Vossen, and D. Maier, Morgan-Kaufman, San Mateo, CA, 1993, To appear.
M.H. Scholl and H.-J. Schek, “A Relational Object Model”, in Proc. ICDT, LNCS, vol. 470, pp. 89–105, Springer, Paris, December 1990.
M.H. Scholl and H.-J. Schek, “A Synthesis of Complex Objects and Object-Orientation”, Proc. IFIP TC 2 Working Conference on Database Semantics: Object Oriented Databases -Analysis, Design and Construction, Windermere, U.K., July 1990.
P.G. Selinger, M.M. Astrahan, D.D. Chamberlin, R.A. Lorie, and T.G. Price, “Access Path Selection in a Relational Database Management System”, Proc. ACM SIGMOD, pp. 23–34, Boston, MA., May—June 1979.
G.M. Shaw and S.B. Zdonik, “A Query Algebra for Object—Oriented Databases”, Proc. IEEE Data Eng., p. 154, Los Angelos, CA, February 1990.
E. Shekita and M. Carey, “Performance Enhancement Through Replication in an Object—Oriented DBMS”, Proc. ACM SIGMOD, p. 325, Portland, OR, May—June 1989.
E.J. Shekita and M.J. Carey, “A Performance Evaluation of Pointer—Based Joins”, Proc. ACM SIGMOD, p. 300, Atlantic City, NJ., May 1990.
D.D. Straube, “Queries and Query Processing in Object—Oriented Database Systems”, University of Alberta, CSD Technical Report 90–33, Edmonton, Canada, December 1990.
A. Swami, “Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques”, Proc. ACM SIGMOD, p. 367, Portland, OR, May—June 1989.
A. Swami and A. Gupta, “Optimizing Large Join Queries”, Proc. ACM SIGMOD, pp. 8–17, Chicago, IL., June 1988.
W.B. Teeuw, C. Rich, M.H. Scholl, and H.M. Blanken, “An Evaluation of Physical Disk I/Os for Complex Object Processing”, Proc. IEEE Conf. on Data Eng., Vienna, Austria, April 1993, To appear. A more detailed version is available as Technical Report 183, ETH Zurich, Dept. of Computer Science, 1992.
D. Wilhelm, “Query— Schnittstelle für DASDBS”,Diplomarbeit, ETH Zurich, Departement Info rmatik, Zurich, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rich, C., Scholl, M.H. (1993). Query Optimization in an OODBMS. In: Stucky, W., Oberweis, A. (eds) Datenbanksysteme in Büro, Technik und Wissenschaft. Informatik aktuell. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-86096-6_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-86096-6_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-56487-4
Online ISBN: 978-3-642-86096-6
eBook Packages: Springer Book Archive