# Figuring out the equivalence between two definitions of "transitive functional dependencies" and intuition behind the intended meaning of definition

The definition given below is present in the exercise of the text Database System Concepts by Korth et. al.

Let $$\alpha$$ and $$\beta$$ be sets of attributes such that $$\alpha \rightarrow \beta$$ holds, but $$\beta \rightarrow \alpha$$ does not hold. Let $$A$$ be an attribute that is not in $$\alpha$$, is not in $$\beta$$, and for which $$\beta → A$$ holds. We say that $$A$$ is transitively dependent on $$\alpha$$ .

The definition given below is from the text Fundamentals of Database Systems by Navathe et. al.

A functional dependency $$X → Y$$ in a relation schema $$R$$ is a transitive dependency if there exists a set of attributes $$Z$$ in $$R$$ that is neither a candidate key nor a subset of any key of $$R^\dagger$$ and both $$X → Z$$ and $$Z → Y$$ hold.

$$\dagger:$$ This is the general definition of transitive dependency. Because we are concerned only with primary keys in this section, we allow transitive dependencies where $$X$$ is the primary key but $$Z$$ may be (a subset of) a candidate key.

The above two definitions are not exactly the same apparently. Now with the analogy of mathematical relations, I get the rough idea that if $$X\rightarrow Z$$ and $$Z\rightarrow Y$$ are functional dependencies then $$X\rightarrow Y$$ is a transitive functional dependency. [Just as we have in mathematics $$(a,b)\in R$$ and $$(b,c)\in R$$ and if a relation is transitive then we have $$(a,c)\in R$$.] But the thing is that, here these $$X$$, $$Y$$ and $$Z$$ have some added conditions to them. But in the definitions given in Navathe text and Korth text these conditions seem different.

The first definition says that if $$\alpha \rightarrow \beta$$ holds then $$\beta \rightarrow \alpha$$ should not hold. Also, $$A$$ should not be a part of either $$\alpha$$ or $$\beta$$. While the second definition talks about $$Z$$ being neither a candidate key nor a subset of a candidate key. Neither can I figure out the equivalence between them, [except that if $$Z$$ is not candidate key, then if $$X\rightarrow Z$$ then $$Z \rightarrow X$$ should not hold] nor the intuition behind these conditions.

Let first introduce a third definition of transitive dependency.

The fundamental idea of a transitive dependency is that you have a “cascade” of two “proper” functional dependencies X -> Z and Z -> Y in the same relation scheme. Let’s define exactly what I mean for “cascade of proper FDs”.

First, we want to exclude the case in which X and Z are “equivalent”, that is in which X -> Z and Z -> X. This is because if they are equivalent, it is safe to consider that Z -> Y is perfectly equivalent to X -> Y, so we can say that this is not really a transitive dependency (a “cascade of proper dependencies”). Note that this means also that Z cannot contain a candidate key, otherwise we will have that Z -> X.

Then, we want to exclude also the dependencies which are trivial, or in which Y contains at least an attribute which belongs to X or Z. Such dependencies in a certain sense are not “proper”, because the information contained in the dependency AB -> AC is perfectly equivalent to that contained in the dependency AB -> C (since A is obviously equal).

This is the basic definition of transitive dependency.

The main differences between the two definitions are so the following:

1. The first one considers dependencies with a single attribute in the right part, while in the second Y can be a set of attributes. As we have seen, this is not really an important difference, but can produce slightly different definitions.

2. The first definition takes into account trivial dependencies, while the second one ignore them (maybe this is said before the definition).

3. The first definition includes implicitly the fact that 𝛽 (in my definition Z) is not a candidate key, otherwise we will have 𝛽 -> 𝛼, while it do not say anything about the possibility that it contains only a subset of a candidate key. This is a real difference between the two definitions. I think that this constraint in the second definition is tied to the fact that the definition of transitive dependency is used in the definition of normal forms. Note that in one of the first paper on the subject, Bernstein, Philip A. “Synthesizing Third Normal Form Relations from Functional Dependencies.” ACM Transactions on Database Systems 1, no. 4 (1976): 277–98, the definition of transitive dependency is equivalent to that of the first book.

• Comments are not for extended discussion; this conversation has been moved to chat.
– D.W.
Nov 29, 2021 at 21:36