Functional-Join Processing.

Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)
  author    = {Reinhard Braumandl and
               Jens Clau{\ss}en and
               Alfons Kemper and
               Donald Kossmann},
  title     = {Functional-Join Processing},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {3-4},
  year      = {2000},
  pages     = {156-177},
  ee        = {db/journals/vldb/BraumandlCKK00.html},
  bibsource = {DBLP,}


Inter-object references are one of the key concepts of object-relational and object-oriented database systems. In this work, we investigate alternative techniques to implement inter-object references and make the best use of them in query processing, i.e., in evaluating functional joins. We will give a comprehensive overview and performance evaluation of all known techniques for simple (single-valued) as well as multi-valued functional joins. Furthermore, we will describe special order-preserving functional-join techniques that are particularly attractive for decision support queries that require ordered results. While most of the presentation of this paper is focused on object-relational and object-oriented database systems, some of the results can also be applied to plain relational databases because index nested-loop joins along key/foreign-key relationships, as they are frequently found in relational databases, are just one particular way to execute a functional join.

Key Words

Object identifier - Logical OID - Physical OID - Query processing - Pointer join - Functional join - Order-preserving join

Copyright © 2000 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


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 BibTeX
Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
Alexandros Biliris, Euthimios Panagos: A High Performance Configurable Storage Manager. ICDE 1995: 35-43 BibTeX
Alfred L. Brown, John Rosenberg: Persistent Object Stores: An Implementation Technique. POS 1990: 199-212 BibTeX
Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392 BibTeX
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
Michael J. Carey, David J. DeWitt, Joel E. Richardson, Eugene J. Shekita: Object and File Management in the EXODUS Extensible Database System. VLDB 1986: 91-100 BibTeX
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
Michael J. Carey, Eugene J. Shekita, George Lapis, Bruce G. Lindsay, John McPherson: An Incremental Join Attachment for Starburst. VLDB 1990: 662-673 BibTeX
David J. DeWitt, Daniel F. Lieuwen, Manish Mehta: Pointer-Based Join Techniques for Object-Oriented Databases. PDIS 1993: 172-181 BibTeX
Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988) BibTeX
André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29 BibTeX
André Eickler, Alfons Kemper, Donald Kossmann: Finding Data in the Neighborhood. VLDB 1997: 336-345 BibTeX
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
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
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX
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
Evan P. Harris, Kotagiri Ramamohanarao: Join Algorithm Costs Revisited. VLDB J. 5(1): 64-84(1996) BibTeX
Mark F. Hornick, Stanley B. Zdonik: A Shared, Segmented Memory System for an Object-Oriented Database. ACM Trans. Inf. Syst. 5(1): 70-95(1987) BibTeX
Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416 BibTeX
Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157 BibTeX
Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 BibTeX
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991) BibTeX
Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999) BibTeX
David Maier, Goetz Graefe, Leonard D. Shapiro, Scott Daniels, Thomas Keller, Bennet Vance: Issues in Distributed Object Assembly. IWDOM 1992: 165-181 BibTeX
David Maier, Jacob Stein: Development and Implementation of an Object-Oriented DBMS. Research Directions in Object-Oriented Programming 1987: 355-392 BibTeX
Jignesh M. Patel, Michael J. Carey, Mary K. Vernon: Accurate Modeling of the Hybrid Hash Join Algorithm. SIGMETRICS 1994: 56-66 BibTeX
Hennie J. Steenhagen, Peter M. G. Apers, Henk M. Blanken, Rolf A. de By: From Nested-Loop to Join Queries in OODB. VLDB 1994: 618-629 BibTeX
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 BibTeX
Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 BibTeX
Michael Stonebraker, Dorothy Moore: Object-Relational DBMSs: The Next Great Wave. Morgan Kaufmann 1996, ISBN 1-55860-397-2
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
Ifor Williams, Mario Wolczko: An Object-Based Memory Architecture. POS 1990: 114-130 BibTeX
Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533 BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sun May 17 00:31:37 2009