Solved

celko tree model

Posted on 2004-10-24
348 Views
Last Modified: 2010-08-05
hello i have implemented joe celko's model to store heirarchy and it works well and nice
i have a question about SQL

let's say i have this chart representation of the table



                                                                     nancy
                                      .   andrew    .                                   .     janet    .
                       . margaret .              . steven .             . michael .              robert
                    laura         ann          ina      david        ron           dan


this is the actual table

member  side     left     right
------------------------------------------
nancy          L      1      36
andrew       L       4      21
steven         R      5      12
ina              L      6       7
david           R     10     11
margaret     L     13     20
ann             R     14     15
laura           L     18     19
janet           R     24     35
michael       L     25     30
dan            R     26     27
ron            L      28     29
robert        R     33     34


the Side column is to tell its left, or right. this is a binary heirarcy.
i have this problem i have to solve, im still banging my head. If given the member

'Nancy' , i need to find left-most(Laura) and right-most(Robert)
'Janet'  = left most is ron, right most is robert
'Andrew = left most is laura, right most is David


Hope u get my plan. could u help me with the sql ?
0
Question by:dynamicrevolutions
    6 Comments
     
    LVL 8

    Accepted Solution

    by:
    Here is the query, I'll post the explanation in the next comment:

    select
        case when children.[side] = 'L' then (
            select n.member from h n where n.[left] = min(children.[left])
        ) end LeftMost,
        case when children.[side] = 'R' then (
            select n.member from h n where n.[right] = max(children.[right])
        ) end as RightMost
    from
        h
            inner join h children
                inner join h parent
                on
                    parent.[left] < children.[left]
                    and parent.[right] > children.[right]
                    and parent.[side] = children.[side]
            on
                children.[left] > h.[left]
                and children.[right] < h.[right]
                and children.[left] + 1 = children.[right]
                and (
                    select top 1 parent.[side]
                    from h parent
                    where
                        parent.[left] < children.[left]
                        and parent.[right] > children.[right]
                    order by parent.[right] - parent.[left]
                ) = children.[side]
    where h.member = 'andrew'
    group by children.[side]
    0
     
    LVL 8

    Expert Comment

    by:sigmacon
    Sorry, in the query above, this part is redundant, I forgot to delete it:

                inner join h parent
                on
                    parent.[left] < children.[left]
                    and parent.[right] > children.[right]
                    and parent.[side] = children.[side]

    Here is my explanation:

    I called the table with the hierarchy [h]. Here is how it goes:

    first we need all children of a member:

        children.[left] > h.[left]
        and children.[right] < h.[right]

    but we only want end nodes (have no children):

        and children.[left] + 1 = children.[right]

    which gives this:

    select *
    from
        h
            inner join h children
            on
                children.[left] > h.[left]
                and children.[right] < h.[right]
                and children.[left] + 1 = children.[right]
    where h.member = 'andrew'

    we actually only want children whose IMMEDIATE parent:

        select top 1 *
        from h parent
        where
            parent.[left] < children.[left]
            and parent.[right] > children.[right]
        order by parent.[right] - parent.[left]

    is on the same side:

        and (
            select top 1 parent.[side]
            from h parent
            where
                parent.[left] < children.[left]
                and parent.[right] > children.[right]
            order by parent.[right] - parent.[left]
        ) = children.[side]


    Which gives:

    select *
    from
        h
            inner join h children
            on
                children.[left] > h.[left]
                and children.[right] < h.[right]
                and children.[left] + 1 = children.[right]
                and (
                    select top 1 parent.[side]
                    from h parent
                    where
                        parent.[left] < children.[left]
                        and parent.[right] > children.[right]
                    order by parent.[right] - parent.[left]
                ) = children.[side]
    where h.member = 'andrew'

    Now we want to find the lowest index child furthest left and the hight for the child furthest right:

        case when children.[side] = 'L' then min(children.[left]) end as LeftMost,
        case when children.[side] = 'R' then max(children.[right]) end as RightMost

    which requires a group by side.

    Now we just need to get the appropriate child name base on the left / right value:

    select
        case when children.[side] = 'L' then (
            select n.member from h n where n.[left] = min(children.[left])
        ) end LeftMost,
        case when children.[side] = 'R' then (
            select n.member from h n where n.[right] = max(children.[right])
        ) end as RightMost
    from
        h
            inner join h children
            on
                children.[left] > h.[left]
                and children.[right] < h.[right]
                and children.[left] + 1 = children.[right]
                and (
                    select top 1 parent.[side]
                    from h parent
                    where
                        parent.[left] < children.[left]
                        and parent.[right] > children.[right]
                    order by parent.[right] - parent.[left]
                ) = children.[side]
    where h.member = 'andrew'
    group by children.[side]
    0
     
    LVL 8

    Expert Comment

    by:sigmacon
    kselvia beat me by two min.

    kselvia, if you feel like having a puzzle, maybe you can improve on this (you old friends - parent-child, done as nested sets):

    http://www.experts-exchange.com/Databases/Microsoft_SQL_Server/Q_21180918.html
    0
     
    LVL 8

    Expert Comment

    by:sigmacon
    ignore last post, wrong question
    0
     
    LVL 5

    Author Comment

    by:dynamicrevolutions
    if i add 'roger' under Left of Laura, then add 'Kelvin' left or Roger,

    then for margeret, it will only give me left most, which is kelvin.it doesn't give me 'Ann'
    0
     
    LVL 5

    Author Comment

    by:dynamicrevolutions
    i'll repost the sql, and i'll re-award u another 500 points ok, if you could help me

    http://www.experts-exchange.com/Databases/Microsoft_SQL_Server/Q_21180993.html
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    Course: From Zero to Hero with Nodejs & MongoDB

    Interested in Node.js, but don't know where to start or how to learn it properly? Confused about how the MEAN stack pieces of MongoDB, Expressjs, Angularjs, and Nodejs fit together? Or how it's even possible to run JavaScript outside of the browser?

    This is my first ever Article on EE or elsewhere; therefore, please bear with me if I have some discrepancies in my writing. I read many articles and questions related to "how to pass values to SSIS packages at run-time?"  Hence, this common ques…
    I wrote this interesting script that really help me find jobs or procedures when working in a huge environment. I could I have written it as a Procedure but then I would have to have it on each machine or have a link to a server-related search that …
    This video shows, step by step, how to configure Oracle Heterogeneous Services via the Generic Gateway Agent in order to make a connection from an Oracle session and access a remote SQL Server database table.
    Using examples as well as descriptions, and references to Books Online, show the documentation available for datatypes, explain the available data types and show how data can be passed into and out of variables.

    860 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

    14 Experts available now in Live!

    Get 1:1 Help Now