Interval hierarchies and their application to predicate files

A dynamic index, called an interval hierarchy, is described, which supports several important retrieval operations on files of simple conjunctive predicates, and search and maintenance algorithms for interval hierarchies are given.

Abstract

Predicates are used extensively in modern database systems for purposes ranging from user specification of associative accesses to data, to user-invisible system control functions such as concurrency control and data distribution. Collections of predicates, or predicate files, must be maintained and accessed efficiently. This paper describes a dynamic index, called an interval hierarchy, which supports several important retrieval operations on files of simple conjunctive predicates. Search and maintenance algorithms for interval hierarchies are given. For a file of n predicates, typical of the kind expected in practice, these algorithms require time equal to Ο (log n ).