Processing Object-Oriented Queries with Invertible Late Bound Functions.

Staffan Flodin, Tore Risch: Processing Object-Oriented Queries with Invertible Late Bound Functions. VLDB 1995: 335-344

@inproceedings{DBLP:conf/vldb/FlodinR95,
  author    = {Staffan Flodin and
               Tore Risch},
  editor    = {Umeshwar Dayal and
               Peter M. D. Gray and
               Shojiro Nishio},
  title     = {Processing Object-Oriented Queries with Invertible Late Bound
               Functions},
  booktitle = {VLDB'95, Proceedings of 21th International Conference on Very
               Large Data Bases, September 11-15, 1995, Zurich, Switzerland},
  publisher = {Morgan Kaufmann},
  year      = {1995},
  isbn      = {1-55860-379-4},
  pages     = {335-344},
  ee        = {db/conf/vldb/FlodinR95.html},
  crossref  = {DBLP:conf/vldb/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

New demands are put on query processing in Object-Oriented (OO) databases to provide efficient and relationally complete query languages. A flexible 00 data model requires overloading and late binding of functionnames. Relational completeness requires capabilities to handle queries where functions are inverted, i.e. where it is possible to select those objects y that satisfies fn(y)-x where x is known. A system that supports both late binding and inverted functions must be able to solve fn(y)-x for a given x and unknown y when fn is late bound, i.e. the resolvent (implementation of a function name) to apply on y is selected based on the type of y. This combination of late binding and inverted function calls require novelquery processing capabilities to fully utilize indexes referenced in late bound function calls. This paper presents an approach to the management of late binding in queryprocessing. The main result is a query processing method where late bound function calls are efficiently executed and optimized for both inverted and regular execution. The proposed solution is based on substituting each late bound function call in the execution plan with a special function, DTR, which dynamically selects the actual resolvent to call. We define the inverse of DTR and its correctness. We show a dramatic execution time improvement by making DTR invertible andby defining its cost model for query optimization. The improvements are verified by performance measurements.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Umeshwar Dayal, Peter M. D. Gray, Shojiro Nishio (Eds.): VLDB'95, Proceedings of 21th International Conference on Very Large Data Bases, September 11-15, 1995, Zurich, Switzerland. Morgan Kaufmann 1995, ISBN 1-55860-379-4
Contents

References

[1]: Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik: The Object-Oriented Database System Manifesto. DOOD 1989: 223-240
[2]: Luca Cardelli, Peter Wegner: On Understanding Types, Data Abstraction, and Polymorphism. ACM Comput. Surv. 17(4): 471-522(1985)
[3]: R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
[4]: Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160
[5]: Scott Daniels, Goetz Graefe, Thomas Keller, David Maier, Duri Schmidt, Bennet Vance: Query Optimization in Revelation, an Overview. IEEE Data Eng. Bull. 14(2): 58-62(1991)
[6]: Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102
[7]: ...
[8]: ...
[9]: ...
[10]: Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276
[11]: Witold Litwin, Tore Risch: Main Memory Oriented Optimization of OO Queries Using Typed Datalog with Foreign Predicates. IEEE Trans. Knowl. Data Eng. 4(6): 517-528(1992)
[12]: ...
[13]: David Maier, Scott Daniels, Thomas Keller, Bennet Vance, Goetz Graefe, William J. McKenna: Challenges for Query Processing in Object-Oriented Databases. Query Processing for Advanced Database Systems, Dagstuhl 1991: 337-380
[14]: ...
[15]: Tore Risch, Martin Sköld: Active Rules based on Object-Oriented Queries. IEEE Data Eng. Bull. 15(1-4): 27-30(1992)
[16]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[17]: Gail M. Shaw, Stanley B. Zdonik: Object-Oriented Queries: Equivalence and Optimization. DOOD 1989: 281-295
[18]: David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981)
[19]: ...
[20]: Dave D. Straube, M. Tamer Özsu: Queries and Query Processing in Object-Oriented Database Systems. ACM Trans. Inf. Syst. 8(4): 387-430(1990)
[21]: Dave D. Straube, M. Tamer Özsu: Query Optimization and Execution Plan Generation in Object-Oriented Data Management Systems. IEEE Trans. Knowl. Data Eng. 7(2): 210-227(1995)
[22]: Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78
[23]: Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355
[24]: Bjarne Stroustrup: The C++ Programming Language, Second Edition. Addison-Wesley 1991, ISBN 0-201-53992-6
[25]: Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167