CS 430/630 Homework 6 FDs, Normalization, Access Control

due Wed.,  May 15 in class, on paper

Note 1. An essential computation here is an attribute closure. Here is an example from slide 11 of Lecture 20:
FDs given and numbered: (1) C -> CSJDPQV, (2) JP -> C, (3) SD ->  P
Compute SDJ+, attribute closure of SDJ:
  SDJ+ = SDJ,  = SDJP  by (3), = SDJPC by (2), = SDJPCR by (1), = R (all attributes)

Note 2. BCNF and 3NF are equivalent for tables with only single-column key(s), i.e., the majority of tables in practice. In fact, the only tables that are 3NF but not BCNF have at least one multi-column key with an inbound FD to part of the key, making them even rarer in practice. However, grad students should make an effort to understand the two definitions in R&G, sections 19.4.1 and 19.4.2. Undergrads may restrict their expertise to tables with possibly multiple one-column keys, in which case 3NF is equivalent to BCNF. Note that the BCNF decomposition algorithm (Sec. 19.6.1) is still relevant for 3NF decompositions: just look for violations of 3NF, not BCNF in choosing the FD to drive the decomposition step. If you end up with a lost FD (not preserved in one of the tables), add back a table as described by the bullets on pg. 627 under Dependency-Preserving Decomposition into 3NF.

1. Finding FDs. Exercise 19.3, which is solved online. Do those 2 parts and add a third part,
    3. Change the original contents by changing the lower two y1 values in the Y column to y2, leaving the upper two equal to y1. List all the FDs this new instance satisfies.

2. Exercise 19.2 Finding keys, determining 3NF, BCNF.
a. Replace the given FDs with the set  Given (1) A → B (2) BC → D, and (3) E → AC. This will yield a single key, so we can be sure that 3NF status will be the same as BCNF status, i.e., the table is not in BCNF and also not in 3NF, or is in both BCNF and 3NF. If it's not in 3NF, say also whether it is in 2NF or not.

b.  (CS630 only) Use the original set of FDs: Given (1) A → B (2) BC → E, and (3)  ED → A
This will yield multiple multicolumn keys, so 3NF statis may differ from BCNF.

3. FDs, decomposition. Here is a table for classes at a college, with numbered time periods in each day:

a.       Find a functional dependency (FD) with one attribute (other than Name) on each side that holds for this instance.

b.      Disprove the proposed FD “department period -> room”

c.       Find a single-column key and a multi-column key that hold for this instance

d.    Is this table in 2NF? Why or why not?

e.      Propose a decomposition that removes the redundancy implied by the FD you found in a. Show the smaller table in full and state what column can be dropped in the larger table compared to the original table. Hint: this is a lot like the R -> W dependency example of Figures 19.1 and 19.2 and in the slides of Lecture 19.

4. Exercise 19.10 (a. and b.) Lossless Joins. For part b., a good decomposition means it provides lossless join(s) and preserves FDs. For each case 1-4, first check if the join(s) are lossless and give up if not. If lossless, determine whether the FDs are preserved.

5. Decompositions. Find a BCNF decomposition of the relation of Problem 19.10 for parts 1. and 2., using the FD sets given for each case. Part 2 is optional for CS630 since it involves a situation where BCNF and 3NF are possibly different: it has two two-column keys. Analyze the BCNF decomposition for unpreserved dependencies. If you find a 3NF decomposition that preserves dependencies along the way, report it. Note that the first step is to find the keys, so you can test FDs as described on pp. 616-618. When you have a choice as to which non-BCNF FD to work on (in part 2), choose the first such FD and use it for a decomposition, then later come back and determine what happens if you choose the second one.

6. Views for Access Control. Suppose you need to provide access to the employees table without the salary information, to user clerk. Give the code to define a view empinfo(eid, ename) that provides this information from table employees, which is in schema HR for this problem. The view is also in schema HR. Give the command to grant select access to empinfo for user clerk, while keeping employees protected from clerk. Assume you can login to account HR, so you have full privileges on employees and empinfo. We don't need to do anything special about employees to hide it from user clerk because by default it is not visible to other users. You can test the view online but not the granted access, so just record everything in your paper.