vaelii.impl.kv — com.vaelii/vaelii 0.25.0

The key-value substrate the index rests on, and the one IndexStore implementation written over it.

The index — the trie, the secondary roots, the rule indexes, the exception re-check index, and the inverted term index — is all sets and counters keyed by structured vectors. KvIndexStore encodes that structure once, in terms of a small KvBackend protocol; a backend is then just an adapter that says how a scalar, a counter, and a set live in some store. An in-memory map (vaelii.impl.memory) and an on-disk WAL (vaelii.impl.disk.kv) are two such adapters; a SQL or overlay backend is another.

The count-aware trie

A sentex is indexed by its trie path. Every node, identified by its path prefix, is exactly three keys:

count-key [:trie :count prefix] -> integer: how many sentexes live at the leaves under this prefix (selectivity without walking). set-key [:trie :children prefix] -> a SET: the next possible token labels (the node's child edges). leaf-key [:trie :handles prefix] -> a SET: the handles of the sentexes whose path ends exactly here.

Child edges and leaf handles are separate keys because the trie is ragged. Paths differ in length with arity, so one sentex's full path can be a proper prefix of another's: (rel A B) in CxCee keys as [rel A B CxCee], and (rel A B CxCee X) in CxDee keys as [rel A B CxCee X CxDee] — the first path is an interior node of the second. Storing both handles and child tokens in one set therefore mixed them, and a caller could not tell them apart by type (a handle is an integer, and so is the token 1970). Two keys make the distinction structural: lookup reads only the leaf key at its terminus, so it can never return a token as a handle, and children reads only the child set, so plan's fan-out divisor can never count a handle as a branch.

Alongside the trie sit eleven smaller count tries whose last level is the context — the argument roots, the predicate extent, the two rule indexes, the rule extent, the opposed bodies, the self tuples, the arity bindings, the taxonomy's supporters and the mint family's two ("The count tries that end in the context" below) — and three flat sets whose cardinality is their own size: the context root, the exception re-check index and the inverted term index. One more flat set, the term roster [:term-roster], holds the term index's names rather than handles, so the vocabulary can be listed and counted in O(terms) instead of a walk over every record.

Contract: lookup expects a full path (sentence tokens + a context slot; the context may itself be a variable). A short pattern terminates on an interior node, whose leaf key is empty, so it yields nothing rather than that node's child labels dressed up as handles.

The KvBackend

Logical keys are structured vectors and set members are bare values; a backend turns those into whatever its store wants (an in-memory map uses them directly; the on-disk backend nippy-frames them into its log). The required ops are kv-batch (the whole index write for one sentex lands as one unit — one batched write) and kv-intersect (the multi-column narrowing sentexes-with-args needs, one set intersection rather than N fetch-and-filter reads). A batch op is a vector [op key & args] with op one of :put, :delete, :increment, :decrement, :add-to-set, :remove-from-set; kv-batch returns one reply per op in order (only :increment/:decrement replies — the post-op counter value — are read; the rest are placeholders that keep the vector aligned).

kv-member? is a membership test, not a fetch, and it is its own op because on several backends those cost different orders. exception-rule? is the gate chain/rule-view-of takes once per candidate rule per new datum, so answering it by materializing the roster and testing the result makes forward chaining a product of two KB-sized quantities. A flat-map backend hands the stored set back by reference and hides the distinction entirely; a dense one holds the roster as an IntPostings, where 1e5 gate calls against a roster of 1,000 cost 15,926 ms built-then-tested against 87 ms on the flat map — so the op exists to let each backend answer with the probe it already has (a hash lookup, a binary search, a bitmap test).

apply-op clj

(apply-op m [op k a])

Apply one kv-batch write op to map m, returning [m' reply]. Only :increment/:decrement carry a meaningful reply (the post-op counter value); the rest reply nil. :remove-from-set drops the key when the set empties, so an absent key and an empty set are indistinguishable — a set with no members does not exist.

The op semantics live here, with the protocol that names them, and not in the backends. Both map-shaped backends fold their writes through this — the in-memory one (vaelii.impl.memory) over its state map, the on-disk one (vaelii.impl.disk.kv) over the RAM half of its write-ahead log, where it is also what replays the log, since a WAL frame there is the write op itself rather than the resulting value. Written twice, the two copies could answer one op differently, and the disk side is replay: a seventh op added to the live path and missed in the fold would be a write that applies once and never comes back.

An unrecognized op goes to unknown-op!, which every adapter shares: a bulk load taking the transient path, a dense backend's own batch, a fork decorator's, and an ordinary write taking this one may not disagree about what an unreadable op is.

:decrement floors at zero, per the KvBackend contract: these counters are cardinalities. The floor is in every fold rather than in one of them, because the WAL replays through this and the live write went through a backend — a floor applied on only one side would make a reopened store disagree with the one that wrote it.

arg-slots clj

(arg-slots sentex)

[[pred pos term] ...] - the argument-root nodes a fact enters, each term canonical. Empty for a rule and for a non-fact, matching root-keys.

The canonicalization is here rather than in the key constructors so a term reaching a key or a backend read is canonical whichever of the three rosters it is going into.

family-ctxs clj

(family-ctxs op ctxs)

ctxs as a family read takes it: nil for p/every-context, the set otherwise. Throws on nil, which a reader passes by forgetting its ancestor set. Both implementers call it.

flat-family-adds clj

(flat-family-adds backend trie sentex handle)

{:ops [...] :counts {:terms n :roots n :roster n :slots n}} — the non-trie write ops entering sentex under handle, and the number of ops each family takes.

Both roster reads run here, before the caller batches the ops, so a name enters the term roster and a predicate enters its argument slot exactly on the first sentex to carry it.

flat-family-retires clj

(flat-family-retires backend trie sentex handle)

{:ops [...] :counts {:terms n :roots n :roster n :slots n}} — the mirror of flat-family-adds: the ops taking handle out of those same families, and the number of ops each family takes.

Every read runs here, before the caller batches the ops, so a name leaves the term roster, a predicate leaves its argument slot and a node leaves the argument trie exactly on the last sentex to carry it.

index-families clj

The index families, one row per key tag (the first element of every key the index writes), as data. dense-kv's handle-posting test reads :leaf, the importer's records-only test reads :source, and the root-roster keys below read :root. docs/indexing.md, "The index-family registry", states what each field decides.

• :shape — :trie, :count-trie ([tag :count|:children node] and [tag :handles (conj node ctx)]), :set or :counter.
• :leaf — :handles (int postings) or :names (terms, keys); nil for a counter.
• :context-last? — whether the key's last level is the context.
• :children? — whether a node lists the contexts below it.
• :root — the tag of the roster one level above the family's nodes, where one is stored.
• :canon? — whether a key term is sx/canon'd.
• :source — what the write posts from: :sentex (index-sentex), :rule (rules/index-rule, rules/index-exception), :justification (special/post-mint!) or :taxonomy (taxonomy's post!).
• :class — what a KB without the family loses: :access-path, :scan-recoverable or :sole-witness, with :class-evidence holding :oracle (test vars) and :via (the families the other path reads), :writes (the writes that read the family, empty when none does) or :readers.

index-layout-version clj

Which key shapes this build's index is written in.

The key families below — [:trie :count|:children|:handles prefix], the context root, the five count tries ending in the context, the exception index, the term index and the rosters — are the index's portable form, so a dump of them is only readable by a build that agrees on them. An index written in a layout this build does not use reads as empty rather than as wrong (a lookup finds no key and answers nothing), which is fail-safe and undiagnosable — so the layout is stated as a number and checked, rather than discovered by a KB that quietly stopped answering.

Bump it whenever a key shape changes: a new family, a renamed tag, a different arity, or a different value type at an existing key.

2 scopes the argument roots by predicate ([:argument-root pred pos term]) and adds the [:argument-slot pos term] roster that keeps the predicate-agnostic reads answerable. 3 adds the [:unary-slot term] roster beside it, which is what lets a membership question read a term's types without fetching every fact that names it. 4 keys the argument roots as a count trie over [pred pos term ctx]: a node's [:argument-root :count|:children [pred pos term]] and the leaf [:argument-root :handles [pred pos term ctx]]. 5 replaces the functor root with the predicate extent, a count trie over [pred ctx], and keys the two rule indexes as count tries over [key ctx] (:rule-antecedent, :rule-consequent). 6 adds the rule extent, a count trie over [kind ctx] (:rule-extent), and the antecedent trie's root level, [:rule-antecedent-keys]. 7 adds the bodies stored in both polarities: the count trie :opposed over [body ctx], its root level [:opposed-bodies], and the members by context, [:opposed-in ctx]. 8 adds the taxonomy's supporter families: a count trie over [k ctx] keyed by the key a declaration installs (:tax-support), and [:tax-installs h]. 9 adds the mint family: the :mint count trie over [term ctx] with its root level [:mint-terms], and the :mint-in count trie over [ctx]. 10 adds the shape roster, [:shape-count f n] and [:shape-lengths f], [:unary-multi], the terms the unary roster lists two or more predicates of, and the self-tuple count trie over [pred ctx] (:self-tuple). 11 adds the same terms by predicate, [:unary-kept pred] and [:unary-kept-types], and the terms a stored denial names by predicate, [:unary-denied pred] and [:unary-denied-types]. 12 adds the arity bindings: the count trie :arity-binding over [pred kind value ctx], with [:arity-binding-kinds pred] and [:arity-bound] above its nodes. 13 replaces the shape counter with the count trie :shape-tuple over [f n ctx], the positive facts of functor f holding n arguments, with [:shape-lengths f] above its nodes.

justification-family-entry? clj

(justification-family-entry? entry)

Is entry, a [key value] index entry, one of a family the stored justifications derive rather than the stored sentexes (:source :justification in index-families)?

root-keys clj

(root-keys sentex)

The handle postings a sentex enters outside the trie and the term index: its context root always, plus the leaf under each of its fact-nodes in its context.

roster-adds clj

(roster-adds backend terms)

The write ops entering terms (one sentex's, from sentex-terms) in the roster — read BEFORE their postings are written, so a name is entered exactly by the first sentex to mention it.

roster-retires clj

(roster-retires backend terms handle)

The write ops retiring the names in terms that handle is the last mention of — read BEFORE their postings are removed, so a name dies exactly when its posting is #{handle}.

sealed-prefix clj

The count prefix of the batch-seal counter: incremented as the last op of every index-sentex batch and decremented as the last op of an unindex's cleanup batch, so it equals the indexed-sentex count exactly when every batch landed whole. The durable open's coverage gate compares it against the record count: the WAL logs one frame per op, so a torn tail keeps a batch's prefix — the root counter count-at [] reads is op 0 and survives every tear, which is what makes it the wrong instrument — while this counter is the op a tear loses first. A namespaced keyword, so it collides with no term path; only the count key is written, so no trie walk ever meets it. Zero on a store whose index arrived by index-load replay or was written before the counter existed — the gate falls back to the root count there.

sentex-terms clj

(sentex-terms sentex)

The distinct terms that make a sentex findable: its indexable content terms (see sentex/index-terms — connective-free, no numbers/strings/variables) plus its context.

slot-adds clj

(slot-adds backend sentex)

Write ops entering a sentex's predicates in their slots - read BEFORE the postings are written, so a predicate is entered exactly by the fact that creates its node.

The unary roster is the exception and takes no read at all: its entry is written by every unary fact rather than by the first, because the node that guards the others is [pred 1 term], which a binary fact of the same predicate about the same term also creates - so a reference count read off it would skip the unary entry whenever the binary fact arrived first, and a missing entry there loses a membership. An :add-to-set of a member already present is a no-op inside the same batch. A term joins unary-multi-key when the entry is its second predicate, which two reads of the unary roster decide, and unary-kept-key under each predicate it then holds (kept-adds).

term-key clj

(term-key term)

trie-reads clj

(trie-reads count-at children leaf)

The two trie reads the opposed family's writes take, over count-at (prefix -> count) and children and leaf (prefix -> set): :count, and :leaves, the [child handles] of each child of a prefix whose leaf one level below holds a handle.