Clustering in Object Bases

Carsten A. Gerlhof
Alfons Kemper
Christoph Kilger
Guido Moerkotte
Technical Report:
No. 6/92, Fakultät für Informatik, Universität Karlsruhe, D-52056 Karlsruhe, June 1992.
We investigate clustering techniques that are specifically tailored for object-oriented database systems. Unlike traditional database systems object-oriented data models incorporate the application behavior in the form of type-associated operations. This source of information is exploited for clustering decisions by statically determining the operations' access behavior applying dataflow analysis techniques. This process yields a set of weighted access paths.

The statically extracted (syntactical) access patterns are then matched with the actual object net. Thereby the inter-object reference chains that are likely being traversed in the database applications accumulate correspondingly high weights. The object net can then be viewed as a weighted graph whose nodes correspond to objects and whose edges are weighted inter-object references. We then employ a newly developed (greedy) heuristics for graph partitioning - which exhibits moderate complexity and, thus, is applicable to object bases of realistic size.

Extensive benchmarking indicates that our clustering approach consisting of static operation analysis followed by greedy graph partitioning is in many cases superior to traditional clustering techniques - most of which are based on dynamically monitoring the overall access behavior of database applications.

To receive the whole postscript file klick here.

Carsten A. Gerlhof, 02.06.1994