Database Allocation Modeling for Optimal Design of Distributed Systems

Jae-Woo LEE  Doo-Kwon BAIK  

IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.7   pp.1795-1804
Publication Date: 2004/07/01
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Distributed, Grid and P2P Computing
distributed database,  fragment replication,  heuristic algorithm,  file allocation model,  NP-completeness,  

Full Text: PDF>>
Buy this Article

By using distributed database systems, many advantages can be obtained such as database management cost, efficiency, and high integrity of systems through allocating fragments to many distributed sites with horizontal/vertical fragmentation of global database schema. 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 paper proposes near optimal heuristic algorithms for minimizing cost by defining a cost model based on read and update queries that are requested in many sites. 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.