Recursive query

[Roberto C]

Hi.
My problem is:
I have build an "hierarquical" query that selects from a
EMPLOYEES table and, for every manager, lists his/her name
and in the subsequent lines lists his/her subordinated
employees, and so on. Notice that a subordinated employee
may also have subordinated employees.
The table EMPLOYEE is:
create table EMPLOYEES (
emp_id bigint primary key,
emp_name varchar(100),
emp_function varchar(50),
emp_manager_id foreign key references EMPLOYEES(emp_id)
)
As you can see, an employee's record points to the
employee's boss.
So, the listing should show:
EMP_ID EMP_NAME EMP_FUNCTION
------ ------------- -------------------------
001 Anthony Manager of IT
005 Charles Business Analyst
020 Denys B.An. Trainee
050 Albert B.An. Trainee
009 Cindy Data Administrator
056 Helen D.A. Trainee
006 Marcus Manager of Accounting
022 Steve Accountant
070 Fred Accountant
..........
and so on.
I'd appreciate so much any help you can give me.
Thank you all.
Roberto.

[David Portas]

See Expanding Hierarchies topic in BOL.

Also consider using the Nested Sets model which makes it easier to query a
hierarchy of unknown depth:

[url]http://www.intelligententerprise.com/001020/celko1_1.shtml[/url]

--
David Portas
------------
Please reply only to the newsgroup
--

[John Gilson]

"Roberto C" <roberto_camara@hotmail.com> wrote in message
news:003301c343e6$ade0dd40$a501280a@phx.gbl...

> Hi.
> My problem is:
> I have build an "hierarquical" query that selects from a
> EMPLOYEES table and, for every manager, lists his/her name
> and in the subsequent lines lists his/her subordinated
> employees, and so on. Notice that a subordinated employee
> may also have subordinated employees.
> The table EMPLOYEE is:
> create table EMPLOYEES (
> emp_id bigint primary key,
> emp_name varchar(100),
> emp_function varchar(50),
> emp_manager_id foreign key references EMPLOYEES(emp_id)
> )
> As you can see, an employee's record points to the
> employee's boss.
> So, the listing should show:
> EMP_ID EMP_NAME EMP_FUNCTION
> ------ ------------- -------------------------
> 001 Anthony Manager of IT
> 005 Charles Business Analyst
> 020 Denys B.An. Trainee
> 050 Albert B.An. Trainee
> 009 Cindy Data Administrator
> 056 Helen D.A. Trainee
> 006 Marcus Manager of Accounting
> 022 Steve Accountant
> 070 Fred Accountant
> .........
> and so on.
> I'd appreciate so much any help you can give me.
> Thank you all.
> Roberto.

CREATE TABLE Employees
(
emp_id INT NOT NULL PRIMARY KEY,
emp_name VARCHAR(25) NOT NULL,
emp_function VARCHAR(50) NOT NULL,
emp_manager_id INT NULL REFERENCES Employees (emp_id)
)

-- Used by UDF below
CREATE VIEW Tree (node_id, parent)
AS
SELECT emp_id, emp_manager_id
FROM Employees

/*
Here's a UDF that will give you a depth-first traversal of the tree
whose root node is provided.
The nodes visited are numbered consecutively starting from a given
starting value, which is 1 by default.
*/
CREATE FUNCTION DepthFirstTraversal
(@root_node INT, @traversal_num_start INT = 1)
RETURNS @visited_nodes TABLE
(node_id INT NOT NULL UNIQUE,
traversal_num INT NOT NULL PRIMARY KEY
CHECK (traversal_num >= 1),
level INT NOT NULL CHECK (level >= 0))
AS
BEGIN
-- Level in tree, where the root node is at level 0
-- Nodes numbered with consecutive numbers reflecting
-- depth-first order of traversal
IF EXISTS (SELECT * FROM Tree WHERE node_id = @root_node)
BEGIN
DECLARE @level INT, @traversal_num INT
SELECT @level = 0,
@traversal_num = @traversal_num_start

-- Nodes traversed
INSERT INTO @visited_nodes (node_id, traversal_num, level)
SELECT node_id, @traversal_num, @level
FROM Tree
WHERE node_id = @root_node

