Query hierarchy in reverse

[John_A]

In it's simplest form, I have a tree hierarchy in a MySQL database where every section has both a 'sectionID' and a 'parent', both numeric values.

 

My starting point will be an array of sectionID numbers, e.g. 2, 3, 5, 8, 13, 21, 34, 55 & 89 - but this could be much larger.

 

From this array, I want to go back up the tree on each until a certain parent is hit, say for example 144 (which isn't guaranteed).

 

From this I want to create two new arrays: -

 

1) Those sectionIDs from the original list where 144 is listed as a parent somewhere higher up the hierarchy and

2) Those where 144 doesn't feature higher up the tree

 

The depth is unknown, but I'd know the end is reached when parent is either not set or is equal to 1 or 0.

 

Any help would be greatly appreciated!

Edited September 24, 2013 by John_A

[Ch0cu3r]

Are your trying to do a breadcrumb?

For example a breadcrumb menu like

Home > Tutorials > PHP > what ever

 

Home is id 0

Tutorials is id 5

PHP id 100

wahat ever is id 105

 

Then from what ever menu traverse backwards to get the parents name and display a menu?

[John_A]

Are your trying to do a breadcrumb?

 

Not really, I don't care much for the in-between stages.

 

I only need to know which ID's from a given bunch feature the given single ID (in my example 144) anywhere higher up the hierarchy, and those in which 144 doesn't feature.

Edited September 24, 2013 by John_A

[Ch0cu3r]

maybe these articles might help you

 

The following article explains how to handle/store Hierarchical Data with MySQL with example data and queries.

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

 

The article gives example with PHP code

http://www.sitepoint.com/hierarchical-data-database-2/

[John_A]

Thanks

 

I had actually just found that second one before you replied...it looks like it could be a good starting point.

 

I'm stuck with the database structure as it's an existing (third party) application and I'm querying the database, but I should be able to do something based on that...

[trq]

If you were using the nested set model this would be so much simpler, but anyway, you have described what you need to do... have you tried coding it? Where are you stuck exactly?

[John_A]

If you were using the nested set model this would be so much simpler, but anyway, you have described what you need to do... have you tried coding it? Where are you stuck exactly?

 

I was basically looking for a nod in the right direction before starting, as I want to be sure I'm doing it the most efficient way possible with what i've got.

 

The sitepoint article Ch0cu3r linked to looks like a good starting point, I'll post back with actual code if I get stuck (or think what I end up with could be improved upon)...

[vinny42]

Nested set is brilliant for finding parents and entire trees, but it is pure hell to maintain as the tree gets bigger.

 

A simple compromise is to add a new column that holds the entire path to each record, reducing the problem to a LIKE query, which may or may not be faster than recursing through the parents. (MySQL cannot index for LIKE, other databases can use TRIGRAM indexes which are designed for this purpose)

[jazzman1]

Keep in mind, that MySQL is not designed to be a hierarchical database, it's a relational database. When you're going so deeply in the hierarchically tree structure, your code will get much harder to read from you or somebody else after at time. Remember, we are human not machines and our effort should be pointed out to anyone, who can understand what's going on in the script as better as possible. I would suggest you, to take down the fetching data from MySQL and to do this in php.

[vinny42]

 

When you're going so deeply in the hierarchically tree structure, your code will get much harder to read from you or somebody else after at time.

 

That's a matter of documentation. If you don't know PHP then a PHp solution is not going to be any easier to read.

 

More to the point; is this soemthing the database should do and can do?

For MySQL the answer is no, MySQL cannot do recursion by itself, so you'll have to do the recursion in PHP. That does *not* mean that you load all records in PHP, because PHP isn't opartcularly brilliant at processing lots of data either.

For PostgeSQL the answer is yes, PostgreSQL can do a recursive selfjoin, which does exactly what is required here.

[Barand]

