Logo der Universität Wien

Optimal type hierarchy linearization for queries in OODB

Kurzbeschreibung

Selection criteria in OODB refer to object properties as well as to type membership. The latter stimulated research on type hierarchy indexing, i.e, fast access to object sets based on type membership criteria. A recent proposal in this context is the multikey type index. It is based on a symmetrical multikey search structure with n dimensions for n indexed object properties and one additional dimension for type membership. The domain of this type dimension is the type set of the indexed object. However, an important prerequisite for an efficient implementation of a multikey type index is an optimal linearization of the type set. In this paper we show in how far the linearization affects the performance of the multikey type index and present the construction of optimal linearizations which is straightforward only in case of single inheritance. In case of multiple inheritance a recursive divide-and-conquer solution produces all existing optimal linearizations for a given type hierarchy. The main contribution of this paper is a detailed outline of the corresponding algorithm for multiple inheritance type hierarchies. By using this algorithm, the multikey type index is an interesting alternative to the traditional approaches for type hierarchy indexing, which are almost exclusively based on B+-tree derivates.

Grafik Top
Referenz
Kategorie
Paper in Conference Proceedings or in Workshop Proceedings (Paper)
Veranstaltungstitel
Fifth International Conference on Database Systems for Advanced Applications
Institut
Workflow Systems and Technology
Veranstaltungsort
Melbourne, Australia
Veranstaltungsart
Conference
Veranstaltungsdatum
April 1997
ISSN/ISBN
981-02-3107-5
Verlag
World Scientific Publishing
Seitenbereich
pp. 225-234
Datum
1997
Export
Grafik Top
Kontakt
Fakultät für Informatik
Universität Wien

Währinger Straße 29
1090 Wien