ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates.

Sven Helmer, Guido Moerkotte: Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. VLDB 1997: 386-395
@inproceedings{DBLP:conf/vldb/HelmerM97,
  author    = {Sven Helmer and
               Guido Moerkotte},
  editor    = {Matthias Jarke and
               Michael J. Carey and
               Klaus R. Dittrich and
               Frederick H. Lochovsky and
               Pericles Loucopoulos and
               Manfred A. Jeusfeld},
  title     = {Evaluation of Main Memory Join Algorithms for Joins with Set
               Comparison Join Predicates},
  booktitle = {VLDB'97, Proceedings of 23rd International Conference on Very
               Large Data Bases, August 25-29, 1997, Athens, Greece},
  publisher = {Morgan Kaufmann},
  year      = {1997},
  isbn      = {1-55860-470-7},
  pages     = {386-395},
  ee        = {db/conf/vldb/HelmerM97.html},
  crossref  = {DBLP:conf/vldb/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Current data models like the NF2 model and object-oriented models support set-valued attributes. Hence, it becomes possible to have join predicates based on set comparison. This paper introduces and evaluates two main memory algorithms to evaluate efficiently this kind of join. More specifically, we concentrate on subset predicates.

Copyright © 1997 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Matthias Jarke, Michael J. Carey, Klaus R. Dittrich, Frederick H. Lochovsky, Pericles Loucopoulos, Manfred A. Jeusfeld (Eds.): VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, August 25-29, 1997, Athens, Greece. Morgan Kaufmann 1997, ISBN 1-55860-470-7
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Electronic Edition

From CS Dept., University Trier (Germany)

References

[1]
...
[2]
Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
R. G. G. Cattell: The Object Database Standard: ODMG-93 (Release 1.2). Morgan Kaufmann 1996
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
David J. DeWitt, Daniel F. Lieuwen, Manish Mehta: Pointer-Based Join Techniques for Object-Oriented Databases. PDIS 1993: 172-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: An Evaluation of Non-Equijoin Algorithms. VLDB 1991: 443-452 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
David J. DeWitt, Jeffrey F. Naughton, Donovan A. Schneider: Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting. PDIS 1991: 280-291 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Christos Faloutsos, Stavros Christodoulakis: Signature Files: An Access Method for Documents and Its Analytical Performance Evaluation. ACM Trans. Inf. Syst. 2(4): 267-288(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Shinya Fushimi, Masaru Kitsuregawa, Hidehiko Tanaka: An Overview of The System Software of A Parallel Relational Database Machine GRACE. VLDB 1986: 209-219 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Goetz Graefe: Sort-Merge-Join: An Idea Whose Time Has(h) Passed? ICDE 1994: 406-417 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Goetz Graefe, Ann Linville, Leonard D. Shapiro: Sort versus Hash Revisited. IEEE Trans. Knowl. Data Eng. 6(6): 934-944(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[19]
Yoshiharu Ishikawa, Hiroyuki Kitagawa, Nobuo Ohbo: Evaluation of Signature Files as Set Access Facilities in OODBs. SIGMOD Conference 1993: 247-256 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[20]
...
[21]
Christoph Kilger, Guido Moerkotte: Indexing Multiple Sets. VLDB 1994: 180-191 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
Masaru Kitsuregawa, Masaya Nakayama, Mikio Takagi: The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method. VLDB 1989: 257-266 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Hash-Joins. SIGMOD Conference 1996: 247-258 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Raymond A. Lorie, Honesty C. Young: A Low Communication Sort Algorithm for a Parallel Database Machine. VLDB 1989: 125-134 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Jai Menon: A Study of Sort Algorithms for Multiprocessor Database Machines. VLDB 1986: 197-206 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[28]
Masaya Nakayama, Masaru Kitsuregawa, Mikio Takagi: Hash-Partitioned Join Method Using Dynamic Destaging Strategy. VLDB 1988: 468-478 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
Patrick E. O'Neil, Goetz Graefe: Multi-Table Joins Through Bitmapped Join Indices. SIGMOD Record 24(3): 8-11(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Jignesh M. Patel, David J. DeWitt: Partition Based Spatial-Merge Join. SIGMOD Conference 1996: 259-270 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
Charles S. Roberts: Partial-Match Via the Method of Superimposed Codes. Proceedings of the IEEE 67(12): 1624-1642(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
Ron Sacks-Davis, Kotagiri Ramamohanarao: A two level superimposed coding scheme for partial match retrieval. Inf. Syst. 8(4): 273-289(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[35]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[37]
Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[38]
Eugene J. Shekita, Michael J. Carey: A Performance Evaluation of Pointer-Based Joins. SIGMOD Conference 1990: 300-311 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[39]
Dong Keun Shin, Arnold Charles Meltzer: A New Join Algorithm. SIGMOD Record 23(4): 13-18(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[40]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[41]
Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[42]
Zhaohui Xie, Jiawei Han: Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases. VLDB 1994: 522-533 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
  2. Alfons Kemper, Donald Kossmann, Christian Wiesner: Generalised Hash Teams for Join and Group-by. VLDB 1999: 30-41
  3. Jens Claußen, Alfons Kemper, Guido Moerkotte, Klaus Peithner: Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases. VLDB 1997: 286-295

Copyright © Mon Nov 2 21:19:10 2009 by Michael Ley (ley@uni-trier.de)