Functional dependency calculator

$Id: functional-dependencies.php,v 1.11 2006/04/10 16:32:48 bigfoot Exp $

This script automatically calculates functional dependencies for relational tables with a known set of rows.
Inspired by "Conceptual Design of Database Systems" exercises at IMMD6, FAU Erlangen, led by Maciej Suchomski.
Use the examples at the bottom of this page to see what's going on (please send me more interesting examples!).
TODO: verify correct behaviour towards transitive dependencies (feedback, please!)
TODO: external links to documentation
NOTE: This is currently alpha. Please inform me about any errors.

INPUT:

OUTPUT:

->	"functionally determines"
F	full functional dependency
P	partial functional dependency
C	key candidate
C!	minimal length key candidate
T	transitive dependency to underlined dependents (experimental!)

1.	A	->	C	F
2.	A, B	->	C, D, E	P	C!	T
3.	A, B, C	->	D, E	P	C
4.	A, B, C, D	->	E	P	C
5.	A, B, C, E	->	D	P	C
6.	A, B, D	->	C, E	P	C	T
7.	A, B, D, E	->	C	P	C
8.	A, B, E	->	C, D	P	C
9.	A, C, D, E	->	B	P	C
10.	A, D	->	C	P
11.	A, D, E	->	B, C	P	C
12.	A, E	->	C	P
13.	B	->	D	F
14.	B, C	->	A, D, E	P	C!	T
15.	B, C, D	->	A, E	P	C	T
16.	B, C, D, E	->	A	P	C
17.	B, C, E	->	A, D	P	C
18.	B, D, E	->	A, C	P	C	T
19.	B, E	->	A, C, D	P	C!	T
20.	C	->	A	F
21.	C, D	->	A	P
22.	C, D, E	->	A, B	P	C
23.	C, E	->	A	P
24.	D, E	->	A, B, C	P	C!	T
25.	E	->	A, C	F		T

EXAMPLES

partially taken from Maciej Suchomski's exercise slides
(NEW: click "try it" to run the example):

(1)
A B C D E
---------
a b z w q
e b r w p
a d z w t
e d r w q
a f z s t
e f r s t

try it

(2) (default)
A B C
-----
a b x
a b y
a d x
a d y
c f x
c f y

try it

(3)
A B C D E
---------
a b x v q
e b y v z
a d x v t
e d y v p
a f x p t
e f y p z

try it

Cust# Name  Address
-------------------
43    Jones 121_1st
55    Smith 222_2nd

try it

Invoice# Line# Quant1 Part1      Amt1
-------------------------------------
1001     1     200    Screw      2.00
1001     2     300    Nut        2.25
1001     3     100    Whatever   0.75
1002     1       1    Motor     52.00
1002     2      10    Saw      121.00
1003     3       5    Brace     44.44

try it

Project_No Pers_ID Dept_No Job Salary
-------------------------------------
5 1 1 Analysis  13
5 1 2 Leader    18
7 1 1 Leader    18
8 1 1 Marketing 15
8 1 2 Leader    18

try it

transitive dependency?
A B C
-----
a a 1
b a 1
c b 1
d b 1
e c 2
f c 2

try it