5

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.

4

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.

-1

For those who are reading on this topic, I thought the following elaboration might be helpful.

From C.J. Date's SQL and Relational Theory-How to Write Accurate SQL Code, it is mentioned in Appendix B that

It’s also immediate that every FD is a JD, because (as Heath’s theorem tells us) if R satisfies a certain FD, then it can be nonloss decomposed into certain projections (in other words, it satisfies a certain JD).

Essentially, Heath's theorem states

Heath's theorem. • A relation R(X,Y,Z) that satisfies a functional dependency X → Y can always be non-loss decomposed into its projections R1=πXY(R) and R2=πXZ(R)

  • This quote is taken from Appendix B of the 1st version of C.J. Date’s book (2009). In the 2nd edition (2012), the contents of this appendix have been removed. We must now refer to “Database Design & Relational Theory, Normal Forms & All That Jazz” (2012), where is written (page 114) “FDs aren’t JDs) [...] every FD implies a JD [...] the converse is false”... – François Jul 17 '18 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.