(1) Heirarchy: No urgency, but good question for a pro

sfullman

Every now and then someone asks a question here that isn't a request for help but just for feedback. This is one of those; if you've dealt with heirarchy this thread is meant for you.

Suppose you have a table called Posts, the primary key (auto_incrmenting int) is called ID.
Now, you have another field, also an int field, called Parent_ID. If the value is NULL or 0, this is a parent record. If the value is an integer it means this record's parent is the record with ID = the value of Parent_ID in this record.

From that, of course, it's possible to build a complete heirarchy which can be very complex.

My question is about the most efficient query to display that heirarchy. Suppose instead I had a table of Items, which can be subItems of other items in the table. I want to display this text:

GreatGrandParentItem -> GrandParentItem -> ParentItem -> CHILDITEM

If I know the ID of the item, I could run this query:

SELECT
CONCAT(
IF(d.ID>0,CONCAT(d.Name,' -> '),''),
IF(c.ID>0,CONCAT(c.Name,' -> '),''),
IF(b.ID>0,CONCAT(b.Name,' -> '),''),
a.Name
),
/* this is a way to get individual fields */
a.Name AS Name,
b.Name AS P1Name,
c.Name AS P2Name,
d.Name AS P3Name

FROM 
items a LEFT JOIN items b /*parent*/ 
ON a.Parent_ID = b.ID
LEFT JOIN items c
ON b.Parent_ID = c.ID
LEFT JOIN items d
ON c.Parent_ID = d.ID

My thoughts on this are:
1. It's cumbersome
2. It builds the query from the bottom up, instead of from the top down. This means everything has to be shifted to the left by the entry with longest number of parents. Adds complexity.
3. I can just keep adding left joins of the table for each level present. But, what if I don't know how many levels deep we go?
4. From #3, is there a way to query the table and see how many levels of heirarchy there are FIRST, if that type of left join query is my only option?

Threads on forums are a good example of this too, so if anyone has worked on a forum coding, you'd probably have some advice on this.

Like I said, this is not a "help me please thread" but just a request for feedback from the community on best techniques and theory behind heirarchical structures.

Thanks for your input,
sam fullman
compass point media

Drakla

I've done quite a few experiments with MySQL and PHP to find the most efficient methods of doing that kind of thing, and even though recursion seems lovely, I eventually wrote iterative solutions just to test if they were quicker, and they were.

To display a breadcrumb trail with exactly the same sort of heirarchy you've got I wrote this:

function show_breadcrumbs_search($categid, $linkThis=0)
{
	global $db, $areaCode, $searchWords, $searchPage, $paramString,
	 $homePage, $areaName, $catName, $thisPid, $locnWords;

$q="SELECT * FROM cats WHERE id=$categid LIMIT 1";
$db->query($q);
$row=$db->fetch_assoc();	

if($linkThis)	//link or NOT link this cat, needed for company details
	$trail=" >> <a href='$searchPage?catid=$row[id]&$paramString'>$row[name]</a>";
else
	$trail=" >> $row[name]";

$thisPid=$row['pid'];
$catName=$row['name'];

while($row['pid'])
{
	$db->query("SELECT * FROM cats WHERE id=$row[pid] LIMIT 1");
	$row=$db->fetch_assoc();

	$trail=" >> <a href='$searchPage?catid=$row[id]&$paramString'>$row[name]</a>".$trail;
}

echo "<a href='$homePage?$paramString'>HOME</a>";
echo $trail;

// print extras due to parameters	
if($searchWords) echo ' matching "'.implode(' ', $searchWords).'"';
if($locnWords) echo ' locations "'.implode(' ', $locnWords).'"';
if($areaCode)
{
	echo " in $areaName // <a href='$searchPage?catid=$categid";

	if( $searchWords) echo "&searchWords=".implode(" ", $searchWords);

	echo "'>All Areas</a>";
}
}

It's got loads of stuff in it you won't need but you sound as if you don't really need any help picking it out. To display the whole category tree I've just stuck with the recursion:

// recursive function to show children
function show_branch($catid=0)
{
	static $depth=-1;

$depth++;

$padder='';	
for($i=0;$i<$depth;$i++) $padder.="         ";

$query="SELECT * from cats WHERE pid=$catid ORDER BY name";	
$db->safe_query($query);

while( $row=$db->fetch_assoc() )
{
	$name="<a href='searchV3.php?catid=$row[id]'>$row[name]</a>";
	echo $padder.$name.'<br>';

	show_branch( $row['id'] );
	//find mah chillun
}

$db->free_result();
$db->close();

$depth--;
}

