[RESOLVED] PHP/MySQL - Query that pairs hierarchical data with non-hierarchical data

[Ivarska]

The title of this thread wasn't the easiest to figure out, so it wouldn't surprise me if it's misleading.

However - I've got a MySQL table of nested set model (test_competence) containing categories where users (test_users) could pick multiple of them. The links between users and categories are located in test_list_competence.

In other words we've got three tables in total:

• test_competence(id, name, lft, rgt, parent)

• test_users(id, alias, occupation)

• test_list_competence(user, competence)

We've also got a table named test_occupation with exactly the same structure as test_competence, but this table isn't relevant at the moment.

Now let's take some example data (not required to read/understand but could simplify):

test_competence(1, "Competences", 1, 14, 0)
test_competence(2, "Languages", 2, 9, 1)
test_competence(3, "Interpreting", 3, 8, 2)
test_competence(4, "Persian", 4, 5, 3)
test_competence(5, "Arabic", 6, 7, 3)
test_competence(6, "Crafts", 10, 13, 1)
test_competence(7, "Joinery", 11, 12, 6)

test_users(32, "Peter", 56)

test_list_competence(32, 4)
test_list_competence(32, 5)
test_list_competence(32, 7)

Now we've got a user named Peter with the categories Persian, Arabic and joinery. He appears to be a pharmacist in this example.

So, on a PHP page I'd like to present the users with their categories (in this case also called "competences"). Right now I'm doing this with the following hellish query:

SELECT u.id,
u.alias,
(SELECT GROUP_CONCAT(parent.name SEPARATOR " » ") FROM test_occupation AS node, test_occupation AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.id = u.occupation AND parent.id != 1 ORDER BY parent.lft) AS occupation,
GROUP_CONCAT((SELECT GROUP_CONCAT(parent.name SEPARATOR " &raquo; ") FROM test_competence AS node, test_competence AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.id = l.competence AND parent.id != 1 ORDER BY parent.lft) SEPARATOR "<br />\n") AS competences
FROM test_users AS u,
test_list_competence AS l
WHERE u.id = l.user
GROUP BY u.id
ORDER BY u.alias;

And I could consequently present Peter's information like this:

Peter
Occupation: Pharmacist
Competences:
Languages » Interpreting » Persian
Languages » Interpreting » Arabic
Crafts » Joinery

But I want to present his information like this (the dots represents indent):

Peter
Occupation: Pharmacist
Competences:
...Languages
......Interpreting
.........Persian
.........Arabic
...Crafts
......Joinery

It's very easy to list only all the competences like this, so it shouldn't be too hard to do it together with the users, should it? Take a look at the following query that only lists all the competences:

SELECT node.id,
node.name,
node.parent,
(COUNT(parent.id) - 1) AS depth
FROM test_competence AS node,
test_competence AS parent
WHERE node.lft BETWEEN parent.lft AND parent.rgt
GROUP BY node.id
ORDER BY node.lft;

So, how do I solve this?

Thank you in advance!

[CoderDan]

would something like this work?

SELECT
test_users.id user_id,
test_users.alias,
node.id node_id,
node.name,
node.parent,
( COUNT( parent.id ) - 1 ) AS depth
FROM test_competence AS node,
test_competence AS parent
INNER JOIN test_list_competence ON test_list_competence.competence = test_competence.id
INNER JOIN test_users ON test_list_competence.user = test_users.id 
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND test_users.id = $user_id 
GROUP BY node.id
ORDER BY node.lft

- basically your latter node query with a user join and filter added on.
Should be able to run it however you handle the node only query, aside for each row will have the user info in it as well.
You could run something like this:

SELECT
node.id node_id,
node.name,
node.parent,
( COUNT( parent.id ) - 1 ) AS depth
FROM test_competence AS node,
test_competence AS parent
INNER JOIN test_list_competence ON test_list_competence.competence = test_competence.id
WHERE node.lft BETWEEN parent.lft AND parent.rgt
AND test_list_competence.user = $user_id 
GROUP BY node.id
ORDER BY node.lft

To just get the competences for the user, and a seperate query to pull teh user info, also.
It really depends on how you grind the results to generate your output.
If you LEFT JOIN the user instead of inner joining, you should get a full set of results for printing out the competences, and then you'd use php to filter out any result competence that has no user match for it. as a last step (else I assume it might not get parent info for competences that the user has down the line)

[Ivarska]

CoderDan;10921963 wrote:

would something like this work?

Hm, strange - I get the following error:

Unknown column 'test_competence.id' in 'on clause'

[CoderDan]

ahh, I copied your query, and you're aliasing tables, and i neglected to follow that pattern

[Ivarska]

But the table test_competence do exist, I don't believe you gotta alias tables to make it work. Hm, I'll try to overcome this - thanks, I'll return later.

[CoderDan]

Oh, I mean you aliased it 'node' and 'parent'. try changing the INNER (or LEFT if you change it) join to ON ON test_list_competence.competence = node.id and see if that works.

[Ivarska]

CoderDan;10921996 wrote:

Oh, I mean you aliased it 'node' and 'parent'. try changing the INNER (or LEFT if you change it) join to ON ON test_list_competence.competence = node.id and see if that works.

Yeah, I tried that as well, and apparently I get Unknown column 'node_id' in 'on clause'. Pretty weird.

By the way, what change would it be if I changed to LEFT? Havn't worked with joins very much, just simple ones.

[CoderDan]

node_id or node.id ?

[Ivarska]

CoderDan;10921999 wrote:

node_id or node.id ?

Sorry, I ment node.id. I recently tried node_id.

[CoderDan]

Well, I'm at work so I can't make the tables, but I did look over them again and realized I have a question:
What's with the lft and rgt fields - looks to me like they're a number range of id's that it's children fall inside of, and if so, why? isn't the parent field all the linkup you need? (Not saying it is, just an unusual setup to me - then again, my habit is to just use a parent ID, then query to collect all the rows, and use php to organize them into either a multidimensional array or an object structure, and then use that to print out the list with the filter based off user data or whatever, so every page that needs competencies, would have it constructed early in memory and could reuse it over and over wherever it's needed) I'm assuming your counting of the parent id to get depth is somehow related to this.

[Ivarska]

CoderDan;10922004 wrote:

Well, I'm at work so I can't make the tables, but I did look over them again and realized I have a question:
What's with the lft and rgt fields - looks to me like they're a number range of id's that it's children fall inside of, and if so, why? isn't the parent field all the linkup you need? (Not saying it is, just an unusual setup to me - then again, my habit is to just use a parent ID, then query to collect all the rows, and use php to organize them into either a multidimensional array or an object structure, and then use that to print out the list with the filter based off user data or whatever, so every page that needs competencies, would have it constructed early in memory and could reuse it over and over wherever it's needed) I'm assuming your counting of the parent id to get depth is somehow related to this.

First off - I solved the weird error about an "unknown column" with this page.

If you havn't heard of the nested set model, you must be very intelligent that realized the number range by yourself. As you mentioned, the nodes fall inside their parent with the lft and rgt values - it's very well explained here (if you scroll down a little bit).
Although, I encountered a problem once where I realized that sorting data alphabetically in a nested set model is pretty like impossible. For that reason I threw together a PHP function that uses the parent value to recreate the structure of the data. So at the moment I think that I'm mostly using it to get the depth of the nodes (as you mentioned as well). It feels pretty dumb if I'm just using it to get the depth, but in matter of performance the nested set model should be very good (if you use it properly).

I really appreciate your time.

[CoderDan]

Ahh that makes for some interesting reading, thanks 🙂
Next time I get to building a large set of static data I might just use this.
The adding/deleting while it looks like it would work seems like some nasty overhead, but otherwise it's pretty elegant.
So far I've never dealt with anything with more than a couple of hundred elements or so, and is rarely static, and for that I think using php to manage it is still the way to go, but that definatly scores a bookmark from me 🙂

