README

本包提供了在 SQL 数据库中存储和查询有向无环图 (DAG) 的模型功能。通过包含一个特性并创建一个新关联模型，可以将任何模型转换为 DAG。您的模型将获得从原生 BelongsToMany 多对多关系扩展的关系，这样您除了 DAG 特定功能外，还可以使用许多原生的 Laravel 方法。

有向无环图特别适合存储和处理层次数据结构。作为特殊情况，通过包含一个额外的特性，您可以轻松高效地将模型转换为树。

安装

本包与 PHP 7.4 - 8.3 和 Laravel 6.20 - 11 兼容。它支持 MySQL (MariaDB)、PostgreSQL 和 SQLite。

通过 composer 安装

composer require marcovo/laravel-dag-model

文档

此页面包含在 Packagist 上无法正常工作的链接。在 Gitlab 中打开

在开始使用此包之前，请确保阅读了重要说明（特别是注意事项部分）。

基本用法

即使在没有此包的情况下，使用 Laravel 的 BelongsToMany 关系，也可以存储 DAG 并查询其本地关系，例如 children 和 parents。在此基础上，此包将为您的模型提供额外的关系，用于查询远程关系，例如祖先和后代。

给定一个顶点模型实例 $vertex 或查询构建器 $query，此包提供了以下功能：

    $vertex->children // Obtain all children
    $vertex->descendants()->get() // Obtain all descendants using a query
    
    $vertex->children()->attach($child) // Attach a child
    $vertex->children()->detach($child) // Detach a child

    // Use the relations in a query
    $query->whereHas('children', $callback)
    $query->whereHas('ancestors', $callback)
    
    // Use specialized DAG query methods
    $query->whereAncestorOf($vertex)

一个简单的示例

    // Store 3 vertices
    $parent = MyVertexModel::create();
    $child = MyVertexModel::create();
    $grandchild = MyVertexModel::create();

    // Store 2 edges (+1 implicit transitive closure edge
    // which will be automatically added by the TC algorithm)
    $parent->children()->attach($child);
    $child->children()->attach($grandchild);

    $ancestors = $grandchild->ancestors;
    // $ancestors now is a collection containing $parent and $child,
    // as new model instances received freshly from the database

有关更多示例和详细信息，请参阅上述文档页面。

树

作为树是有向无环图 (DAG) 的特殊情况，此包可用于操作和查询树。为此，此包包含一个特性 IsForest，可用于管理一个或多个树（= 森林）。特性提供了针对森林优化的专用操作查询，以及针对树特定的额外方法，例如 ->parent() 和 ->siblings()。有关更多信息，请参阅森林（树）扩展页面。

树数据结构：枢纽表（DAG）与嵌套集

在实现树数据结构时，可以遵循以下两种主要方法之一

使用嵌套集实现，在模型上添加两个整数列 left 和 right
使用包含节点之间边的枢纽表，就像此 DAG 包所做的那样

这两种方法都是合理的解决方案，每种方法都有其优缺点。最佳方法将取决于您的用例。

使用嵌套集的树

(优点) 每个模型/节点只需额外存储两列，这两列存储在同一个模型中
(优点) 在大多数情况下，两个检索到的模型之间的关系推导（例如，isDescendantOf()）可以在不查询数据库的情况下进行：所有所需信息都存储在两个left和right列中
(缺点) 在涉及继承关系复杂查询的情况下，嵌套集使用的非等式约束难以优化。特别是，数据库通常只能针对每个子查询优化一个非等式约束，其余的则通过表扫描进行过滤
(缺点) 变更会引起全局状态改变：添加、删除或移动一个节点通常需要更新大量节点，需要对这些行的写入锁

使用枢纽表的树（DAG）

(优点) 涉及继承关系的复杂查询基于性能良好的外键关系，允许轻松优化
(优点) 模型表不需要额外的列
(优点) 变更是局部操作：只有与添加/删除/移动的节点直接链接的枢纽表中的行将被修改
(缺点) 需要额外的数据库表
(缺点) 在大多数情况下，两个检索到的节点之间的关系推导（例如，isDescendantOf()）将需要查询枢纽表

与CTE方法的比较

此DAG模型包中使用的这种方法是将DAG的整个传递闭包存储在数据库中。作为替代，也可以只存储DAG本身，并构建能够在运行时确定和查询所需关系的查询。这种方法由staudenmeir/laravel-adjacency-list采用，使用公共表表达式（CTE）。

注意以下这些方法的优缺点

使用CTE的DAG和树

(优点) 不需要额外的列或存储
(优点) 变更没有性能损失
(缺点) 必须为涉及远程关系的每个SELECT查询计算一个CTE

使用存储传递闭包的DAG和树

(优点) 传递闭包作为远程关系的缓存，查询远程关系的所有信息都 readily 可用，无需实时计算
(缺点) 需要额外的数据库列并存储额外的行
(缺点) 每次变更都需要更新传递闭包

总结：当您的应用程序频繁变更图结构时，CTE方法应该是最佳选择。此包中使用的传递闭包方法最适合突变稀疏且表对远程关系进行大量读取的情况。

版本控制

此包遵循语义版本控制。向后兼容性承诺涵盖了API文档中定义的所有公共API。任何未在该文档中记录的方法（无论可见性如何）应被视为私有API，因此对它们的显式调用不受向后兼容性承诺的覆盖。换句话说，未列在API文档中的方法在非主版本发布中可能会更改。所有公共API方法都带有@api注释，所有内部方法带有@internal。

就像在Laravel中一样，方法参数名称不被视为向后兼容性承诺的一部分。

贡献

欢迎提出功能请求，但鼓励您也以合并请求的形式提供实现。只有测试覆盖率达到100%的合并请求才会被合并。此包遵循PSR-12编码标准。

使用以下方式测试您的贡献

gitlab-runner exec docker test:7.4
gitlab-runner exec docker test:8.1
gitlab-runner exec docker test:8.2
gitlab-runner exec docker test:8.3
gitlab-runner exec docker phpcs

marcovo / laravel-dag-model

维护者

详细信息