Assignment #7
Due Wednesday November 27
This assignment will be graded out of 40 points.
Important note: This assignment is due on the Wednesday before
the Thanksgiving holiday weekend. Thus, we will not accept
any late submissions for this assignment, and SITN students will need
to turn in their assignments earlier than usual: Oncampus
assignments must be submitted by Wednesday at 5:00 PM. SITN
assignments must be sent with the Wednesday courier at the latest.
 (3 points)
Consider a relation R(A,B,C). Suppose R
contains the following four tuples:
A  B  C 
1  2  3 
1  2  4 
5  2  3 
5  2  6 
List all completely nontrivial functional dependencies that hold on
this instance of R.
 (6 points: 3 for (a), 1 for (b), 2 for (c))
Consider a
relation R(A,B,C,D). Let the following two functional dependencies
hold on R:
 (a)
 For each subset S of the four attributes (there are 15
nonempty subsets), give the closure S+ of the subset of
attributes based on the functional dependencies.
 (b)
 Based on part (a), list all keys for relation R.
 (c)
 Is relation R in BoyceCodd Normal Form (BCNF)? If not,
decompose R into smaller relations so that all decomposed relations
are in BCNF.
 (3 points)
Consider a relation R(A,B,C,D,E). Let the
following two functional dependencies hold on R:
Suppose we decompose R into these two relations:
R1(A,B,C)
R2(C,D,E)
Show that this decomposition does not preserve the correct joining
property. That is, give an instance r of R (i.e., give a set of
tuples for R) such that both dependencies hold on r but:
r <> pi{A,B,C}(r) Join pi{C,D,E}(r)
Give the simplest instance you can find.
 (3 points: 2 for (a), 1 for (b))
Consider a database for a
university that may include information about students, courses,
professors, etc.
 (a)
 Specify an example relation for this database and a set of
functional dependencies over the relation such that the relation is in
Third Normal Form (3NF) but is not in BCNF. Your relation need not be
extensive (i.e., it need not include many attributes and it may
represent only a very small part of the complete university
information), but the schema and the dependencies should be realistic
in their modeling of the real world. You should make no assumptions
besides those captured by the schema and the functional dependencies.
 (b)
 Decompose your relation from part (a) so that the new schema is
in BCNF. Are there any functional dependencies that cannot be
enforced in the decomposition, assuming that dependencies are enforced
on one relation at a time?
 (3 points)
Prove the correctness of the transitive rule
for functional dependencies. The definition of the transitive rule is
given at the beginning of Section 3.6.4 in your course reader. The
definition of the rule is followed by a somewhat informal argument of
its correctness. You are to provide a more formal proof of
correctness based on the formal definition of a functional dependency.
The formal definition of a functional dependency is repeated here for
your convenience:
A1,...,An > B1,...,Bm iff:
for all tuples t and u in R:
if t[A1,...An] = u[A1,...,An] then t[B1,...,Bm] = u[B1,...,Bm]
Your proof for the transitive rule should have the following general
form: ``Suppose A1,...,An > B1,...,Bm
holds. Then for all tuples t and u in R, ...fill in
this part ... Therefore
A1,...,An > C1,...,Cm
holds.''
 (3 points)
Prove that the splitting rule for functional
dependencies does not apply to the lefthandside of a dependency.
That is, prove that the following rule is incorrect:
If A1,...,An > B1,...,Bm then Ai > B1,...,Bm
for i = 1,...,n.
To prove the incorrectness of this rule, you need to give: (i) a
relation schema R, (ii) a functional dependency
A1,...,An > B1,...,Bm
on R, and (iii) a relation instance
r for R such that the tuples in r satisfy the functional
dependency
A1,...,An > B1,...,Bm
but do not
satisfy
Ai > B1,...,Bm
for some i . Provide
the simplest example you can find. Do not use the schema from the
course reader.
 PDA: Written (7 points: 3 for (b), 2 for (c), 1 each for
(d) and (e))
In this problem you'll determine how good the schema design is that
you've been using for your PDA.
 (a)

Remind us of the relational schema S you're using for your
PDA.
 (b)

For each relation R in S: Specify a set of nontrivial
functional dependencies that hold on R. Any functional dependencies
that actually hold in the realworld scenario that you're modeling
with your PDA should be specified or should follow from the specified
dependencies by the rules for functional dependencies. Don't worry if
you find that some of your relations have no nontrivial functional
dependencies.
 (c)

For each relation R in S: Is R in BCNF with respect to the
functional dependencies you specified in part (b)? If not, decompose
R into smaller relations so that each relation is in BCNF.
 (d)

For each relation R in the original schema S: Is R in 3NF
with respect to the functional dependencies you specified in part (b)?
If not, decompose R into smaller relations so that each relation is
in 3NF.
 (e)

If your designs for parts (c) and (d) differ, which design is
``better,'' the BCNF design or the 3NF design? Why?
 PDA: Programming (12 points: 8 for (a), 4 for (b))
Your PDA assignment for this week is to build a userfriendly
interactive application program front end to your personal database
using the C programming language. (We regret that we've discovered
Sybase does not support C++ application programming.) You will
experiment with two different paradigms for interaction between the
application program and Sybase.
Your program should consist of a continuous loop in which:
 1.
 A list of alternative options is offered to the user.
(One of the alternatives should be quit.)
 2.
 The user selects an alternative.
 3.
 The system prompts the user for appropriate input
values.
 4.
 The system accesses the database to perform the
appropriate queries and/or modifications.
 5.
 Data or an appropriate acknowledgment is returned to the user.
You should include both queries and modifications. For example, a
maternity ward application might include in its menu:
 A number of useful queries on the database, with both input and
output in a format more convenient and pleasing than raw interactive SQL.
 Options to update a patient's age, room, or risk.
 Options to add information about a new baby.
 (a)
 First write your program using Embedded SQL (ESQL) to interact
with the database server, as described in the accompanying handout
``Embedded SQL, Library SQL, and Stored Procedures in Sybase.'' Turn
in your C code along with a script showing an interaction with your
program in which all of its features are exhibited.
 (b)

Convert your program from part (a) to instead use Library SQL
(DBLib) to interact with the database server, as described in the
accompanying handout ``Embedded SQL, Library SQL, and Stored
Procedures in Sybase.'' Turn in your C code along with a script
showing an interaction with your program in which all of its features
are exhibited.
You will not be using Stored Procedures in this assignment; they will
be covered in Assignment #8.
The TAs of CS145,
cs145ta@cs.stanford.edu,
last modified: 11/19/96