C H A P T E R 8
R
e
l
a
t
i
o
n
a
l
–
D
a
t
a
b
a
s
e
D
e
s
i
g
n
E
x
e
r
c
i
s
e
s
8.1 What is a lossy join decomposition? Give a small example including a relation
instance and its decomposition.
. .
.4
8.2 Give both dependency preserving and non–dependency preserving BCNF de–
8.3 Given a set of dependencies A → B, B → C and C → D, and a relation
r(A,
B,
C,
D), what is the best order for the BCNF decomposition to consider
the dependencies, and why?
. .
.3
8.4 Give the definition of when a relation is in BCNF.
. . .2
8.6 Given the relation
r(A,
B, C) and the functional dependencies A → B and B
→
C, give a lossless join dependency preserving decomposition of
r
into BCNF.
. .
.2
8.7 For the same relation as above, give a lossless join but
non–dependency
preserv–
ing decomposition of
r
into BCNF.
. .
.2
8.8 What, from a normalization perspective, is wrong with a system of student-id
8.10 Show that all binary relations are in BCNF.
. . .3
19
20 Chapter 8 Relational-Database
Design
8.11 Does A →→ BC logically imply A →→ B and A →→ C? If yes prove it, else give
8.12 Consider the following
functional dependencies
for
relation
schema R
=
(A, B, C,
D
,
8.13 Give an example of a relation, with one or more multivalued dependencies,
which is not in 4NF, and show how to bring your example to 4NF.
. .
.2+ 2
8.14 Dependency theory
a. Give an example of functional
dependencies
on relation
r(A,
B, C) such that
r
does not satisfy BCNF, and give an example relation showing the resultant
redundancy.
. .
.2 + 2
8.15 Show using the schema
r(A,
B,
C,
D, E) with functional dependencies A →
B
8.16 Dependency theory
a. Prove, from first principles, the transitivity axiom for multivalued depen-
dencies (α →→ β and β →→ γ ⇒ α →→ γ − β ).
. .
.4
b. Prove, using Armstrong’s axioms, the union rule for functional
dependen-
cies (α → β and α → γ ⇒ α → βγ).
. . .3
c. Does A →→ BC imply A →→ B and A →→ C. Prove or give a
counter-
example.
. . .3
d. Given a schema R(A, B,
C,
D), with an MVD A →→ BC, what MVDs, if
any, hold on a decomposition of R into R1(A, B, D) and R2(A,
C,
D)? Prove
8.17 Normalization
A
B
C
a1
a1
a2
a2
b
1
b
1
b
1
b
1
c1
c2
c1
c3
Exercises
21
b. Consider a relation schema R
=
(A, B,
C,
D, E) with the functional depen-
dencies
8.18 List all non-trivial functional dependencies satisfied by the following
relation
instance.
. . .5
8.19 Give a canonical cover of the following set of functional dependencies.
8.20 a. Given a relation R, it is sufficient to use the given set of dependencies
F
instead of
F
+
to test for BCNF violation. Explain why this is so (an informal
8.21 a. Give an example of a relation with no dependency preserving decomposi–
tion into BCNF, but which is in 3NF.
. .
.2
b. What is the redundancy in the above example?
. . .2
8.22 Normalization
a. Give the definition of BCNF.
. .
.2
b. Can a relation that is in BCNF not be in 3NF? Why or why not?
. .
.2
c. Give the definition of 4NF.
. .
.2
8.23 Suppose you have a relation
t
r
a
n
s
a
c
t
i
o
n
(
a
cco
u
n
t
n
o
,
seqno,
a
m
o
u
n
t
)
where the
amount can be positive (deposit) or negative (withdrawal), and the sequence
22 Chapter 8 Relational-Database Design
Write a query to output every accountno which has a negative balance (the balance
is the cumulative total from the earliest sequence number for the ac- count).
. .
.8
8.24 Questions on advanced normalization (Appendix
C)
a. When inferring MVDs on a decomposition of R into R1 and R2, what do we need
to do after computing
D+,
the closure of the given set of MVDs?
. .
.3
b. If a schema is in PJNF, list all the other normal forms it is in.
. .
.2
(NOT join) of the decomposed relations gives the original relations back,
and such that superkey, foreign key and domain constraints on the decom–
posed relations (without any other constraints) are sufficient to ensure that
the constraint above is satisfied.
Give the decomposition and the
super
/
foreign
key declarations in
pseu-
docode (no need for SQL). (NOTE: the solution may not be great if the num-
ber of courses is large, that’s OK.)
. .
.7