Transitive closure
A term's definition may require additional properties that are not listed in this table.
For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets R+ is the unique minimal transitive superset of R. For example, if X is a set of airports and x R y means "there is a direct flight from airport x to airport y" (for x and y in X), then the transitive closure of R on X is the relation R+ such that x R+ y means "it is possible to fly from x to y in one or more flights".
More formally, the transitive closure of a binary relation R on a set X is the smallest (w.r.t.
An example of a non-transitive relation with a less meaningful transitive closure is "x is the day of the week after y".
This occurs, for example, when taking the union of two equivalence relations or two preorders.
In computer science, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer reachability questions.
The transitive closure of the adjacency relation of a directed acyclic graph (DAG) is the reachability relation of the DAG and a strict partial order.
Constructing the transitive closure is an equivalent formulation of the problem of finding the components of the graph.
[1] The transitive closure of a binary relation cannot, in general, be expressed in first-order logic (FO).
This means that one cannot write a formula using predicate symbols R and T that will be satisfied in any model if and only if T is the transitive closure of R. In finite model theory, first-order logic (FO) extended with a transitive closure operator is usually called transitive closure logic, and abbreviated FO(TC) or just TC.
The fact that FO(TC) is strictly more expressive than FO was discovered by Ronald Fagin in 1974; the result was then rediscovered by Alfred Aho and Jeffrey Ullman in 1979, who proposed to use fixpoint logic as a database query language.
This is because the transitive closure property has a close relationship with the NL-complete problem STCON for finding directed paths in a graph.
Similarly, the class L is first-order logic with the commutative, transitive closure.
When transitive closure is added to second-order logic instead, we obtain PSPACE.
Since the 1980s Oracle Database has implemented a proprietary SQL extension CONNECT BY... START WITH that allows the computation of a transitive closure as part of a declarative query.
The SQL 3 (1999) standard added a more general WITH RECURSIVE construct also allowing transitive closures to be computed inside the query processor; as of 2011 the latter is implemented in IBM Db2, Microsoft SQL Server, Oracle, PostgreSQL, and MySQL (v8.0+).
[4] MariaDB implements Recursive Common Table Expressions, which can be used to compute transitive closures.
[5] Efficient algorithms for computing the transitive closure of the adjacency relation of a graph can be found in Nuutila (1995).
However, this approach is not practical since both the constant factors and the memory consumption for sparse graphs are high (Nuutila 1995, pp.
For directed graphs, Purdom's algorithm solves the problem by first computing its condensation DAG and its transitive closure, then lifting it to the original graph.
[7][8][9][10] More recent research has explored efficient ways of computing transitive closure on distributed systems based on the MapReduce paradigm.
