Question about nested set extraction order

Hi again,

Some time ago I asked for a suggestion about nested set query and I had a
really valuable help, thank you again to all.
I'm developing my application using the queries managing nested set
method and I have another "curiosity" about an additional feature I would
like to have in the data result from the query. I think my "request" will
not be possible to realize, but I would try to ask. :-)

Based to this article:

http://dev.mysql.com/tech-resources/...ical-data.html

the following query will extract tree data as reported:

SELECT node.name, (COUNT(parent.name) - 1) AS depth
FROM nested_category AS node,
nested_category AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.name
ORDER BY node.lft;

+----------------------+-------+
| name | depth |
+----------------------+-------+
| ELECTRONICS | 0 |
| TELEVISIONS | 1 |
| TUBE | 2 |
| LCD | 2 |
| PLASMA | 2 |
| PORTABLE ELECTRONICS | 1 |
| MP3 PLAYERS | 2 |
| FLASH | 3 |
| CD PLAYERS | 2 |
| 2 WAY RADIOS | 2 |
+----------------------+-------+

This query order data by the "lft" field for have all the nodes ordered
in "descending" way and this is very good for "make" a tree inside a
control. I would to know if it will be possible to have another "sub-
order" insithe this data. I would like to have this data in this same
main "descending" order but, inside every "sub-level depth group" have
also ordered the name alphabetically. For use the same example I would to
have the data axtreacted ordered in the following mode:

+----------------------+-------+
| name | depth |
+----------------------+-------+
| ELECTRONICS | 0 |
| PORTABLE ELECTRONICS | 1 |
| 2 WAY RADIOS | 2 |
| CD PLAYERS | 2 |
| MP3 PLAYERS | 2 |
| FLASH | 3 |
| TELEVISIONS | 1 |
| LCD | 2 |
| PLASMA | 2 |
| TUBE | 2 |
+----------------------+-------+

Is this possible to have a query making this result? I think no, but is
better to ask to experts.
Thank you again for the help

On 3 Mar, 12:42, Maxxx <non...@nohost.xxx> wrote:
> Hi again,
>
> Some time ago I asked for a suggestion about nested set query and I had a
> really valuable help, thank you again to all.
> I'm developing my application using the queries managing nested set
> method and I have another "curiosity" about an additional feature I would
> like to have in the data result from the query. I think my "request" will
> not be possible to realize, but I would try to ask. :-)
>
> Based to this article:
>
> http://dev.mysql.com/tech-resources/...ical-data.html
>
> the following query will extract tree data as reported:
>
> SELECT node.name, (COUNT(parent.name) - 1) AS depth
> FROM nested_category AS node,
> nested_category AS parent
> WHERE node.lft BETWEEN parent.lft AND parent.rgt
> GROUP BY node.name
> ORDER BY node.lft;
>
> +----------------------+-------+
> | name | depth |
> +----------------------+-------+
> | ELECTRONICS | 0 |
> | TELEVISIONS | 1 |
> | TUBE | 2 |
> | LCD | 2 |
> | PLASMA | 2 |
> | PORTABLE ELECTRONICS | 1 |
> | MP3 PLAYERS | 2 |
> | FLASH | 3 |
> | CD PLAYERS | 2 |
> | 2 WAY RADIOS | 2 |
> +----------------------+-------+
>
> This query order data by the "lft" field for have all the nodes ordered
> in "descending" way and this is very good for "make" a tree inside a
> control. I would to know if it will be possible to have another "sub-
> order" insithe this data. I would like to have this data in this same
> main "descending" order but, inside every "sub-level depth group" have
> also ordered the name alphabetically. For use the same example I would to
> have the data axtreacted ordered in the following mode:
>
> +----------------------+-------+
> | name | depth |
> +----------------------+-------+
> | ELECTRONICS | 0 |
> | PORTABLE ELECTRONICS | 1 |
> | 2 WAY RADIOS | 2 |
> | CD PLAYERS | 2 |
> | MP3 PLAYERS | 2 |
> | FLASH | 3 |
> | TELEVISIONS | 1 |
> | LCD | 2 |
> | PLASMA | 2 |
> | TUBE | 2 |
> +----------------------+-------+
>
> Is this possible to have a query making this result? I think no, but is
> better to ask to experts.
> Thank you again for the help

Did you try adding node.name to the ORDER BY clause? If so what
happened?

On Mon, 03 Mar 2008 13:58:33 +0100, Captain Paralytic
<paul_lautman@yahoo.com> wrote:

> On 3 Mar, 12:42, Maxxx <non...@nohost.xxx> wrote:
>> Hi again,
>>
>> Some time ago I asked for a suggestion about nested set query and I had
>> a
>> really valuable help, thank you again to all.
>> I'm developing my application using the queries managing nested set
>> method and I have another "curiosity" about an additional feature I
>> would
>> like to have in the data result from the query. I think my "request"
>> will
>> not be possible to realize, but I would try to ask. :-)
>>
>> Based to this article:
>>
>> http://dev.mysql.com/tech-resources/...ical-data.html
>>
>> the following query will extract tree data as reported:
>>
>> SELECT node.name, (COUNT(parent.name) - 1) AS depth
>> FROM nested_category AS node,
>> nested_category AS parent
>> WHERE node.lft BETWEEN parent.lft AND parent.rgt
>> GROUP BY node.name
>> ORDER BY node.lft;
>>
>> +----------------------+-------+
>> | name | depth |
>> +----------------------+-------+
>> | ELECTRONICS | 0 |
>> | TELEVISIONS | 1 |
>> | TUBE | 2 |
>> | LCD | 2 |
>> | PLASMA | 2 |
>> | PORTABLE ELECTRONICS | 1 |
>> | MP3 PLAYERS | 2 |
>> | FLASH | 3 |
>> | CD PLAYERS | 2 |
>> | 2 WAY RADIOS | 2 |
>> +----------------------+-------+
>>
>> This query order data by the "lft" field for have all the nodes ordered
>> in "descending" way and this is very good for "make" a tree inside a
>> control. I would to know if it will be possible to have another "sub-
>> order" insithe this data. I would like to have this data in this same
>> main "descending" order but, inside every "sub-level depth group" have
>> also ordered the name alphabetically. For use the same example I would
>> to
>> have the data axtreacted ordered in the following mode:
>>
>> +----------------------+-------+
>> | name | depth |
>> +----------------------+-------+
>> | ELECTRONICS | 0 |
>> | PORTABLE ELECTRONICS | 1 |
>> | 2 WAY RADIOS | 2 |
>> | CD PLAYERS | 2 |
>> | MP3 PLAYERS | 2 |
>> | FLASH | 3 |
>> | TELEVISIONS | 1 |
>> | LCD | 2 |
>> | PLASMA | 2 |
>> | TUBE | 2 |
>> +----------------------+-------+
>>
>> Is this possible to have a query making this result? I think no, but is
>> better to ask to experts.
>> Thank you again for the help
>
> Did you try adding node.name to the ORDER BY clause? If so what
> happened?

That would destroy the whole ordering. lft is unique, and used for
maintaining the hierarchy. Sorting by lft first & name second would not
change a thing, sorting by name first & lft later will destory all
hierarchical information. A nested set has an explicit order, and to alter
that order still maintaining the hierarchy is quite difficult in 1 query.

The last time the exact same question was asked, this was the best answer
I could come up with:

On Fri, 01 Feb 2008 17:55:42 +0100, Rik Wasmus
<luiheidsgoeroe@hotmail.com> wrote:
> SELECT CONCAT( REPEAT(' ', COUNT(parent.name)-1), node.name) AS name,
> GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '~') as 'path',
> node.lft
> FROM nested_category AS node
> LEFT JOIN nested_category AS parent
> ON node.lft BETWEEN parent.lft AND parent.rgt
> GROUP BY node.name
> ORDER BY path,node.name;
>
> '~' is chosen because of it's high ascii value. In case of unicode /
> higher characters, this could potentially break. If the
> possibilities/character set for node.name is limited, this will work
> though.

I'm open to better suggestions, one that comes to mind are right padding
the strings with the lowest ascii character available (space probably?) to
their maximum length:

SELECT MAX(CHAR_LENGTH(name)) FROM nested_category INTO @char_length;
SELECT
CONCAT(REPEAT(' ',COUNT(parent.category_id)-1),node.name) AS name,
GROUP_CONCAT(RPAD(parent.name,@char_length,' ') ORDER BY parent.lft
SEPARATOR '') AS 'path',
COUNT(parent.category_id) -1 as 'depth',
node.lft
FROM nested_category AS node
LEFT JOIN nested_category AS parent
ON node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.category_id
ORDER BY path;
--
Rik Wasmus

On Mon, 03 Mar 2008 15:10:20 +0100, Rik Wasmus
<luiheidsgoeroe@hotmail.com> wrote:

> On Mon, 03 Mar 2008 13:58:33 +0100, Captain Paralytic
> <paul_lautman@yahoo.com> wrote:
>
>> On 3 Mar, 12:42, Maxxx <non...@nohost.xxx> wrote:
>>> Hi again,
>>>
>>> Some time ago I asked for a suggestion about nested set query and I
>>> had a
>>> really valuable help, thank you again to all.
>>> I'm developing my application using the queries managing nested set
>>> method and I have another "curiosity" about an additional feature I
>>> would
>>> like to have in the data result from the query. I think my "request"
>>> will
>>> not be possible to realize, but I would try to ask. :-)
>>>
>>> Based to this article:
>>>
>>> http://dev.mysql.com/tech-resources/...ical-data.html
>>>
>>> the following query will extract tree data as reported:
>>>
>>> SELECT node.name, (COUNT(parent.name) - 1) AS depth
>>> FROM nested_category AS node,
>>> nested_category AS parent
>>> WHERE node.lft BETWEEN parent.lft AND parent.rgt
>>> GROUP BY node.name
>>> ORDER BY node.lft;
>>>
>>> +----------------------+-------+
>>> | name | depth |
>>> +----------------------+-------+
>>> | ELECTRONICS | 0 |
>>> | TELEVISIONS | 1 |
>>> | TUBE | 2 |
>>> | LCD | 2 |
>>> | PLASMA | 2 |
>>> | PORTABLE ELECTRONICS | 1 |
>>> | MP3 PLAYERS | 2 |
>>> | FLASH | 3 |
>>> | CD PLAYERS | 2 |
>>> | 2 WAY RADIOS | 2 |
>>> +----------------------+-------+
>>>
>>> This query order data by the "lft" field for have all the nodes ordered
>>> in "descending" way and this is very good for "make" a tree inside a
>>> control. I would to know if it will be possible to have another "sub-
>>> order" insithe this data. I would like to have this data in this same
>>> main "descending" order but, inside every "sub-level depth group" have
>>> also ordered the name alphabetically. For use the same example I would
>>> to
>>> have the data axtreacted ordered in the following mode:
>>>
>>> +----------------------+-------+
>>> | name | depth |
>>> +----------------------+-------+
>>> | ELECTRONICS | 0 |
>>> | PORTABLE ELECTRONICS | 1 |
>>> | 2 WAY RADIOS | 2 |
>>> | CD PLAYERS | 2 |
>>> | MP3 PLAYERS | 2 |
>>> | FLASH | 3 |
>>> | TELEVISIONS | 1 |
>>> | LCD | 2 |
>>> | PLASMA | 2 |
>>> | TUBE | 2 |
>>> +----------------------+-------+
>>>
>>> Is this possible to have a query making this result? I think no, but is
>>> better to ask to experts.
>>> Thank you again for the help
>>
>> Did you try adding node.name to the ORDER BY clause? If so what
>> happened?
>
> That would destroy the whole ordering. lft is unique, and used for
> maintaining the hierarchy. Sorting by lft first & name second would not
> change a thing, sorting by name first & lft later will destory all
> hierarchical information. A nested set has an explicit order, and to
> alter that order still maintaining the hierarchy is quite difficult in 1
> query.
>
> The last time the exact same question was asked, this was the best
> answer I could come up with:
>
> On Fri, 01 Feb 2008 17:55:42 +0100, Rik Wasmus
> <luiheidsgoeroe@hotmail.com> wrote:
>> SELECT CONCAT( REPEAT(' ', COUNT(parent.name)-1), node.name) AS name,
>> GROUP_CONCAT(parent.name ORDER BY parent.lft SEPARATOR '~') as 'path',
>> node.lft
>> FROM nested_category AS node
>> LEFT JOIN nested_category AS parent
>> ON node.lft BETWEEN parent.lft AND parent.rgt
>> GROUP BY node.name
>> ORDER BY path,node.name;
>>
>> '~' is chosen because of it's high ascii value. In case of unicode /
>> higher characters, this could potentially break. If the
>> possibilities/character set for node.name is limited, this will work
>> though.
>
> I'm open to better suggestions, one that comes to mind are right padding
> the strings with the lowest ascii character available (space probably?)
> to their maximum length:
>
> SELECT MAX(CHAR_LENGTH(name)) FROM nested_category INTO @char_length;
> SELECT
> CONCAT(REPEAT(' ',COUNT(parent.category_id)-1),node.name) AS name,
> GROUP_CONCAT(RPAD(parent.name,@char_length,' ') ORDER BY parent.lft
> SEPARATOR '') AS 'path',
> COUNT(parent.category_id) -1 as 'depth',
> node.lft
> FROM nested_category AS node
> LEFT JOIN nested_category AS parent
> ON node.lft BETWEEN parent.lft AND parent.rgt
> GROUP BY node.category_id
> ORDER BY path;

On a side note: see the difference in counting category_id & GROUPing by
that? If you don't enforce a UNIQUE name in the table, don't group by it.
However, technically it's possible to have 2 nodes, on the same level,
with the same parent, with the same name. If that's possible in the real
table used, some more elaborate syntax is required:

