A New Indexing Technique for Nested Queries on Composite Objects

Yong-Moo KWON  Yong-Jin PARK  

IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.6   pp.861-872
Publication Date: 1992/11/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Databases
composite object,  nested query,  aggregation hierarchy,  indexing technique,  object-oriented database ,  

Full Text: PDF(816.9KB)>>
Buy this Article

A new indexing technique for rapid evaluation of nested query on composite object is propoced, reducing the overall cost for retrieval and update. An extended B+ tree is introduced in which object identifier (OID) to be searched and path information usud for update of index record are stored in leaf node and subleaf node, respectively. In this method, the retrieval oeration is applied only for OIDs in the leaf node. The index records of both leaf and subleaf nodes are updated in such a way that the path information in the subleaf node and OIDs in the leaf node are reorganized by deleting and inserting the OIDs. The techniaue presented offers advantages over currently related indexing techniques in data reorganization and index allocation. In the proposed index record, the OIDs to be reorganized are always consecutively provided, and thus only the record directory is updated when an entire page should be removed. In addition, the proposed index can be allocate to a path with the length greater than 3 without splitting the path. Comparisons under a variety of conditions are given with current indexing techniques, showing improved performance in cost, i.e., the total number of pages accessed for retrieval and update.