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

Question

假设我有实体 entry具有多引用属性 :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

TL;博士

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

这里有3个策略:

编写使用 2 个否定和 1 个析取或递归规则的动态 Datalog 查询(见下文)

生成查询代码(相当于 Alan Thompson 的回答):缺点是动态生成 Datalog 子句的常见缺点，即您无法从 query plan caching 中受益.

使用 indexes直接(EAVT 或 AVET)。

动态数据日志查询

Datalog 没有直接的方式来表达动态连接(逻辑 AND/'for all ...'/set intersection)。但是，您可以在纯 Datalog 中通过组合一个析取(逻辑 OR/'exists ...'/set union)和两个否定来实现它，即 (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 在查询中以其他方式绑定(bind))。

生成查询代码

生成查询代码的优点是在这种情况下它相对简单，并且它可能使查询执行比更动态的替代方案更有效。在 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)))))