Database
Assignment #2 – Exercises
1. Exercise 3.2.1(3rd edition) ¡æ Exercise 3.6.1 (2rd edition). ¡æ ¿¬½À¹®Á¦ 3.5.1 (¹ø¿ªÆÇ)
2.
Exercise 3.2.2(3rd
edition) ¡æ Exercise 3.6.2 (2rd
edition). ¡æ ¿¬½À¹®Á¦ 3.5.2 (¹ø¿ªÆÇ)
3. Exercise 3.2.6 (3rd edition) : Show that
each of the following are not valid rules about FD¡¯s by giving example relations that satisfy the
given FD¡¯s (following the ¡°if¡±) but not the FD that allegedly follows (after the ¡°then¡±).
a) If AB ¡æ C, then A ¡æ C or B ¡æ C.
b) If A ¡æ B then B ¡æ A.
c) If AB ¡æ C and A ¡æ C, then B ¡æ C.
4. Exercise 3.3.1 (3rd edition): For each of the
following relation schemas and sets of FD's:
a) R(A, B, C, D) with FD's
B ¡æ A, C ¡æ B, D ¡æ C, and A ¡æ D.
b) R(A, B, C, D) with FD's
BC ¡æ D, D ¡æ A, and A ¡æ B.
c) R(A, B, C, D) with FD's
A ¡æ B and A ¡æ C
d) R(A, B, C, D) with FD's
AB ¡æ D, BD ¡æ C. CD ¡æ A, and AC ¡æ B.
e) R(A, B, C, D, E) with
FD's AB ¡æ C, C ¡æ E, E ¡æ A, and E ¡æ D.
f) R(A, B, C, D, E) with
FD's AB ¡æ C, DE ¡æ C, B ¡æ E.
do the following:
¨ç Indicate all the BCNF
violations. Do not forget to consider FD's that are not in the given set, but
follow from them. However, it is not necessary to give violations that have
more than one attribute on the right side.
¨è Decompose the relations,
as necessary, into collections of relations that are in BCNF.
5. Exercise 3.4.1 (3rd edition): Let R(A, B, C, D, E) be decomposed into relations with the
following three sets of attributes: {A, B, C}, {B, C, D}, and {A, C, E}. For
each of the following sets of FD's, use the chase test to tell whether the
decomposition of R is lossless. For those that are not lossless, give an
example of an instance of R that returns more than R when projected onto the
decomposed relations and rejoined.
a) BC ¡æ D and AC ¡æ E.
b) B ¡æ E, E ¡æ D and B ¡æ E.
c) B ¡æ E, CE ¡æ D and D ¡æ E.
d) A ¡æ D and CD ¡æ B.
6. Exercise 3.5.3 (3rd edition): Consider the relation
Courses(C, T, H, R, S, G), whose attributes may be
thought of informally as course, teacher, hour, room, student, and grade. Let
the set of FD's for Courses be C ¡æ T, HR ¡æ C, HT ¡æ R, HS ¡æ R, and CS ¡æ
G. Intuitively, the first says that a course has a unique teacher, and the
second says that only one course can meet in a given room at a given hour. The
third says that a teacher can be in only one room at a given hour, and the
fourth says the same about students. The last says that students get only one
grade in a course.
a) What are all the keys
for Courses?
b) Verify that the given
FD's are their own minimal basis.
c) Use the 3NF synthesis
algorithm to find a lossless-join, dependency-preserving decomposition of R
into 3NF relations. Are any of the relations not in BCNF?
[Chase
test to see the decomposition is lossless]
For a given table R and
decomposition of this table, we can apply chase test to tell whether it is a
lossless.
It is explained with the following example;
R(A,B,C,D) is a relation
with FD: F={AàB, BàC, CDàA}. And the decomposed
tables are R1(A,D), R2(A,C), and R3(B,C,D).
We want to check whether this decomposition is a lossless. The process of chase
test is explained as below;
We conclude that tuple t(a,b,c,d) is in R¡¯. It means that
tuple t is produced by the join operation and the decomposition is lossless.
Submission
Deadline: Nov. 12 before the class