Data fragmentation and allocation algorithms for distributed database design
Minyoung Ra · University of Florida Digital Collections (University of Florida) · 1991
In a distributed database system data fragmentation and allocation are the major design issues. This dissertation presents a set of algorithms for fragmentation (or partitioning) and allocation. The relational model of data is assumed for convenience. The algorithms can be applied to other data models with minor variations. The partitioning of a global schema into fragments can be performed in two different ways: vertical partitioning and horizontal partitioning. Vertical partitioning is the process of subdividing the attributes of a relation or a record type into multiple records, thereby creating fragments. Horizontal partitioning is the process that divides a global relation into subsets of tuples, called horizontal fragments. In this dissertation a new vertical partitioning algorithm is presented. This algorithm starts from the attribute affinity matrix by considering it as a complete graph. Then, forming a linearly connected spanning tree, it generates all meaningful fragments simultaneously. A new horizontal partitioning algorithm is also presented, which is developed by applying the same graphical technique as in vertical partitioning. The need for mixed partitioning arises because database users usually access data subsets which are simultaneously vertical and horizontal fragments of global relations. However, this problem has not been addressed well in the current literature. A mixed partitioning methodology, which first forms a grid by partitioning a global relation vertically and horizontally in an independent fashion and then produces the final fragments (called mixed fragments) by merging the grid cells, is addressed. In most of the previous allocation work, the unit of allocation is the fragment that results from horizontal partitioning or vertical partitioning. Little work has been done for the allocation of the result of mixed partitioning. This dissertation presents an allocation algorithm for fragments that are generated from our mixed partitioning procedure. In this algorithm a mixed fragment is the unit of allocation. This algorithm is developed based on a heuristic called the pseudoallocation technique. The contribution of this dissertation consists of providing efficient graph oriented algorithms for partitioning, developing a mixed partitioning approach to distribution and a new approach to fragment allocation in distributed databases.