staudenmeir / laravel-adjacency-list
Recursive Laravel Eloquent relationships with CTEs
Fund package maintenance!
paypal.me/JonasStaudenmeir
Installs: 2 656 310
Dependents: 21
Suggesters: 0
Security: 0
Stars: 1 384
Watchers: 25
Forks: 111
Open Issues: 3
Requires
- php: ^8.2
- illuminate/database: ^11.0
- staudenmeir/eloquent-has-many-deep-contracts: ^1.2
- staudenmeir/laravel-cte: ^1.11
Requires (Dev)
- barryvdh/laravel-ide-helper: ^3.0
- harrygulliford/laravel-firebird: ^3.3
- larastan/larastan: 2.9.8
- mockery/mockery: ^1.5.1
- orchestra/testbench: ^9.0
- phpunit/phpunit: ^11.0
- singlestoredb/singlestoredb-laravel: ^1.5.4
- staudenmeir/eloquent-has-many-deep: ^1.20
Suggests
- barryvdh/laravel-ide-helper: Provide type hints for attributes and relations.
- dev-main
- v1.23.1
- v1.23
- v1.22.2
- v1.22.1
- v1.22
- v1.21
- 1.20.x-dev
- v1.20.1
- v1.20
- v1.19
- v1.18
- v1.17
- v1.16
- v1.15
- v1.14
- v1.13.11
- v1.13.10
- v1.13.9
- v1.13.8
- v1.13.7
- v1.13.6
- v1.13.5
- v1.13.4
- v1.13.3
- v1.13.2
- v1.13.1
- v1.13
- 1.12.x-dev
- v1.12.11
- v1.12.10
- v1.12.9
- v1.12.8
- v1.12.7
- v1.12.6
- v1.12.5
- v1.12.4
- v1.12.3
- v1.12.2
- v1.12.1
- v1.12
- v1.11.4
- v1.11.3
- v1.11.2
- v1.11.1
- v1.11
- v1.10.3
- v1.10.2
- v1.10.1
- v1.10
- 1.9.x-dev
- v1.9.6
- v1.9.5
- v1.9.4
- v1.9.3
- v1.9.2
- v1.9.1
- v1.9
- v1.8
- v1.7.1
- v1.7
- v1.6.1
- v1.6
- 1.5.x-dev
- v1.5.1
- v1.5
- v1.4.1
- v1.4
- 1.3.x-dev
- v1.3.3
- v1.3.2
- v1.3.1
- v1.3
- v1.2.3
- v1.2.2
- v1.2.1
- v1.2
- 1.1.x-dev
- v1.1.5
- v1.1.4
- v1.1.3
- v1.1.2
- v1.1.1
- v1.1
- 1.0.x-dev
- v1.0.4
- v1.0.3
- v1.0.2
- v1.0.1
- v1.0
- dev-firebird-tests
- dev-sqlsrv-varchar
- dev-TODO
This package is auto-updated.
Last update: 2024-12-19 21:25:58 UTC
README
This Laravel Eloquent extension provides recursive relationships for trees and graphs using common table expressions (CTE).
Compatibility
- MySQL 8.0+
- MariaDB 10.2+
- PostgreSQL 9.4+
- SQLite 3.8.3+
- SQL Server 2008+
- SingleStore 8.1+ (only trees)
- Firebird
Installation
composer require staudenmeir/laravel-adjacency-list:"^1.0"
Use this command if you are in PowerShell on Windows (e.g. in VS Code):
composer require staudenmeir/laravel-adjacency-list:"^^^^1.0"
Versions
Usage
The package offers recursive relationships for traversing two types of data structures:
Trees: One Parent per Node (One-to-Many)
Use the package to traverse a tree structure with one parent per node. Use cases might be recursive categories, a page hierarchy or nested comments.
Supports Laravel 5.5+.
- Getting Started
- Included Relationships
- Trees
- Filters
- Order
- Depth
- Path
- Custom Paths
- Nested Results
- Initial & Recursive Query Constraints
- Additional Methods
- Custom Relationships
- Deep Relationship Concatenation
- Known Issues
Getting Started
Consider the following table schema for hierarchical data in trees:
Schema::create('users', function (Blueprint $table) { $table->id(); $table->unsignedBigInteger('parent_id')->nullable(); });
Use the HasRecursiveRelationships
trait in your model to work with recursive relationships:
class User extends Model { use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasRecursiveRelationships; }
By default, the trait expects a parent key named parent_id
. You can customize it by overriding getParentKeyName()
:
class User extends Model { public function getParentKeyName() { return 'parent_id'; } }
By default, the trait uses the model's primary key as the local key. You can customize it by
overriding getLocalKeyName()
:
class User extends Model { public function getLocalKeyName() { return 'id'; } }
Included Relationships
The trait provides various relationships:
ancestors()
: The model's recursive parents.ancestorsAndSelf()
: The model's recursive parents and itself.bloodline()
: The model's ancestors, descendants and itself.children()
: The model's direct children.childrenAndSelf()
: The model's direct children and itself.descendants()
: The model's recursive children.descendantsAndSelf()
: The model's recursive children and itself.parent()
: The model's direct parent.parentAndSelf()
: The model's direct parent and itself.rootAncestor()
: The model's topmost parent.rootAncestorOrSelf()
: The model's topmost parent or itself.siblings()
: The parent's other children.siblingsAndSelf()
: All the parent's children.
$ancestors = User::find($id)->ancestors; $users = User::with('descendants')->get(); $users = User::whereHas('siblings', function ($query) { $query->where('name', 'John'); })->get(); $total = User::find($id)->descendants()->count(); User::find($id)->descendants()->update(['active' => false]); User::find($id)->siblings()->delete();
Trees
The trait provides the tree()
query scope to get all models, beginning at the root(s):
$tree = User::tree()->get();
treeOf()
allows you to query trees with custom constraints for the root model(s). Consider a table with multiple
separate lists:
$constraint = function ($query) { $query->whereNull('parent_id')->where('list_id', 1); }; $tree = User::treeOf($constraint)->get();
You can also pass a maximum depth:
$tree = User::tree(3)->get(); $tree = User::treeOf($constraint, 3)->get();
You can also chaperone tree relationships to load ancestors
and parent
relationships already present in the tree to
(potentially) reduce N+1 queries:
$users = User::tree(3)->get(); $users->loadTreeRelationships();
Or with toTree()
:
$users = User::tree(1)->get(); $tree = $users->loadTreeRelationships()->toTree();
Filters
The trait provides query scopes to filter models by their position in the tree:
hasChildren()
: Models with children.hasParent()
: Models with a parent.isLeaf()
/doesntHaveChildren()
: Models without children.isRoot()
: Models without a parent.
$noLeaves = User::hasChildren()->get(); $noRoots = User::hasParent()->get(); $leaves = User::isLeaf()->get(); $leaves = User::doesntHaveChildren()->get(); $roots = User::isRoot()->get();
Order
The trait provides query scopes to order models breadth-first or depth-first:
breadthFirst()
: Get siblings before children.depthFirst()
: Get children before siblings.
$tree = User::tree()->breadthFirst()->get(); $descendants = User::find($id)->descendants()->depthFirst()->get();
Depth
The results of ancestor, bloodline, descendant and tree queries include an additional depth
column.
It contains the model's depth relative to the query's parent. The depth is positive for descendants and negative for ancestors:
$descendantsAndSelf = User::find($id)->descendantsAndSelf()->depthFirst()->get(); echo $descendantsAndSelf[0]->depth; // 0 echo $descendantsAndSelf[1]->depth; // 1 echo $descendantsAndSelf[2]->depth; // 2
Change the column name by overriding getDepthName()
if your table already contains a depth
column:
class User extends Model { public function getDepthName() { return 'depth'; } }
Depth Constraints
You can use the whereDepth()
query scope to filter models by their relative depth:
$descendants = User::find($id)->descendants()->whereDepth(2)->get(); $descendants = User::find($id)->descendants()->whereDepth('<', 3)->get();
Queries with whereDepth()
constraints that limit the maximum depth still build the entire (sub)tree internally.
Use withMaxDepth()
to set a maximum depth that improves query performance by only building the requested section of
the tree:
$descendants = User::withMaxDepth(3, function () use ($id) { return User::find($id)->descendants; });
This also works with negative depths (where it's technically a minimum):
$ancestors = User::withMaxDepth(-3, function () use ($id) { return User::find($id)->ancestors; });
Path
The results of ancestor, bloodline, descendant and tree queries include an additional path
column.
It contains the dot-separated path of local keys from the query's parent to the model:
$descendantsAndSelf = User::find(1)->descendantsAndSelf()->depthFirst()->get(); echo $descendantsAndSelf[0]->path; // 1 echo $descendantsAndSelf[1]->path; // 1.2 echo $descendantsAndSelf[2]->path; // 1.2.3
Change the column name by overriding getPathName()
if your table already contains a path
column:
class User extends Model { public function getPathName() { return 'path'; }
You can also customize the path separator by overriding getPathSeparator()
:
class User extends Model { public function getPathSeparator() { return '.'; } }
Custom Paths
You can add custom path columns to the query results:
class User extends Model { public function getCustomPaths() { return [ [ 'name' => 'slug_path', 'column' => 'slug', 'separator' => '/', ], ]; } } $descendantsAndSelf = User::find(1)->descendantsAndSelf; echo $descendantsAndSelf[0]->slug_path; // user-1 echo $descendantsAndSelf[1]->slug_path; // user-1/user-2 echo $descendantsAndSelf[2]->slug_path; // user-1/user-2/user-3
You can also reverse custom paths:
class User extends Model { public function getCustomPaths() { return [ [ 'name' => 'reverse_slug_path', 'column' => 'slug', 'separator' => '/', 'reverse' => true, ], ]; } }
Nested Results
Use the toTree()
method on a result collection to generate a nested tree:
$users = User::tree()->get(); $tree = $users->toTree();
This recursively sets children
relationships:
[ { "id": 1, "children": [ { "id": 2, "children": [ { "id": 3, "children": [] } ] }, { "id": 4, "children": [ { "id": 5, "children": [] } ] } ] } ]
Initial & Recursive Query Constraints
You can add custom constraints to the CTE's initial and recursive query. Consider a query where you want to traverse a tree while skipping inactive users and their descendants:
$tree = User::withQueryConstraint(function (Builder $query) { $query->where('users.active', true); }, function () { return User::tree()->get(); });
You can also add a custom constraint to only the initial or recursive query using withInitialQueryConstraint()
/
withRecursiveQueryConstraint()
.
Additional Methods
The trait also provides methods to check relationships between models:
isChildOf(Model $model)
: Checks if the current model is a child of the given model.isParentOf(Model $model)
: Checks if the current model is a parent of the given model.getDepthRelatedTo(Model $model)
: Returns the depth of the current model related to the given model.
$rootUser = User::create(['parent_id' => null]); $firstLevelUser = User::create(['parent_id' => $rootUser->id]); $secondLevelUser = User::create(['parent_id' => $firstLevelUser->id]); $isChildOf = $secondLevelUser->isChildOf($firstLevelUser); // Output: true $isParentOf = $rootUser->isParentOf($firstLevelUser); // Output: true $depthRelatedTo = $secondLevelUser->getDepthRelatedTo($rootUser); // Output: 2
Custom Relationships
You can also define custom relationships to retrieve related models recursively.
- HasManyOfDescendants
- BelongsToManyOfDescendants
- MorphToManyOfDescendants
- MorphedByManyOfDescendants
- Intermediate Scopes
- Usage outside of Laravel
HasManyOfDescendants
Consider a HasMany
relationship between User
and Post
:
class User extends Model { public function posts() { return $this->hasMany(Post::class); } }
Define a HasManyOfDescendants
relationship to get all posts of a user and its descendants:
class User extends Model { public function recursivePosts() { return $this->hasManyOfDescendantsAndSelf(Post::class); } } $recursivePosts = User::find($id)->recursivePosts; $users = User::withCount('recursivePosts')->get();
Use hasManyOfDescendants()
to only get the descendants' posts:
class User extends Model { public function descendantPosts() { return $this->hasManyOfDescendants(Post::class); } }
BelongsToManyOfDescendants
Consider a BelongsToMany
relationship between User
and Role
:
class User extends Model { public function roles() { return $this->belongsToMany(Role::class); } }
Define a BelongsToManyOfDescendants
relationship to get all roles of a user and its descendants:
class User extends Model { public function recursiveRoles() { return $this->belongsToManyOfDescendantsAndSelf(Role::class); } } $recursiveRoles = User::find($id)->recursiveRoles; $users = User::withCount('recursiveRoles')->get();
Use belongsToManyOfDescendants()
to only get the descendants' roles:
class User extends Model { public function descendantRoles() { return $this->belongsToManyOfDescendants(Role::class); } }
MorphToManyOfDescendants
Consider a MorphToMany
relationship between User
and Tag
:
class User extends Model { public function tags() { return $this->morphToMany(Tag::class, 'taggable'); } }
Define a MorphToManyOfDescendants
relationship to get all tags of a user and its descendants:
class User extends Model { public function recursiveTags() { return $this->morphToManyOfDescendantsAndSelf(Tag::class, 'taggable'); } } $recursiveTags = User::find($id)->recursiveTags; $users = User::withCount('recursiveTags')->get();
Use morphToManyOfDescendants()
to only get the descendants' tags:
class User extends Model { public function descendantTags() { return $this->morphToManyOfDescendants(Tag::class, 'taggable'); } }
MorphedByManyOfDescendants
Consider a MorphedByMany
relationship between Category
and Post
:
class Category extends Model { public function posts() { return $this->morphedByMany(Post::class, 'categorizable'); } }
Define a MorphedByManyOfDescendants
relationship to get all posts of a category and its descendants:
class Category extends Model { public function recursivePosts() { return $this->morphedByManyOfDescendantsAndSelf(Post::class, 'categorizable'); } } $recursivePosts = Category::find($id)->recursivePosts; $categories = Category::withCount('recursivePosts')->get();
Use morphedByManyOfDescendants()
to only get the descendants' posts:
class Category extends Model { public function descendantPosts() { return $this->morphedByManyOfDescendants(Post::class, 'categorizable'); } }
Intermediate Scopes
You can adjust the descendants query (e.g. child users) by adding or removing intermediate scopes:
User::find($id)->recursivePosts()->withTrashedDescendants()->get(); User::find($id)->recursivePosts()->withIntermediateScope('active', new ActiveScope())->get(); User::find($id)->recursivePosts()->withIntermediateScope( 'depth', function ($query) { $query->whereDepth('<=', 10); } )->get(); User::find($id)->recursivePosts()->withoutIntermediateScope('active')->get();
Usage outside of Laravel
If you are using the package outside of Laravel or have disabled package discovery for staudenmeir/laravel-cte
, you
need to add support for common table expressions to the related model:
class Post extends Model { use \Staudenmeir\LaravelCte\Eloquent\QueriesExpressions; }
Deep Relationship Concatenation
You can include recursive relationships into deep relationships by concatenating them with other relationships
using staudenmeir/eloquent-has-many-deep. This
works with Ancestors
, Bloodline
and Descendants
relationships (Laravel 9+).
Consider a HasMany
relationship between User
and Post
and building a deep relationship to get all posts of a
user's descendants:
User
→ descendants → User
→ has many → Post
Install the additional package, add the
HasRelationships
trait to the recursive model
and define a
deep relationship:
class User extends Model { use \Staudenmeir\EloquentHasManyDeep\HasRelationships; use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasRecursiveRelationships; public function descendantPosts(): \Staudenmeir\EloquentHasManyDeep\HasManyDeep { return $this->hasManyDeepFromRelations( $this->descendants(), (new static)->posts() ); } public function posts() { return $this->hasMany(Post::class); } } $descendantPosts = User::find($id)->descendantPosts;
At the moment, recursive relationships can only be at the beginning of deep relationships:
- Supported:
User
→ descendants →User
→ has many →Post
- Not supported:
Post
→ belongs to →User
→ descendants →User
Known Issues
MariaDB doesn't yet support correlated CTEs in subqueries. This affects
queries like User::whereHas('descendants')
or User::withCount('descendants')
.
Graphs: Multiple Parents per Node (Many-to-Many)
You can also use the package to traverse graphs with multiple parents per node that are defined in a pivot table. Use cases might be a bill of materials (BOM) or a family tree.
Supports Laravel 9+.
- Getting Started
- Included Relationships
- Pivot Columns
- Cycle Detection
- Subgraphs
- Order
- Depth
- Path
- Custom Paths
- Nested Results
- Initial & Recursive Query Constraints
- Deep Relationship Concatenation
- Known Issues
Getting Started
Consider the following table schema for storing directed graphs as nodes and edges:
Schema::create('nodes', function (Blueprint $table) { $table->id(); }); Schema::create('edges', function (Blueprint $table) { $table->unsignedBigInteger('source_id'); $table->unsignedBigInteger('target_id'); $table->string('label'); $table->unsignedBigInteger('weight'); });
Use the HasGraphRelationships
trait in your model to work with graph relationships and specify the name of the pivot
table:
class Node extends Model { use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasGraphRelationships; public function getPivotTableName(): string { return 'edges'; } }
By default, the trait expects a parent key named parent_id
and child key named child_id
in the pivot table. You can
customize them by overriding getParentKeyName()
and getChildKeyName()
:
class Node extends Model { public function getParentKeyName(): string { return 'source_id'; } public function getChildKeyName(): string { return 'target_id'; } }
By default, the trait uses the model's primary key as the local key. You can customize it by
overriding getLocalKeyName()
:
class Node extends Model { public function getLocalKeyName(): string { return 'id'; } }
Included Relationships
The trait provides various relationships:
ancestors()
: The node's recursive parents.ancestorsAndSelf()
: The node's recursive parents and itself.children()
: The node's direct children.childrenAndSelf()
: The node's direct children and itself.descendants()
: The node's recursive children.descendantsAndSelf()
: The node's recursive children and itself.parents()
: The node's direct parents.parentsAndSelf()
: The node's direct parents and itself.
$ancestors = Node::find($id)->ancestors; $nodes = Node::with('descendants')->get(); $nodes = Node::has('children')->get(); $total = Node::find($id)->descendants()->count(); Node::find($id)->descendants()->update(['active' => false]); Node::find($id)->parents()->delete();
Pivot Columns
Similar to BelongsToMany
relationships, you can retrieve additional columns from the pivot table besides the parent
and child key:
class Node extends Model { public function getPivotColumns(): array { return ['label', 'weight']; } } $nodes = Node::find($id)->descendants; foreach ($nodes as $node) { dump( $node->pivot->label, $node->pivot->weight ); }
Cycle Detection
If your graph contains cycles, you need to enable cycle detection to prevent infinite loops:
class Node extends Model { public function enableCycleDetection(): bool { return true; } }
You can also retrieve the start of a cycle, i.e. the first duplicate node. With this option, the query results include
an is_cycle
column that indicates whether the node is part of a cycle:
class Node extends Model { public function enableCycleDetection(): bool { return true; } public function includeCycleStart(): bool { return true; } } $nodes = Node::find($id)->descendants; foreach ($nodes as $node) { dump($node->is_cycle); }
Subgraphs
The trait provides the subgraph()
query scope to get the subgraph of a custom constraint:
$constraint = function ($query) { $query->whereIn('id', $ids); }; $subgraph = Node::subgraph($constraint)->get();
You can pass a maximum depth as the second argument:
$subgraph = Node::subgraph($constraint, 3)->get();
Order
The trait provides query scopes to order nodes breadth-first or depth-first:
breadthFirst()
: Get siblings before children.depthFirst()
: Get children before siblings.
$descendants = Node::find($id)->descendants()->breadthFirst()->get(); $descendants = Node::find($id)->descendants()->depthFirst()->get();
Depth
The results of ancestor, descendant and subgraph queries include an additional depth
column.
It contains the node's depth relative to the query's parent. The depth is positive for descendants and negative for ancestors:
$descendantsAndSelf = Node::find($id)->descendantsAndSelf()->depthFirst()->get(); echo $descendantsAndSelf[0]->depth; // 0 echo $descendantsAndSelf[1]->depth; // 1 echo $descendantsAndSelf[2]->depth; // 2
Change the column name by overriding getDepthName()
if your table already contains a depth
column:
class Node extends Model { public function getDepthName(): string { return 'depth'; } }
Depth Constraints
You can use the whereDepth()
query scope to filter nodes by their relative depth:
$descendants = Node::find($id)->descendants()->whereDepth(2)->get(); $descendants = Node::find($id)->descendants()->whereDepth('<', 3)->get();
Queries with whereDepth()
constraints that limit the maximum depth still build the entire (sub)graph internally.
Use withMaxDepth()
to set a maximum depth that improves query performance by only building the requested section of
the graph:
$descendants = Node::withMaxDepth(3, function () use ($id) { return Node::find($id)->descendants; });
This also works with negative depths (where it's technically a minimum):
$ancestors = Node::withMaxDepth(-3, function () use ($id) { return Node::find($id)->ancestors; });
Path
The results of ancestor, descendant and subgraph queries include an additional path
column.
It contains the dot-separated path of local keys from the query's parent to the node:
$descendantsAndSelf = Node::find(1)->descendantsAndSelf()->depthFirst()->get(); echo $descendantsAndSelf[0]->path; // 1 echo $descendantsAndSelf[1]->path; // 1.2 echo $descendantsAndSelf[2]->path; // 1.2.3
Change the column name by overriding getPathName()
if your table already contains a path
column:
class Node extends Model { public function getPathName(): string { return 'path'; } }
You can also customize the path separator by overriding getPathSeparator()
:
class Node extends Model { public function getPathSeparator(): string { return '.'; } }
Custom Paths
You can add custom path columns to the query results:
class Node extends Model { public function getCustomPaths(): array { return [ [ 'name' => 'slug_path', 'column' => 'slug', 'separator' => '/', ], ]; } } $descendantsAndSelf = Node::find(1)->descendantsAndSelf; echo $descendantsAndSelf[0]->slug_path; // node-1 echo $descendantsAndSelf[1]->slug_path; // node-1/node-2 echo $descendantsAndSelf[2]->slug_path; // node-1/node-2/node-3
You can also reverse custom paths:
class Node extends Model { public function getCustomPaths(): array { return [ [ 'name' => 'reverse_slug_path', 'column' => 'slug', 'separator' => '/', 'reverse' => true, ], ]; } }
Nested Results
Use the toTree()
method on a result collection to generate a nested tree:
$nodes = Node::find($id)->descendants; $tree = $nodes->toTree();
This recursively sets children
relationships:
[ { "id": 1, "children": [ { "id": 2, "children": [ { "id": 3, "children": [] } ] }, { "id": 4, "children": [ { "id": 5, "children": [] } ] } ] } ]
Initial & Recursive Query Constraints
You can add custom constraints to the CTE's initial and recursive query. Consider a query where you want to traverse a node's descendants while skipping inactive nodes and their descendants:
$descendants = Node::withQueryConstraint(function (Builder $query) { $query->where('nodes.active', true); }, function () { return Node::find($id)->descendants; });
You can also add a custom constraint to only the initial or recursive query using withInitialQueryConstraint()
/
withRecursiveQueryConstraint()
.
Deep Relationship Concatenation
You can include recursive relationships into deep relationships by concatenating them with other relationships using staudenmeir/eloquent-has-many-deep (Laravel 9+).
Consider a HasMany
relationship between Node
and Post
and building a deep relationship to get all posts of a
node's descendants:
Node
→ descendants → Node
→ has many → Post
Install the additional package, add the
HasRelationships
trait to the recursive model
and define a
deep relationship:
class Node extends Model { use \Staudenmeir\EloquentHasManyDeep\HasRelationships; use \Staudenmeir\LaravelAdjacencyList\Eloquent\HasGraphRelationships; public function descendantPosts(): \Staudenmeir\EloquentHasManyDeep\HasManyDeep { return $this->hasManyDeepFromRelations( $this->descendants(), (new static)->posts() ); } public function posts() { return $this->hasMany(Post::class); } } $descendantPosts = Node::find($id)->descendantPosts;
At the moment, recursive relationships can only be at the beginning of deep relationships:
- Supported:
Node
→ descendants →Node
→ has many →Post
- Not supported:
Post
→ belongs to →Node
→ descendants →Node
Known Issues
MariaDB doesn't yet support correlated CTEs in subqueries. This affects
queries like Node::whereHas('descendants')
or Node::withCount('descendants')
.
Package Conflicts
staudenmeir/eloquent-param-limit-fix
: Replace both packages with staudenmeir/eloquent-param-limit-fix-x-laravel-adjacency-list to use them on the same model.
Contributing
Please see CONTRIBUTING and CODE OF CONDUCT for details.