A graph based cluster approach for vertical partitioning in database design

摘要

In this paper, a new graphical approach to vertical partitioning of a relation is presented. The proposed algorithm - taking an attribute affinity graph as an input - has two major steps. In the first phase, a set of clusters on the affinity graph is constructed, where each cluster is a vertex set of a subgraph with a ‘strong’ connectivity between its vertices. In the second phase, clusters with the ‘highest affinity index’ are iteratively chosen as fragments. This approach resolves most of the deficiencies of the partitioning algorithm by Navathe-Ra [11]. Moreover, it produces better quality results than the approach presented in [10].