Index Configuration in Object-Oriented Databases.

Elisa Bertino: Index Configuration in Object-Oriented Databases. VLDB J. 3(3): 355-399(1994)

@article{DBLP:journals/vldb/Bertino94,
  author    = {Elisa Bertino},
  title     = {Index Configuration in Object-Oriented Databases},
  journal   = {VLDB J.},
  volume    = {3},
  number    = {3},
  year      = {1994},
  pages     = {355-399},
  ee        = {db/journals/vldb/Bertino94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In relational databases, an attribute of a relation can have only a single primitive value, making it cumbersome to model complex objects. The object-oriented paradigm removes this difficulty by introducing the notion of nested objects, which allows the value of an object attribute to be another object or a set of other objects. This means that a class consists of a set of attributes, and the values of the attributes are objects that belong to other classes; that is, the definition of a class forms a hierarchy of classes. All attributes of the nested classes are nested attributes of the root of the hierarchy. A branch of such hierarchy is called a path. In this article, we address the problem of index configuration for a given path. We first summarize some basic concepts, and introduce the concept of index configuration for a path. Then we present cost formulas to evaluate the costs of the various configurations. Finally, we present the algorithm that determines the optimal configuration, and show its correctness.

Copyright © 1994 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Index selection, physical database design, query optimization.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An4-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[Andrews & Harris 1987]: Tim Andrews, Craig Harris: Combining Language and Database Advances in an Object-Oriented Development Environment. OOPSLA 1987: 430-440
[Banerjee et al. 1987]: Jay Banerjee, Hong-Tai Chou, Jorge F. Garza, Won Kim, Darrell Woelk, Nat Ballou, Hyoung-Joo Kim: Data Model Issues for Object-Oriented Applications. ACM Trans. Inf. Syst. 5(1): 3-26(1987)
[Banerjee et al. 1988]: Jay Banerjee, Won Kim, Kyung-Chang Kim: Queries in Object-Oriented Databases. ICDE 1988: 31-38
[Batory 1985]: Don S. Batory: Modeling the Storage Architectures of Commercial Database Systems. ACM Trans. Database Syst. 10(4): 463-528(1985)
[Bayer & McCreight 1972]: Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972)
[Bertino & Kim 1989]: Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989)
[Bertino 1990]: Elisa Bertino: Optimization of Queries using Nested Indices. EDBT 1990: 44-59
[Bertino et al. 1992]: Elisa Bertino, Mauro Negri, Giuseppe Pelagatti, Licia Sbattella: Object-Oriented Query Languages: The Notion and the Issues. IEEE Trans. Knowl. Data Eng. 4(3): 223-237(1992)
[Bertino & Martino 1993]: ...
[Bertino 1993]: ...
[Bjornerstedt & Hulton 1989]: Anders Björnerstedt, Christer Hulten: Version Control in an Object-Oriented Architecture. Object-Oriented Concepts, Databases, and Applications 1989: 451-485
[Breitl et al. 1989]: Robert Bretl, David Maier, Allen Otis, D. Jason Penney, Bruce Schuchardt, Jacob Stein, E. Harold Williams, Monty Williams: The GemStone Data Management System. Object-Oriented Concepts, Databases, and Applications 1989: 283-308
[Comer 1990]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[Deux 1990]: O. Deux: The Story of O2. IEEE Trans. Knowl. Data Eng. 2(1): 91-108(1990)
[Finkelstein et al. 1988]: Sheldon J. Finkelstein, Mario Schkolnick, Paolo Tiberio: Physical Database Design for Relational Databases. ACM Trans. Database Syst. 13(1): 91-128(1988)
[Fishman et al. 1987]: Daniel H. Fishman, David Beech, H. P. Cate, E. C. Chow, Tim Connors, J. W. Davis, Nigel Derrett, C. G. Hoch, William Kent, Peter Lyngbæk, Brom Mahbod, Marie-Anne Neimat, T. A. Ryan, Ming-Chien Shan: Iris: An Object-Oriented Database Management System. ACM Trans. Inf. Syst. 5(1): 48-69(1987)
[Jenq et al. 1989]: B. Paul Jenq, Darrell Woelk, Won Kim, Wan-Lik Lee: Query Processing in Distributed ORION. EDBT 1990: 169-187
[Lam et al. 1988]: Herman Lam, Stanley Y. W. Su, Nageshwar R. Koganti: A Physical Database Design Evaluation System for CODASYL Databases. IEEE Trans. Software Eng. 14(7): 1010-1022(1988)
[Lang et al. 1989]: Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: A Unified Analysis of Batched Searching of Sequential and Tree-Structured Files. ACM Trans. Database Syst. 14(4): 604-618(1989)
[Kemper & Moerkotte 1990]: Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374
[Kim 1990]: Won Kim: Object-Oriented Databases: Definition and Research Directions. IEEE Trans. Knowl. Data Eng. 2(3): 327-341(1990)
[Kim et al. 1988]: Kyung-Chang Kim, Won Kim, Darrell Woelk, Alfred G. Dale: Acyclic Query Processing in Object-Oriented Databases. ER 1988: 329-346
[Kim et al. 1989a]: Won Kim, Elisa Bertino, Jorge F. Garza: Composite Objects Revisted. SIGMOD Conference 1989: 337-347
[Kim et al. 1989b]: Won Kim, Kyung-Chang Kim, Alfred G. Dale: Indexing Techniques for Object-Oriented Databases. Object-Oriented Concepts, Databases, and Applications 1989: 371-394
[Maier & Stein 1986]: David Maier, Jacob Stein: Indexing in an Object-Oriented DBMS. OODBS 1986: 171-182
[Reuter & Kinzinger 1984]: Andreas Reuter, Horst Kinzinger: Automatic Design of the Internal Schema for a CODASYL Database System. IEEE Trans. Software Eng. 10(4): 358-375(1984)
[Rullo & Sacca 1988]: Pasquale Rullo, Domenico Saccà: An Automatic Physical Designer for Network Model Databases. IEEE Trans. Software Eng. 14(9): 1293-1306(1988)
[Schkolnick & Tiberio 1985]: Mario Schkolnick, Paolo Tiberio: Estimating the Cost of Updates in a Relational Database. ACM Trans. Database Syst. 10(2): 163-179(1985)
[Skarra et al. 1986]: Andrea H. Skarra, Stanley B. Zdonik, Steven P. Reiss: An Object Server for an Object-Oriented Database System. OODBS 1986: 196-204
[Valduriez et al. 1986]: Patrick Valduriez, Setrag Khoshafian, George P. Copeland: Implementation Techniques of Complex Objects. VLDB 1986: 101-110
[Valduriez 1987]: Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987)
[Whang et al. 1984]: Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Separability - An Approach to Physical Database Design. IEEE Trans. Computers 33(3): 209-222(1984)
[Yao 1977]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)
[Yu et al. 1985]: Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu: Adaptive Record Clustering. ACM Trans. Database Syst. 10(2): 180-204(1985)