Decomposition AlgorithmsIn the previous section, we discussed decomposition and its types with the help of small examples. In the actual world, a database schema is too wide to handle. Thus, it requires algorithms that may generate appropriate databases. Here, we will get to know the decomposition algorithms using functional dependencies for two different normal forms, which are:
Decomposition using functional dependencies aims at dependency preservation and lossless decomposition. Let's discuss this in detail. Decomposition to BCNFBefore applying the BCNF decomposition algorithm to the given relation, it is necessary to test if the relation is in BoyceCodd Normal Form. After the test, if it is found that the given relation is not in BCNF, we can decompose it further to create relations in BCNF. There are following cases which require to be tested if the given relation schema R satisfies the BCNF rule: Case 1: Check and test, if a nontrivial dependency α > β violate the BCNF rule, evaluate and compute α^{+ }, i.e., the attribute closure of α. Also, verify that α+ includes all the attributes of the given relation R. It means it should be the superkey of relation R. Case 2: If the given relation R is in BCNF, it is not required to test all the dependencies in F^{+}. It only requires determining and checking the dependencies in the provided dependency set F for the BCNF test. It is because if no dependency in F causes a violation of BCNF, consequently, none of the F^{+} dependency will cause any violation of BCNF. Note: Case2 does not work if the relation gets decomposed. It means during the testing of the given relation R, we cannot check the dependency of F for the cause of violation of BCNF.BCNF Decomposition AlgorithmThis algorithm is used if the given relation R is decomposed in several relations R_{1}, R_{2},…, R_{n} because it was not present in the BCNF. Thus, For every subset α of attributes in the relation R_{i}, we need to check that α^{+} (an attribute closure of α under F) either includes all the attributes of the relation R_{i} or no attribute of R_{i}α. result={R}; done=false; compute F^{+}; while (not done) do if (there is a schema Ri in result that is not in BCNF) then begin let α>β be a nontrivial functional dependency that holds on R_{i} such that α>R_{i} is not in F^{+}, and α ꓵ β= ø; result=(resultR_{i}) U (R_{i}β) U (α,β); end else done=true; Note: If some set of attributes α in Ri violates the specified condition in the algorithm, in such case consider the functional dependency α>( α+  α) ꓵ R_{i}. Such dependency can be present in the F^{+} dependency.This algorithm is used for decomposing the given relation R into its several decomposers. This algorithm uses dependencies that show the violation of BCNF for performing the decomposition of the relation R. Thus, such an algorithm not only generates the decomposers of relation R in BCNF but is also a lossless decomposition. It means there occurs no data loss while decomposing the given relation R into R_{1}, R_{2}, and so on… The BCNF decomposition algorithm takes time exponential in the size of the initial relation schema R. With this, a drawback of this algorithm is that it may unnecessarily decompose the given relation R, i.e., overnormalizing the relation. Although decomposing algorithms for BCNF and 4NF are similar, except for a difference. The fourth normal form works on multivalued dependencies, whereas BCNF focuses on the functional dependencies. The multivalued dependencies help to reduce some form of repetition of the data, which is not understandable in terms of functional dependencies. Difference between Multivalued Dependency and Functional DependencyThe difference between both dependencies is that a functional dependency expels certain tuples from being in a relation, but a multivalued dependency does not do so. It means a multivalued dependency does not expel or rule out certain tuples. Rather it requires other tuples of certain forms to exist in relation. Due to such a difference, the multivalued dependency is also referred to as tuplegenerating dependency, and the functional dependency is referred to as equalitygenerating dependency. Decomposition to 3NFThe decomposition algorithm for 3NF ensures the preservation of dependencies by explicitly building a schema for each dependency in the canonical cover. It guarantees that at least one schema must hold a candidate key for the one being decomposed, which in turn ensures the decomposition generated to be a lossless decomposition. 3NF Decomposition Algorithmlet Fc be a canonical cover for F; i=0; for each functional dependency α>β in F_{c} i = i+1; R = αβ; If none of the schemas R_{j}, j=1,2,…I holds a candidate key for R Then i = i+1; R_{i}= any candidate key for R; /* Optionally, remove the repetitive relations*/ Repeat If any schema R_{j} is contained in another schema Rk Then /* Delete R_{j} */ R_{j} = R_{i}; i = i1; until no more Rjs can be deleted return (R_{1}, R_{2}, . . . ,R_{i}) Here, R is the given relation, and F is the given set of functional dependency for which F_{c} maintains the canonical cover. R_{1}, R_{2}, . . . , R_{i} are the decomposed parts of the given relation R. Thus, this algorithm preserves the dependency as well as generates the lossless decomposition of relation R. A 3NF algorithm is also known as a 3NF synthesis algorithm. It is called so because the normal form works on a dependency set, and instead of repeatedly decomposing the initial schema, it adds one schema at a time. Drawbacks of 3NF Decomposing Algorithm
Next TopicDBMS Tutorial
