More Web Proxy on the site http://driver.im/

research-article

Join Index Hierarchy: An Indexing Structure for Efficient Navigation in Object-Oriented Databases

Authors:

Zhaohui (Alex) Xie,

Yongjian FuAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 11, Issue 2

Pages 321 - 337

https://doi.org/10.1109/69.761666

Published: 01 March 1999 Publication History

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.

References

[1]

J. Banerjee W. Kim and K.C. Kim, "Queries in Object-Oriented Databases," Proc. Int'l Conf. Data Eng., pp. 31-39, Los Angeles, Feb. 1988.

Digital Library

[2]

E. Bertino, "An Indexing Technique for Object-Oriented Databases," Proc. Int'l Conf. Data Eng., pp. 160-170, Kobe, Japan, Apr. 1991.

Digital Library

[3]

E. Bertino and P. Foscoli, "Index Organizations for Object-Oriented Database Systems," IEEE Trans. Knowledge and Data Eng., vol. 7, no. 2, pp. 193-209, 1995.

Digital Library

[4]

E. Bertino and W. Kim, "Indexing Techniques for Queries on Nested Objects," IEEE Trans. Knowledge and Data Eng., vol. 1, no. 2, pp. 196-214, 1989.

Digital Library

[5]

J.A. Blakeley W.J. McKenna and G. Graefe, "Experiences Building the Open OODB Query Optimizer," Proc. ACM-SIGMOD Conf. Management Data, pp. 287-296, Washington, D.C., May 1993.

Digital Library

[6]

C.Y. Chan C.H. Goh and B.C. Ooi, "Indexing OODB Instances Based on Access Proximity," Proc. 13th Int'l Conf. Data Eng., pp. 14-21, Birmingham, U.K., 1997.

Digital Library

[7]

S. Choenni E. Bertino H.M. Blanken and T. Chang, "On the Selection of Optimal Index Configuration in OO Databases," Proc. Int'l Conf. Data Eng., pp. 526-537, Phoenix, Ariz., Feb. 1994.

Digital Library

[8]

S. Cluet and C. Delobel, "A General Framework for the Optimization of Object-Oriented Queries," Proc. ACM-SIGMOD Conf. Management Data, pp. 383-392, 1992.

Digital Library

[9]

G. Graefe, "Query Evaluation Techniques for Large Databases," ACM Computing Survey, vol. 25, no. 2, pp. 73-170, June 1993.

Digital Library

[10]

G. Graefe and D. Maier, "Query Optimization in Object-Oriented Database Systems: A Prospectus," Advances in Object-Oriented Database Systems, Springer-Verlag, 1988.

Digital Library

[11]

T. Haerder, "Implementing A Generalized Access Path Structure for A Relational Database System," ACM Trans. Database Systems, vol. 3, no. 3, pp. 285-298, Sept. 1978.

Digital Library

[12]

K.A. Hua and C. Tripathy, "Object Skeletons: An Efficient Navigation Structure for Object-Oriented Database Systems," Proc. Int'l Conf. Data Eng., pp. 508-517, Houston, Feb. 1994.

Digital Library

[13]

K. Kato and T. Masuda, "Persistent Caching: An Implementation Technique for Complex Objects with Object Identity," IEEE Trans. Software Eng., vol. 18, no. 7, July 1992.

Digital Library

[14]

T. Keller G. Graefe and D. Maier, "Efficient Assembly of Complex Objects," Proc. ACM-SIGMOD Conf. Management Data, pp. 148-157, Denver, Colo., May 1991.

Digital Library

[15]

A. Kemper and G. Moerkotte, "Access Support in Object Bases," Proc. ACM-SIGMOD Conf. Management Data, pp. 364-374, Atlantic City, N.J., May 1990.

Digital Library

[16]

A. Kemper and G. Moerkotte, "Advanced Query Processing in Object Bases Using Access Support Relations," Proc. Int'l Conf. Very Large Databases, pp. 290-301, Brisbane, Australia, Aug. 1990.

Digital Library

[17]

C. Kilger and G. Moerkotte, "Indexing Multiple Sets," Proc. Int'l Conf. Very Large Databases, Santiago, Chile, Sept. 1994.

Digital Library

[18]

K.C. Kim W. Kim and A. Dale, "Indexing Techniques for Object-Oriented Databases," W. Kim and F.H. Lochovsky, eds., Object-Oriented Concepts, Databases, and Applications, pp. 371-394. Addison-Wesley, 1989.

Digital Library

[19]

H.A. Kuno and H.A. Rundensteiner, "Augmented Inherited Multi-Index Structure for Maintenance of Materialized Path Query Views," Proc. Sixth Int'l Workshop Research Issues in Data Eng., pp. 128-137, New Orleans, 1996.

Digital Library

[20]

R.S.G. Lanzelotte P. Valduriez M. Ziane and J. Cheiney, "Optimization of Nonrecursive Queries in OODBs," Proc. Int'l Conf. Deductive and Object-Oriented Databases (DOOD), Munich, Germany, Dec. 1991.

[21]

C.C. Low B.C. Ooi and H. Lu, "H-Tree: A Dynamic Associative Search Index for OODB," Proc. ACM-SIGMOD Conf. Management Data, pp. 134-143, San Diego, May 1992.

Digital Library

[22]

W. Lu and J. Han, "Distance-Associated Join Indices for Spatial Range Search," Proc. Eighth Int'l Conf. Data Eng., pp. 284-292, Phoenix, Ariz., Feb. 1992.

Digital Library

[23]

