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}
}
BibTeX

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 ... BibTeX

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 BibTeX

References

[BK89]
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
[BP95]
Alexandros Biliris, Euthimios Panagos: A High Performance Configurable Storage Manager. ICDE 1995: 35-43 BibTeX
[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 BibTeX
[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 BibTeX
[DLM93]
David J. DeWitt, Daniel F. Lieuwen, Manish Mehta: Pointer-Based Join Techniques for Object-Oriented Databases. PDIS 1993: 172-181 BibTeX
[EGK95]
André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29 BibTeX
[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 BibTeX
[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 BibTeX
[Gra93]
Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
[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) BibTeX
[HR96]
Evan P. Harris, Kotagiri Ramamohanarao: Join Algorithm Costs Revisited. VLDB J. 5(1): 64-84(1996) BibTeX
[Ita93]
...
[KC86]
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
[KM90]
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 BibTeX
[LLOW91]
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) BibTeX
[LMB97]
...
[O2T94]
...
[PCV94]
Jignesh M. Patel, Michael J. Carey, Mary K. Vernon: Accurate Modeling of the Hybrid Hash Join Algorithm. SIGMETRICS 1994: 56-66 BibTeX
[SC90]
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 BibTeX
[SS86]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[Sto96]
Michael Stonebraker, Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2
BibTeX
[Val87]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[Ver90]
...
[XH94]
Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533 BibTeX

Referenced by

  1. Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
  2. Sophie Cluet: Review - Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases. ACM SIGMOD Digital Review 1: (1999)
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:46:20 2009