SQL Server Forums
Profile | Register | Active Topics | Members | Search | Forum FAQ
 
Register Now and get your question answered!
Username:
Password:
Save Password
Forgot your Password?

 All Forums
 SQL Server 2000 Forums
 SQL Server Development (2000)
 Hierarchies (with a twist)
 New Topic  Reply to Topic
 Printer Friendly
Author Previous Topic Topic Next Topic  

dsetzer
Starting Member

USA
31 Posts

Posted - 01/16/2001 :  14:41:00  Show Profile  Visit dsetzer's Homepage  Send dsetzer an AOL message  Reply with Quote
The topic of hierarchies has been beaten with an ugly stick, but, there's something that I've been trying to figure out.

The traditional hierarchy is that a child node is only a child node of a single parent, but, if you think about a corporate heirarchy from a regional/departmental standpoint you end up with a tree like:

East
| Atlanta
| | Legal
| | | IS
| | | Development
| | Brokers
| | | IS
| Boston
| | Admin.
| | | Development


Where an accounting report would be "What was the spending for all 'Development' departments in the East region?"

I've come up with the following DB structures, but, I don't know how to use it effectively:

TABLE: tblHierElement
HierID HierDescr HierLevel
------ --------- ---------
1 East 0
2 Atlanta 1
3 Boston 1
4 Legal 2
5 Broker 2
6 Admin. 2
7 IS 3
8 Development 3

TABLE: tblHierRelation
relID rel_hierID parent_relID
----- ---------- ------------
1 1 0
2 2 1
3 4 2
4 7 3
5 8 3
6 5 2
7 7 6
8 3 1
9 6 8
10 8 9


I would then store the relID for each order for the East/Boston/Admin/Development.

Should I be storing the AND'd ID's in a field? (.1.2.3.)? I've written a view that takes these 2 tables and gives me a flat recordset of (hierID, hierDescr, hierLevel, parent_hierID) but it doesn't shed any light on the hierarchy path something is (the difference between east/boston/admin/development and east/atlanta/legal/development).

Any ideas are greatly appreciated.

robvolk
Most Valuable Yak

USA
15636 Posts

Posted - 01/16/2001 :  16:21:19  Show Profile  Visit robvolk's Homepage  Reply with Quote
I was just thinking about this (really, I'm not kidding) and what I came up with was an extra field that stored the lineage, or hierarchy path.

My table is the generic Employee-Boss layout. I added a Depth field, like your HierLevel, and a Lineage field, which is varchar(255). The only thing is that I am storing lineage as varchar data, because my values are varchar, not numeric. If you don't mind doing the conversion, you might be able to use something like this.

Every Employee is unique (primary key). Boss cannot be Null, so the guy who is the top dog is his own boss (Employee=Boss). You'd change this to HierLevel=0.

Here is my procedure to recalculate the hierarchy/lineage:

UPDATE people set depth=0, lineage=NULL
UPDATE people set depth=1, lineage="\" where Employee=Boss
WHILE EXISTS (SELECT * FROM people WHERE Depth=0)
UPDATE P set P.depth=B.Depth+1, P.Lineage=B.Lineage+P.Boss+"\"
FROM People AS P INNER JOIN People AS B ON (P.Boss=B.Employee)
WHERE B.Depth>0 AND B.Lineage Is Not Null AND P.Depth=0


The first line clears everyone's depth and lineage. The second line updates the top boss, setting him at depth=1 and lineage="\", or root. The WHILE loop looks for anyone who is still depth=0 and will stop when they're all updated. The last line updates each employee by incrementing their depth to their boss' depth+1, and takes their boss' lineage (his boss or bosses) and adds THEIR boss to it. I use a delimiter "\" to separate each step of the lineage, so this would work with numbers as well.

The first time the loop runs, it only updates the people who report to the top guy. The second time the loop runs, it update THEIR employees, and so on down to the leaf level, which are the poor shmucks who don't have anybody working for them.

The nice thing is I only have to keep an employee's immediate boss logged. Any time I update someone's boss I rerun this procedure to redo the entire hierarchy. I could actually include this in an UPDATE trigger. (hmmmmmmm, I think I will now!)

Now, let's say I want all of someone's (Joe Blow) subordinates, no matter how far down they are:

SELECT * from people WHERE Lineage Like '%Joe Blow%'

Now I want all of Joe Blow's superiors:

DECLARE @line varchar(255)
SELECT @line=Lineage FROM people WHERE Employee='Joe Blow'
SELECT * FROM people WHERE CharIndex(Employee,@line)<>0


I haven't worked out all of the formulas to select entire divisions, etc. but it's pretty straightforward. Let me know if this works or if you need help. I hope to work out this whole thing and maybe present it here as an article, so keep your eyes peeled.

Go to Top of Page

dsetzer
Starting Member

USA
31 Posts

Posted - 01/16/2001 :  18:44:06  Show Profile  Visit dsetzer's Homepage  Send dsetzer an AOL message  Reply with Quote
I found an article that expanded on the Books Online "Expanding Hierarchies" section. It provided a sp that I've been able to work with, modify and change that supports what I need. I give it a top level relationship ID and it gives me all lower hierarchies. I can then filter that based on relationID, hierarchy ID or anything else that I want.


create proc ap_getDescendants @startRelID int = 0
as

set nocount on

declare @nLevel int,
@current_relID int

create table #stack (nLevel int, relID int)
create table #hierarchy (relID int, parent_relID int, hierID int, hasChild bit)

if @startRelID = 0
begin
select top 1 @nLevel = 1, @current_relID = relID from tblHierRelation where parent_relID = 0

insert into #stack (nLevel, relID)
select @nLevel, relID from tblHierRelation where parent_relID = 0
end
else
begin
select top 1 @nLevel = 1, @current_relID = relID from tblHierRelation where relID = @startRelID
insert into #stack (nLevel, relID)
values (@nLevel, @current_relID)
end

while (@nLevel > 0)
begin
if exists (select 'true' from #stack where nLevel = @nLevel)
begin
-- pop one record
select top 1 @current_relID = relID from #stack where nLevel = @nLevel
delete from #stack where relID = @current_relID and nLevel = @nLevel
-- pop one record

-- insert the record into hierarchy table
insert into #hierarchy (relID, parent_relID, hierID, hasChild)
select @current_relID, hr.parent_relID, hr.rel_hierID, case
when exists (select 'true' from tblHierRelation childHR where childHR.parent_relID = @current_relID) then 1
else 0
end
from tblHierRelation hr where hr.relID = @current_relID

-- insert leaf records (ones with no children) directly into #hierarchy table
insert into #hierarchy (relID, parent_relID, hierID, hasChild)
select hr.relID, hr.parent_relID, hr.rel_hierID, 0
from tblHierRelation hr left outer join tblHierRelation hrB on hr.relID = hrB.parent_relID
where hr.parent_relID = @current_relID and hrB.relID IS NULL

-- insert non-leaf (ones that have some children) into #stack table
insert into #stack (nLevel, relID)
select @nLevel + 1, hr.relID
from tblHierRelation hr inner join tblHierRelation hrB on hr.relID = hrB.parent_relID
where hr.parent_relID = @current_relID

-- if any leaf(s) found increment the @nLevel
if @@rowcount > 0
begin
select @nLevel = @nLevel + 1
end
end
else -- if exists (select 'true' from #stack where nLevel = @nLevel)
begin
select @nLevel = @nLevel - 1
end
end -- while (@nLevel > 0)


select relID, parent_relID, hierID, hasChild
from #hierarchy

drop table #hierarchy
Go to Top of Page

irresistableflavor
Starting Member

2 Posts

Posted - 03/03/2005 :  15:21:43  Show Profile  Reply with Quote
I am trying to figure out how to display a family tree of my member
management/replication system and I am having much trouble understanding
how to put the sql query together to Re-Build all the users lineage fields!

Mainly it's the part where there is a WHILE loop inside of the sql query!!!

Also, I have all user data inside of one table so I guess there would be no
need to do a INNER JOIN which is something I was just learning now.

Apparently it is used to join one table to another table.

I think the only fields that would come into play
would be the username, sponsor, lineage field
and mabey the id field would count too.

Here's the structure of my table:
==================================
TABLE: $user_info_table
id username   sponsor  lineage
-- --------   -------  -------
1  flavor              
2  licker     flavor   flavor
3  loser      licker   flavor/licker
4  lamer      licker   flavor/licker
5  spunky     flavor   flavor 
6  spanky     spunky   flavor/spunky
7  sporky     spanky   flavor/spunky/spanky
8  spyder     sporky   flavor/spunky/spanky/sporky
======================================
The Tree I'm Trying To Create Would Look Like This:
======================================
+->flavor
      |
      +->licker
      |     |
      |     +->loser
      |     |
      |     +->lamer
      |
      +->spunky
            |
            +->spanky
                  |
                  +->sporky
                        |
                        +->spyder
==================================
Please tell me I can do this with one table;-]!

I would imagine it would be possible if the
query could call on it's own table again.

I just have no idea how to write it.

I know html+css+js+php+mysql

(well, basic mysql)

Peace~in~it;-]
irresistableflavor
=-=-=-=-=-=-=-=-=-=-
P.S. I ditched the depth
field because I'm hoping the (/)
slashes could be counted to get that.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Edited by - irresistableflavor on 03/03/2005 16:09:19
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 03/03/2005 :  16:37:00  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
Well when my site comes back up take a look at:
http://www.seventhnight.com/treestructs.asp

I've got a very detailed example out there.
To be fair, there is an article here too
http://www.sqlteam.com/item.asp?ItemID=8866

I think someone else has another one too, but I can't find it right now...


Corey

"If the only tool you have is a hammer, the whole world looks like a nail." - Mark Twain
Go to Top of Page

irresistableflavor
Starting Member

2 Posts

Posted - 03/04/2005 :  14:51:32  Show Profile  Reply with Quote
Hello SeventhNight,

I was looking at this tutorial u gave me...
http://www.sqlteam.com/item.asp?ItemID=8866

and I found this part about half way down the page:

quote:
The first thing to do is to populate the parent nodes, which is unecessary if you use a single table, but it's easy to do in any case:

I found this interesting because I only have one table in my case!

So, what I would like to do instead of having nodes is to just
build it off of a username/sponsor relationship where sponsor
is the username of the person who sponsored the person;-]

