Transitive Closure

The transitive closure of a directed graph G is the graph with the same vertices as G and with an edge connecting each pair of nodes that are connected by a path (not necessarily containing just one edge) in G. The transitive closure helps answer a number of questions immediately, without the need to explore paths in the graph. For example, is David a manager of Aaron (directly or indirectly)? If the transitive closure of the Employees graph contains an edge from David to Aaron, he is. Does Double Espresso contain water? Can I drive from Los Angeles to New York? If the input graph contains the edges (a, b) and (b, c), a and c have a transitive relationship. The transitive closure contains the edges (a, b), (b, c), and also (a, ...

Get Inside Microsoft® SQL Server® 2008: T-SQL Querying now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.