The branch relation branch-name branch-cityassets Downtown Brooklyn 9000000 Redwood Palo Alto 2100000 Perryridge Horseneck 1700000 Mianus Horseneck 400000 Round Hill Horseneck 8000000 Pownal Bennington 300000 North Town rye 3700000 Brighton Brooklyn 7100000 Branch-name>assets? assets→ Branch-name? Database System Concepts 7.16 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.16 ©Silberschatz, Korth and Sudarshan The branch Relation Branch-name→assets? assets→Branch-name?
Closure of a set of Functional Dependencies(函教依赖慕的阌包 Given a set F set of functional dependencies there are certain other functional dependencies that are logically implied(逻辑蘊合)byF. E.g.|fA→> B and b→C, then we can infer that a→C The set of all functional dependencies logically implied by F is the closure of f We denote the closure of f by ft We can find all of F+ by applying Armstrongs AXioms(A2) if Bca, then a→>B ( reflexivity)自反律 ifa→> B, then y a→>yB augmentation)增补率 ifa→>B,andβ→Y,thenα→>y( transitiⅳvity)传递率 These rules are Sound(保真的)(不会产生错误的函数依赖) complete(完备的)(对一个给定函教依赖集F,它们能产个 Database System Concepts 7.17 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.17 ©Silberschatz, Korth and Sudarshan Closure of a Set of Functional Dependencies（函数依赖集的闭包） Given a set F set of functional dependencies, there are certain other functional dependencies that are logically implied（逻辑蕴含） by F. E.g. If A → B and B → C, then we can infer that A → C The set of all functional dependencies logically implied by F is the closure of F. We denote the closure of F by F+ . We can find all of F+ by applying Armstrong’s Axioms（公理）: if , then → (reflexivity)自反律 if → , then → (augmentation)增补率 if → , and → , then → (transitivity)传递率 These rules are Sound（保真的）(不会产生错误的函数依赖) complete （完备的） (对一个给定函数依赖集F，它们能产生整个F+ )
Example R=(A, B, C,G,H, / F={A→>B A→C CG→H CG→ B→>H some members of ft A→H by transitivity from A→> B and B→>H AG→ by augmenting A→> C with G, to get AG→CG and then transitivity with CG>/ CG→H from cg→ H and cg→)l:“ union rule" can be inferred from definition of functional dependencies, or Augmentation of CG>/to infer CG->CGI, augmentation CG→ H to infer CG/→Hl, and then transitivity Database System Concepts 7.18 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.18 ©Silberschatz, Korth and Sudarshan Example R = (A, B, C, G, H, I) F = { A → B A → C CG → H CG → I B → H} some members of F+ A → H by transitivity from A → B and B → H AG → I by augmenting A → C with G, to get AG → CG and then transitivity with CG → I CG → HI from CG → H and CG → I : “union rule” can be inferred from – definition of functional dependencies, or – Augmentation of CG → I to infer CG → CGI, augmentation of CG → H to infer CGI → HI, and then transitivity
Procedure for Computing F+ To compute the closure of a set of functional dependencies F repeat for each functional dependency fin Ft apply reflexivity and augmentation rules on f add the resulting functional dependencies to F for each pair of functional dependencies f,and f2 in F if f, and f2 can be combined using transitivity then add the resulting functional dependency to F until Ft does not change any further 2×2n=2n+1 NOTE: We will see an alternative procedure for this task later Database System Concepts 7.19 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.19 ©Silberschatz, Korth and Sudarshan Procedure for Computing F+ To compute the closure of a set of functional dependencies F: F + = F repeat for each functional dependency f in F + apply reflexivity and augmentation rules on f add the resulting functional dependencies to F + for each pair of functional dependencies f1and f2 in F + if f1 and f2 can be combined using transitivity then add the resulting functional dependency to F + until F + does not change any further 2×2 n＝2 n+1 NOTE: We will see an alternative procedure for this task later
Closure of Functional Dependencies (Cont) We can further simplify manual computation of Ft by using the following additional rules fa→> B holds and a→ >y holds, then a→β y holds unon)合开率 fa→ By holds, then a→> B holds and a- r holds ( decomposition)分解率 fa→> B holds and B→>δ holds, then ay->8 holds ( pseudotransitivity)伪传递率 The above rules can be inferred from Armstrongs axioms 标 Database System Concepts 7.20 @Silberschatz, Korth and Sudarshan
Database System Concepts 7.20 ©Silberschatz, Korth and Sudarshan Closure of Functional Dependencies (Cont.) We can further simplify manual computation of F + by using the following additional rules. If → holds and → holds, then → holds (union)合并率 If → holds, then → holds and → holds (decomposition)分解率 If → holds and → holds, then → holds (pseudotransitivity)伪传递率 The above rules can be inferred from Armstrong’s axioms