查找 ref-to-many 属性包含输入的所有元素的实体

Question

假设我有entry具有 ref-to-many 属性的实体:entry/groups。我应该如何构建查询以查找其:entry/groups属性包含我所有输入外部 ID 的实体？

下一个伪代码将更好地说明我的问题：

[2 3] ; having this as input foreign ids

;; and having these entry entities in db
[{:entry/id "A" :entry/groups  [2 3 4]}  
 {:entry/id "B" :entry/groups  [2]}     
 {:entry/id "C" :entry/groups  [2 3]}  
 {:entry/id "D" :entry/groups  [1 2 3]}
 {:entry/id "E" :entry/groups  [2 4]}] 

;; only A, C, D should be pulled

作为 Datomic/Datalog 的新手，我用尽了所有选项，因此感谢您提供任何帮助。谢谢！

Answer 1

长话短说

您正在解决 Datomic 数据日志中“动态结合”的一般问题。

这里有 3 个策略：

1. 编写一个使用 2 个否定和 1 个析取或递归规则的动态数据记录查询（见下文）
2. 生成查询代码（相当于Alan Thompson的答案）：缺点是动态生成Datalog子句的常见缺点，即您无法从查询计划缓存中受益。
3. 直接使用索引（EAVT 或 AVET）。

动态数据记录查询

Datalog 没有直接的方式来表达动态连接（逻辑 AND /“for all ...”/集合交集）。但是，您可以在纯 Datalog 中通过组合一个析取（逻辑 OR /“存在...”/集合并）和两个否定来实现它，即(For all ?g in ?Gs p(?e,?g)) <=> NOT(Exists ?g in ?Gs, such that NOT(p(?e, ?g)))

就您而言，这可以表示为：

[:find [?entry ...] :in $ ?groups :where
  ;; these 2 clauses are for restricting the set of considered datoms, which is more efficient (and necessary in Datomic's Datalog, which will refuse to scan the whole db)
  ;; NOTE: this imposes ?groups cannot be empty!
  [(first ?groups) ?group0]
  [?entry :entry/groups ?group0]
  ;; here comes the double negation
  (not-join [?entry ?groups]
    [(identity ?groups) [?group ...]]
    (not-join [?entry ?group]
      [?entry :entry/groups ?group]))]

好消息：这可以表示为非常通用的 Datalog 规则（我最终可能会将其添加到Datofu中）：

[(matches-all ?e ?a ?vs)
 [(first ?vs) ?v0]
 [?e ?a ?v0]
 (not-join [?e ?a ?vs]
   [(seq ?vs) [?v ...]]
   (not-join [?e ?a ?v]
     [?e ?a ?v]))]

...这意味着您的查询现在可以表示为：

[:find [?entry ...] :in % $ ?groups :where
 (matches-all ?entry :entry/groups ?groups)]

注意：有一种使用递归规则的替代实现：

[[(matches-all ?e ?a ?vs)
  [(seq ?vs)]
  [(first ?vs) ?v]
  [?e ?a ?v]
  [(rest ?vs) ?vs2]
  (matches-all ?e ?a ?vs2)]
 [(matches-all ?e ?a ?vs)
  [(empty? ?vs)]]]

这个的优点是接受空集合?vs（只要 和?e已?a在查询中以某种其他方式绑定）。

生成查询代码

生成查询代码的优点是在这种情况下相对简单，并且它可能比更动态的替代方案使查询执行更高效。在 Datomic 中生成 Datalog 查询的缺点是您可能会失去查询计划缓存的好处；因此，即使您要生成查询，您仍然希望使它们尽可能通用（即仅取决于值的数量v）

(defn q-find-having-all-vs 
  [n-vs]
  (let [v-syms (for [i (range n-vs)]
                 (symbol (str "?v" i)))]
    {:find '[[?e ...]]
     :in (into '[$ ?a] v-syms)
     :where 
     (for [?v v-syms]
       ['?e '?a ?v])}))

;; examples    
(q-find-having-all-vs 1)
=> {:find [[?e ...]], 
    :in [$ ?a ?v0],
    :where 
    ([?e ?a ?v0])}
(q-find-having-all-vs 2)
=> {:find [[?e ...]],
    :in [$ ?a ?v0 ?v1], 
    :where
    ([?e ?a ?v0] 
     [?e ?a ?v1])}
(q-find-having-all-vs 3)
=> {:find [[?e ...]], 
    :in [$ ?a ?v0 ?v1 ?v2], 
    :where 
    ([?e ?a ?v0] 
     [?e ?a ?v1]
     [?e ?a ?v2])}


;; executing the query: note that we're passing the attribute and values!
(apply d/q (q-find-having-all-vs (count groups))
  db :entry/group groups)

直接使用索引

我完全不确定上述方法在 Datomic Datalog 当前实现中的效率如何。如果您的基准测试显示这很慢，您始终可以回退到直接索引访问。

以下是 Clojure 中使用 AVET 索引的示例：

(defn find-having-all-vs
  "Given a database value `db`, an attribute identifier `a` and a non-empty seq of entity identifiers `vs`,
  returns a set of entity identifiers for entities which have all the values in `vs` via `a`"
  [db a vs]
  ;; DISCLAIMER: a LOT can be done to improve the efficiency of this code! 
  (apply clojure.set/intersection 
    (for [v vs]
      (into #{} 
        (map :e)
        (d/datoms db :avet a v)))))