JISE


  [1] [2] [3] [4] [5] [6] [7] [8]


Journal of Information Science and Engineering, Vol. 15 No. 2, pp. 217-241


Design of a New Indexing Organization for a Class-Aggregation Hierarchy in Object-Oriented Databases


Chien-I Lee, Ye-In Chang* and Wei-Pang Yang**
Institute of InformationEducation 
National Tainan Teachers College 
Tainan, Taiwan 700, R.O.C. 
* Department of Applied Mathematics 
National Sun Yat-Sen University 
Kaohsiung, Taiwan 804, R.O.C. 
** Department of Computer and Information Science 
National Chiao Tung University 
Hsinchu, Taiwan 300, R.O.C.


    In an object-oriented database, 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 class-aggregation hierarchy of classes. A branch of such a hierarchy is called a path. Several index organizations have been proposed to support object-oriented query languages, including multiindex, join index and path index. All the proposed index organizations are helpful only for q query which retrieves the objects of the root class of a given path using a predicate which specifies the value of the attributed at the end of the path. In this paper, we propose a new index organization for evaluating queries, called full index, where an index is allocated for each class and its attribute (or nested attributed) along the path. From the analysis results, we show that a full index can support any type of query along a given path with a lower retrieval cost than all the other index organizations. Moreover, to reduce the high update cost for a long given path, we split the path into several subpaths and allocate a separate index to each supath. Given a path, the number of subpaths and the index organization of each subpath define an index configuration. Since a low retrievalcost and a low update cost are always a trade-off in index organization, we also propose cost formulas to determine the index configuration which can provide the best performance for various applications by taking into account various types of queries along a given path and a set of queries with more than one nested predicated along a given path.


Keywords: access methods, complex objects, index selection, object-oriented databases, query optimization

  Retrieve PDF document (JISE_199902_03.pdf)