Join index hierarchy: an indexing structure for efficient navigation in object-oriented databases

Jiawei Han; Zhaohui Xie; Yongjian Fu

doi:10.1109/69.761666

Join index hierarchy: an indexing structure for efficient navigation in object-oriented databases

Jiawei Han, Zhaohui Xie, Yongjian Fu

Research output: Contribution to journal › Article › peer-review

Abstract

A novel indexing structure - join index hierarchy - is proposed to handle the 'gotos on disk' problem in object-oriented query processing. The method constructs a hierarchy of join indices and transforms a sequence of pointer chasing operations into a simple search in an appropriate join index file, and thus accelerates navigation in object-oriented databases. The method extends the join index structure studied in relational and spatial databases, supports both forward and backward navigations among objects and classes, and localizes update propagations in the hierarchy. Our performance study shows that partial join index hierarchy outperforms several other indexing mechanisms in object-oriented query processing.

Original language	English (US)
Pages (from-to)	321-337
Number of pages	17
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	11
Issue number	2
DOIs	https://doi.org/10.1109/69.761666
State	Published - 1999
Externally published	Yes

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Online availability

10.1109/69.761666

Library availability

Discover UIUC Full Text

Cite this

@article{1445807f0ec04a59a27e1c986f50409a,

title = "Join index hierarchy: an indexing structure for efficient navigation in object-oriented databases",

abstract = "A novel indexing structure - join index hierarchy - is proposed to handle the 'gotos on disk' problem in object-oriented query processing. The method constructs a hierarchy of join indices and transforms a sequence of pointer chasing operations into a simple search in an appropriate join index file, and thus accelerates navigation in object-oriented databases. The method extends the join index structure studied in relational and spatial databases, supports both forward and backward navigations among objects and classes, and localizes update propagations in the hierarchy. Our performance study shows that partial join index hierarchy outperforms several other indexing mechanisms in object-oriented query processing.",

author = "Jiawei Han and Zhaohui Xie and Yongjian Fu",

note = "Funding Information: This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, under Grant No. OGP03723; the Institute for Robotics and Intelligent Systems, under Grants No. HMI-5 and No. IC-2; and the Center for Systems Science at Simon Fraser University. This article is a substantially extended and modified version of a conference paper, “Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases,” by Zhaohui Xie and Jiawei Han, published on pages 522 to 533 of the Proceedings of the 20th International Conference on Very Large Data Bases. The conference was held in Santiago, Chile, in September 1994. Part of the work of Zhaohui Xie was done while he was studying at Simon Fraser University.",

year = "1999",

doi = "10.1109/69.761666",

language = "English (US)",

volume = "11",

pages = "321--337",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "2",

}

TY - JOUR

T1 - Join index hierarchy

T2 - an indexing structure for efficient navigation in object-oriented databases

AU - Han, Jiawei

AU - Xie, Zhaohui

AU - Fu, Yongjian

N1 - Funding Information: This research was partially supported by the Natural Sciences and Engineering Research Council of Canada, under Grant No. OGP03723; the Institute for Robotics and Intelligent Systems, under Grants No. HMI-5 and No. IC-2; and the Center for Systems Science at Simon Fraser University. This article is a substantially extended and modified version of a conference paper, “Join Index Hierarchies for Supporting Efficient Navigations in Object-Oriented Databases,” by Zhaohui Xie and Jiawei Han, published on pages 522 to 533 of the Proceedings of the 20th International Conference on Very Large Data Bases. The conference was held in Santiago, Chile, in September 1994. Part of the work of Zhaohui Xie was done while he was studying at Simon Fraser University.

PY - 1999

Y1 - 1999

N2 - A novel indexing structure - join index hierarchy - is proposed to handle the 'gotos on disk' problem in object-oriented query processing. The method constructs a hierarchy of join indices and transforms a sequence of pointer chasing operations into a simple search in an appropriate join index file, and thus accelerates navigation in object-oriented databases. The method extends the join index structure studied in relational and spatial databases, supports both forward and backward navigations among objects and classes, and localizes update propagations in the hierarchy. Our performance study shows that partial join index hierarchy outperforms several other indexing mechanisms in object-oriented query processing.

AB - A novel indexing structure - join index hierarchy - is proposed to handle the 'gotos on disk' problem in object-oriented query processing. The method constructs a hierarchy of join indices and transforms a sequence of pointer chasing operations into a simple search in an appropriate join index file, and thus accelerates navigation in object-oriented databases. The method extends the join index structure studied in relational and spatial databases, supports both forward and backward navigations among objects and classes, and localizes update propagations in the hierarchy. Our performance study shows that partial join index hierarchy outperforms several other indexing mechanisms in object-oriented query processing.

UR - http://www.scopus.com/inward/record.url?scp=0032660209&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032660209&partnerID=8YFLogxK

U2 - 10.1109/69.761666

DO - 10.1109/69.761666

M3 - Article

AN - SCOPUS:0032660209

SN - 1041-4347

VL - 11

SP - 321

EP - 337

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 2

ER -

Join index hierarchy: an indexing structure for efficient navigation in object-oriented databases

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this