Tag: recursion
Nabin Nepal (Starx) database database-design mysql recursion sql
February 24, 2013

How do I structure a bunch of items that chain together in a MySQL database?

Question by HartleySan

HartleySanHartleySan

I apologize for the vagueness of my question title, but I don’t even know what to call what I’m trying to accomplish.

The best way to describe what I want is that I want to be able to chain a bunch of items together, and then (possibly) recursively find all the items that are part of any chains that contain the target item. For example, note item3 in the following chains: 

item1 => item2 => item3 => item4
item5 => item3 => item6  
item3 => item7 => item8  
item3 => item9 => item10  
item11 => item12 => item13 => item3

If a user were to do a search for item3, then I’d want all five chains above to be displayed. In other words, I want to be able to find all descendants and ancestors of item3, so that I can display the data in an HTML table (or whatever HTML structure works best).
The thing that makes this tricky is that (as shown above) any given item may have many descendants and many ancestors. As such, I’m not sure that regular recursion in MySQL would work.
I did have a look at both of the articles linked to in the top answer for the following SO thread, but I don’t think that the suggested solutions will work for my desired data structure:
Mysql recursion?

Is there any way to structure this kind of data into a MySQL DB so that with fairly easy and lightweight queries (i.e., hopefully one query per item request), I can get the information and structure I’m looking for?
Thank you very much.

Answer by Starx

StarxStarx

I have a suggestion.

Store item in the following structure.

+---------+-----------+
|   id    |    item   |
+---------+-----------+
|   1     |   item3   |
+---------+-----------+

And add the link references in the following

+---------+-----------+------------+
|  itemid |  ancestor | descendant |
+---------+-----------+------------+
|  1      |  3        | 2          |
+---------+-----------+------------+
|  1      |  5        | 7          |
+---------+-----------+------------+

Create a index on all three columns. This will enable you to add same time as many times as it appears on a chain.
Also you can query a particular item to find all its related links.

Nabin Nepal (Starx) php recursion tree
April 4, 2012

How to recursively build a <select> with unknown tree depth

Question by simone

simonesimone

I have a MySQL table with a tree data structure. The fields are _id, name and parentId. When the record hasn’t a parent, parentId defaults as 0. This way I can build an array and then recursively print each record.

The builded array looks like this:

Array
(
    [1] => Array
        (
            [parentId] => 0
            [name] => Countries
            [_id] => 1
            [children] => Array
                (
                    [2] => Array
                        (
                            [parentId] => 1
                            [name] => America
                            [_id] => 2
                            [children] => Array
                                (
                                    [3] => Array
                                        (
                                            [parentId] => 2
                                            [name] => Canada
                                            [_id] => 3
                                            [children] => Array
                                                (
                                                    [4] => Array
                                                        (
                                                            [parentId] => 3
                                                            [name] => Ottawa
                                                            [_id] => 4
                                                        )

                                                )

                                        )

                                )

                        )

                    [5] => Array
                        (
                            [parentId] => 1
                            [name] => Asia
                            [_id] => 5
                        )

                    [6] => Array
                        (
                            [parentId] => 1
                            [name] => Europe
                            [_id] => 6
                            [children] => Array
                                (
                                    [7] => Array
                                        (
                                            [parentId] => 6
                                            [name] => Italy
                                            [_id] => 7
                                        )

                                    [11] => Array
                                        (
                                            [parentId] => 6
                                            [name] => Germany
                                            [_id] => 11
                                        )

                                    [12] => Array
                                        (
                                            [parentId] => 6
                                            [name] => France
                                            [_id] => 12
                                        )

                                )

                        )

                    [8] => Array
                        (
                            [parentId] => 1
                            [name] => Oceania
                            [_id] => 8
                        )

                )

         )

 )

Printing an unordered list <ul> is very simple with recursion. Here’s the function I use:

function toUL ($arr) {

    $html = '<ul>' . PHP_EOL;

    foreach ( $arr as $v ) {

        $html.= '<li>' . $v['name'] . '</li>' . PHP_EOL;

        if ( array_key_exists('children', $v) ) {
            $html.= toUL($v['children']);
        }

    }

    $html.= '</ul>' . PHP_EOL;

    return $html;
}

But I’m stuck at printing a <select> in a tree-structured way:

Countries
-- America
---- Canada
------ Ottawa
-- Asia
-- Europe
---- Italy
---- Germany
---- France
-- Oceania

I thought to print -- as many times as the element’s depth, but I don’t know how to calculate the depth.

My question is: is it possible to build a <select> without knowing the depth?

Thank you in advance.

Answer by Starx

StarxStarx

Pass a parameter to count the iteration like $pass

function toUL ($arr, $pass = 0) {

    $html = '<ul>' . PHP_EOL;

    foreach ( $arr as $v ) {           

        $html.= '<li>';
        $html .= str_repeat("--", $pass); // use the $pass value to create the --
        $html .= $v['name'] . '</li>' . PHP_EOL;

        if ( array_key_exists('children', $v) ) {
            $html.= toUL($v['children'], $pass+1);
        }

    }

    $html.= '</ul>' . PHP_EOL;

    return $html;
}
...

Please fill the form - I will response as fast as I can!