threatgrid / asami Goto Github PK

View Code? Open in Web Editor NEW

633.0 633.0 29.0 33.89 MB

A graph store for Clojure and ClojureScript

License: Eclipse Public License 1.0

Clojure 99.96% Shell 0.04%

asami's People

Contributors

Stargazers

Watchers

asami's Issues

Transitive predicates in ClojureScript

The recent fixes in transitive queries are somehow not working in ClojureScript. Start with the simple transitive data demo:

(require '[asami.core :as d :refer [transact q]])
(def db-uri "asami:mem://dbname")
(d/create-database db-uri)
(def conn (d/connect db-uri))
(def data
  [{:db/id -1 :name "Washington Monument"}
   {:db/id -2 :name "National Mall"}
   {:db/id -3 :name "Washington, DC"}
   {:db/id -4 :name "USA"}
   {:db/id -5 :name "Earth"}
   {:db/id -6 :name "Solar System"}
   {:db/id -7 :name "Orion-Cygnus Arm"}
   {:db/id -8 :name "Milky Way Galaxy"}
   {:db/id -9 :db/ident 9 :name "Arlington"}
   {:db/id -10 :db/ident 10 :name "Falls Church"}
   [:db/add -1 :is-in -2]
   [:db/add -2 :is-in -3]
   [:db/add -3 :is-in -4]
   [:db/add -4 :is-in -5]
   [:db/add -5 :is-in -6]
   [:db/add -6 :is-in -7]
   [:db/add -7 :is-in -8]
   [:db/add -9 :neighbor -3]
   [:db/add -10 :neighbor -9]])
(def db (:db-after @(transact conn {:tx-data data})))

Zero Step

The zero-step query does not work:

(q '[:find [?name ...] :where [?e :name "Washington Monument"] [?e :is-in* ?e2] [?e2 :name ?name]] db)

The correct answer is provided by Clojure:

("Washington Monument" "National Mall" "Washington, DC" "USA" "Earth" "Solar System" "Orion-Cygnus Arm" "Milky Way Galaxy")

ClojureScript misses the zero-step:

("National Mall" "Washington, DC" "USA" "Earth" "Solar System" "Orion-Cygnus Arm" "Milky Way Galaxy")

Property Paths

(pprint (q '[:find [?name ...] :where [?e :name "Falls Church"][?e ?a* ?e2][?e2 :name ?name]] db))

Clojure gives:

("Falls Church"
 "Arlington"
 "Earth"
 "Orion-Cygnus Arm"
 "Solar System"
 "Milky Way Galaxy"
 "USA"
 "Washington, DC")

ClojureScript says:

Execution error (ExceptionInfo) at (<cljs repl>:1).
Unable to do transitive closure with nothing bound

cljs.user=> (node:79580) [DEP0097] DeprecationWarning: Using a domain property in MakeCallback is deprecated. Use the async_context variant of MakeCallback or the AsyncResource class instead.

Explicit default graph fails

If the default graph is described explicitly then this fails:

(q '[:find ?name . :in $ :where [?m :movie/title ?name][?m :movie/release-year 1985]] db)
Execution error (ArityException) at asami.query/eval7243$create-bindings$fn (query.cljc:382).
Wrong number of args (0) passed to: asami.query/eval7135/outer-product--7140

#error {
 :cause "Wrong number of args (0) passed to: asami.query/eval7135/outer-product--7140"
 :via
 [{:type clojure.lang.ArityException
   :message "Wrong number of args (0) passed to: asami.query/eval7135/outer-product--7140"
   :at [clojure.lang.AFn throwArity "AFn.java" 429]}]
 :trace
 [[clojure.lang.AFn throwArity "AFn.java" 429]
  [clojure.lang.AFn invoke "AFn.java" 28]
  [clojure.core.protocols$seq_reduce invokeStatic "protocols.clj" 28]
  [clojure.core.protocols$fn__8146 invokeStatic "protocols.clj" 75]
  [clojure.core.protocols$fn__8146 invoke "protocols.clj" 75]
  [clojure.core.protocols$fn__8088$G__8083__8101 invoke "protocols.clj" 13]
  [clojure.core$reduce invokeStatic "core.clj" 6824]
  [clojure.core$reduce invoke "core.clj" 6810]
  [asami.query$eval7243$create_bindings__7248$fn__7249 invoke "query.cljc" 382]
  [asami.query$eval7243$create_bindings__7248 invoke "query.cljc" 366]
  [asami.query$eval7783$query_entry__7788$fn__7789 invoke "query.cljc" 646]
  [asami.query$eval7783$query_entry__7788 invoke "query.cljc" 641]
  [asami.core$q invokeStatic "core.cljc" 359]
  [asami.core$q doInvoke "core.cljc" 354]
  [clojure.lang.RestFn invoke "RestFn.java" 423]
  [user$eval10532 invokeStatic "form-init11600158981584690779.clj" 1]
  [user$eval10532 invoke "form-init11600158981584690779.clj" 1]
  [clojure.lang.Compiler eval "Compiler.java" 7177]
  [clojure.lang.Compiler eval "Compiler.java" 7132]
  [clojure.core$eval invokeStatic "core.clj" 3214]
  [clojure.core$eval invoke "core.clj" 3210]
  [clojure.main$repl$read_eval_print__9086$fn__9089 invoke "main.clj" 437]
  [clojure.main$repl$read_eval_print__9086 invoke "main.clj" 437]
  [clojure.main$repl$fn__9095 invoke "main.clj" 458]
  [clojure.main$repl invokeStatic "main.clj" 458]
  [clojure.main$repl doInvoke "main.clj" 368]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [nrepl.middleware.interruptible_eval$evaluate invokeStatic "interruptible_eval.clj" 79]
  [nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 55]
  [nrepl.middleware.interruptible_eval$interruptible_eval$fn__921$fn__925 invoke "interruptible_eval.clj" 142]
  [clojure.lang.AFn run "AFn.java" 22]
  [nrepl.middleware.session$session_exec$main_loop__1022$fn__1026 invoke "session.clj" 171]
  [nrepl.middleware.session$session_exec$main_loop__1022 invoke "session.clj" 170]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.lang.Thread run "Thread.java" 834]]}

Workaround: don't include an :in clause when only the default graph is needed

Count queries

We want simple counts for queries as per Datomic. This is just for returning a scalar count of the entire result set.

Zero Step transitive Closures are not returned

Given the following data:

(def data
  [{:db/id -1 :name "Washington Monument"}
   {:db/id -2 :name "National Mall"}
   {:db/id -3 :name "Washington, DC"}
   {:db/id -4 :name "USA"}
   {:db/id -5 :name "Earth"}
   {:db/id -6 :name "Solar System"}
   {:db/id -7 :name "Orion-Cygnus Arm"}
   {:db/id -8 :name "Milky Way Galaxy"}
   {:db/id -9 :name "Arlington"}
   {:db/id -10 :name "Falls Church"}
   [:db/add -1 :is-in -2]
   [:db/add -2 :is-in -3]
   [:db/add -3 :is-in -4]
   [:db/add -4 :is-in -5]
   [:db/add -5 :is-in -6]
   [:db/add -6 :is-in -7]
   [:db/add -7 :is-in -8]])

The following query works as expected:

=> (d/q '[:find ?name :where [?e :name "Washington Monument"] [?e :is-in+ ?e2] [?e2 :name ?name]] (d/db conn))
(["National Mall"] ["Washington, DC"] ["USA"] ["Earth"] ["Solar System"] ["Orion-Cygnus Arm"] ["Milky Way Galaxy"])

However, the "zero step" query (using * rather than +) does not return "Washington Monument":

=> (d/q '[:find ?name :where [?e :name "Washington Monument"] [?e :is-in* ?e2] [?e2 :name ?name]] (d/db conn))
(["National Mall"] ["Washington, DC"] ["USA"] ["Earth"] ["Solar System"] ["Orion-Cygnus Arm"] ["Milky Way Galaxy"])

Zero step on some transitive functions still not appearing

Referencing the data in #70
The final in the following queries fails to return the zero step:

user=> (d/q '[:find [?e] :where [?e :name "Falls Church"]] (d/db conn))
[:tg/node-10736]
user=> (d/q '[:find ?name :where [:tg/node-10736 ?p+ ?e2][?e2 :name ?name]] (d/db conn))
(["Orion-Cygnus Arm"] ["Solar System"] ["Earth"] ["Washington, DC"] ["USA"] ["Milky Way Galaxy"] ["Arlington"])
user=> (d/q '[:find ?name :where [:tg/node-10736 ?p* ?e2][?e2 :name ?name]] (d/db conn))
(["Orion-Cygnus Arm"] ["Solar System"] ["Earth"] ["Washington, DC"] ["USA"] ["Milky Way Galaxy"] ["Arlington"])

This last one should have included the name "Falls Church". Check the [:v ? ?] transitive handler.

Add a `t` value to the `Database` type

Databases are currently identified by transaction number according to their position in a database history. However, there is an expectation that the :t value will be on the type. This need only be the count of the history.

ie. the initial creation of the database has a history of [], and the :t will be 0. After the first transaction, the history will be [empty-db] and the :t will be 1. After the second transaction, the history will be [empty-db first-db] and the :t will 2. etc.

Add OPTIONAL keyword

Use the SPARQL semantics for optional

The syntax can be the same as for and and or

Multigraphs required

The current index supports storing each statement once. This is what is needed for most applications. But we also have a need for a multigraph. This can be done by reifying each triple. The reification could be an entire map, but for now, just store an integer.

Implement deletes for the multi-graph

Add a delete-multi function.

Multi-insert optimization

Insert/delete is done a single statement at a time. These do update-in on the indexes. There may be a point at which a large transaction should be done with transient objects. The issue is that all the nested structures would need to be converted back to persistent when the transaction is done, which is why it is only worth doing after a particular size of transaction.

Update planner to push transitive attributes back

Using the #70 data, the transitive attribute gets pushed forward in the following query:

=> (d/q '[:find ?a ?name :where [?e :name "Falls Church"][?e2 :name ?name][?e ?a* ?e2]] (d/db conn))
([nil "Falls Church"]
 [:neighbor "Arlington"]
 [:neighbor "Solar System"]
 [:neighbor "Washington, DC"]
 [:neighbor "USA"]
 [:neighbor "Orion-Cygnus Arm"]
 [:neighbor "Earth"]
 [:neighbor "Milky Way Galaxy"])

This can (and probably should) be modified to return more than the first step in ?a, but it is also better to push this to the back of the query, where both ends of the constraint get bound:

=> (d/q '[:find ?a ?name :where [?e :name "Falls Church"][?e2 :name ?name][?e ?a* ?e2]] (d/db conn) :planner :user)
([[:neighbor :neighbor :is-in :is-in :is-in :is-in] "Orion-Cygnus Arm"]
 [[:neighbor :neighbor :is-in :is-in :is-in] "Solar System"]
 [[:neighbor :neighbor :is-in :is-in] "Earth"]
 [[:neighbor :neighbor] "Washington, DC"]
 [[:neighbor :neighbor :is-in] "USA"]
 [[:neighbor :neighbor :is-in :is-in :is-in :is-in :is-in] "Milky Way Galaxy"]
 [[:neighbor] "Arlington"])

Extract Connection and Database as protocols

To make the new storage implementations accessible, we want to talk to them using the same API as the memory-based code. Database and Connection should be extracted as protocols, so that a new implementation can be slotted in seamlessly

Transitive closures

Implement transitive closure on predicates. Depending on the pre-bindings this can be used to determine simple transitivity, or more complex concepts like shortest path, and subgraph identification.

Merge Naga-store

Projection is currently handled through the Naga-store library. This needs to be brought in locally in order to:

Avoid the Storage protocol for direct Asami use.
Annotate projections to detect things like property updates.

Naga-store can continue as a separate library, but Asami needs its own version as well.

Simple aggregates need distinct

Right now, queries with single constraints count the entire result:

(d/q '[:find (count ?e) :where [?e ?a ?v]] (d/db conn))

This counts all the triples, before projection down to the ?e column. The dedup operation has to be applied after projection, not before.

Create buffer-backed tree index

Planning to implement indices over AVL trees, though if this is done with a decent interface then a different tree structure ought to be pluggable.

Trees are to be backed by a buffer that is either a memory mapped file, via tree.block-file or a block abstraction to be built over a JavaScript ArrayBuffer.

Dependencies:

Index-+                                  (this ticket)
      +- AVL-tree-+                      (#63 AVL Tree)
                  +- Mapped Block File   (complete)
                  +- ArrayBuffer Blocks  (#62 Array Buffer Blocks)

These will be used to build a triples index, and to build a data-pool (per data type)

Re-enable the identity query planner

The asami.quert/select-planner function chooses a query planner based on an options map. The default is to choose planner/plan-path. The other supported option is :user which will choose the plan as provided by the user. e.g.

{:planner :user}

The options map is not being supplied right now, and needs to be passed all the way in from asami.core\q

Shift asami.core/graphs-of into asami.query and apply after truncating input according to the length of in

Filter Regression

Larger ClojureScript systems can trigger eval to stop recognizing symbols. Update functions to build a function that does not use eval

Re-establish var binding operation

These worked, but were disabled due to failing to get eval working under ClojureScript. Add them back in, even if it only covers a few functions. Map them manually if we have to.

Add selection syntaxes to aggregates

Right now, aggregates have to use the standard projection function. Update the :find clause parsing to select an appropriate projection function.

Transitive closures not binding

Testing for bindings on a transitive closure are not working correctly.

Given the following data:

(def data
  [{:db/id -1 :db/ident 1 :name "Washington Monument"}
   {:db/id -2 :db/ident 2 :name "National Mall"}
   {:db/id -3 :db/ident 3 :name "Washington, DC"}
   {:db/id -4 :db/ident 4 :name "USA"}
   {:db/id -5 :db/ident 5 :name "Earth"}
   {:db/id -6 :db/ident 6 :name "Solar System"}
   {:db/id -7 :db/ident 7 :name "Orion-Cygnus Arm"}
   {:db/id -8 :db/ident 8 :name "Milky Way Galaxy"}
   {:db/id -9 :db/ident 9 :name "Arlington"}
   {:db/id -10 :db/ident 10 :name "Falls Church"}
   [:db/add -1 :is-in -2]
   [:db/add -2 :is-in -3]
   [:db/add -3 :is-in -4]
   [:db/add -4 :is-in -5]
   [:db/add -5 :is-in -6]
   [:db/add -6 :is-in -7]
   [:db/add -7 :is-in -8]
   [:db/add -9 :neighbor -3]
   [:db/add -10 :neighbor -9]])

Note: :db/ident is provided to avoid a reflexive property.

Variable transitive predicates are:
a) not binding correctly (ClojureScript example):

=> (d/q '[:find ?e2 :where [?e :name "Falls Church"] [?e ?p+ ?e2]] (d/db conn))
(node:80638) [DEP0097] DeprecationWarning: Using a domain property in MakeCallback is deprecated. Use the async_context variant of MakeCallback or the AsyncResource class instead.
Execution error (ExceptionInfo) at (<cljs repl>:1).
Unable to do transitive closure with nothing bound

b) Traverses the graph when starting from a bound value:

=> (d/q '[:find [?e] :where [?e :name "Falls Church"]] (d/db conn))
:tg/node-10
=> (d/q '[:find ?e2 :where [:tg/node-10 ?p+ ?e2]] (d/db conn))
([:tg/node-10] ["Falls Church"] [:tg/node-4] [:tg/node-8] ["Orion-Cygnus Arm"] ["Solar System"] [true] [:tg/node-5] [:tg/node-9] [:tg/node-6] ["Earth"] ["Washington, DC"] ["USA"] ["Milky Way Galaxy"] [:tg/node-3] ["Arlington"] [:tg/node-7])

Note: This includes the zero step, which is wrong when + is used!

However, these values are not being joined:

=> (d/q '[:find ?name :where [:tg/node-10 ?p+ ?e2][?e2 :name ?name]] (d/db conn))
(["Arlington"])

Note: Projection fails for unwrapping the rows:

=> (d/q '[:find [?name] :where [:tg/node-10 ?p+ ?e2][?e2 :name ?name]] (d/db conn))
Execution error (Error) at (<cljs repl>:1).
No item 1 in vector of length 1

Grouped counts

We need full counting by groups. This goes beyond issue #3 and allows a count to be returned with other variables, and group-by clauses.

Ideally, we want a HAVING clause, as per SPARQL.

Create backup/load functions

For now, these could just dump and slurp edn. But I think we want something super simple for users

Encoder/Decoder

The ClojureScript codec will need to convert bytes to printable strings. To achieve this, we can use a base 64 encoding. The encoding map will be:

          111111111122222222223333333333444444444455555555556666
0123456789012345678901234567890123456789012345678901234567890123

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.$

The first 2 rows are the number to be encoded. The last row is the encoding character.

This scheme will encode 3 bytes in 4 characters. For bytes labeled a, b, c with bits 0-7, then the encoding will be:

first char	second char	third char	fourth char
a7 a6 a5 a4 a3 a2	a1 a0 b7 b6 b5 b4	b3 b2 b1 b0 c7 c6	c5 c4 c3 c2 c1 c0

Example

Encoding the bytes de ad be ef gives bits of:

de	ad	be	ef
`11011110`	`10101101`	`10111110`	`11101111`

This will be split into groups of 3 byte, with the second group requiring zero padding:

Group 1	Group 2
`11011110` , `10101101` , `10111110`	`11101111` , `00000000` , `00000000`

The bits from each group of 8 bit values are then rearranged into groups of 6 bits. The commas between 8 bit bytes are left in place here:

Group 1
`110111` `10,1010` `1101,10` `111110`

Group 2
`111011` `11,0000` `0000,00` `000000`

These 6 bit values in decimal are:

Group 1
`59` `42` `54` `62`

Group 2
`59` `48` `0` `0`

The encoding for these are:

Group 1	Group 2
`XGS.`	`XM00`

Add underscore as a valid variable

Datomic allows for underscores to indicate a "Do not care" position. This is essentially the same as a variable, but it should be mapped to a gensym'ed var, so that it does not lead to attempts to match multiple uses of the symbol

when is mako coming out?

sorry. just noticed the legend of korra references. big fan of both the show and the libraries.

Array Buffer Blocks

We want a storage abstraction for blocks, similar to what we can get in tree.block-file but backed by a JavaScript ArrayBuffer.

Note that we need a "save" mechanism, which will store this buffer persistently. Investigate if this needs serialization/deserialization, or if browser persistent data can manage a buffer without conversion (I'm skeptical of that, but haven't yet looked)

Finish optimizer to handle cross products

The optimizer handles the ordering of constraints, and groups constraints by shared variables. When groups with unrelated variables exist, then the groups are currently unordered. There are some heuristics that can improve this rare situation:

If a first constraint has a count of 1, then it should be pushed to the back, since the cross product does not expand a partial result, and it acts to bind its variables.
other than this, order groups according to expected size of full results. Expected size is of a similar order to the resolution size of the smallest constraint resolution that is greater than 1.

Change line 138 to use cons rather than concat. Then at line 140, sort all-ordered to use the above heuristics.

Prebindings failing in not clauses

The following query fails to filter the required value:

(asami/q '[:find ?type ?value
            :in $ ?disposition
            :where
            [?observable :type ?type]
            [?observable :value ?value]
            ;; deliberated, not internal, not clean  
            [?observable :deliberated true]
            (not [?observable :internal true])
            (not [?verdict :disposition ?disposition]
                 [?verdict :observable ?verdict-observable]
                 [?verdict-observable :type ?type]
                 [?verdict-observable :value ?value])]
          store
          1)

However, when ?disposition is replaced with a literal 1 then the not clause works fine.

Shift Data from Naga to Datomic

Naga is for rules, while the Data API can be used to build entities for Asami. This library needs to move between projects.

AVL Tree

As we are using a persistent-data approach, I'm expecting that an AVL tree will be appropriate. This is because:

Locality will be clustered around paths. This is because a path to an inserted node will be in adjacent blocks (hence good locality), as the path is allocated when a new block is inserted.
The top of the tree gets cached by the OS for memory-mapped files.
searching is O(log(n)) and single writes are O(log(n)) per node, but transacted writes get asymptotically closer to O(1) for each node (or O(n) in the size of the transaction).
Simpler structures.

Over time we can try other structures, but I have a lot of experience with AVL, and they have proven fast for this type of application.

The implementation will require:

A block manager for storage (#62 Array Buffer Blocks, and tree.block-file)
A reference to another block manager for stored data.
Each node will have a reserved "payload" space which holds relevant node info and a pointer to full info.
A comparator function that reads the payload and can access the secondary file.

Optimize simple queries

There are many queries to resolve a single pattern. However, these go through the optimizer, and reduction just like any other query, which is a lot of unnecessary work. This has shown up as a hot spot when being used in browsers, as per IROH-UI #906 (Private repo).

Address this by short circuiting simple queries to perform a simple projection over an index lookup.

Implement durable storage

Documenting the process in a blog series. The blog is describing everything from first principles, so it is presenting everything using Javascript and Java. However, the final implementation will be in Clojure/ClojureScript.

Storage will be in blocks in immutable buffers. These will be identified by keys which will be compound, joining both the immutable buffer and the offset in that buffer. The idea is to support:

Memory mapped files (JVM)
browser persistent buffers (ClojureScript)
AWS S3 buckets
Databases

Failing filters in ClojureScript

Filters in ClojureScript are failing, complaining about their namespace. Filters are essential for our initial rules.

Counting efficiency

Counting for patterns is currently done by issuing a count on results. This needs to be improved to work with the indexes. Counts are based on how many bound elements there are in the pattern:

0: reduce + over reducing + over the set counts
1: reduce + over the count of the vals
2: count the set
3: 0 or 1

Multi-arity attributes

Currently, entities with multiple-arity properties cannot be correctly stored or retrieved.

Zuko Issue #1 addresses this.

Data Writer/Reader

Flat files will contain length/type information followed by raw bytes.

This needs a reader/writer.

Length/Type

Byte 0:

Pattern	Type	Description
0xxxxxxx	string	7 bits of length info. Up to 128
10xxxxxx	URI	6 bits of length info. Up to 64
110xxxxx	keyword	5 bits of length info. Up to 32
111xyyyy	variable	Type determined in low 4 bits

If the pattern begins with 111 then the length will be in the following bytes. The following bits are:

Bits	Description
5-7	all 1
4	Indicates the number of length bytes
3-0	type info

Bytes 1, 2, 3, 4

If bit4 of Byte0 is 0 then the next byte contains the length (up to 256). If 1, then the next 2 bytes (16 bits) indicate the length. 2 byte lengths can be up to 32kB.

If the 16 bit value is negative (bit15 = 1), then the length is actually 4 bytes, with a total of 31 bits indicating length. This gives a total possible length of 2GB.

Types

Bit3-Bit0 indicate the type information:

Pattern	Type
0000	string
0001	uri
0010	long
0011	double
0100	BigInt
0101	BigFloat
0110	timestamp
0111	keyword
1000	urn
1001	blob
1010	xsd encoded

There are 5 available codes remaining.

Each one of the above will have functions for encoding/decoding the data from the remaining bytes. The XSD type is expected to be extensible: encoding to a type URI a separator char, and a string format for the data. The default types are described in XML Schema Part 2: Datatypes. In particular, see the type hierarchy diagram.

Query options can't be passed as a map

Query options are only passable as key/value pairs. These should also be passable as a map of values.

user=> (d/show-plan '[:find ?name ?sequel :where [?m :movie/title ?name] [?m :movie/release-year 1995] (optional [?m :movie/sequel ?sequel])] db {:planner :user})
Execution error (IllegalArgumentException) at asami.query/eval7930$query-entry$fn (query.cljc:757).
No value supplied for key: {:planner :user}

Regex filters fail

When attempting to search for a regular expression in a :where clause, the Pattern argument is failing:

=> (q '[:find ?name :where [?m :movie/title ?name][?m :movie/genre ?genre][(re-find #"comedy" ?genre)]] db)
Execution error (ExceptionInfo) at asami.query/eval6842$filter-join$fn (query.cljc:177).
Error executing filter: java.lang.ClassCastException: class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')

The full response is:

#error {
 :cause "Error executing filter: java.lang.ClassCastException: class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
 :data {:error #error {
 :cause "class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
 :via
 [{:type java.lang.ClassCastException
   :message "class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
   :at [clojure.core$re_matcher invokeStatic "core.clj" 4849]}]
 :trace
 [[clojure.core$re_matcher invokeStatic "core.clj" 4849]
  [clojure.core$re_find invokeStatic "core.clj" 4898]
  [clojure.core$re_find invoke "core.clj" 4898]
  [clojure.lang.AFn applyToHelper "AFn.java" 156]
  [clojure.lang.AFn applyTo "AFn.java" 144]
  [clojure.lang.Var applyTo "Var.java" 705]
  [clojure.core$apply invokeStatic "core.clj" 665]
  [clojure.core$apply invoke "core.clj" 660]
  [asami.query$eval6842$filter_join__6847$fn__6861$filter_fn__6873 doInvoke "query.cljc" 171]
  [clojure.lang.RestFn invoke "RestFn.java" 408]
  [clojure.core$filter$fn__5893 invoke "core.clj" 2821]
  [clojure.lang.LazySeq sval "LazySeq.java" 42]
  [clojure.lang.LazySeq seq "LazySeq.java" 51]
  [clojure.lang.LazySeq withMeta "LazySeq.java" 36]
  [clojure.lang.LazySeq withMeta "LazySeq.java" 17]
  [clojure.core$with_meta__5420 invokeStatic "core.clj" 218]
  [clojure.core$with_meta__5420 invoke "core.clj" 217]
  [asami.query$eval6842$filter_join__6847$fn__6861 invoke "query.cljc" 173]
  [asami.query$eval6842$filter_join__6847 invoke "query.cljc" 155]
  [asami.query$left_join invokeStatic "query.cljc" 305]
  [asami.query$left_join invoke "query.cljc" 297]
  [asami.query$eval7305$run_simple_query__7310$fn__7318$ljoin__7325 invoke "query.cljc" 405]
  [clojure.lang.ArrayChunk reduce "ArrayChunk.java" 58]
  [clojure.core.protocols$fn__8154 invokeStatic "protocols.clj" 136]
  [clojure.core.protocols$fn__8154 invoke "protocols.clj" 124]
  [clojure.core.protocols$fn__8114$G__8109__8123 invoke "protocols.clj" 19]
  [clojure.core.protocols$seq_reduce invokeStatic "protocols.clj" 31]
  [clojure.core.protocols$fn__8144 invokeStatic "protocols.clj" 75]
  [clojure.core.protocols$fn__8144 invoke "protocols.clj" 75]
  [clojure.core.protocols$fn__8088$G__8083__8101 invoke "protocols.clj" 13]
  [clojure.core$reduce invokeStatic "core.clj" 6828]
  [clojure.core$reduce invoke "core.clj" 6810]
  [asami.query$eval7305$run_simple_query__7310$fn__7318 invoke "query.cljc" 419]
  [asami.query$eval7305$run_simple_query__7310 invoke "query.cljc" 398]
  [asami.query$eval7389$join_patterns__7394$fn__7395 invoke "query.cljc" 461]
  [asami.query$eval7389$join_patterns__7394 doInvoke "query.cljc" 436]
  [clojure.lang.RestFn invoke "RestFn.java" 445]
  [asami.query$eval7563$execute_query__7568$fn__7569 invoke "query.cljc" 534]
  [asami.query$eval7563$execute_query__7568 invoke "query.cljc" 519]
  [asami.query$eval7783$query_entry__7788$fn__7789 invoke "query.cljc" 652]
  [asami.query$eval7783$query_entry__7788 invoke "query.cljc" 641]
  [asami.core$q invokeStatic "core.cljc" 359]
  [asami.core$q doInvoke "core.cljc" 354]
  [clojure.lang.RestFn invoke "RestFn.java" 423]
  [user$eval10510 invokeStatic "form-init11600158981584690779.clj" 1]
  [user$eval10510 invoke "form-init11600158981584690779.clj" 1]
  [clojure.lang.Compiler eval "Compiler.java" 7177]
  [clojure.lang.Compiler eval "Compiler.java" 7132]
  [clojure.core$eval invokeStatic "core.clj" 3214]
  [clojure.core$eval invoke "core.clj" 3210]
  [clojure.main$repl$read_eval_print__9086$fn__9089 invoke "main.clj" 437]
  [clojure.main$repl$read_eval_print__9086 invoke "main.clj" 437]
  [clojure.main$repl$fn__9095 invoke "main.clj" 458]
  [clojure.main$repl invokeStatic "main.clj" 458]
  [clojure.main$repl doInvoke "main.clj" 368]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [nrepl.middleware.interruptible_eval$evaluate invokeStatic "interruptible_eval.clj" 79]
  [nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 55]
  [nrepl.middleware.interruptible_eval$interruptible_eval$fn__921$fn__925 invoke "interruptible_eval.clj" 142]
  [clojure.lang.AFn run "AFn.java" 22]
  [nrepl.middleware.session$session_exec$main_loop__1022$fn__1026 invoke "session.clj" 171]
  [nrepl.middleware.session$session_exec$main_loop__1022 invoke "session.clj" 170]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.lang.Thread run "Thread.java" 834]]}}
 :via
 [{:type clojure.lang.ExceptionInfo
   :message "Error executing filter: java.lang.ClassCastException: class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
   :data {:error #error {
 :cause "class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
 :via
 [{:type java.lang.ClassCastException
   :message "class clojure.lang.Keyword cannot be cast to class java.util.regex.Pattern (clojure.lang.Keyword is in unnamed module of loader 'app'; java.util.regex.Pattern is in module java.base of loader 'bootstrap')"
   :at [clojure.core$re_matcher invokeStatic "core.clj" 4849]}]
 :trace
 [[clojure.core$re_matcher invokeStatic "core.clj" 4849]
  [clojure.core$re_find invokeStatic "core.clj" 4898]
  [clojure.core$re_find invoke "core.clj" 4898]
  [clojure.lang.AFn applyToHelper "AFn.java" 156]
  [clojure.lang.AFn applyTo "AFn.java" 144]
  [clojure.lang.Var applyTo "Var.java" 705]
  [clojure.core$apply invokeStatic "core.clj" 665]
  [clojure.core$apply invoke "core.clj" 660]
  [asami.query$eval6842$filter_join__6847$fn__6861$filter_fn__6873 doInvoke "query.cljc" 171]
  [clojure.lang.RestFn invoke "RestFn.java" 408]
  [clojure.core$filter$fn__5893 invoke "core.clj" 2821]
  [clojure.lang.LazySeq sval "LazySeq.java" 42]
  [clojure.lang.LazySeq seq "LazySeq.java" 51]
  [clojure.lang.LazySeq withMeta "LazySeq.java" 36]
  [clojure.lang.LazySeq withMeta "LazySeq.java" 17]
  [clojure.core$with_meta__5420 invokeStatic "core.clj" 218]
  [clojure.core$with_meta__5420 invoke "core.clj" 217]
  [asami.query$eval6842$filter_join__6847$fn__6861 invoke "query.cljc" 173]
  [asami.query$eval6842$filter_join__6847 invoke "query.cljc" 155]
  [asami.query$left_join invokeStatic "query.cljc" 305]
  [asami.query$left_join invoke "query.cljc" 297]
  [asami.query$eval7305$run_simple_query__7310$fn__7318$ljoin__7325 invoke "query.cljc" 405]
  [clojure.lang.ArrayChunk reduce "ArrayChunk.java" 58]
  [clojure.core.protocols$fn__8154 invokeStatic "protocols.clj" 136]
  [clojure.core.protocols$fn__8154 invoke "protocols.clj" 124]
  [clojure.core.protocols$fn__8114$G__8109__8123 invoke "protocols.clj" 19]
  [clojure.core.protocols$seq_reduce invokeStatic "protocols.clj" 31]
  [clojure.core.protocols$fn__8144 invokeStatic "protocols.clj" 75]
  [clojure.core.protocols$fn__8144 invoke "protocols.clj" 75]
  [clojure.core.protocols$fn__8088$G__8083__8101 invoke "protocols.clj" 13]
  [clojure.core$reduce invokeStatic "core.clj" 6828]
  [clojure.core$reduce invoke "core.clj" 6810]
  [asami.query$eval7305$run_simple_query__7310$fn__7318 invoke "query.cljc" 419]
  [asami.query$eval7305$run_simple_query__7310 invoke "query.cljc" 398]
  [asami.query$eval7389$join_patterns__7394$fn__7395 invoke "query.cljc" 461]
  [asami.query$eval7389$join_patterns__7394 doInvoke "query.cljc" 436]
  [clojure.lang.RestFn invoke "RestFn.java" 445]
  [asami.query$eval7563$execute_query__7568$fn__7569 invoke "query.cljc" 534]
  [asami.query$eval7563$execute_query__7568 invoke "query.cljc" 519]
  [asami.query$eval7783$query_entry__7788$fn__7789 invoke "query.cljc" 652]
  [asami.query$eval7783$query_entry__7788 invoke "query.cljc" 641]
  [asami.core$q invokeStatic "core.cljc" 359]
  [asami.core$q doInvoke "core.cljc" 354]
  [clojure.lang.RestFn invoke "RestFn.java" 423]
  [user$eval10510 invokeStatic "form-init11600158981584690779.clj" 1]
  [user$eval10510 invoke "form-init11600158981584690779.clj" 1]
  [clojure.lang.Compiler eval "Compiler.java" 7177]
  [clojure.lang.Compiler eval "Compiler.java" 7132]
  [clojure.core$eval invokeStatic "core.clj" 3214]
  [clojure.core$eval invoke "core.clj" 3210]
  [clojure.main$repl$read_eval_print__9086$fn__9089 invoke "main.clj" 437]
  [clojure.main$repl$read_eval_print__9086 invoke "main.clj" 437]
  [clojure.main$repl$fn__9095 invoke "main.clj" 458]
  [clojure.main$repl invokeStatic "main.clj" 458]
  [clojure.main$repl doInvoke "main.clj" 368]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [nrepl.middleware.interruptible_eval$evaluate invokeStatic "interruptible_eval.clj" 79]
  [nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 55]
  [nrepl.middleware.interruptible_eval$interruptible_eval$fn__921$fn__925 invoke "interruptible_eval.clj" 142]
  [clojure.lang.AFn run "AFn.java" 22]
  [nrepl.middleware.session$session_exec$main_loop__1022$fn__1026 invoke "session.clj" 171]
  [nrepl.middleware.session$session_exec$main_loop__1022 invoke "session.clj" 170]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.lang.Thread run "Thread.java" 834]]}}
   :at [asami.query$eval6842$filter_join__6847$fn__6861 invoke "query.cljc" 177]}]
 :trace
 [[asami.query$eval6842$filter_join__6847$fn__6861 invoke "query.cljc" 177]
  [asami.query$eval6842$filter_join__6847 invoke "query.cljc" 155]
  [asami.query$left_join invokeStatic "query.cljc" 305]
  [asami.query$left_join invoke "query.cljc" 297]
  [asami.query$eval7305$run_simple_query__7310$fn__7318$ljoin__7325 invoke "query.cljc" 405]
  [clojure.lang.ArrayChunk reduce "ArrayChunk.java" 58]
  [clojure.core.protocols$fn__8154 invokeStatic "protocols.clj" 136]
  [clojure.core.protocols$fn__8154 invoke "protocols.clj" 124]
  [clojure.core.protocols$fn__8114$G__8109__8123 invoke "protocols.clj" 19]
  [clojure.core.protocols$seq_reduce invokeStatic "protocols.clj" 31]
  [clojure.core.protocols$fn__8144 invokeStatic "protocols.clj" 75]
  [clojure.core.protocols$fn__8144 invoke "protocols.clj" 75]
  [clojure.core.protocols$fn__8088$G__8083__8101 invoke "protocols.clj" 13]
  [clojure.core$reduce invokeStatic "core.clj" 6828]
  [clojure.core$reduce invoke "core.clj" 6810]
  [asami.query$eval7305$run_simple_query__7310$fn__7318 invoke "query.cljc" 419]
  [asami.query$eval7305$run_simple_query__7310 invoke "query.cljc" 398]
  [asami.query$eval7389$join_patterns__7394$fn__7395 invoke "query.cljc" 461]
  [asami.query$eval7389$join_patterns__7394 doInvoke "query.cljc" 436]
  [clojure.lang.RestFn invoke "RestFn.java" 445]
  [asami.query$eval7563$execute_query__7568$fn__7569 invoke "query.cljc" 534]
  [asami.query$eval7563$execute_query__7568 invoke "query.cljc" 519]
  [asami.query$eval7783$query_entry__7788$fn__7789 invoke "query.cljc" 652]
  [asami.query$eval7783$query_entry__7788 invoke "query.cljc" 641]
  [asami.core$q invokeStatic "core.cljc" 359]
  [asami.core$q doInvoke "core.cljc" 354]
  [clojure.lang.RestFn invoke "RestFn.java" 423]
  [user$eval10510 invokeStatic "form-init11600158981584690779.clj" 1]
  [user$eval10510 invoke "form-init11600158981584690779.clj" 1]
  [clojure.lang.Compiler eval "Compiler.java" 7177]
  [clojure.lang.Compiler eval "Compiler.java" 7132]
  [clojure.core$eval invokeStatic "core.clj" 3214]
  [clojure.core$eval invoke "core.clj" 3210]
  [clojure.main$repl$read_eval_print__9086$fn__9089 invoke "main.clj" 437]
  [clojure.main$repl$read_eval_print__9086 invoke "main.clj" 437]
  [clojure.main$repl$fn__9095 invoke "main.clj" 458]
  [clojure.main$repl invokeStatic "main.clj" 458]
  [clojure.main$repl doInvoke "main.clj" 368]
  [clojure.lang.RestFn invoke "RestFn.java" 1523]
  [nrepl.middleware.interruptible_eval$evaluate invokeStatic "interruptible_eval.clj" 79]
  [nrepl.middleware.interruptible_eval$evaluate invoke "interruptible_eval.clj" 55]
  [nrepl.middleware.interruptible_eval$interruptible_eval$fn__921$fn__925 invoke "interruptible_eval.clj" 142]
  [clojure.lang.AFn run "AFn.java" 22]
  [nrepl.middleware.session$session_exec$main_loop__1022$fn__1026 invoke "session.clj" 171]
  [nrepl.middleware.session$session_exec$main_loop__1022 invoke "session.clj" 170]
  [clojure.lang.AFn run "AFn.java" 22]
  [java.lang.Thread run "Thread.java" 834]]}

As a workaround, the regex can be passed as a variable:

=> (q '[:find ?name :in $ ?re :where [?m :movie/title ?name][?m :movie/genre ?genre][(re-find ?re ?genre)]] db #"comedy")
(["Explorers"] ["Toy Story"])

Disjunctions

Provide disjunction operations, as per or in Datomic

Transact operations for graphs

The asami.graph.Graph protocol needs a new function to take multiple triples for load and delete. This is required for transactions, which are necessary for mutable updates that finish with a commit to persistent structures.

Deltas are empty

Databases after a transaction should return a list of entity IDs from the deltas function. Asami currently returns an empty list.

Negation

Provide a NOT option as per Datomic. cf SPARQL MINUS

Regression in `create-bindings` operation

Querying a store with the q operation loses the default store during create-bindings if there is no :in clause.

Subgraph detection

Build on transitive closures on unbound predicates from issue #36 to find all subgraphs.

Optional constraints being mishandled in the planner

Example query showed that optional was inserted twice.

(require '[asami.core :as d :refer [q]])
(def db-uri "asami:mem://movie")
(d/create-database db-uri)
(def conn (d/connect db-uri))
(def first-movies [{:movie/title "Explorers"
                    :movie/genre "adventure/comedy/family"
                    :movie/release-year 1985}
                   {:movie/title "Demolition Man"
                    :movie/genre "action/sci-fi/thriller"
                    :movie/release-year 1993}
                   {:movie/title "Johnny Mnemonic"
                    :movie/genre "cyber-punk/action"
                    :movie/release-year 1995}
                   {:movie/title "Toy Story"
                    :movie/genre "animation/adventure/comedy"
                    :movie/release-year 1995
                    :movie/sequel "Toy Story 2"}
                   {:movie/title "Sense and Sensibility"
                    :movie/genre "drama/romance"
                    :movie/release-year 1995}])

@(d/transact conn {:tx-data first-movies})
(def db (d/db conn))
(d/show-plan '[:find ?name ?sequel :where [?m :movie/title ?name] [?m :movie/release-year 1995] (optional [?m :movie/sequel ?sequel])] db)

Results in:

{:plan ([?m :movie/release-year 1995] (optional [?m :movie/sequel ?sequel]) [?m :movie/title ?name] (optional [?m :movie/sequel ?sequel]))}

GraphQL API

GraphQL is more suited to a hierarchy than a heterogeneous graph. However, there is some utility here, and an expectation of its availability.

The appropriate library to implement this API is Lacinia. Check out what would be needed and how we can go about it.

Allow shortened pattern constraints

Introduce truncated triple-pattern constraints. Datomic allows these constraints to be shortened, as in:

[?entity :my/attribute]

This will bind to any entity that has an attribute, regardless of the associated value. This is semantically equivalent to:

[?entity :my/attribute ?unused]

Where the ?unused variable is not referenced anywhere. This, in turn, is equivalent to using an underscore variable, as in ticket #49:

[?entity :my/attribute _]

Note that single-element patterns are also possible:

[?entity]

This would bind to every entity ID.

Create new functions for reporting query plans

I'm considering a new namespace here: asami.report

The show-plan function can take the same parameters as asami.core/q and return the output of ((asami.core/select- planner options) graph all-patterns options)

If the query is an aggregate then it will need to do some of the same work as aggregate-query which is a risk of losing sync if that ever changes, but I'm happy to deal with that.

Implement unbound negations

Negations which share no bindings with the remainder of the query need to act as a gate. If they do not result in anything, then return the rest of the query. If they have a result, then return nothing.

The current implementation can work (inefficiently), but the query planner may push the negation to the head of the query, which will fail.

Instead, check if any group returns a single (not ...) operation. If so, then this is a gating term and it can go first. When left-join is applied to this operation, then use it as a gate.