-- Nodes to traverse
DECLARE @unvisited_nodes TABLE
(node_id INT NOT NULL PRIMARY KEY,
level INT NOT NULL CHECK (level > 0))
SELECT @level = 1
INSERT INTO @unvisited_nodes (node_id, level)
SELECT T.node_id, @level
FROM @visited_nodes AS V
INNER JOIN
Tree AS T
ON T.parent = V.node_id

WHILE EXISTS (SELECT * FROM @unvisited_nodes)
BEGIN
DECLARE @parent_node INT
SELECT @parent_node = T.node_id,
@level = L.level
FROM (SELECT MAX(level) AS level
FROM @unvisited_nodes) AS L
INNER JOIN
Tree AS T
ON T.node_id = (SELECT MIN(node_id)
FROM @unvisited_nodes
WHERE level = L.level)

DELETE FROM @unvisited_nodes
WHERE node_id = @parent_node AND
level = @level

SELECT @traversal_num = @traversal_num + 1
INSERT INTO @visited_nodes (node_id, traversal_num, level)
VALUES (@parent_node, @traversal_num, @level)

INSERT INTO @unvisited_nodes (node_id, level)
SELECT node_id, @level + 1
FROM Tree
WHERE parent = @parent_node
END
END
RETURN
END

/*
UDF to traverse multiple trees in depth-first order but applying
consecutive traversal numbering across all.
*/
CREATE FUNCTION DepthFirstTraversalAllTrees ()
RETURNS @visited_nodes TABLE
(node_id INT NOT NULL UNIQUE,
traversal_num INT NOT NULL PRIMARY KEY
CHECK (traversal_num >= 1),
level INT NOT NULL CHECK (level >= 0))
AS
BEGIN
DECLARE @root_nodes TABLE
(node_id INT NOT NULL PRIMARY KEY)
DECLARE @current_root_node INT, @current_traversal_num INT
INSERT INTO @root_nodes (node_id)
SELECT node_id
FROM Tree
WHERE parent IS NULL
SELECT @current_root_node = MIN(node_id), @current_traversal_num = 1
FROM @root_nodes
WHILE @current_root_node IS NOT NULL
BEGIN
INSERT INTO @visited_nodes (node_id, traversal_num, level)
SELECT node_id, traversal_num, level
FROM DepthFirstTraversal(@current_root_node, @current_traversal_num)
SELECT @current_root_node = MIN(node_id)
FROM @root_nodes
WHERE node_id > @current_root_node
SELECT @current_traversal_num = MAX(traversal_num) + 1
FROM @visited_nodes
END
RETURN
END

-- Sample data
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES(1, 'Anthony', 'Manager of IT', NULL)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (5, 'Charles', 'Business Analyst', 1)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (20, 'Denys', 'B.An. Trainee', 5)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (50, 'Albert', 'B.An. Trainee', 5)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (9, 'Cindy', 'Data Administrator', 1)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (56, 'Helen', 'D.A. Trainee', 9)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (6, 'Marcus', 'Manager of Accounting', NULL)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (22, 'Steve', 'Accountant', 6)
INSERT INTO Employees (emp_id, emp_name, emp_function, emp_manager_id)
VALUES (70, 'Fred', 'Accountant', 6)

-- Return all trees, with appropriate level indentation, by giving
-- nodes of each tree in depth-first order
DECLARE @level_indentation INT
SET @level_indentation = 5
SELECT REPLICATE(' ', @level_indentation * D.level) +
CAST(E.emp_id AS VARCHAR) AS emp_id,
E.emp_name,
E.emp_function,
E.emp_manager_id
FROM DepthFirstTraversalAllTrees() AS D
INNER JOIN
Employees AS E
ON E.emp_id = D.node_id
ORDER BY D.traversal_num ASC

emp_id emp_name emp_function emp_manager_id
1 Anthony Manager of IT NULL
5 Charles Business Analyst 1
20 Denys B.An. Trainee 5
50 Albert B.An. Trainee 5
9 Cindy Data Administrator 1
56 Helen D.A. Trainee 9
6 Marcus Manager of Accounting NULL
22 Steve Accountant 6
70 Fred Accountant 6

