Write a java program that implements the Chase Algorithm to determine if a relation satisfies a Join dependency or a functional dependency. More precisely: given scheme R and F, a set of JDS and FDs determine using the chase algorithm if F implies a particular JD or a particular FD.

Your program should input from a text file a). the scheme (i.e. # of attributes), b). the set of FDs and c). the set of JDS as follows :

# of attributes # FDS # JDS

FDS follow 1 per line beginning in column 1

JDS follow 1 per line beginning in column 1

1. Program should input from a text file relation1.txt from the command line and then read it subsequently it should prompt the user to enter either an FD or JD in the form of the text file below, or to halt.

the text file is as follows: Note attributes are space delimited and LHS and RHS of FD are separated by ->

4 3 2 (4 attributes, 3 FDs, and 2 JDS)

2 3 -> 1 1st FD

0 1 -> 2 2nd FD

0 -> 1 3rd FD

*[0 1, 1 2, 2 3] 1st JD

*[1 2 3, 2 3 0] 2nd JD

1). Write a java method called pj (for project join) which, for a particular JD that a tableau (i.e. a table) t is supposed to satisfy computes the project join and prints to standard out (JD *[0 1, 1 2, 2 3] adds the following tuples: each tuple beginning in column 1) any additional tuples that must be added to the tableau in order for the tableau to satisfy the particular JD. The input JD will be represented using integers (as explained below) to represent attributes for example *[0 1, 1 2, 2 3].

2). Determine using the chase algorithm if F => *[R1,R2,...,Rn] where R=R1R2...Rn, i.e. that F implies R1,R2 where R = R1R2. Use the following approach. Convert String attributes of R to integers via an array of pointers. Implement tableau t, as an array of integers. a's are all stored as 0 (obviously a 0 in column i really is ai and bij is stored as i (obviously an i in column j is really bij). bs are stored as positive numbers set to the row that the b is in. Then try to replace bigger integers with smaller integers (ideally 0) (which is a) by the following

do

1. apply all FDs repeatedly (i.e. cycle thru all the FDs all FDs repeatedly to tableau t until no change, then

2. apply all JDs repeatedly (i.e. cycle thru all the JDs repeatedly) to tableau t until no change. Note the easiest way to apply a JD to tableau t is to do a project join using method pj.

until t does not change

then if t has a row of 0's

then print out F ==> *[R1,R2,....Rn] //F implies the JD

else print out F =|=> *[R1,R2,...Rn] //F does not imply the JD

3) Determine using the chase algorithm if F => X -> Y (F implies x functionally determines y). Set row one to subscripted a's (i.e. 0s). and row two to subscripted a's (i.e. a set to 0). for attributes in X and subscripted bs (any b is a positive number) for R-X. Convert to integers as discussed in 2) above and repeatedly apply all FDs and JDs exactly as done in 2) above until t does not change.

Then if t has 0s in the second row for attributes Y

then print out F => X -> Y

else print out F =|=> X ->Y

In all cases your program must print out the final tableau contents. Note when applying FDs your program must print to standard out FD X -> Y changed tuple n to <new tuple> beginning in column 1.

also need a README.txt

book: david maier theory of relational databases : online

reference :

http://en.wikipedia.org/wiki/Chase_(algorithm)

**Subject Computer Science Java Programming**