ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases.

Reinhard Braumandl, Jens Claußen, Alfons Kemper: Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases. VLDB 1998: 110-122
@inproceedings{DBLP:conf/vldb/BraumandlCK98,
  author    = {Reinhard Braumandl and
               Jens Clau{\ss}en and
               Alfons Kemper},
  editor    = {Ashish Gupta and
               Oded Shmueli and
               Jennifer Widom},
  title     = {Evaluating Functional Joins Along Nested Reference Sets in Object-Relational
               and Object-Oriented Databases},
  booktitle = {VLDB'98, Proceedings of 24rd International Conference on Very
               Large Data Bases, August 24-27, 1998, New York City, New York,
               USA},
  publisher = {Morgan Kaufmann},
  year      = {1998},
  isbn      = {1-55860-566-5},
  pages     = {110-122},
  ee        = {db/conf/vldb/BraumandlCK98.html},
  crossref  = {DBLP:conf/vldb/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Previous work on functional joins was constrained in two ways: (1) all approaches we know assume references being implemented as physical object identifiers (OIDs) and (2) most approaches are, in addition, limited to single-valued reference attributes. Both are severe limitations since most object-relational and all object-oriented database systems do support nested reference sets and many object systems do implement references as location-independent (logical) OIDs. In this work, we develop a new functional join algorithm that can be used for any realization form for OIDs (physical or logical) and is particularly geared towards supporting functional joins along nested reference sets. The algorithm can be applied to evaluate joins along arbitrarily long pathexpressions which may include one or more reference sets. The new algorithm generalizes previously proposed partition-based pointer joins by repeatedly applying partitioning with interleaved re-merging before evaluating the next functional join. Consequently, the algorithm is termed P(PM)*M where P standsfor partitioning and M denotes merging. Our prototype implementation as well as an analytical assessment based on a cost model prove that this new algorithm performs superior in almost alldatabase configurations.

Copyright © 1998 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 DiSC

CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...

ACM SIGMOD Anthology

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

Printed Edition

Ashish Gupta, Oded Shmueli, Jennifer Widom (Eds.): VLDB'98, Proceedings of 24rd International Conference on Very Large Data Bases, August 24-27, 1998, New York City, New York, USA. Morgan Kaufmann 1998, ISBN 1-55860-566-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[BK89]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BP95]
Alexandros Biliris, Euthimios Panagos: A High Performance Configurable Storage Manager. ICDE 1995: 35-43 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CBB+97]
...
[CDF+94]
Michael J. Carey, David J. DeWitt, Michael J. Franklin, Nancy E. Hall, Mark L. McAuliffe, Jeffrey F. Naughton, Daniel T. Schuh, Marvin H. Solomon, C. K. Tan, Odysseas G. Tsatalos, Seth J. White, Michael J. Zwilling: Shoring Up Persistent Applications. SIGMOD Conference 1994: 383-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CSL+90]
Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DLM93]
David J. DeWitt, Daniel F. Lieuwen, Manish Mehta: Pointer-Based Join Techniques for Object-Oriented Databases. PDIS 1993: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[EGK95]
André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GGT96]
Georges Gardarin, Jean-Robert Gruser, Zhao-Hui Tang: Cost-based Selection of Path Expression Processing Algorithms in Object-Oriented Databases. VLDB 1996: 390-401 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GKG+97]
Torsten Grust, Joachim Kröger, Dieter Gluche, Andreas Heuer, Marc H. Scholl: Query Evaluation in CROQUE - Calculus and Algebra Coincide. BNCOD 1997: 84-100 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HCLS97]
Laura M. Haas, Michael J. Carey, Miron Livny, Amit Shukla: Seeking the Truth About ad hoc Join Costs. VLDB J. 6(3): 241-256(1997) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HR96]
Evan P. Harris, Kotagiri Ramamohanarao: Join Algorithm Costs Revisited. VLDB J. 5(1): 64-84(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ita93]
...
[KC86]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KM90]
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LLOW91]
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LMB97]
...
[O2T94]
...
[PCV94]
Jignesh M. Patel, Michael J. Carey, Mary K. Vernon: Accurate Modeling of the Hybrid Hash Join Algorithm. SIGMETRICS 1994: 56-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SC90]
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS86]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sto96]
Michael Stonebraker, Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Val87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ver90]
...
[XH94]
Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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