- Namespace: thi.ng.trio.core
This namespace provides various protocols for the low-level triple store API, as well as a persistent in-memory store implementation and a flexible dataset type to aggregate models/stores and query multiple at once.
(defprotocol PTriple
(triple-id [_])
(subject [_])
(predicate [_])
(object [_]))This protocol is used to easily convert Clojure collections into a
triple sequence. Implementations are provided for sequences & maps
further below. This protocol is also used by the PModelConvert
implementations.
(defprotocol PTripleSeq
(triple-seq [_]))This protocol is used to easily convert Clojure collections into an triplestore and so allow the query engine to operate directly on these collections. Implementations are provided for sequences & maps further below.
(defprotocol PModelConvert
(as-model [_]))This protocol defines various accessors & predicate fns which must be implemented by a triple store in order to allow the trio query engine to act on it.
(defprotocol PModel
(subjects [_])
(predicates [_])
(objects [_])
(subject? [_ x])
(predicate? [_ x])
(object? [_ x])
(indexed? [_ x])
(model-size [_])
(latest-triple [_])
(latest-triple-id [_]))This protocol defines accessors to add, update and remove triples from a store. Bulk operations are defined, in order to allow optimized implementations relying on connections to external storage layers.
(defprotocol PModelUpdate
(add-triple [_ s] [_ g s])
(add-triples [_ triples] [_ g triples])
(remove-triple [_ s] [_ g s])
(remove-triples [_ triples] [_ g triples])
(update-triple [_ s s'] [_ g s s'])
(remove-subject [_ s] [_ g s]))This protocol allows for the injection of middleware during model updates. There’re two kinds of hooks, pre-commit and post-commit and both are triggered for each single triple added or removed.
Each hook is a function accepting 4 args:
- commit type (
:addor:remove) - watched store/model
- triple to add/remove
- watch ID
Pre-commit hooks are always called, irrespectively of the triple
being already present in the store (when attempting to add) or missing
(during remove). A pre-commit hook must return a triple (e.g. the
passed arg) to signal success or nil to indicate the add/remove op
should be canceled. This convention therefore allows hooks to be used
as triple verifiers or transformers.
Since hooks are stored in a map, their call order is undefined. Subsequent hooks will receive as triple arg the result of earlier hooks invoked. The model operation (add/remove) will only succeed if all hooks have returned a triple. If any hook fails, the model remains untouched.
Post-commit hooks are only called if a triple has actually been added
or removed from the model. Furthermore, these hooks must return a
model instance (usually the passed arg) to signal success or nil to
indicate failure and cancel the model operation. This allows
post-commit hooks to further validate and/or transform the model (e.g.
add additional triples to the watched model without invoking any
hooks).
Apart from that post-hooks follow the same calling order and all-or-nothing convention as described above for pre-commit hooks.
(def g
(-> (plain-store)
(watched-model)
;; this hook stringifies all triples elements
(add-pre-commit-hook
:stringify (fn [_ _ triple _] (mapv str triple)))
;; trace successful additions/removals
(add-post-commit-hook
:trace (fn [type model triple id] (prn id type triple) model))
(add-triple '[s p o])))
;; => :trace :add ["s" "p" "o"]
;; => #'user/g(defprotocol PModelWatch
(add-pre-commit-hook [_ id f])
(add-post-commit-hook [_ id f])
(remove-pre-commit-hook [_ id])
(remove-post-commit-hook [_ id]))(defprotocol PModelSelect
(select [_] [_ s p o] [_ g s p o])
(select-with-alts [_ s p o] [_ g s p o]))The select method is plays the main role here and is used to perform
low-level pattern match queries on a triplestore. Given any
combination of subject, predicate or object, the method performs a
search and returns all matching triples. The overall contract is that
if any SPO arg is nil, then this triple element matches anything.
Hence, there’re eight possible variations to match triples:
;; match all triples
(select store nil nil nil)
;; match all triples w subject = :s
(select store :s nil nil)
;; match all triples w/ pred = :p
(select store nil :p nil)
;; match all triples w/ obj = :o
(select store nil nil :o)
;; match all triples w/ subj = :s AND pred = :p
(select store :s :p nil)
;; match all triples w/ subj= :s AND obj = :o
(select store :s nil :o)
;; match all triples w/ pred = :p AND obj = :o
(select store nil :p :o)
;; match only given triple [:s :p :o]
(select store :s :p :o)In trio terminology, a dataset constitutes a triplestore, which
logically combines a number of other (independent) PModel
implementations. PDataset implementations must provide a PModel
implementation too and any queries run over a dataset will produce a
combined result from all included models. In addition, a dataset
must provide a select implementation with an extra graph arg to
directly query a specific model, rather than all.
(defprotocol PDataset
(remove-model [_ id])
(update-model [_ id m])
(get-model [_ id]))This is an experimental feature to support triplestore implementations which allow the aliasing/renaming of individual triple elements and provide potentially optimized solutions. See Store with alias support for more details.
(defprotocol PAliasModelSupport
(rewrite-alias [_ a b]))(def ^:private triple-ident (atom 0))
(defn- next-triple-id [] (swap! triple-ident inc))
(defn- remove-from-index
[idx i1 i2 i3]
(let [kv (idx i1)
v (disj (kv i2) i3)
kv (if (seq v) kv (dissoc kv i2))]
(if (seq kv)
(if (seq v)
(assoc-in idx [i1 i2] v)
(assoc idx i1 kv))
(dissoc idx i1))))
(defn- rewrite-alias*
[store pred id p q]
(if (pred store p)
(let [xs (apply select store (assoc [nil nil nil] id p))
store (remove-triples store xs)]
(add-triples store (map #(assoc % id q) xs)))
store))
(defn rewrite-alias-naive
[store p q]
(-> store
(rewrite-alias* subject? 0 p q)
(rewrite-alias* predicate? 1 p q)
(rewrite-alias* object? 2 p q)))
(defn trace [prefix x] (prn prefix x) x)The triplestore implementations defined in this namespace use a
custom/optimized 3-element vector type to store triples internally.
This Triple type can be used like a normal vector since it
implements all necessary Clojure protocols. In addition to using
numeric indices (0..2) to refer to elements, the keywords :s, :p
and :o can be used alternatively. Furthermore, the Triple type
supports swizzling to look up, edit and/or change the order of elements:
(def t (triple 'karsten 'nickname 'toxi))
(:s t) ; => karsten
(:p t) ; => nickname
(:o t) ; => toxi
(:so t) ; => [karsten toxi]
(:ops t) ; => [toxi nickname karsten]
(assoc t :p 'same-as) ; => [karsten same-as toxi]
(assoc t :po '[author trio]) ; => [karsten author trio]
(assoc t :op '[trio author]) ; => [karsten author trio]In order to deduplicate shared code between both the Clojure & ClojureScript protocol implementations, we first define a few snippets as re-usable templates, which are injected in the appropriate places of the code.
(replace-regexp-in-string "{{fn}}" fn
"(condp = (count args)
1 ({{fn}} _ (first args) nil)
2 ({{fn}} _ (first args) (second args))
(err/arity-error! (count args)))")(case (int k)
0 (Triple. v p o (next-triple-id) nil)
1 (Triple. s v o (next-triple-id) nil)
2 (Triple. s p v (next-triple-id) nil)
(err/key-error! k))(not (nil? (#{0 1 2 :s :p :o} k)))(replace-regexp-in-string
"{{fn}}" fn
"(if (instance? Triple x)
(and ({{fn}} s (.-s ^Triple x))
({{fn}} p (.-p ^Triple x))
({{fn}} o (.-o ^Triple x)))
(and (instance? java.util.Collection x)
(== 3 (count x))
({{fn}} s (nth x 0))
({{fn}} p (nth x 1))
({{fn}} o (nth x 2))))")(case (int k) 0 s, 1 p, 2 o, (err/key-error! k))(case (int k) 0 s, 1 p, 2 o, nf)(if (instance? Triple x)
(let [c (compare s (.-s ^Triple x))]
(if (== 0 c)
(let [c (compare p (.-p ^Triple x))]
(if (== 0 c)
(compare o (.-o ^Triple x))
c))
c))
(let [c (count x)]
(if (== 3 c) (compare x _) (- 3 c))))(-> 31
(unchecked-add-int (hash s))
(unchecked-multiply-int 31)
(unchecked-add-int (hash p))
(unchecked-multiply-int 31)
(unchecked-add-int (hash o)))(cons p (cons o nil))(let [acc (f s p)]
(if (reduced? acc)
@acc
(let [acc (f acc o)]
(if (reduced? acc)
@acc
acc))))(let [acc (f start s)]
(if (reduced? acc)
@acc
(let [acc (f acc p)]
(if (reduced? acc)
@acc
(let [acc (f acc o)]
(if (reduced? acc)
@acc
acc))))))(deftype Triple
#?(:clj [s p o id ^:unsynchronized-mutable __hash])
#?(:cljs [s p o id ^:mutable __hash])#?@(:clj
[clojure.lang.ILookup
(valAt [_ k] (swizzle _ k nil))
(valAt [_ k nf] (swizzle _ k nf))
java.util.concurrent.Callable
(call [_] (.invoke ^clojure.lang.IFn _))
java.lang.Runnable
(run [_] (.invoke ^clojure.lang.IFn _))
clojure.lang.IFn
(invoke [_ k] (swizzle _ k nil))
(invoke [_ k nf] (swizzle _ k nf))
(applyTo
[_ args]
<<tpl-apply(fn="swizzle")>>)
clojure.lang.IPersistentVector
clojure.lang.Associative
(count [_] 3)
(length [_] 3)
(containsKey [_ k] <<tpl-contains-key>>)
(entryAt [_ k] (clojure.lang.MapEntry. k <<tpl-nth-err>>))
(assoc [_ k v] (swizzle-assoc _ k v))
(assocN
[_ k v]
<<tpl-assoc-n>>)
java.util.Collection
(isEmpty [_] false)
(iterator [_] (.iterator ^java.util.Collection (list s p o)))
(toArray [_] (object-array _))
(size [_] 3)
clojure.lang.Sequential
clojure.lang.Seqable
(seq [_] (seq [s p o]))
(cons [_ x] [s p o x])
(peek [_] o)
(pop [_] [s p])
(rseq [_] (seq [o p s]))
(nth [_ k] <<tpl-nth-err>>)
(nth [_ k nf] <<tpl-nth-nf>>)
(equiv
[_ x]
<<tpl-equals(fn="clojure.lang.Util/equiv")>>)
(equals
[_ x]
<<tpl-equals(fn="clojure.lang.Util/equals")>>)
(hashCode
[_]
<<tpl-hashcode>>)
clojure.lang.IHashEq
(hasheq
[_]
(or __hash (set! __hash
(mix-collection-hash
<<tpl-hashcode>>
3))))
Comparable
(compareTo
[_ x]
<<tpl-compare>>)
cp/InternalReduce
(internal-reduce
[_ f start]
<<tpl-reduce-start>>)
cp/CollReduce
(coll-reduce
[_ f]
<<tpl-reduce>>)
(coll-reduce
[_ f start]
<<tpl-reduce-start>>)
Object
(toString
[_]
(.toString
(doto (StringBuilder. "#trio/Triple [")
(.append (pr-str s))
(.append " ")
(.append (pr-str p))
(.append " ")
(.append (pr-str o))
(.append " ")
(.append (pr-str id))
(.append "]"))))
])#?@(:cljs
[ICloneable
(-clone
[_] (Triple. s p o id __hash))
ILookup
(-lookup [_ k] (swizzle _ k nil))
(-lookup [_ k nf] (swizzle _ k nf))
IFn
(-invoke [_ k] (swizzle _ k nil))
(-invoke [_ k nf] (swizzle _ k nf))
ICounted
(-count [_] 3)
IAssociative
(-contains-key? [_ k] <<tpl-contains-key>>)
(-assoc [_ k v] (swizzle-assoc _ k v))
IVector
(-assoc-n
[_ k v]
<<tpl-assoc-n>>)
ISequential
ISeq
(-first [_] s)
(-rest [_] <<tpl-rest>>)
INext
(-next [_] <<tpl-rest>>)
ISeqable
(-seq [_] _)
IReversible
(-rseq [_] (seq o p s))
IIndexed
(-nth [_ k] <<tpl-nth-err>>)
(-nth [_ k nf] <<tpl-nth-nf>>)
ICollection
(-conj [_ x] [s p o x])
IStack
(-peek [_] o)
(-pop [_] [s p])
IComparable
(-compare
[_ x]
<<tpl-compare>>)
IHash
(-hash
[_]
(or __hash
(set! (.-__hash _)
(mix-collection-hash
(-> 31 (+ (hash s))
(bit-or 0)
(imul 31) (+ (hash p))
(bit-or 0)
(imul 31) (+ (hash o))
(bit-or 0))
3))))
IEquiv
(-equiv
[_ x]
(if (instance? Triple x)
(and (= s (.-s ^Triple x)) (= p (.-p ^Triple x)) (= o (.-o ^Triple x)))
(and (sequential? x) (== 3 (count x))
(= s (nth x 0)) (= p (nth x 1)) (= o (nth x 2)))))
IReduce
(-reduce
[coll f]
<<tpl-reduce>>)
(-reduce
[coll f start]
<<tpl-reduce-start>>)
Object
(toString
[_]
(str "#trio/Triple ["
(pr-str s) " "
(pr-str p) " "
(pr-str o) " "
(pr-str id) "]"))
])PTriple
(triple-id [_] id)
(subject [_] s)
(predicate [_] p)
(object [_] o))#?(:clj
(defmethod clojure.pprint/simple-dispatch Triple
[^Triple o] ((get-method clojure.pprint/simple-dispatch clojure.lang.IPersistentVector) o)))
#?(:clj
(defmethod print-method Triple
[^Triple o ^java.io.Writer w] (.write w (.toString o))))(defn- lookup3
[^Triple _ k nf]
(case k
\s (.-s _)
\p (.-p _)
\o (.-o _)
(or nf (err/key-error! k))))
(defn- swizzle
[^Triple _ k default]
(if (number? k)
(case (int k)
0 (.-s _)
1 (.-p _)
2 (.-o _)
(or default (err/key-error! k)))
(case k
:s (.-s _)
:p (.-p _)
:o (.-o _)
(let [n (name k) c (count n)]
(case c
2 [(lookup3 _ (nth n 0) default)
(lookup3 _ (nth n 1) default)]
3 (Triple.
(lookup3 _ (nth n 0) default)
(lookup3 _ (nth n 1) default)
(lookup3 _ (nth n 2) default)
(next-triple-id)
nil)
(or default (err/key-error! k)))))))
(defn- swizzle-assoc*
[_ keymap k v]
(let [n (name k)
c (count n)]
(if (and (<= c (count keymap)) (== c (count v) (count (into #{} n))))
(loop [acc (vec _), i 0, n n]
(if n
(recur (assoc acc (keymap (first n)) (v i)) (inc i) (next n))
(Triple. (acc 0) (acc 1) (acc 2) (next-triple-id) nil)))
(err/key-error! k))))
(defn- swizzle-assoc
[^Triple _ k v]
(case k
:s (Triple. v (.-p _) (.-o _) (next-triple-id) nil)
:p (Triple. (.-s _) v (.-o _) (next-triple-id) nil)
:o (Triple. (.-s _) (.-p _) v (next-triple-id) nil)
0 (Triple. v (.-p _) (.-o _) (next-triple-id) nil)
1 (Triple. (.-s _) v (.-o _) (next-triple-id) nil)
2 (Triple. (.-s _) (.-p _) v (next-triple-id) nil)
(swizzle-assoc* _ {\s 0 \p 1 \o 2} k v)))(defn triple
([s p o] (Triple. s p o (next-triple-id) nil))
([t] (if (instance? Triple t)
t
(Triple.
(first t) (nth t 1) (nth t 2)
(if (= 4 (count t)) (nth t 3) (next-triple-id)) nil))))(defn- select-with-alts-1
[coll idx]
(->> (set/intersection coll (set (keys idx)))
(mapcat #(->> % idx vals (apply concat)))))
(defn- select-with-alts-2
[outer inner idx]
(mapcat
(fn [o]
(let [out (idx o)]
(->> (set (keys out))
(set/intersection inner)
(mapcat out))))
outer))
(defn- select-with-alts-3
[outer inner preds idx lookup]
(reduce
(fn [acc o]
(let [out (idx o)]
(->> (set (keys out))
(set/intersection preds)
(reduce
(fn [acc p]
(if-let [t (some #(if (inner (lookup %)) %) (out p))]
(conj acc t)
acc))
acc))))
[] outer))
(deftype PlainMemoryStore [spo pos osp size]
Object
(toString [_] (str "#trio/MemStore " (pr-str (vec (select _ nil nil nil)))))
PModelUpdate
(add-triple
[_ [s p o :as t]]
(if (-> spo (get s nil) (get p nil) (get t nil)) _
(let [s (get (find spo s) 0 s)
p (get (find pos p) 0 p)
o (get (find osp o) 0 o)
t (Triple. s p o (next-triple-id) nil)]
(PlainMemoryStore.
(update-in spo [s p] d/set-conj t)
(update-in pos [p o] d/set-conj t)
(update-in osp [o s] d/set-conj t)
(inc size)))))
(add-triples [_ triples]
(loop [changed? false, spo spo, pos pos, osp osp, size size, xs triples]
(if xs
(let [[s p o :as t] (first xs)]
(if (-> spo (get s nil) (get p nil) (get t nil))
(recur changed? spo pos osp size (next xs))
(let [s (get (find spo s) 0 s)
p (get (find pos p) 0 p)
o (get (find osp o) 0 o)
t (Triple. s p o (next-triple-id) nil)]
(recur
true
(update-in spo [s p] d/set-conj t)
(update-in pos [p o] d/set-conj t)
(update-in osp [o s] d/set-conj t)
(inc size)
(next xs)))))
(if changed?
(PlainMemoryStore. spo pos osp size)
_))))
(remove-triple [_ [s p o :as t]]
(if (-> spo (get s nil) (get p nil) (get t nil))
(PlainMemoryStore.
(remove-from-index spo s p t)
(remove-from-index pos p o t)
(remove-from-index osp o s t)
(dec size))
_))
(remove-triples [_ triples]
(loop [changed? false, spo spo, pos pos, osp osp, size size, xs triples]
(if xs
(let [[s p o :as t] (first xs)]
(if (-> spo (get s nil) (get p nil) (get t nil))
(recur
true
(remove-from-index spo s p t)
(remove-from-index pos p o t)
(remove-from-index osp o s t)
(dec size)
(next xs))
(recur changed? spo pos osp size (next xs))))
(if changed?
(PlainMemoryStore. spo pos osp size)
_))))
(update-triple [_ s1 s2]
(add-triple (remove-triple _ s1) s2))
(remove-subject [_ s]
(remove-triples _ (select _ s nil nil)))
PModel
(subject? [_ x]
(if (spo x) x))
(predicate? [_ x]
(if (pos x) x))
(object? [_ x]
(if (osp x) x))
(indexed? [_ x]
(if (or (spo x) (pos x) (osp x)) x))
(subjects [_] (keys spo))
(predicates [_] (keys pos))
(objects [_] (keys osp))
(model-size [_] size)
(latest-triple [_]
(->> spo vals (mapcat vals) (apply concat) ;; select all
(reduce
(fn [a b] (if (< (triple-id a) (triple-id b)) b a)))))
(latest-triple-id [_]
(triple-id (latest-triple _)))
PModelSelect
(select [_]
(select _ nil nil nil))
(select
[_ s p o]
(if s
(if p
(if o
;; s p o
(let [t (triple s p o)]
(if (-> spo (get s nil) (get p nil) (get t nil)) [t]))
;; s p nil
(-> spo (get s nil) (get p nil)))
;; s nil o / s nil nil
(if o
(-> osp (get o nil) (get s nil))
(->> (spo s) vals (apply concat))))
(if p
(if o
;; nil p o
(-> pos (get p nil) (get o nil))
;; nil p nil
(->> (pos p) vals (apply concat)))
(if o
;; nil nil o
(->> (osp o) vals (apply concat))
;; nil nil nil
(->> spo vals (mapcat vals) (apply concat))))))
(select-with-alts
[_ s p o]
(let [s (if (set? s) (if-not (empty? s) s) (if s #{s}))
p (if (set? p) (if-not (empty? p) p) (if p #{p}))
o (if (set? o) (if-not (empty? o) o) (if o #{o}))]
(if s
(if p
(if o
(select-with-alts-3 s o p spo peek)
(select-with-alts-2 s p spo))
(if o
(select-with-alts-2 o s osp)
(select-with-alts-1 s spo)))
(if p
(if o
(select-with-alts-2 p o pos)
(select-with-alts-1 p pos))
(if o
(select-with-alts-1 o osp)
(->> spo vals (mapcat vals) (apply concat)))))))
PAliasModelSupport
(rewrite-alias
[_ a b] (rewrite-alias-naive _ a b)))
#?(:clj
(defmethod print-method
PlainMemoryStore [^PlainMemoryStore o ^java.io.Writer w] (.write w (.toString o))))Some use cases require support for aliased resources stored in
triples. For example in RDF resources can be explicitly declared as
equal via an owl:sameAs relationship.
The AliasMemoryStore defined below achieves this goal by wrapping an
existing triplestore and combines it with an Union Find index to allow
registration of aliases and queries using them.
Union Find is based on the concept of disjoint sets of connected
components. For each component (set) a single canonical value is
chosen. In the case of the AliasMemoryStore this means any triples
containing aliased values will be rewritten to contain only canonical
values. This happens with already existing triples and newly added
ones. Aliases can be defined and removed at any time, although it’s
more efficient to declare aliases before inserting new triples to
avoid major rewrite operations.
(defrecord AliasMemoryStore [store aliases]
PModelUpdate
(add-triple
[_ [s p o]]
(let [t [(or (u/canonical aliases s) s)
(or (u/canonical aliases p) p)
(or (u/canonical aliases o) o)]]
(AliasMemoryStore. (add-triple store t) aliases)))
(add-triples
[_ triples]
(loop [store store, xs triples]
(if xs
(let [[s p o] (first xs)
t [(or (u/canonical aliases s) s)
(or (u/canonical aliases p) p)
(or (u/canonical aliases o) o)]]
(recur (add-triple store t) (next xs)))
(AliasMemoryStore. store aliases))))
PModel
(subject? [_ x]
(subject? store (or (u/canonical aliases x) x)))
(predicate? [_ x]
(predicate? store (or (u/canonical aliases x) x)))
(object? [_ x]
(object? store (or (u/canonical aliases x) x)))
(indexed? [_ x]
(indexed? store (or (u/canonical aliases x) x)))
(subjects [_] (subjects store))
(predicates [_] (predicates store))
(objects [_] (objects store))
(model-size [_] (model-size store))
PModelSelect
(select
[_] (select _ nil nil nil))
(select
[_ s p o]
(let [s (or (u/canonical aliases s) s)
p (or (u/canonical aliases p) p)
o (or (u/canonical aliases o) o)]
(select store s p o)))
u/PUnionFind
(canonical [_ p] (u/canonical aliases p))
(canonical? [_ p] (u/canonical? aliases p))
(component [_ p] (u/component aliases p))
(disjoint-components [_] (u/disjoint-components aliases))
(register [_ p] (AliasMemoryStore. store (u/register aliases p)))
(unregister
[_ p]
(if (u/canonical? aliases p)
(let [q (first (disj (u/component aliases p) p))
aliases (u/unregister aliases p)
store (if q (rewrite-alias store p q) store)]
(AliasMemoryStore. store aliases))
(AliasMemoryStore. store (u/unregister aliases p))))
(unified? [_ p q] (u/unified? aliases p q))
(union
[_ p q]
(if (and p q)
(let [aliases (u/union aliases p q)
canon (u/canonical aliases p)
store (if (= p canon)
(rewrite-alias store q canon)
(rewrite-alias store p canon))]
(AliasMemoryStore. store aliases))
(err/illegal-arg! (str "aliases must be both non-nil values: " [p q])))))Currently still inefficient (1.5-2x slower than PlainMemoryStore),
but still thinking this approach of treating triples (incl. with
wildcards) as graph, might have better milage later as part of the
implementation for an efficient inferencer…
(defprotocol PNode
(get-children [_])
(add-child [_ c])
(remove-child [_ c])
(is-leaf? [_]))
(defprotocol PGraph
(add-node [_ n] [_ n parents])
(get-node [_ t])
(get-node-for-id [_ id])
(get-ids [_])
(get-nodes [_]))
(deftype TripleNode [triple ^:unsynchronized-mutable children]
PNode
(get-children
[_] children)
(add-child
[_ c] (set! children (conj (or children #{}) c)) _)
(remove-child
[_ c] (set! children (disj children c)) _)
(is-leaf?
[_] (and (first triple) (nth triple 1) (nth triple 2)))
Object
(toString [_] (str (pr-str triple) " " (pr-str children))))
(def ^:private root [nil nil nil])
(defn tg-select-with-alts
[_ s p o]
(if (and (seq s) (seq p) (seq o))
(mapcat
(fn [[s p o]] (select _ s p o))
(d/cartesian-product s p o))))
(declare index-branch)
(deftype TripleGraph [nodes ids next-id size]
Object
(toString
[_] (str ":nodes " (pr-str nodes)
" :ids " (pr-str ids)
" :next " next-id))
PGraph
(add-node
[_ n] (add-node _ n nil))
(add-node
[_ n parents]
(let [g (TripleGraph.
(assoc nodes next-id n)
(assoc ids (.-triple ^TripleNode n) next-id)
(inc next-id)
(if (is-leaf? n) (inc size) size))]
(when (seq parents)
(doseq [^TripleNode p parents]
(add-child p next-id)))
g))
(get-node
[_ t] (nodes (ids t)))
(get-node-for-id
[_ id] (nodes id))
PModel
(subject?
[_ x] ((subjects _) x))
(predicate?
[_ x] ((predicates _) x))
(object?
[_ x] ((objects _) x))
(indexed?
[_ x] (or (subject? _ x) (predicate? _ x) (object? _ x)))
(subjects
[_] (->> (nodes 0)
(get-children)
(map #(first (.-triple ^TripleNode (nodes %))))
(filter identity)
(set)))
(predicates
[_] (->> (nodes 0)
(get-children)
(map #(nth (.-triple ^TripleNode (nodes %)) 1))
(filter identity)
(set)))
(objects
[_] (->> (nodes 0)
(get-children)
(map #(nth (.-triple ^TripleNode (nodes %)) 2))
(filter identity)
(set)))
(model-size
[_] size)
PModelUpdate
(add-triple
[_ [s p o :as t]]
(if-not (ids t)
(let [id (.-next-id _)
^TripleGraph g (add-node _ (TripleNode. (Triple. s p o (next-triple-id) nil) nil) nil)]
(-> (index-branch g id [[s p nil] [s nil nil] root])
(index-branch id [[nil p o] [nil p nil] root])
(index-branch id [[s nil o] [nil nil o] root])))
_))
(add-triples
[_ triples] (reduce add-triple _ triples))
PModelSelect
(select
[_] (select _ nil nil nil))
(select
[_ s p o]
(let [ids (if (or s p o)
(if-let [id (ids (triple s p o))] [id])
(->> (nodes 0)
(get-children)
(filter #(first (.-triple ^TripleNode (nodes %))))))]
(if (seq ids)
(loop [acc (transient [])
ids (into #?(:clj clojure.lang.PersistentQueue/EMPTY :cljs cljs.core.PersistentQueue.EMPTY) ids)]
(if (seq ids)
(let [^TripleNode n (nodes (peek ids))
c (get-children n)]
(if c
(recur acc (into (pop ids) c))
(recur (conj! acc (.-triple n)) (pop ids))))
(persistent! acc))))))
(select-with-alts
[_ s p o]
(let [s (if (set? s) (if-not (empty? s) s) (if s #{s}))
p (if (set? p) (if-not (empty? p) p) (if p #{p}))
o (if (set? o) (if-not (empty? o) o) (if o #{o}))]
(if s
(if p
(if o
(tg-select-with-alts
_
(set/intersection s (subjects _))
(set/intersection p (predicates _))
(set/intersection o (objects _)))
(tg-select-with-alts
_ (set/intersection s (subjects _)) (set/intersection p (predicates _)) #{nil}))
(if o
(tg-select-with-alts
_ (set/intersection s (subjects _)) #{nil} (set/intersection o (objects _)))
(tg-select-with-alts
_ (set/intersection s (subjects _)) #{nil} #{nil})))
(if p
(if o
(tg-select-with-alts
_ #{nil} (set/intersection p (predicates _)) (set/intersection o (objects _)))
(tg-select-with-alts
_ #{nil} (set/intersection p (predicates _)) #{nil}))
(if o
(tg-select-with-alts
_ #{nil} #{nil} (set/intersection o (objects _)))
(select _ nil nil nil)))))))
(defn- index-branch
[g id patterns]
(loop [^TripleGraph g g, id id, ps patterns]
(if ps
(let [id' ((.-ids g) (first ps))]
(if id'
(do
(add-child ^TripleNode ((.-nodes g) id') id)
g)
(recur
(add-node g (TripleNode. (triple (first ps)) #{id}) nil)
(.-next-id g)
(next ps))))
g)))
#?(:clj
(defn triple-graph->dot
([g]
(str "digraph g {\n"
"node[color=black,style=filled,fontname=Inconsolata,fontcolor=white,fontsize=9];\n"
"edge[fontname=Inconsolata,fontsize=9];\n"
(triple-graph->dot g 0 "")
"}"))
([g id dot]
(let [n (get-node-for-id g id)
t (.-triple ^TripleNode n)
d (format
"%d[label=\"%d: %s\",color=%s];\n"
id id (pr-str t)
(if (is-leaf? n) "red" "grey"))]
(reduce
(fn [dot id'] (triple-graph->dot g id' (str dot (format "%d -> %d;\n" id id'))))
(str dot d)
(get-children n))))))(defn plain-store
[& triples]
(add-triples (PlainMemoryStore. (hash-map) (hash-map) (hash-map) 0) triples))
(defn plain-store-from-reader
[triples] (apply plain-store triples))
(defn alias-store
[store aliases & triples]
(add-triples (reduce (partial apply u/union) (AliasMemoryStore. store (u/disjoint-set)) aliases) triples))
(defn triple-graph
[]
(let [root' (TripleNode. root nil)]
(add-node (TripleGraph. {} {} 0 0) root')))(defrecord PlainDataset [models]
PModelUpdate
(add-triple [_ s]
(add-triple _ :default s))
(add-triple [_ g s]
(update-in _ [:models g] add-triple s))
(add-triples [_ triples]
(add-triples _ :default triples))
(add-triples [_ g triples]
(update-in _ [:models g] add-triples triples))
(remove-triple [_ s]
(remove-triple _ :default s))
(remove-triple [_ g s]
(update-in _ [:models g] remove-triple s))
(remove-triples [_ triples]
(remove-triples _ :default triples))
(remove-triples [_ g triples]
(update-in _ [:models g] remove-triples triples))
(remove-subject [_ s]
(remove-subject _ :default s))
(remove-subject [_ g s]
(update-in _ [:models g] remove-subject s))
PModel
(subject? [_ x]
(some #(subject? % x) (vals models)))
(predicate? [_ x]
(some #(predicate? % x) (vals models)))
(object? [_ x]
(some #(object? % x) (vals models)))
(indexed? [_ x]
(some #(indexed? % x) (vals models)))
(subjects [_]
(set (mapcat subjects (vals models))))
(predicates [_]
(set (mapcat predicates (vals models))))
(objects [_]
(set (mapcat objects (vals models))))
(model-size [_]
(reduce + (map model-size (vals models))))
PModelSelect
(select [_]
(select _ nil nil nil))
(select [_ s p o]
(mapcat #(select % s p o) (vals models)))
(select [_ g s p o]
(if-let [g (models g)] (select g s p o)))
PDataset
(update-model [_ id m]
(assoc-in _ [:models id] m))
(remove-model [_ id]
(update-in _ [:models] dissoc id))
(get-model [_ id]
(models id)))(defn plain-dataset
[& {:as models}]
(PlainDataset. (assoc models :default (plain-store))))(defrecord WatchedModel
[model pre-hooks post-hooks]
PModelWatch
(add-pre-commit-hook
[_ id hook-fn]
(assoc-in _ [:pre-hooks id] hook-fn))
(remove-pre-commit-hook
[_ id]
(update-in _ [:pre-hooks] dissoc id))
(add-post-commit-hook
[_ id hook-fn]
(assoc-in _ [:post-hooks id] hook-fn))
(remove-post-commit-hook
[_ id]
(update-in _ [:post-hooks] dissoc id))
PModel
(subject?
[_ x] (subject? model x))
(predicate?
[_ x] (predicate? model x))
(object?
[_ x] (object? model x))
(indexed?
[_ x] (indexed? model x))
(subjects
[_] (subjects model))
(predicates
[_] (predicates model))
(objects
[_] (objects model))
(model-size
[_] (model-size model))
PModelUpdate
(add-triple
[_ t]
(let [t (reduce-kv
(fn [t k v] (if-let [t' (v :add model t k)] t' (reduced nil)))
t pre-hooks)]
(if-not (seq (apply select model t))
(let [m' (add-triple model t)
m' (reduce-kv
(fn [m k v] (if-let [m' (v :add m t k)] m' (reduced nil)))
m' post-hooks)]
(if m' (assoc _ :model m') _))
_)))
(add-triples
[_ triples]
(reduce add-triple model triples))
(remove-triple
[_ t]
(let [t (reduce-kv
(fn [t k v] (if-let [t' (v :remove model t k)] t' (reduced nil)))
t pre-hooks)]
(if (seq (apply select model t))
(let [m' (remove-triple model t)
m' (reduce-kv
(fn [m k v] (if-let [m' (v :remove m t k)] m' (reduced nil)))
m' post-hooks)]
(if m' (assoc _ :model m') _))
_)))
(remove-triples
[_ triples]
(reduce add-triple model triples))
(update-triple
[_ t t'])
(remove-subject
[_ s])
PModelSelect
(select
[_] (select model nil nil nil))
(select
[_ s p o] (select model s p o))
(select-with-alts
[_ s p o] (select-with-alts model s p o)))(defn watched-model
[model] (WatchedModel. model {} {}))Whereas select-with-alts enables the pre-constrained search of
triples using sets of possible values for each SPO, the search
function below allows us to specify search patterns using Regular
Expressions. Different patterns can be given for S, P, O and nil
values indicate a “match-all” wildcard (just as with select &
select-with-alts). For example:
(def g (as-model '[[karsten nick toxi] [mia nickname miaki] [nicolas nic nick]]))
(search g nil #"nick.*" nil)
;; => ([karsten nick toxi] [giedre nickname mia])
;; [nicolas nic nick] is not matched, since the `nic` pred is misspelledThe actual search function is using select-with-alts itself and
acts merely as a pre-processing step to build up value sets based on
regexp matches. Note: Non-string values are cast to strings in order to
apply the regexps.
#?(:clj (defn regexp? [x] (instance? java.util.regex.Pattern x)))
(defn regexp-matches
[ds f re]
;;(into #{} (filter #(if (string? %) (re-find x %)) (f ds)))
(into #{} (filter #(re-find re (if (string? %) % (str %))) (f ds))))
(defn search
[ds s p o]
(->> [s p o]
(map #(if (regexp? %2) (regexp-matches ds % %2) %2)
[subjects predicates objects])
(apply select-with-alts ds)))Using the PTripleSeq and PModelConvert protocols defined above, we
can provide a mechanism to automatically convert Clojure collections
into triple seqs or a triplestore. Of course, such an approach will
involve some assumptions about the internal structure of these
collections, but the implementations below are quite flexible and
allow for very succinct definitions of graph structures by specifying
shared subjects, predicates or objects within a given triple pattern.
The PModelConvert simply wraps the PTripleSeq implementation and
produces a new PlainMemoryStore with the supplied triples.
Note: The triple seqs produced are all lazy (using mapcat).
To convert maps into a flat sequence of triples, the converter assumes the data layout shown below. Unlike with sequences (discussed next), which allow multiple subjects, predicates or objects per pattern, for maps we can only support multiple object values for a given pair of subject/predicate:
(as-model
{:s1 {:p1 [:s2 :s3 :s4] :p2 23}
:s2 {:p2 "foo"}
:s3 {:p3 :s1}})
;; => [[:s1 :p1 :s2] [:s1 :p1 :s3] [:s1 :p1 :s4] [:s1 :p2 23] ...]The map converter then simply flattens each SP tuple:
(defn triple-seq-associative
"Converts a single nested map into a seq of triples.
Each key must have another map as value. Toplevel keys become
subjects, value map keys predicates, inner map values objects. Each
predicate key can define a seq of values to produce multiple
triples."
[coll]
(mapcat
(fn [[s v]]
(mapcat
(fn [[p o]]
(if (sequential? o)
(mapv (fn [o] [s p o]) o)
[[s p o]]))
v))
coll))Clojure sequences offer more flexibility than maps to encode graph
structures and furthermore can contain maps themselves. The
conversion supports any mixture of formats shown below by computing
the cartesian product of each individual pattern to produce a flat
sequence of triples. If a sequence item is a map, it will be converted
with the triple-seq-associative fn.
(as-model
'[[s p o] ;; => [s p o]
[s p [o1 o2]] ;; => [s p o1] [s p o2]
[s [p1 p2] o] ;; => [s p1 o] [s p2 o]
[s [p1 p2] [o1 o2]] ;; => [s p1 o1] [s p2 o1] [s p1 o2] [s p2 o2]
[[s1 s2] p o] ;; => [s1 p o] [s2 p o]
[[s1 s2] [p1 p2] o] ;; => [s1 p1 o] [s1 p2 o] [s2 p1 o] [s2 p2 o]
[[s1 s2] [p1 p2] [o1 o2]]]) ;; => [s1 p1 o1] [s1 p2 o2] [s2 p1 o1] ...
(as-model
'[{s1 {p1 [o1 o2]} ;; => [s1 p1 o1] [s1 p1 o2]
s2 {p1 [o3 o4]}} ;; => [s2 p1 o3] [s2 p1 o4]
{s1 {p2 o1, p3 o5}}]) ;; => [s1 p2 o1] [s1 p3 o5](defn triple-seq-sequential
[coll]
(mapcat
(fn [triple]
(if (map? triple)
(triple-seq triple)
(->> triple
(map #(if (sequential? %) % [%]))
(apply d/cartesian-product))))
coll))(extend-protocol PTripleSeq
#?(:clj clojure.lang.Sequential
:cljs PersistentVector)
(triple-seq [_] (triple-seq-sequential _))
#?@(:cljs
[List
(triple-seq [_] (triple-seq-sequential _))
LazySeq
(triple-seq [_] (triple-seq-sequential _))
IndexedSeq
(triple-seq [_] (triple-seq-sequential _))])
#?(:clj clojure.lang.IPersistentMap
:cljs PersistentHashMap)
(triple-seq [_] (triple-seq-associative _))
#?@(:cljs
[PersistentArrayMap
(triple-seq [_] (triple-seq-associative _))]))
(extend-protocol PModelConvert
#?(:clj clojure.lang.Sequential
:cljs PersistentVector)
(as-model [_] (apply plain-store (triple-seq-sequential _)))
#?@(:cljs
[List
(as-model [_] (apply plain-store (triple-seq-sequential _)))
LazySeq
(as-model [_] (apply plain-store (triple-seq-sequential _)))
IndexedSeq
(as-model [_] (apply plain-store (triple-seq-sequential _)))])
#?(:clj clojure.lang.IPersistentMap
:cljs PersistentHashMap)
(as-model [_] (apply plain-store (triple-seq-associative _)))
#?@(:cljs
[PersistentArrayMap
(as-model [_] (apply plain-store (triple-seq-associative _)))]))(defn select-from-seq
[_ s p o]
(-> (if s
(if p
(if o
(fn [[s' p' o']] (and (= s s') (= p p') (= o o')))
(fn [[s' p']] (if (= s s') (= p p'))))
(if o
(fn [[s' _ o']] (if (= s s') (= o o')))
(fn [t] (= s (first t)))))
(if p
(if o
(fn [[_ p' o']] (if (= p p') (= o o')))
(fn [t] (= p (nth t 1))))
(if o
(fn [t] (= o (nth t 2)))
identity)))
(filter _)))
(extend-protocol PModelSelect
#?(:clj clojure.lang.Sequential
:cljs PersistentVector)
(select
([_] (select-from-seq _ nil nil nil))
([_ s p o] (select-from-seq _ s p o)))
#?@(:cljs
[List
(select
([_] (select-from-seq _ nil nil nil))
([_ s p o] (select-from-seq _ s p o)))
LazySeq
(select
([_] (select-from-seq _ nil nil nil))
([_ s p o] (select-from-seq _ s p o)))
IndexedSeq
(select
([_] (select-from-seq _ nil nil nil))
([_ s p o] (select-from-seq _ s p o)))])){trio/Triple thi.ng.trio.core/triple
trio/MemStore thi.ng.trio.core/plain-store-from-reader}(ns thi.ng.trio.core
(:refer-clojure :exclude [object? indexed?])
(:require
[thi.ng.dstruct.core :as d]
[thi.ng.dstruct.unionfind :as u]
[thi.ng.xerror.core :as err]
[clojure.set :as set]
#?@(:clj
[[clojure.pprint]
[clojure.core.protocols :as cp]])))
<<protos>>
<<helpers>>
(declare swizzle swizzle-assoc)
<<triple>>
<<memstore>>
<<alias-store>>
<<dataset>>
<<watched-model>>
<<ctors>>
<<search>>
<<convert>>
<<coll-select>>