Hierarchical Query

I have a table representing a tree structure - self referencing table. For
any node, I need to traverse upwards until root and retreives all the
traversed nodes.
With SQL only, how could I do this? In Oracle, there is START WITH, CONNECT
BY clause to help me. What is the equivalence in sql server?Here is an alternative method
http://toponewithties.blogspot.com/
Roji. P. Thomas
Net Asset Management
https://www.netassetmanagement.com
"as" <none@.asgmeail.com> wrote in message
news:42928048$1_1@.rain.i-cable.com...
>I have a table representing a tree structure - self referencing table. For
> any node, I need to traverse upwards until root and retreives all the
> traversed nodes.
> With SQL only, how could I do this? In Oracle, there is START WITH,
> CONNECT
> BY clause to help me. What is the equivalence in sql server?
>|||See Itzik Ben-Gan's example
IF object_id('dbo.Employees') IS NOT NULL
DROP TABLE Employees
GO
IF object_id('dbo.ufn_GetSubtree') IS NOT NULL
DROP FUNCTION dbo.ufn_GetSubtree
GO
CREATE TABLE Employees
(
empid int NOT NULL,
mgrid int NULL,
empname varchar(25) NOT NULL,
salary money NOT NULL,
CONSTRAINT PK_Employees_empid PRIMARY KEY(empid),
CONSTRAINT FK_Employees_mgrid_empid
FOREIGN KEY(mgrid)
REFERENCES Employees(empid)
)
CREATE INDEX idx_nci_mgrid ON Employees(mgrid)
INSERT INTO Employees VALUES(1 , NULL, 'Nancy' , $10000.00)
INSERT INTO Employees VALUES(2 , 1 , 'Andrew' , $5000.00)
INSERT INTO Employees VALUES(3 , 1 , 'Janet' , $5000.00)
INSERT INTO Employees VALUES(4 , 1 , 'Margaret', $5000.00)
INSERT INTO Employees VALUES(5 , 2 , 'Steven' , $2500.00)
INSERT INTO Employees VALUES(6 , 2 , 'Michael' , $2500.00)
INSERT INTO Employees VALUES(7 , 3 , 'Robert' , $2500.00)
INSERT INTO Employees VALUES(8 , 3 , 'Laura' , $2500.00)
INSERT INTO Employees VALUES(9 , 3 , 'Ann' , $2500.00)
INSERT INTO Employees VALUES(10, 4 , 'Ina' , $2500.00)
INSERT INTO Employees VALUES(11, 7 , 'David' , $2000.00)
INSERT INTO Employees VALUES(12, 7 , 'Ron' , $2000.00)
INSERT INTO Employees VALUES(13, 7 , 'Dan' , $2000.00)
INSERT INTO Employees VALUES(14, 11 , 'James' , $1500.00)
GO
CREATE FUNCTION dbo.ufn_GetSubtree
(
@.mgrid AS int
)
RETURNS @.tree table
(
empid int NOT NULL,
mgrid int NULL,
empname varchar(25) NOT NULL,
salary money NOT NULL,
lvl int NOT NULL,
path varchar(900) NOT NULL
)
AS
BEGIN
DECLARE @.lvl AS int, @.path AS varchar(900)
SELECT @.lvl = 0, @.path = '.'
INSERT INTO @.tree
SELECT empid, mgrid, empname, salary,
@.lvl, '.' + CAST(empid AS varchar(10)) + '.'
FROM Employees
WHERE empid = @.mgrid
WHILE @.@.ROWCOUNT > 0
BEGIN
SET @.lvl = @.lvl + 1
INSERT INTO @.tree
SELECT E.empid, E.mgrid, E.empname, E.salary,
@.lvl, T.path + CAST(E.empid AS varchar(10)) + '.'
FROM Employees AS E JOIN @.tree AS T
ON E.mgrid = T.empid AND T.lvl = @.lvl - 1
END
RETURN
END
GO
SELECT empid, mgrid, empname, salary
FROM ufn_GetSubtree(3)
GO
/*
empid mgrid empname salary
2 1 Andrew 5000.0000
5 2 Steven 2500.0000
6 2 Michael 2500.0000
*/
/*
SELECT REPLICATE (' | ', lvl) + empname AS employee
FROM ufn_GetSubtree(1)
ORDER BY path
*/
"as" <none@.asgmeail.com> wrote in message
news:42928048$1_1@.rain.i-cable.com...
> I have a table representing a tree structure - self referencing table.
For
> any node, I need to traverse upwards until root and retreives all the
> traversed nodes.
> With SQL only, how could I do this? In Oracle, there is START WITH,
CONNECT
> BY clause to help me. What is the equivalence in sql server?
>|||Hi as,
Can you try the something like following which i implemented while working
on Hierarchical query (I converted this to a stored proc. This code example
is given in Books online, with little modification it worked fine for me.)
--Begin--
--
Accessing and Changing Relational Data
Expanding Hierarchies
Databases often store hierarchical information. For example, the following
data is a hierarchical representation of regions of the world. This
representation does not clearly show the structure implied by the data.
Parent Child
-- --
World Europe
World North America
Europe France
France Paris
North America United States
North America Canada
United States New York
United States Washington
New York New York City
Washington Redmond
This example is easier to interpret:
World
North America
Canada
United States
Washington
Redmond
New York
New York City
Europe
France
Paris
The following Transact-SQL procedure expands an encoded hierarchy to any
arbitrary depth. Although Transact-SQL supports recursion, it is more
efficient to use a temporary table as a stack to keep track of all of the
items for which processing has begun but is not complete. When processing is
complete for a particular item, it is removed from the stack. New items are
added to the stack as they are identified.
CREATE PROCEDURE expand (@.current char(20)) as
SET NOCOUNT ON
DECLARE @.level int, @.line char(20)
CREATE TABLE #stack (item char(20), level int)
INSERT INTO #stack VALUES (@.current, 1)
SELECT @.level = 1
WHILE @.level > 0
BEGIN
IF EXISTS (SELECT * FROM #stack WHERE level = @.level)
BEGIN
SELECT @.current = item
FROM #stack
WHERE level = @.level
SELECT @.line = space(@.level - 1) + @.current
PRINT @.line
DELETE FROM #stack
WHERE level = @.level
AND item = @.current
INSERT #stack
SELECT child, @.level + 1
FROM hierarchy
WHERE parent = @.current
IF @.@.ROWCOUNT > 0
SELECT @.level = @.level + 1
END
ELSE
SELECT @.level = @.level - 1
END -- WHILE
The input parameter (@.current) indicates the place in the hierarchy to
start. It also keeps track of the current item in the main loop.
The local variables used are @.level, which keeps track of the current level
in the hierarchy, and @.line, which is a work area used to construct the
indented line.
The SET NOCOUNT ON statement avoids cluttering the output with ROWCOUNT
messages from each SELECT.
The temporary table, #stack, is created and primed with the item identifier
of the starting point in the hierarchy, and @.level is set to match. The leve
l
column in #stack allows the same item to appear at multiple levels in the
database. Although this situation does not apply to the geographic data in
the example, it can apply in other examples.
In this example, when @.level is greater than 0, the procedure follows these
steps:
If there are any items in the stack at the current level (@.level), the
procedure chooses one and calls it @.current.
Indents the item @.level spaces, and then prints the item.
Deletes the item from the stack so it will not be processed again, and then
adds all its child items to the stack at the next level (@.level + 1). This i
s
the only place where the hierarchy table (#stack) is used.
With a conventional programming language, you would have to find each child
item and add it to the stack individually. With Transact-SQL, you can find
all child items and add them with a single statement, avoiding another neste
d
loop.
If there are child items (IF @.@.ROWCOUNT > 0), descends one level to process
them (@.level = @.level + 1); otherwise, continues processing at the current
level.
If there are no items on the stack awaiting processing at the current level,
goes back one level to see if there are any awaiting processing at the
previous level (@.level = @.level - 1). When there is no previous level, the
expansion is complete.
--End---
--
Regards,
Siva
"as" wrote:

> I have a table representing a tree structure - self referencing table. Fo
r
> any node, I need to traverse upwards until root and retreives all the
> traversed nodes.
> With SQL only, how could I do this? In Oracle, there is START WITH, CONNE
CT
> BY clause to help me. What is the equivalence in sql server?
>
>|||>> What is the equivalent in sql server? <<
The equivalent is a cursor becasue that what Oracle does under the
covers in their proprietary syntax. Instead:
1) Get a copy of TREES & HIERACHIES IN SQL from Amazon.com. There are
much better ways of modeling a tree.
2) Google for "Nested set model" in this newsgroup. There is no need
for procedural code.l|||Joe,
I would like to know your opinion about the approach discussed in
http://toponewithties.blogspot.com/ (Path Enumeration using Prime number
Products)
Regards
Roji
Roji. P. Thomas
Net Asset Management
https://www.netassetmanagement.com
"--CELKO--" <jcelko212@.earthlink.net> wrote in message
news:1116960769.637939.154330@.z14g2000cwz.googlegroups.com...
> The equivalent is a cursor becasue that what Oracle does under the
> covers in their proprietary syntax. Instead:
> 1) Get a copy of TREES & HIERACHIES IN SQL from Amazon.com. There are
> much better ways of modeling a tree.
> 2) Google for "Nested set model" in this newsgroup. There is no need
> for procedural code.l
>|||I wish I had seen this before finishing TREES & HIERARCHIES IN SQL.
The only problem I can see is the size of the primes as the trees get
larger, but we are living in a 64-bit world now. Since the math is
simple integer division and multiplication, the speed is probably
pretty good.
Random thought: if we give each node a prime in a general graph, then a
cycle|||Thanks Joe,
I am a happy man.
You can consider this for the next version of TREES & HIERARCHIES IN SQL :)
Roji. P. Thomas
Net Asset Management
https://www.netassetmanagement.com
"--CELKO--" <jcelko212@.earthlink.net> wrote in message
news:1117037337.540731.73370@.g14g2000cwa.googlegroups.com...
>I wish I had seen this before finishing TREES & HIERARCHIES IN SQL.
> The only problem I can see is the size of the primes as the trees get
> larger, but we are living in a 64-bit world now. Since the math is
> simple integer division and multiplication, the speed is probably
> pretty good.
> Random thought: if we give each node a prime in a general graph, then a
> cycle
>|||--CELKO-- wrote:
> I wish I had seen this before finishing TREES & HIERARCHIES IN SQL.
> The only problem I can see is the size of the primes as the trees get
> larger, but we are living in a 64-bit world now. Since the math is
> simple integer division and multiplication, the speed is probably
> pretty good.
Kendall Willets suggested this method on comp.databases.theory some
time ago.

> Random thought: if we give each node a prime in a general graph, then a
> cycle
Prime numbers set with "divided by" binary relation is a partial order.
More specifically it is a lattice. An arbitrary DAG can be embedded
into a lattice. However, the prime numbers encoding for graphs is
volatile. Adding a node into a graph would force to recalculate
encodings for large graph fragment. Plus, how to handle acyclic graphs?|||Mikito Harakiri wrote:
> --CELKO-- wrote:
> Kendall Willets suggested this method on comp.databases.theory some
> time ago.
>
> Prime numbers set with "divided by" binary relation is a partial order.
> More specifically it is a lattice. An arbitrary DAG can be embedded
> into a lattice. However, the prime numbers encoding for graphs is
> volatile. Adding a node into a graph would force to recalculate
> encodings for large graph fragment. Plus, how to handle acyclic graphs?
Could the access path be indexed? Imagine that we don't have this silly
64 bit limit and you are presented with a node encoded with a number
3107418240490043721350750035888567930037
3460228427
2754572016194882320644051808150455634682
9671723286
7824379162728380334154710731085019195485
2900733772
4822783525742386454014691736602477652346
609
(RSA-640) and are asked what are the ancestors. Can you answer that in
a reasonable amount of time.
I'm cheating of course, if the primes are small you can factor the
number reasonably fast. Still, what about the access path? For
comparison, in case of nested sets we are talking about index range
scan (at least one way).