TUR09 CISC3000 Tutorial 09

Answer Reference

Question 1

List all nontrivial functional dependencies satisfied by the relation of the below figure:

Figure. Relation of Exercise

Answer Q1

:::success The nontrivial function dependencies are:
A -> B and C -> B, and
a dependency they logically imply: AC -> B.

C does not functionally determine A because the first and third tuples have the same C but different A values.

The same tuples also show B does not functionally determine A.

Likewise, A does not functionally determine C because the first two tuples have the same A value and different C values.

The same tuples also show B does not functionally determine C.
There are 19 trivial functional dependencies of the form a -> b, where b is included by a.:::

Question 2

Use Armstrong’s axioms to prove the soundness of the union rule.
(Hint: Use the augmentation rule to show that, if  α→β , then α→αβ.
Apply the augmentation rule again, using α→γ, and then apply the transitivity rule.)

Answer Q2

To prove that

Following the hint, we derive:
given
augmentation rule
union of identical sets
given
augmentation rule

transitivity rule and set union communtativity

Question 3

Use Armstrong’s axioms to prove the soundness of the pseudotransitivity rule.

Answer Q3

Proof using Armstrong’s axioms of the Pseudotransitivity Rule:

given
augmentation rule and set union commutativity
given

Result:
transitivity rule

Question 4

Use Armstrong’s axioms to prove the soundness of the decomposition rule.

Answer Q4

The decomposition rule, and its derivation from Armstrong’s axioms are given below:

given
reflexivity rule
transitivity rule
reflexive rule
transitive rule

Result:
1) transitivity rule
2) transitive rule

Question 5

Compute the closure of the following set F of functional dependencies for relation
schema R = (A, B, C, D, E).
A → BC
CD → E
B → D
E → A
List the candidate keys for R.

Answer Q5

schema R = (A, B, C, D, E)
F ={
    A → BC => A > B, A > C
  CD → E => A > C, A > D => A > E
  B → D => A > B, B > D => A > D
  E → A
}
Prime Attribute: A,E,C,D
(A, B, C, D, E) += {A, B, C, D, E} to
(A, x, x, x, x)
(A) += {A,B,C,D,E}
(E) += {E,A,B,C,D}
(CD) += {C,D,E,A,B}
    check (C) += {C}
  check (D) += {D}
(BC) += {B,C,D,E,A}
    check (B) += {B, D}
  check (C) += {C}

The candidate keys are A, BC, CD, and E.

:::success List the candidate keys for R
Ans:
Starting with A > BC, we can conclude: A > B and A > C.
Since A > B and B > D, A > D
(Decomposition transitive)
Since A > CD and CD > E, A > E
(Union, decomposition, Transitive)
Since A > A, we have A > ABCDE from the above steps
(Reflexive and Union)
Since E > A, E > ABCDE
(Transitive)
Since CD > E, CD > ABCDE
(Transitive)
Since B > D and BC > CD, BC > ABCDE
(Augmentative, Transitive)
Also, C > C, D > D, BD > D, etc

Therefore, any functional dependency with A, E, BC, or CD on the left-hand side of the arrow is in F+, no matter which other attributes appear in the FD.

Allow to represent any set of attriubutes in R, then F+ is
BD > B, BD > D,
C > C,
D > D,
BD > BD,
B > D, B > B, B > BD
and all FDs of the form A > alpha, BC > alpha, CD > alpha, E * > alpha
where alpha is any subset of { A, B, C, D, E }

The candidate keys are A, BC, CD and E. :::

Example

R = {A, B, C, G, H, I}
F = {
    A -> B,
  A -> C,
  CG -> H,
  CG -> I,
  B -> H
}
(A,B,C,G,H,I) += (A, B, C, G, H, I) to
(A,x,x,G,x,x) += (A, B, C, G, H, I)
(AG) += (A, B, C, G, H, I)

Question 6

Using the following functional dependencies,
compute the canonical cover Fc.

F = FDs {
  A → BC
  CD → E
  B → D
  E → A
}

Answer Q6

:::success The given set of FDs F is:

• A > BC => A > B, A > C
• CD > E
• B > D
• E > A

The left side of each FD in F is unique.
Also none of the attributes in the left side or right side of any of the FDs is extraneous 多餘的.
Therefore the canonical cover Fc is equal to F.:::

Example

Suppose that

Extraneous Attributes

F = { AB -> CD, A -> C}
{AB > C, A > D, D > C} - {AB > C} u {A > C}
{AB > CD, A > C} - { AB > CD } u { AB > CD - C}
implies F
F = {
    AB -> C,
  AB -> D,
  A -> C
} -- OK
{
    A -> CD, B -> CD, -- Wrong!!
  A -> C -- Wrong!!
}

R = {A, B, C}
F =  { A > BC, B > C, A > B, AB > C }
{ A > B, A > C, B > C, A > B, AB > C }
{ A > B, A > C, B > C, AB > C }
-- Remove B in AB > C
{ A > B, A > C, B > C, A > C }
{ A > B, A > C, B > C }
{ A > B, B > C }

Dependency Preservation

F = { AB > CD, A > E, E > C }
    = { AB > C, AB > D, A > E, E > C}
  = { AB > D, A > E, E > C}
  -- Because A > E > C -> A > C & AB > A, 
  -- del AB > C

Canonical Cover

Example - Dependency Preservation

Question:
Consider schema R(X,Y,Z,W)
and F={ X > Z，Z > X, Y > XZ,W > XZ}that holds on R.
Give the lossless,dependency preserving decomposition of this schema into 3NF

X > Z
Z > X
Y > XZ => Y > X, Y > Z
W > XZ => W > X, W > Z

:::success Ans:
The solution is follows:

1. Find {YW} += R

(这里有一个确定候选键的原则，首先如果一个属性只出现在了关系式右边，则必定不是，如果只出现在左边，则必定在候选键当中，然后加上别的属性，如果全集等于U，则就是候选键。候选键不只有一个，候选键中不能有冗余)

1. Calculate the Fc, Minimal Relation 最小關係集

2. With respect to F = {X > Z, Z > X, Y > XZ, W >XZ},

considering X in Y > XZ and Z in W > XZ,<br />{X > Z, Z > X, Y > Z, W > X} implies F, so X in Y > XZ and Z in W > XZ are all extraneous
(这两个属性在这里是多余的，首先把它们化简掉)

attributes, and one of canonical covers for F is
Fc = {X > Z, Z > X, Y > Z, W > X}
（但不是唯一一個）

1. 对Fc中的每一个依赖函数 A -> B，都将它变成AB这样一个 subschema

R1 = {XZ}, R2 = {YZ}, R3 = {WX}
由於缺少一個候選鍵，再加上
R4 = {YW}
因此，最後的分解式應該是
{XZ, YZ, WX, YW} :::