# functional dependency of table attributes

posted 10 years ago

Hi guys,

I need a method to check all the functional dependency in a given table .

for an example:

r1 r2

2 5

2 5

3 10

4 10

5 32

here r2 depends on r1 because when r1 is 2, r2 is always 5 ,but r1 does not depended on r2 because when r2 is 10,r1 have two different values,which is 3 and 4

i guess i need to find the similar numbers and if they relate to same numbers in other rows, then functional dependencies exist.

can someone give me a hint (hopefully some source code) to get all dependencies of a table (columns, rows).

should return a string like r2->r1 ( or A->(B,C) ) ect..

thank you for your help !

I need a method to check all the functional dependency in a given table .

for an example:

r1 r2

2 5

2 5

3 10

4 10

5 32

here r2 depends on r1 because when r1 is 2, r2 is always 5 ,but r1 does not depended on r2 because when r2 is 10,r1 have two different values,which is 3 and 4

i guess i need to find the similar numbers and if they relate to same numbers in other rows, then functional dependencies exist.

can someone give me a hint (hopefully some source code) to get all dependencies of a table (columns, rows).

should return a string like r2->r1 ( or A->(B,C) ) ect..

thank you for your help !

posted 10 years ago

Well keep in mind that you are working only with a subset of data, so the functional dependencies you infer from the data will hold as long as new data is not inserted that could violate any such functional dependencies (assuming you dont know any of dependencies a database is enforcing).

For 2 columns, the solution (as you saw in your example) is pretty trivial, but for multiple columns its a little harder. The obvious (but computationally expensive) solution is to assume all functional dependencies possible exist, then go on eliminate ones that do not work. There are ways of combining results (using recursive and dynamic programming), such as if A->ABC then A->A, A->B, A->C, and so on and those substrings do not need to be checked.

I wrote something similar to this (shameless plug) although it works with the real functional dependencies instead of example data as you have. http://dbtools.cs.cornell.edu/norm_index.html

There are a number of algorithms to solve this faster, and I believe they rely on finding the super keys and keys of the relation (table).

[ December 10, 2005: Message edited by: Scott Selikoff ]

For 2 columns, the solution (as you saw in your example) is pretty trivial, but for multiple columns its a little harder. The obvious (but computationally expensive) solution is to assume all functional dependencies possible exist, then go on eliminate ones that do not work. There are ways of combining results (using recursive and dynamic programming), such as if A->ABC then A->A, A->B, A->C, and so on and those substrings do not need to be checked.

I wrote something similar to this (shameless plug) although it works with the real functional dependencies instead of example data as you have. http://dbtools.cs.cornell.edu/norm_index.html

There are a number of algorithms to solve this faster, and I believe they rely on finding the super keys and keys of the relation (table).

[ December 10, 2005: Message edited by: Scott Selikoff ]

[OCA 8 Book] [OCP 8 Book] [Blog] * SCJP (1.4, 1.6) * OCAJP 8 * OCPJP 8

Stan James

(instanceof Sidekick)

Ranch Hand

Ranch Hand

Posts: 8791

posted 10 years ago

You described the way you look for dependency yourself. To paraphrase, for each value in R1, count the values associated with it in R2. If the answer is always 1, then R2 depends on R1. (Actually the first time the answer is not 1 I think we can stop.) Repeat for all the values in R2 to see if there is a dependency the other way.

Now, how do we say that in code?

Does that look right? Can you say that in Java?

Now, how do we say that in code?

Does that look right? Can you say that in Java?

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

posted 10 years ago

thanks for stan and scott for their precious replies.

well the solution proposed by stan is interesting; but will it work in case two attributes depends on 1 or two ones . ex : A->(B,C) or (A,C)->(B,D) etc...

is there a way to construct output like above one. should i use the same method described by stan ?

thanks

well the solution proposed by stan is interesting; but will it work in case two attributes depends on 1 or two ones . ex : A->(B,C) or (A,C)->(B,D) etc...

is there a way to construct output like above one. should i use the same method described by stan ?

thanks

posted 10 years ago

Example

Relation R1

A B C

1 2 2

1 3 2

2 2 1

1 3 3

should give

C→A

BC→A

how can i test for BC→A ? which logic should i use ?

thanks.

Relation R1

A B C

1 2 2

1 3 2

2 2 1

1 3 3

should give

C→A

BC→A

how can i test for BC→A ? which logic should i use ?

thanks.

posted 10 years ago

hi,

i wrote a method to check fd between two rows...for example i found these dependences :

C->A

B->A

A->B

B->C

C->B

now from above relations i need to deduce the relations :

C→A

BC→A

which reflect the dependencies of the table.

can you help me find an algorithm to deduce second rel from relations above?

thanks.

i wrote a method to check fd between two rows...for example i found these dependences :

C->A

B->A

A->B

B->C

C->B

now from above relations i need to deduce the relations :

C→A

BC→A

which reflect the dependencies of the table.

can you help me find an algorithm to deduce second rel from relations above?

thanks.

Ulf Dittmer

Rancher

Posts: 42967

73

posted 10 years ago

Hello "E.othman"-

We have a policy on screen names here on JavaRanch, and yours does not conform to it. You have been asked before to change it; please so now on this page. Accounts with improper screen names are generally closed. Thanks for your attention to this matter.

We have a policy on screen names here on JavaRanch, and yours does not conform to it. You have been asked before to change it; please so now on this page. Accounts with improper screen names are generally closed. Thanks for your attention to this matter.

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |