1

I am looking for a non-recursive solution to make a MySQL query to select all of the leaf nodes (children, grandchildren etc) of a node while only knowing who the direct child of the node is.

Currently I have the following tables:

Nodes:

  • id (INT)
  • data (VARCHAR)

Relationships:

  • parentId (INT)
  • childId (INT)
  • childNodeOrder (INT)

The way I have it currently I can only select the direct child nodes of a parent node (for this example let the parent Id = 1):

SELECT * FROM  Nodes n
JOIN Relationships r ON r.childId = n.id
WHERE r.parentId = 1
ORDER BY r.childNodeOrder;

Is there any way for me to change this database around easily to not use a recursive call (on my server side code) and to be able to get all of the descendant leaves of a parent?

I so far have looked at questions like this one which would seem like a radical change, and not very easy to switch over...

Community
  • 1
  • 1
Naftali
  • 144,921
  • 39
  • 244
  • 303
  • Why are you only storing direct relationships in the table? – Esailija Nov 28 '12 at 15:57
  • @Esailija that is my question, what and how can I change my database to be more useful for what I need to do...? – Naftali Nov 28 '12 at 15:58
  • So the question is that you understand your table is screwed and need to know how to convert it to the proper closure table format? – Esailija Nov 28 '12 at 16:02
  • @Esailija yes. that is what my question is... :-\ – Naftali Nov 28 '12 at 16:02
  • It is pretty bad DB relation design, exactly because of difficulties with performing typical tree operations on your data. Probably easiest way to implement non-recursive search in hierarchical structure is to add "path" column to your table. – samuil Nov 28 '12 at 16:03
  • @samuil Actually closure table is the best solution for that afaik, he just implemented it wrong – Esailija Nov 28 '12 at 16:05
  • Generally there are multiple options. I like this overview: http://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database . Everything depends on what are most common operations that will be performed on the set. – samuil Nov 28 '12 at 16:25
  • possible duplicate of [What is the most efficient/elegant way to parse a flat table into a tree?](http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree) – Naftali Dec 12 '12 at 16:49

1 Answers1

1

See the NESTED SET data model, it probably can help here.

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Edit: since more context is needed, here are the details.

A parent node will have a left and right attributes that cover a range [left, right].

All the children nodes will be included in that range, so that:

parent.left <= child.left <= child.right <= parent.right.

All leaf nodes have a range of 1, so that left + 1 = right only for leaves.

To get all the leaves from a parent, use a where clause similar to this:

WHERE (left + 1 = right) AND (left >= parent.left) AND (right <= parent.right)

Marc Alff
  • 8,227
  • 33
  • 59
  • Answers that are links are **not** answers. Please add some context.... The way your answer is now, it is more of a _comment_. – Naftali Nov 28 '12 at 16:27
  • just sayin' the provided link in this case is actually pretty darn useful :) – tom Dec 11 '17 at 14:23