Ahh, also, I just added my below sig, it's not directed at you or anyone in particular 😛

[Ivarska]

CoderDan;10922024 wrote:

Ahh that makes for some interesting reading, thanks 🙂
Next time I get to building a large set of static data I might just use this.
The adding/deleting while it looks like it would work seems like some nasty overhead, but otherwise it's pretty elegant.
So far I've never dealt with anything with more than a couple of hundred elements or so, and is rarely static, and for that I think using php to manage it is still the way to go, but that definatly scores a bookmark from me 🙂

Ahh, also, I just added my below sig, it's not directed at you or anyone in particular 😛

Yeah, I hoped you'd find it interesting. 🙂 It's better at fetching data than inputing/removing data, and I guess it's more common to fetch than input.

My problem isn't resolved yet, if that's what you ment. 😉
Your code doesn't work as I expected - I get a row for each node (no parent) with the same user info. Ex:

[user_id] => 32
[alias] => Peter
[node_id] => 7
[name] => Joinery
[parent] => 6
[depth] => 95

And the depth is pretty wrong; it should be 3 in this case I guess.

Did I ever mention that users obviously can have the same categories?

[CoderDan]

Yeah I think you'll need to use the left join, not the inner, for the user lookup, and then filter your results based on this - not sure if it'll end up exactly what you are after, but not sure you'll be able to get any closer, and it should contain all the data you need (and, unfortunately, more)

[Ivarska]

CoderDan;10922029 wrote:

Yeah I think you'll need to use the left join, not the inner, for the user lookup, and then filter your results based on this - not sure if it'll end up exactly what you are after, but not sure you'll be able to get any closer, and it should contain all the data you need (and, unfortunately, more)

Hm, I changed to LEFT JOIN and the info is still wrong. Don't you think it could be solved with subqueries, or maybe even multiple queries if we involve some PHP?

[CoderDan]

oh, doing it with multiple queries/a bit of php is easy.
You already have the queries and code to pull out a hierarchical list, as you mentioned, and I am assuming each row of that can be attributed to a test_competence id, and you have the ability to query the test_list_competence with a user filter (to get all the test_competence id's for that user) All you need to do after that is spit out the hierarchical list but only those that the user has an entry for, which is what the last query with teh left join was supposed to get.

Unless I'm wrong on what you want, and thus ov course you're not getting the data you need...

If you use the query with the left join, and spit out the same indented list, but add the user_id for each resulting row as a boolean (so it's 1 if user existed, 0 if not) would you get a list like this?:

Peter
Occupation: Pharmacist
Competences:
...Languages 0
......Interpreting 0
.........Persian 1
.........Arabic 1
......Something else perhaps 0
........Something else perhaps 0
...Crafts 0
......Joinery 1
......Something else perhaps 0

If so, can you not then hide any item that a) has no user flag AND b) either has no children or none of it's children have a user flag ?
this would then get you the indented list for the user
I'd need to look at that page you linked me about the nested set model to figure out how much would need to be grafted in to get just the result set you want, assuming it's possible, so this way gets you all teh data withe the user flagged on it where they have it, and it's just a matter of going through it and ignoring what you don't need...

anyhows, I have to go, catcha tomorrow.

[Ivarska]

