Functional dependency, 3NF checking and decomposition is implemented below in java -- Using book A First Course in Database Systems, 3rd ed. by Ullman and Widom, 2008 Chapter 3

Review and complete FDS3.java by completing the function is3NF() where it says "Your Code". Test the program on some examples and display the output.

// FDS3.java // Algorithm 3.26 3NF decomposition // Find all prime attributes // Usage: java FDS3 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 FDS3{ HashSet R = new HashSet(); // all attributes HashSet F = new HashSet(); // the set of FDs HashSet aKey = null; HashSet primeAttributes = new HashSet(); public FDS3(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 FDS3(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 } HashSet> findKeys(HashSet candidates, HashSet subset){ // starts with candidates = R and subset = empty // returns all keys HashSet> keys = new HashSet>(); HashSet clo = closure(subset); if (!clo.containsAll(R)){ // adding one candidate attribute to subset and recursion on it HashSet candidates2 = new HashSet(candidates); for (char c: candidates){ candidates2.remove(c); subset.add(c); keys.addAll(findKeys(new HashSet(candidates2), new HashSet(subset))); // recursive call subset.remove(c); } }else{ // subset may be a key if (isKey(subset)){ // printSet(subset); System.out.println(); // printing key keys.add(subset); // gathering prime attributes } } return keys; } boolean isKey(HashSet possibleKey){ for (char c: possibleKey){ HashSet set2 = new HashSet(possibleKey); set2.remove(c); if (closure(set2).containsAll(R)) return false; } return true; } void findAllPrimeAttributes(){ HashSet> keys = findKeys(R, new HashSet()); for (HashSet key: keys){ if (aKey == null) aKey = key; primeAttributes.addAll(key); } // printSet(primeAttributes); System.out.println(); // print out prime attributes } boolean is3NF(){  /* Your code here for (FD fd: F) if ( your code for fd violating 3NF) return false; */ return true; } void decompose(){ // Algorithm 3.26 // HashSet G = minCover(F); // step 1 of Algorithm 3.26, skip it for now HashSet G = new HashSet(F); // step 2 of Algorithm 3.26 FDs with identical lhs will be combined HashSet> H = new HashSet>(); for (FD fd: G) H.add(fd.lhs); // all the lhs's HashSet> schemas = new HashSet>(); for (HashSet cs: H){ // for each identical lhs add all the rhs's to form a schema HashSet schema = new HashSet(); schema.addAll(cs); for (FD fd: G) if (fd.lhs.equals(cs)) schema.add(fd.rhs); schemas.add(schema); } // step 3 of Algorithm 3.26 boolean keyIn = false; for (HashSet s: schemas) if (closure(s).containsAll(R)){ keyIn = true; break; } if (!keyIn) schemas.add(aKey); // additional step to rid redundant relations (projections of other relations) for (HashSet s: schemas) for (HashSet t: schemas) if (t.size() >= s.size() && !t.equals(s) && t.containsAll(s)) schemas.remove(s); for (HashSet s: schemas){ printSet(s); System.out.println(); } } public static void main(String[] args){ FDS3 fds = new FDS3(args[0]); fds.findAllPrimeAttributes(); if (fds.is3NF()) System.out.println("Relation is in 3NF"); else fds.decompose(); } }