 |
|
|
Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships |
Full Paper (PDF)
|
Time of creation is one of the predominant (often implicit) clustering strategies found not only in Data Warehouse systems: line items are created together with their corresponding order, objects are created together with their subparts and so on.
The newly created data is then appended to the existing data.
We present a new join algorithm, called Diag- Join, which exploits time-of-creation clustering.
If we are able to take advantage of time- of-creation clustering, then theperformance evaluation reveals the superiority of Diag-Join over standard join algorithms like block-wise nested-loop join, GRACE hash join, and index nested-loop join.
We also present an analytical cost model for Diag-Join.
|
References, where available, link to the DBLP on the World Wide Web.
[1]...
[2]Kjell Bratbergsengen:
Hashing Methods and Relational Algebra Operations.
VLDB 1984: 323-333[3]David J. DeWitt, Robert H. Gerber:
Multiprocessor Hash-Based Join Algorithms.
VLDB 1985: 151-164[4]David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood:
Implementation Techniques for Main Memory Database Systems.
SIGMOD Conference 1984: 1-8[5]David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider:
Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting.
PDIS 1991: 280-291[6]Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka:
An Overview of The System Software of A Parallel Relational Database Machine GRACE.
VLDB 1986: 209-219[7]...
[8]Goetz Graefe:
Sort-Merge-Join: An Idea whose time has(h) passed?
ICDE 1994: 406-417[9]Goetz Graefe, Ann Linville, Leonard D. Shapiro:
Sort versus Hash Revisited.
TKDE 6(6): 934-944(1994)[10]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)[11]Theo Härder:
Implementing a Generalized Access Path Structure for a Relational Database System.
TODS 3(3): 285-298(1978)[12]Evan P. Harris, Kotagiri Ramamohanarao:
Join Algorithm Costs Revisited.
VLDB Journal 5(1): 64-84(1996)[13]...
[14]...
[15]Christoph Kilger, Guido Moerkotte:
Indexing Multiple Sets.
VLDB 1994: 180-191[16]Won Kim, Kyung-Chang Kim, Alfred G. Dale:
Indexing Techniques for Object-Oriented Databases.
Object-Oriented Concepts, Databases, and Applications 1989: 371-394[17]Ralph Kimball:
The Data Warehouse Toolkit: Practical Techniques for Building Dimensional Data Warehouses.
John Wiley 1996, ISBN 0-471-15337-0
[18]Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi:
The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method.
VLDB 1989: 257-266[19]Raymond A. Lorie, Honesty C. Young:
A Low Communication Sort Algorithm for a Parallel Database Machine.
VLDB 1989: 125-134[20]Jai Menon:
A Study of Sort Algorithms for Multiprocessor Database Machines.
VLDB 1986: 197-206[21]Priti Mishra, Margaret H. Eich:
Join Processing in Relational Databases.
Computing Surveys 24(1): 63-113(1992)[22]Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi:
Hash-Partitioned Join Method Using Dynamic Destaging Strategy.
VLDB 1988: 468-478[23]Patrick E. O'Neil, Goetz Graefe:
Multi-Table Joins Through Bitmapped Join Indices.
SIGMOD Record 24(3): 8-11(1995)[24]Betty Salzberg, Alex Tsukerman, Jim Gray, Michael Stewart, Susan Uren, Bonnie Vaughan:
FastSort: A Distributed Single-Input Single-Output External Sort.
SIGMOD Conference 1990: 94-101[25]Donovan A. Schneider, David J. DeWitt:
Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines.
VLDB 1990: 469-480[26]Leonard D. Shapiro:
Join Processing in Database Systems with Large Main Memories.
TODS 11(3): 239-264(1986)[27]Dong Keun Shin, Arnold Charles Meltzer:
A New Join Algorithm.
SIGMOD Record 23(4): 13-18(1994)[28]...
[29]Patrick Valduriez:
Join Indices.
TODS 12(2): 218-246(1987)[30]Zhaohui Xie, Jiawei Han:
Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases.
VLDB 1994: 522-533
|
@inproceedings{DBLP:conf/vldb/HelmerWM98,
author = {Sven Helmer and
Till Westmann and
Guido Moerkotte},
editor = {Ashish Gupta and
Oded Shmueli and
Jennifer Widom},
title = {Diag-Join: An Opportunistic Join Algorithm for 1:N Relationships},
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 = {98-109},
crossref = {DBLP:conf/vldb/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
