Solved

finding end and parent nodes in a recursive table

Posted on 2004-10-21
337 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
Question by:jbrahy
    16 Comments
     
    LVL 32

    Expert Comment

    by:bhess1
    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
    0
     
    LVL 1

    Author Comment

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

    0
     
    LVL 1

    Author Comment

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

    Author Comment

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

    Expert Comment

    by:bhess1
    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
    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:bhess1
    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
    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:bhess1
    >>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:bhess1
    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

    >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:bhess1
    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
    could you turn that into a function that returns a table object?
    0
     
    LVL 32

    Accepted Solution

    by:
    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
    cool, thank you for your help
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How to improve team productivity

    Quip adds documents, spreadsheets, and tasklists to your Slack experience
    - Elevate ideas to Quip docs
    - Share Quip docs in Slack
    - Get notified of changes to your docs
    - Available on iOS/Android/Desktop/Web
    - Online/Offline

    SQL Server Side Trace is a technique of Profiling SQL Server Events Silently (i.e without Using the Profiling Tool). Running a visual tool in production increases overhead, but we can develop server side Trace using Sql Server Profiler itself. We…
    Slowly Changing Dimension Transformation component in data task flow is very useful for us to manage and control how data changes in SSIS.
    Familiarize people with the process of utilizing SQL Server functions from within Microsoft Access. Microsoft Access is a very powerful client/server development tool. One of the SQL Server objects that you can interact with from within Microsoft Ac…
    This videos aims to give the viewer a basic demonstration of how a user can query current session information by using the SYS_CONTEXT function

    856 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

    Need Help in Real-Time?

    Connect with top rated Experts

    11 Experts available now in Live!

    Get 1:1 Help Now