Functional-Join Processing.

Reinhard Braumandl, Jens Claußen, Alfons Kemper, Donald Kossmann: Functional-Join Processing. VLDB J. 8(3-4): 156-177(2000)

@article{DBLP:journals/vldb/BraumandlCKK00,
  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, http://dblp.uni-trier.de}
}

Abstract

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An5-2 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[BCK98]: 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
[BK89]: Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
[BM72]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[BP95]: Alexandros Biliris, Euthimios Panagos: A High Performance Configurable Storage Manager. ICDE 1995: 35-43
[BR90]: Alfred L. Brown, John Rosenberg: Persistent Object Stores: An Implementation Technique. POS 1990: 199-212
[CD92]: Sophie Cluet, Claude Delobel: A General Framework for the Optimization of Object-Oriented Queries. SIGMOD Conference 1992: 383-392
[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
[CDRS86]: 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
[CKK98]: ...
[CM95]: ...
[Com79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[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
[ED88]: Richard J. Enbody, H. C. Du: Dynamic Hashing Schemes. ACM Comput. Surv. 20(2): 85-113(1988)
[EGK95]: André Eickler, Carsten Andreas Gerlhof, Donald Kossmann: A Performance Evaluation of OID Mapping Techniques. VLDB 1995: 18-29
[EKK97]: André Eickler, Alfons Kemper, Donald Kossmann: Finding Data in the Neighborhood. VLDB 1997: 336-345
[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
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents
[H�r78]: Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978)
[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)
[HZ87]: 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)
[Ita93]: ...
[KC86]: Setrag Khoshafian, George P. Copeland: Object Identity. OOPSLA 1986: 406-416
[KGM91]: Thomas Keller, Goetz Graefe, David Maier: Efficient Assembly of Complex Objects. SIGMOD Conference 1991: 148-157
[KM90]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[Lit80]: Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223
[LLOW91]: Charles Lamb, Gordon Landis, Jack A. Orenstein, Daniel Weinreb: The ObjectStore Database System. Commun. ACM 34(10): 50-63(1991)
[LMB97]: ...
[LR99]: Zhe Li, Kenneth A. Ross: Fast Joins Using Join Indices. VLDB J. 8(1): 1-24(1999)
[MGS+94]: David Maier, Goetz Graefe, Leonard D. Shapiro, Scott Daniels, Thomas Keller, Bennet Vance: Issues in Distributed Object Assembly. IWDOM 1992: 165-181
[MS87]: David Maier, Jacob Stein: Development and Implementation of an Object-Oriented DBMS. Research Directions in Object-Oriented Programming 1987: 355-392
[O2T94]: ...
[Obj96]: ...
[PCV94]: Jignesh M. Patel, Michael J. Carey, Mary K. Vernon: Accurate Modeling of the Hybrid Hash Join Algorithm. SIGMETRICS 1994: 56-66
[SABdB94]: 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
[SC90]: Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311
[SG89]: Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215
[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]: ...
[WW90]: Ifor Williams, Mario Wolczko: An Object-Based Memory Architecture. POS 1990: 114-130
[XH94]: Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533