MySQL category tree db sorting

I'm trying to work out what the most efficient way will be to get the
complete tree structure from top to bottom of a category tree db.
Starting with the first main branch listing it's first child branch
followed by it's children, after that the second child branch, ect. When
the first main branch is done it should start with the second main
branch, etc.

I've got a category tree db with the following columns:

cat_id - Unique id for each row
parent_id - cat_id of its parent, 0 if it has none
prev_sibling_id - cat_id of it's previous sibling, 0 if it has none
next_sibling_id - cat_id of it's next sibling, 0 if it has none.

To get the complete tree stucture from the db, is it possible to get the
sequence from top to bottom by one sql query, should the whole table be
gotten and sorted using php or does it require multiple (nested)
query's? (or a combination of both)
If all the rows are correctly sorted I can use php to determine which
position it has in the tree if I run by each row one by one.

I could at least group by parent_id but sorting in the quiry can hardly
be done because the id itself tells nothing about the position or
sequence in the tree.
If the prev_sibling=0 it could be placed first and if next_silbing=0 it
could be placed last (per parent group) but again you have no controle
over the rows in between, am I right about this so far?

What would be the best solution?

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: MySQL category tree db sorting

I'd recommend you search the PHP archives for an answer. This question comes
up a few times a year and the last time I remember seeing it, somebody (John
Holmes, I think) provided an excellent discourse on the different ways to
approach this solution.

You'll probably get other new responses with recommendations as to how to
proceed as well, but the archives should yield a wealth of information on
this issue in a relatively short period of time.

HTH,
Rich


