EB103A- Homework 8 Solved

Assignments
1 Description
Unless specified otherwise, you have to show all of your work. We cannot look into your mind and determine 72 your thinking process unless it is written out. You may refer to the numbers of the FDs as you refer to the 73 original FDs or as you number FDs in the new sets you get to simplify your explanation.
74                  2. You have to follow the procedures we covered in class and not any other procedures for what’s asked for. 75             You must use only the algorithmic techniques and not the ad-hoc approach that was described using the 76         university example, which may or may not work.

2 Review of the procedure
For your convenience a summary is provided. It may or may not be helpful for any specific question.
Input: A relational schema (informally, a relation) R and a set of FDs α.
Output: A set of relational schemas (informally, relations) such that the decompostion (a formal term for the
set) satisfies the conditions
It is lossless join
It preserves dependencies 84 3. The resulting tables are in 3NF. 85 Procedure:
Find a minimal cover for α, say ω
Produce a relation from each FD in ω by combining the attributes from both the LHS and the RHS
One by one, remove a relation that is a subset of another relation
If (at least) one of the relations contains a key of R, you are done
Otherwise, add a relation whose attributes form a key for R
Example 1. Assume that I am supposed to do that for
Relational Schema R = ABCDEF, with the following set of FDs
α:
AA → ABB
AB → C
B → C
E → F
F → E
I will start with the given set as Old, and I will attempt to simplify it by producing a “candidate” set New. In 100 general, the two sets are not equivalent. I can replace Old by New if and only if I can prove equivalence.
101                    Let’s start. Below we have a table with the current Old and the proposed New.

Old
New
1. AA → ABB
1. A → B
2. AB → C
2. AB → C
3. B → C
3. B → C
4. E → F
4. E → F
5. F → E
5. F → E
102

103 New was obtained by removing the “defective” parts of Old (which appeared only in 1.), which produces a 104 trivially equivalent New, so there is nothing to do for proving the equivalence. New now becomes Old.

Old
New
1. A → B
1. A → B
2. AB → C
2. A → C
3. B → C
3. B → C
4. E → F
4. E → F
5. F → E
5. F → E
105

106 We attempt to simplify 2. in Old getting 2. in New. New could only be stronger, so to prove equivalence we 107          need to prove 2. in New from all in Old.

108 We compute A+ = ABC, and as it contains C, we proved equivalence. New becomes Old.

Old
New
1. A → B
1. A → BC
2. A → C
2. B → C
3. B → C
3. E → F
4. E → F 5. F → E
4. F → E
109

110 We attempt to simplify 1. and 2. in Old getting 1. in New. This is an application of the union rule, which always 111 produces an equivalent set. So there is nothing to prove/check and New becomes Old.

Old
New
1. A → BC
1. A → C
2. B → C
2. B → C
3. E → F
3. E → F
4. F → E
4. F → E
112

113 We will try something that does not work, just to have an example. You do not need to try transformations that 114                     you believe do not work (if your belief is correct).

115 We attempt to simplify 1. in Old getting 1. in New. New could only be weaker, so to prove equivalence we need 116                     to prove 1. in Old from all in New.

117 We compute A+ = AC. As BC is not in AC, we proved non-equivalence. So we continue with Old (and do not 118            replace it by New).

Old
New
1. A → BC
1. A → B
2. B → C
2. B → C
3. E → F
3. E → F
4. F → E
4. F → E
119

120 We attempt to simplify 1. in Old getting 1. in New. New could only be weaker, so to prove equivalence we need 121                     to prove 1. in Old from all in New.

We compute A+ = ABC. As BC is in ABC, we proved equivalence.
We are done, but in general we need to make sure that no simplifications are possible. Here this is trivial because
There are no defective parts
The union rule cannot be applied
Both sides of all the FDs consist of one attribute only, so no simplification is possible (generally, this step 127 will require more work because even in a minimal cover there may be several attributes in some sides of 128 some FDs, and we need to check whether some of them should be removed).
Our minimal cover ω is
A → B
B → C
E → F
F → E
We get the following tables/relations
AB 136 2. BC
EF
FE
We remove FE because it is a subset of EF and we get
AB 141 2. BC
EF
We now proceed to get a global key for R. Perhaps one of the 3 tables already includes a global key for R. We 144 compute
AB+ = ABC
BC+ = BC
EF+ = EF
but we need R = ABCDEF.
We examine all the attributes of R accounting for all the FDs that are satisfied. It may be simplest to use the 150 minimal cover, so we will do that. But you can use any equivalent set of FDs, including the initial set given to us.
We classify the attributes based on where they appear in the FDs:
On both sides: B, E, F
On left side only: A
On right side only: C
Nowhere: D
AD appear in every key. C does not appear in any key. B, E, and F may appear in a key. We start with ABDEF, 157 which must contain a key. We cannot remove AD but may try to remove B, E, and F.
We attempt to remove B. We compute ADEF+ = ABCDEF. We can remove B and we continue with ADEF.
We attempt to remove E. We compute ADF+ = ABCDEF. We can remove E and we continue with ADF.
We attempt to remove F. We compute AD+ = ABCD. We cannot remove F and we continue with ADF.
Nothing else can be done. To remind: AD have to be in every key and we cannot remove F from ADF (because 162 we tried to remove it and did not succeed).
163                   As nothing else can be done, ADF is a global key. (ADE is another global key, but we are only looking for one.) 164          Our final decomposition is

AB
BC
EF
ADF
3 Assignments
You are given a relational schema R = ABCDE satisfying the set of FDs α:
AC → E
AC → CB
E → DE
D → B
(a) Compute ω, a minimal cover for α. You do not need to prove that what you claim to be a minimal 176 cover is in fact a minimal cover.
Review Example 1.
Do not skip any steps in your solution. That means for your larger case
Whenever your want to show an equivalence of two sets of FDs, you need to explicitly compute the 180 closure of an appropriate set of attributes using an appropriate set of FDs.
You do not need to prove that you have actually obtained a minimal cover. (You will be asked for
such a proof in another problem.)
You are given a relational schema R = ABCDEF satisfying the set of FDs α:
AB → C
A → E
DE → F
E → EF
F → B
(a) Compute ω, a minimal cover for α. You do not need to prove that what you claim to be a minimal 190 cover is in fact a minimal cover.
Review Example 1.
Do not skip any steps in your solution. That means for your larger case
Whenever your want to show an equivalence of two sets of FDs, you need to explicitly compute the 194 closure of an appropriate set of attributes using an appropriate set of FDs.
You do not need to prove that you have actually obtained a minimal cover. (You will be asked for
such a proof in another problem.)
You are given a relational schema R = ABCDEFGH satisfying the set of FDs:
AB → CD
C → EF
E → C
F → G
(a) Prove that the given set of FDs is already a minimal cover. To do that show that no simplification is 203 Attempt all simplifications.
204 To show that a simplification is not possible, you will need to explicitly compute the closures of the 205 relevant sets of attributes using the FDs in a relevant set of FDs. Do not use any shortcuts or heuristics.

(b) Produce a decomposition satisfying the conditions for Output in Section 3.2.