Laravel query builder for recursive results? E.g. id, parent_id

Question

So I have data structured like this:

id|parent_id|name
1 |null     |foo
2 |1        |bar
3 |2        |baz

So basically foo->bar->baz. I'm stumped on how to use laravel's query builder to get rows for a child row, then its ancestors (until parent_id == null). Can this be done with laravel? I've done a little research and Postgres has RECURSIVE while MySQL doesn't (Postgres recursive query to update values of a field while traversing parent_id).

I believe MySQL has something similar: How to do the Recursive SELECT query in MySQL?

But how would I implement this in Laravel?

My starting code is basically using a query scope, but I'm just not getting it right:

Model::select('name')->getParent(3); //get baz and the ancestors of baz
protected function scopeGetParent($id) {
  $parent = Model::where('id', '=', $id);
  return $query->getParent($parent->parent_id);
}

The desired result I want is:

name
baz
bar
foo

Any ideas?

Can't you use a recursive (php) function that asks one row of the database each time it is called? Of course there is an overhead and it's possibly less clean then to have all that in you query but have you considered it? — Gregory, Feb 25 '14 at 13:01
I guess I can write something like that but I wanted to use Laravel's awesome features and keep stuff a clean as possible. — tiffanyhwang, Feb 25 '14 at 13:07
To be honest I'm not sure this is possible (yet?). But you have intrigued me... If you happen to find anything, let us know — Gregory, Feb 25 '14 at 13:32
Come tot hink of it, have you checked raw expressions: http://laravel.com/docs/queries#raw-expressions? — Gregory, Feb 25 '14 at 13:34
Yep, I'm aware of raw expressions, it's a last resort if I run out of time. I'm looking at using a recursive `merge()` method from the `Collection` class. — tiffanyhwang, Feb 25 '14 at 13:44
Or just avoid the need for any recusion at all http://www.sitepoint.com/hierarchical-data-database/ - that way can get all children in one query — barryhunter, Feb 25 '14 at 13:58
@Gregory I might have a solution to the recursive function you said in PHP, still couldn't do it with one whole query though. — tiffanyhwang, Feb 25 '14 at 15:06

score 11 · Answer 1 · answered Feb 25 '14 at 15:03

So after fiddling around with the merge() method for the Collections class:

public static function ancestors($id)
{
    $ancestors = Model::where('id', '=', $id)->get();

    while ($ancestors->last()->parent_id !== null)
    {
      $parent = Model::where('id', '=', $ancestors->last()->parent_id)->get();
      $ancestors = $ancestors->merge($parent);
    }

    return $ancestors;
}

That will produce what I needed, however I believe it can be more cleaner so please feel free to edit it!

score 7 · Answer 2 · edited May 23 '17 at 11:53

I modified tiffanyhwang solution and turned it into a non-static method and included a attribute accessor to make it easier to get results.

public function ancestors()
{
    $ancestors = $this->where('id', '=', $this->parent_id)->get();

    while ($ancestors->last() && $ancestors->last()->parent_id !== null)
    {
        $parent = $this->where('id', '=', $ancestors->last()->parent_id)->get();
        $ancestors = $ancestors->merge($parent);
    }

    return $ancestors;
}

and accessor to retrieve a collection of ancestors from model attribute

public function getAncestorsAttribute()
{
    return $this->ancestors();
    // or like this, if you want it the other way around
    // return $this->ancestors()->reverse();
}

so now you can get ancestors like this:

$ancestors = $model->ancestors;

and since its a Collection, you can now easily do for example this:

echo $model->ancestors->implode('title',', ');

score 4 · Answer 3 · answered Feb 25 '14 at 14:03

An other way could be to use the etrepat/baum package, it's a Laravel implementation of the Nested set model. It's using an ordered tree that is faster and use non-recursive queries. While your data structured like this :

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

There are structured like this in nested set model :

 ___________________________________________________________________
|  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
|   |___________________________|   |___________________________|   |
|___________________________________________________________________|

And inserting nodes is easy as :

$child1 = $root->children()->create(['name' => 'Child 1']);

That's a great package. I'll try my best to work on a native solution before taking a look at this. Thanks. — tiffanyhwang, Feb 25 '14 at 14:13
Although this is a great package, it says itself: The drawback is that insertions/moves/deletes require complex SQL. Its quick in reading it, but very slow in altering the structure... — Gregory, Feb 25 '14 at 17:00
check out http://en.wikipedia.org/wiki/Nested_set_model for a better understanding. There is a section on performance and drawbacks too. — Gregory, Feb 25 '14 at 17:04
Nested model insertion/moves/delete is slower than a classic parent_id system but outputting a tree is way faster if the data structure is huge. — WilliamD., Feb 25 '14 at 17:12

score 2 · Answer 4 · answered Jun 06 '19 at 02:32

I've created a package that uses common table expressions (CTE) to implement recursive relationships: https://github.com/staudenmeir/laravel-adjacency-list

You can use the ancestors relationship to get all parents of a model recursively:

class YourModel extends Model
{
    use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasRecursiveRelationships;
}

$allParents = YourModel::find($id)->ancestors;

score 0 · Answer 5 · answered Dec 23 '19 at 15:57

I modified ruuter answer to use relationships. If you have a parent() belongsTo relationship on the model you can use that one to remove the where clause, see below:

public function parents()
{
        $parents = $this->parent()->get();

        while ($parents->last() && $parents->last()->parent_id !== null) {
                $parent = $parents->last()->parent()->get();
                $parents = $parents->merge($parent);
        }

        return $parents;
}

And then you can access it:

public function allParents(): Collection 
{
        return $this->parents();
}

Laravel query builder for recursive results? E.g. id, parent_id

5 Answers5

Linked