D. Maier and J. Stein, "Indexing in An Object-Oriented DBMS," Proc. IEEE Int'l Workshop Object-Oriented Database System, pp. 171-182, Pacific Grove, Calif, Sept. 1986.

Digital Library

[24]

T.A. Mueck and M.L. Polaschek, "The Multikey Type Index for Persistent Object Sets," Proc. 13th Int'l Conf. Data Eng., pp. 22-31, Birmingham, U.K., 1997.

Digital Library

[25]

B.C. Ooi J. Han H. Lu and K.L. Tan, "Index Nesting—An Efficient Approach to Indexing in Object-Oriented Databases," VLDB J., vol. 5, pp. 215-228, 1996.

Digital Library

[26]

M. Palmer and S.B. Zdonik, "FIDO: A Cach that Learns to Fetch," Proc. Int'l Conf. Very Large Databases, Barcelona, Spain, 1991.

Digital Library

[27]

S. Ramaswamy and P.C. Kanellakis, "OODB Indexing by Class-Division," SIGMOD Record, vol. 24, pp. 139-150, 1995.

Digital Library

[28]

D. Rotem, "Spatial Join Indices," Proc. Seventh Int'l Conf. Data Eng., pp. 500-509, Kobe, Japan, Apr. 1991.

Digital Library

[29]

S.K. Seo and Y.J. Lee, "Methodology for Index Configurations in Object-Oriented Databases," Information Sciences, vol. 93, pp. 187-210, 1996.

Digital Library

[30]

E.J. Shekita and M.J. Carey, "Performance Enhancement Through Replication in An Object-Oriented DBMS," Proc. ACM-SIGMOD Conf. Management Data, pp. 325-336, 1989.

Digital Library

[31]

D.D. Straube and M.T. Ozsu, "Queries and Query Processing in Object-Oriented Database Systems," ACM Trans. Office and Information Systems, vol. 6, no. 4, pp. 387-430, Oct 1990.

Digital Library

[32]

P. Valduriez, "Join indices," ACM Trans. Database Systems, vol. 12, no. 2, pp. 218-246, 1987.

Digital Library

[33]

Z. Xie and J. Han, "Optimization of Queries Containing Complex Selections, Joins, and Aggregations," Proc. Int'l Conf. Computing and Information, Peterborough, Ont., Canada, May 1994.

[34]

S.B. Yao, "Approximating Block Accesses in Database Organizations," Comm. ACM, vol. 20, no. 4, pp. 260-261, Apr. 1977.

Digital Library

Cited By

Chmiel JMorzy TWrembel RSong IOrdonez C(2010)Time-HOBIProceedings of the ACM 13th international workshop on Data warehousing and OLAP10.1145/1871940.1871957(69-76)Online publication date: 30-Oct-2010
https://dl.acm.org/doi/10.1145/1871940.1871957
Terzi EVakali AAngelis L(2004)A simulated annealing approach for multimedia data placementJournal of Systems and Software10.1016/j.jss.2003.09.02073:3(467-480)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1016/j.jss.2003.09.020
Vakali ATerzi EBertino EElmagarmid A(2003)Hierarchical data placement for navigational multimedia applicationsData & Knowledge Engineering10.1016/S0169-023X(02)00124-644:1(49-80)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1016/S0169-023X%2802%2900124-6
Show More Cited By

Index Terms

Join Index Hierarchy: An Indexing Structure for Efficient Navigation in Object-Oriented Databases

Recommendations

DMVI: a dynamic materialized view index for efficiently discovering usable views for progressive queries
CASCON '12: Proceedings of the 2012 Conference of the Center for Advanced Studies on Collaborative Research

Progressive queries (PQ) are a new type of query emerged from numerous data intensive applications. A user formulates a PQ in several steps using a set of inter-related step-queries (SQ). Efficiently processing PQs in a DBMS is crucial in supporting ...
Slot Index Spatial Join

Efficient processing of spatial joins is very important due to their high cost and frequent application in spatial databases and other areas involving multidimensional data. This paper proposes slot index spatial join (SISJ), an algorithm that joins a ...
D-Index: Distance Searching Index for Metric Data Sets

In order to speedup retrieval in large collections of data, index structures partition the data into subsets so that query requests can be evaluated without examining the entire collection. As the complexity of modern data types grows, metric spaces ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 11, Issue 2

March 1999

96 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 1999 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 1999

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chmiel JMorzy TWrembel RSong IOrdonez C(2010)Time-HOBIProceedings of the ACM 13th international workshop on Data warehousing and OLAP10.1145/1871940.1871957(69-76)Online publication date: 30-Oct-2010
https://dl.acm.org/doi/10.1145/1871940.1871957
Terzi EVakali AAngelis L(2004)A simulated annealing approach for multimedia data placementJournal of Systems and Software10.1016/j.jss.2003.09.02073:3(467-480)Online publication date: 1-Nov-2004
https://dl.acm.org/doi/10.1016/j.jss.2003.09.020
Vakali ATerzi EBertino EElmagarmid A(2003)Hierarchical data placement for navigational multimedia applicationsData & Knowledge Engineering10.1016/S0169-023X(02)00124-644:1(49-80)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1016/S0169-023X%2802%2900124-6
Zaremba MSt-Laurent LNiemann ORichardson DLi KMakki KPissinou NRavada S(2000)Integration of self-organizing maps with spatial indexing for efficient processing of multi-dimensional dataProceedings of the 8th ACM international symposium on Advances in geographic information systems10.1145/355274.355285(77-82)Online publication date: 1-Nov-2000
https://dl.acm.org/doi/10.1145/355274.355285

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents