"Pavel Schevaev" <pacha_shevaev_at_mail.ru> wrote in message
news:320b3b2.0404090545.692729f1_at_posting.google.com...
> Nested sets are just great and i've been using it for quite a while
> already.
> The only inconvenience that popped up lately was that it seems like
> it's impossible to order node siblings by some arbitrary parameter,
> say, alphabetically, in sigle query without any vendor-specific stuff.
>
> Oracle10g supports such sorting, even without nested sets(of course we
> can't afford it):
>
> SELECT LEVEL, LPAD(' ',2*(LEVEL - 1)) || EMP_NAME "EMPLOYEE", EMP_ID,
> MGR_IDFROM EMPLOYEESTART WITH EMP_ID = 7839CONNECT BY PRIOR EMP_ID =
> MGR_IDORDER SIBLINGS BY EMP_NAME;
> LEVEL EMPLOYEE EMP_ID MGR_ID
> ----- -------------------- ---------- ----------
> 1 KING 7839
> 2 BLAKE 7698 7839
> 3 ALLEN 7499 7698
> 3 JAMES 7900 7698
> 3 MARTIN 7654 7698
> 3 TURNER 7844 7698
> 3 WARD 7521 7698
> 2 CLARK 7782 7839
> 3 MILLER 7934 7782
> 2 JONES 7566 7839
> 3 FORD 7902 7566
> 4 SMITH 7369 7902
> 3 SCOTT 7788 7566
> 4 ADAMS 7876 7788
>
> (if above ascii art is messed up here's the link
> http://www.dbazine.com/mishra3.shtml)
>
> Probably there's someone who faced the same problem already and got a
> solution?
The idea is to assign a sequence number to each node which is in
accordance with the ordering desired, i.e., an ORDER BY on the
sequence number column will return the nodes in the required order.
To find the sequence number of a given node N, gather together the set
A which is comprised of node N and each of its ancestor nodes. Let's
refer to the cardinality of set A as |A|. For each node "a" in A:
- Find each sibling node S of node "a" that meets the specified
ordering, e.g., all siblings less than the node "a".
- For each sibling node S, count the sibling node S and all of its
descendants to get count C.
- Sum all the counts C and add to |A| and this becomes the sequence
number for node N.
CREATE TABLE Tree
(
node_value INT NOT NULL PRIMARY KEY,
left_value INT NOT NULL UNIQUE,
right_value INT NOT NULL UNIQUE,
CHECK (right_value > left_value)
)
- All paths for tree along with path length
CREATE VIEW PathsToRoot (from_node_value, from_node_left, from_node_right,
path_node_value, path_node_left, path_node_right,
path_edges_tally)
AS
SELECT T1.node_value, T1.left_value, T1.right_value,
T2.node_value, T2.left_value, T2.right_value,
COUNT(T3.node_value)
FROM Tree AS T1
INNER JOIN
Tree AS T2
ON T2.left_value <= T1.left_value AND
T2.right_value >= T1.right_value
LEFT OUTER JOIN
Tree AS T3
ON T3.left_value < T1.left_value AND
T3.left_value >= T2.left_value AND
T3.right_value > T1.right_value AND
T3.right_value <= T2.right_value
GROUP BY T1.node_value, T1.left_value, T1.right_value,
T2.node_value, T2.left_value, T2.right_value
- For each node, all sibling nodes
CREATE VIEW Siblings (node_value,
node_left, node_right,
sibling_node_value,
sibling_node_left, sibling_node_right)
AS
SELECT SP1.from_node_value, SP1.from_node_left, SP1.from_node_right,
SP2.from_node_value, SP2.from_node_left, SP2.from_node_right
FROM PathsToRoot AS SP1
INNER JOIN
PathsToRoot AS SP2
ON SP1.from_node_value <> SP2.from_node_value AND
SP1.path_node_value = SP2.path_node_value AND
SP1.path_edges_tally = 1 AND
SP2.path_edges_tally = 1
- Sequence number of nodes when using nested set model with no gaps
CREATE VIEW OrderedNodes (node_value, sequence_number)
AS
SELECT P.from_node_value,
SUM(COALESCE((S.sibling_node_right - S.sibling_node_left) / 2 + 1, 0))
+ COUNT(DISTINCT P.path_node_value)
FROM PathsToRoot AS P
LEFT OUTER JOIN
Siblings AS S
ON S.node_value = P.path_node_value AND
S.sibling_node_value < P.path_node_value -- ordering constraint
GROUP BY P.from_node_value
- Sequence number of nodes when using nested set model with gaps
CREATE VIEW OrderedNodesWhenGaps (node_value, sequence_number)
AS
SELECT P.from_node_value,
COUNT(SP.path_node_value) + COUNT(DISTINCT P.path_node_value)
FROM PathsToRoot AS P
LEFT OUTER JOIN
Siblings AS S
ON S.node_value = P.path_node_value AND
S.sibling_node_value < P.path_node_value -- ordering constraint
LEFT OUTER JOIN
PathsToRoot AS SP
ON SP.path_node_value = S.sibling_node_value
GROUP BY P.from_node_value
- Sample tree encoded with nested set model with no gaps
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (5, 1, 30)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (12, 2, 9)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (6, 3, 4)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (3, 5, 6)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (7, 7, 8)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (10, 10, 23)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (2, 11, 12)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (13, 13, 14)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (17, 15, 16)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (1, 17, 22)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (9, 18, 19)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (4, 20, 21)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (18, 24, 29)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (25, 25, 26)
INSERT INTO Tree (node_value, left_value, right_value)
VALUES (20, 27, 28)
SELECT node_value, sequence_number
FROM OrderedNodes
ORDER BY sequence_number ASC
node_value sequence_number
5 1
10 2
1 3
4 4
9 5
2 6
13 7
17 8
12 9
3 10
6 11
7 12
18 13
20 14
25 15
--
JAG
Received on Mon Apr 26 2004 - 23:27:41 CDT