So, in order to populate the lineage fields I would
need to do some kind of sql UPDATE query which
is the place I come to a screeching halt @.

As for ditching the depth field I think
it could be done if a slash was left
on either side of the lineage
path which would create
the correct number
levels down for
each user;-]

Any Thoughts?

Peace~in~it;-]
irresistableflavor...
=-=-=-=-=-=-=-=-=-=-=-
P.S. Extinction of the Stick People:
Go to Top of Page

rschaeferhig
Starting Member

USA
2 Posts

Posted - 05/19/2005 :  14:20:53  Show Profile  Visit rschaeferhig's Homepage  Reply with Quote
I'm lost. I tried to implement Rob Volk's code against a table of Employees. Each Employee has and ID and a ManagerID (their manager). I've been able to get the code Rob posted working, but when I select out the results and sort by Lineage I essentially end up with the top guy, the second level folks, then all the other folks in sort of ridiculous sequences (I'm sure it makes sense to SQL, but not to me...). I added the current node to the lineage and it works perfectly to display each level beneath the manager above that level, i.e. Fred and Jim->Bob->Joe then George and Jane->Ann->Joe. You can read it as a tree and print an appropriately indented report.

EXCEPT!!!

The end-node people need to be sorted by name. Since their lineage now includes their own node they're all sorted by their node regardless of name order. What would I need to do to the tree to recurse it and set a flag (i.e. EndNode) for all the poor schmucks at the bottom? If I can find them then I can trim their lineage back one level and sort them by name like my customer wants.

Here's the code I have so far to produce the Tree:
Truncate Table Tree

Insert into Tree (EmployeeID)
select '225663' as ID

Insert into Tree (EmployeeID)
Select ID from Employees where Status<>2 and Supv_ID is not null

UPDATE T SET T.ParentNode=P.Node
FROM Tree as T
INNER JOIN Employees E ON T.EmployeeID=E.ID
INNER JOIN Employees B ON E.Supv_ID=B.ID
INNER JOIN Tree P ON B.ID=P.EmployeeID

UPDATE Tree set depth=0, lineage=NULL
UPDATE Tree set depth=1, lineage='\100\' where EmployeeID='225663'

WHILE EXISTS (SELECT * FROM Tree WHERE Depth=0)
UPDATE P set P.depth=B.Depth+1,
P.Lineage=B.Lineage+cast(P.Node as varchar(6))+'\'
FROM Tree AS P INNER JOIN Tree AS B ON (P.ParentNode=B.Node)
WHERE B.Depth>0 AND B.Lineage Is Not Null AND P.Depth=0

