Prove that the algorithm for synthesizing 3NF decompositions yields schemas that satisfy the conditions of 3NF.
Use the proof-by-contradiction technique. Assume that some FD violates 3NF and then show that this contradicts the fact that the algorithm synthesized schemas out of a minimal cover.
Suppose, to the contrary, that one of the schemas, say (XA; {X ? A,...}), which results from the synthesis using the FD set F, is not in 3NF. Then there must be Y ? B ? F+, where YB? XA, which violates the 3NF conditions.
If A = B ,then Y ? X . However, this means that the FD X ? A cannot be in the minimal cover of F, because Y ? X and so Y ? A holds and has a smaller left-hand side.
If A = B ,thenB ? X and B but it cannot be part of a key (because otherwise Y ? B would not have violated 3NF). Thus, there is a key, W ,of XA such that W ? X ?{A}. In particular, it implies that W ? A ? F+. Again, this means that X ? A cannot be in a minimal cover of F.
You might also like to view...
The_______ tier maintains data for the application.
a) bottom. b) server. c) middle. d) Both b and c.
Why do many television ads list a phone number like 1-800 CALL ATT instead of as 1-800 225 5288? After all it’s easier to use the numbers on the touch pad instead of hunting up the letters. Relate this to short-term memory.
What will be an ideal response?
The equipment of network service providers and links are tied together by a(n) ____.
A. NAP B. DSL C. NSP D. IP
To count words, click the Word Count indicator on the Home tab to display the Word Count dialog.
Answer the following statement true (T) or false (F)