ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

A Multikey Hashing Scheme Using Predicate Trees.

Patrick Valduriez, Yann Viémont: A Multikey Hashing Scheme Using Predicate Trees. SIGMOD Conference 1984: 107-114
@inproceedings{DBLP:conf/sigmod/ValduriezV84,
  author    = {Patrick Valduriez and
               Yann Vi{\'e}mont},
  editor    = {Beatrice Yormark},
  title     = {A Multikey Hashing Scheme Using Predicate Trees},
  booktitle = {SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts,
               June 18-21, 1984},
  publisher = {ACM Press},
  year      = {1984},
  pages     = {107-114},
  ee        = {http://doi.acm.org/10.1145/602259.602275, db/conf/sigmod/ValduriezV84.html},
  crossref  = {DBLP:conf/sigmod/84},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A new method for multikey access suitable for dynamic files is proposed that transforms multiple key values into a logical address. This method is based on a new structure, called predicate tree, that represents the function applied to several keys. A predicate tree permits to specify in a unified way various hashing schemes by allowing for different definitions of predicates. A logical address qualifies a space partition of a file according to its predicate tree. This address is seen as a single key by a digital hashing method which transforms it into a physical address. This method is used to address records in a file and to transform a retrieval qualification on a file into a set of partitions to access. Finally, a qualitative analysis of the behavior of the method is given which exhibits its value.

Copyright © 1984 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

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

Printed Edition

Beatrice Yormark (Ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press 1984 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 14(2)
Contents

Online Edition: ACM Digital Library


References

[BAYE72]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BENT79]
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BLAS77]
Mike W. Blasgen, Richard G. Casey, Kapali P. Eswaran: An Encoding Method for Multifield Sorting and Indexing. Commun. ACM 20(11): 874-878(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BURK83]
Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[COME79]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FAGI79]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GARD83]
...
[GARD84]
Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KNUT73]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LARS78]
Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LITW78]
Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LITW81]
Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LOME83]
David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[NIEV81]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multi-Key File Structure. ECI 1981: 236-251 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OUKS83]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[VALD84]
Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Referenced by

  1. Ludger Becker, Klaus Hinrichs, Ulrich Finke: A New Algorithm for Computing Joins with Grid Files. ICDE 1993: 190-197
  2. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
  3. Georges Gardarin, Jean-Pierre Cheiney, Gerald Kiernan, Dominique Pastre, Hervé Stora: Managing Complex Objects in an Extensible Relational DBMS. VLDB 1989: 55-65
  4. Masaru Kitsuregawa, Lilian Harada, Mikio Takagi: Join Strategies on KB-Tree Indexed Relations. ICDE 1989: 85-93
  5. Mireille Régnier: Trie Hashing Analysis. ICDE 1988: 377-381
  6. Jean-Pierre Cheiney, Gerald Kiernan: A Functional Clustering Method for Optimal Access to Complex Domains in a Relational DBMS. ICDE 1988: 394-401
  7. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel, Jean-Marc Thévenin: A Reliable Backend Using Multiattribute Clustering and Select-Join Operator. VLDB 1986: 220-227
  8. Serge Abiteboul, Michel Scholl, Georges Gardarin, Eric Simon: Towards DBMSs for Supporting New Applications. VLDB 1986: 423-435
  9. Jean-Pierre Cheiney, Pascal Faudemay, Rodolphe Michel: An Extension of Access Paths to Improve Joins and Selections. ICDE 1986: 270-280

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