In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the transitive closure of a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
on a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
is the smallest
relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
on that contains and is
transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite sets it is the unique
minimal transitive
superset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...
of .
For example, if is a set of airports and means "there is a direct flight from airport to airport " (for and in ), then the transitive closure of on is the relation such that means "it is possible to fly from to in one or more flights". Informally, the ''transitive closure'' gives you the set of all places you can get to from any starting place.
More formally, the transitive closure of a binary relation on a set is the transitive relation on set such that contains and is minimal; see . If the binary relation itself is transitive, then the transitive closure is that same binary relation; otherwise, the transitive closure is a different relation.
Conversely,
transitive reduction
In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists if ...
adduces a minimal relation from a given relation such that they have the same closure, that is, ; however, many different with this property may exist.
Both transitive closure and transitive reduction are also used in the closely related area of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
.
Transitive relations and examples
A relation ''R'' on a set ''X'' is transitive if, for all ''x'', ''y'', ''z'' in ''X'', whenever and then . 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 before ''y''" on the set of all people. Symbolically, this can be denoted as: if and then .
One example of a non-transitive relation is "city ''x'' can be reached via a direct flight from city ''y''" 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 city ''x'' and ends at city ''y''". 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 the
day of the week
In many languages, the names given to the seven days of the week are derived from the names of the classical planets in Hellenistic astronomy, which were in turn named after contemporary deities, a system introduced by the Sumerians and la ...
after ''y''". The transitive closure of this relation is "some day ''x'' comes after a day ''y'' on the calendar", which is trivially true for all days of the week ''x'' and ''y'' (and thus equivalent to the
Cartesian square
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...
, which is "''x'' and ''y'' are both days of the week").
Existence and description
For any relation ''R'', the transitive closure of ''R'' always exists. To see this, note that the
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of any
family
Family (from la, familia) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its ...
of transitive relations is again transitive. Furthermore,
there exists
In predicate logic, an existential quantification is a type of quantifier, a logical constant which is interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by the logical operator symbol ∃, which, w ...
at least one transitive relation containing ''R'', namely the trivial one: ''X'' × ''X''. The transitive closure of ''R'' is then given by the intersection of all transitive relations containing ''R''.
For finite sets, we can construct the transitive closure step by step, starting from ''R'' and adding transitive edges.
This gives the intuition for a general construction. For any set ''X'', we
can prove that transitive closure is given by the following expression
:
where
is the ''i''-th power of ''R'', defined inductively by
:
and, for
,
:
where
denotes
composition of relations
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplica ...
.
To show that the above definition of ''R''
+ is the least transitive relation containing ''R'', we show that it contains ''R'', that it is transitive, and that it is the smallest set with both of those characteristics.
*
:
contains all of the
, so in particular
contains
.
*
is transitive: If
, then
and
for some
by definition of
. Since composition is associative,
; hence
by definition of
and
.
*
is minimal, that is, if
is any transitive relation containing
, then
: Given any such
,
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
on
can be used to show
for all
as follows: ''Base:''
by assumption. ''Step:'' If
holds, and
, then
and
for some
, by definition of
. Hence,
by assumption and by induction hypothesis. Hence
by transitivity of
; this completes the induction. Finally,
for all
implies
by definition of
.
Properties
The
intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their i ...
of two transitive relations is transitive.
The
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
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 two
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s or two
preorder
In mathematics, especially in order theory, a preorder or quasiorder is a binary relation that is reflexive and transitive. Preorders are more general than equivalence relations and (non-strict) partial orders, both of which are special c ...
s. 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).
In graph theory
![Transitive-closure](https://upload.wikimedia.org/wikipedia/commons/6/60/Transitive-closure.svg)
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the concept of transitive closure can be thought of as constructing a data structure that makes it possible to answer
reachability
In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s an ...
questions. That is, can one get from node ''a'' to node ''d'' in one or more hops? A binary relation tells you only that node a is connected to node ''b'', and that node ''b'' is connected to node ''c'', etc. After the transitive closure is constructed, as depicted in the following figure, in an
O(1)
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Land ...
operation one may determine that node ''d'' is reachable from node ''a''. The data structure is typically stored as a matrix, so if matrix
4] = 1, 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 a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(DAG) is the reachability relation of the DAG and a
strict partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
.
![Equivalentie](https://upload.wikimedia.org/wikipedia/commons/3/38/Equivalentie.svg)
The transitive closure of an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
produces a
cluster graph
In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs.
Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster gra ...
, a
disjoint union
In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of
cliques
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...
. Constructing the transitive closure is an equivalent formulation of the problem of finding the
components
Circuit Component may refer to:
•Are devices that perform functions when they are connected in a circuit.
In engineering, science, and technology Generic systems
* System components, an entity with discrete structure, such as an assem ...
of the graph.
In logic and computational complexity
The transitive closure of a binary relation cannot, in general, be expressed in
first-order logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
(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. TC is a sub-type of
fixpoint logic In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query la ...
s. The fact that FO(TC) is strictly more expressive than FO was discovered by
Ronald Fagin
Ronald Fagin (born 1945) is an American mathematician and computer scientist, and IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, and reasoning about knowledge.
Biography
Ron ...
in 1974; the result was then rediscovered by
Alfred Aho
Alfred Vaino Aho (born August 9, 1941) is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.
Aho was elected into ...
and
Jeffrey Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the dr ...
in 1979, who proposed to use fixpoint logic as a
database query language
Query languages, data query languages or database query languages (DQL) are computer languages used to make queries in databases and information systems. A well known example is the Structured Query Language (SQL).
Types
Broadly, query language ...
. 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 not
Gaifman-local.
In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
NL corresponds precisely to the set of logical sentences expressible in TC. This is because the transitive closure property has a close relationship with the
NL-complete In computational complexity theory, NL-complete is a complexity class containing the languages that are complete for NL, the class of decision problems that can be solved by a nondeterministic Turing machine using a logarithmic amount of memory s ...
problem
STCON for finding
directed path
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct (and since the vertices are distinct, so are the edges). A directed path (sometimes c ...
s 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
In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
First-order logic quantifies onl ...
instead, we obtain
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
.
In database query languages
Since the 1980s
Oracle Database
Oracle Database (commonly referred to as Oracle DBMS, Oracle Autonomous Database, or simply as Oracle) is a multi-model database management system produced and marketed by Oracle Corporation.
It is a database commonly used for running online t ...
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
Db2 is a family of data management products, including database servers, developed by IBM. It initially supported the relational model, but was extended to support object–relational features and non-relational structures like JSON a ...
,
Microsoft SQL Server
Microsoft SQL Server is a relational database management system developed by Microsoft. As a database server, it is a software product with the primary function of storing and retrieving data as requested by other software applications—which ma ...
,
Oracle
An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination.
Description
The word '' ...
,
PostgreSQL
PostgreSQL (, ), also known as Postgres, is a free and open-source relational database management system (RDBMS) emphasizing extensibility and SQL compliance. It was originally named POSTGRES, referring to its origins as a successor to the In ...
, and
MySQL
MySQL () is an open-source relational database management system (RDBMS). Its name is a combination of "My", the name of co-founder Michael Widenius's daughter My, and "SQL", the acronym for Structured Query Language. A relational database o ...
(v8.0+).
Datalog
Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
also implements transitive closure computations.
MariaDB
MariaDB is a community-developed, commercially supported fork of the MySQL relational database management system (RDBMS), intended to remain free and open-source software under the GNU General Public License. Development is led by some of the ori ...
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.
Algorithms
Efficient algorithms for computing the transitive closure of the adjacency relation of a graph can be found in . Reducing the problem to multiplications of adjacency matrices achieves the least time complexity, viz. that of
matrix multiplication
In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...
(, ), which is
. However, this approach is not practical since both the constant factors and the memory consumption for sparse graphs are high . The problem can also be solved by the
Floyd–Warshall algorithm
In computer science, the Floyd–Warshall algorithm (also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with p ...
in
, or by repeated
breadth-first search
Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...
or
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
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
, where
is the number of edges between its
strongly connected component
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...
s.
More recent research has explored efficient ways of computing transitive closure on distributed systems based on the
MapReduce
MapReduce is a programming model and an associated implementation for processing and generating big data sets with a parallel, distributed algorithm on a cluster.
A MapReduce program is composed of a ''map'' procedure, which performs filtering ...
paradigm.
[(Afrati et al. 2011)]
See also
*
Ancestral relation
*
Deductive closure
In mathematical logic, a set of logical formulae is deductively closed if it contains every formula that can be logically deduced from , formally: if always implies . If is a set of formulae, the deductive closure of is its smallest superse ...
*
Reflexive closure In mathematics, the reflexive closure of a binary relation ''R'' on a set ''X'' is the smallest reflexive relation on ''X'' that contains ''R''.
For example, if ''X'' is a set of distinct numbers and ''x R y'' means "''x'' is less than ''y''", the ...
*
Symmetric closure In mathematics, the symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R.
For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the ...
*
Transitive reduction
In the mathematical field of graph theory, a transitive reduction of a directed graph is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices , a (directed) path from to in exists if ...
(a smallest relation having the transitive closure of ''R'' as its transitive closure)
References
* 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,
*
*
*
*
*
* Keller, U., 2004,
Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog' (unpublished manuscript)*
*
*
*
* {{cite book, author1=Abraham Silberschatz, author2=Henry Korth, author3=S. Sudarshan, title=Database System Concepts, year=2010, edition=6th, publisher=McGraw-Hill, isbn=978-0-07-352332-3, title-link=Database System Concepts}
Appendix C(online only)
External links
*
Transitive closure and reduction, The Stony Brook Algorithm Repository, Steven Skiena.
Binary relations
Closure operators
Graph algorithms