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

Journal of Inforamtion Science and Engineering, Vol.15 No.2, pp.217-241 (March 1999)
Design of a New Indexing Organization for
a Class-Aggregation Hierarchy in Object-Oriented
Databases1

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

Full Text () Retrieve PDF document (199903_03.pdf : 228,870 bytes)

Received April 10, 1997; accepted December 14, 1997.
Communicated by Arbee L.P. Chen.
1 This research was supported in part by the National Science Council of Republic of China under Grant No. NSC-84-2213-E-110-009.