Re: Adjacency list to Nested set model statement
Date: Tue, 05 Mar 2002 01:02:02 -0800
Message-ID: <u892cars4e5l27_at_news.supernews.com>
In article <c0d87ec0.0203041356.6f2454a9_at_posting.google.com>, "--CELKO--" <71062.1056_at_compuserve.com> wrote:
>>> I've cleaned up the code and posted it at:
>
> http://willets.org/treecrawl.sql <<
>
> I just picked up a copy and it looks great! You are right about the
> whole approach and my stuff stinks.
>
>
>
Thanks, I've been working on some tree-based enumeration algorithms that also avoid the use of a stack. This is a useful spin-off, I suppose.
I'm not sure if this approach is really faster, due to the queries that have to be run at each step. But it's simple, in a way.
> PL/SQL is very close to the Standard SQL/PSM. In fact, almost too close
> -- it has some stuff that other SQL products don't have yet. For
> example:
>
> BEGIN
> SELECT MIN(node_id)
> INTO nxt
> FROM Tree AS C
> WHERE C1.parent_id = last_visited
> AND C1.nodenum IS NULL;
> EXCEPTION WHEN NO_DATA_FOUND
> THEN SET nxt = NULL;
> END;
>
> would get the same effect as just:
>
> SET nxt
> = (SELECT MIN(node_id)
> FROM Tree AS C
> WHERE C1.parent_id = last_visited
> AND C1.nodenum IS NULL);
>
>
>
>
>
I tried that, and it didn't work. It took me a long time to give up and find the silly exception method. And SET doesn't work either (AND I had to use := instead of =). Those are features which work in Sybase/SQL server but not in PL/SQL. If anyone can prove me wrong I'll be happy.
> Other products don't have the singleton select or the exception
> handling, which are standard. But we can take advantage of the rules
> about aggregate functions and emptry sets to get it all into one
> statement.
>
> And we should get rid of the sql%rowcount somehow. That one is
> proprietary. Can we get a WHILE condition at the start of the loop based
> on the size of the tree?
>
>
>
>
Yes, that's a good idea; it could be twice the number of edges, or 2n-2
where n is node count.
I guess SQLCA is not part of the standard? That's the part that always had the row counts and completion status in DB2 and Oracle IIRC. Counts are very useful with these "go until no more" loops.
>>> One only needs a stack if a node can have multiple paths to it from
> root. <<
>
> But then it is not a tree.
>
>
>
>
>
Agreed, I was speaking more of a DAG.
>>> I have another idea for a more parallelizable algorithm based on
> some
> stuff I did a few years ago. I'll see if I can reconstitute the stuff I
> need to try that out. <<
>
>
>
>
I've worked this out but I don't have time to code it. It's fairly easy to percolate node counts up a tree so that each node has the count of its descendants. This counting can be done across a bunch of nodes at once with a series of SQL statements, one per level. I've written this type of thing before, so I'm confident it'll work.
Once the counts are known, the task of counting all the nodes "to the left of" a node X can be done recursively from root by observing that a given node X's sequence number is the sequence number of its parent P, plus all the nodes of X's left siblings.
It's like this:
P: seq = 33
/ | \
/ | \
S1:5 S2:3 X: seq = ??
(P is the parent of S1, S2, and X. S1 has 5 descendants, S2 has 3.)
If P is the 33rd node in the Depth first search, then X's sequence number will be 33 + (S1's descendants) + (S2's descendants) + 1 = 42. Likewise S1 will have seq = 34 and S2 will have seq = 33+5+1 = 39.
Since we know the descendant counts already, we don't have to search the subtrees to calculate the increments that they produce.
The algorithm for percolating the counts is basically systolic. We start knowing that the leaves have a count of 1, and we use a "ready" flag to signify nodes which are correctly totalled. Then we iteratively total and set the ready flag for each node from its child nodes, moving totals up from leaves to root. That's not a very good descripton, but I'll see if I can code it up sometime soon. Received on Tue Mar 05 2002 - 10:02:02 CET