[Competion Questions] Recursive SQL?

[Guest Anonymous]

This is a slightly unusual question that is designed to test your skills at thinking ahead and choosing the correct tools for the job.

Basically, the question is, given a possible large set of forums (say CE forums), how can we easily compute the total number of topics / posts on a per board basis *including* child forums?

The sample data has a simplified set of forums laid at as follows:

 

Forum                               Topics       Posts
------------------------------  ----------  ----------
Programmers and Webdev Zone              0           0
PHP/MySQL                               39         295
MySQL                                   13         141
Beginning PHP                            2          15
PHP FAQs                                19          98
PHP Databases                            1           1
PHP How-To                               3          39
Pro PHP                                  0           0
Moderated Pro PHP                        1          12
Pro Discussion                           3           7
Competition Questions                    2           0
Answered Questions                       1           2

 

Now, what want to display is aggregated totals for each board:

 

Forum                               Topics       Posts
------------------------------  ----------  ----------
Programmers and Webdev Zone             81         608
 PHP/MySQL                             81         608
   MySQL                               13         141
   Beginning PHP                        2          15
   PHP FAQs                            19          98
   PHP Databases                        1           1
   PHP How-To                           3          39
   Pro PHP                              0           0
   Moderated Pro PHP                    4          19
     Pro Discussion                     3           7
Competition Questions                    3           2
 Answered Questions                     1           2

 

Your challenge is to implement a suitable routine to display the data with the correct aggregated totals. You may use any method you can think of, language is of course PHP.

Sample Data suitable for phpMyAdmin

CREATE TABLE IF NOT EXISTS `sample`
(
`ID` int(10) unsigned NOT NULL,
`Parent` int(10) unsigned NOT NULL,
`Name` varchar(50) NOT NULL,
`Topics` int(10) unsigned NOT NULL DEFAULT '0',
`Posts` int(10) unsigned NOT NULL DEFAULT '0',

PRIMARY KEY (`ID`)
)
ENGINE=MyISAM;

INSERT INTO `sample` (`ID`, `Parent`, `Name`, `Topics`, `Posts`) VALUES
(1, 0, 'Programmers and Webdev Zone', 0, 0),
(2, 1, 'PHP/MySQL', 39, 295),
(3, 2, 'MySQL', 13, 141),
(4, 2, 'Beginning PHP', 2, 15),
(5, 2, 'PHP FAQs', 19, 98),
(6, 2, 'PHP Databases', 1, 1),
(7, 2, 'PHP How-To', 3, 39),
(8, 2, 'Pro PHP', 0, 0),
(9, 2, 'Moderated Pro PHP', 1, 12),
(10, 9, 'Pro Discussion', 3, 7),
(11, 0, 'Competition Questions', 2, 0),
(12, 11 'Answered Questions', 1, 2)
 ;

 

(Edited to fix the parent of the Answered Questions forum)

[Floydian]

Re: [Competion Questions] Recursive SQL?

I give up lol

Tried it out, came close and no cigar.

If there were money involved, I'd slog it out hehehe

[Guest Anonymous]

Re: [Competion Questions] Recursive SQL?

Glad you tried, there's a couple in IRC have been giving it some thought, but I'll leave it a couple of days till I post my suggestion for the preferred solution.

It's actually a lot easier than you think ;)

[Spudinski]

Re: [Competion Questions] Recursive SQL?

I have also tried, but haven't succeeded.

I get to the point where it reconizes that it has child boards, and print them.

But I have a problem assinging the correct child boards to the correct boards.

Here is a raw array that my script produced:

Array
(
   [Programmers and Webdev Zone] => Array
       (
           [php/MySQL] => Array
               (
               )

       )

   [php/MySQL] => Array
       (
           [0] => MySQL
           [1] => Beginning PHP
           [2] => PHP FAQs
           [3] => PHP Databases
           [4] => PHP How-To
           [5] => Pro PHP
           [Moderated Pro PHP] => Array
               (
               )

       )

   [Moderated Pro PHP] => Array
       (
           [0] => Pro Discussion
       )

   [Competition Questions] => Array
       (
       )

   [Answered Questions] => Array
       (
       )

)

 

Here is my current script if anyone wondered:

<?php
mysql_selectdb('test', $connection);
$depth = 8;

function get_childboards() {
global $connection,  $posts, $topics, $names, $depth, $last_id, $q;
$query_txt = 'SELECT * FROM `forums` WHERE `Parent` = \'' . $last_id . '\'';
$query = mysql_query($query_txt);
while($c = mysql_fetch_assoc($query)) {
	$query2_txt = 'SELECT * FROM `forums` WHERE `Parent` = \'' . $c['ID'] . '\'';
	$query2 = mysql_query($query2_txt);
	$posts[$q['Name']] += $c['Posts'];
	$topics[$q['Name']] += $c['Topics'];
	if (mysql_num_rows($query2) != 0) {
		$names[$q['Name']][$c['Name']] = array();
		$q = $c;
		$alt = $c['Name'];
	}
	else if(!empty($alt)) {
		$posts[$q['Name']][$alt] = $c['Posts'];
		$topics[$q['Name']][$alt] = $c['Topics'];
	}
	else {
		$names[$q['Name']][] = $c['Name'];
		$posts[$c['Name']] = $c['Posts'];
		$topics[$c['Name']] = $c['Topics'];
	}
	$last_id = $c['ID'];
}
$depth--;
}	
echo '<table><tr><th>Forum</th><th>Topics</th><th>Posts</th></tr>';
$query_txt = 'SELECT * FROM `forums` WHERE `Parent` = 0';
$query = mysql_query($query_txt);
while($q = mysql_fetch_assoc($query)) {
$posts[$q['Name']] = $q['Posts'];
$topics[$q['Name']] = $q['Topics'];
$names[$q['Name']] = array();
$last_id = $q['ID'];
while($depth != 0) get_childboards($q);
}
foreach($names as $name => $array) {
echo '<tr><td>[-]' . $name . '</td><td>' . $topics[$name] . '</td><td>' . $posts[$name] . '</td></tr>';
foreach($array as $cname) {
	if (!is_array($cname)) echo '<tr><td>[+]' . $cname . '</td><td>' . $topics[$cname] . '</td><td>' . $posts[$cname] . '</td></tr>';
}	
//while(!is_array($array[0][0])) print_childboards($array);
}
echo '</table>';
?>

[Guest Anonymous]

Re: [Competion Questions] Recursive SQL?

Excellent, whilst that doesn't quite work, it does demonstrate one particular technique. Good try.

[Floydian]

Re: [Competion Questions] Recursive SQL?

 

<?php
require_once(); // Database file
require_once(); // function file

/*
query() = mysql_query()
fa() = mysql_fetch_array()
Yes, I'm lazy and can't be bothered typing the whole thing out, so I made functions to shorten the name.
*/

function counter_adder($child, $parent) {

global $forum_count, $forum_data;
foreach ($forum_data as $forum_id => $data) {
	if ($forum_id == $parent) {
		$forum_count[$forum_id]['topics'] += $forum_data[$child]['topics'];
		$forum_count[$forum_id]['posts'] += $forum_data[$child]['posts'];
		counter_adder($child, $data['parent']);
	}
}


}

$q_get = sprintf('select ID, Parent, Name, Topics, Posts from sample');
$q_get = query($q_get);
$forum_count = array();
$forum_data = array();
while (list($id, $parent, $name, $topics, $posts) = fa($q_get)) {
$forum_count[$id] = array('topics' => 0, 'posts' => 0);
$forum_data[$id] = array('name' => $name, 'topics' => $topics, 'posts' => $posts, 'parent' => $parent);
}


foreach ($forum_data as $forum_id => $data) {
$forum_count[$forum_id]['topics'] += $forum_data[$forum_id]['topics'];
$forum_count[$forum_id]['posts'] += $forum_data[$forum_id]['posts'];
counter_adder($forum_id, $data['parent']);
}

