A TRANSACTION-BASED APPROACH TO VERTICAL PARTITIONING FOR RELATIONAL DATABASE-SYSTEMS

A new approach to vertical partitioning in relational databases is proposed in which the attributes of a relation are partitioned according to a set or transactions. The objective of vertical partitioning is to minimize the number of disk accesses in the system. Since transactions have more semantic meanings than attributes, this approach allows the optimization of the partitioning based on a selected set of important transactions. An optimal binary partitioning algorithm, OBP, based on the branch and bound method, is presented with the worst case complexity of O(2n) where n is the number of transactions. To handle systems with a large number of transactions, an algorithm BPi with complexity varying from O(n) to O(2n) is also developed. Our experimental results reveal that the performance of vertical partitioning is sensitive to the skewness of transaction accesses. Further, BPi converges rather rapidly to OBP. Both OBP and BPi yield results comparable with that of global optimum obtained from an exhaustive search.