How to query graph/hierarchical data in mysql

3
votes

Suppose I have a table of objects structured in a hierarchy:

A
|--B
|--C
|  +--D
+--E

They are stored in a "parent-child" table thus:

parent  child
A       B
A       C
C       D
A       E

How do I query this to get the structure defined above? I think I need something that produces info like this:

object  full_path
A       NULL
B       A
C       A
D       A.C
E       A

I cannot figure out how to do the objects nested more than one level deep. It feels like I might need to iterate over the table (no idea if this is possible in SQL), or otherwise use some kind of query I've never encountered before.

Additional Info:

  1. A need not be the only orphan object.
  2. Children may have multiple parents BUT for now I'm happy with an answer to whichever scenario is easier to solve. I can abide converting a multi-parent structure to a single parent with a simple GROUP BY and MIN statement.
5
mysqldatabasegraphrelational-databasehierarchy
Do all items have only one parent, does the data have a single head (i.e. only A has no parent and all items are descended from A) and in the middle table, does A have a record that says it has no parent? – joocer
see edits. A does not have record that says it has no parent, but this can be determined with a simple left join query. – cammil

5 Answers

4
votes

The other answers are correct, there is no recursive functionality in mysql. This link describes how to approach hierarchies in mysql: http://explainextended.com/2009/03/17/hierarchical-queries-in-mysql/

I found the link on two other SO questions: How to do MySQL Looped Join which tests if results are complete? and Hierarchical Data in MySql .

0
votes

MySQL does not support recursive queries. But if you can use a Nested Set which simplifies fetching subtrees.

0
votes

You cannot do it with mysql because mysql doesn't support recursive functions but if you doesn't need unlimited depth you can use self joins to get the tree. Otherwise you need a recursive function in a programming language or you can use a nested-set which makes it easier to pick subtrees.

0
votes

Basically this will not work!

You need to have a definition for root nodes. And by the way your "tree" doesn't match your hierary definition.

This would be a better approach:

parent  child
-       A
A       B
A       C
C       D
-       E

The minus parent entries are root nodes. And this reflects your tree.

Sql does not offer hierarchy queries. But you can iterate whith a trick:

A good explanation can be found here:

I would try to find root nodes and use a recursion to concat the text.

root nodes will be:

SELECT * FRON objects WHERE parent = '-'
-1
votes

If u have a key (varchar)m u can sort by it. The key values would look like:

001
001.001
001.001.001
001.001.002
001.001.003
002
002.001
002.001
003
003.001
...
...