DM505, Spring 2007, 4th Quarter - Weekly Note 6

This week, there will be one lecture slot (May 23) and two exercise slots (May 21 and 24).

Note for the exercise slot May 24: The exercises from the book can only be done after the lecture May 23, so plan some time for this in your agenda. The programming exercises can be done already now.

Lecture May 16

Even more on normalization theory.

Reading

Kifer, Bernstein, and Lewis: Sections 6.6.2, 6.8, 6.11, and 6.13.

Remarks

Fourth Normal Form (Sections 6.9-10) is not part of curriculum.

Lecture May 23 (Expected Contents)

Indexes.

Reading

Kifer, Bernstein, and Lewis: Chapter 9.

Exercises May 21

Postponed exercises: Exercises 6.26, 6.22, 6.21, 6.18, 6.29, 6.30, and 6.19 in Kifer, Bernstein, and Lewis.

Exercises May 24

Exercises 9.2, 9.4, 9.5, 9.7, 9.8, 9.10, 9.15, 9.17 (make the calculation for the following three cases: an equality search returning 10 rows, a range search returning 10 rows, and a range search returning 50.000 rows), 9.20, and 9.23 in Kifer, Bernstein, and Lewis.

The following programming exercises (where it may be advantageous to work in pairs):

1. Make in Java (or another language of your choice) an implementation of the algorithm in Figure 6.3 (page 205) for finding attribute closure. The first step is to choose appropriate representations (many are possible) in your program for a subset X of attributes of a relation R, for functional dependencies, and for a set F of functional dependencies. You do not need to spend time on input, i.e. just let X and F be hardcoded in your program.

2. Implement an algorithm which generates all subsets of attributes of a relation R (again, just hardcode R in your program). I.e., for R having three attributes ABC, the generated subsets should be (in some order) ABC, AB, AC, BC, A, B, C, and the empty set.

3. Based on the two previous implementations, implement an algorithm for finding the closure of a set F of functional dependencies on a relation R. The algorithm should work by running the algorithm for attribute closure on all possible left-hand sides for functional dependencies (this will give a version of the closure of F where all functional dependencies with the same left-hand side has been merged, which by the union and decomposition rules (page 202, middle) is equivalent to the full closure).

4. Improve on the output of the previous implementation by filtering out all "triviality" of the resulting functional dependencies - more precisely, only output functional dependencies where there is no overlap between the left-hand side and the right-hand side. For example, the functional dependency ABCD -> CDEF should be output as ABCD -> EF, and the functional dependency ABCD -> ABC should not be output at all. By the reflexivity rule (page 201), this is equivalent to the unfiltered version.

5. Sketch how you could use the first two implementations to find all candidate keys of a relation. (If you like, you may of course also carry out the actual implementation).