Professional Web Applications Themes

Equivalent to Oracle's START AT .... CONNECT TO for tree ordering - Microsoft SQL / MS SQL Server

>> I've always considered the Nested Set Model a workaround for NOT having something like START AT. . .CONNECT TO to query hierarchies. << Unh? SQL is a set oriented language, so why would a set-oriented approach be a work-around? Imitation of pointer chains and linked list via the adjecency model (which was I first used in FORTRAN II more years ago than I will admit) is the "unnatural way" in such an environment.  [/ref] relational model". << I avoid the need for cursors and other procedural code. The adjacency list model **requires** procedural code, either iteration or recursion in ...

  1. #1

    Default Re: Equivalent to Oracle's START AT .... CONNECT TO for tree ordering

    >> I've always considered the Nested Set Model a workaround for NOT
    having something like START AT. . .CONNECT TO to query hierarchies. <<

    Unh? SQL is a set oriented language, so why would a set-oriented
    approach be a work-around? Imitation of pointer chains and linked list
    via the adjecency model (which was I first used in FORTRAN II more years
    ago than I will admit) is the "unnatural way" in such an environment.
     [/ref]
    relational model". <<

    I avoid the need for cursors and other procedural code. The adjacency
    list model **requires** procedural code, either iteration or recursion
    in explicit or hidden cursors. The order the rows appear from out of a
    START AT. . .CONNECT TO construct has meaning -- a hugh no-no in the
    relational model.
     [/ref]
    sub tree involves inserts and updates to multiple rows. <<

    The nodes (personnel) are in a separate table from the strucuture (org
    chart), so changing a node is easy (hire/fire someone for some
    position). Changing the structure is more complex because you must
    change all the relationships among the subtrees.

    The adjacency list model inserts new edges faster because all of those
    relationships are calculated instead of being captured in the data.

    However, if I drop a row in a nested sets table, subordination is
    preserved in the heirarchy. If I drop a row in an adjacency list, I get
    a forest instead of a tree. Important point here: an adjacency list
    models a tree, not a hierarchy.

    In most cases, the hierarchy is more stable than the nodes (i.e. the
    company hires and fires people more often than it re-organizes -- unless
    you work for a dot-com or run a message board). However, since the
    structrue table is small -- perhaps only three integers: (node_key_fk
    lft, rgt) -- it is actually very fast to update in practice. Having
    proper constraints is what kills the speed, but that is also true with
    the adjacency list model.
     [/ref]
    self-reference to store the ordering relation? <<

    Unh? The adjacency list does not use single rows for entities and the
    nested set model does. Let's take an organizational chart and fire
    middle manager 'Chuck'; I have to find him in *multiple rows* where we
    have ('chuck', <subordinate>) pairs. He is in one and only row in the
    nested sets model.
     [/ref]
    design of the database in order to enable queries of hierarchies of
    arbitrary depth. <<

    Unh? This query finds all subordinates of 'Chuck' in one pure SQL
    statement for any depth:

    SELECT O1.*
    FROM OrgChart AS O1, OrgChart AS O2
    WHERE O1.lft BETWEEN O2.lft AND O2.rgt
    AND O2.emp = 'Chuck';

    No cursors, no iteration, no sequential numbering to order the output,
    no procedural code.
     [/ref]
    relationship as a simple foreign key. Why use a different pattern when
    the relationship is between rows on the same table? <<

    Because REFERENCE and subordination are not the same concepts. The DRI
    can be a general graph, without subordination. Trees are a special case
    of graphs.

    Also, don't newer programmers find it easier to think in terms of XML,
    HTML, etc. which is what nested set are most like?
     [/ref]
    TO to facilitate querying the hierarchy would be the more "relational"
    since it enables you to use the simplest and most straight-forward table
    design. <<

    It's a cursor, it is defined by procedural code, therefore it is less
    relational. Years ago, Phil Shaw from IBM brought in a horribly complex
    version of a hidden cursor syntax, which let you pick breath-first,
    depth-first, preorder, postorder, etc. traversals -- over a dozen
    options if I remember it right. A smaller version of Phil's paper made
    it into SQL-99 and the WITH clause; but it is still defined
    procedurally.

    Another problem is that writing the needed constraints for preserving
    the tree structure is difficult in the adjacency list model, but
    relatively easy in the nested sets model. Okay, I'll be honest, the
    lack of constraints is more of a programmer failure than a flaw in the
    model. "Against stupidity the gods themselves struggle in vain." - Die
    Jungfrau von Orleans; Friedrich von Schiller (1759-1805). But I have
    never seen an adjacency list model with proper constraints in practice.

    Trees are graphs that have the following properties for which you will
    need to write constraints:

    1) A tree is a connected graph which has no cycles.

    2) Every node is the root of a subtree. The most trivial case is a
    subtree of only one node.

    3) Every two nodes in the tree are connected one and only one path.

    4) A tree is a connected graph which has one less edge than it has
    nodes.

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

  2. #2

    Default Re: Equivalent to Oracle's START AT .... CONNECT TO for tree ordering



    Joe Celko wrote:
     [/ref]
    >encoding of the set structure, which you can see by the fact that it
    >introduces the rgt and lft columns which are what? <<
    >
    >Yes, that's right! And numerals are not really numbers, but only an
    >ASCII encoding of them. And employee ids are not really employees.
    >That is what a model is all about -- representing a fact in symbols.
    >
    >[/ref]
    You've spent a lot of finger energy in these newsgroups arguing
    that data should be verifiable. But you've never answered the
    question of how the values of lft and rgt are verifiable from the
    real world. How do you look at an employee and deduce his or
    her lft or rgt attribute? The question is a good one. rgt and lft are
    what?
    They seem completely artificial to me (which I don't find problematic,
    but you seem to).
     
    So long as no one has ever been fired.
     
    And what kind of computer do you have that doesn't do things
    sequentially? Even with multiple processors, if the table exists on
    a single device, everything happens sequentially.
     
    Um, don't you need to exclude rows where boss_emp_nbr IS NULL from your
    edge count?
     
    Isn't check (select count(*) from OrgChart where boss_emp_nbr is null) = 1)
    a little simpler way to check "only one NULL in the boss_emp_nbr column" ?


    -- Steve Kass
    -- Drew University
    -- Ref: 6E27E3DB-F383-4D3C-8377-3C2CBEEC8BBA

    Steve Guest

  3. #3

    Default Re: Equivalent to Oracle's START AT .... CONNECT TO for tree ordering



    There may be efficient implementations of the update, but it doesn't change
    the fact that the every change to the tree requires editing the whole
    subtree. And that can only be done by one user at a time.
     

    Which I'll take as an admission that the nested set model is a poor choice
    for applications requiring which store trees with a high velocity of change. 

    Inserts and updates are slow and serialized.
     

    But a relation of the form (id, rgt, lft) does not always produce a nested
    set.

    joe,1,6
    bob,2,5
    frank,3,4

    is, but

    joe,1,6
    bob,2,5
    frank,3,7

    is just meaningless. While the adjency list always produces a graph, the
    nested set model stores a subset of DxNxN, which may or may not be the
    nested set representation of a tree. Where are the constraints that
    guarantee that what is stored is actually a correct nested set?

     

    Still just saying "Arrgh, there be cursors", doesn't make it so.
    The RDBMS could employ a recursive nested loops join behind the scenes. It
    can discover at run time how many joins are required to traverse the tree
    and save an execution plan using those joins to process the query without a
    cursor in sight.
     

    Only if someone designed a magic RDBMS that allows two users to
    simultaneously edit the same row.

    Two users updating the same tree have to update the same rows.
    So the first user must complete the update of the whole tree, and commit the
    transaction in which the update runs, before the second user can even see
    her starting values of rgt and lft.


    David


    David Guest

Similar Threads

  1. sql server equivalent procedure in Oracle
    By reenaroy in forum Coldfusion Database Access
    Replies: 4
    Last Post: November 9th, 05:18 AM
  2. How to do equivalent to Crypt:CBC of Perl in Oracle pl/sql
    By Ron Reidy in forum PERL Miscellaneous
    Replies: 1
    Last Post: July 29th, 05:35 AM
  3. Oracle/SQL Server and Informix Equivalent Command
    By shahid.mehmood in forum Informix
    Replies: 3
    Last Post: July 19th, 01:12 AM
  4. Oracle RowNum Equivalent
    By Kevin Munro in forum Microsoft SQL / MS SQL Server
    Replies: 4
    Last Post: July 9th, 09:46 AM
  5. Replies: 3
    Last Post: December 6th, 02:36 PM

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