Functional Dependency & Closure of Attributes -- Using book A First Course in Database Systems, 3rd ed. by Ullman and Widom, 2008 Chapter 3

Complete FDS.java with the four incomplete functions. Test the program on some examples.

// FDS.java

// Algorithm 3.7 closure of X under F

// Usage: java FDS F X

// 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

// X is a string of characters represent a set of attributes

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 class FDS{

HashSet R = new HashSet(); // all attributes

HashSet F = new HashSet(); // the set of FDs

public FDS(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();

}

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

}

boolean follows(FD fd){ // fd follows from FDS

return // ?

}

boolean covers(FDS T){ // FDs in T follows F

// your code

return // ?

}

boolean equivalent(FDS T){ // this covers T and T covers this

return // ?

}

HashSet findAKey(){ // returns a key to the relation

// your code

}

public static void main(String[] args){

FDS fds = new FDS(args[0]);

HashSet X = fds.string2set(args[1]);

fds.printSet(fds.closure(X));

// and other functions to test

}

}