Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10]


Journal of Information Science and Engineering, Vol. 20 No. 2, pp. 275-304 (March 2004)

Building Signature Trees into OODBs

Yangjun Chen
Department of Applied Computer Science
University of Winnipeg
Winnipeg, Manitoba, R3B 2E9, Canada

Although object-oriented database systems offer more powerful modeling capability than relational database systems, their performance suffers from the increased complexity in the data model. Recently, a lot of research has focused on mitigating this problem by building indexes over single classes, class hierarchies, or nested object hierarchies. In this paper, we pro?pose a new indexing method. It is based on the technique that employs signature files, but dif?fers 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 signature scanning. Together with the concept of query signature hierarchies, this technique reduces the search space dramatically and, therefore, improves significantly the time complexity of query evaluation.

Keywords: OODBs, indexes, signature files, signature trees, query evaluation

Full Text () Retrieve PDF document (200403_05.pdf)

Received February 22, 2002; revised November 25, 2002; accepted February 21, 2003.
Communicated by Arbee L. P. Chen.