Heuristic Algorithms for optimal Fragment Allocation in Distributed Database Systems
Graduate School Korea University
Department of Computer Science and Engineering
Database Systems Heuristic Algorithms optimal Fragmen Allocation;
- 원문 URL
By using distributed database systems, many advantages can be obtained such as reduction of database management cost, efficiency, and high integrity of systems through allocating fragments to many distributed sites with horizontal and/or vertical fragmentation of global database schema. In distributed database systems, database management costs can be reduced by allocating frequently used fragments to local site and increasing local autonomy with availability and reliability. To minimize costs, distributed algorithms must be applied so that database fragments are allocated to optimal sites. It is useful to replicate fragments, such as allocating many copies in many sites including load balancing. But there are too many possible combinations of each site and fragment, making it impossible to find a solution in real time, i.e., it is an NP-complete problem. This thesis proposes heuristic algorithms with an optimization model for minimizing database allocation cost by defining a cost model based on read and update queries that are requested in many sites. In this thesis, the fragment allocation model is defined using database transaction frequency and types in distributed database systems. Various factors are applied to the proposed algorithms for sizing efficient network resources that compute database transactions as remote query or update requests for consistency in replicated database systems. For network load balancing, incoming network traffic table is defined in each site. A request transaction from unallocated sites to allocated sites can be accessed properly at any other replicated sites by using the network traffic table. Finally, some experimental results verified the proposed algorithms by comparing actual cases of database allocation.