With the advent of relational database systems, multi-key searching problems have became the focus of a great deal of research. In this paper, we present a new data structure called predicate trees for clustering tuples of a relation in a way that allows the system to accelerate a large number of multi-dimensional queries. The directories used for the implementation of predicate trees in SABRE are organized as relations which are searched efficiently by filters. One of the most significant advantages of predicate trees is the possibility of defining logical addresses based on content, called signatures, and to use filters to manage directories.

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