Distributed Databases Review CS347 June 6 2001 1 Fragmentation How to partition relation into various pieces fragments Types Primary Horizontal Derived Horizontal Vertical Hybrid of the above possible Desiderata Completeness don t lose tuples Disjointness no duplicate tuples Reconstruction make sure you can get back original relation 2 Minterm based horizontal frag Simple predicates Pr p1 p2 pm and R Generate minterm predicates from Pr Eliminate and simplify depends on app semantics Generate fragment m R for each minterm m Simple predicates Pr must be complete do not under fragment and minimal do not over fragment Use predicates occurring in most frequent queries 3 Derived Horizontal R fragmented into R1 R2 Rn For S derive S1 S2 Sn where Si S Ri Useful for join queries between R and S For completeness referential integrity constraint S For disjointness join attribute is key of R R Vertical Split R by attributes Repeat key attribute in each vertical fragment Attribute affinities define grouping 4 Localization Convert query tree on relations into query tree on fragments Simplify up down Rules R False C1 R C2 R C1 C2 R C1 S C2 R S C1 C2 R A S A A A Give vertical fragments Ri Ai R for any B A B R B i Ri B Ai 5 Distributed Operators Sort Basic sort sort each individual fragment Range partitioning sort partition by sort attribute basic sort Parallel external sort merge local sort range partition by sort attribute Key issue selecting partitioning vector Join Partitioned join only for equi joins Asymmetric fragment replicate join fragment R replicate S General fragment replicate join fragment and replicate R and S join all possible pairs Semi join programs to reduce communication cost 6 Query Optimization Exhaustive pruning Enumerate all possible QEP s with given set of operators Prune using heuristics e g avoid cartesian products Choose minimum cost QEP Hill climbing Initial feasible QEP set of QEP transformations Iterate until no more cost reduction Transform current QEP all possible ways Check cost of each transformed QEP Choose minimum and set as current QEP 7
View Full Document
Unlocking...