IF A -> BB, CC -> D, and CC is a subset of BB THEN A -> Dwhere A and D are single attributes and BB and CC are sets of attributes. For simplicity you may assume that A and D are not in BB or CC. Prove the correctness of this rule. Your proof should not be based on closure or on other rules for functional dependencies, but rather it should be based on the formal definition of functional dependencies:
AA -> BB = for all tuples t and u, if t[AA]=u[AA] then t[BB]=u[BB]where AA and BB are sets of attributes.
Your proof might have roughly the following form: Suppose A -> BB holds, CC -> D holds, and CC is a subset of BB. Then for all tuples t and u, ... [fill in] ... To prove that A -> D holds, we need to prove that for all tuples t and u, ... [fill in]. Therefore A -> D holds.
IF AA ->> BB and AA ->> CC THEN AA ->> (BB intersect CC)where AA, BB, and CC are sets of attributes, and intersect performs set intersection. For simplicity you may assume that AA does not intersect BB or CC, and that there are no attributes in the relation besides those in AA, BB, and CC. As in Problem 1, your proof should be based on the formal definition of (in this case) multivalued dependencies, and not on other rules for multivalued dependencies.
Your proof might have roughly the following form: Suppose AA ->> BB and AA ->> CC hold. Then for all tuples t and u there exists a tuple v such that ... [fill in] ... Let DD = BB intersect CC. To prove that AA ->> DD holds, we need to prove that for all tuples t and u there exists a tuple v such that ... [fill in]. Therefore AA ->> DD holds.
IF A,B -> C THEN A -> Cwhere A, B, and C are single attributes. Show that this "rule" does not hold by providing the simplest counterexample you can find. To provide a counterexample, you need to specify a relation schema and a relation instance (set of tuples) for which A,B -> C holds but A -> C does not hold.
(b) The same "rule" does not hold for multivalued dependencies either:
IF A,B ->> C THEN A ->> Cwhere A, B, and C are single attributes. Show that this "rule" does not hold by providing the simplest counterexample you can find. To provide a counterexample, you need to specify a relation schema and a relation instance (set of tuples) for which A,B ->> C holds but A ->> C does not hold.
A | B |
---|---|
00 | 0 |
01 | 0 |
10 | 1 |
11 | 1 |
This example serves as a hint for parts (a) and (b) that follow.
(a) Consider a relation R(A,B,C) where all attributes contain values that are bit strings. Find an instance of R that satisfies the functional dependencies A -> B, B -> C, and all functional dependencies that follow from these two, but it does not satisfy any other functional dependencies (such as C -> A, BC -> A, etc.).
(b) Consider a relation R(A,B,C,D) where all attributes contain values that are bit strings. Find an instance of R that satisfies the functional dependencies A -> B, B -> C, C -> D, and all functional dependencies that follow from these three, but it does not satisfy any other functional dependencies (such as C -> A, D -> B, CD -> A, etc.).
Sale(clerk, store, city, date, item#, size, color) // records that a clerk sold an item on a particular day Item(item#, size, color, price) // records prices and available sizes and colors for itemsMake the following assumptions, and only these assumptions, about the real world being modeled:
(a) Based on the assumptions above (and no others), specify an appropriate set of completely nontrivial functional dependencies for relations Sale and Item.
(b) Based on the assumptions above (and no others), specify all keys for relations Sale and Item.
(c) Are relations Sale and Item in Boyce-Codd Normal Form (BCNF)? If not, decompose the relations so they are in 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). Based on the assumptions above (and no others), specify all nontrivial multivalued dependencies for the relations. Do not include multivalued dependencies that also are functional dependencies.
(e) Are the relations you used in part (d) in Fourth Normal Form (4NF)? If not, decompose the relations so they are in 4NF.
(a) Please attach a copy of your E/R diagram from PDA Part 1. If you would like to make changes to your original E/R diagram at this point (due to staff feedback or any other reason), you may do so. The new E/R design will not be graded but will be used as a basis for grading part (b).
(b) Using the method for translating an E/R diagram to relations, produce a set of relations for your database design. As usual, please be sure to underline key attributes in your relations.
(c) For each relation in your schema, specify a set of completely nontrivial functional dependencies for the relation. Any functional dependencies that actually hold in the real-world scenario that you're modeling should be specified, or should follow from the specified dependencies. Don't worry if you find that some of your relations have no nontrivial functional dependencies.
(d) Is each relation in your schema in Boyce-Codd Normal Form (BCNF) with respect to the functional dependencies you specified? If not, decompose the relation into smaller relations so that each relation is in BCNF. Be sure to underline key attributes in your new relations. Don't worry if you don't have any BCNF violations - many PDAs will not have any.
(e) Are there any nontrivial multivalued dependencies that hold on any of the relations in your schema? (You needn't consider MVD's that are also functional dependencies.) If so, specify the multivalued dependencies, then decompose the relations into smaller ones so that each one is in Fourth Normal Form (4NF). Be sure to underline key attributes in your new relations. Don't worry if you don't have any 4NF violations - most PDAs will not have any.
(f) Now that you've decomposed your relations as far as possible, are there any relations that could be combined without introducing redundancy (i.e., without creating BCNF or 4NF violations)? If so, combine them.
(g) Is there anything you still don't like about the schema (e.g., attribute names, relation structure, etc.)? If so, modify the relational schema to something you prefer. You will be working with this schema quite a bit, so it's worth spending some time now to make sure you're happy with it. And once again: