Contents

Store Record Search and Fact Projection

This note defines how runtime stores supply admitted records to Datalog without becoming Datalog engines, exposure authorities, or public raw store APIs. The numbered specs define record and Datalog truth; this document defines the implementation boundary.

Boundary

The store boundary is semantic operation data:

StoreOp -> StoreResult | StoreError

Operations:

CurrentStorePosition
ResolveStoreRecordIds
FindRecords
LoadRecordsByHash
LoadRecordsByStoreId
StoreRecords

Results:

CurrentStorePosition(StorePosition)
ResolvedStoreRecordIds([StoreRecordId | Missing])
FoundRecords(rows, continuation)
LoadedRecords([Loaded(record bytes) | Missing])
StoredRecords([Stored(StoreRecordId) | Duplicate(StoreRecordId)], StorePosition)

Resolve, exact-load, and store vectors are positional against their ordered requests. Their outcomes do not echo requested hashes, requested ids, input record hashes, or response indexes. Loaded bytes, returned ids and dispositions, post-store position, broad-query discoveries and continuation, and typed errors remain because they carry new information.

Rust stores implement the doc-hidden runtime_support::StoreBackend trait: execute(StoreOp), an Inline or Blocking execution class that selects runtime scheduling, consuming close, and one provided current_position that rejects any other result shape as a store failure. Runtimes adopt one boxed backend; no public constructor accepts the trait.

StoreCall carries one such operation between a machine and its host-selected store. It remains machine-owned. Foreign hosts execute one owned StoreWork and submit one complete ticket-checked result as defined in store-request-response-ffi-boundary.md. A pending operation never becomes empty facts, and StoreError remains an error.

What stores do

A store persists admitted records and answers policy-neutral questions:

A store may use in-memory maps, ephemeral or durable posting lists, transactions, workers, LMDB/SQL indexes, OPFS files, or scan-equivalent fallback. Those choices do not change the result semantics. The shared Rust indexed in-memory store uses ephemeral primitive-key posting lists; it remains a store implementation, not a fact database.

Store adoption and coherent access

One runtime-owned Lace exclusively adopts one concrete store object. A built-in store object is consumed or marked claimed at adoption; a second adoption fails at that object, without a registry, and an adopted object exposes no record operation around its Lace. Raw aliases and advanced custom-store aliases cannot be enforced by Lace and therefore carry an explicit caller-owned single-owner, no-bypass contract.

Adoption also fixes exactly one immutable metadata value:

position_may_advance_externally: bool

false guarantees that StorePosition advances only through mutations executed by the adopting Lace. true means an outside advance is possible and makes CurrentStorePosition the Lace’s authoritative external-progress probe. The value is adoption metadata passed alongside the concrete store; it is not a StoreOp, a fact or protocol input, or a property that every store implementation exposes. Memory, portable file, and filesystem-shaped stores, including native, Node, OPFS, and browser local storage, adopt false. The optional native LMDB store adopts true. Lace-100 owns the public Python custom-store signature and its validation order; lace-tokio, lace-rt, and JavaScript expose no generic public custom-store boundary.

A native filesystem root has one exclusive lifetime owner. An independent same-process or cross-process opener, including a path alias, fails on lock contention. The optional LMDB profile permits one environment per physical root per process; cooperating processes may share it, while same-process operations share Lace handles. Its physical schema and streaming, non-resident index realization are owned by native-lmdb-store.md. Each root owns its admission order, hash-to-id relation, committed prefix, and StoreRecordId and StorePosition domain. That domain is monotonic within one adoption. Compaction, which runs while no Lace adopts the root, restarts it contiguously from 1 while preserving the retained records’ relative admission order; no store operation removes a record.

Explicit Lace close prevents new handle access, drains concrete active reads, mutations, and position refreshes, then consumes the store object. Filesystem close releases exclusive root ownership. LMDB close does not affect other processes’ environments. Without explicit close, handles and started work keep their concrete resources alive until final owner drop.

CurrentStorePosition returns one coherent non-regressing position that includes every commit completed before its read linearization point; a concurrent commit may linearize before or after that read. StoreRecords also returns its mutation result position, but the Lace confirms publication through the mandatory post-mutation CurrentStorePosition probe.

The Lace serializes mutations and authoritative position refreshes through durable classification, current-position refresh, and monotonic position publication. Native filesystem operations use resident admitted state established by open recovery and local mutations, including durable reconciliation after failed writes. LMDB reads the last primary entry in a fresh transaction; it has no admission replay, cached validated prefix, or open-time consistency scan. FindRecords and ResolveStoreRecordIds honor their explicit fixed read_through without widening that semantic boundary. Exact immutable loads use the requested hash or retained StoreRecordId/expected-hash association and do not gain a speculative read_through field. Each backend supplies coherent records and authoritative Missing outcomes.

What stores do not do

Stores do not own or receive:

Exposure is policy lowering above the store boundary. Peer-origin record-fact resolution sees only the peer exposure view because the evaluator filters owning records by evaluator-owned hash membership before record-fact projection and logical candidate-work accounting. The store receives ordinary batched identity resolution and load requests, with no exposure or viewer input. The compiled evaluator mechanics are defined in interlace-policy-lowering.md.

FindRecords

FindRecords is a same-record candidate search. The supported query shape is intentionally small:

The store returns matching full records in increasing admission order. It does not return Datalog variable bindings. Datalog projects facts and builds bindings above the store result.

FindRecords uses one range and continuation model. Both boundaries are explicit StorePosition values; a returned row is always a nonzero identity:

lower_exclusive < StoreRecordId <= upper_inclusive
resume_after: optional last returned StoreRecordId

upper_inclusive is at most the evaluation snapshot’s fixed read-through. With a cursor, only greater ids inside the range are returned. Results are unique and strictly increasing. max_rows applies after query constraints. For a nonzero or unbounded limit, complete means no matching row remains beyond the returned cursor. A zero limit returns empty-complete without candidate traversal or index materialization; it is not an exhaustion probe. Lifecycle, failed-write recovery, and finite read-boundary validation still precede this result. A finite read-through above the current position fails; raw u64::MAX selects the observed high-water. These boundary checks also apply to empty identity-resolution batches. Empty incomplete progress is invalid.

A store must not count false positives toward max_rows, omit matching records inside a complete range, or report empty-not-complete as ordinary progress. If it cannot safely answer, it returns a store failure or an incomplete result that the caller must respect. A candidate id within the observed high-water that has no committed row is a store failure (CorruptStore), never filtered absence.

Candidate traversal

Rust stores share one planner and read executor in runtime_support::store_index. The planner chooses one candidate source by a single narrowing ladder: exact hash; otherwise posting keys for exact fields, field presence, field prefixes, link targets, link name/data, and link name-only presence (a link is a field occurrence of its name), omitting presence implied by another key on the same field; otherwise a scan. Backends supply only posting candidates and committed rows. Stores without prefix lists narrow a prefix by its field’s presence list.

The shared Rust indexed-memory/native filesystem stores and JS Node/OPFS stores seek query bounds in sorted posting lists, then intersect borrowed slices or retained arrays lazily in increasing id order; the portable file store intersects the same way over list files read a page at a time. The shortest bounded list drives monotone traversal of the others. LMDB drives with its smallest posting by duplicate count and checks the other keys by exact pair seeks. Query scratch is proportional to the number of participating lists, not their members; scans likewise walk the bounded admission range without collecting candidate IDs. Index preparation and cold read/repair may still require full-list or unchecked-suffix work. Filesystem posting lifetimes belong to filesystem-shaped-store.md.

Every candidate still passes the complete record matcher. A bounded query stops at one additional matching row beyond max_rows, not one additional candidate; exhaustion without that extra match establishes completeness. Results retain only returned records, not intermediate candidate bags. Native candidates_visited diagnostics count residual candidates actually visited, including the completeness lookahead or a candidate whose record load failed. They neither count IDs skipped inside intersections nor exhaust a query to obtain a total. These diagnostics do not change evaluator work accounting.

Coherent Datalog evaluation

Each round’s evaluation observes one finite coherent record view at one root-wide read_through. The advertisement phase obtains CurrentStorePosition and establishes that value as the endpoint’s round-local boundary; the request phase reuses it instead of obtaining a new position. Every store search and identity batch in either phase reads through that value. ResolveStoreRecordIds atomically maps a unique ordered hash vector to a positional vector of Option<StoreRecordId> at that boundary; the result does not repeat the hashes. Indexed stores perform direct lookups; linear stores scan once. Local or external commits while host work is pending do not widen the fixed boundary: newer records remain outside both round evaluations and can participate only in a later round.

