1

I have a hierarchical database strucutre, e.g. columns ID and PARENT_ID defined for each row, with the top level rows having a NULL PARENT_ID.

I have all the relationships from this table flattened into another table, e.g. if there were three records in a single hierarchy of grandparent, parent, grandchild, there would be 3 records:

**ANCESTOR, DESCENDANT**
grantparent, parent
grandparent, grandchild
parent, grandchild

Rather than execute a hierarchical query to determine that the grandchild is a descendant of the grandparent I can simply check for the existence of a (grandparent, grandchild) record in this flattened table.

My question is, using this flattened table, how can I most efficiently return all records which are between two nodes. Using the example, with grandparent and grandchild as my parameters, how can I get back the (grandparent, parent) record.

I do not want to use a hierarchical query to solve this... I'm wondering if it's possible to do this without any joins.

aw crud
  • 8,791
  • 19
  • 71
  • 115
  • Presumably your real hierarchies are not limited to three levels? – Ed Harper Nov 03 '10 at 16:37
  • @Renderln, does your flattened table *only* include Ancestor and Descendant columns, or are there other columns (such as number of generations/levels) included? Also, can there be multiple ways to link one descendant to the same ancestor? –  Nov 03 '10 at 16:55
  • @Ed Harper: Yes, this table contains multiple hierarchies of varying levels. – aw crud Nov 03 '10 at 18:15
  • @Mark Bannister: Each record contains the # of hops the ancestor and descendant nodes are apart from each other. It also specifies the root node for that hierarchy. It does not contain a total height of the hierarchy. Each ancestor can have multiple descendants, but a descendant can only have one parent. – aw crud Nov 03 '10 at 18:17

3 Answers3

2
SELECT  *
FROM    mytable
WHERE   descendant = @descendant
        AND hops < 
        (
        SELECT  hops
        FROM    mytable
        WHERE   descendant = @descendant
                AND ancestor = @ancestor
        )

This will automatically take care of cases when @ancestor is not really a @descendant's ancestor.

Create an index on (descendant, hops) for this to work fast.

Quassnoi
  • 413,100
  • 91
  • 616
  • 614
1

Try:

select h1.descendant intermediate_node
from hierarchy h0 
join hierarchy h1 
  on h0.ancestor = h1.ancestor 
 and h0.hops > h1.hops  -- redundant condition, but may improve performance
join hierarchy h2
  on h1.ancestor = h2.ancestor 
 and h0.descendant = h2.descendant
where h0.ancestor = :ancestor and h0.descendant = :descendant
0
SELECT
   distinct ancestor 
FROM 
   hierarchy 
WHERE descendant = :1 AND 
      ancestor IN (
                    SELECT 
                       distinct descendant 
                    FROM 
                       hierarchy WHERE ancestor = :2
                  )
ilan berci
  • 3,883
  • 1
  • 16
  • 21