Building Signature File Hierarchies into Object-oriented Databases

Y. Chen (Canada)


objectoriented databases, indexes, signature files, signature trees


Although object-oriented database systems of fer more powerful modeling capability than relational data base systems, their performance suffers from the increased complexity in the data model. Recently, a lot of research has been directed to mitigating this problem by building indexes over single classes, class hierarchies or nested object hier archies. In this paper, we propose a new indexing method. It is based on the technique of signature files, but differs from the existing methods in two aspects: (1) all the signature files are organized into a hierarchy to filter irrelevant data as early as possible; (2) a signature file itself is stored as a tree structure (called a signature tree) to speed up the sig nature scanning. Together with the concept of query signa ture hierarchies, this technique reduces the search space dramatically and therefore improves significantly the time complexity of query evaluation.

Important Links:

Go Back