sqlhierarchical-datahierarchical-treeshierarchical-querytransitive-closure-table

How do I query for all the nodes between two nodes in a tree?


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.


Solution

  • 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.