recursive search

From: mireero <mireero_at_free.fr>
Date: Sat, 10 Sep 2016 01:01:03 +0200
Message-ID: <57d33f2f$0$24777$426a74cc_at_news.free.fr>

[Quoted] Hello folks,

I have a table of elements.
[Quoted] [Quoted] Each of these elements can be a parent of another element.

For example:

"ElementA" is:
- parent of "ElementB"

• parent of "ElementC"

"ElementB" has no chidren

"ElementC" is:
- parent of "ElementD"

• parent of "ElementA"

"ElementD" is:
- parent of "ElementE"

"ElementE" has no chidren

Etc.

You can notice that "ElementC" is parent of his parent "ElementA"(unlike in real world).
So any element can be a parent of any other element (except directly himself).

We have 2 tables, one which list all the elements (table "element"), and another for relationships (table "relation"):

create database test;
use test;
create table element(id int primary key, element varchar(8)); insert into element (id,element) values (1,'ElementA'),(2,'ElementB'),(3,'ElementC'),(4,'ElementD'),(5,'ElementE'); create table relation (parent int, child int); insert into relation (parent, child) values (1,2),(1,3),(3,4),(3,1),(4,5);

mysql> select * from element;
+----+----------+
| id | element |
+----+----------+

|  1 | ElementA |
|  2 | ElementB |
|  3 | ElementC |
|  4 | ElementD |
|  5 | ElementE |

+----+----------+
5 rows in set (0.00 sec)

mysql> select * from relation;
+--------+-------+
| parent | child |
+--------+-------+

|      1 |     2 |
|      1 |     3 |
|      3 |     4 |
|      3 |     1 |
|      4 |     5 |

+--------+-------+
5 rows in set (0.00 sec)

Maybe you already have an idea of the question!

For a given element, I'd like to get all the descendants (and descendants of descendants) of this element. 2 possibilities:

• Variant 1: Getting all descendants and descendants of descendants and treating all those descendants simply as "direct" descendants (no difference between children and grandchildren and ...) For "ElementA", the result would be: "ElementB" "ElementC" "ElementD" "ElementE"
• Variant 2: Getting all descendants and descendants of descendants and keeping relationships: For "ElementA", we would have: "ElementB" "ElementC" "ElementD" "ElementE"

Either way, I don't care to know if "ElementA" is parent (or grandparent...) of himself and we need to avoid an infinite loop.

I know how to manage this with an external tool (like PHP), multiple mysql queries and recursion.
I could have a function like in:

function getChidren($element) {	// Returns array of descendants
	// getChildren() builds an array with descendants and returns it
	// Query to the database to get all children of "$element".
	// In the first call of this function (for "elementA"), that
	// ...would return "ElementB" and "ElementC".
	// So we would then call:
	// getChildren("ElementB");
	// getChildren("ElementC");
	// and so on ...

	$ret = array(		// to hold all descendants of "$element"
		$element => array()
	);
	// Query database and get descendants
	$descendants = query_db_to_get_descendants($element);
	// Loop on all descendants and find their descendants
	foreach ($descendants as $descendant) {
		// Recursion, add descendants to the array
		$ret[$element][] = getChildren($descendant);
		// Add some logic to avoid infinite loop
		// Global variable (which would need a reset
		// ...before the first call of getChildren())
		// Or some other way (add a parameter to getChildren()
		// ...with all found descendants up to now)
		// Or ...
	}
	return $ret;

}

This should return something like (for "ElementA"): array(

	'ElementA' => array(
		'ElementB' => array(),
		'ElementC' => array(
			'ElementD' => array(
				'ElementE' => array()
			)
		)
	)

)

As you guessed, this is for variant 2.

For variant 1, the returned array would be: array(

	'ElementB',
	'ElementC',
	'ElementD',
	'ElementE'

)

Now the question:
[Quoted] [Quoted] Is there a way to achieve this just using sql ?

[Quoted] I hope I was clear and thanks for getting up to here, mireero Received on Sat Sep 10 2016 - 01:01:03 CEST