Incremental Queries

The query engine normally evaluates a pattern against a complete TribleSet, recomputing every match from scratch. Applications that ingest data continuously often only need to know which results are introduced by new tribles. Tribles supports this with semi‑naive evaluation, a classic incremental query technique. Instead of running the whole query again, we focus solely on the parts of the query that can see the newly inserted facts and reuse the conclusions we already derived from the base dataset.

Delta evaluation

Given a base dataset and a set of newly inserted tribles, the engine runs the original query multiple times. Each run restricts a different triple constraint to the delta while the remaining constraints see the full set. The union of these runs yields exactly the new solutions. The process is:

compute a delta TribleSet containing only the inserted tribles,
for every triple in the query, evaluate a variant where that triple matches against delta,
union all per‑triple results to obtain the incremental answers.

Because each variant touches only one triple from the delta, the work grows with the number of constraints and the size of the delta set rather than the size of the full dataset.

In practice the base dataset is often cached or already available to the application. Maintaining a delta set alongside it lets the engine quickly answer “what changed?” without re-deriving prior results. If the delta is empty the engine can skip evaluation entirely, making idle updates effectively free.

Monotonicity and CALM

Removed results are not tracked. Tribles follow the CALM principle: a program whose outputs are monotonic in its inputs needs no coordination. Updates simply add new facts and previously derived conclusions remain valid. When conflicting information arises, applications append fresh tribles describing their preferred view instead of retracting old ones. Stores may forget obsolete data, but semantically tribles are never deleted.

Exclusive IDs and absence checks

Exclusive identifiers tighten the blast radius of non-monotonic logic without abandoning CALM. Holding an ExclusiveId proves that no other writer can add tribles for that entity, so checking for the absence of a triple about that entity becomes stable: once you observe a missing attribute, no concurrent peer will later introduce it. This permits existence/absence queries in the narrow scope of entities you own while keeping global queries monotonic.

Even with that safety net, prefer monotonic reads and writes when possible because they compose cleanly across repositories. Absence checks should be reserved for workflows where the ExclusiveId guarantees a closed world for the entity—such as asserting a default value when none exists or verifying invariants before emitting additional facts. Outside that boundary, stick to append-only predicates so derived results remain valid as new data arrives from other collaborators.

Example

The pattern_changes! macro expresses these delta queries. It behaves like pattern! but takes the current TribleSet and a precomputed changeset. The macro unions variants of the query where each triple is constrained to that changeset, matching only the newly inserted tribles. It keeps the incremental flow compatible with the familiar find! interface, so callers can upgrade existing queries without changing how they collect results.

#![allow(unused)]
fn main() {
    let storage = MemoryRepo::default();
    let mut repo = Repository::new(storage, SigningKey::generate(&mut OsRng));
    let branch_id = repo.create_branch("main", None).expect("branch");
    let mut ws = repo.pull(*branch_id).expect("pull");

    // Commit initial data
    let shakespeare = ufoid();
    let hamlet = ufoid();
    let mut base = TribleSet::new();
    base += entity! { &shakespeare @ literature::firstname: "William", literature::lastname: "Shakespeare" };
    base += entity! { &hamlet @ literature::title: "Hamlet", literature::author: &shakespeare };
    ws.commit(base.clone(), None);
    let c1 = ws.head().unwrap();

    // Commit a new book
    let macbeth = ufoid();
    let mut change = TribleSet::new();
    change += entity! { &macbeth @ literature::title: "Macbeth", literature::author: &shakespeare };
    ws.commit(change.clone(), None);
    let c2 = ws.head().unwrap();

    // Compute updated state and delta between commits
    let base_state = ws.checkout(c1).expect("base");
    let updated = ws.checkout(c2).expect("updated");
    let delta = updated.difference(&base_state);

    // Find new titles by Shakespeare
    let results: Vec<_> = find!(
        (author: Value<_>, book: Value<_>, title: Value<_>),
        pattern_changes!(&updated, &delta, [
            { ?author @ literature::firstname: "William", literature::lastname: "Shakespeare" },
            { ?book @ literature::author: ?author, literature::title: ?title }
        ])
    )
    .map(|(_, b, t)| (b, t))
    .collect();

    println!("{results:?}");
}

The example stages an initial commit, records a follow-up commit, and then compares their checkouts. Feeding the latest checkout alongside the difference between both states allows pattern_changes! to report just the additional solutions contributed by the second commit. This mirrors how an application can react to a stream of incoming events: reuse the same query, but swap in a fresh delta set each time new data arrives.

Delta maintenance always comes down to set algebra. pattern_changes! cares only that you hand it a TribleSet containing the fresh facts, and every convenient workflow for producing that set leans on the same few operations:

take two snapshots and difference them to discover what was added;
union the new facts into whatever baseline you keep cached;
intersect a candidate subset when you need to focus a change further.

Workspaces showcase this directly. Each checkout materializes a TribleSet, so comparing two history points is just another snapshot diff: take the newer checkout, difference it against the older one to obtain the delta, and hand both sets to pattern_changes!. That matches the local buffering story as well. Keep a baseline TribleSet for the current state, accumulate incoming facts in a staging set, and union the staging set with the baseline to produce the updated snapshot you pass as the first argument. The delta comes from difference(&updated, &old) or from the staging set itself when you only stage fresh facts. Reusing the same set helpers keeps the bookkeeping short, avoids custom mirrors of the data, and stays efficient no matter where the updates originate.

Comparing history points

Workspace::checkout accepts commit selectors which can describe ranges in repository history. Checking out a range like a..b walks the history from b back toward a, unioning the contents of every commit that appears along the way but excluding commits already returned by the a selector. When commits contain only the tribles they introduce, that checkout matches exactly the fresh facts added after a. Feeding that delta into pattern_changes! lets us ask, “What new matches did commit b introduce over a?”

Trade‑offs

Applications must compute and supply the delta set; the engine does not track changes automatically.
Queries must remain monotonic since deletions are ignored.
Each triple incurs an extra variant, so highly selective constraints keep incremental evaluation efficient.
Delta sets that grow unboundedly lose their advantage. Regularly draining or compacting the changeset keeps semi-naive evaluation responsive.

Tribles Book