Assignment #7
Due Wednesday November 27

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: On-campus assignments must be submitted by Wednesday at 5:00 PM. SITN assignments must be sent with the Wednesday courier at the latest.

1. (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.

2. (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,B	-->	C
   B,C	-->	D

   (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 Boyce-Codd Normal Form (BCNF)? If not, decompose R into smaller relations so that all decomposed relations are in BCNF.

3. (3 points)
   Consider a relation R(A,B,C,D,E). Let the following two functional dependencies hold on R:

   A	-->	C
   C	-->	E

   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.

4. (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?

5. (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.''

6. (3 points)
   Prove that the splitting rule for functional dependencies does not apply to the left-hand-side 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.

7. 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 real-world 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?

8. PDA: Programming (12 points: 8 for (a), 4 for (b))

   Your PDA assignment for this week is to build a user-friendly 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 (E-SQL) 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.