[Feature Request] Cycle detection

[Nextra]

When trying to model certain graphs it can be difficult to avoid cycles in the relationships. I know performing a LIMIT query with an unreasonably high count can alleviate infinite loops, but it is not a particularly pretty solution. It needs additional handling of the result set, and still makes the database run the loop to that limit unnecessarily.

At least MariaDB and PostgreSQL allow avoiding this problem by detecting cycles at the query level. For MariaDB this is a fairly new addition while PostgreSQL has been able to do it for quite a while. However PostgreSQL version 14 makes the syntax quite a bit nicer, and it seems to me like it would be much easier to "attach" to a query (I'm not really proficient with the internal Laravel query machinations).

MariaDB CYCLE ... RESTRICT PostgreSQL 14 CYCLE ... SET ... USING

Would it be possible to integrate this functionality in this package?

[staudenmeir]

I have actually looked into this topic while working on a new feature that allows nodes with multiple parents (#26), but I didn't consider it for the existing relationships. I didn't think a cycle could realistically appear in a single-parent tree.

Can you share an example of a cycle in your (real-life) data?

[Nextra]

I stumbled on this when (maybe naively) importing a somewhat conventional organizational hierarchy.

Once I get to the top in this particular case - think board members - everyone is modeled as being each others boss, going around in a big circle.

That means from any given starting point I have a (somewhat arbitrarily) long string of ancestors and then a big loop at the top. Kind of like a lasso :smile:

While that wasn't a deal breaker, it did get me curious if databases offer any mitigation for this problem. Then I discovered that PostgreSQL had just recently introduced clean syntax for this problem, that can be basically bolted on to a WITH RECURSIVE CTE.

[staudenmeir]

What Laravel version and database are you using?

[Nextra]

Laravel 9.4 and PostgreSQL 14.0

[staudenmeir]

I added cycle detection to the underlying laravel-cte package, but I'm still thinking about the integration into this package.

If you want to use it immediately, you can override scopeWithRelationshipExpression() in your model:

use Illuminate\Database\Eloquent\Builder;
use Illuminate\Database\Eloquent\Model;
use Staudenmeir\LaravelAdjacencyList\Eloquent\HasRecursiveRelationships;

class BoardMember extends Model
{
    use HasRecursiveRelationships;

    /**
     * Add a recursive expression for the relationship to the query.
     *
     * @param \Illuminate\Database\Eloquent\Builder $query
     * @param string $direction
     * @param callable $constraint
     * @param int $initialDepth
     * @param string|null $from
     * @param int|null $maxDepth
     * @return \Illuminate\Database\Eloquent\Builder
     */
    public function scopeWithRelationshipExpression(Builder $query, $direction, callable $constraint, $initialDepth, $from = null, $maxDepth = null)
    {
        $from = $from ?: $this->getTable();

        $grammar = $query->getExpressionGrammar();

        $expression = $this->getInitialQuery($grammar, $constraint, $initialDepth, $from)
                           ->unionAll(
                               $this->getRecursiveQuery($grammar, $direction, $from, $maxDepth)
                           );

        $name = $this->getExpressionName();

        $query->getModel()->setTable($name);

        return $query->withRecursiveExpressionAndCycleDetection($name, $expression, 'id', 'is_cycle', 'cycle_path')->from($name);
    }
}

[Nextra]

Works beautifully on Postgres, excellent stuff!