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 «««34567

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: Yesterday @ 9:45 PM
Points: 36,013, Visits: 30,300
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."

"Change is inevitable. Change for the better is not." -- 04 August 2013
(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: Thursday, March 14, 2013 6:51 PM
Points: 4, Visits: 12
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: Yesterday @ 3:34 PM
Points: 8,295, Visits: 8,748
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: Yesterday @ 9:45 PM
Points: 36,013, Visits: 30,300
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."

"Change is inevitable. Change for the better is not." -- 04 August 2013
(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: Yesterday @ 9:45 PM
Points: 36,013, Visits: 30,300
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."

"Change is inevitable. Change for the better is not." -- 04 August 2013
(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: Yesterday @ 9:45 PM
Points: 36,013, Visits: 30,300
@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."

"Change is inevitable. Change for the better is not." -- 04 August 2013
(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
« Prev Topic | Next Topic »

Add to briefcase «««34567

Permissions Expand / Collapse