Counting items through multiple sub-categories

[rivka]

I've been wrestling with the best way to do this: Let's say you have a table, called categories, in which you store categories. Now, here are the relevant columns in that table:

catid (category id)
pcatid (the parent category id)
category (category name)
leveldown (how many levels deep the category is)

You've got a second table called items. It has a column that stores the catid that the item belongs to.

So you've got a top level category - it has sub-categories. Each of those sub categories could have sub-categories and so on. I want to be able to count the TOTAL number of items within each category and its sub-categories. i.e. if you're at a top-level category, it should count the number of items within that category, and all it's subcategories. Does that make sense? My concern is that because it could branch off into so many sub-sub-sub-categories, that it would be a huge recursive function. Does anyone have any clever ideas on how to pull this off?

[Weedpacket]

One of the biggest performance hits would be dozens of queries to the database. But to get counts of all the subcategories under each category, subcategories, subsubcategories, etc. with a single query would be

SELECT pcatid, COUNT(DISTINCT catid)
FROM the_table
[[i]any WHERE clauses[/i]]
GROUP BY pcatid

This would give you, for each pcatid, the number of records that have that pcatid; which I take it would be the number of immediate subcategories under that parent category.

It won't say which categories are subcategories of which, of course; only how many there are. Since you probably what that for some category you might be better of just selecting all the relevant columns (pcatid and catid) into PHP with one query and then recursively going through that.
The important thing is to get the database queries out of the recursion.

[Weedpacket]

Let's dash something off:

Save wear and tear on our db: get everything we need once.

select catid, pcatid from the_table

$rows=mysql_num_rows($result);
$tree = array();
for($i=0;$i<$rows;++$i)
{	$row = mysql_fetch_array($result);
	$parent = $row['pcatid'];
	$cat = $row['catid'];
	$tree[$cat]=$parent;
}

Then (for the core of the recursive function) the number of immediate subcategories of catid $cat can be found with

count(array_keys($tree,$cat));

And if you want to know what those subcategories actually are, just leave off the count().

Dunno how you identify the root. I guess it's the one where count(array_keys()) returns 0.
However you do it, that of course is where the recursion starts. Given the catid $root:

function recurse($tree, $catid)
{	$subcats = array_keys($tree,$catid);
	$count_subcats = count($subcats);
	/*  Insert Useful Code Here */
	foreach($subcats as $subcat)
	{	recurse($tree, $subcat);
	}
}

recurse($root);

Obviously the Useful Code depends on your application; and you'd probably be wanting to get more than just raw catids. The raw one-dimensional $tree array above won't be suitable to store additional bits for each category: an associative array would be more useful - the key feature of the above is that catids are used as the $tree array's keys.