Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase «««45678»»

Hierarchies on Steroids #1: Convert an Adjacency List to Nested Sets Expand / Collapse
Author
Message
Posted Thursday, March 14, 2013 5:19 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 8:35 AM
Points: 36,977, Visits: 31,494
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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1431301
Posted Thursday, March 14, 2013 6:59 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Wednesday, August 6, 2014 7:19 PM
Points: 4, Visits: 14
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.

Thanks again,
Matthew
Post #1431317
Posted Saturday, August 24, 2013 11:07 AM


SSCrazy Eights

SSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy EightsSSCrazy Eights

Group: General Forum Members
Last Login: Today @ 8:31 AM
Points: 8,707, Visits: 9,255
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".


Tom
Post #1488134
Posted Saturday, August 24, 2013 11:57 AM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 8:35 AM
Points: 36,977, Visits: 31,494
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.

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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1488139
Posted Saturday, August 24, 2013 12:00 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 8:35 AM
Points: 36,977, Visits: 31,494
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".


BWAA-HAAA!!!! I always knew you were a salty old dog! 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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1488140
Posted Monday, November 11, 2013 7:55 AM
SSC Rookie

SSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC RookieSSC Rookie

Group: General Forum Members
Last Login: Tuesday, December 17, 2013 8:15 AM
Points: 31, 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

Post #1513144
Posted Tuesday, January 21, 2014 2:07 AM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Wednesday, January 22, 2014 11:01 PM
Points: 1, 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...
Post #1532907
Posted Thursday, January 23, 2014 8:05 PM


SSC-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 8:35 AM
Points: 36,977, Visits: 31,494
@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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #1534320
Posted Wednesday, January 29, 2014 11:07 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Wednesday, January 29, 2014 11:02 PM
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?
Post #1536169
Posted Friday, July 18, 2014 6:02 PM
Forum Newbie

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Tuesday, August 12, 2014 11:48 AM
Points: 5, 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

Post #1594276
« Prev Topic | Next Topic »

Add to briefcase «««45678»»

Permissions Expand / Collapse