Professional Web Applications Themes

Hierarchies - Microsoft SQL / MS SQL Server

Hello, I've successfully implemented a hierarchy strategy in my database using the method Itzik Ben-Gan writes about... but I'm having a problem searching over multiple criteria. I need to be able to search for all those records on say level 1 that have a certain property and all those records on say level 3 that have a certain property but I want only those records that match *both*. If all items in the hierarchy share the same branch then I can easily solve it using relational division. So my wider question is how do I use the relational division approach ...

  1. #1

    Default Hierarchies

    Hello, I've successfully implemented a hierarchy strategy in my
    database using the method Itzik Ben-Gan writes about... but I'm having
    a problem searching over multiple criteria.

    I need to be able to search for all those records on say level 1 that
    have a certain property and all those records on say level 3 that have
    a certain property but I want only those records that match *both*.

    If all items in the hierarchy share the same branch then I can easily
    solve it using relational division. So my wider question is how do I
    use the relational division approach with these hierarchies, or is
    there a better solution.

    Any thoughts appreciated...

    Kevin,
    Kevin Munro Guest

  2. #2

    Default Re: Hierarchies

    Please post DDL, so that people do not have to guess what the keys,
    constraints, Declarative Referential Integrity, datatypes, etc. in your
    schema are. Here is an equally vague reply to those "specs" --

    I would assume that nodes are in one table and the tree structure is
    another table. If you put both of them in one table, it would not be a
    correct table, since it would contain entities and relationships.

    So you would do the relational division on the nodes tables, then see if
    they were in the proper relationship in the tree table.

    In the nested sets model, it is pretty easy to compare structures to
    each other. Just put the trees in a canonical form that starts
    numbering at zero and see if they match:

    EXISTS(
    SELECT X.lft, X.rgt
    FROM (SELECT lft -(SELECT MIN(lft) FROM Tree1),
    rgt -(SELECT MIN(lft) FROM Tree1)
    FROM Tree1
    UNION ALL
    SELECT lft -(SELECT MIN(lft) FROM Tree2,
    rgt -(SELECT MIN(lft) FROM Tree2
    FROM Tree2) AS X(lft, rgt)
    GROUP BY X.lft, X.rgt
    HAVING COUNT(*) <> 2)

    I can build a "query tree" then compare it to possible subtrees in the
    target tree. Since the nested set model tells me the size of each
    subtree in formula ((lft-rgt+1)/2), I can eliminate many of the
    subtrees.

    And this is probably as clear as mud without a drawing to look at. How
    about this: "is there a man named 'John' with three kids, the youngest
    of whom is also named 'John'?"

    INSERT INTO QueryTree VALUES ('John', 0, 7);
    INSERT INTO QueryTree VALUES ('%', 1, 2);
    INSERT INTO QueryTree VALUES ('%', 3, 4);
    INSERT INTO QueryTree VALUES ('John', 5, 6);

    I take this pattern and apply it against a target tree, using LIKE
    predicates to match the names.

    --CELKO--
    ===========================
    Please post DDL, so that people do not have to guess what the keys,
    constraints, Declarative Referential Integrity, datatypes, etc. in your
    schema are.

    *** Sent via Developersdex [url]http://www.developersdex.com[/url] ***
    Don't just participate in USENET...get rewarded for it!
    Joe Celko Guest

  3. #3

    Default Re: Hierarchies

    Thanks Joe, I'll post DDL tomorrow when I'm back in the office - or
    rather a simplified version to illustrate my problem. It was an end of
    the day post borne out of another days frustration...

    I like your nested sets approach. I would have gone with it if your
    sample code was SQL Server and I could see how to upgrade my existing
    hierarchy.

    Kevin.

    Joe Celko <anonymousdevdex.com> wrote in message news:<ea#u4WLRDHA.2224TK2MSFTNGP12.phx.gbl>...
    > Please post DDL, so that people do not have to guess what the keys,
    > constraints, Declarative Referential Integrity, datatypes, etc. in your
    > schema are. Here is an equally vague reply to those "specs" --
    <snip>
    Kevin Munro Guest

  4. #4

    Default Re: Hierarchies

    >> I would have gone with it if your sample code was SQL Server and I
    could see how to upgrade my existing
    hierarchy. <<


    Unh? I write pure, standard SQL-92 almost all the time, so people can
    translate into their local dialect. And I tend to test in SQL Server
    these days.

    And changing the heirarchy is not that bad. Look for pairs of nodes in
    the path enumeration model to convert it to an adjacency list model.
    Then use a push-down stack on the adjacency model to get it to nested
    sets.

    But you need new code to maintain it.

    --CELKO--
    ===========================
    Please post DDL, so that people do not have to guess what the keys,
    constraints, Declarative Referential Integrity, datatypes, etc. in your
    schema are.

    *** Sent via Developersdex [url]http://www.developersdex.com[/url] ***
    Don't just participate in USENET...get rewarded for it!
    Joe Celko Guest

Similar Threads

  1. Clustering in the presence of hierarchies (fwd)
    By Ioannis Theoharis in forum PostgreSQL / PGSQL
    Replies: 0
    Last Post: December 11th, 03:27 PM
  2. Clustering in the presence of hierarchies
    By Ioannis Theoharis in forum PostgreSQL / PGSQL
    Replies: 0
    Last Post: December 10th, 03:15 AM
  3. Form Field Hierarchies
    By Amit_Arora@adobeforums.com in forum Adobe Acrobat Windows
    Replies: 0
    Last Post: April 21st, 11:03 AM
  4. Hierarchies/Relational Division
    By Kevin Munro in forum Microsoft SQL / MS SQL Server
    Replies: 10
    Last Post: July 10th, 08:30 AM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139