• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 426
  • Last Modified:

celko tree model

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
dynamicrevolutions
Asked:
dynamicrevolutions
  • 4
  • 2
1 Solution
 
sigmaconCommented:
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
 
sigmaconCommented:
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
 
sigmaconCommented:
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
Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

 
sigmaconCommented:
ignore last post, wrong question
0
 
dynamicrevolutionsAuthor Commented:
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
 
dynamicrevolutionsAuthor Commented:
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

Featured Post

Get expert help—faster!

Need expert help—fast? Use the Help Bell for personalized assistance getting answers to your important questions.

  • 4
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now