SELECT MAX(CHAR_LENGTH(name)) FROM nested_category INTO @char_length;
SELECT FLOOR(LOG10(MAX(category_id))) + 1 FROM nested_category INTO
@id_length;
SELECT
CONCAT(REPEAT(' ',COUNT(parent.category_id)-1),node.name) AS name,
GROUP_CONCAT(CONCAT(RPAD(parent.name,@char_length, '
'),LPAD(parent.category_id,@id_length,'0')) ORDER BY parent.lft SEPARATOR
'') AS 'path',
COUNT(parent.category_id) -1 as 'depth',
node.lft
FROM nested_category AS node
LEFT JOIN nested_category AS parent
ON node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.category_id
ORDER BY path;

Notice we anxiously keep 1 parent portion of the path a fixed length. Not
doing so might yield unexpected results if a name of a record starts with
a number. It would be a rare condition indeed (exact same parent, and id
+ number in a name actually matching up with an id of a sibling), but it
wouldn't be the first time 'rare' conditions occured and destroyed a lot
of logic further on.
--
Rik Wasmus

Let me re-name things and remove the non-relational auto-numbering

CREATE TABLE Catalog
(product_name VARCHAR(20) NOT NULL PRIMARY KEY,
lft INTEGER NOT NULL,
rgt INTEGER NOT NULL);

INSERT INTO Catalog
VALUES
('ELECTRONICS', 1, 20),
('TELEVISIONS', 2, 9),
( 'TUBE', 3, 4),
('LCD', 5, 6),
('PLASMA', 7, 8),
('PORTABLE ELECT', 10, 19),
('MP3 PLAYERS', 11, 14),
('FLASH', 12, 13),
('CD PLAYERS', 15, 16),
('2 WAY RADIOS', 17, 18);

SELECT X.product_name, X.lvl,
ROW_NUMBER() OVER (PARTITION BY lvl ORDER BY
X.product_name) AS sorting
FROM (SELECT Children.product_name, (COUNT(Parents.product_name) -
1) AS lvl
FROM Catalog AS Children, Catalog AS Parents
WHERE Children.lft BETWEEN Parents.lft AND
Parents.rgt
GROUP BY Children.product_name) AS X (product_name,
lvl)
ORDER BY lvl, sorting;

This numbers the items horizontally across the tree:

product name lvl sorting
===========================
ELECTRONICS 0 1
PORTABLE ELECT 1 1
TELEVISIONS 1 2
2 WAY RADIOS 2 1
CD PLAYERS 2 2
LCD 2 3
MP3 PLAYERS 2 4
PLASMA 2 5

On Mon, 03 Mar 2008 20:28:19 +0100, --CELKO-- <jcelko212@earthlink.net>
wrote:

> Let me re-name things and remove the non-relational auto-numbering
>
> CREATE TABLE Catalog
> (product_name VARCHAR(20) NOT NULL PRIMARY KEY,
> lft INTEGER NOT NULL,
> rgt INTEGER NOT NULL);
>
> INSERT INTO Catalog
> VALUES
> ('ELECTRONICS', 1, 20),
> ('TELEVISIONS', 2, 9),
> ( 'TUBE', 3, 4),
> ('LCD', 5, 6),
> ('PLASMA', 7, 8),
> ('PORTABLE ELECT', 10, 19),
> ('MP3 PLAYERS', 11, 14),
> ('FLASH', 12, 13),
> ('CD PLAYERS', 15, 16),
> ('2 WAY RADIOS', 17, 18);
>
> SELECT X.product_name, X.lvl,
> ROW_NUMBER() OVER (PARTITION BY lvl ORDER BY
> X.product_name) AS sorting
> FROM (SELECT Children.product_name, (COUNT(Parents.product_name) -
> 1) AS lvl
> FROM Catalog AS Children, Catalog AS Parents
> WHERE Children.lft BETWEEN Parents.lft AND
> Parents.rgt
> GROUP BY Children.product_name) AS X (product_name,
> lvl)
> ORDER BY lvl, sorting;
>
> This numbers the items horizontally across the tree:
>
> product name lvl sorting
> ===========================
> ELECTRONICS 0 1
> PORTABLE ELECT 1 1
> TELEVISIONS 1 2
> 2 WAY RADIOS 2 1
> CD PLAYERS 2 2
> LCD 2 3
> MP3 PLAYERS 2 4
> PLASMA 2 5

According to the OP, this is not the desired result, and this particuler
order (at least as far as I see it, you left some rows out, I don't
understand your query fully) could just as easily be obtained by:

SELECT
node.name,
COUNT(parent.lft) - 1 as 'lvl'
FROM nested_category node
LEFT JOIN nested_category parent
ON node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.lft
ORDER BY lvl, node.name

Aside from not having the 'sorting' columns identical ordering, but once
again, not what the OP seems to want.

(Dropped microsoft.public.sqlserver.programming, according to it's syntax
I suspect this is actually the place it originates from, sadly my somewhat
limited news server doesn't carry it though. If someone has both, feel
free do duplicate my posts to that group... And the OP might state what
database he's actually using :) )
--
Rik Wasmus