[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

finding end and parent nodes in a recursive table

Posted on 2004-10-21
16
Medium Priority
?
342 Views
Last Modified: 2006-11-17
I'm trying to find an efficent way to find the end node id to assign products, because in the system that I am writing I can only add products at the end nodes.

I've got the catalog structure stored in a table:

[Catalog] (
 [CatalogID] [int] IDENTITY (1000, 1) NOT NULL ,
 [ParentID] [int] NOT NULL ,
 [StatusID] [int] NOT NULL
)

So, I need the output to be in a recordset with two columns name and id.
like this

parent level = [bikes,1000]
sub level [red,1002] ...
sub levels continuing [name,catalogid]
end node [Red LT Cruiser,1003]

so if the end node is 30 levels deep it would produce a recordset in that order.

any ideas on that?








0
Comment
Question by:jbrahy
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 7
16 Comments
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12375531
Use Oracle instead?

Your example (data versus structure) is a bit ambiguous, as is your question.  When you say that you can only add products at "the end nodes", do you mean that (using your data example) given this structure:

Bikes --> Red --> .... --> Red LT Cruiser

That, if I needed to add another Red bike, I could only add it as a child of the Red LT Cruiser node?
0
 
LVL 10

Expert Comment

by:imrancs
ID: 12378180
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12383309
bhess1: yeah, that's right.  we'd have a few products at that level, such as 26" womens' bike, 26" mens' bike...

0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 1

Author Comment

by:jbrahy
ID: 12383331
Imran: It looks like it's doing the opposite of what I'm looking for.
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12568229
ok, I'll try anything...
0
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12569373
One question to add here:  It looks as if you can have multiple leaf nodes off of the bottom of the tree, e.g. 26" womens' bike, 26" mens' bike both off of th  Red LT Cruiser node.  If this is the case, then it is a much more standard problem, but you need to clarify:  How can we tell if a particular node is an 'End Node'?
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12569452
it's an end node if it doesn't exist anywhere in the parentID column. or stated another way, an end node is a node without children.
0
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12569463
Consider the following query:

SELECT * From Catalog c
WHERE NOT EXISTS (Select * FROM Catalog x WHERE x.ParentID = c.CatalogID

This gives us all of the leaf nodes in the table as a recordset.  Now, what you appear to need is (??all of the??) chain(s) from these items to their root item, provided as recordsets.  Is this correct?

Also, rereading your question, it looks as if you need to get the ID of that Red PT Cruiser entry, without considering the value of the leaf "mens" and "womens" entries.  This is a bit more complex, and cannot be coded for explicitly unless the StatusID value would be usable to indicate that the given node is a Branch where products may come off of (thos would be your simplest option).  Can this be done?  If not, how can you tell what node ais a branch that can contain products, even if no products have yet been assigned to that branch?
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12569574
The catalog structure will be hard coded, so I could add additional rows to make it easier.

>This is a bit more complex, and cannot be coded for explicitly unless the StatusID value would be usable >to indicate that the given node is a Branch where products may come off of (this would be your simplest >option).  Can this be done?  
can you elaborate on this? it sounds like it has possibilities


>If not, how can you tell what node ais a branch that can contain products, even if no products have yet >been assigned to that branch?
It doesn't have to contain products, it just has to be an end node so I can assign products to it.
0
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12569766
>>it's an end node if it doesn't exist anywhere in the parentID column. or stated another way, an end node is a node without children.<<

Although this does not seem to make logical sense (why would the 26" Women's bike be a sub-node of the 26" Men's bike?), finding this is not an issue.  A query to return the entire threading up to the top would be something like this:

Create Table #tmpChildren(Name varchar(128),  CatID int, CatParentID int)

Insert Into #tmpChildren
SELECT Name, CatalogID, ParentID
From Catalog c
WHERE NOT EXISTS (Select * FROM Catalog x WHERE x.ParentID = c.CatalogID)

----------

Now, build chains.  This assumes that the top-level node's parentID = 0

Create Table #tmpChains (ChainID int, CatID int, CatParentID int, StepID int, Name varchar(128))
Create Unique Index ix1 On #tmpChains (ChainID, CatID)   - Prevent accidental looping

Declare @StepID int
Declare @Rows int

Set @StepID = 1

Insert Into #tmpChains (ChainID, CatID, CatParentID, StepID, Name)
SELECT CatID, CatID, CatParentID, @StepID, Name
FROM #tmpChildren

Set @Rows = @@ROWCOUNT

WHILE @Rows <> 0
BEGIN
    Set @StepID = @StepID + 1

    Insert Into #tmpChains (ChainID, CatID, CatParentID, StepID, Name)
    SELECT ChainID, CatParentID, ParentID, @StepID, c.Name
    FROM #tmpChains ch
    INNER JOIN Catalog c ON ch.CatParentID = c.CatalogID
    LEFT JOIN #tmpChains cx ON ch.ChainID = cx.ChainID AND ch.CatID = cx.CatParentID
    WHERE ch.CatParentID <> 0  -- Don't bother looking for items above the parent
    AND cx.ChainID Is Null  -- Only insert if it does not already exist
   
    Set @Rows = @@ROWCOUNT
END

--- Now, each product's chain is linked in from top to bottom.  To get them out in the order of Parent -->...--> Child, you would:

SELECT ChainID, CatID, Name
FROM #tmpChains
Order By ChainID,         -- Get individual chains
              StepID Desc   -- in the reverse order that they were entered
0
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12569821
On the StatusID:  Normal status codes are something like Active, Inactive, etc.  You could add a status of "Active End Node" to your statuses, and when you designate a node as an end node, then you could modify the previous select something like this:

(NOTE: for the purposes of this coding, I am assuming that the StatusID of Active End Nodes = 9 -- it could be any value.)

The only part that needs to change is the build of the #tmpChildren table.  This would be set up as:

Insert Into #tmpChildren
SELECT Name, CatalogID, ParentID
From Catalog c
WHERE StatusID = 9

0
 
LVL 1

Author Comment

by:jbrahy
ID: 12571363

>Although this does not seem to make logical sense (why would the 26" Women's bike be a sub-node of >the 26" Men's bike?), finding this is not an issue.  A query to return the entire threading up to the top >would be something like this:

If I typed that, then I typed it incorrectly. It's basically a breadcrumb trail of the parents of the node ie:
I'm looking for a dataset that has this type of information:
CatalogID, Catalog Name, Breadcrumb Name Trail, Breadcrumb ID Trail
1000, 26" bikes, Bicycles->women's bikes->red bikes->26" bikes,"1000,1001,1002,1003"
1000, 26" bikes, Bicycles->women's bikes->red bikes->27" bikes,"1000,1001,1002,1004"
1000, 26" bikes, Bicycles->women's bikes->red bikes->28" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->white bikes->26" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->white bikes->27" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->white bikes->28" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->blue bikes->26" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->blue bikes->27" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->women's bikes->blue bikes->28" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->red bikes->26" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->red bikes->27" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->red bikes->28" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->white bikes->26" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->white bikes->27" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->white bikes->28" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->blue bikes->26" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->blue bikes->27" bikes,"1000,1001,1002,1005"
1000, 26" bikes, Bicycles->men's bikes->blue bikes->28" bikes,"1000,1001,1002,1005"


0
 
LVL 32

Expert Comment

by:Brendt Hess
ID: 12571499
oho!  A different thing entirely!

Let's see what we can do, using the above query as the base:

-- Now, each product's chain is linked in from top to bottom.  To get them out in the "breadcrumb" method, you could do like this:

Declare @NameTrail varchar(2000)
Declare @IDTrail varchar(1000)

Create Table #tmpOutput (CatID int, CatName varchar(128), NameTrail varchar(2000), IDTrail varchar(1000))

Declare @CurrID Int, @LastID Int, @ParentID int
Declare @CurrName varchar(128), @LastName varchar(128)
Declare @chain int

-- A cursor to spin through all bottom entries

Declare c_TrailMix CURSOR FOR
Select ChainID, Name, CatParentID, CatID
FROM #tmpChains
WHERE StepID = 1

Open c_TrailMix
Fetch Next from c_TrailMix INTO @Chain, @NameTrail, @ParentID, @CurrID
WHILE @@FETCH_STATUS = 0
BEGIN
      Set @IDTrail = Cast(CurrID As varchar)
      SELECT @CurrName = Name, @CurrID = CatID, @NameTrail = @CurrName + '->' + @NameTrail, @IDTrail = Cast(@CurrID As varchar) + ', ' + @IDTrail
      FROM #tmpChains
      WHERE ChainID = @Chain
      AND StepID > 1
      ORDER BY StepID Desc

      INSERT INTO #tmpOutput (CatID, CatName, NameTrail, IDTrail) Values (@CurrID, @CurrName, @NameTrail, @IDTrail)
      Fetch Next from c_TrailMix INTO @Chain, @NameTrail, @ParentID, @CurrID
END

Close c_TrailMix
Deallocate c_TrailMix

SELECT CatID As CatalogID, CatName As [Catalog Name], NameTrail As [Breadcrumb Name Trail], IDTrail As [Breadcrumb ID Trail]
FROM #tmpOutput
Order By CatID, NameTrail

---------------------------------


If everything works, you should get the output you need.
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12661714
could you turn that into a function that returns a table object?
0
 
LVL 32

Accepted Solution

by:
Brendt Hess earned 1400 total points
ID: 12668710
Should be able to.  Just replace the CREATE TABLE #.... calls with DECLARE @<name> Table(....) statements, and encapsulate it all in a CREATE FUNCTION... RETURN @TmpTable wrapper, and you *should* be ready to go.
0
 
LVL 1

Author Comment

by:jbrahy
ID: 12668904
cool, thank you for your help
0

Featured Post

Get your Disaster Recovery as a Service basics

Disaster Recovery as a Service is one go-to solution that revolutionizes DR planning. Implementing DRaaS could be an efficient process, easily accessible to non-DR experts. Learn about monitoring, testing, executing failovers and failbacks to ensure a "healthy" DR environment.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What if you have to shut down the entire Citrix infrastructure for hardware maintenance, software upgrades or "the unknown"? I developed this plan for "the unknown" and hope that it helps you as well. This article explains how to properly shut down …
It is possible to export the data of a SQL Table in SSMS and generate INSERT statements. It's neatly tucked away in the generate scripts option of a database.
Using examples as well as descriptions, and references to Books Online, show the documentation available for date manipulation functions and by using a select few of these functions, show how date based data can be manipulated with these functions.
Via a live example, show how to backup a database, simulate a failure backup the tail of the database transaction log and perform the restore.

650 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question