Question? Leave a message!

Distributed Database Design

Distributed Database Design
Chapter 3: Distributed Database Design • Design problem • Design strategies(topdown, bottomup) • Fragmentation • Allocation and replication of fragments, optimality, heuristics Acknowledgements: I am indebted to Arturas Mazeika for providing me his slides of this course. DDB 2008/09 J. Gamper Page 1Design Problem • Design problem of distributed systems: Making decisions about the placement of data and programs across the sites of a computer network as well as possibly designing the network itself. • In DDBMS, the distribution of applications involves – Distribution of the DDBMS software – Distribution of applications that run on the database • Distribution of applications will not be considered in the following; instead the distribution of data is studied. DDB 2008/09 J. Gamper Page 2Framework of Distribution • Dimension for the analysis of distributed systems – Level of sharing: no sharing, data sharing, data + program sharing – Behavior of access patterns: static, dynamic – Level of knowledge on access pattern behavior: no information, partial information, complete information • Distributed database design should be considered within this general framework. DDB 2008/09 J. Gamper Page 3Design Strategies • Topdown approach – Designing systems from scratch – Homogeneous systems • Bottomup approach – The databases already exist at a number of sites – The databases should be connected to solve common tasks DDB 2008/09 J. Gamper Page 4Design Strategies . . . • Topdown design strategy DDB 2008/09 J. Gamper Page 5Design Strategies . . . • Distribution design is the central part of the design in DDBMSs (the other tasks are similar to traditional databases) – Objective: Design the LCSs by distributing the entities (relations) over the sites – Two main aspects have to be designed carefully ∗ Fragmentation · Relation may be divided into a number of subrelations, which are distributed ∗ Allocation and replication · Each fragment is stored at site with ”optimal” distribution · Copy of fragment may be maintained at several sites • In this chapter we mainly concentrate on these two aspects • Distribution design issues – Why fragment at all – How to fragment – How much to fragment – How to test correctness – How to allocate DDB 2008/09 J. Gamper Page 6Design Strategies . . . • Bottomup design strategy DDB 2008/09 J. Gamper Page 7Fragmentation • What is a reasonable unit of distribution Relation or fragment of relation • Relations as unit of distribution: – If the relation is not replicated, we get a high volume of remote data accesses. – If the relation is replicated, we get unnecessary replications, which cause problems in executing updates and waste disk space – Might be an Ok solution, if queries need all the data in the relation and data stays at the only sites that uses the data • Fragments of relationas as unit of distribution: – Application views are usually subsets of relations – Thus, locality of accesses of applications is defined on subsets of relations – Permits a number of transactions to execute concurrently, since they will access different portions of a relation – Parallel execution of a single query (intraquery concurrency) – However, semantic data control (especially integrity enforcement) is more difficult ⇒ Fragments of relations are (usually) the appropriate unit of distribution. DDB 2008/09 J. Gamper Page 8Fragmentation . . . • Fragmentation aims to improve: – Reliability – Performance – Balanced storage capacity and costs – Communication costs – Security • The following information is used to decide fragmentation: – Quantitative information: frequency of queries, site, where query is run, selectivity of the queries, etc. – Qualitative information: types of access of data, read/write, etc. DDB 2008/09 J. Gamper Page 9Fragmentation . . . • Types of Fragmentation – Horizontal: partitions a relation along its tuples – Vertical: partitions a relation along its attributes – Mixed/hybrid: a combination of horizontal and vertical fragmentation (a) Horizontal Fragmentation (b) Vertical Fragmentation (c) Mixed Fragmentation DDB 2008/09 J. Gamper Page 10Fragmentation . . . • Exampe Data ER Diagram DDB 2008/09 J. Gamper Page 11Fragmentation . . . • Example (contd.): Horizontal fragmentation of PROJ relation – PROJ1: projects with budgets less than200,000 – PROJ2: projects with budgets greater than or equal to200,000 DDB 2008/09 J. Gamper Page 12Fragmentation . . . • Example (contd.): Vertical fragmentation of PROJ relation – PROJ1: information about project budgets – PROJ2: information about project names and locations DDB 2008/09 J. Gamper Page 13Correctness Rules of Fragmentation • Completeness – Decomposition of relationR into fragmentsR ,R ,...,R is complete iff each 1 2 n data item inR can also be found in someR . i • Reconstruction – If relationR is decomposed into fragmentsR ,R ,...,R , then there should exist 1 2 n some relational operator∇ that reconstructsR from its fragments, i.e., R =R ∇...∇R 1 n ∗ Union to combine horizontal fragments ∗ Join to combine vertical fragments • Disjointness – If relationR is decomposed into fragmentsR ,R ,...,R and data itemd 1 2 n i appears in fragmentR , thend should not appear in any other fragmentR ,k =j j i k (exception: primary key attribute for vertical fragmentation) ∗ For horizontal fragmentation, data item is a tuple ∗ For vertical fragmentation, data item is an attribute DDB 2008/09 J. Gamper Page 14 6Horizontal Fragmentation • Intuition behind horizontal fragmentation – Every site should hold all information that is used to query at the site – The information at the site should be fragmented so the queries of the site run faster • Horizontal fragmentation is defined as selection operation,σ (R) p • Example: σ (PROJ) BUDGET200000 σ (PROJ) BUDGET≥200000 DDB 2008/09 J. Gamper Page 15Horizontal Fragmentation . . . • Computing horizontal fragmentation (idea) – Compute the frequency of the individual queries of the siteq ,...,q 1 Q – Rewrite the queries of the site in the conjunctive normal form (disjunction of conjunctions); the conjunctions are called minterms. – Compute the selectivity of the minterms – Find the minimal and complete set of minterms (predicates) ∗ The set of predicates is complete if and only if any two tuples in the same fragment are referenced with the same probability by any application ∗ The set of predicates is minimal if and only if there is at least one query that accesses the fragment – There is an algorithm how to find these fragments algorithmically (the algorithm CON MIN andPHORIZONTAL (pp 120122) of the textbook of the course) DDB 2008/09 J. Gamper Page 16Horizontal Fragmentation . . . • Example: Fragmentation of thePROJ relation – Consider the following query: Find the name and budget of projects given their PNO. – The query is issued at all three sites – Fragmentation based on LOC, using the set of predicates/minterms ′ ′ ′ ′ ′ ′ LOC = Montreal,LOC = NewYork,LOC = Paris PROJ =σ ′ ′(PROJ) 2 LOC= NewYork ′ ′ PROJ =σ (PROJ) 1 LOC= Montreal PNO PNAME BUDGET LOC PNO PNAME BUDGET LOC P2 Database Develop. 135000 New York P1 Instrumentation 150000 Montreal P3 CAD/CAM 250000 New York ′ ′ PROJ =σ (PROJ) 3 LOC= Paris PNO PNAME BUDGET LOC P4 Maintenance 310000 Paris • If access is only according to the location, the above set of predicates is complete – i.e., each tuple of each fragmentPROJ has the same probability of being accessed i • If there is a second query/application to access only those project tuples where the budget is less than 200000, the set of predicates is not complete. – P2 inPROJ has higher probability to be accessed 2 DDB 2008/09 J. Gamper Page 17Horizontal Fragmentation . . . • Example (contd.): – AddBUDGET ≤ 200000 andBUDGET 200000 to the set of predicates to make it complete. ′ ′ ′ ′ ′ ′ ⇒LOC = Montreal,LOC = NewYork,LOC = Paris, BUDGET ≥ 200000,BUDGET 200000 is a complete set – Minterms to fragment the relation are given as follows: ′ ′ (LOC = Montreal )∧(BUDGET ≤ 200000) ′ ′ (LOC = Montreal )∧(BUDGET 200000) ′ ′ (LOC = NewYork )∧(BUDGET ≤ 200000) ′ ′ (LOC = NewYork )∧(BUDGET 200000) ′ ′ (LOC = Paris)∧(BUDGET ≤ 200000) ′ ′ (LOC = Paris)∧(BUDGET 200000) DDB 2008/09 J. Gamper Page 18Horizontal Fragmentation . . . • Example (contd.): Now,PROJ will be split in two fragments 2 ′ ′ ′ ′ PROJ =σ (PROJ) PROJ =σ (PROJ) 1 2 LOC= Montreal LOC= NY ∧BUDGET200000 PNO PNAME BUDGET LOC PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal P2 Database Develop. 135000 New York ′ ′ ′ PROJ =σ (PROJ) PROJ =σ ′ ′ (PROJ) 3 LOC= Paris 2 LOC= NY ∧BUDGET≥200000 PNO PNAME BUDGET LOC PNO PNAME BUDGET LOC P4 Maintenance 310000 Paris P3 CAD/CAM 250000 New York – PROJ andPROJ would have been split in a similar way if tuples with budgets 1 2 smaller and greater than 200.000 would be stored DDB 2008/09 J. Gamper Page 19Horizontal Fragmentation . . . • In most cases intuition can be used to build horizontal partitions. Lett ,t ,t , 1 2 3 t ,t , andt ,t ,t ,t be query results. Then tuples would be fragmented in the 4 5 2 3 4 5 following way: t t t t t 1 2 3 4 5 DDB 2008/09 J. Gamper Page 20Vertical Fragmentation • Objective of vertical fragmentation is to partition a relation into a set of smaller relations so that many of the applications will run on only one fragment. • Vertical fragmentation of a relationR produces fragmentsR ,R ,... , each of which 1 2 contains a subset ofR’s attributes. • Vertical fragmentation is defined using the projection operation of the relational algebra: Π (R) A ,A ,...,A 1 2 n • Example: PROJ = Π (PROJ) 1 PNO,BUDGET PROJ = Π (PROJ) 2 PNO,PNAME,LOC • Vertical fragmentation has also been studied for (centralized) DBMS – Smaller relations, and hence less page accesses – e.g., MONET system DDB 2008/09 J. Gamper Page 21Vertical Fragmentation . . . • Vertical fragmentation is inherently more complicated than horizontal fragmentation – In horizontal partitioning: forn simple predicates, the number of possible minterms is n 2 ; some of them can be ruled out by existing implications/constraints. – In vertical partitioning: form nonprimary key attributes, the number of possible fragments is equal toB(m) (= themth Bell number), i.e., the number of partitions of a set withm members. m 9 ∗ For large numbers,B(m)≈m (e.g.,B(15) = 10 ) • Optimal solutions are not feasible, and heuristics need to be applied. DDB 2008/09 J. Gamper Page 22Vertical Fragmentation . . . • Two types of heuristics for vertical fragmentation exist: – Grouping: assign each attribute to one fragment, and at each step, join some of the fragments until some criteria is satisfied. ∗ Bottomup approach – Splitting: starts with a relation and decides on beneficial partitionings based on the access behaviour of applications to the attributes. ∗ Topdown approach ∗ Results in nonoverlapping fragments ∗ “Optimal” solution is probably closer to the full relation than to a set of small relations with only one attribute ∗ Only vertical fragmentation is considered here DDB 2008/09 J. Gamper Page 23Vertical Fragmentation . . . • Application information: The major information required as input for vertical fragmentation is related to applications – Since vertical fragmentation places in one fragment those attributes usually accessed together, there is a need for some measure that would define more precisely the notion of “togetherness”, i.e., how closely related the attributes are. – This information is obtained from queries and collected in the Attribute Usage Matrix and Attribute Affinity Matrix. DDB 2008/09 J. Gamper Page 24Vertical Fragmentation . . . • Given are the user queries/applicationsQ = (q ,...,q ) that will run on relation 1 q R(A ,...,A ) 1 n • Attribute Usage Matrix: Denotes which query uses which attribute: ( 1 iffq usesA i j use(q ,A ) = i j 0 otherwise – Theuse(q ,•) vectors for each application are easy to define if the designer knows i the applications that willl run on the DB (consider also the 8020 rule) DDB 2008/09 J. Gamper Page 25Vertical Fragmentation . . . • Example: Consider the following relation: PROJ(PNO,PNAME,BUDGET,LOC) and the following queries: q = SELECT BUDGET FROM PROJ WHERE PNO=Value 1 q = SELECT PNAME,BUDGET FROM PROJ 2 q = SELECT PNAME FROM PROJ WHERE LOC=Value 3 q = SELECT SUM(BUDGET) FROM PROJ WHERE LOC =Value 4 • Lets abbreviateA =PNO,A =PNAME,A =BUDGET,A =LOC 1 2 3 4 • Attribute Usage Matrix DDB 2008/09 J. Gamper Page 26Vertical Fragmentation . . . • Attribute Affinity Matrix: Denotes the frequency of two attributesA andA with i j respect to a set of queriesQ = (q ,...,q ): 1 n X X aff(A ,A ) = ( ref (q )acc (q )) i j k l k l use(q ,A )=1, i sitesl k k: use(q ,A )=1 j k where – ref (q ) is the cost (= number of accesses to(A ,A )) of queryq at sitel i j K k l – acc (q ) is the frequency of queryq at sitel l k k DDB 2008/09 J. Gamper Page 27Vertical Fragmentation . . . • Example (contd.): Let the cost of each query beref (q ) = 1, and the frequency k l acc (q ) of the queries be as follows: l k Site1 Site2 Site3 acc (q ) = 15 acc (q ) = 20 acc (q ) = 10 1 1 2 1 3 1 acc (q ) = 5 acc (q ) = 0 acc (q ) = 0 1 2 2 2 3 2 acc (q ) = 25 acc (q ) = 25 acc (q ) = 25 1 3 2 3 3 3 acc (q ) = 3 acc (q ) = 0 acc (q ) = 0 1 4 2 4 3 4 • Attribute affinity matrixaff(A ,A ) = i j P P 1 3 – e.g., aff(A ,A ) = acc (q ) = acc (q )+acc (q )+acc (q ) = 45 1 3 l k 1 1 2 1 3 1 k=1 l=1 (q is the only query to access bothA andA ) 1 1 3 DDB 2008/09 J. Gamper Page 28Vertical Fragmentation . . . • Take the attribute affinity matrix (AA) and reorganize the attribute orders to form clusters where the attributes in each cluster demonstrate high affinity to one another. • Bond energy algorithm (BEA) has been suggested to be useful for that purpose for several reasons: – It is designed specifically to determine groups of similar items as opposed to a linear ordering of the items. – The final groupings are insensitive to the order in which items are presented. 2 – The computation time is reasonable (O(n ), wheren is the number of attributes) • BEA: – Input: AA matrix – Output: Clustered AA matrix (CA) – Permutation is done in such a way to maximize the following global affinity mesaure (affinity ofA andA with their neighbors): i j n n XX AM = aff(A ,A )aff(A ,A )+ aff(A ,A )+ i j i j−1 i j+1 i=1 j=1 aff(A ,A )+ aff(A ,A ) i−1 j i+1 j DDB 2008/09 J. Gamper Page 29Vertical Fragmentation . . . • Example (contd.): Attribute Affinity MatrixCA after running the BEA – Elements with similar values are grouped together, and two clusters can be identified – An additional partitioning algorithm is needed to identify the clusters inCA ∗ Usually more clusters and more than one candidate partitioning, thus additional steps are needed to select the best clustering. – The resulting fragmentation after partitioning (PNO is added inPROJ explicilty 2 as key): PROJ =PNO,BUDGET 1 PROJ =PNO,PNAME,LOC 2 DDB 2008/09 J. Gamper Page 30Correctness of Vertical Fragmentation • RelationR is decomposed into fragmentsR ,R ,...,R 1 2 n – e.g.,PROJ =PNO,BUDGET,PNAME,LOC into PROJ =PNO,BUDGET andPROJ =PNO,PNAME,LOC 1 2 • Completeness – Guaranteed by the partitioning algortihm, which assigns each attribute inA to one partition • Reconstruction – Join to reconstruct vertical fragments – R =R ⋊⋉···⋊⋉R =PROJ ⋊⋉PROJ 1 n 1 2 • Disjointness – Attributes have to be disjoint in VF. Two cases are distinguished: ∗ If tuple IDs are used, the fragments are really disjoint ∗ Otherwise, key attributes are replicated automatically by the system ∗ e.g.,PNO in the above example DDB 2008/09 J. Gamper Page 31Mixed Fragmentation • In most cases simple horizontal or vertical fragmentation of a DB schema will not be sufficient to satisfy the requirements of the applications. • Mixed fragmentation (hybrid fragmentation): Consists of a horizontal fragment followed by a vertical fragmentation, or a vertical fragmentation followed by a horizontal fragmentation • Fragmentation is defined using the selection and projection operations of relational algebra: σ (Π (R)) p A ,...,A 1 n Π (σ (R)) A ,...,A p 1 n DDB 2008/09 J. Gamper Page 32Replication and Allocation • Replication: Which fragements shall be stored as multiple copies – Complete Replication ∗ Complete copy of the database is maintained in each site – Selective Replication ∗ Selected fragments are replicated in some sites • Allocation: On which sites to store the various fragments – Centralized ∗ Consists of a single DB and DBMS stored at one site with users distributed across the network – Partitioned ∗ Database is partitioned into disjoint fragments, each fragment assigned to one site DDB 2008/09 J. Gamper Page 33Replication . . . • Replicated DB – fully replicated: each fragment at each site – partially replicated: each fragment at some of the sites • Nonreplicated DB (= partitioned DB) – partitioned: each fragment resides at only one site • Rule of thumb: read only queries – If ≥ 1, then replication is advantageous, otherwise replication may update queries cause problems DDB 2008/09 J. Gamper Page 34Replication . . . • Comparison of replication alternatives DDB 2008/09 J. Gamper Page 35Fragment Allocation • Fragment allocation problem – Given are: – fragmentsF =F ,F ,...,F 1 2 n – network sitesS =S ,S ,...,S 1 2 m – and applicationsQ =q ,q ,...,q 1 2 l – Find: the ”optimal” distribution ofF toS • Optimality – Minimal cost ∗ Communication + storage + processing (read and update) ∗ Cost in terms of time (usually) – Performance ∗ Response time and/or throughput – Constraints ∗ Per site constraints (storage and processing) DDB 2008/09 J. Gamper Page 36Fragment Allocation . . . • Required information – Database Information ∗ selectivity of fragments ∗ size of a fragment – Application Information ∗ RR : number of read accesses of a queryq to a fragmentF ij i j ∗ UR : number of update accesses of queryq to a fragmentF ij i j ∗ u : a matrix indicating which queries updates which fragments, ij ∗ r : a similar matrix for retrievals ij ∗ originating site of each query – Site Information ∗ USC : unit cost of storing data at a siteS k k ∗ LPC : cost of processing one unit of data at a siteS k k – Network Information ∗ communication cost/frame between two sites ∗ frame size DDB 2008/09 J. Gamper Page 37Fragment Allocation . . . • We present an allocation model which attempts to – minimize the total cost of processing and storage – meet certain response time restrictions • General Form: min(Total Cost) – subject to ∗ response time constraint ∗ storage constraint ∗ processing constraint • Functions for the total cost and the constraints are presented in the next slides. • Decision variablex ij ( 1 if fragmentF is stored at siteS i j x = ij 0 otherwise DDB 2008/09 J. Gamper Page 38Fragment Allocation . . . • The total cost function has two components: storage and query processing. X X X TOC = STC + QPC i jk S ∈SF ∈F q ∈Q k j i – Storage cost of fragmentF at siteS : j k STC =USC ∗size(F )∗x i ij jk k whereUSC is the unit storage cost at sitek k – Query processing cost for a queryq is composed of two components: i ∗ composed of processing cost (PC) and transmission cost (TC) QPC =PC +TC i i i DDB 2008/09 J. Gamper Page 39Fragment Allocation . . . • Processing cost is a sum of three components: – access cost (AC), integrity contraint cost (IE), concurency control cost (CC) PC =AC +IE +CC i i i i – Access cost: X X AC = (UR +RR )∗x ∗LPC i ij ij ij k s ∈SF ∈F k j whereLPC is the unit process cost at sitek k – Integrity and concurrency costs: ∗ Can be similarly computed, though depends on the specific constraints • Note:AC assumes that processing a query involves decomposing it into a set of i subqueries, each of which works on a fragment, ..., – This is a very simplistic model – Does not take into consideration different query costs depending on the operator or different algorithms that are applied DDB 2008/09 J. Gamper Page 40Fragment Allocation . . . • The transmission cost is composed of two components: – Cost of processing updates (TCU) and cost of processing retrievals (TCR) TC =TCU +TCR i i i – Cost of updates: ∗ Inform all the sites that have replicas + a short confirmation message back X X TCU = u ∗(update message cost+ acknowledgment cost) i ij S ∈SF ∈F k j – Retrieval cost: ∗ Send retrieval request to all sites that have a copy of fragments that are needed + sending back the results from these sites to the originating site. X TCR = min∗(cost of retrieval request+ cost of sending back the result) i S ∈S k F ∈F j DDB 2008/09 J. Gamper Page 41Fragment Allocation . . . • Modeling the constraints – Response time constraint for a queryq i execution time ofq ≤ max. allowable response time forq i i – Storage constraints for a siteS k X storage requirement ofF atS ≤ storage capacity ofS j k k F ∈F j – Processing constraints for a siteS k X processing load ofq at siteS ≤ processing capacity ofS i k k q ∈Q i DDB 2008/09 J. Gamper Page 42Fragment Allocation . . . • Solution Methods – The complexity of this allocation model/problem is NPcomplete – Correspondence between the allocation problem and similar problems in other areas ∗ Plant location problem in operations research ∗ Knapsack problem ∗ Network flow problem – Hence, solutions from these areas can be reused – Use different heuristics to reduce the search space ∗ Assume that all candidate partitionings have been determined together with their associated costs and benefits in terms of query processing. · The problem is then reduced to find the optimal partitioning and placement for each relation ∗ Ignore replication at the first step and find an optimal nonreplicated solution · Replication is then handeled in a second step on top of the previous nonreplicated solution. DDB 2008/09 J. Gamper Page 43Conclusion • Distributed design decides on the placement of (parts of the) data and programs across the sites of a computer network • On the abstract level there are two patterns: Topdown and Bottomup • On the detail level design answers two key questions: fragmentation and allocation/replication of data – Horizontal fragmentation is defined via the selection operationσ (R) p ∗ Rewrites the queries of each site in the conjunctive normal form and finds a minimal and complete set of conjunctions to determine fragmentation – Vertical fragmentation via the projection operationπ (R) A ∗ Computes the attribute affinity matrix and groups “similar” attributes together – Mixed fragmentation is a combination of both approaches • Allocation/Replication of data – Type of replication: no replication, partial replication, full replication – Optimal allocation/replication modelled as a cost function under a set of constraints – The complexity of the problem is NPcomplete – Use of different heuristics to reduce the complexity DDB 2008/09 J. Gamper Page 44
Document Information
User Name:
User Type:
Uploaded Date: