June 6, 2003 at 9:21 am
hello, i have a design that require a implementation using hierarchy as tree structure with unlimited number of levels, the hierarchy structure may be built using only 2 tables (for nodes and links between them) but it may be built using one table with auto references , i must use recursive algorithm to proccess the tree, you know this algorithm is very slow with tree very big, what do you recommend to use tow tables or just one and another algorithm to procces the tree?
example
id
01
|_ 01.01
| |_01.01.01
| |_01.01.02
| | |_01.01.02.01
| |_01.01.03
| |_01.01.03.01
| |_01.01.03.02
|_ 01.02
|_01.02.01
| |_01.02.01.01
| |_01.02.01.02
| |_01.02.01.03
|_01.02.02
|_01.02.02.01
Thanks
June 6, 2003 at 11:57 am
If you can rely on a child only having 1 parent, then use a linked list approach, built on a single table:
CREATE TABLE Nodes
(
NodeID INT NOT NULL
. NodeLink VARCHAR(255) NOT NULL
, ParentNode INT NULL
)
-- This will select all root nodes
SELECT NodeID , NodeLink
FROM Nodes
WHERE ParentNode IS NULL
I would return this resultset to memory, then execute a recursive call to a function which returns the list of nodes tied to the NodeID in the original resultset:
CREATE PROC dbo.GetNodesByParent
(
@ParentNode INT
)
AS
SELECT NodeID, NodeLink
FROM Nodes
WHERE ParentNode = @ParentNode
Question: where are you planning to do this recursive call? I would recommend steering clear of cursors on the T-SQL platform and use a procedural programming platform to do the recursion.
June 9, 2003 at 9:57 am
A standard recursive call would involve a cursor but that is a dirty word on this forum.
Depending on the target application you could use a 'fragment caching' technique. Fragment caching is saving a frequently used query to the application cache, for example standard navigation.
But without knowing your target I can't say.
Another technique you could use would be to build a summary table (very old technique that is probably outlawed by the SQL police) that would contain something like
o parent node
o node
o node name
o indent
You could also add a trigger that rebuilt this table when your node list got changed.
<disclaimer>
As I said these are techniques that should only be used if the circumstances are right.
</disclaimer>
June 9, 2003 at 10:11 am
You may want to explore so called "worm method". Imaging a worm crawling the tree starting in the root and numbering each node as it goes from the left and right side. So each node has a left number and right number. All its children have numbers between those two. You could find more information about this technique on the Web. It is very fast for data retrieval, avoids recursion (and cursors). It is not as strait-forward for updates of the tree though. You may find how other people implemented manipulation with a tree using this method on the Web.
June 9, 2003 at 10:47 am
Hi there,
there is an alternative scheme to mark and process a hierarchical structure. I've seen the method you've used discussed in books, but have not used it so i can't be too sure about performance comparisons. a key difference is the use of INTs rather than VARCHARs to maintain the network.
Each record has a "index" number and "downline end" number. On the hierarchy below the these are 1 and 15 for the root node. Leaves have the index=downline end.
To select all nodes + leaves below a given node (N), including N
select *
from table t
where @Nindex <= t.Index And t.index <= @NDownlineEnd
To count the number of nodes and leaves below a given node N
select @N_DownlineEnd - @NIndex
processing will always be a little difficult due to the recursive nature of the structure, this can't be avoided.
For presentation purposes it will also be necessary to maintain a "depth" field, indicating the number of levels the node (or leaf) is below the root.
I've modified the sample structure you provided to show this scheme. The downline end is in brackets.
1 (15)
|
|_ 2 (8)
| |
| |_3 (3)
| |
| |_4 (5)
| | |
| | |_5 (5)
| |
| |_6 (6)
| |
| |_7 (7)
| |
| |_8 (8)
|
|_ 9 (9)
|
|_10 (13)
| |
| |_11 (11)
| |
| |_12 (12)
| |
| |_13 (13)
|
|_14 (14)
|
|_15 (15)
i can provide some sample TSQL code to mark a given hierarchy of records this way if you like. I'll have to dig it out though, as it's at home.
hope this helps (and is coherent)
Andrew
June 10, 2003 at 12:10 am
If you are interested in traversing the hierarchy then you can do it with the sampel SP which builds the tree using @@rowcount variable. Hope this helps. If its irrelevant then accpet my applogies.
Regards,
Affan
SET QUOTED_IDENTIFIER ON
GO
SET ANSI_NULLS ON
GO
CREATE PROCEDURE sp_BuildHierarchy
AS
BEGIN
-- Deletes all the data from Export Table
DELETE FROM ExpTblCostCentre
-- Inserts all the data from Cost Centre Table to Export Table
INSERT INTO ExpTblCostCentre (Id, EmployeeId, Name, ParentId, ParentEmployeeId)
SELECT Id, EmployeeId, Code, ParentId, ParentEmployeeId FROM CostCentre
-- Updates the Hierarchy IDs and strings for the first level in the export table
UPDATE A
SET A.CostCentreIDString = CAST(B.ID AS VARCHAR) + ':' + CAST(B.EmployeeID AS VARCHAR)
, A.CostCentreNameString = b.Code
FROM ExpTblCostCentre A
INNER JOIN CostCentre B
ON A.[ID] = B.[ID] AND A.EmployeeID = B.EmployeeID
AND A.ParentID IS NULL AND A.ParentEmployeeId IS NULL
WHILE @@ROWCOUNT > 0
BEGIN
-- Updates the Hierarchy IDs and strings
-- for All the levels in the export table
UPDATE Chld
SET Chld.CostCentreIDString = CAST(Prnt.CostCentreIDString AS VARCHAR(8000)) + ':' + CAST(Chld.[ID] AS VARCHAR(255)),
Chld.CostCentreNameString = Prnt.CostCentreNameString + ':' + Chld.[Name]
FROM ExpTblCostCentre Chld
INNER JOIN ExpTblCostCentre PRnt
ON Chld.ParentID = Prnt.[ID] AND Chld.ParentEmployeeID = Prnt.EmployeeID
WHERE Prnt.CostCentreNameString IS NOT NULL AND Chld.CostCentreNameString IS NULL
END
END
GO
SET QUOTED_IDENTIFIER OFF
GO
SET ANSI_NULLS ON
GO
July 8, 2003 at 9:38 am
I've used recursive calls to TSQL functions and sprocs to process hierarchical data. The biggest hitch is the 32 nestlevel limitation. Most trees are less than 32 levels deep, but not all. I've also experienced excellent performance.
Viewing 7 posts - 1 through 6 (of 6 total)
You must be logged in to reply to this topic. Login to reply