Rather than do a recursive search up the hierarchy for every item in the array I would do a single recursive search for all descendants of item 144 and store them in an array.

 

All you need to do then is traverse your original array and check if they are in the array of descendants.

[John_A]

Rather than do a recursive search up the hierarchy for every item in the array I would do a single recursive search for all descendants of item 144 and store them in an array.

 

All you need to do then is traverse your original array and check if they are in the array of descendants.

 

Maybe I've misunderstood, but I'm not sure this is simpler?

 

A section row only lists its parent, not any children. So the only way to find the children of any section is to query the whole sections table for results where it is given as the parent.

 

So, it seems to me, that it's just as difficult to go down the tree as up...?

[Barand]

The point is you then only need do a single recursive search and not one for each section_id in the array.

[John_A]

The point is you then only need do a single recursive search and not one for each section_id in the array.

 

But how do I find all descendants of section 144 without querying every single section and working my way up the hierarchy?

[vinny42]

 

But how do I find all descendants of section 144 without querying every single section and working my way up the hierarchy?

 

What barand is saying is that you only want to know which nodes in the supplied array are descendants of 144. So if you make an array that contains *all* descendants of 144, you can just compare the two arrays.

 

Whether this is an option depends on the size of your tree relative to the number of nodes you are looking for.

[John_A]

What barand is saying is that you only want to know which nodes in the supplied array are descendants of 144. So if you make an array that contains *all* descendants of 144, you can just compare the two arrays.

 

Whether this is an option depends on the size of your tree relative to the number of nodes you are looking for.

 

Do you mean storing this descendants array somewhere and comparing it whenever I need to? The heirarchy is dynamic and subject to change, quite how often I'm not sure, and so the comparison really needs to be done at that moment...or did you mean something else?

[vinny42]

 

 and so the comparison really needs to be done at that moment..

 

 

You would ofcourse create the array when you want to start the search.

[Zane]

... have you tried coding it? Where are you stuck exactly?

I was basically looking for a nod in the right direction before starting, as I want to be sure I'm doing it the most efficient way possible with what i've got....

Experiment first, ask questions later. It's like asking someone the best way to hold your breath underwater; you will never know for sure unless you get in the water yourself. Edited September 26, 2013 by Zane

[vinny42]

 

Experiment first, ask questions later. It's like asking someone the best way to hold your breath underwater; you will never know for sure unless you get in the water yourself. 

 

I've seen some wonderful solutions made using the "code first, ask questions later" technique. Especially because once the solution "works", there's no need to ask questions anymore.

 

So, no. Always ask before you write code. Worst case they tell you you were right, best case you get a solution that is far better than what you had in mind.

[John_A]

For the record, I wasn't expecting anyone to do this for me...as I said a nod in the right direction is all I wanted as I didn't want to waste time going down the wrong route.

 

Thanks to all for their input, here's what I have which seems to work

 

Any comments welcome... 

<?php
$targetsection=144;

$editedSectionsArray = array();
$invertedSectionsArray = array();

$fullSectionsArray = array(2,3,5,8,13,21,34,55,89);

foreach ($fullSectionsArray as &$theSection) {
	if(get_my_path($theSection,$targetsection)==true && $theSection != $targetsection) { // target section features nowhere in ancestry
		array_push($invertedSectionsArray,$theSection); 
	} else { // it is there, so add to this array instead
		array_push($editedSectionsArray,$theSection); 
	}
}

echo '<strong>Full Array:</strong><br/>';
echo '<pre>';
print_r($fullSectionsArray);
echo '</pre>';

echo '<strong>Edited Array:</strong><br/>';
echo '<pre>';
print_r($editedSectionsArray);
echo '</pre>';

echo '<strong>Inverted Array:</strong><br/>';
echo '<pre>';
print_r($invertedSectionsArray);
echo '</pre>';


