Relational Theory – Difference Between Functional Dependency and Join Dependency

relational-theory

By definition, a functional dependency is defined as

Let X and Y be subsets of attributes of a relation R. A functional dependency X → Y holds over R if and only if for any instance r of R,
whenever two tuples t1 and t2 of r agree on the attributes X, they
also agree on the attributes Y. That is,

t1.X = t2.X ⇒ t1.Y = t2.Y

A join dependency, meanwhile,

A table T is subject to a join dependency if T can always be recreated by joining multiple tables each having a subset of the attributes of T.

I could be wrong, but I was wondering if there are any relation between the concept of functional dependency and join dependency.

Best Answer

Join Dependencies can be considered a generalization of Multivalued Dependencies, following the fact that a Multivalued Dependency X →→ Y in a relation R can be seen as another way of writing a binary Join Dependency ⨝[XY, X(U − Y)], where U is the set of all the attributes of the relation R.

For instance, in a relation describing employees together with their salary history as well as other attributes R(empNo, salary, year, name, role), we can say that there is a MultivaluedDependency empNo →→ salary, year or, equivalenty that there is a Join Dependency ⨝[{empNo, salary, year}, {empNo, name, role}] (note that this makes clear that in R holds also the “dual” Multivalued Dependency empNo →→ name, role).

You are asking which relations there are between Functional Dependencies and Join Dependencies. The question is reasonable, since there is a relation between Functional Dependencies and Multivalued Dependencies.

In Chapter 8 of Abiteboul, S. “Foundations of Databases.” Reading, Mass: Addison-Wesley, 1995. you can find an answer which is also proved:

Proposition 8.3.3. Let U be a set of attributes, {X, Y, Z} be a partition of U, and Σ be a set of Functional Dependencies over U. Then Σ ⊨ ⨝[XY, XZ] if and only if either Σ ⊨ X → Y or Σ ⊨ X → Z.

In other words, if a Functional Dependency X → Y holds in a relation schema R, then this implies that the binary Join Dependency ⨝[XY, XZ] holds, and viceversa. Note that this is equivalent to say that you can perform always a lossless decomposition of a relation R{X,Y,Z} with a functional dependency X → Y in R1{XY}, R2{XZ}.

So, for instance, in the previous example, since empNo → name, the Join Dependency ⨝[{empNo, name}, {empNo, salary, year, role}] holds and {R1(empNo, name), R2(empNo, salary, year, role)} is a lossless decomposition.

Related Question