Transitive dependency
Encyclopedia
In mathematics, a transitive dependency is a functional dependency
which holds by virtue of transitivity
. A transitive dependency can occur only in a relation
that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation. Suppose all three of the following conditions hold:
Then the functional dependency A → C (which follows from 1 and 3 by the axiom of transitivity) is a transitive dependency.
In database normalization
, one of the important features of third normal form
is that it excludes certain types of transitive dependencies. E.F. Codd, the inventor of the relational model
, introduced the concepts of transitive dependence and third normal form in 1971.
The functional dependency {Book} → {Author Nationality} applies; that is, if we know the book, we know the author's nationality. Furthermore:
Therefore {Book} → {Author Nationality} is a transitive dependency.
Transitive dependency occurred because a non-key attribute (Author) was determining another non-key attribute (Author Nationality).
Functional dependency
A functional dependency is a constraint between two sets of attributes in a relation from a database.Given a relation R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, if, and only if, each X value is associated with precisely one Y value...
which holds by virtue of transitivity
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
. A transitive dependency can occur only in a relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation. Suppose all three of the following conditions hold:
- A → B
- It is not the case that B → A
- B → C
Then the functional dependency A → C (which follows from 1 and 3 by the axiom of transitivity) is a transitive dependency.
In database normalization
Database normalization
In the design of a relational database management system , the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce smaller, well-structured relations...
, one of the important features of third normal form
Third normal form
In computer science, the third normal form is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971. Codd's definition states that a table is in 3NF if and only if both of the following conditions hold:...
is that it excludes certain types of transitive dependencies. E.F. Codd, the inventor of the relational model
Relational model
The relational model for database management is a database model based on first-order predicate logic, first formulated and proposed in 1969 by Edgar F...
, introduced the concepts of transitive dependence and third normal form in 1971.
Example
A transitive dependency occurs in the following relation:Book | Genre | Author | Author Nationality |
---|---|---|---|
Twenty Thousand Leagues Under the Sea Twenty Thousand Leagues Under the Sea Twenty Thousand Leagues Under the Sea is a classic science fiction novel by French writer Jules Verne published in 1870. It tells the story of Captain Nemo and his submarine Nautilus as seen from the perspective of Professor Pierre Aronnax... |
Science Fiction Science fiction Science fiction is a genre of fiction dealing with imaginary but more or less plausible content such as future settings, futuristic science and technology, space travel, aliens, and paranormal abilities... |
Jules Verne Jules Verne Jules Gabriel Verne was a French author who pioneered the science fiction genre. He is best known for his novels Twenty Thousand Leagues Under the Sea , A Journey to the Center of the Earth , and Around the World in Eighty Days... |
French French people The French are a nation that share a common French culture and speak the French language as a mother tongue. Historically, the French population are descended from peoples of Celtic, Latin and Germanic origin, and are today a mixture of several ethnic groups... |
Journey to the Center of the Earth Journey to the Center of the Earth A Journey to the Center of the Earth is a classic 1864 science fiction novel by Jules Verne. The story involves a German professor who believes there are volcanic tubes going toward the center of the Earth... |
Science Fiction Science fiction Science fiction is a genre of fiction dealing with imaginary but more or less plausible content such as future settings, futuristic science and technology, space travel, aliens, and paranormal abilities... |
Jules Verne Jules Verne Jules Gabriel Verne was a French author who pioneered the science fiction genre. He is best known for his novels Twenty Thousand Leagues Under the Sea , A Journey to the Center of the Earth , and Around the World in Eighty Days... |
French |
Leaves of Grass Leaves of Grass Leaves of Grass is a poetry collection by the American poet Walt Whitman . Though the first edition was published in 1855, Whitman spent his entire life writing Leaves of Grass, revising it in several editions until his death... |
Poetry Poetry Poetry is a form of literary art in which language is used for its aesthetic and evocative qualities in addition to, or in lieu of, its apparent meaning... |
Walt Whitman Walt Whitman Walter "Walt" Whitman was an American poet, essayist and journalist. A humanist, he was a part of the transition between transcendentalism and realism, incorporating both views in his works. Whitman is among the most influential poets in the American canon, often called the father of free verse... |
American United States The United States of America is a federal constitutional republic comprising fifty states and a federal district... |
Anna Karenina Anna Karenina Anna Karenina is a novel by the Russian writer Leo Tolstoy, published in serial installments from 1873 to 1877 in the periodical The Russian Messenger... |
Literary Fiction Literary fiction Literary fiction is a term that came into common usage during the early 1960s. The term is principally used to distinguish "serious fiction" which is a work that claims to hold literary merit, in comparison from genre fiction and popular fiction . In broad terms, literary fiction focuses more upon... |
Leo Tolstoy Leo Tolstoy Lev Nikolayevich Tolstoy was a Russian writer who primarily wrote novels and short stories. Later in life, he also wrote plays and essays. His two most famous works, the novels War and Peace and Anna Karenina, are acknowledged as two of the greatest novels of all time and a pinnacle of realist... |
Russian Russians The Russian people are an East Slavic ethnic group native to Russia, speaking the Russian language and primarily living in Russia and neighboring countries.... |
A Confession A Confession A Confession is a short work on questions of religion by Leo Tolstoy. It was first distributed in Russia in 1882.Consisting of autobiographical notes on the development of the author's belief, A Confession shows the process of searching for answers to the profound questions: "What will come of my... |
Religious Autobiography | Leo Tolstoy Leo Tolstoy Lev Nikolayevich Tolstoy was a Russian writer who primarily wrote novels and short stories. Later in life, he also wrote plays and essays. His two most famous works, the novels War and Peace and Anna Karenina, are acknowledged as two of the greatest novels of all time and a pinnacle of realist... |
Russian |
The functional dependency {Book} → {Author Nationality} applies; that is, if we know the book, we know the author's nationality. Furthermore:
- {Book} → {Author}
- {Author} does not → {Book}
- {Author} → {Author Nationality}
Therefore {Book} → {Author Nationality} is a transitive dependency.
Transitive dependency occurred because a non-key attribute (Author) was determining another non-key attribute (Author Nationality).