Oracle FAQ Your Portal to the Oracle Knowledge Grid
HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US
 

Home -> Community -> Usenet -> comp.databases.theory -> Re: Proper siblings sorting in nested sets model

Re: Proper siblings sorting in nested sets model

From: John Gilson <jag_at_acm.org>
Date: Tue, 27 Apr 2004 04:27:41 GMT
Message-ID: <1jljc.46077$Nn4.10021247@twister.nyc.rr.com>


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

  1. Find each sibling node S of node "a" that meets the specified ordering, e.g., all siblings less than the node "a".
  2. For each sibling node S, count the sibling node S and all of its descendants to get count C.
  3. 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)
)

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

Original text of this message

HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US