数据库课件总结：Database-Chapter-Seven-Outline.docx

Database Chapter Seven Outline
Trivial:
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 FtF+ is a superset of F.
BCNF:
A relation schema R is in BCNF with respect to a set F of functional dependencies if for all functional dependencies in F+ of the form a —>£where aq R and J3^R, at least one of the following holds:
a T 0 is trivial (i.e., a)a is a superkey for R
Decomposing a Schema into BCNF
Suppose we have a schema R and a non-trivial dependency a causes a violation of BCNF.
We decompose R into:
• (a U p )(R-(/?-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 functional dependencies hold, then that decomposition is dependency preserving.
Decide a decomposition is good or badLossless-join decide whether the relation is able to decompose or not
Because it is not always possible to achieve both BCNF and dependency preservation, we consider a weaker normal form, known as third normal form.
模式分解的目标：保持依赖的，无损分解，坚持BCNF模式的分解可能会导致非保持依赖的。
Third Normal FormA relation schema R is in third normal form (3NF) if for all:
a - £in F+at least one of the following holds:
a f - is trivial (i.e., a) a is a superkey for R Each attribute A in p- a is contained in a candidate key for 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 Dependencies
Given a relational schema R, a functional dependency/on R is logically implied by a set functional dependencies F on R if every relation instance r(R) that satisfies F also satisfiesif Q之 a, then a —尸(reflexivity)
if a->» theny af yp(augmentation)if a —川 and% then a f y (transitivity)
If a —川 holds and a f y holds, then a f holds (union)If a—holds, then a f 尸 holds and a —>y holds (decomposition)
If a —> 夕 holds and y 尸—3 holds, then a y f B holds (pseudotransitivity)To compute the closure of a set of functional dependencies F:
F+ = Frepeat
for each functional dependency/in F+apply reflexivity and augmentation rules on/ add the resulting functional dependencies to F +
for each pair of functional dependencies fiand/2 in F + if/i and/2 can be combined using transitivity then add the resulting functional dependency to F + until F+ does not change any furtherClosure of Attribute Sets
Given a set of attributes a, define the closure of a under F (denoted by a+) as the set of attributes that are functionally determined by a under FAlgorithm to compute a+, the closure of a under F result := a;
while (changes to result) dofor each 0 - y in F do
begin
if p o result then result := result u y endUses of Attribute Closure
esting for superkey:
Testing functional dependenciesComputing closure of F
Computation of candidate key
If attribute A doesn't 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 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 dependencies or redundant parts of dependencies To test if attribute A e a is extraneous in acompute ({a}- A)+ using the dependencies in F用原来函数依赖关系
1. check that ({a} - A)+ contains p; if it does, A is extraneousTo test if attribute/A e p is extraneous in p用去除属性后的函数依赖关系
1. compute a+ using only the dependencies inF' = (F - {a —> P}) o {a f 4一八)}7
2. check that a+ contains A; if it does, A is extraneousA canonical cover for Fis a set of dependencies Fcsuch that
F logically implies all dependencies in FC/ and logically implies all dependencies in F, and
No functional dependency in Fc contains an extraneous attribute Each left side of functional dependency in Fc is uniqueTo compute a canonical cover for F:
repeat
Use the union rule to replace any dependencies in Fai f Pi and ai -历 with ai —> 历能
Find a functional dependency a f [3 with anextraneous attribute either in a or in p
If an extraneous attribute is found, delete it from a -> puntil F does not change
Lossless-join Decomposition
A decomposition of R into Ri and Ri is lossless join if and only if at least one of the following dependencies is in F+:
RiC R2 f RiRl C /?2 -，/?2
如果R'CRz是Rl或者R2的超码，那么是无损分解。
Dependency PreservationA decomposition is dependency preserving, if
(FiDF2D.・. uFn)+= F +方法一：计算F+与F+比拟是否相等。
方法二：
To check if a dependency a f p is preserved in a decomposition of R into Ri, R2, Rn we apply the following test (with attribute closure done with respect to F) result = a while (changes to result) dofor each Ri in the decomposition
t = (result n R)+ n R, result = result u t
If result contains all attributes in p, then the functional dependency a — 0 is preserved.
Testing Decomposition for BCNF
for every set of attributes a o R), check that a+ (the attribute closure of a under F) either includes no attribute of Ri- a, or includes all attributes of /?/.
► If the condition is violated by some a f in F+, the dependencya f (a+ - a ) c R/
can be shown to hold on Ri, and /?, violates BCNF.
BCNF Decomposition Algorithmresult := {R};
done := false;compute F+;
while (not done) do
if (there is a schema R)in result that is not in BCNF)then begin
let a t 0 be a nontrivial functional dependency that holds on R,such that a f Ri is not in F+, and an/? = 0;
result := (result - Ri) u (/?, -/?) u (a, P);end
else done := true;3NF Decomposition Algorithm
Let Fc be a canonical cover for F;i := 0;
for each functional dependency a -> /7in Fc doif none of the schemas & 1 < / < / contains a p
then begin/ := / + 1;
R ：= a BV
endif none of the schemas /?；, 1 < ; < / contains a
candidate key for/?’then begin
/ := / + 1;Rj := any candidate key for R;
Vend
return R% RJctA«n CnncAnfc - M* Pditmn hilv 7ft7 似2曲，Knrth and Ri
Above algorithm ensures:
each relation schema Ri is in 3NF decomposition is dependency preserving and lossless-join Proof of correctness is at end of this fileComparison of BCNF and 3NF
It is always possible to decompose a relation into a set of relations that are in 3NF such that:
the decomposition is losslessthe dependencies are preserved
It is always possible to decompose a relation into a set of relations that are in BCNF such that:
the decomposition is losslessit may not be possible to preserve dependencies.
Goal for a relational database design is:
BCNF.
Lossless join.
Dependency preservation.
If we cannot achieve this, we accept one ofLack of dependency preservation
Redundancy due to use of 3NF