Mysql recursion?

Question

Consider a table like this:

   folders_table
   -----------------------
      INT id_folder
      INT id_folder_parent
      VARCHAR folder_name

Which stores a simple directory structure. How could I get all subdirectories of a directory with a single SELECT query?

Answer 1

It is possible, but you need to change your database structure; once the changes are made, you can retrieve a tree of any depth in one query. The queries are slightly more complex, but it's still pretty straightforward.

• Storing Hierarchical Data in a Database (SitePoint) - this article is step by step, very clear.
• Managing Hierarchical Data in MySQL - not as clear as the above.

Answer 2

With the table structure you have shown, this cannot be done with MySQL as it does not support recursive queries

Answer 3

With MySql/MariaDB you can use the Open Query Graph engine (http://openquery.com/graph/doc) which is a mysql plugin that lets you create a special table where you put the relationships, basically parentId and childId.

The magic is that you query this table with a special column latch depending of the value passed in the query will tell the OQGRAPH engine which command to execute. See the docs for details.

It handle not only tree (recursive 1-n relations), but graph data structures (recursive n-m relations) with weight (think for example that you want to store companies ownership, a company can have several subsidiaries and can also have several shareholders).

Answer 4

The other option is to store both the depth of the node and keep an identifier for the complete path of each node and use both of these as criteria.

The way I store XML nodes in a relational database is the following:

SELECT id,value FROM element e1
INNER JOIN element e2 ON (e2.id=e1.parent_id AND name='friend')
WHERE e1.depth>4 AND e1.path like 'root[1]/users[1]/user:dana[1]/public[1]%'

In this example, I've got a field for the node name and an interator in square brackets for duplicate nodes with the same node name at each level in the tree.

When you insert each node, you have to calculate the full path by following the parents down to the root node (parent_id IS NULL) appending each level onto an array, at the same time store the depth of the path.

It is always good in any kind of hierarchy stored in a database to have a visual representation and easy access to any path as following the tree on every request can be costly, especially with mysql which does not have any direct recursive SQL syntax.

The left/right scheme of storing nodes in a hierarchy (nested set adjacency list) is too dangerous in my mind and much more can go wrong with this kind of scheme, for one it is very complicated to manage.

Answer 5

1、create a new table. tree_folder(id, id_folder, tree_id) 2、create a new table. tree(id, tree_json)

The tree table maintain a whole tree node. For example, the following tree with a root node 1.

{
    "folder_id": 1,
    "parent_folder_id": 0,
    "children": [
      {
          "folder_id": 10,
          "parent_folder_id": 1,
          "children": null
      },
      {
          "folder_id": 11,
          "parent_folder_id": 2,
          "children": null
      }
    ]
}

The table contains this row.

[id, tree_json]
[1, "xxxxx"]

Then maintain the relation between the node and tree. As you can see the tree contains the node 1, 10, 11. Then we have the table tree_folder.

[id, folder_id, tree_id]
[1,  1        ,  1]
[2,  10       , 1]
[3,  11       , 1]

When you need get the folder 10's tree. just get from the tree, then deal it in you program.

In this way, you just do recursion in memory instead of mysql.

That is you should maintain the structure when write the data, but the query is easy and fast. If the query is frequent, this works fine. But if the write is frequent, just use a cache instead of this method.