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

BibTeX

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

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/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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/aDVD1 or /dvd

BibTeX

Printed Edition

Beatrice Yormark (Ed.): SIGMOD'84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984. ACM Press 1984 BibTeX , 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) BibTeX
[BENT79]: Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[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) BibTeX
[BURK83]: Walter A. Burkhard: Interpolation-Based Index Maintenance. PODS 1983: 76-89 BibTeX
[COME79]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[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) BibTeX
[GARD83]: ...
[GARD84]: Georges Gardarin, Patrick Valduriez, Yann Viémont: Predicate Trees: An Approach to Optimize Relational Query Operations. ICDE 1984: 439-444 BibTeX
[KNUT73]: Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[LARS78]: Per-Åke Larson: Dynamic Hashing. BIT 18(2): 184-201(1978) BibTeX
[LITW78]: Witold Litwin: Virtual Hashing: A Dynamically Changing Hashing. VLDB 1978: 517-523 BibTeX
[LITW81]: Witold Litwin: Trie Hashing. SIGMOD Conference 1981: 19-29 BibTeX
[LOME83]: David B. Lomet: A High Performance, Universal, Key Associative Access Method. SIGMOD Conference 1983: 120-133 BibTeX
[NIEV81]: Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multi-Key File Structure. ECI 1981: 236-251 BibTeX
[OUKS83]: Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[VALD84]: Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX

Referenced by

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

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]