Functional Dependency & CDNF decomposition Complete FDS2.java with the one line in project() and run the program on examples Using book A First Course in Database Systems, 3rd ed. by Ullman and Widom, 2008 Chapter 3  // FDS2.java // Algorithm 3.20 BCNF decomposition and Algorithm 3.12 Projection of FDs // Usage: java FDS2 F // F is a file that has the first line all the attributes and // then an FD a line with a space between the left-hand side and the right-hand side import java.io.*; import java.util.*; class FD{ HashSet lhs; char rhs; public FD(HashSet l, char r){ lhs = l; rhs = r; } public boolean equals(Object obj){ FD fd2 = (FD)obj; return lhs.equals(fd2.lhs) && rhs == fd2.rhs; } public void printout(){ for (char c: lhs) System.out.print(c); System.out.print(" "); System.out.print(rhs); System.out.println(); } }; public class FDS2{ HashSet R = new HashSet(); // all attributes HashSet F = new HashSet(); // the set of FDs public FDS2(String filename){ // 1. split FDs so each FD has a single attribute on the right Scanner in = null; try { in = new Scanner(new File(filename)); } catch (FileNotFoundException e){ System.err.println(filename + " not found"); System.exit(1); } String line = in.nextLine(); for (int i = 0; i < line.length(); i++) R.add(line.charAt(i)); while (in.hasNextLine()){ HashSet l = new HashSet(); String[] terms = in.nextLine().split(" "); for (int i = 0; i < terms[0].length(); i++) l.add(terms[0].charAt(i)); for (int i = 0; i < terms[1].length(); i++) F.add(new FD(l, terms[1].charAt(i))); } in.close(); } public FDS2(HashSet r, HashSet f){ R = r; F = f; } HashSet string2set(String X){ HashSet Y = new HashSet(); for (int i = 0; i < X.length(); i++) Y.add(X.charAt(i)); return Y; } void printSet(Set X){ for (char c: X) System.out.print(c); } HashSet closure(HashSet X){ // Algorithm 3.7 HashSet Xplus = new HashSet(X); // 2. initialize int len = 0; do { // 3. push out len = Xplus.size(); for (FD fd: F) if (Xplus.containsAll(fd.lhs) && !Xplus.contains(fd.rhs)) Xplus.add(fd.rhs); } while (Xplus.size() > len); return Xplus; // 4. found closure of X } FD BCNFviolation(){ for (FD fd: F) if (!closure(fd.lhs).containsAll(R)) return fd; return null; } void BCNFdecompose(){ // Algorithm 3.20 FD fd = BCNFviolation(); if (fd == null){ // Step 1 printSet(R); System.out.println(); for (FD f: F){ // get a minimal basis for F boolean redundant = false; for (FD f2: F) // remove those with lhs larger than necessary if (f2.rhs == f.rhs && f.lhs.containsAll(f2.lhs) && !f.lhs.equals(f2.lhs)){ redundant = true; break; } if (!redundant) f.printout(); } System.out.println(); }else{ HashSet R1 = closure(fd.lhs); // Step 2 with these three lines HashSet R2 = new HashSet(fd.lhs); for (char c: R) if (!R1.contains(c)) R2.add(c); // decomposed into R1 and R2 FDS2 fds1 = new FDS2(R1, project(R1, R1, new HashSet())); // Step 3 fds1.BCNFdecompose(); // recursive call on R1, Step 4 FDS2 fds2 = new FDS2(R2, project(R2, R2, new HashSet())); // Step 3 fds2.BCNFdecompose(); // recursive call on R2, Step 4 } } HashSet project(HashSet R1, HashSet candidates, HashSet X){ // Algorithm 3.12, starts with candidates = R1 and subset X = empty HashSet T = new HashSet(); // Let T be the eventual output set of FD's. // Initially, T is empty. Step 1 // This recursive function generates all subsets of R1 in a depth-first way by set inclusion HashSet Xplus = closure(X); // Step 2 if (X.size() > 0) // Your code next line for (char A: Xplus) if (A is not in X and A is in R1) T.add(new FD(X, A)); if (!Xplus.containsAll(R)){ // otherwise no superset needs to be explored // If we already know that the closure of X is all attributes, then we cannot discover any // new FD's by closing supersets of X. p.83 HashSet candidates2 = new HashSet(candidates); for (char c: candidates){ // go through all supersets of X by adding one attribute candidates2.remove(c); X.add(c); T.addAll(project(R1, new HashSet(candidates2), new HashSet(X))); X.remove(c); } } return T; } public static void main(String[] args){ FDS2 fds = new FDS2(args[0]); fds.BCNFdecompose(); } }