 |
|
|
Evaluating Functional Joins Along Nested Reference Sets in Object-Relational and Object-Oriented Databases |
Full Paper (PDF)
|
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.
|
References, where available, link to the DBLP on the World Wide Web.
[BK89]Elisa Bertino, Won Kim:
Indexing Techniques for Queries on Nested Objects.
TKDE 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.
Computing Surveys 25(2): 73-170(1993)[HCLS97]Laura M. Haas, Michael J. Carey, Miron Livny, Amit Skukla:
Seeking the Truth About ad hoc Join Costs.
VLDB Journal 6(3): 241-256(1997)[HR96]Evan P. Harris, Kotagiri Ramamohanarao:
Join Algorithm Costs Revisited.
VLDB Journal 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, Danel Weinreb:
The ObjectStore System.
CACM 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.
IS 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.
TODS 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
|
@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},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