I don't think looping through all the categories for each user would be effective, neither my code below; I just wrote a quick, awful-looking test to find out the possibilities, but right now it just feels like there's too many loops.

	$data_comp->table = 'test_competence';
	$data_comp->id_as_key = true;
	$data_comp->tree_fetch();
	$competences = $data_comp->fetched_tree;
	$query = 'SELECT u.id, ';
	$query .= 'u.alias, ';
	$query .= '(SELECT GROUP_CONCAT(parent.name SEPARATOR " » ") FROM test_occupation AS node, test_occupation AS parent WHERE node.lft BETWEEN parent.lft AND parent.rgt AND node.id = u.occupation AND parent.id != 1 ORDER BY parent.lft) AS occupation, ';
	$query .= 'GROUP_CONCAT(l.competence) AS competences ';
	$query .= 'FROM test_users AS u, ';
	$query .= 'test_list_competence AS l ';
	$query .= 'WHERE l.user = u.id ';
	$query .= 'GROUP BY u.id ';
	$query .= 'ORDER BY ' . $list_order;
	$result = mysql_query($query) or die(mysql_error());
	while($data = mysql_fetch_assoc($result))
	{
		$data['competences'] = explode(',', $data['competences']);
		$o .= $data['alias'] . '<br />' . "\n";
		foreach($data['competences'] as $cmp)
		{
			$tmp_arr;
			$tmp_id = $cmp;
			for($i=$competences[$cmp]['depth'];$i>0;$i--)
			{
				$tmp_arr[] = $competences[$tmp_id]['name'];
				$tmp_id = $competences[$tmp_id]['parent'];
			}
			$o .= implode(' &raquo; ', array_reverse($tmp_arr)) . ', ' . "\n";
			unset($tmp_arr);
		}
		$o .= '<br /><br />' . "\n";
	}

$competences is an array containing id, name depth and parent at the moment, but if you think it's required it could also contain lft and rgt.

