如何在 Datomic 中实现排序的 to-many 关系？

Question

Datomic 中没有 out-of-the-box 模式功能用于对 to-many 关系中的 child 实体进行排序，但这是一个非常普遍的要求。谷歌搜索发现了一些解决方案，所以我想在这里列出需求和解决方案的变化，并希望得到社区的评论。

可能的要求

• R1：child 个实体的少量 (N) 个（不确定 small/large 阈值应该是）
• R2：大量 child 个实体
• R3: single-parent child仁
• R4: multi-parent child仁
• R5：递归 children 即存储在 Datomic
中的树

我的具体用例是 R1 + R3 + R5，我怀疑这很常见，但我想尽可能多地列举，以便将来可能成为其他人有用的参考。

解决方案

• S1：具有 "position" 属性的嵌套组件实体，例如Datofu
• S2：向每个 child 添加自定义 "position" 属性，如 using transactor fns here and in this post
所述
• S3：在 datomic-linklist
中实现的每个 child 实体上使用 "next" 属性的链表
• S4：将边缘表示为 described in this post
的单独包装器实体

问题

每个解决方案似乎都有挑战。我能想到的是：

• P1：维护插入、删除或移动操作的恒定时间操作。有人建议对 "position" 值使用小数，以避免在 re-ordering
时必须更新所有 children
• P2：支持多个 parent 排序关系
• P3：随着排序或成员发生变化，维护存储顺序的位置或边缘的复杂性。
• P4：对 "position" 属性的更改会影响 child 实体的隐含 "last changed" 日期，但实际上并未更改
• P5：queries/pull（尤其是递归查询）在通过包装器实体连接时会变得困难

对于我的树use-case，我不关心P2，P1不是大问题，因为N通常很低

所有这些研究都没有帮助我弄清楚哪种解决方案最适合我的树用例，但我倾向于 S2。最简单的复杂性自然是我的目标，但我怀疑所有的解决方案都会很复杂。

问题 : 你有没有遇到过这个问题？你可以​​分享什么来帮助其他人做出决定？我将在上面添加更多 R、S 和 P，因为它们已被指出。我（和许多其他人）非常感谢任何反馈。

几年前曾有人问过 ，但当时并没有发生太多事情。

Answer 1

这实际上取决于您的实际用例（您可能同时在单个数据库中有多个不同的用例）。

首先，在one-to-many和many-to-many之间选择parent-child关系：

• one-to-many 意味着您可以将额外的属性直接附加到 child 实体上，避免在额外的 :db/id、:my.domain/guid、:ordinal/ref 属性上花费宝贵的数据，和历史大小。
• many-to-many 意味着您必须有单独的实体来跟踪 children.
之间的排序

此时，您可能仍想选择单独的实体，以避免弄乱 child 实体上的一些 latest change date stats/subscriptions，如果有的话。从语义上讲，children 的顺序改变意味着 parent 实体发生了变化，而不是 children 的。

接下来，解决 recursive pull patterns and queries 问题。如果你选择 attribute on child – 你已经很好了。 如果您使用 separate entity，请将序数实体保留在 parent 实体的单独属性中：

{:foo/bars [{:db/id 4}
            {:db/id 2}]
 :foo/bars-order [{:db/id 9 :ordinal/idx 0 :ordinal/ref {:db/id 2}}
                  {:db/id 8 :ordinal/idx 1 :ordinal/ref {:db/id 4}}]} 

缺点是：你需要保持两者同步以避免孤儿序数，或下落不明 children.

最后，linked list 与 position values 更像是一个品味问题。然而，positional values 有更大的 tx-data 足迹（例如，在 10 个元素列表的位置 0 插入单个元素需要 10 个额外的 datom，在添加新元素的基础上每 10 个元素接触一次）。

我认为，唯一的 inferior-no-matter-what 解决方案 – 包装 children (parent-wrapper-child)，它消除了你的递归拉模式，并以其他方式阻碍.

现在回到您的用例：
single-parent + recursive queries = idx 或 child 上的 next 属性。

Answer 2

为了将来参考，我通过使用带拉链的 Datomic Linked List 包装器成功地满足了我的要求（有序树存储）。链接列表代码有几个错误，我很快就会 fork/fix/deploy 到 clojars。

此解决方案非常简单，更改操作的时间恒定，因此性能良好。

一个挑战是多个有序的子关系。链表代码假定每个实体有一个有序列表，在我的例子中，我需要 1 个树子列表，但更多列表用于其他数据。我已经解决了这个问题，但如果您的要求相似，则需要考虑这一点。

如果从这个原型中得出其他有用的观察结果，我会 post 进一步评论。

Answer 3

自 2019 年 6 月 Datomic 中的新功能以来，这个问题有了新的解决方案，在我对问题 的回答中有所描述。