Determining optimal binary inter-relational clustering schema for a relational database^*

^*This work is supported by Bogazici University Research Fund under grant number 90HA0138.

Abstract

Clustering the related tuples of a pair of relations that are in many-to-one relationship (We call it inter-clustering.) expedites equijoin and natural join operations on these base relations. However, inter-clustering slows down other relational algebra operations. Thus it is important to determine globally the pairs of relations to inter-cluster. In this paper we present a methodology which first finds out the candidate pairs of relations to inter-cluster from database accesses. Then it determines an optimal schema consisting of pairs of relations to inter-cluster, using a global optimization algorithm based on a weighted graph matching solution. The objective of the optimization is minimizing the cost of processing the relational algebra operations on the base relations associated with the database accesses. The optimization algorithm gives an exact solution and is not a heuristic one. The whole methodology is of polynomial worst case time order complexity. The proof of correctness of the various steps of the methodology is given. Also the methodology is implemented and tested with satisfaction.

Keywords:

• Graph theory
• inter-file clustering
• optimization model
• relational databases
• storage structure selection methodology
• weighted graph matching

C.R. Categories:

• H.3.3
• I.2.8

^*This work is supported by Bogazici University Research Fund under grant number 90HA0138.

^*This work is supported by Bogazici University Research Fund under grant number 90HA0138.

Notes

^*This work is supported by Bogazici University Research Fund under grant number 90HA0138.