// $node is the name of the node we want the path of 
function get_my_path($node,$targetsection) {
	global $tableSections;

	// look up the parent of this node
	$query = "SELECT parent FROM $tableSections WHERE sectionID = " . $node;
	$result = mysql_query($query);
	$record = mysql_fetch_assoc($result);

	// save the path in this array 
	$myPath = array(); 
	array_push($myPath,$node); 

	// only continue if this $node isn't the root node (that's the node with no parent)
	if ($record['parent'] != '' && $record['parent'] != '0') { 
		// the last part of the path to $node, is the name 
		// of the parent of $node 
		myPath[] = $record['parent'];
		if ($record['parent'] == $targetsection) $excludeThis = 1;
 
		// we should add the path to the parent of this node to the path 
		$myPath = array_merge(get_my_path($record['parent']), $myPath);
	} 
 

	// return the result
	if (isset($excludeThis)) {
		return false;
	} else {
		return true;
	}
}
?>

Edited September 26, 2013 by John_A

[John_A]

Ok, that didn't work for a number of reasons....while it seemed to on my test server, it was obviously much more tolerant of my rubbish code as the production server spat it out for numerous reasons, primarily the wrong number of arguments passed to the function in one instance, and the function didn't return an array as expected (I forgot I changed that to true / false).

 
The biggest issue was that the hierarchy seemed to fail after only going 2 generations up....?
 
Anyway, I decided to approach it slightly differently and go back to the function returning a path, then I'll compare the arrays and do what needs doing there...trouble is I've now hit a brick wall as multi-dimensional arrays aren't really a strong point of mine....
 
What I have: -
 

<?php
$targetsection=144;

$fullSectionsArray = array(1,1505,1507,1509,1510,1511);
$editedSectionsArray = array();
$invertedSectionsArray = array();
$pathsArray = array();

foreach ($fullSectionsArray as &$theSection) {
	$thispath = get_my_path($theSection);
	$pathsArray[$theSection] = $thispath;
}

print_r($pathsArray);


///////////////////////////////////////////
// what to do here to populate the other //
// 2 arrays - $editedSectionsArray and   //
// $invertedSectionsArray   ???          //
///////////////////////////////////////////

echo '<strong>Full Array:</strong><br/>';
echo '<pre>';
print_r($fullSectionsArray);
echo '</pre>';

echo '<strong>Edited Array:</strong><br/>';
echo '<pre>';
print_r($editedSectionsArray);
echo '</pre>';

echo '<strong>Inverted Array:</strong><br/>';
echo '<pre>';
print_r($invertedSectionsArray);
echo '</pre>';

// $node is the name of the node we want the path of 
function get_my_path($node) {
	global $tableSections;

    // look up the parent of this node
	$query = "SELECT parent FROM $tableSections WHERE sectionID = " . $node;
	$result = mysql_query($query);
	$record = mysql_fetch_assoc($result);

    // save the path in this array 
    $myPath = array(); 

    // only continue if this $node isn't the root node (that's the node with no parent)
    if ($record['parent'] != '' && $record['parent'] != '0' && $record['parent'] != '1') { 
        // the last part of the path to $node, is the name 
        // of the parent of $node 
        $myPath[] = $record['parent'];
 
        // we should add the path to the parent of this node to the path 
        $myPath = array_merge(get_my_path($record['parent']), $myPath);
    } 
 
    // return the result
	return $myPath;
}
?>

which produces a $pathsArray like: -
 

Array
(
    [1] => Array
        (
        )

    [1505] => Array
        (
            [0] => 1586
            [1] => 28
            [2] => 222
            [3] => 406
        )

    [1507] => Array
        (
            [0] => 1586
            [1] => 28
            [2] => 222
            [3] => 406
        )

    [1509] => Array
        (
            [0] => 28
            [1] => 222
            [2] => 406
        )

    [1510] => Array
        (
            [0] => 1586
            [1] => 28
            [2] => 222
            [3] => 406
        )

    [1511] => Array
        (
            [0] => 1586
            [1] => 28
            [2] => 222
            [3] => 406
        )

)

All I need to do now (!) is: -

 

1. add to the $editedSectionsArray, any of $pathsArray in which any value in the sub-array (if there is one) = the $targetsection (e.g. 1505, 1507, 1510 & 1511 in the above example) - taking these key numbers and adding them as values to $editedSectionsArray.
    
2. add to the $invertedSectionsArray any $pathsArray which either have no sub-arrays, or where the sub-array does not contain $targetsection (e.g. 1 & 1509 in the above example) - taking the key numers and adding them as values to $invertedSectionsArray.

 

Any pointers would be, as always, greatly appreciated.

Edited September 26, 2013 by John_A

[vinny42]

 

The biggest issue was that the hierarchy seemed to fail after only going 2 generations up....?

 

Perhaps, but no code posted = no solution given...

 

 

as multi-dimensional arrays aren't really a strong point of mine.

 

That shouldn't really matter, you don't need them to solve your problem.

 

I'll see if I can write up an example.

[John_A]

Perhaps, but no code posted = no solution given...

I posted all the code (at that time, - db stuff) in post #20? But since then I've changed my approach a little and feel I'm much closer to a solution (see above).

Edited September 26, 2013 by John_A

[vinny42]

I hate forums that use pagination :-)

 

Maybe this helps to get back to the original problem of finding the parents in a tree, under the motto of "keep it simple".

 

 

class pathFinder
{
    /**
     * @var \PDO
     */
    private $_objPDO;
 
    public function __construct($pObjPdo)
    {
        $this->_objPDO = $pObjPdo;
    }
 
    public function  findInPath($pIntStartNodeId, $pIntNodeToFind)
    {
        // Find the parentid of the supplied node, but only if the parent_id is not NULL (top of the tree)
        if (false === ($objResult = $this->_objPDO->query("SELECT parent_id FROM recurse WHERE parent_id IS NOT NULL AND id = " . $pIntStartNodeId))) {
            var_dump($this->_objPDO->errorInfo());
            exit;
        }
 
        // If nothing is found then stop.
        if (0 == $objResult->rowCount()) {
            return false;
        };
 
        // If something has been found, check if it was wat we were looking for.
        $arrRow = $objResult->fetch(\PDO::FETCH_ASSOC);
        if ($arrRow['parent_id'] == $pIntNodeToFind) {
            return true;
        }
        else {
            return $this->findInPath($arrRow['parent_id'], $pIntNodeToFind);
        }
    }
}
 
echo '<pre>';
$objDb = new \PDO('mysql:localhost', 'demouser', 'demopassword');
$objDb->query("USE demos");
$objDb->query("DROP TABLE IF EXISTS recurse");
$objDb->query("CREATE table recurse (id integer, parent_id integer)");
$objDb->query("INSERT INTO recurse (id, parent_id) VALUES (1,null),(2,1),(3,2),(4,1),(5,1),(6,5),(7,6),(8,7)");
 
$objPathFinder = new pathFinder($objDb);
// Is 4 a child of 1?
var_dump($objPathFinder->findInPath(4, 1));
// Is 40 a child of 1?
var_dump($objPathFinder->findInPath(40, 1));
// Is 4 a child of 8?
var_dump($objPathFinder->findInPath(4, );

[John_A]

I hate forums that use pagination :-)

 

Maybe this helps to get back to the original problem of finding the parents in a tree, under the motto of "keep it simple".

Thanks, but that's as far from simple as it's possible to get (for me, at least!). None of that looks remotely familiar to me, and so I'd rather not use it in case something goes wrong in future. Also, I tried dropping it in on my test server and got 500 errors / blank pages and can't really debug it myself (see previous sentence!).

 

Sorry, I really do appreciate your help, but I think I'd rather a "simple" solution I can drop in to #21

Edited September 26, 2013 by John_A