The session evaluator carries its state from round to round and reads only what the store admitted since the previous boundary B_{r-1}. A scan group’s change is one FindRecords over its own same-record query with lower_exclusive = B_{r-1} and upper_inclusive = B_r, so a selective query never enumerates unrelated commits. Watched missing values settle as described under evaluator record values. Every search is paged, at most 256 records per page, through max_rows and resume_after.

Incomplete search is not safe input to MaySend or MayRequest. Evaluation resumes ordered FindRecords continuation and exposes an output only after its dependencies reach a fixed point. A scheduling page boundary is not semantic exhaustion.

Pending store work is never interpreted as empty facts.

Fact projection

Base record facts remain the 020 predicates:

Have(Record)
Field(Record,name,index,value)
RecordLink(Record,name,index,data,Target)
ContainsRecord(Outer,Contained)

Fact projection is owned by Rust Datalog/interlace code above the store-facing API. From returned records or identities, the evaluator applies:

Hot-path projection should use scoped visitors over trusted committed record bytes where possible. Owned tuple bags are for derived facts, diagnostics, and tests, not the normal base-record fact path.

Direct finite record snapshots

RecordSnapshot is the doc-hidden finite evaluator adapter used by pure tests, tools, and fixtures. It retains validated Record values in admission order plus one owner-hash map required for bound-owner lookup, Have membership, and direct admission-order resolution. It does not retain projected base-fact tuples.

Construction also counts the complete projected facts and maximum fact arity without retaining tuples. Generic finite evaluation checks these counts together with all supplied tuple and runtime inputs against its prepared limits, including unused inputs. This explicit finite-input boundary does not add a store count operation or a scan to lazy exchange evaluation.

Generic finite evaluation runs the session evaluator for one round and answers its record requests from the snapshot, so direct snapshots and store-backed evaluation share one visitor-based matcher for one candidate record. A snapshot chooses candidates by one owner-map lookup or an admission-ordered scan; a runtime store chooses candidates through FindRecords under its coherent read boundary. In both cases, validated record bytes establish exact Have, Field, RecordLink, and ContainsRecord matches above candidate selection.

Complete owned tuple bags remain explicit test and diagnostic projections, not a base-record access representation. A direct snapshot’s one-based admission position is logical finite-evaluator state and is not physical StoreRecordId identity.

ContainsRecord is projected in Rust from validated record views, never queried as a store constraint. H3 projection emits no row for a Blob, the contained Blob for a Plex, and both the contained Plex and Blob for a Seal. The relation is the complete canonical nesting set; it excludes record links and record-shaped Blob data.

When ordinary exact-hash, field, or link constraints cannot narrow the local-origin owning Outer, evaluation uses one complete scan-equivalent store request. A group gated by a unary relation over its owner, such as an exposure wrapper, instead probes the gate’s owners: their unknown identities resolve in batches at the read boundary, Have-only membership uses those identities without bytes, and other projections batch-load the held owners by identity. Hidden outer records enter neither containment projection nor its candidate work. Indexed stores avoid unrelated owners; scan-oriented stores resolve the hash batch without a separate scan per owner. The concrete backend determines the batch’s lookup cost. Stores receive no owner filter, viewer, exposure, or containment query. See interlace-policy-lowering.md for guarded-rule execution.

Cross-record joins stay above stores

A rule such as:

same_topic(Record1,Record2) :- Field(Record1,'Topic',_,topic), Field(Record2,'Topic',_,topic).

is evaluated as store candidate searches plus Datalog joins on topic. The store is not asked for a multi-record query. A later group whose owner is unbound but whose search depends on an earlier binding groups each block of up to 1,024 bindings by the query each needs and issues one paged search per distinct query. A block needing more than 64 distinct queries issues the group’s unbound query once instead and joins each found record with the bindings one of its facts can match, keyed by the values of the group atom’s bound arguments. Either way a search suspends evaluation and resumption continues at the suspended step and block, so such a join’s work, like that of a binding-dependent negated or counted atom, grows linearly with its bindings and the records found.

A query step whose group a unary relation gates, such as an exposure wrapper with a selective bound argument, reads at most one record more than the gate holds rows. It then serves every binding still owed from the gate’s owners, each binding owing only the records above the identity its query had reached. Likewise, a gated scan group whose gate holds fewer rows than the round admitted records takes its change from the gate’s owners admitted in the round. Hidden records cost no logical work on any of these paths.

