next up previous
Next: Multi-column hashing Up: Data Structures Used Previous: Dictionaries


The problem definition of indexing relations is as follows.

We have chosen a system of composite indices. Since the fields have all been compressed to an integer representation, the set of fields can be treated as an orthogonal basis for a vector space, with each tuple corresponding to a point in this space. Given an n-ary relation we can construct one or more m-ary indices, , each of which constitutes a projection of the relation space onto an m dimensional sub space. The specification of values for p fields, for , then defines an m-p dimensional submanifold of the m dimensional index space space within which the tuples that constitute valid responsed to the query must lie. Clearly for the special case of m=1 we have a conventional single field index. The indices are implemented using multi-dimensional hash tables.

W Paul Cockshott
Fri Sep 6 10:29:18 BST 1996