Re: recursive search

On 9/9/2016 7:01 PM, mireero wrote:
> Hello folks,
>
> I have a table of elements.
> 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:
> Is there a way to achieve this just using sql ?
>
> I hope I was clear and thanks for getting up to here,
> mireero

There is, but not with MySQL, at least easily. MySQL does not support recursive SQL.

You might be able to do it with a stored procedure; I haven't tried. When I need recursive SQL I use a database which support it (usually DB2).

Sorry.

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex_at_attglobal.net
==================