Same-record repeated variable equality, for example Field(Record,'Label',_,value), Field(Record,'Mode',_,value), is also not a required store fast path. The evaluator may request broader candidates and filter while projecting facts.

Admission-order comparison

AdmitOrder(Record) is a Datalog ordering expression backed by local StoreRecordId. It is not a record fact, store operation, public identity, or cursor API. The evaluator resolves it only for records with visible Have in the current fact view. Peer-origin evaluation therefore gates every referenced record through exposure.

A compiled comparison adds a Have group for each operand and compares the operands’ session identities, so an absent or hidden record has no admission-order value. The operands’ identities resolve in one batch per block of bindings rather than one suspension per binding. A comparison between a record group’s owner and a constant anchor whose identity the session id map holds also narrows that group’s FindRecords range: '>' and '>=' raise its lower bound to the anchor, '<' and '<=' lower its upper bound. An anchor that is not held leaves the range, and the comparison rejects every record. For TopK(candidate(...),PartitionBy(...),AdmitOrder(...),direction,k), the evaluator applies candidate constraints and origin-aware exposure before constructing partitions or ranking. Peer ordering records require independently visible Have, including when the candidate names a static hash or a disclosed link target. Global and partitioned TopK use bounded winner heaps above the store after complete lower-stratum candidate derivation, ranking again only the partitions a round’s candidate changes touch. Candidate definitions are not truncated by an ordered store limit. The store receives neither partition tuples nor an aggregate operation.

Evaluator record values

Within one session, a record-reference value is either a local stored identity (StoreRecordId, RecordHash) or a hash whose local admission is unknown. Logical equality, tuple keys, deduplication, tie-breaking, and protocol output use the hash. Admission ordering and load-by-id use the retained stored identity.

Owning record arguments returned by visible Have, Field, RecordLink, and ContainsRecord access may refine from hash to stored identity. A link target or ContainsRecord contained argument does not refine merely because its owning record is stored; it requires independently visible Have, preserving 020 semantics. Admitting an outer does not assign its contained hashes a StoreRecordId or make them loadable by hash. Stores may privately deduplicate contained bytes, but that physical state is not admission or Datalog state. Stored identities never cross physical admission domains, sessions, source text, advertisements, or wire boundaries. Cooperating LMDB processes over one root use the same domain and resolve the same admitted hash to the same id.

The session id map records each value’s identity at the round boundary: a held record keeps its id while any relation row or constant references the value, and a missing one stays missing within the round. A probe group whose owner a constant or a relation row binds watches the owners it finds missing. At the next boundary the evaluator settles them by resolving the watched hashes again, in batches of 1,024, or by reading the records admitted in (B_{r-1}, B_r] when those are fewer; the watched values that became held are that group’s change. A probe whose owner only record facts bind keeps no watch and takes its change from the admitted records. Entries no relation row or constant references are reclaimed between rounds, so long sessions do not grow with values they no longer hold.

A record-fact group whose owning record every binding of a block already names, such as a link target bound by an earlier group, resolves the identities the map does not know in one batch and, when projection needs bytes, loads the held owners in one LoadRecordsByStoreId batch, instead of one exact search per binding. Negated and counted record atoms over a bound owner are acquired the same way; over the owner of a positive group in the same rule they are tested inside that group’s record. Records loaded for a block are dropped after it. Every loaded view used for an identity is checked against its expected hash. Conflicts and malformed successful responses fail as Integration; returned store errors remain Store. These are local association checks, not a store-wide audit. Equality and hash-table operations never perform hidden StoreCall.

Store ids and indexes

StoreRecordId is the only durable local record identity. For a native store, “local” means the physical root’s admission domain rather than one opener or process:

Durable posting lists, SQL row mappings, LMDB keys, and OPFS indexes may contain StoreRecordId values or exact physical encodings of them. They must not create a second durable identity.

Store indexes are internal, rebuildable candidate finders, never a public authority surface. Corrupt or stale indexes repair, rebuild, or fall back to scan-equivalent search; inability to do so is an operational failure. Rows are committed truth, not acceleration: an admitted id without a row is a store failure. Durable heat and materialization policy belongs to filesystem-shaped-store.md.

In-memory store terminology

The shared Rust indexed in-memory store is the normal cross-runtime memory store primitive. It uses ephemeral posting lists to narrow same-record candidates, then applies trusted-record byte visitors as a correctness guard. It does not retain a durable facts layer or an unbounded per-record projection cache.

