7

If I use Oracle there is the connect by keyword which can be used to create hierarchical queries. Currently I'm using MySQL on a project and I would like to know whether there is an alternative for connect by in MySQL?

I tried google but for no avail so far. What I'm trying to achieve is to fetch a tree from the database with one query. There are two tables involved:

areas and area_to_parent_join. The latter contains two ids one is area_id and the other is parent_id. So it is basically a self-join and I can create graphs using that model. In fact it is currently only used to create trees but this might change in the future. But in either case what I would like to have is just a spanning tree.

Edit: areas might have more than 1.000.000 records which makes most of the space-intensive options unfeasible.

Adam Arold
  • 29,285
  • 22
  • 112
  • 207
  • 2
    In short: no there isn't any. You'll have to write a stored procedure to traverse the hierarchy if you want to do it on db side. – peterm Oct 02 '13 at 08:16
  • 4
    You can always upgrade to Postgres ;) –  Oct 02 '13 at 08:29
  • @a_horse_with_no_name That's a good one! :) – peterm Oct 02 '13 at 08:30
  • Actually, there is no need to rely on recursive queries to navigate a hierarchy... – STT LCU Oct 02 '13 at 08:31
  • @Adam: how deep is the tree of the areas? – STT LCU Oct 02 '13 at 09:34
  • It varies but I think depth is limited to 6 or 7. – Adam Arold Oct 02 '13 at 09:40
  • possible duplicate of http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database? Long story short `CONNECT BY` is quite old Oracle's proprietary extension. The SQL standard defines recursive CTEs for this purpose. MySQL does not support neither of them. But you can avoid MySQL's limitations by changing db shema - see the link. – ibre5041 Mar 26 '15 at 16:53

2 Answers2

10

As said in comments, there isn't a short way with mysql.

BUT!

If you have the possibility to change the database structure, you can deploy a better design to handle tree-like hierarchies.

If you follow THIS TUTORIAL from Bill Karwin (HERE is the original answer which references that slideshow tutorial), you can find 4 methods used to model an hierarchical structure:

  1. Adiacency List
  2. Path Enumeration
  3. Nested sets
  4. Closure table

Now, the best model possible is the 4th one (I leave descriptions of the other 3 models to the reader), which basically needs 2 tables: one for the elements and one for the paths. In the paths table (the closure table itself), you'll store every path from each node to every descendant (not just the direct childs!).

It's suggested to save also the path length for each row, because it makes easier to query for immediate childrens in the tree.

Even if this solution requires more space, it has the best overall performance and it's really easy to use: it doesn't rely on recursive queries at all AND it will grants referential integrity for the whole dataset!

For example, to get every child of the node #4:

select a.*
from nodes a
join paths b
on a.node_id = b.descendant
where b.ancestor = 4

Another example: get all the ancestors of the node #11

select a.*
from nodes a
join paths b
on a.node_id = b.ancestor
where b.descendant = 11

need to delete the subtree of the node #6

delete from paths where descendant in
(select descendant from paths where ancestor = 6)
Community
  • 1
  • 1
STT LCU
  • 4,348
  • 4
  • 29
  • 47
  • 2
    I really like the 4th idea but the problem is that I might have 1.000.000 records. Since the closure table has `O(n^2)` worst case space complexity it means that storing all the paths for 1.000.000 records will take up 8381 terabytes of space. This is obviously not acceptable. Closure tables might work for small datasets but it does not scale well. – Adam Arold Oct 02 '13 at 08:57
  • @AdamArold I agree that the worst case is O(n^2) but it will never happen: a full closure table means that every node is connected to every other node. Is this your case? I don't think so! Since you're modeling a tree structure, O(n^2) won't ever happen. It's much, much closer to O(n) in reality. Give it a try (it even says so on the slides) – STT LCU Oct 02 '13 at 09:05
  • the "weight" of the closure table depends much more on the tree topography than on the number of nodes itself: with 10 nodes, a tree with 1 root and 9 leaves has 17 paths in the closure table, one with 1 root, 7 intermediate nodes and 2 leaves has 34 paths and one with 1 root, 8 intermediate nodes and 1 leaf has 56 paths! (note that even the worst case for a tree is very far from the teorethical worst case for the closure table: 56 vs 100 while the average is even less). – STT LCU Oct 02 '13 at 09:27
  • I think there is an error in your queries: `node` does not have a `descendant` or `ancestor` column. – Adam Arold Oct 02 '13 at 09:30
  • a full binary tree of 15 nodes has less than 50 entries in the closure table (against the theoretical worst case of 225) – STT LCU Oct 02 '13 at 09:32
  • @AdamArold sure, sorry it was a typo – STT LCU Oct 02 '13 at 09:33
  • Anyway +1 for the detailed answer. I've never heard of closure tables before. I'll wait a bit for other answers then I can accept yours. – Adam Arold Oct 02 '13 at 09:42
1

In my application, I rarely need to ask for the entire subtree. So, to get away from the big issue of o2, I use 3-deep association / closure table lookups - populating the table with ancestor - descendent only for child, parent, and grandparents. Just recognize that you get what you put in - i.e. don't query for the entire tree without a stored procedure.

dvand
  • 11
  • 3