1. Consider a relation R(A,B,C) and suppose R
contains the following four tuples:
A
B
C
1
2
2
1
3
2
1
4
2
2
5
2
For each of the following functional dependencies, state whether or
not the dependency is satisfied by this relation instance.
(a) A → B
(b) A → C
(c) B → A
(d) B → C
(e) C → A
(f) C → B
(g) AB → C
(h) AC → B
(i) BC → A
2. Which of the
following rules for functional dependencies are correct (i.e., the
rule holds over all databases) and which are incorrect (i.e., the
rule does not hold over some database)? For incorrect rules, give
the simplest example relation instance you can come up with where
the rule does not hold.
(a) If A → B and BC → D, then AC → D
(b) If AB → C then A → C
(c) If A → B1,..,Bn and C1,..,Cm → D and
{C1,...,Cm} is a subset of {B1,..,Bn}, then A → D
(d) If A → C and B → C and ABC → D, then A → D
3. Consider a
relation R(A,B,C,D,E) with the following functional dependencies:
A → B
CD → E
E → A
B → D
Specify all minimal keys for R.
4. Consider a
relation R(A,B,C,D,E,F,G,H) with the following functional
dependencies:
A → BCD
AD → E
EFG → H
F → GH
(a) Based on these functional dependencies, there is one minimal key
for R. What is it?
(b) One of the four functional dependencies can be removed without
altering the key. Which one?
5. Consider a
relation R(A,B,C,D,E,F) with the following set of functional
dependencies:
A → C
DE → F
B → D
(a) Based on these functional dependencies, there is one minimal key
for R. What is it?
(b) Add to the above set of functional dependencies the dependency A
→ B. Now suppose we want A to be a key. Name one more functional
dependency that, if added to the set, makes A a key. As an
additional restriction, the new functional dependency must have only
one attribute on the left-hand side and only one attribute on the
right-hand side.
6. Consider the
following sets of functional dependencies over a relation R(A,B,C).
F1 = {A → B, B → C}
F2 = {A → B, A → C}
F3 = {A → B, AB → C}
Which of these sets are equivalent? (Two sets of functional
dependencies (FDs) F and F' are equivalent if all FDs in F' follow
from the ones in F, and all FDs in F follow from the ones in F'.)
Multivalued Dependencies
7. Consider
a relation R(A,B,C) and suppose R contains the following five
tuples:
A
B
C
1
2
3
1
3
2
1
2
2
3
2
1
3
2
3
For each of the following multivalued dependencies, state whether or
not the dependency is satisfied by this relation instance.
(a) A →> B
(b) A →> C
(c) B →> A
(d) B →> C
(e) C →> A
(f) C →> B
8. Consider a
relation R(A,B,C,D) that satisfies A →> B and B →>
C. Suppose R contains the tuples (1,2,3,4) and (1,5,6,7). What other
tuples must also be in R?
9. Which of the
following rules for multivalued dependencies are correct (i.e., the
rule holds over all databases) and which are incorrect (i.e., the
rule does not hold over some database)? For incorrect rules, give
the simplest example relation instance you can come up with where
the rule does not hold.
(a) If A →> BC and A →> CD then A →> C
(b) If AB →> C then A →> C
(c) If A →> BC then A →> B and A →> C
(d) If A →> BCD and A →> C then A →> BD
Functional and Multivalued
Dependencies
10. The relation
R(A,B,C) satisfies an unknown set of functional and multivalued
dependencies. All we know about R is that it allows at least the
following two instances:
A
B
C
1
2
3
1
3
4
A
B
C
1
3
3
2
2
4
3
3
3
Consider the following possible functional and multivalued
dependencies:
(a) A → B
(b) A → C
(c) B → A
(d) B → C
(e) C → A
(f) C → B
(g) AB → C
(h) AC → B
(i) BC → A
(j) A →> B
(k) A →> C
(l) B →> A
(m) B →> C
(n) C →> A
(o) C →> B
Which of these dependencies are ruled out by the two instances of R
above?
11. Consider the
following relational schema:
Car(make, model, year, color, dealer)
Each tuple in relation Car specifies that one or more cars of a
particular make, model, and year in a particular color are available
at a particular dealer. For example, the tuple
(Honda, Civic, 2010, Blue, Fred's Friendly Folks)
indicates that 2010 Honda Civics in blue are available at the Fred's
Friendly Folks car dealer.
For each of the following English statements, write one nontrivial
functional or multivalued dependency that best captures the
statement.
(a) The model name for a car is trademarked by its make, i.e., no
two makes can use the same model name.
(b) Each dealer sells only one model of each make of car.
(c) If a particular make, model, and year of a car is available in a
particular color at a particular dealer, then that color is
available at all dealers carrying the same make, model, and year.
(d) Based on your answers for (a)-(c), specify all minimal keys for
relation Car.
Functional and Multivalued
Dependencies, Normal Forms, Decomposition
12. Consider the
following two relational schemas:
Schema 1: R(A,B,C,D)
Schema 2: R1(A,B,C), R2(B,D)
(a) Consider Schema 1 and suppose that the only functional
dependencies that hold on the relations in this schema are A → B, C
→ D, and all dependencies that follow from these. Is Schema 1 in
Boyce-Codd Normal Form (BCNF)?
(b) Consider Schema 2 and suppose that the only functional
dependencies that hold on the relations in this schema are A → B, A
→ C, B → A, A → D, and all dependencies that follow from these. Is
Schema 2 in BCNF?
(c) Suppose we omit dependency A → D from part (b). Is Schema 2 in
BCNF?
(d) Consider Schema 1 and suppose that the only functional and
multivalued dependencies that hold on the relations in this schema
are A → BC, B → D, B →>
CD, and all dependencies that follow from these. Is Schema 1 in
Fourth Normal Form (4NF)?
(e) Consider Schema 2 and suppose that the only functional and
multivalued dependencies that hold on the relations in this schema
are A → BD, D → C, A →>
C, B →> D, and all
dependencies that follow from these. Is Schema 2 in 4NF?
13. Consider a
relation R(A,B,C) and suppose R contains the following four tuples:
A
B
C
1
2
3
1
2
4
5
2
3
5
2
6
(a) Specify all completely nontrivial functional dependencies that
hold on this instance of R.
(b) Specify all nontrivial multivalued dependencies that hold on
this instance of R. Do not include multivalued dependencies that are
also functional dependencies.
(c) Is this instance of R in Boyce-Codd Normal Form (BCNF) with
respect to the dependencies you gave in part (a)? If not, specify
all valid BCNF decompositions.
14. Consider a
relation R(A,B,C,D,E) with the following functional dependencies:
AB → C
BC → D
CD → E
DE → A
(a) Specify all minimal keys for R.
(b) Which of the given functional dependencies are Boyce-Codd Normal
Form (BCNF) violations?
(c) Give a decomposition of R into BCNF based on the given
functional dependencies.
(d) Give a different decomposition of R into BCNF based on the given
functional dependencies.
Each tuple in relation UnivInfo encodes the fact that the student
with the given ID and name took the given course from the professor
with the given ID and office. Assume that students have unique IDs
but not necessarily unique names, and professors have unique IDs but
not necessarily unique offices. Each student has one name; each
professor has one office.
(a) Specify a set of completely nontrivial functional dependencies
for relation UnivInfo that encodes the assumptions described above
and no additional assumptions.
(b) Based on your functional dependencies in part (a), specify all
minimal keys for relation UnivInfo.
(c) Is UnivInfo in Boyce-Codd Normal Form (BCNF) according to your
answers to (a) and (b)? If not, give a decomposition of UnivInfo
into BCNF.
(d) Now add the following two assumptions: (1) No student takes two
different courses from the same professor; (2) No course is taught
by more than one professor (but a professor may teach more than one
course). Specify additional functional dependencies to take these
new assumptions into account.
(e) Based on your functional dependencies for parts (a) and (d)
together, specify all minimal keys for relation UnivInfo.
(f) Is UnivInfo in BCNF according to your answers to (d) and (e)? If
not, give a decomposition of UnivInfo into BCNF.
16. Consider the
following relational schema:
Sale(clerk, store, city, date, item, size, color) // a
clerk sold an item on a particular day
Item(item, size, color, price) // prices and available
sizes and colors for items
Make the following assumptions, and only these assumptions, about
the real world being modeled:
-- Each clerk works in one store.
-- Each store is in one city.
-- A given item always has the same price, regardless of size or
color.
-- Each item is available in one or more sizes and one or more
colors, and each item is available in all combinations of sizes and
colors for that item.
Sale does not contain duplicates: If a clerk sells more than one of
a given item in a given size and color on a given day, still only
one tuple appears in relation Sale to record that fact.
(a) Specify a set of completely nontrivial functional dependencies
for relations Sale and Item that encodes the assumptions described
above and no additional assumptions.
(b) Based on your functional dependencies in part (a), specify all
minimal keys for relations Sale and Item.
(c) Is the schema in Boyce-Codd Normal Form (BCNF) according to your
answers to (a) and (b)? If not, give a decomposition into BCNF.
(d) Now consider your decomposed relations from part (c), or the
original relations if you did not need to decompose them for part
(c). Specify a set of nontrivial multivalued dependencies for
relations Sale and Item that encodes the assumptions described above
and no additional assumptions. Do not include multivalued
dependencies that also are functional dependencies.
(e) Are the relations you used in part (d) in Fourth Normal Form
(4NF) according to your answers for (a)-(d)? If not, give a
decomposition into 4NF.
1.
(a) not satisfied
(b) satisfied
(c) satisfied
(d) satisfied
(e) not satisfied
(f) not satisfied
(g) satisfied
(h) not satisfied
(i) satisfied
2.
(a) is correct
(b) is incorrect - R(A,B,C) with R={(1,2,3),(1,4,5)}
(c) is correct
(d) is incorrect - R(A,B,C,D) with R={(1,2,3,4),(1,5,3,6)}
3. AC, BC, CD, CE
4.
(a) AF
(b) EFG → H
5.
(a) ABE
(b) A → E (or B → E or C → E or D → E)
6.
F2 and F3 are equivalent - A* = ABC, B* = B, C* = C
F1 is not equivalent - A* = ABC, B* = BC, C* = C
7.
(a) not satisfied
(b) not satisfied
(c) not satisfied
(d) not satisfied
(e) satisfied
(f) satisfied
9.
(a) correct
(b) incorrect - R(A,B,C,D) with R={(1,2,3,4),(1,5,6,7)}
(c) incorrect - R(A,B,C,D) with
R={(1,2,3,4),(1,5,6,7),(1,2,3,7),(1,5,6,4)}
(d) correct
10. Ruled out - (a)
(b) (c) (e) (i) (j) (k)
11.
(a) model → make
(b) dealer,make → model
(c) make,model,year →>
color (or make,model,year →>
dealer)
(d) (make,year,color,dealer), (model,year,color,dealer)
12.
(a) No - neither A nor C are keys, so A → B and C → D are BCNF
violations
(b) Yes
(c) Yes
(d) No - B is not a key, so B →>
C is a 4NF violation
(e) Yes
13.
(a) A → B, C → B, AC → B
(b) A →> C, C →> A
(c) No - A is not a key in A → B and C is not a key in C → B
Decomposition 1: R1(A,B),
R2(A,C)
Decomposition 2: R1(A,C),
R2(B,C)
14.
(a) AB, BC, BDE
(b) CD → E, DE → A
(c) R1(C,D,E) R2(A,B,C,D)
(d) R1(A,D,E) R2(C,D,E), R3(B,C,D)
15.
(a) studID → studName, profID → profOffice
(b) (studID,profID,course)
(c) No - neither studID nor profID is a key
Decomposition:
R1(studID,studName), R2(profID,profOffice), R3(studID,course,profID)
(d) studID,profID → course, course → profID
(e) (studID,profID) (studID,course)
(f) No - studID, profID, and course are not keys
Decomposition:
R1(studID,studName), R2(profID,profOffice), R3(studID,course),
R4(course,profID)