Transitive closure

The closure of a relation to make it transitive. See Warshall's algorithm.

Recall that a set A is said to be transitive if whenever x is in A and y is in x then y is in A. To put that another way, every member is also a subset.

If X is any set, the transitive closure of X is the smallest set Y such that Y is transitive and contains X. "Smallest" in this context means that whenever Z is transitive and contains X, then Z contains Y.

It can be shown that every set has a transitive closure; this is an application of the recursion theorem.

Stepping aside from set theory for a moment - the transitive closure of a graph is another interesting problem/property. For a directed graph G = (V, E), the transitive closure of G is the graph (call it G') (V, E') such that an edge e is in E' if and only if there is a directed path from e_v1 to e_v2. That is, the edge set of G' is all pairs of vertices in G where there is a path between the two vertices.

I don't suppose that was very enlightening, was it? Alright then, express the edge set of G as the relation Edge(A, B), where A and B are the endpoints of an edge. In datalog, one program that would find the relation describing all edges in the transitive closure of G would be:

• Closure(x,y)<--Edge(x,y)
• Closure(x,y)<--Closure(x,z), Edge(z,y)

I will state here, without backing it up (another node for another day, if it doesn't exist), that to find the transitive closure of a graph, the toolset you use needs to have some sort of iterative or recursive tool. This is why transitive closure can be found simply in datalog, but cannot be expressed at all in simple relational algebras (any of the first few described in relational algebra, for example). To find the transitive closure of a graph using relational algebra (using the same sort of relation as described above for datalog), you would need to add a while or fixpoint operator.