Regards,
jag

[Toralf Kirsten]

Hi,
here a question to query data recursively from a table (unfortunately
I'm not so familar with it)
there is a table test (a integer, b integer, c integer) containing the
following data

a | b | c
---------
1 | 1 | 2
1 | 2 | 3
1 | 3 | 4

i'd like to have the following output:

a | b
-----
1 | 1
1 | 2
1 | 3
1 | 4

i tried the following sql statement

with z(a, b) as
((select a, b
from test)
union all
(select test.a, test.b
from z, test
where z.b=test.c))
select * from z

but it doesn't really the output which i want. Any ideas?
Thanks, Toralf

[Knut Stolze]

Toralf Kirsten <tkirsten@izbi.uni-leipzig.de> wrote:

> Hi,
> here a question to query data recursively from a table (unfortunately
> I'm not so familar with it)
> there is a table test (a integer, b integer, c integer) containing the
> following data
>
> a | b | c
> ---------
> 1 | 1 | 2
> 1 | 2 | 3
> 1 | 3 | 4
>
> i'd like to have the following output:
>
> a | b
> -----
> 1 | 1
> 1 | 2
> 1 | 3
> 1 | 4
>
> i tried the following sql statement
>
> with z(a, b) as
> ((select a, b
> from test)
> union all
> (select test.a, test.b
> from z, test
> where z.b=test.c))
> select * from z
>
> but it doesn't really the output which i want. Any ideas?

What are the actual semantics of your query? I assume the following:

The column "c" represents something that is dependent from the column "b",
i.e. the following relations exist 1->2, 2->3, 3->4. Do you also have the
column "a" to define the start for the dependencies or is this some sort of
grouping??

To get your result, a query like this could do if I got this sort of right
with the dependency thingy:

WITH z(a, b) AS
( SELECT a, b
FROM test
UNION ALL
SELECT test.a, test.c
FROM z, test
WHERE z.b = test.b )
SELECT DISTINCT *
FROM z

This might or might not be what you have in mind. So getting a description
could help to come up with a more adequate solution.


--
Knut Stolze
Information Integration
IBM Germany / University of Jena

[Toralf Kirsten]

Hi Knut,
thank you for your fast response.

So getting a description

> could help to come up with a more adequate solution.

ok, that's right.

The table compromises the relationships between two nodes of several
connected graphs. Field a of the table represents the graph id, field b
and c represent two connected node id's.
For a special case, I need all nodes (b, c) for a given graph (a) in a
simple list. That's why I tried to query the table recursively. Do think
there is another / better way to do it?

The query returns only
a | b
-----
1 | 1
1 | 2
1 | 3

without the last node 4.

Do you have an idea what's wrong.
Thanks Toralf

[Knut Stolze]

Toralf Kirsten <tkirsten@izbi.uni-leipzig.de> wrote:

>> So getting a description
>> could help to come up with a more adequate solution.

> ok, that's right.
>
> The table compromises the relationships between two nodes of several
> connected graphs. Field a of the table represents the graph id, field b
> and c represent two connected node id's.
> For a special case, I need all nodes (b, c) for a given graph (a) in a
> simple list. That's why I tried to query the table recursively. Do think
> there is another / better way to do it?
>
> The query returns only
> a | b
> -----
> 1 | 1
> 1 | 2
> 1 | 3
>
> without the last node 4.

I see your problem. It would actually be a bit worse if your graph consists
of multiple, disconnected subgraphs.

You could either use the recursive query I gave in te other post as it
should return the result you want, or you use a UNION operator like this:

SELECT a, b
FROM test
UNION
SELECT a, c
FROM test

Please note that UNION will eliminate duplicates. I guess that this should
be simpler than the recursive query for DB2.

You can also try if the following query gives you better performane (in case
performance is an issue for you):

SELECT a, b
FROM test
UNION ALL
SELECT a, c
FROM test
WHERE (a, c) NOT IN ( SELECT a, b
FROM test )

--
Knut Stolze
Information Integration
IBM Germany / University of Jena