Re: transitive closure code and SQL wanted

From: Steve Kass <skass_at_drew.edu>
Date: Mon, 13 May 2002 23:35:13 -0400
Message-ID: <3CE085F1.A65784C6@drew.edu>

Steve,

While it's not efficient, the straightforward way to get the transitive closure is to start with the adjacency matrix M for the graph and compute M & M^2 & M^3 ... until there are no further changes.

A recent article on maintaining the transitive closure in SQL is:

"Maintaining Transitive Closure of Graphs in SQL," Guozhu Dong, Leonid Libkin, Jianwen Su, Limsoon Wong, Int. Journal of Information Technology (1999)

use tempdb
go

DROP PROCEDURE TransClose
DROP TABLE Management
DROP TABLE Employees
GO

CREATE TABLE Employees
(
empid INT NOT NULL PRIMARY KEY, empname VARCHAR(25) NOT NULL,
salary MONEY NOT NULL
)
GO

CREATE TABLE Management (
dist int NOT NULL DEFAULT 1,
empid int NOT NULL REFERENCES Employees (empid), mgrid int NOT NULL REFERENCES Employees (empid), CONSTRAINT Management_pk PRIMARY KEY NONCLUSTERED (empid, mgrid), CONSTRAINT Management_acyclic CHECK (empid <> mgrid) )
GO

CREATE UNIQUE CLUSTERED INDEX Matrices_mrc ON Management(dist, empid, mgrid) GO

CREATE PROCEDURE TransClose
AS
  SET NOCOUNT ON
  DELETE FROM Management
  WHERE dist > 1

  DECLARE @dist int
  SET @dist = 1
Extend:
  INSERT INTO Management
  SELECT @dist+1, A.empid, B.mgrid
  FROM Management A JOIN Management B
  ON A.dist = 1
  AND B.dist = @dist
  AND A.mgrid = B.empid
  GROUP BY A.empid, B.mgrid
  IF @@rowcount > 0 BEGIN
    SET @dist = @dist + 1
    GOTO Extend
  END
GO

INSERT INTO employees(empid, empname, salary) VALUES(1, 'Nancy', $10000.00) INSERT INTO employees(empid, empname, salary) VALUES(2, 'Andrew', $5000.00) INSERT INTO Management(empid, mgrid) VALUES (2,1) INSERT INTO employees(empid, empname, salary) VALUES(3, 'Janet', $5000.00) INSERT INTO Management(empid, mgrid) VALUES (3,1) INSERT INTO employees(empid, empname, salary) VALUES(4, 'Margaret', $5000.00) INSERT INTO Management(empid, mgrid) VALUES (4,1) INSERT INTO employees(empid, empname, salary) VALUES(5, 'Steven', $2500.00) INSERT INTO Management(empid, mgrid) VALUES (5,2) INSERT INTO employees(empid, empname, salary) VALUES(6, 'Michael', $2500.00)

INSERT INTO Management(empid, mgrid) VALUES (6,2)
INSERT INTO Management(empid, mgrid) VALUES (6,3)
INSERT INTO Management(empid, mgrid) VALUES (6,4)

INSERT INTO employees(empid, empname, salary) VALUES(7, 'Robert', $2500.00) INSERT INTO Management(empid, mgrid) VALUES (7,3) INSERT INTO employees(empid, empname, salary) VALUES(8, 'Laura', $2500.00) INSERT INTO Management(empid, mgrid) VALUES (8,3) INSERT INTO employees(empid, empname, salary) VALUES(9, 'Ann', $2500.00) INSERT INTO Management(empid, mgrid) VALUES (9,3) INSERT INTO employees(empid, empname, salary) VALUES(10, 'Ina', $2500.00) INSERT INTO Management(empid, mgrid) VALUES (10,4) INSERT INTO employees(empid, empname, salary) VALUES(11, 'David', $2000.00) INSERT INTO Management(empid, mgrid) VALUES (11,7) INSERT INTO employees(empid, empname, salary) VALUES(12, 'Ron', $2000.00) INSERT INTO Management(empid, mgrid) VALUES (12,7) INSERT INTO employees(empid, empname, salary) VALUES(13, 'Dan', $2000.00) INSERT INTO Management(empid, mgrid) VALUES (13,7) INSERT INTO employees(empid, empname, salary) VALUES(14, 'James', $1500.00) INSERT INTO Management(empid, mgrid) VALUES (14,11) INSERT INTO Management(empid, mgrid) VALUES (14,13) GO

EXEC TransClose
GO

SELECT
Management.mgrid,
COUNT(Management.empid) AS Subordinates, SUM(Salary) AS TotalSubSalary
FROM Management JOIN Employees
ON Management.empid = Employees.empid
GROUP BY Management.mgrid
ORDER BY 3 desc

SELECT
Employees.empid as Unfortunate,
COUNT(Management.mgrid) AS MgrCount
FROM Employees LEFT JOIN Management
ON Employees.empid = Management.empid
AND dist = 1
GROUP BY Employees.empid
HAVING COUNT(Management.mgrid) > 1
GO

Illegal inserts that will show when
TransClose is executed
Second manager at different level INSERT INTO Management(empid,mgrid) VALUES (14,6) EXEC TransClose

Steve Kass
Drew University

Steven Tolkin wrote:

> Summary:
> I want to get code (includes the the database DLDL and queries)
> that will compute the transitive closure of a graph (actually a tree).
> I am willing to pay a reasonable amount, but reliable freeware or
> shareware is fine.
> The database can be MS Access, MS SqlServer, or Oracle.
> The code can be in ASP, VB, Perl, or JavaScript.
> This should be as close to a "turnkey" tool as possible,
> but I also would prefer having the source code.
> But I could settle for binary only if well
> documented and supported.
> Other keywords sometimes used to describe this problem:
> self-join, recursive hierarchy.
>
> Details:
> My data is a tree of nodes.
> Suppose I have a table named node_parent that
> has two columns: node_id and parent_id.
> I want the code that will calculate a table named node_ancestor
> having the two columns: node_id and ancestor_id.
>
> (The names I use for tables and columns are just examples;
> they can have other names and other structure.)
>
> I also would like a GUI that presented the
> parent_child data, e.g. in a tree control or other editable GUI.
> To support this the node_parent table needs another column, named
> e.g. local_order, that holds the order among the siblings.
>
> It would be nice if the code also populated a column in
> node_ancestor that showed either the depth of the ancestor
> and/or the distance from the node to its ancestor.
> The point is to support the query that given a node, shows
> all its ancestors in the order parent, grandparent, ... root.
>
> Ideally the node_ancestor table will also contain a
> global_order column that is populated as the table is constructed.
>
> I am aware of the technique that assigns each node in the
> node_parent table a pair of numbers for the left and right
> edes of the interval defined by its descendants.
> Using this technique is fine, provided the code to referesh
> these after editing the the tree is included.
> I do not care how the root node is denoted; using either a NULL
> value or its own node_id is OK.
>
> Since my node_parent_child table should be a single tree
> it would be nice if the code complained if it found otherwise,
> e.g. multiple root nodes, unreachable nodes, multiple parents,
> or a cycle.
>
> Thanks,
> Steve
> --
> Steven Tolkin steve.tolkin_at_fmr.com 617-563-0516
> Fidelity Investments 82 Devonshire St. V8D Boston MA 02109
> There is nothing so practical as a good theory. Comments are by me,
> not Fidelity Investments, its subsidiaries or affiliates.
Received on Mon May 13 2002 - 22:35:13 CDT