Search code examples
databasefunctional-dependencies

Determining functional dependencies from a chart

Can anyone explain to me how to go about figuring out which dependencies the following instance satisfies?

 A   B   C
 1   0   1
 1   1   1

I know it satisfies B-> A, B->C, A->C, C->A (and other implied dependencies) but I haven't been able to grasp the concept of how to just view that from this chart. Can anyone explain how I am supposed to read it and go about determining what it satisfies with only the 0's and 1's ?

Adding another example to help better understand:

 A  B  C
 1  0  1
 1  1  1 
 2  2  1

Since there is only one row where B = 0 and B = 2, can you base the B -> A off of only one row with one unique value. Like since there is only one place where B = 0 and A = 1 does that mean it automatically holds since there is no other value of B with a 0 ?

Solution

  • A way of answering to a question like this is to look at all the possible proper subsets of columns, let's call them X1, X2, ... , starting first with single columns (so in this case we start with X1=A, X2=B, X3=C, and trying to see, for identical value in Xi, which other columns have identical values.

    For instance, starting with A, we discover that for A=1, B has two different values: this means that B cannot depend on A, (that is has not the same value for the value of A, which is the definition of functional dependency), while C has the same value (1), so that we know that this instance of relation satisfies A → C.

    Looking at B, we discover that all the values are different, so we can say that all the other columns are dependent on it, and we add B → A, B → C. Finally, in analysing C, we discover that only the values of A are equal when the values of C are equal, so that C → A.

    We can stop here, without considering the pairs of attributes AB, AC, and BC, since in this simple case every attribute is the determinant of some dependency, so that dependencies with set of attributes as determinant are implied by the dependencies already found.

    In summary

    In a certain instance, to know if a dependency X -> Y hold or not, we check: if all the values of X are different, then the dependency hold; if there are rows with repeat values, then, if for each row with the same value of X the value of Y is always the same, then the dependency holds, otherwise no.

    Here is another example:

     A  B  C
 1  2  2
 0  3  3
 1  2  4
 2  2  4

    In this instance A → B ? Yes, since the are two rows (the first and the fourth) with the same value of A (1), and in both rows the value of B is equal (2). Is A → C ? No, since C has two different values in the first and fourth row. B → A ? No, since B has three rows with the same value (2) and A has different values in the same rows (1 and 2).