SQL Clone
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets


Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets

Author
Message
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)

Group: General Forum Members
Points: 87198 Visits: 41113
Thanks for the feedback. Basically, great minds think alike because all I did was make a "mapping" table. You could certainly incorporate that into your original employee table but I didn't want to lock the whole table with the update/table scan that would occur. I didn't know how big your table would be.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
LordHz
LordHz
Forum Newbie
Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)Forum Newbie (4 reputation)

Group: General Forum Members
Points: 4 Visits: 21
Jeff,

Not putting that back in the original table (mines not employee), I'm just maintaining the mapping in your hierarchy table. My thought is to make your stored procedure more generic, so I can simply pass in the table name, Id/ParentId and the sort field(s) and use dynamic SQL to create a the sorted mapping table. That would then update the rgt/lft extends (your bowers) back into the original table. That way the less knowledgeable developers could implement without having to modify the stored procedure. At least that's my thought, haven't implemented it yet. Most of our hierarchies are in the under 100k row range, most under 10k. We do a lot of hierarchies, product, geo, object, person, etc. This update has provided some great brain food.:-D

Thanks again,
Matthew
Tom Thomson
Tom Thomson
SSChampion
SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)SSChampion (14K reputation)

Group: General Forum Members
Points: 14402 Visits: 12213
Hi Jeff, great article.

I have one quibble: terminology; even an old relic like me knows that "best bower" and "small bower" have been superseded by "starboard bower" and "port bower" but I've never before heard or seen "right bower" and "left bower". :-D

Tom

Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)

Group: General Forum Members
Points: 87198 Visits: 41113
LordHz (3/14/2013)
Jeff,

Not putting that back in the original table (mines not employee), I'm just maintaining the mapping in your hierarchy table. My thought is to make your stored procedure more generic, so I can simply pass in the table name, Id/ParentId and the sort field(s) and use dynamic SQL to create a the sorted mapping table. That would then update the rgt/lft extends (your bowers) back into the original table. That way the less knowledgeable developers could implement without having to modify the stored procedure. At least that's my thought, haven't implemented it yet. Most of our hierarchies are in the under 100k row range, most under 10k. We do a lot of hierarchies, product, geo, object, person, etc. This update has provided some great brain food.:-D

Thanks again,
Matthew


Hi Matthew,

Sorry I missed this post. That's some great feedback and a great idea. If you get the chance, please post back how your suggestion worked out for you. Shoot... it's such a good idea, you might even want to write an article about it.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)

Group: General Forum Members
Points: 87198 Visits: 41113
L' Eomot Inversé (8/24/2013)
Hi Jeff, great article.

I have one quibble: terminology; even an old relic like me knows that "best bower" and "small bower" have been superseded by "starboard bower" and "port bower" but I've never before heard or seen "right bower" and "left bower". :-D


BWAA-HAAA!!!! I always knew you were a salty old dog! :-D Thanks for the feedback, Tom.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
ashley.wardell
ashley.wardell
Valued Member
Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)Valued Member (57 reputation)

Group: General Forum Members
Points: 57 Visits: 194
this is my stab at nested set. i generate on every set of the table.
i am looking to refactor and trim it down at some point.
if this is any help to anyone enjoy
or anyone wants to refactor it a bit more i would appreciate it


CREATE TABLE [dbo].[Organisation](
[OrganisationId] [int] IDENTITY(1,1) primary key NOT NULL,
[ParentId] [int] NULL,
[MinNest] [int] NULL,
[MaxNest] [int] NULL,
[Name] [varchar](50) NULL
) ON [PRIMARY]

GO

/****** Object: StoredProcedure [dbo].[UpdateOrgHierarchy] Script Date: 11/11/2013 14:17:12 ******/
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
ALTER PROCEDURE [dbo].[UpdateOrgHierarchy]
AS
BEGIN
begin transaction

SELECT top 1 *
into #tmp
from dbo.Organisation with (TABLOCKX)

;WITH orgCTE2 AS (
SELECT OrganisationId,
OrganisationId as CurrentOrgId,
1 as Total
FROM dbo.Organisation e
where ParentId IS NULL
UNION ALL
SELECT parent.OrganisationId,
e.OrganisationId as CurrentOrgId,
1 as Total
FROM dbo.Organisation e
INNER JOIN orgCTE2 parent ON parent.CurrentOrgId = e.ParentId
UNION ALL
SELECT e.OrganisationId,
e.OrganisationId as CurrentOrgId,
1 as Total
FROM dbo.Organisation e
INNER JOIN orgCTE2 parent ON parent.CurrentOrgId = e.ParentId
) , orgCTE3 AS (
select OrganisationId,
count(*) as [count]
from (select distinct OrganisationId, CurrentOrgId from orgCTE2) a
where Organisationid != CurrentOrgId
group by OrganisationId
) , orgCTE AS (
SELECT OrganisationId as TopOrgId,
OrganisationId as OrganisationId,
ParentId as ParentId,
1 as depth
FROM dbo.Organisation
UNION ALL
SELECT child.TopOrgId,
e.OrganisationId as OrganisationId,
e.ParentId,
depth + 1 as depth
FROM dbo.Organisation e
INNER JOIN orgCTE child ON child.parentId = e.OrganisationId
), orgCTE4 AS (
SELECT OrganisationId,
ParentId,
cast(null as INT) as parentOrganisationId,
OrganisationId as superparentOrganisationId,
',' + cast(OrganisationId as varchar(max)) + ',' as idstack,
1 as depth
FROM dbo.Organisation
WHERE parentid IS NULL
UNION ALL
SELECT e.OrganisationId,
e.ParentId,
parent.organisationid as parentOrganisationId,
superparentOrganisationId,
idstack + cast(e.OrganisationId as varchar(max)) + ',' as idstack,
depth + 1 as depth
FROM dbo.Organisation e
INNER JOIN orgCTE4 parent ON parent.organisationid = e.parentId
)
UPDATE org
set minNest = ((row_num-1) * 2) + 1 - (d-1),
maxNest = ((row_num-1) * 2) + 1 - (d-1)+(cnn*2)-1
from dbo.Organisation org
join (select c.*, e.maxdepth - c.depth + 1 as dep, isnull(par.[count] + 1,1) cnn, st.depth as d,
row_number() OVER (PARTITION BY 1 ORDER BY idstack) as row_num
from orgCTE c
join orgCTE4 st
on c.OrganisationId = st.OrganisationId
LEFT JOIN orgCTE3 par
on c.OrganisationId = par.OrganisationId
JOIN (
select max(depth) maxdepth, toporgid
from orgCTE c
group by toporgid ) e
on c.toporgid = e.toporgid
where c.depth = 1) ln
on org.OrganisationId = ln.OrganisationId

COMMIT transaction

END


dinson
dinson
Forum Newbie
Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)

Group: General Forum Members
Points: 3 Visits: 2
excellent article. But i got a question. I hav a tree structure which i want to store in a DB. The structure is not fixed and can change, ie, nodes can b added, deleted or renamed.

Using your article, i find that i can navigate and extract data from such a structure very effeciently. But how do i deal with inserting and deleting the nodes into the DB table?

I am using this from a C# application and my DB is MySQL.
My tree structure concerns a document archive that is full of old documents that are old enough to get damaged if accessed repeatedly and so need to be scanned and put into the DB. The arrangement of the documents follow a tree structure i.e.:

Archive root>>Room no>>Cabin no>>Drawer no>>category

the first 3 levels i.e. room, cabin and drawer remain constant but the category can have many sub levels. Files can b stored directly under category level as well as under any sub level of category, and so i am using a tree structure to store this location info. What i am planning to do is to create the tree with the first 3 levels and then allow the client to put up further nodes as and when they need. Then they can upload scanned documents to the appropriate places.
The file upload to any level is OK as far as that level/sub category is already defined and stored properly in the DB and can be accessed properly. To make navigation and search of documents from this tree effective and fast i wanted to first of all speed up the tree navigation itself and thus came upon your article. The navigation using your method will be fast even if there are too many sub-levels and files, but how do I manage the insert and delete of the various sub-levels when using your method? Do I need to calculate the Left and Right bower every time a node is inserted or deleted?

I want to do this right from the beginning because i know the amount of data they have is humongous. The DB will slow down because of this and thus the app i am making would slow down too...
Jeff Moden
Jeff Moden
SSC Guru
SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)SSC Guru (87K reputation)

Group: General Forum Members
Points: 87198 Visits: 41113
@Dinson,

If done correctly, there won't be any slowdown in the DB. The example I used was a million row example and it all worked in under a minute.

The key is to establish the rules early. For example, can a document exist under more than one category? To be honest, I'd make category (or categories) an attribute (or attributes) of the document rather than storing categories in a hierarchy of locations. In all honesty, I can see two hierarchies here... one for location and one for categorization. Document IDs shouldn't be stored as a subset of categories. I'd have a document table and a bridging table that contains document IDs and the IDs of the categories that a document belonged to and there would be nothing hierarchical about that.

--Jeff Moden

RBAR is pronounced ree-bar and is a Modenism for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
princektd.x
princektd.x
Forum Newbie
Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)

Group: General Forum Members
Points: 1 Visits: 2
thnx jeff.
OK, that makes sense. So, i leave category out of the document table.
I will try to set the bower calculations as a trigger on insert/update...


Does that sound ok?
Jeztagab
Jeztagab
Forum Newbie
Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)Forum Newbie (9 reputation)

Group: General Forum Members
Points: 9 Visits: 44
Can I use these method to resolve the problem below? Please help

My problem here is how to identity and select a patients service date. A service date could be admission date(hospital), discharge date(hospital), CBC taken date, CBC result date, xray taken date, xray result read date etc.. . Each date is paired and are reconciled thru a similar account number. lets say an admission date is always paired with discharge date and so both dates will have similar account number, so is CBC taken date paired with CBC result date. This might happen in the same day but the time will be different. However we are receiving the data in a format where we don't know what kind of service was performed, we only have the service date. so we are assuming that a patients earliest date is an admission date and whatever date that has a similar account number is the discharge date. I want to select all patients record that contains admission date and discharge date base on the assumption that the earliest date is an admission date and the other date on that accountnumber is the discharge date. whatever dates that fall in between the admission date and discharge date will be ignored. However a patient could be admitted and discharge from the hospital multiple times a year. so the earliest date after the first discharge date will also be considered as a 2nd admission date.. so on and so forth the cycle continues..

example data..
memberid, accountnum, servicedate
1 , ABC11, 10/24/2013
1 , ABC12, 10/26/2013
1 , ABC13, 10/28/2013
1 , ABC12, 10/30/2013
1 , ABC13, 11/2/2013
1 , ABC11, 11/5/2013
1 , ABC14, 11/30/2013
1 , ABC15, 12/1/2013
1 , ABC16, 12/3/2013
1 , ABC17, 12/8/2013
1 , ABC17, 12/10/2013
1 , ABC16, 12/9/2013
1 , ABC15, 12/12/2013
1 , ABC14, 12/11/2013

in these sample data the expected data to be return is:

memberid, accountnumber, servicedate
1, ABC11, 10/24/2013
1, ABC11, 11/5/2013
1, ABC14, 11/30/2013
1, ABC14, 12/11/2013

please help me . is this type of logic complex and be better implemented as a SQL CLR or recursive cte or tally table.. I could only manage to recover the first admission date and discharge date for each member...


;with cte1 as (
select memberid, acctnum, servicedate,
member_earliestdate = ROW_NUMBER()over(partition by memberid order by servicedate asc)
from patient_admitlog)

select * from
(select * from cte1 where member_earliestdate = 1)t1 join
cte1 on t1.acctnum = cte1. acctnum and t1.memberid = cte1.memberid
Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search