Transitive binary relations v t e
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti- reflexive Equivalence relation Y ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Preorder(Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Y ✗ ✗ Partial order ✗ Y ✗ ✗ ✗ ✗ Y ✗ ✗ Total preorder ✗ ✗ Y ✗ ✗ ✗ Y ✗ ✗ Total order ✗ Y Y ✗ ✗ ✗ Y ✗ ✗ Prewellordering ✗ ✗ Y Y ✗ ✗ Y ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Y ✗ ✗ Y ✗ ✗ Well-ordering ✗ Y Y Y ✗ ✗ Y ✗ ✗ Lattice ✗ Y ✗ ✗ Y Y Y ✗ ✗ Join-semilattice ✗ Y ✗ ✗ Y ✗ Y ✗ ✗ Meet-semilattice ✗ Y ✗ ✗ ✗ Y Y ✗ ✗ Strict partial order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict weak order ✗ Y ✗ ✗ ✗ ✗ ✗ Y Y Strict total order ✗ Y Y ✗ ✗ ✗ ✗ Y Y Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all${\displaystyle a,b}$ and${\displaystyle S\ne \varnothing :}$ ${\displaystyle \begin{array}{r}minS\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\vee b\\ \text{exists}\end{array}}$ ${\displaystyle \begin{array}{r}a\wedge b\\ \text{exists}\end{array}}$ ${\displaystyle aRa}$ ${\displaystyle \text{not }aRa}$ ${\displaystyle \begin{array}{r}aRb\Rightarrow \\ \text{not }bRa\end{array}}$
Y indicates that the column's property is always true for the row's term (at the very left), while✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated byY in the "Symmetric" column and✗ in the "Antisymmetric" column, respectively. All definitions tacitly require thehomogeneous relation${\displaystyle R}$ betransitive: for all${\displaystyle a,b,c,}$ if${\displaystyle aRb}$ and${\displaystyle bRc}$ then${\displaystyle aRc.}$ A term's definition may require additional properties that are not listed in this table.

Inmathematics, thetransitive closureR⁺ of ahomogeneous binary relationR on asetX is the smallestrelation onX that containsR and istransitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite setsR⁺ is the uniqueminimal transitivesuperset ofR.

For example, ifX is a set of airports andx R y means "there is a direct flight from airportx to airporty" (forx andy inX), then the transitive closure ofR onX is the relationR⁺ such thatxR⁺y means "it is possible to fly fromx toy in one or more flights".

More formally, the transitive closure of a binary relationR on a setX is the smallest (w.r.t. ⊆) transitive relationR⁺ onX such thatR ⊆R⁺; seeLidl & Pilz (1998, p. 337). We haveR⁺ =R if, and only if,R itself is transitive.

Conversely,transitive reduction reduces a minimal relationS from a given relationR such that they have the same closure, that is,S⁺ =R⁺; however, many differentS with this property may exist.

Both transitive closure and transitive reduction are also used in the closely related area ofgraph theory.

A relationR on a setX is transitive if, for allx,y,z inX, wheneverx R y andy R z thenx R z. Examples of transitive relations include the equality relation on any set, the "less than or equal" relation on any linearly ordered set, and the relation "x was born beforey" on the set of all people. Symbolically, this can be denoted as: ifx <y andy <z thenx <z.

One example of a non-transitive relation is "cityx can be reached via a direct flight from cityy" on the set of all cities. Simply because there is a direct flight from one city to a second city, and a direct flight from the second city to the third, does not imply there is a direct flight from the first city to the third. The transitive closure of this relation is a different relation, namely "there is a sequence of direct flights that begins at cityx and ends at cityy". Every relation can be extended in a similar way to a transitive relation.

An example of a non-transitive relation with a less meaningful transitive closure is "x is theday of the week aftery". The transitive closure of this relation is "some dayx comes after a dayy on the calendar", which is trivially true for all days of the weekx andy (and thus equivalent to theCartesian square, which is "x andy are both days of the week").

For any relationR, the transitive closure ofR always exists. To see this, note that theintersection of anyfamily of transitive relations is again transitive. Furthermore,there exists at least one transitive relation containingR, namely the trivial one:X ×X. The transitive closure ofR is then given by the intersection of all transitive relations containingR.

For finite sets, we can construct the transitive closure step by step, starting fromR and adding transitive edges.This gives the intuition for a general construction. For any setX, wecan prove that transitive closure is given by the following expression

${\displaystyle R^{+}=\bigcup _{i=1}^{\mathrm{\infty }}{R}^i.}$

where${\displaystyle R^i}$ is thei-th power ofR, defined inductively by

${\displaystyle R^1=R}$

and, for${\displaystyle i>0}$,

${\displaystyle R^{i+1}=R\circ R^i}$

where${\displaystyle \circ }$ denotescomposition of relations.

To show that the above definition ofR⁺ is the least transitive relation containingR, we show that it containsR, that it is transitive, and that it is the smallest set with both of those characteristics.

• ${\displaystyle R\subseteq R^{+}}$:${\displaystyle R^{+}}$ contains all of the${\displaystyle R^i}$, so in particular${\displaystyle R^{+}}$ contains${\displaystyle R}$.
• ${\displaystyle R^{+}}$ is transitive: If${\displaystyle (s_1,s_2),(s_2,s_3)\in R^{+}}$, then${\displaystyle (s_1,s_2)\in R^j}$ and${\displaystyle (s_2,s_3)\in R^k}$ for some${\displaystyle j,k}$ by definition of${\displaystyle R^{+}}$. Since composition is associative,${\displaystyle R^{j+k}=R^j\circ R^k}$; hence${\displaystyle (s_1,s_3)\in R^{j+k}\subseteq R^{+}}$ by definition of${\displaystyle \circ }$ and${\displaystyle R^{+}}$.
• ${\displaystyle R^{+}}$ is minimal, that is, if${\displaystyle T}$ is any transitive relation containing${\displaystyle R}$, then${\displaystyle R^{+}\subseteq T}$: Given any such${\displaystyle T}$,induction on${\displaystyle i}$ can be used to show${\displaystyle R^i\subseteq T}$ for all${\displaystyle i}$ as follows:Base:${\displaystyle R^1=R\subseteq T}$ by assumption.Step: If${\displaystyle R^i\subseteq T}$ holds, and${\displaystyle (s_1,s_3)\in R^{i+1}=R\circ R^i}$, then${\displaystyle (s_1,s_2)\in R}$ and${\displaystyle (s_2,s_3)\in R^i}$ for some${\displaystyle s_2}$, by definition of${\displaystyle \circ }$. Hence,${\displaystyle (s_1,s_2),(s_2,s_3)\in T}$ by assumption and by induction hypothesis. Hence${\displaystyle (s_1,s_3)\in T}$ by transitivity of${\displaystyle T}$; this completes the induction. Finally,${\displaystyle R^i\subseteq T}$ for all${\displaystyle i}$ implies${\displaystyle R^{+}\subseteq T}$ by definition of${\displaystyle R^{+}}$.

Theintersection of two transitive relations is transitive.

Theunion of two transitive relations need not be transitive. To preserve transitivity, one must take the transitive closure. This occurs, for example, when taking the union of twoequivalence relations or twopreorders. To obtain a new equivalence relation or preorder one must take the transitive closure (reflexivity and symmetry—in the case of equivalence relations—are automatic).

Incomputer science, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answerreachability questions. That is, can one get from nodea to noded in one or more hops? A binary relation tells you only that node a is connected to nodeb, and that nodeb is connected to nodec, etc. After the transitive closure is constructed, as depicted in the following figure, in anO(1)-time operation one may determine that noded is reachable from nodea. The data structure is typically stored as a Boolean matrix, so if matrix[1][4] = true, then it is the case that node 1 can reach node 4 through one or more hops.

The transitive closure of the adjacency relation of adirected acyclic graph (DAG) is the reachability relation of the DAG and astrict partial order.

The transitive closure of anundirected graph produces acluster graph, adisjoint union ofcliques. Constructing the transitive closure is an equivalent formulation of the problem of finding thecomponents of the graph.^[1]

The transitive closure of a binary relationcannot, in general, be expressed infirst-order logic (FO).This means that one cannot write a formula using predicate symbolsR andT that will be satisfied inany model if and only ifT is the transitive closure ofR.Infinite model theory, first-order logic (FO) extended with a transitive closure operator is usually calledtransitive closure logic, and abbreviated FO(TC) or just TC. TC is a sub-type offixpoint logics. The fact that FO(TC) is strictly more expressive than FO was discovered byRonald Fagin in 1974; the result was then rediscovered byAlfred Aho andJeffrey Ullman in 1979, who proposed to use fixpoint logic as adatabase query language.^[2] With more recent concepts of finite model theory, proof that FO(TC) is strictly more expressive than FO follows immediately from the fact that FO(TC) is notGaifman-local.^[3]

Incomputational complexity theory, thecomplexity classNL corresponds precisely to the set of logical sentences expressible in TC. This is because the transitive closure property has a close relationship with theNL-complete problemSTCON for findingdirected paths in a graph. Similarly, the classL is first-order logic with the commutative, transitive closure. When transitive closure is added tosecond-order logic instead, we obtainPSPACE.

Since the 1980sOracle Database has implemented a proprietarySQL extensionCONNECT BY... START WITH that allows the computation of a transitive closure as part of a declarative query. TheSQL 3 (1999) standard added a more generalWITH RECURSIVE construct also allowing transitive closures to be computed inside the query processor; as of 2011 the latter is implemented inIBM Db2,Microsoft SQL Server,Oracle,PostgreSQL, andMySQL (v8.0+).SQLite released support for this in 2014.

Datalog also implements transitive closure computations.^[4]

MariaDB implements Recursive Common Table Expressions, which can be used to compute transitive closures. This feature was introduced in release 10.2.2 of April 2016.^[5]

Efficient algorithms for computing the transitive closure of the adjacency relation of a graph can be found inNuutila (1995). Reducing the problem to multiplications of adjacency matrices achieves the time complexity offast matrix multiplication algorithms,^[6]${\displaystyle O(n^{2.3728596})}$. However, this approach is not practical since both the constant factors and the memory consumption for sparse graphs are high (Nuutila 1995, pp. 22–23, sect.2.3.3). The problem can also be solved by theFloyd–Warshall algorithm in${\displaystyle O(n^3)}$, or by repeatedbreadth-first search ordepth-first search starting from each node of the graph.

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. Its runtime is${\displaystyle O(m+\mu n)}$, where${\displaystyle \mu }$ is the number of edges between itsstrongly connected components.^{[7][8][9][10]}

More recent research has explored efficient ways of computing transitive closure on distributed systems based on theMapReduce paradigm.^[11]

• Ancestral relation
• Deductive closure
• Reflexive closure
• Symmetric closure
• Transitive reduction (a smallest relation having the transitive closure ofR as its transitive closure)

• Foto N. Afrati, Vinayak Borkar,Michael Carey, Neoklis Polyzotis,Jeffrey D. Ullman,Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden,ISBN 978-1-4503-0528-0
• Aho, A. V.;Ullman, J. D. (1979). "Universality of data retrieval languages".Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages - POPL '79. pp. 110–119.doi:10.1145/567752.567763.
• Benedikt, M.; Senellart, P. (2011). "Databases". In Blum, Edward K.; Aho, Alfred V. (eds.).Computer Science. The Hardware, Software and Heart of It. pp. 169–229.doi:10.1007/978-1-4614-1168-0_10.ISBN 978-1-4614-1167-3.
• Heinz-Dieter Ebbinghaus; Jörg Flum (1999).Finite Model Theory (2nd ed.). Springer. pp. 123–124,151–161,220–235.ISBN 978-3-540-28787-2.
• Fischer, M.J.; Meyer, A.R. (Oct 1971)."Boolean matrix multiplication and transitive closure"(PDF). In Raymond E. Miller and John E. Hopcroft (ed.).Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Computer Society. pp. 129–131.doi:10.1109/SWAT.1971.4.
• Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007).Finite Model Theory and Its Applications. Springer. pp. 151–152.ISBN 978-3-540-68804-4.
• Keller, U., 2004,Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)
• Libkin, Leonid (2004),Elements of Finite Model Theory, Springer,ISBN 978-3-540-21202-7
• Lidl, R.; Pilz, G. (1998),Applied abstract algebra,Undergraduate Texts in Mathematics (2nd ed.), Springer,ISBN 0-387-98290-6
• Munro, Ian (Jan 1971). "Efficient determination of the transitive closure of a directed graph".Information Processing Letters.1 (2):56–58.doi:10.1016/0020-0190(71)90006-8.
• Nuutila, Esko (1995).Efficient transitive closure computation in large digraphs. Finnish Academy of Technology.ISBN 951-666-451-2.OCLC 912471702.
• Abraham Silberschatz; Henry Korth; S. Sudarshan (2010).Database System Concepts (6th ed.). McGraw-Hill.ISBN 978-0-07-352332-3.Appendix C (online only)

• "Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena.

• Binary relations
• Closure operators
• Graph algorithms

• Articles with short description
• Short description is different from Wikidata