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