ACM SIGMOD Anthology VLDB dblp.uni-trier.de

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

ACM SIGMOD Anthology

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Luca Cardelli, Peter Wegner: On Understanding Types, Data Abstraction, and Polymorphism. ACM Comput. Surv. 17(4): 471-522(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.1). Morgan Kaufmann 1994
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Richard L. Cole, Goetz Graefe: Optimization of Dynamic Query Evaluation Plans. SIGMOD Conference 1994: 150-160 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
...
[9]
...
[10]
Joseph M. Hellerstein, Michael Stonebraker: Predicate Migration: Optimizing Queries with Expensive Predicates. SIGMOD Conference 1993: 267-276 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Tore Risch, Martin Sköld: Active Rules based on Object-Oriented Queries. IEEE Data Eng. Bull. 15(1-4): 27-30(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
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
[18]
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Michael Stonebraker: Implementation of Integrity Constraints and Views by Query Modification. SIGMOD Conference 1975: 65-78 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Bjarne Stroustrup: The C++ Programming Language, Second Edition. Addison-Wesley 1991, ISBN 0-201-53992-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Scott L. Vandenberg, David J. DeWitt: Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance. SIGMOD Conference 1991: 158-167 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:22:05 2010 by Michael Ley (ley@uni-trier.de)