Professional Web Applications Themes

Nested set model - Microsoft SQL / MS SQL Server

Joe, When I run this query, I get this result: <root> i0 j3 i2 j3 i[0..n] j3 What I need is not to get just the first part of the tree up to level j3. I also need the path all the way up to level l5 and even deeper if level l5 is not the leaf node. <root> i0 j3 k0 l5 m1 n1 n2 m2 n1 n2 k[y] l5 m[0..n] .. i[x] j3 k[y] l5 m[0.n] Or when talking in circles, I need the intersection of circles i[n], j[3], k[m], l[5], m[o], n[p]... all the way down to ...

  1. #1

    Default Re: Nested set model

    Joe,

    When I run this query, I get this result:

    <root>
    i0
    j3
    i2
    j3
    i[0..n]
    j3

    What I need is not to get just the first part of the tree up to level j3. I
    also need the path all the way up to level l5 and even deeper if level l5 is
    not the leaf node.

    <root>
    i0
    j3
    k0
    l5
    m1
    n1
    n2
    m2
    n1
    n2
    k[y]
    l5
    m[0..n]
    ..
    i[x]
    j3
    k[y]
    l5
    m[0.n]


    Or when talking in circles, I need the intersection of circles i[n], j[3],
    k[m], l[5], m[o], n[p]... all the way down to the bottom of the tree (and
    for that matter, all the way up to the root of the tree.). The enclosed
    circle may be present in more than one set. This is a little different than
    the boss-employee hierarchy.

    I have tried creating the entire tree using the same query, but this gets
    very slow indeed. There is also a similar query for getting all l5 nodes. It
    also proves impossible to retrieve all data from the leave nodes down.

    Marcel

    "Joe Celko" <edu> wrote in message
    news:O30NX%phx.gbl... [/ref]
    > CustomCode 'j3' in common. The UNION selects both the upper and lower
    > part of the tree. Subquery 2 selects all trees that end with CustomCode
    > = 'l5'. I use both subqueries to build new trees from the leaves 'l5'
    > downwards. <<
    >
    > I am reading this to mean that you want all the subtrees such that 'j3'
    > is a superior of 'l5', but not necessarily an IMMEDIATE superior and
    > that 'l5' does not have to be a leaf node.
    >
    > SELECT T1.* AS subtree_root
    > FROM NestedTree AS T1, NestedTree AS T2, NestedTree AS T3
    > WHERE T2.custom_code = 'j3'
    > AND T3.custom_code = 'l5'
    > AND T3.lft BETWEEN T2.lft AND T2.rgt
    > AND T2.lft BETWEEN T1.lft AND T1.rgt
    >
    > Imagine circles inside circles, with T3 inside T2 inside T1. This will
    > start aT the root of the whole tree, then "prune" the tree from the top
    > down to the nodes where (custom_code = 'j3') and stop.
    >
    > --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 http://www.developersdex.com ***
    > Don't just participate in USENET...get rewarded for it![/ref]


    margel Guest

  2. #2

    Default Re: Nested set model

    This is a good problem; let me think out loud.

    I need to clean up the DDL in this thread first. In yours, IDENTITY can
    never be a key; you allow NULLs everywhere; you allow duplicate rows;
    etc. And I made the mistake of making the custom_code column a key.
    Arrgh! So this is what the table should look like:

    CREATE TABLE NestedTree
    (custom_code VARCHAR(20) NOT NULL, --dups allowed
    lft INTEGER NOT NULL UNIQUE,
    rgt INTEGER NOT NULL UNIQUE,
    CHECK (lft BETWEEN 1 AND rgt),
    PRIMARY KEY (lft, rgt));
     [/ref]
    'j3'. I also need the path all the way up to level 'l5' and even deeper
    if level 'l5' is not the leaf node. <<

    Let me try this again: You want all the paths from the root to the leaf
    nodes such that 'j3' is a superior of 'l5' somewhere in that path.

    I have been thinking of working from the root down; it looks better to
    think of going from leaf nodes up.

    SELECT T1.* AS candidate_leaf
    FROM NestedTree AS T1, NestedTree AS T2, NestedTree AS T3
    WHERE T1.lft = T1.rgt - 1 --start at leaf nodes
    AND T1.lft BETWEEN T2.lft AND T2.rgt --T1 inside T2
    AND T2.custom_code = 'l5'
    AND T2.lft BETWEEN T3.lft AND T3.rgt --T2 inside T3
    AND T3.custom_code = 'j3';

    This should give you the leaf nodes of the paths in which 'j3' is a
    superior to 'l5'. From the leaf nodes, you can easily construct the
    paths with the usual BETWEEN predicates.

    SELECT T0.*
    FROM NestedTree AS T0,
    (<<above>>) AS L0
    WHERE L0.lft BETWEEN T0.lft AND T0.rgt;

    I'd consider displaying this as one path on a line, if the tree is not
    too deep.

    --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 http://www.developersdex.com ***
    Don't just participate in USENET...get rewarded for it!
    Joe Guest

  3. #3

    Default Re: Nested set model

    Since DDL's are such an important communication method, I added the full DDL
    to this message. I think this DDL is as good as it needs to be.

    CREATE TABLE [dbo].[NestedTree] (
    [ID] [int] IDENTITY (1, 1) NOT NULL ,
    [CustomCode] [char] (15) COLLATE Latin1_General_CI_AS NULL ,
    [Description] [nvarchar] (50) COLLATE Latin1_General_CI_AS NULL ,
    [lft] [int] NOT NULL ,
    [rgt] [int] NOT NULL ,
    CONSTRAINT [PK_ParentChildTree] PRIMARY KEY NONCLUSTERED (
    [ID]) ON [PRIMARY] ,
    CONSTRAINT [CK_NestedTree_lft_nul] CHECK ([lft] > 0),
    CONSTRAINT [CK_NestedTree_lft_rgt_smaller] CHECK ([lft] < [rgt]),
    CONSTRAINT [CK_NestedTree_rgt_one] CHECK ([rgt] > 1)) ON [PRIMARY]

    GO
    CREATE UNIQUE CLUSTERED INDEX [IX_NestedTree_lft_rgt] ON
    [dbo].[NestedTree]([lft], [rgt]) ON [PRIMARY]

    GO

    CREATE UNIQUE INDEX [IX_NestedTree_rgt] ON [dbo].[NestedTree]([rgt]) ON
    [PRIMARY]

    GO

    CREATE INDEX [IX_NestedTree_CustomCode] ON [dbo].[NestedTree]([CustomCode])
    ON [PRIMARY]

    GO

    CREATE INDEX [IX_NestedTree_CustomCode_rgt] ON
    [dbo].[NestedTree]([CustomCode], [rgt]) ON [PRIMARY]

    GO

    CREATE UNIQUE INDEX [IX_NestedTree_lft] ON [dbo].[NestedTree]([lft]) ON
    [PRIMARY]

    GO

    CREATE INDEX [IX_NestedTree_CustomCode_lft] ON
    [dbo].[NestedTree]([CustomCode], [lft]) ON [PRIMARY]

    GO

    I put your query together and I ran the following statement:

    SELECT T0.*
    FROM NestedTree AS T0,
    (

    SELECT T1.*
    FROM NestedTree AS T1, NestedTree AS T2, NestedTree AS T3
    WHERE T1.lft = T1.rgt - 1 --start at leaf nodes
    AND T1.lft BETWEEN T2.lft AND T2.rgt --T1 inside T2
    AND T2.CustomCode = 'l5'
    AND T2.lft BETWEEN T3.lft AND T3.rgt --T2 inside T3
    AND T3.CustomCode = 'j3'

    ) AS L0
    WHERE L0.lft BETWEEN T0.lft AND T0.rgt;

    I am sorry, but this is a really bad query. As a matter of fact, it is still
    running as I type this message. (I stopped after 11 minutes.) Remember my
    UNION query ran for 4 seconds. It seems the way the query is put together is
    very important.

    This is a good problem indeed.

    Marcel


    "Joe Celko" <edu> schreef in bericht
    news:phx.gbl... [/ref]
    > 'j3'. I also need the path all the way up to level 'l5' and even deeper
    > if level 'l5' is not the leaf node. <<
    >
    > Let me try this again: You want all the paths from the root to the leaf
    > nodes such that 'j3' is a superior of 'l5' somewhere in that path.
    >
    > I have been thinking of working from the root down; it looks better to
    > think of going from leaf nodes up.
    >
    > SELECT T1.* AS candidate_leaf
    > FROM NestedTree AS T1, NestedTree AS T2, NestedTree AS T3
    > WHERE T1.lft = T1.rgt - 1 --start at leaf nodes
    > AND T1.lft BETWEEN T2.lft AND T2.rgt --T1 inside T2
    > AND T2.custom_code = 'l5'
    > AND T2.lft BETWEEN T3.lft AND T3.rgt --T2 inside T3
    > AND T3.custom_code = 'j3';
    >
    > This should give you the leaf nodes of the paths in which 'j3' is a
    > superior to 'l5'. From the leaf nodes, you can easily construct the
    > paths with the usual BETWEEN predicates.
    >
    > SELECT T0.*
    > FROM NestedTree AS T0,
    > (<<above>>) AS L0
    > WHERE L0.lft BETWEEN T0.lft AND T0.rgt;
    >
    > I'd consider displaying this as one path on a line, if the tree is not
    > too deep.
    >
    > --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 http://www.developersdex.com ***
    > Don't just participate in USENET...get rewarded for it![/ref]







    margel Guest

  4. #4

    Default Re: Nested set model

    I tried posting thru DevDex and it did not work, so I am going thru
    Google. Devdex s up when the postings go over two display pages.
    This has happened before and it drives me nuts.
     [/ref]
    is missing. I probably gain some performance by reassigning my
    indices. I'm
    going to follow the lead of Steve Kass on this one. <<

    I'd use the Standard SQL constraints instead of the proprietary CREATE
    INDEX syntax for portability and drop the silly IDENTITY column.
    Perhaps spliting the code descriptions out as another table would
    help.

    I think I might have it.

    SELECT T1.custom_code, T1.lft, T1.rgt
    FROM NestedTree AS T1, -- leaf nodes
    NestedTree AS T2 -- paths
    WHERE T1.lft = T1.rgt - 1
    AND T1.lft BETWEEN T2.lft AND T2.rgt
    GROUP BY T1.custom_code, T1.lft, T1.rgt
    HAVING MIN(CASE WHEN T2.custom_code = 'l5'
    THEN T2.rgt - T2.lft
    ELSE NULL END)
    < MAX(CASE WHEN T2.custom_code = 'j3'
    THEN T2.rgt - T2.lft
    ELSE NULL END);

    Follow all paths from the leaf nodes to the node, making each of them
    into a group. The order of the nodes in path is represented by the
    size of the (rgt-lft) spread -- closer to the root, the greater the
    spread. Therefore, if 'l5' appears subordinate to 'j3', it will have
    a smaller spread.

    The problem is the spec we use if 'l5' and 'j3'occur many times in the
    same path. I could have a path like (root, 'l5', 'j3', 'l5', leaf)
    and it will pass; is that right?
    --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.
    --CELKO-- Guest

Similar Threads

  1. New release of Config-Model, first draft for Xorg model
    By Dominique in forum PERL Modules
    Replies: 2
    Last Post: September 24th, 03:22 PM
  2. New release of Config::Model with fstab model example
    By Dominique Dumont in forum PERL Modules
    Replies: 0
    Last Post: May 22nd, 12:08 PM
  3. model.userData returns nested property lists
    By thellers_rem in forum Macromedia Director 3D
    Replies: 0
    Last Post: September 1st, 02:09 PM
  4. model showing in 3d editor but not in castmember model list
    By Gianpiero Colagiacomo in forum Macromedia Director 3D
    Replies: 1
    Last Post: May 6th, 02:05 AM
  5. Model within model transform.position, intersection, overlapping models
    By Zafada webforumsuser@macromedia.com in forum Macromedia Director 3D
    Replies: 0
    Last Post: August 30th, 12: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