Any ideas on an additional WHERE clause to spin the tree again and find the end-node rows would be greatly appreciated. I've been looking at this so long I can't even see it anymore.
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 05/19/2005 :  15:43:22  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
Well if you are just trying to identify the end nodes, all you need is to figure out those records that do not have 'children'.

This should be the set of 'end nodes':

Select * From tree A
Where not exists(Select * From tree B Where parentNode = A.node)


As far as Alphabatizing, I reorder the entire table alphabetically with an orderId column.

I then use the orderId as the lineage data src. I still have to use parentnode and node to determine relationships so the query is a bit larger, but manageable.

Click the image below to see an example of an alphabatized multiparent tree structure (my photo categories)

Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.
Go to Top of Page

DustinMichaels
Constraint Violating Yak Guru

464 Posts

Posted - 05/19/2005 :  16:28:49  Show Profile  Reply with Quote
We used this article as a guide to creating a page hierarchy for our content management system and it has worked quite well.

http://www.sqlteam.com/item.asp?ItemID=8866

Dustin Michaels
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 05/19/2005 :  16:33:22  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
they are already referencing that.

and hopefully they've looked at mine too (http://www.seventhnight.com/treestructs.asp)

Corey

Secret Service Agent: Mr. President, you're urinating on me.
President Lyndon Johnson: I know I am. It's my prerogative.
Go to Top of Page

rschaeferhig
Starting Member

USA
2 Posts

Posted - 05/20/2005 :  07:09:45  Show Profile  Visit rschaeferhig's Homepage  Reply with Quote
That's pretty much the query I came up with 7th. I got the whole thing working exactly the way the customer wants it. Took some work but hopefully they'll like it. And yes, I did read your article.

Thanks everyone for all the help.
Go to Top of Page

intellisoftwares
Starting Member

Singapore
1 Posts

Posted - 01/21/2006 :  00:26:17  Show Profile  Visit intellisoftwares's Homepage  Reply with Quote
I have used the method as suggested by dsetzer (using stored procedure). I want to be able to use output of stored procedure in a select statements so that I can join to other tables and retrieve other information.
For example SELECT * FROM (EXEC ap_getDescendants 1).

This is not a valid statement in SQL server. I cannot convert it to UDF or view as both types cannot use temp tables. Is there any other way I can obtain hierarchy information for any given member and be able to use it in a select statement directly?

I do not want to use Lineage column coz I need 24452 characters long string to save lineage of bottom most node in the hierarchy and this hierarchy is growing every day.

Thanks for your help in advance.

Cheers,

Best MLM Software-Intelli Pyramid
http://www.intellipyramid.com/
Go to Top of Page

blindman
Flowing Fount of Yak Knowledge

USA
2365 Posts

Posted - 01/21/2006 :  17:30:52  Show Profile  Reply with Quote
Change ap_getDescendants from a stored procedure to a user-defined table function. Then you can reference it like this:

SELECT * FROM dbo.ap_getDescendants(1)
Go to Top of Page

Seventhnight
Flowing Fount of Yak Knowledge

USA
2878 Posts

Posted - 01/23/2006 :  08:42:31  Show Profile  Visit Seventhnight's Homepage  Reply with Quote
quote:

I do not want to use Lineage column coz I need 24452 characters long string to save lineage of bottom most node in the hierarchy and this hierarchy is growing every day.



how many levels does this represent??

oh and you could also execute the sp to a table... though it is a 2 step process

Insert Into #SomeDefinedTable
Exec ap_getDescendants 1

Corey

Co-worker on children "...when I have children, I'm going to beat them. Not because their bad, but becuase I think it would be fun ..."
Go to Top of Page

sshelper
Posting Yak Master

216 Posts

Posted - 04/29/2006 :  00:42:42  Show Profile  Visit sshelper's Homepage  Reply with Quote
This may be an old thread but since this is part of the "sticky" FAQ list, might as well contribute the following links which deal with hierarchical table structures:

http://www.sql-server-helper.com/functions/get-tree-path.aspx
http://www.sql-server-helper.com/functions/get-tree-node-level.aspx

SQL Server Helper
http://www.sql-server-helper.com
Go to Top of Page
  Previous Topic Topic Next Topic  
 New Topic  Reply to Topic
 Printer Friendly
Jump To:
SQL Server Forums © 2000-2009 SQLTeam Publishing, LLC Go To Top Of Page
This page was generated in 0.14 seconds. Powered By: Snitz Forums 2000