Re: recursive search

From: The Natural Philosopher <tnp_at_invalid.invalid>
Date: Sat, 10 Sep 2016 09:17:44 +0100
Message-ID: <nr0fj8$58j$1_at_news.albasani.net>

On 10/09/16 00:01, 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 did this years ago, for a multilevel kit bill of materials.

The answer is that although I could do up to N levels of recursion with a single SQL query, in the end only an application seemed able to to the fully recursive situation.

Hres the 'lets do a lot of levels in SQL' query

Select distinct
t0.name as l0,t1.name as l1,t2.name as l2,t3.name as l3 ,t4.name as l4, t0.id as i0,t1.id as i1,t2.id as i2,t3.id as i3 ,t4.id as i4, CONCAT_WS(':',t0.name,t1.name,t2.name,t3.name,t4.name) as catname, trim(product.name) as prodname, product.id from kits, product

LEFT join category as t4 on t4.id = product.category
LEFT JOIN category AS t3 ON t3.id = t4.parent
LEFT JOIN category AS t2 ON t2.id = t3.parent
LEFT join category as t1 on t1.id=t2.parent
LEFT JOIN category as t0 on t0.id=t1.parent

where kits.parent=product.id
order by catname, prodname

> I hope I was clear and thanks for getting up to here,
> mireero

-- 
“it should be clear by now to everyone that activist environmentalism 
(or environmental activism) is becoming a general ideology about humans, 
about their freedom, about the relationship between the individual and 
the state, and about the manipulation of people under the guise of a 
'noble' idea. It is not an honest pursuit of 'sustainable development,' 
a matter of elementary environmental protection, or a search for 
rational mechanisms designed to achieve a healthy environment. Yet 
things do occur that make you shake your head and remind yourself that 
you live neither in Joseph Stalin’s Communist era, nor in the Orwellian 
utopia of 1984.”

Vaclav Klaus

Received on Sat Sep 10 2016 - 10:17:44 CEST