ACM SIGMOD Anthology VLDB dblp.uni-trier.de

A Configrable Type Hierarchy Index for OODB.

Thomas A. Mück, Martin L. Polaschek: A Configrable Type Hierarchy Index for OODB. VLDB J. 6(4): 312-332(1997)
@article{DBLP:journals/vldb/MuckP97,
  author    = {Thomas A. M{\"u}ck and
               Martin L. Polaschek},
  title     = {A Configrable Type Hierarchy Index for OODB},
  journal   = {VLDB J.},
  volume    = {6},
  number    = {4},
  year      = {1997},
  pages     = {312-332},
  ee        = {db/journals/vldb/MuckP97.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

With respect to the specific requirements of advanced OODB applications, index data structures for type hierarchies in OODBMS have to provide efficient support for multiattribute queries and have to allow index optimization for a particular query profile. We describe the multikey type index and an efficient implementation of this indexing scheme. It meets both requirements: in addition to its multiattribute query capabilities it is designed as a mediator between two standard design alternatives, key-grouping and type-grouping. A prerequisite for the multikey type index is a linearization algorithm which maps type hierarchies to linearly ordered attribute domains in such a way that each subhierarchy is represented by an interval of this domain. The algorithm extends previous results with respect to multiple inheritance. The subsequent evaluation of our proposal focuses on storage space overhead as well as on the number of disk I/O operations needed for query execution. The analytical results for the multikey type index are compared to previously published figures for well-known single-key search structures. The comparison clearly shows the superiority of the multikey type index for a large class of query profiles.

Key Words

OODB, Access methods, Indexing, Type hierarchies, Multiple inheritance

Copyright © 1997 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[1]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[2]
Elisa Bertino: An Indexing Technique for Object-Oriented Databases. ICDE 1991: 160-170 BibTeX
[3]
Elisa Bertino, Beng Chin Ooi, Ron Sacks-Davis, Kian-Lee Tan, Justin Zobel, Boris Shidlovsky, Barbara Catania: Indexing Techniques for Advanced Database Systems. Kluwer 1997, ISBN 0-7923-9985-4
BibTeX
[4]
Michael J. Carey, Donovan A. Schneider (Eds.): Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, San Jose, California, May 22-25, 1995. ACM Press 1995
Contents BibTeX
[5]
Chee Yong Chan, Cheng Hian Goh, Beng Chin Ooi: Indexing OODB Instances based on Access Proximity. ICDE 1997: 14-21 BibTeX
[6]
Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561 BibTeX
[7]
Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91 BibTeX
[8]
Ehud Gudes: A Uniform Indexing Scheme for Object-Oriented Databases. ICDE 1996: 238-246 BibTeX
[9]
Stanley Y. W. Su (Ed.): Proceedings of the Twelfth International Conference on Data Engineering, February 26 - March 1, 1996, New Orleans, Louisiana. IEEE Computer Society 1996, ISBN 0-8186-7240-4
Contents BibTeX
[10]
W. A. Gray, Per-Åke Larson (Eds.): Proceedings of the Thirteenth International Conference on Data Engineering, April 7-11, 1997 Birmingham U.K. IEEE Computer Society 1997, ISBN 0-8186-7807-0
Contents BibTeX
[11]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[12]
Christoph Kilger, Guido Moerkotte: Indexing Multiple Sets. VLDB 1994: 180-191 BibTeX
[13]
Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394 BibTeX
[14]
David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
[15]
Chee Chin Low, Hongjun Lu, Beng Chin Ooi, Jiawei Han: Efficient Access Methods in Deductive and Object-Oriented Databases. DOOD 1991: 68-84 BibTeX
[16]
Chee Chin Low, Beng Chin Ooi, Hongjun Lu: H-trees: A Dynamic Associative Search Index for OODB. SIGMOD Conference 1992: 134-143 BibTeX
[17]
Thomas A. Mück, Martin L. Polaschek: Indexing Type Hierarchies with Multikey Structures. POS 1996: 184-193 BibTeX
[18]
...
[19]
Thomas A. Mück, Martin L. Polaschek: The Multikey Type Index for Persistent Object Sets. ICDE 1997: 22-31 BibTeX
[20]
Beng Chin Ooi, Jiawei Han, Hongjun Lu, Kian-Lee Tan: Index Nesting - An Efficient Approach to Indexing in Object-Oriented Databases. VLDB J. 5(3): 215-228(1996) BibTeX
[21]
Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150 BibTeX
[22]
...
[23]
Boris Shidlovsky, Elisa Bertino: A Graph-Theoretic Approach to Indexing in Object-Oriented Databases. ICDE 1996: 230-237 BibTeX
[24]
B. Sreenath, S. Seshadri: The hcC-tree: An Efficient Index Structure for Object Oriented Databases. VLDB 1994: 203-213 BibTeX
[25]
Jorge B. Bocca, Matthias Jarke, Carlo Zaniolo (Eds.): VLDB'94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile. Morgan Kaufmann 1994, ISBN 1-55860-153-8
Contents BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:31 2009