A runtime-native linear in-memory store is a host-language implementation that scans admitted records to answer FindRecords. These stores are explicit advanced examples of the StoreOp -> StoreResult contract, tiny-store experiments, and scan-equivalent correctness oracles. They are not used by normal application Laces, public porcelain providers/captures/observers, or performance comparisons. Scanning trusted record bytes is distinct from allocating and retaining decoded fact objects; examples should use operation-scoped visitors and add bounded projection caches only after measurement.

Normal operation-owned providers, captures, and observers use the shared Rust indexed in-memory store too. Bindings may seed a finite provider through an opaque one-shot builder over validated records. Runtime-local bounded result collectors may retain the bytes seen in that operation’s StoreCall requests and select results from record events; this is not a public raw store API or a persistent facts cache.

Durable implementations

The optional lmdb-lace workspace crate implements this boundary directly using lace-sans-io operation/result types. It owns no StoreWork, runtime, or policy. Its LMDB metadata/indexes and shared immutable arena retain no per-record Rust metadata collection. All consumers keep their direct sans-IO dependency.

Filesystem-shaped stores implement this semantic boundary without adding a durable facts layer. Their layout, commit, recovery, and index contracts live in filesystem-shaped-store.md. OPFS and Node file adapters remain host-owned; parsing trusted committed bytes to narrow FindRecords candidates is store work, not protocol validation or Datalog.

Validation and trust

Cryptographic record validation occurs at record creation/import boundaries and when ILTP reads untrusted record bytes. Typed records reach StoreRecords; the store does not validate them.

After admission, provider seeding and ordinary load/query/reopen/response paths trust committed store state. They may check a cheap typed glyph and required request/hash association while reconstructing a record wrapper, but do not rerun hashes, embedded-hash checks, or Seal marks. Explicit repair, audit, and corruption recovery may validate stored bytes as maintenance work.

Foreign-host response validation protects the Rust state machine from malformed response shape; it does not create another cryptographic admission boundary or make a faulty store correct. Exact-load bytes are checked against the requested hash or frozen expected hash using the request retained by StoreCall; the host does not echo that identity in the outcome. Exact checks are defined in the ABI appendix.

A store operation may make durable progress before a later IO failure. The owning Lace confirms the durable outcome through CurrentStorePosition even when the operation returns StoreError. Native filesystem writes reconcile their durable log prefix after failure; LMDB reads its committed transactional tip. The error remains an error, and any confirmed advance is published once. If durability failure leaves that position unknowable, Lace invents no position; the concrete store remains the sole authority for whether later ordinary operations can continue. The store error is operation-local unless it occurs in a Lace-owned external-position probe. Async runtimes retain concrete pending work across cancellation long enough to classify that outcome.

The runtime-owned Lace owns mutation sequencing through a mandatory post-mutation CurrentStorePosition refresh and monotonic position publication. Every other same-Lace store call waits outside that complete interval. For a shared-root backend such as LMDB, the refresh may observe a later external commit and publishes the greatest confirmed position. A Lace-owned non-mutating authoritative refresh uses the same gate. Concurrent operations cannot publish StorePosition advances out of order.

Failure of a Lace-owned external-position probe is a terminal Store failure; failure to publish a confirmed position is a terminal Integration failure. Either atomically poisons the Lace, with the first terminal failure retained for all subscribers and close. Later store execution and participant claims are rejected. An ordinary operation-local store failure does not poison the Lace, and a failed StoreRecords remains operation-local when its mandatory refresh and publication succeed. Late mutation or refresh work may publish confirmed progress after its initiating machine boundary was retired, but it never submits to the retired machine. Retirement of the operation that began an external probe does not suppress poisoning. Lace close waits for every started refresh and publication and returns the retained first terminal failure after non-cancellable work drains.

Operation-owned stores

Directional policy is not a store operation or search constraint; stores never receive disabled facets or side roles. Providers, captures, and observers use ordinary store operations, and capture failure never permits target-store inspection. Their operation composition belongs to runtime-provider-architecture.md.

Public boundary

Public applications must not receive direct insert, raw load, record count, posting-list, index, or raw iteration APIs. Public record access goes through LaceHandle, interlace, and porcelain such as get, list, store, and for_each.

Tests

Use scan-equivalent behavior as the correctness oracle. Boundary tests should cover: