Hi Jack 🙂 this answer is assuming that you are referring to persisting Datalog facts, rather than Datalog queries. I'd say the difference between a "graph database" and a KV store here is one of abstraction. Graph databases offer a high-level API but may use many different strategies for persistence and indexing behind the scenes, for instance https://oss.redis.com/redisgraph/ uses sparse matrices and https://terminusdb.com/ uses succinct data structures. However a sorted-KV interface (whether backed by a b-tree, LSM or something more fancy) is also a valid and useful storage abstraction on which to build a graph database - this is essentially the approach taken by all of the Datalog engines listed on https://clojurelog.github.io/ (with the exception of Asami, IIRC).

All layering of abstractions come with costs and all underlying data structures have different performance & scaling trade-offs. For instance sparse matrices are expensive to update, which makes them broadly inappropriate for OLTP use-cases (as I understand it), but they are a good order of magnitude faster for querying than anything else.

Very helpful. Thanks 🙂