the $db-> stuff is just a cakky wrapper that I wrote so I don't have to keep track of result resources and all that guff

Sxooter

There is a SQL spec for this behavior that few databases yet support, but postgresql is working on it.

there are already two or three solutions for it in existence for pgsql, just none that are SQL compliant.

In the contrib/tablefunc directory there is a set of libs that adds something called connectby which is explained in the readme thusly:

connectby(text relname, text keyid_fld, text parent_keyid_fld
[, text orderby_fld], text start_with, int max_depth
[, text branch_delim])
- returns keyid, parent_keyid, level, and an optional branch string
and an optional serial column for ordering siblings
- requires anonymous composite type syntax in the FROM clause. See
the instructions in the documentation below.

Here's an example.

CREATE TABLE connectby_tree(keyid text, parent_keyid text, pos int);

INSERT INTO connectby_tree VALUES('row1',NULL, 0);
INSERT INTO connectby_tree VALUES('row2','row1', 0);
INSERT INTO connectby_tree VALUES('row3','row1', 0);
INSERT INTO connectby_tree VALUES('row4','row2', 1);
INSERT INTO connectby_tree VALUES('row5','row2', 0);
INSERT INTO connectby_tree VALUES('row6','row4', 0);
INSERT INTO connectby_tree VALUES('row7','row3', 0);
INSERT INTO connectby_tree VALUES('row8','row6', 0);
INSERT INTO connectby_tree VALUES('row9','row5', 0);

-- with branch, without orderby_fld
SELECT * FROM connectby('connectby_tree', 'keyid', 'parent_keyid', 'row2', 0, '~')
AS t(keyid text, parent_keyid text, level int, branch text);
keyid | parent_keyid | level | branch
-------+--------------+-------+---------------------
row2 | | 0 | row2
row4 | row2 | 1 | row2~row4
row6 | row4 | 2 | row2~row4~row6
row8 | row6 | 3 | row2~row4~row6~row8
row5 | row2 | 1 | row2~row5
row9 | row5 | 2 | row2~row5~row9

Note that connectby is a reimplementation of the same basic behaviour of the function of the same name in Oracle.

I.e. somebody's already done all this, you just need access to a postgresql server and the ability to customize it.

The tablefunc lib also adds:

normal_rand - returns a set of normally distributed float8 values

and

crosstab - returns a set of row_name plus N category value columns

sfullman

Thanx, Sxooter, I see others work with this same thing. Unfortunately I'm using MYSQL right now, but it sounds like nothing I'm doing is way out of the ballpark, with what I have.

Sam

Sxooter

This is one of the reasons I like Postgresql so much more than MySQL. It's not the innate abilities so much as the extensibility of postgresql that make it attractive. Some guy comes along, needs a recursive query ability, programs it, and it gets added.

You'll likely never see something like that in MySQL until the core developers get around to it, since very little, if any code, comes from outside the core group (an example of outside code being the innodb table type) and it doesn't have any serious stored procedure / user programmable function capabilities.

jara06

no further replies ?? deeply dissapointed 🙁

Im in need of something similar atm .. does anyone has some golden breadcrumbs ... ?

kakki

maybe you can save the full "path" into a text-field,
so you can see the "golden breadcrumbs" in one query

Sxooter

jara06 wrote:
no further replies ?? deeply dissapointed 🙁

Im in need of something similar atm .. does anyone has some golden breadcrumbs ... ?

Golden breadcrumbs:

www.postgresql.org

Together with the example given, you get a workable solution. If you're using the wrong database, then change to the right one.

MySQL is fine for most simple stuff where math isn't critical, but it's just not cut out (yet) for the bigger, heavier jobs. Maybe one day when 5.0.x is mature and 5.1 is in beta, it will have this kind of functionality. Til then, you're gonna need a different database if you want to do this kind of stuff easily, and in the db layer, not in 100 lines of php code.

thorpe

i try and flog this theory to anyone wanting to build a hierarchy. nested sets, i love them. very efficeint for retreiving data, but not so good on adding and updateing.

i am actually in the middle of building quite an extensive database abstraction layer (for sqlite) that when complete will allow nested sets of nested sets.

leatherback

Hi,

Jara: Have a look at recursion or menu in combination with my name. I am sure you will find a script somewhere on this forum