|
Chris Pollett > Old Classes
> |
HW5 Solutions PageAgain, the solution below is a student solution. That student will receive one bonus point. As the HWs are not yet graded, I eyeballed the larger submitted files to find one that looked decent. The answers have not been exhaustively checked but should serve as a guide. The grader has said he won't be able to grade until Wednesday (your test day).
*********10.19*********
f cover g = g can be derived from f+
f is equivalent to g => f covers g and g covers f
f= { A->C g = { A->CD
AC->D E->AH
E->AD }
E->H
}
f covers g
A+ = {A,C,D} AA = A, IR6
f.d. A->CD of g is in A+ of f
E+ = {E,A,D,H,C}
f.d. E->AH of g is in E+ of f
therefore f covers g
g covers f
A+ = {A,C,D}
f.d. A->C, AC->D of f is in A+ of g
E+ = {E,A,H,C,D}
f.d. E->AD,E->H of f is in E+ of g
therefore g covers f
Since f covers g and g covers f, f and g are equivalent
*********10.21*********
emp_dept: G = { ssn->{ename,bdate,address,dnumber},
dnumber ->{dname,dmgrssn}
}
F ={ ssn -> ename
ssn -> bdate
ssn -> address
ssn -> dnumber
dnumber -> dname
dnumber -> dmgrssn
}
no, G is not minimal since F is minimal and F is equivalent to G
prove of equivalent
F covers G
ssn+ ={ ssn, ename, bdate, address, dnumber } ----->F
f.d. ssn ->{ename,bdate,address,dnumber} of G is in ssn+ of F
dnumber+ = {dnumber,dname,dmgrssn} ---->F
f.d. dnumber->{dname,dmgrssn} of G is in dnumber+ of F
G covers F
ssn+ ={ ssn, ename, bdate, address, dnumber } G
f.d.
ssn -> ename
ssn -> bdate
ssn -> address
ssn -> dnumber of F is in ssn+ of G
dnumber+ = {dnumber,dname,dmgrssn}
f.d.
dnumber -> dname
dnumber -> dmgrssn of G is in dnumber+ of F
let F' be minimal exclude f.d. "ssn -> ename"
F' ={ ssn -> bdate
ssn -> address
ssn -> dnumber
dnumber -> dname
dnumber -> dmgrssn
}
check F' covers G
ssn+ = {ssn,bdate,address,dnumber} does not cover the f.d.
ssn -> {ename,bdate,address,dnumber} since it missed ename
attribute
let F' be minimal exclude f.d. "ssn -> bdate"
F' ={ ssn -> ename
ssn -> address
ssn -> dnumber
dnumber -> dname
dnumber -> dmgrssn
}
ssn+ = {ssn,ename,address,dnumber} does not cover the f.d.
ssn -> {ename,bdate,address,dnumber} since it missed bdate
attribute
let F' be minimal exclude f.d. "ssn -> address"
F' ={ ssn -> ename
ssn -> bdate
ssn -> dnumber
dnumber -> dname
dnumber -> dmgrssn
}
ssn+ = {ssn,ename,bdate,dnumber} does not cover the f.d.
ssn -> {ename,bdate,address,dnumber} since it missed address
attribute
let F' be minimal exclude f.d. "ssn -> dnumber"
F' ={ ssn -> ename
ssn -> bdate
ssn -> address
dnumber -> dname
dnumber -> dmgrssn
}
ssn+ = {ssn,ename,bdate,dnumber} does not cover the f.d.
ssn -> {ename,bdate,address,dnumber} since it missed dnumber
attribute
let F' be minimal exclude f.d. "dnumber -> dname"
F' ={ ssn -> ename
ssn -> bdate
ssn -> address
ssn -> dnumber
dnumber -> dmgrssn
}
dnumber = {dmgrssn} does not cover the f.d.
dnumber -> {dnumber,dmgrssn} since it missed dnumber attribute
let F' be minimal exclude f.d. "dnumber -> dname"
F' ={ ssn -> ename
ssn -> bdate
ssn -> address
ssn -> dnumber
dnumber -> dmgrssn
}
dnumber = {dmgrssn} does not cover the f.d.
dnumber -> {dnumber,dmgrssn} since it missed dname attribute
let F' be minimal exclude f.d. "dnumber -> dmgrssn"
F' ={ ssn -> ename
ssn -> bdate
ssn -> address
ssn -> dnumber
dnumber -> dname
}
dnumber = {dname} does not cover the f.d.
dnumber -> {dnumber,dmgrssn} since it missed dmgrssn attribute
*********10.26*********
R={A,B,C,D,E,F,G,H,I,J}
a) F={ AB->C
A->DE
B->F
F->GH
D->IJ
}
{BCDEFGHIJ}+ = {B,C,D,E,F,G,H,I,F} covers F? miss 'A' therefore NO
{ACDEFGHIJ}+ = {A,C,D,E,F,G,H,I,F} covers F? miss 'B' therefore NO
{ABDEFGHIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABEFGHIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABFGHIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABGHIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABHIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABIJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{ABJ}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes but not a key
{AB}+ = {A,B,C,D,E,F,G,H,I,F} covers F? yes and it's a key
b)2NF fully functional dependency
EP1
AB -> C
EP2
A ->DEIJ
EP3
B ->FGH
c) 3nf get rid of transitive function dependency
EP1
AB -> C
EP2
A -> DE
EP3
B -> F
EP4
F -> GH
EP5
D -> IJ
*********11.29*********
a)
i.
D1 = {R1,R2,R3,R4,R5}, R1 ={A,B,C}, R2 ={A,D,E},
R3={B,F}, R4={F,G,H}, R5={D,I,J}
F = {
{A,B} -> {C},
{A} -> {D,E},
{B} -> {F},
{F} -> {G,H},
{D} -> {I,J}
}
F1 = {{A,B} -> {C}}
F2 = {{A} -> {D,E}}
F3 = {{B} -> {F}}
F4 = {{F} -> {G,H}}
F5 = {{D} -> {I,J}}
(F1 U F2 U F3 U F4 UF5)+ = F+
{ABCDEFGHIJ} = {ABCDEFGHIJ}
therefore D1 holds funtional preservation
ii.
After step 3 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 - - - - - - -
R2 a1 - - a4 a5 - - - - -
R3 - a2 - - - a6 - - - -
R4 - - - - - a6 a7 a8 - -
R5 - - - a4 - - - - a9 a10
After step 4 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 **** so d1 has lossless
join property ****
R2 a1 - - a4 a5 - - - a9 a10
R3 - a2 - - - a6 a7 a8 - -
R4 - - - - - a6 a7 a8 - -
R5 - - - a4 - - - - a9 a10
iii.
R1 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R2 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R3 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R4 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R5 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
b)
i.
D2 = {R1,R2,R3}, R1 ={A,B,C,D,E}, R2 ={B,F,G,H},
R3={D,I,J}
F = {
{A,B} -> {C},
{A} -> {D,E},
{B} -> {F},
{F} -> {G,H},
{D} -> {I,J}
}
F1 = {{A,B} -> {C}, {A} -> {D,E}}
F2 = {{B} -> {F},{F} -> {G,H}}
F3 = {{D} -> {I,J}}
(F1 U F2 U F3 U F4 UF5)+ = F+
{ABCDEFGHIJ} = {ABCDEFGHIJ}
therefore D2 holds funtional preservation
ii.
After step 3 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 a4 a5 - - - - -
R2 - a2 - - - a6 a7 a8 - -
R3 - - - a4 - - - - a9 a10
After step 4 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 **** so d2 has lossless join
property ****
R2 - a2 - - - a6 a7 a8 - -
R3 - - - a4 - - - - a9 a10
iii.
R1 - 1NF since a nonkey attribute (D,E) is partially dependent on
a prime attribute (A) and therefore not
in 2NF. And thus, it is in 1NF.
R2 - 2NF since its attribute is fully functional denpedent on its
key.
It is not 3NF because a nonkey attribute is functionally
determined by another nonkey attribute
R3 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
c)
i.
D1 = {R1,R2,R3,R4,R5}, R1 ={A,B,C,D}, R2 ={D,E},
R3={B,F}, R4={F,G,H}, R5={D,I,J}
F = {
{A,B} -> {C},
{A} -> {D,E},
{B} -> {F},
{F} -> {G,H},
{D} -> {I,J}
}
F1 = {{A,B} -> {C}}
F2 = {}
F3 = {{B} -> {F}}
F4 = {{F} -> {G,H}}
F5 = {{D} -> {I,J}}
(F1 U F2 U F3 U F4 UF5)+ = F+
{ABCDFGHIJ} = {ABCDEFGHIJ}
therefore D3 doesn't hold funtional preservation since it doesn't have
f.d. {A} -> {D,E} and missed 'E'
ii.
After step 3 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 a4 - - - - - -
R2 - - - a4 a5 - - - - -
R3 - a2 - - - a6 - - - -
R4 - - - - - a6 a7 a8 - -
R5 - - - a4 - - - - a9 a10
After step 4 in the lossless join algorithm in lecture:
A B C D E F G H I J
R1 a1 a2 a3 a4 - a6 a7 a8 a9 a10 **** does not have lossless
join property
R2 - - - a4 a5 - - - - -
R3 - a2 - - - a6 a7 a8 - -
R4 - - - - - a6 a7 a8 - -
R5 - - - a4 - - - - a9 a10
iii.
R1 - 1NF since a nonkey attribute (D) is partially dependent on a
prime attribute (A) and therefore not
in 2NF. And thus, it is in 1NF.
R2 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R3 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R4 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
R5 - BCNF since we have no nonkey attribute determines other
nonkey attributes (pg321 table10.1).
and no other nonkey attribute determines prime attributes.
Since there isn't any given information
that these attributes are multivalue, I assumed that they
are not multivalue attributes.
*********11.30*********
Refrig (Model#, Year, Price, Manuf_Plant, Color)
Refrig (M , Y , P , MP , C )
F = {
M -> MP,
{M,Y} -> P,
MP -> C
}
a) M+ = {M, MP, C} not equivalent with F+, therefore not a key
{M,Y}+ = {M, Y, P, MP, C} equivalent with F+, therefore it is a key
{M,C}+ = {M, C, MP} not equivalent with F+, therefore not a key
b) A key is {M, Y}. So there is a transitive dependency from M to C and MP partially depends on M. So it is in 1NF
but not 2NF.
c) R1 = {M, Y, P}
R2 = {M, MP, C}
R1 - R2 = M, M is in the F+. Therefore, it has lossless join property.
|