PFun / BCNF Decomposition

Check if a given Relation is in BCNF, if not decompose it to BCNF.
Enter the FDs, in the format : AB->C,D->E.
Enter the Relation in the format: ABCDE


Dependencies: " class="form-control" placeholder="Dependency Value">


Relation: " class="form-control" placeholder="Relation Value">


",$element); array_push($dependencies, array(str_split($single_dep[0]), str_split($single_dep[1]))); } $relation = str_split(str_replace(" ","", $relation)); ////////////////////////////////////////////////// echo "Solution:
"; // Check if the Relation is BCNF if not then Split it $bcnf_relations = check_bcnf_rec($dependencies, $relation); if (count($relation) > 0 && count($bcnf_relations) > 0) { $count=1; echo "

Final Decomposition

"; foreach($bcnf_relations as $ele) { echo "$count. $ele
"; $count++; } } } // Check if a given set of attributes form a SuperKey function check_if_superkey($dependencies, $key, $relation) { $closure = closure($dependencies, $key); return issubset($closure,$relation); } // Recursively called to check if BCNF and split. function check_bcnf_rec($dependencies, $relation) { $bcnf_relations = array(); $bcnf = true; foreach($dependencies as $dep) if (check_valid_dependencies($dep, $relation)) { $issuperkey = check_if_superkey($dependencies, $dep[0], $relation); if (!$issuperkey) { $bcnf = false; $violate_dep = $dep; break; } } if ($bcnf) { $bcnf_relations = array(array_reduce($relation,"joinx")); echo "$bcnf_relations[0] relation is BCNF
"; } else { echo ""; echo array_reduce($relation,"joinx"); echo " relation is not BCNF
"; echo "The BCNF violation is : "; echo array_reduce($violate_dep[0],"joinx"); echo "->"; echo array_reduce($violate_dep[1],"joinx"); echo "
"; echo "Decompose the relation based on the dependency
"; $bcnf_relations = decompose_relation($dependencies, $relation, $violate_dep); } return $bcnf_relations; } function decompose_relation($dependencies, $relation, $violate_dep) { $bcnf_relations = array(); // Find the closure of the LHS of the voilating depedency $closure = closure ($dependencies, $violate_dep[0]); // Make Sure the Closure only had attribues from the Relation $closure = array_intersect($relation, $closure); echo "The relation is decomposed into "; echo array_reduce($closure,"joinx"); echo " and "; echo array_reduce(array_merge($violate_dep[0], array_diff($relation,$closure)),"joinx"); echo "
"; $ret = check_bcnf_rec($dependencies, $closure); foreach($ret as $ele) array_push($bcnf_relations, $ele); $ret = check_bcnf_rec($dependencies, array_merge($violate_dep[0], array_diff($relation,$closure))); foreach($ret as $ele) array_push($bcnf_relations, $ele); return $bcnf_relations; } // Check if the depdndicies are valid. function check_valid_dependencies($dep, $relation) { foreach ($dep as $ele) if (!issubset($relation, $ele)) return false; return true; } ?>