select "chain list"

[Danny Cardonne]

hi,
i have a table that refer to itself for order
mytable
-------
id
info
parent_id

first one has parent_id=0

is there a way to do this with only one query??:

$result = mysql_query(select id,info from mytable where parent_id=0");
while (mysql_num_rows($result)==1){
print mysql_result($result,0,'info')."<br>\n";
$result = mysql_query(select id,info from mytable where
parent_id=".mysql_result($result,0,'id'));
}

i don't like the idea of having a lots of query for something that sound
really simple!

thanks
Danny

[Neo]

According to your code it seems you expect each parent to have only one
child. If that is the case why not just assign the Ids in the correct order?

Then you could simply write

SELECT info FROM mytable ORDER BY id;

"Danny Cardonne" <hey...@videotron.ca> wrote in message
news:3CFFF363...@videotron.ca...

[Andy Hassall]

MySQL doesn't have any hierarchical query extensions like Oracle's CONNECT BY,
so you'd have to either do the structuring in multiple queries and collecting it
in your host language, or fetch the lot and reorder it in an array in your host
language, or denormalise your schema to put the information into the database in
a form that can be quickly queried.

If what you've got is effectively a linked list, i.e. each row has at most one
direct parent or child, then either ensuring the IDs are ascending in the chain,
or adding a 'position in chain' field would work.

Adding a position field will cost you for updates and inserts, as in the worst
case you must update all of the records in the chain. But it helps if the
majority of access is reading the data, as there's now a way to read it all in
one go and in the right order.

This is even more true for the more general case of a tree. You need an 'order
in tree' as well as a 'depth' field, and probably a 'root of tree' field if
you've got more than one tree stored.

treetable
------------
id
parent_id
root_id
position_num
depth_num

e.g.

node1
|
+--- node2
|
+--- node3
| |
| \----node4
|
\---- node 5

Could be represented as:

id | parent_id | root_id | position_num | depth_num
----------------------------------------------------
1 | NULL | 1 | 0 | 0
2 | 1 | 1 | 1 | 1
3 | 1 | 1 | 2 | 1
4 | 3 | 1 | 3 | 2
5 | 1 | 1 | 4 | 1

So you can select your tree with root_id, ordered by position_num, indent the
output according to depth_num, and you get the tree out with a very simple
query.

Inserting a new node involves adding a new row, then adding one to position_num
in all of the nodes below it - how much work that is depends on how big your
trees get, of course, but it's still just one insert and one update.

You have to do a little more when deleting a node; you either step through the
rows below until you reach one on the same or lower depth than the first one you
deleted, or you recursively step through rows with parent_id = the id you just
deleted, and do the same for each of those rows until there are none left (in
either case, the idea is to delete the subtree belonging to the node you just
deleted). Then you have to subtract 'n' from position_num in all the ones below,
according to how many you've deleted.

Since it's denormalised, you have to be careful to make sure the operations
(which involve more than one query) take place atomically - i.e. lock the table
or use transactions. And of course you're storing more data.

Whilst this adds complexity for adding data, it greatly simplifies extracting
data - and since there's a position field, doing paging is trivial. This sort of
layout is great for message boards, where the number of reads is far greater
than the number of posts. So whether the tradeoff is worth it depends on your
data and how it's accessed.

--
Andy Hassall (an...@andyh.org) icq(5747695) http://www.andyh.org
http://www.andyhsoftware.co.uk/space | disk usage analysis tool

[Neo]

> Adding a position field will cost you for updates and inserts, as in the
worst
> case you must update all of the records in the chain. But it helps if the
> majority of access is reading the data, as there's now a way to read it
all in
> one go and in the right order.

like

update mytable set id=id+1 where id >= $insert_pos;
insert mytable (id) values ($insert_pos);

?

[Andy Hassall]

On Sat, 8 Jun 2002 01:06:59 +0600, "Neo" <neomal@_REMOVE_SPAM_ginosko.net>
wrote:

Yep. Remember to lock the tables so that the partially updated data isn't
visible in the time between the two queries.

[Danny Cardonne]

Andy Hassall wrote:
> On Sat, 8 Jun 2002 01:06:59 +0600, "Neo" <neomal@_REMOVE_SPAM_ginosko.net>
> wrote:
>
>
>>> Adding a position field will cost you for updates and inserts, as in the
>>>worst case you must update all of the records in the chain. But it helps if
>>>the majority of access is reading the data, as there's now a way to read it
>>>all in one go and in the right order.

i didn't see it that way,
it's cool!!

thanks
Danny