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), there’s a transitive relationship between a and c. The transitive closure will contain the edges (a, b), (b, ...
Get Inside Microsoft® SQL Server™ 2005: T-SQL Querying now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
