Optimizing Distributed Database Design for Efficient Allocation
Explore the concept of allocation in distributed database design, addressing problems, information requirements, and allocation methods. Discover the fragmentation, file allocation vs. database allocation, and essential information requirements for optimal database performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CHAPTER 3 DISTRIBUTED DATABASE DESIGN SudheerThandu Presentation ID: 13
Index 1. What is allocation? 2. Problems related to allocation 3. Information Requirements 4. Allocation Methods
Allocation Fragmentation Relation may be divided into a number of sub- relations,which are then distributed. Allocation Each fragment is stored at site with optimal distribution.
Fragment allocation Problem Statement Given F = {F1, F2, , Fn} S ={S1, S2, , Sm} Q = {q1, q2, , qq} Find the "optimal" distribution of F to S. Optimality Minimal cost Communication + storage + processing (read & update) Cost in terms of time (usually) Performance Response time and/or throughput Constraints Per site constraints (storage & processing) fragments network sites applications
Allocation File Allocation (FAP) vs Database Allocation (DAP): Fragments are not individual files relationships have to be maintained Access to databases is more complicated remote file access model not applicable relationship between allocation and query processing Cost of integrity enforcement should be considered Cost of concurrency control should be considered
Information Requirements Database Information selectivity of fragments size of a fragment Application Information number of read accesses of a query to a fragment number of update accesses of query to a fragment A matrix indicating which queries updates which fragments A similar matrix for retrievals originating site of each query
Conti.. Site Information unit cost of storing data at a site unit cost of processing at a site Network Information communication cost/frame between two sites frame size
Allocation Methods General Form min(Total Cost) subject to response time constraint storage constraint processing constraint Decision Variable xij= 1 if fragment Fiis stored at site Sj 0 otherwise
Conti.. Solution Methods FAP is NP-complete DAP also NP-complete Heuristics based on single commodity warehouse location (for FAP) knapsack problem branch and bound techniques network flow
Benefits Attempts to reduce the solution space assume all candidate partitioning known; select the best partitioning ignore replication at first sliding window on fragments
