《数据库课件总结:Database Chapter Seven Outline》由会员分享,可在线阅读,更多相关《数据库课件总结:Database Chapter Seven Outline(5页珍藏版)》请在金锄头文库上搜索。
1、Database Chapter Seven OutlineTrivial:A functional dependency is trivial if it is satisfied by all instances of a relationClosure:The set of all functional dependencies logically implied by F is the closure of F.We denote the closure of F by F+.F+ is a superset of F. BCNF:A relation schema R is in B
2、CNF with respect to a set F of functional dependencies if for all functional dependencies in F+ of the form a b where a R and b R, at least one of the following holds:a b is trivial (i.e., b a)a is a superkey for RDecomposing a Schema into BCNFSuppose we have a schema R and a non-trivial dependency
3、a b causes a violation of BCNF.We decompose R into: (a U b ) ( R - ( b - a ) ) 可能会进行BCNF分解时会产生更多不属于BCNF的结果模式,在这种情况下要进行进一步的分解,直至最后产生的结果是一个BCNF模式的集合。dependency preserving:If it is sufficient to test only those dependencies on each individual relation of a decomposition in order to ensure that all func
4、tional dependencies hold, then that decomposition is dependency preserving.Decide a decomposition is good or bad Lossless-join decide whether the relation is able to decompose or notBecause it is not always possible to achieve both BCNF and dependency preservation, we consider a weaker normal form,
5、known as third normal form.模式分解的目标:保持依赖的,无损分解,坚持BCNF模式的分解可能会导致非保持依赖的。Third Normal FormA relation schema R is in third normal form (3NF) if for all:a b in F+at least one of the following holds:a b is trivial (i.e., b a)a is a superkey for R Each attribute A in b a is contained in a candidate key for
6、R. (NOTE: each attribute may be in a different candidate key) Third condition is a minimal relaxation of BCNF to ensure dependency preservationClosure of a Set of Functional DependenciesGiven a relational schema R, a functional dependency f on R is logically implied by a set functional dependencies
7、F on R if every relation instance r(R) that satisfies F also satisfies f.if b a, then a b (reflexivity) if a b, then g a g b (augmentation) if a b, and b g, then a g (transitivity)If a b holds and a g holds, then a b g holds (union) If a b g holds, then a b holds and a g holds (decomposition) If a b
8、 holds and g b d holds, then a g d holds (pseudotransitivity) To compute the closure of a set of functional dependencies F: F + = Frepeatfor 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 de
9、pendencies 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 furtherClosure of Attribute SetsGiven a set of attributes a, define the closure of a under F (denoted by a+) as the set of attributes that are f
10、unctionally determined by a under F Algorithm to compute a+, the closure of a under F result := a;while (changes to result) dofor each b g in F dobeginif b result then result := result g end Uses of Attribute Closureesting for superkey:Testing functional dependenciesComputing closure of FComputation
11、 of candidate keyIf attribute A doesnt appear in any side of f, then A should be part of candidate key If attribute A appear only in the left side of f, then A should be part of candidate key If attribute A appear only in the right side of f, then A would not be part of candidate key If attribute A
12、appear in both sides of f, then A should be tested further, and Attribute Closure could be used.当属性A不出现在函数依赖两边,或者只出现在左边时候,A应该是候选码的一部分。出现在两边时,应该进一步计算其闭包。Canonical Cover 正则闭包Intuitively, a canonical cover of F is a “minimal” set of functional dependencies equivalent to F, having no redundant dependenc
13、ies or redundant parts of dependencies To test if attribute A a is extraneous in a 1. compute (a A)+ using the dependencies in F 用原来函数依赖关系 2. check that (a A)+ contains b; if it does, A is extraneous To test if attribute A b is extraneous in b 用去除属性后的函数依赖关系1. compute a+ using only the dependencies i
14、n F = (F a b) a (b A), 2. check that a+ contains A; if it does, A is extraneousA canonical cover for F is a set of dependencies Fc such that F logically implies all dependencies in Fc, and Fc logically implies all dependencies in F, andNo functional dependency in Fc contains an extraneous attributeE
15、ach left side of functional dependency in Fc is uniqueTo compute a canonical cover for F:repeatUse the union rule to replace any dependencies in F a1 b1 and a1 b2 with a1 b1 b2 Find a functional dependency a b with an extraneous attribute either in a or in b If an extraneous attribute is found, delete it from a b until F does