7

I have the following simplified database table structure for a legacy tickets-like system.

messages
  id         INT
  parent_id  INT
  content    TEXT
  answer     TEXT
  ...

On a list, I show all the messages. When a message is clicked, I display its answer etc.

The problem is, now I need to make a list structure of all parents and children related to this message, as well as the position of this message in the tree. How could I retrieve those from database?

I'm using Laravel, but raw SQL would also help me find the direction.

Example: 
╔════╦═══════════╦════════════════════════╦═════════════════╗
║ id ║ parent_id ║        content         ║     answer      ║
╠════╬═══════════╬════════════════════════╬═════════════════╣
║  1 ║ NULL      ║ Hi, I have a problem   ║ I can't help    ║
║  2 ║ 1         ║ The problem persists   ║ Ok, what is it? ║
║  3 ║ 2         ║ Nevermind, I got this  ║ Oh, well.       ║
║  4 ║ 3         ║ Problem is back        ║ Which problem?  ║
║  5 ║ 4         ║ The same problem again ║ ...             ║
╚════╩═══════════╩════════════════════════╩═════════════════╝

When showing message with id = 4, I should be able to display something like this list:

Message history:
- Hi, I have a problem
- The problem persists
- Nevermind, I got this
- Problem is back
- The same problem again

I could only think of a loop and several SQL query executions, for each parent and child, which looks like a code smell.

UPDATE

As stated by Daan, this question seems like a duplicate for How to create a MySQL hierarchical recursive query.

I decided to not delete it however, since Ravan just answered it with a Laravel approach that helped me solve the problem, so I'll just leave this here for future reference.

Charles
  • 1,118
  • 13
  • 23
  • Unfortunately mysql does not have something to support hierarchical query, you may need to write a recursive function to get the job done. – Abhik Chakraborty Apr 08 '15 at 14:32
  • 1
    possible duplicate of [MySQL hierarchical recursive query](http://stackoverflow.com/questions/20215744/mysql-hierarchical-recursive-query) – Daan Apr 08 '15 at 14:34
  • It really is duplicated. I couldn't think of the word "hierarchical" when searching for this. What should I do, delete this question? – Charles Apr 08 '15 at 14:40
  • I think the question is relevant, since there are solutions specific to Laravel. – Ravan Scafi Apr 08 '15 at 14:43
  • Alright, I'll edit the question's title to focus on Laravel solution, since it's my real scenario, and mention the other possible duplicate, in case it helps someone else. Thanks for your answer Ravan, it was just what I needed. – Charles Apr 08 '15 at 15:00
  • @charlesrockbass cool charles, I myself use this package too. Can you accept my answer since it provided you a solution? – Ravan Scafi Apr 08 '15 at 16:58
  • Whoops! My bad. There it is. Thanks again. – Charles Apr 08 '15 at 18:21

1 Answers1

6

Since you are doing hierarchical operations, you should use a strategy to save and retrieve this data from your database.

One approach is to use Nested Set Model, that can make it easier. Laravel has a great package that deals with it, called etrepat/baum, that also explains how it works and I quote:

The theory behind, a TL;DR version

An easy way to visualize how a nested set works is to think of a parent entity surrounding all of its children, and its parent surrounding it, etc. So this tree:

root
  |_ Child 1
    |_ Child 1.1
    |_ Child 1.2
  |_ Child 2
    |_ Child 2.1
    |_ Child 2.2

Could be visualized like this:

 ___________________________________________________________________
|  Root                                                             |
|    ____________________________    ____________________________   |
|   |  Child 1                  |   |  Child 2                  |   |
|   |   __________   _________  |   |   __________   _________  |   |
|   |  |  C 1.1  |  |  C 1.2 |  |   |  |  C 2.1  |  |  C 2.2 |  |   |
1   2  3_________4  5________6  7   8  9_________10 11_______12 13  14
|   |___________________________|   |___________________________|   |
|___________________________________________________________________|

The numbers represent the left and right boundaries. The table then might look like this:

id | parent_id | lft  | rgt  | depth | data
 1 |           |    1 |   14 |     0 | root
 2 |         1 |    2 |    7 |     1 | Child 1
 3 |         2 |    3 |    4 |     2 | Child 1.1
 4 |         2 |    5 |    6 |     2 | Child 1.2
 5 |         1 |    8 |   13 |     1 | Child 2
 6 |         5 |    9 |   10 |     2 | Child 2.1
 7 |         5 |   11 |   12 |     2 | Child 2.2

To get all children of a parent node, you

SELECT * WHERE lft IS BETWEEN parent.lft AND parent.rgt

To get the number of children, it's

(right - left - 1)/2

To get a node and all its ancestors going back to the root, you

SELECT * WHERE node.lft IS BETWEEN lft AND rgt

As you can see, queries that would be recursive and prohibitively slow on ordinary trees are suddenly quite fast. Nifty, isn't it?

Ravan Scafi
  • 6,382
  • 2
  • 24
  • 32