> -----Original Message-----
> From: Age Bosma [mailto:agebosma@home.nl]
> Sent: Friday, March 19, 2004 9:48 AM
> To: php-db@lists.php.net
> Subject: [PHP-DB] MySQL category tree db sorting
>
>
> I'm trying to work out what the most efficient way will be to get the
> complete tree structure from top to bottom of a category tree db.
> Starting with the first main branch listing it's first child branch
> followed by it's children, after that the second child
> branch, ect. When
> the first main branch is done it should start with the second main
> branch, etc.
>
> I've got a category tree db with the following columns:
>
> cat_id - Unique id for each row
> parent_id - cat_id of its parent, 0 if it has none
> prev_sibling_id - cat_id of it's previous sibling, 0 if it has none
> next_sibling_id - cat_id of it's next sibling, 0 if it has none.
>
> To get the complete tree stucture from the db, is it possible
> to get the
> sequence from top to bottom by one sql query, should the
> whole table be
> gotten and sorted using php or does it require multiple (nested)
> query's? (or a combination of both)
> If all the rows are correctly sorted I can use php to determine which
> position it has in the tree if I run by each row one by one.
>
> I could at least group by parent_id but sorting in the quiry
> can hardly
> be done because the id itself tells nothing about the position or
> sequence in the tree.
> If the prev_sibling=0 it could be placed first and if
> next_silbing=0 it
> could be placed last (per parent group) but again you have no
> controle
> over the rows in between, am I right about this so far?
>
> What would be the best solution?
>
> --
> PHP Database Mailing List (http://www.php.net/)
> To unsubscribe, visit: http://www.php.net/unsub.php
>
>

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: MySQL category tree db sorting

Yes, in briefly reading your requirements, I believe the answer you want
is the "nested set" model:

Here's an article that looks right ... (quick google search)
http://www.dbazine.com/tropashko4.shtml

More information on this is contained in the "SQL for Smarties" book
(which is an excellent book) by Joe Celko. There are some other online
articles dealing with nested set -- try google.

*Also* to make your life much easier you might want to have a look at
the PEAR DB_NestedSet package. This makes the nested set queries much
simpler.

Cheers,
Hans

Age Bosma wrote:
> I'm trying to work out what the most efficient way will be to get the
> complete tree structure from top to bottom of a category tree db.
> Starting with the first main branch listing it's first child branch
> followed by it's children, after that the second child branch, ect. When
> the first main branch is done it should start with the second main
> branch, etc.
>
> I've got a category tree db with the following columns:
>
> cat_id - Unique id for each row
> parent_id - cat_id of its parent, 0 if it has none
> prev_sibling_id - cat_id of it's previous sibling, 0 if it has none
> next_sibling_id - cat_id of it's next sibling, 0 if it has none.
>
> To get the complete tree stucture from the db, is it possible to get the
> sequence from top to bottom by one sql query, should the whole table be
> gotten and sorted using php or does it require multiple (nested)
> query's? (or a combination of both)
> If all the rows are correctly sorted I can use php to determine which
> position it has in the tree if I run by each row one by one.
>
> I could at least group by parent_id but sorting in the quiry can hardly
> be done because the id itself tells nothing about the position or
> sequence in the tree.
> If the prev_sibling=0 it could be placed first and if next_silbing=0 it
> could be placed last (per parent group) but again you have no controle
> over the rows in between, am I right about this so far?
>
> What would be the best solution?

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

Re: MySQL category tree db sorting

From: "Age Bosma"

> I'm trying to work out what the most efficient way will be to get the
> complete tree structure from top to bottom of a category tree db.

Search the archives or Google for "nested sets". That's going to be the most
efficient database scheme to use. Any parent-child-relationship solution is
going to require a lot of queries when your "trees" get large.

I second the recommendation for "SQL for Smarties" by Joe Celko, too.
Excellent book.

---John Holmes...

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

RE: MySQL category tree db sorting

Remember that this is my first script, but here's how I extracted and
associated category hierarchies:

include 'c:\apache2\adodb\adodb\adodb.inc.php';
$ADODB_CACHE_DIR = 'c:\apache2\adodb\adodb-cache';
$db = &ADONewConnection( 'mysql' );
$db -> Connect( 'localhost', 'root', 'mysql', 'reach');

$sql_cats = "SELECT cat_id, cat_title FROM phpbb_categories ORDER BY
cat_id";
$sql_fora = "SELECT forum_id, cat_id, forum_name FROM phpbb_forums ORDER BY
cat_id";
$sql_topics = "SELECT forum_id, topic_id, topic_title FROM phpbb_topics
ORDER BY forum_id";

$db -> SetFetchMode( ADODB_FETCH_ASSOC );
$rs_cats = &$db -> Execute( $sql_cats );
$rs_fora = &$db -> Execute( $sql_fora );
$rs_topics = &$db -> Execute( $sql_topics );

$cat_id = "";
$forum_id = "";
$cats_inc = 1;
$fora_inc = 1;
$topics_inc = 1;

while( $cats_row = $rs_cats -> FetchNextObject() ) {
$cat_id = $cats_row -> CAT_ID;
print "" .
" ..
"style='border:none;cursor:hand;color:#000099;font-weight:60 0'>";

$rs_fora -> MoveFirst();
while( $fora_row = $rs_fora -> FetchNextObject() ) {
if( $cat_id == $fora_row -> CAT_ID ) {
$forum_id = $fora_row -> FORUM_ID;
print "
      type='text' value='+ " .
$fora_row -> FORUM_NAME . "' name='" . $fora_row ->
FORUM_NAME . "' readonly " .
"onclick='change_value( this, this.name, this.value
)' " .

"style='border:none;cursor:hand;color:#000099;font-weigth:60 0'>";
}

$rs_topics -> MoveFirst();
while( $topics_row = $rs_topics -> FetchNextObject() ) {
if(( $topics_row -> TOPIC_TITLE != "" ) && (
$forum_id == $topics_row -> FORUM_ID )){
print
"
          " .
" "onclick='change_value( this, this.name,
this.value )' " .

"style='border:none;cursor:hand;color:#000099;font-weigth:60 0'>";
}
}
}
print " ";
}
?>

I'm sure this can be refactored, but I don't know PHP well enough to
optimize it right now.

Cheers!
Mark

-----Original Message-----
From: John W. Holmes [mailto:holmes072000@charter.net]
Sent: Friday, March 19, 2004 11:42 AM
To: php-db@lists.php.net; Age Bosma
Subject: Re: [PHP-DB] MySQL category tree db sorting


From: "Age Bosma"

> I'm trying to work out what the most efficient way will be to get the
> complete tree structure from top to bottom of a category tree db.

Search the archives or Google for "nested sets". That's going to be the most
efficient database scheme to use. Any parent-child-relationship solution is
going to require a lot of queries when your "trees" get large.

I second the recommendation for "SQL for Smarties" by Joe Celko, too.
Excellent book.

---John Holmes...

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php

--
PHP Database Mailing List (http://www.php.net/)
To unsubscribe, visit: http://www.php.net/unsub.php