echo "<table>\n";
foreach ($forum_data as $forum_id => $data) {
echo <<<EOT
<tr>
	<td>
	{$data['name']}
	</td>
	<td>
	{$forum_count[$forum_id]['topics']}
	</td>
	<td>
	{$forum_count[$forum_id]['posts']}
	</td>
</tr>\n
EOT;
}
echo '</table>';

?>

[Guest Anonymous]

Re: [Competion Questions] Recursive SQL?

Excellent Floydian - you overstepped the issue of recursively querying the database.

This is in fact the whole crux of the problem. SQL (at least on most common databases) does not have the ability to recurse.

Make a call to select data in either a tight loop or in a recursive function is always a bad idea. SELECT the data you need first, then manipulate it.

For reference, here is my sample code:

 

<?php

// Step #1 retrieve the data

// change these to suit....
$db_host     = "localhost";
$db_username = "competitor";
$db_password = "2srYYc6nq6uVW9f6";
$db_database = "competitions";
$db_handle   = mysql_connect($db_host, $db_username, $db_password);

mysql_select_db($db_database, $db_handle);

$sql  = "SELECT * FROM forums";		// let's keep it simple ...
$rs   = mysql_query($sql);
$rows = array();

while ($row = mysql_fetch_assoc($rs))
$rows[] = $row;

mysql_free_result($rs);
mysql_close($db_handle);

// Step #2 print the initial data

echo "<pre>";
echo "[b]Initial data[/b]

";
echo "ID  Parent  Forum                               Topics       Posts
";
echo "--  ------  ------------------------------  ----------  ----------
";

foreach ($rows as $row)
echo sprintf("%2u  %6u  %-30s  %10s  %10s
", $row['ID'], $row['Parent'], $row['Name'], number_format($row['Topics']), number_format($row['Posts']));

echo "</pre>";

// Step #3 recursively collate the data

function make_tree( $forums, $parent = 0, $depth = 0 )
{
$result = array();

foreach ($forums as $forum)
{
	if ($forum['Parent'] == $parent)
	{
		// set the depth of this forum (only used to make things pretty)

		$forum['Depth']    = $depth;

		// collect the child forums

		$forum['Children'] = make_tree($forums, $forum['ID'], $depth + 1);

		// aggregate the child counters

		foreach ($forum['Children'] as $child)
		{
			$forum['Topics'] += $child['Topics'];
			$forum['Posts']  += $child['Posts'];
		}

		// store the result

		$result[] = $forum;
	}
}

return $result;
}

$tree = make_tree($rows);

// Step #4 print the result

function recursive_print( $forums )
{
foreach ($forums as $forum)
{
	echo sprintf
	(
		"%2u  %6u  %-30s  %10s  %10s
",

		$forum['ID'],
		$forum['Parent'],

		str_repeat("  ", $forum['Depth']) . $forum['Name'],
		number_format($forum['Topics']),
		number_format($forum['Posts'])
	);

	if (count($forum['Children']))
		recursive_print($forum['Children']);
}				
}

echo "<pre>";
echo "[b]Final data[/b]

";
echo "ID  Parent  Forum                               Topics       Posts
";
echo "--  ------  ------------------------------  ----------  ----------
";

recursive_print($tree);

echo "</pre>";

// Step #5 print the tree for reference

echo "<pre>";
echo "[b]Tree[/b]

";
print_r($tree);
echo "</pre>";

?>

[Floydian]

Re: [Competion Questions] Recursive SQL?

;)

Now we apply a timer to see how's script runs faster!

And yours was faster. Comparing the low end of the resulting script execution times, yours was about 2 milliseconds faster.

Naturally I commented out Step #2 print the initial data and Step #5 print the tree for reference in your your code.

I can live with that difference in time lol

[Guest Anonymous]

Re: [Competion Questions] Recursive SQL?

Interesting - not sure - we are both using recursion and I never bothered to optimize mine

[me=Nyna]slopes off to optimize the code and slap the data into a memory table :-" ;)[/me]

[Floydian]

Re: [Competion Questions] Recursive SQL?

No no no, no need to optimize honey... lol