Once again, thank you for the time you're spending on my problem. It would be great if you'd read that page about nested sets (if you've got the interest, of course), not to mention that it'd be easier for you to help me. 😃 It took me almost one hour to read and understand since english isn't my native language, but it was definitely worth it. 🙂

[CoderDan]

You can try something like this ( should work if you set up teh mysql and db info right, based off the table structures you first mentioned):

<?php
header( 'Content-type: text/plain' );

$link = mysql_connect( 'localhost', 'root', '' );
if ( !$link )
{
	die( 'Could not connect: '.mysql_error() );
}

mysql_select_db( 'test' ) or die( 'Could not selet DB' );

$query  = "SELECT node.id, ";
$query .= "node.name, ";
$query .= "( COUNT( parent.name ) - 1 ) depth ";
$query .= "FROM test_competence node, ";
$query .= "test_competence parent ";
$query .= "WHERE node.lft BETWEEN parent.lft AND parent.rgt ";
$query .= "GROUP BY node.name ";
$query .= "ORDER BY node.lft DESC ";

$result = mysql_query( $query ) or die( mysql_error( ) );

$last_depth = 1000;
$node_array = array();
$previous_nodes = array();

// assuming a valid data structure, we will go from bottom to top
while ( $node = mysql_fetch_assoc( $result ) )
{
	if ( $node['depth'] > $last_depth ) // new section
	{
		// put old section in placeholder
		$previous_nodes[$last_depth] = $node_array;

	// reinitialize our node_array
	$node_array = array();
}
else if ( $node['depth'] < $last_depth ) // the parent of the last nodeset
{
	$branches = array();

	if ( isset( $previous_nodes[$last_depth] ) ) // do we have other sets of nodes unassigned?
	{
		$branches = $previous_nodes[$last_depth];
		unset( $previous_nodes[$last_depth] );
	}

	if ( count( $node_array ) ) // do we have previous branches?
	{
		$branches = array_merge( $branches, $node_array );
		$node_array = array();
	}

	if ( count( $branches ) )
	{
		// optional:
		uasort( $branches, 'alphabetizeBranches' );
		$node['branches'] = $branches;
	}
}
// else is a sibling

$last_depth = $node['depth'];
$node_array[] = $node;
}

print_r( $node_array );

printCompetencyTreeBranch( $node_array[0] ); // assuming only one trunk, this seems to be necessary for the mysql structure to work...

$query = "SELECT * FROM test_users "; // only have 1 entry in my table based off your data, but this should be able to loop through all of them for you

$result = mysql_query( $query ) or die( mysql_error( ) );

while ( $user = mysql_fetch_assoc( $result ) )
{
	echo "User #$user[id]: $user[alias]\n";

$query = "SELECT competence FROM test_list_competence WHERE user = $user[id] ";

$competence_result = mysql_query( $query ) or die( mysql_error( ) );

$competence_list = array();

while ( $competence = mysql_fetch_row( $competence_result ) )
{
	$competence_list[] = $competence[0];
}

$user_competency = trimBranch( $node_array[0], $competence_list );

printCompetencyTreeBranch( $user_competency );
}

function trimBranch ( $branch, $competence_list )
{
	$branch_competence = false;

if ( isset( $branch['branches'] ) )
{
	foreach ( $branch['branches'] as $pos => $sub_branch )
	{
		if ( $competent_branch = trimBranch( $sub_branch, $competence_list ) )
		{
			$branch['branches'][$pos] = $competent_branch;
		}
		else
		{
			unset( $branch['branches'][$pos] );
		}
	}

	if ( count( $branch['branches'] ) )
	{
		return $branch;
	}
	else
	{
		unset( $branch['branches'] );
	}
}

if ( in_array( $branch['id'], $competence_list ) )
{
	return $branch;
}
else
{
	return false;
}
}

function alphabetizeBranches ( $branch_a, $branch_b )
{
	return strcmp( $branch_a['name'], $branch_b['name'] );
}

function printCompetencyTreeBranch ( $branch, $competence_filter = false )
{
	echo str_repeat( '  ', $branch['depth'] ).$branch['name']."\n";

if ( isset( $branch['branches'] ) )
{
	foreach ( $branch['branches'] as $sub_branch )
	{
		printCompetencyTreeBranch( $sub_branch, $competence_filter );
	}
}
}
?>

[Ivarska]

Cool, gonna test the code tomorrow and then tell wheter it works or not.

[Ivarska]

Sorry about the delay.
Unfortunately it doesn't seem to work. I modified it a little to avoid looped queries, here's how the code looks right now:

<?php
require_once('includes/common.php');
header( 'Content-type: text/plain' );

$database->select_db();

$query  = 'SELECT node.id, ';
$query .= 'node.name, ';
$query .= '(COUNT(parent.id) - 1) depth ';
$query .= 'FROM test_competence node, ';
$query .= 'test_competence parent ';
$query .= 'WHERE node.lft BETWEEN parent.lft AND parent.rgt ';
$query .= 'GROUP BY node.id ';
$query .= 'ORDER BY node.lft DESC';

$result = mysql_query($query) or die(mysql_error());

$last_depth = 1000;
$node_array = array();
$previous_nodes = array();

// assuming a valid data structure, we will go from bottom to top
while($node = mysql_fetch_assoc($result))
{
    if($node['depth'] > $last_depth) // new section
    {
        // put old section in placeholder
        $previous_nodes[$last_depth] = $node_array;

    // reinitialize our node_array
    $node_array = array();
}
else if ( $node['depth'] < $last_depth ) // the parent of the last nodeset
{
    $branches = array();

    if ( isset( $previous_nodes[$last_depth] ) ) // do we have other sets of nodes unassigned?
    {
        $branches = $previous_nodes[$last_depth];
        unset( $previous_nodes[$last_depth] );
    }

    if ( count( $node_array ) ) // do we have previous branches?
    {
        $branches = array_merge( $branches, $node_array );
        $node_array = array();
    }

    if ( count( $branches ) )
    {
        // optional:
        uasort( $branches, 'alphabetizeBranches' );
        $node['branches'] = $branches;
    }
}
// else is a sibling

$last_depth = $node['depth'];
$node_array[] = $node;
}

echo '----------- Competences ($node_array) -----------------------------------' . "\n";
print_r($node_array);
echo "\n";

echo '----------- Users -------------------------------------------------------' . "\n";

printCompetencyTreeBranch( $node_array[0] ); // assuming only one trunk, this seems to be necessary for the mysql structure to work...

$query = 'SELECT u.id, u.alias, GROUP_CONCAT(l.competence) AS competences FROM test_users AS u, test_list_competence AS l WHERE l.user = u.id GROUP BY u.id ORDER BY u.alias'; // only have 1 entry in my table based off your data, but this should be able to loop through all of them for you

$result = mysql_query($query) or die(mysql_error());

while ($user = mysql_fetch_assoc($result))
{
    echo "\n\nUser #$user[id]: $user[alias]\n";
		#print_r($user);
    $competence_list = explode(',', $user['competences']);

$user_competency = trimBranch( $node_array[0], $competence_list );

printCompetencyTreeBranch( $user_competency );
}

function trimBranch ( $branch, $competence_list )
{
    $branch_competence = false;

if ( isset( $branch['branches'] ) )
{
    foreach ( $branch['branches'] as $pos => $sub_branch )
    {
        if ( $competent_branch = trimBranch( $sub_branch, $competence_list ) )
        {
            $branch['branches'][$pos] = $competent_branch;
        }
        else
        {
            unset( $branch['branches'][$pos] );
        }
    }

    if ( count( $branch['branches'] ) )
    {
        return $branch;
    }
    else
    {
        unset( $branch['branches'] );
    }
}

if ( in_array( $branch['id'], $competence_list ) )
{
    return $branch;
}
else
{
    return false;
}
}

function alphabetizeBranches ( $branch_a, $branch_b )
{
    return strcmp( $branch_a['name'], $branch_b['name'] );
}

function printCompetencyTreeBranch ( $branch, $competence_filter = false )
{
    echo str_repeat( '  ', $branch['depth'] ).$branch['name']."\n";

if ( isset( $branch['branches'] ) )
{
    foreach ( $branch['branches'] as $sub_branch )
    {
        printCompetencyTreeBranch( $sub_branch, $competence_filter );
    }
}
}
?>

And this is the output:

----------- Competence ($ node_array) ------------------------------------
Array
(
     [0] => Array
         (
             [id] => 1
             [name] => Competences
             [depth] => 0
             [branches] => Array
                 (
                     [0] => Array
                         (
                             [id] => 2
                             [name] => Administration
                             [depth] => 1
                             [branches] => Array
                                 (
                                     [1] => Array
                                         (
                                             [id] => 13
                                             [name] => Tutorials
                                             [depth] => 2
                                         )

                                 [0] => Array
                                     (
                                         [id] => 4
                                         [name] => Organization
                                         [depth] => 2
                                     )

                             )

                     )

                 [1] => Array
                     (
                         [id] => 3
                         [name] => Crafts
                         [depth] => 1
                         [branches] => Array
                             (
                                 [1] => Array
                                     (
                                         [id] => 7
                                         [name] => Basketry
                                         [depth] => 2
                                     )

                                 [0] => Array
                                     (
                                         [id] => 5
                                         [name] => Joinery
                                         [depth] => 2
                                     )

                             )

                     )

             )

     )

) 

----------- Users ------------------------------------------------------------------
Competences
   Administration
     Tutorial
     Organization
   Crafts
     BASKETRY
     Organization
     Joinery


User # 1: AAA



User # 2: AAB
Competences
   Administration
     Organization
   Crafts
     Joinery


User # 3: AAC



User # 4: AAD



User # 5: AAE
Competences
   Administration
     Tutorial


User # 7: AAG
Competences
   Administration
     Organization


User # 8: AAH
Competences
   Administration
     Tutorial
   Crafts
     Joinery


User # 9: AAI



User # 10: AAJ
Competences
   Crafts
     Basketry


User # 15: AAN
Competences
   Crafts
     Joinery


User # 16: AAO
Competences
   Crafts
     Basketry


User # 17: AAP
Competences
   Administration
     Organization


User # 18: AAQ

It seems like it isn't fetching all the competences, as this is the valid list of all of them:

Competences
     Administration
         Tutorial
         Organization
     Dotkorand
         Atomic Physics
     Philosophy
     Crafts
         Basketry
         Joinery
     Language
         Interpreter
             Arabic
             Persian
             Polish