relmath

relmath is the library crate inside the relmath-rs repository.

It provides exact finite relations with deterministic BTreeSet-backed iteration order.

Current Surface

The current public API covers:

• annotated::Semiring, annotated::BooleanSemiring, and annotated::AnnotatedRelation<F, A> for additive annotation foundations
• temporal::Interval<T> and temporal::IntervalError<T> for deterministic half-open interval foundations
• temporal::ValidTimeSupport<T> and temporal::ValidTimeRelation<F, T> for deterministic valid-time fact support over exact relations
• UnaryRelation<T> for finite unary relations (sets)
• BinaryRelation<A, B> for finite binary relations
• GroupedRelation<T> for deterministic exact grouped n-ary output
• NaryRelation<T> for deterministic schema-aware exact n-ary relations
• provenance::ProvenanceRelation<F, P> and provenance::ProvenanceSet<P> for deterministic fact-level provenance tokens
• schema validation with explicit n-ary relation errors
• named-column inspection with zero-based column_index
• std-only named-row onboarding and export with BTreeMap
• union, intersection, and difference
• domain, range, converse, and composition
• domain/range restriction plus image/preimage with unary relations
• identity on a carrier
• transitive and reflexive-transitive closure on homogeneous relations
• relation property checks for reflexivity, irreflexivity, symmetry, antisymmetry, transitivity, equivalence, and partial order
• n-ary schema inspection, row insertion, deterministic iteration, selection, projection, rename, natural join, and schema-compatible set algebra

Composition uses relational order:

• r.compose(&s) means r ; s
• the result contains (a, c) when some b satisfies (a, b) in r and (b, c) in s

Current Limits

This crate currently implements the exact G1 core plus the first narrow G2 foundation, the first additive G3 provenance step, the first additive G4 annotated relation step, and the first G5 valid-time foundation and temporal operation step:

• natural join plus exact keyed grouping with row counts have landed so far; broader join families, richer aggregation, and division are still later work
• provenance currently tracks exact base-fact tokens only; base-fact why queries have landed, but derived tuple explanations, why_not queries, and derivation DAGs are still later work
• absent facts return None from why and provenance_of; the current API does not use an empty witness as an "absent explanation" sentinel
• the first rule layer is documented as a future positive finite least-fixed-point surface over named exact relations, but no public rules API has landed yet
• deterministic annotated fact storage and exact support materialization have landed in G4, but annotated relation algebra remains later work
• the first G5 valid-time relation foundation plus snapshot_at and relation-level restrict_to have landed, but temporal joins and temporal composition are still later work
• no typed row derives or schema macros yet
• no broad weighted, fuzzy, or probabilistic relation families yet
• no solver-backed or symbolic evaluation

The repository ships focused examples under examples/:

• family for ancestry and reachability
• access_control for role-permission propagation
• workflow for state reachability
• curriculum for schema-aware n-ary filtering and projection
• provenance for deterministic fact-token evidence tracking
• annotated for deterministic annotated facts with exact support queries
• semiring for the first additive annotation-domain foundation
• intervals for deterministic half-open temporal interval reasoning
• valid_time for deterministic valid-time fact support, snapshots, and restriction workflows

N-ary Row Algebra Notes

• select keeps the existing schema and preserves deterministic order among surviving rows
• project follows the requested column order exactly
• project currently rejects empty projections and duplicate projected columns
• rename is a no-op when the source and target names are the same
• union, intersection, and difference require exact schema equality, including column order

N-ary Interchange Notes

• the current G2 interchange boundary is std-only and dependency-free
• from_named_rows loads BTreeMap records into an explicit schema
• to_named_rows exports name-addressable BTreeMap records in deterministic row order
• missing and unexpected columns are rejected explicitly
• serde, JSON, and CSV / TSV onboarding remain later feature-gated work

N-ary Join Notes

• natural_join matches rows when every shared column has equal values
• when two schemas are disjoint, natural_join behaves as a cartesian product
• the output schema keeps the entire left schema, then appends right-only columns in their original order
• output row order stays deterministic because rows are materialized into a BTreeSet
• if no rows match, the result is empty but still carries the joined schema

N-ary Grouping Notes

• group_by uses explicit key columns in the requested order
• group(key) returns the member relation for one exact grouping key
• empty grouping keys are currently rejected by the exact core
• each member group keeps the original relation schema in this first slice
• group iteration order is deterministic by key
• counts is the first exact aggregate and returns the number of stored rows in each group after relation deduplication

G3 Provenance Notes

• the first G3 provenance slice is additive and lives under relmath::provenance
• ProvenanceRelation<F, P> records which exact facts are present and which deterministic token set is attached to each fact
• ProvenanceSet<P> is the user-visible witness type returned by explanation queries for present stored facts
• repeated insertion of the same fact with a new token combines provenance by exact set union
• why(fact) is the preferred explanation query and returns the deterministic witness for a stored fact and None when the fact is absent
• provenance_of(fact) is the current alias for retrieving that same exact witness
• support(), to_unary_relation(), to_binary_relation(), and to_nary_relation() forget provenance tokens and materialize exact relation support only
• witnesses in this first slice are exact token sets for stored facts
• derived tuple provenance, why_not, and rule-driven explanations remain later work, although the first rule-planning ADR now fixes the intended least-fixed-point direction for a later implementation

G3 Example

use relmath::provenance::ProvenanceRelation;

let evidence = ProvenanceRelation::from_facts([
    (("BRCA1", "BreastCancer"), "curated_panel"),
    (("BRCA1", "BreastCancer"), "paper_12"),
    (("TP53", "BreastCancer"), "paper_77"),
]);

let why = evidence
    .why(&("BRCA1", "BreastCancer"))
    .expect("expected explanation");

assert_eq!(why.to_vec(), vec!["curated_panel", "paper_12"]);
assert_eq!(
    evidence
        .provenance_of(&("BRCA1", "BreastCancer"))
        .expect("expected explanation")
        .to_vec(),
    vec!["curated_panel", "paper_12"]
);
assert!(evidence.why(&("BRCA1", "Olaparib")).is_none());
assert_eq!(
    evidence.support().to_vec(),
    vec![("BRCA1", "BreastCancer"), ("TP53", "BreastCancer")]
);

G3 Rule Planning Notes

• the first rule and fixed-point slice is documented in ADR 0007
• the planned first rule shape is positive finite rules over named exact relations with least-fixed-point semantics
• no public rules module or executable rule engine has landed in this crate yet

G4 Annotated Notes

• the first G4 annotated slice is additive and lives under relmath::annotated
• Semiring defines zero as absence, one as multiplicative identity, add as union-like combination, and mul as composition-like chaining
• BooleanSemiring is the first built-in annotation family and models the exact boolean semantics already used by the published relation core
• AnnotatedRelation<F, A> stores annotated facts in deterministic fact order and combines repeated facts by Semiring::add
• only non-zero annotations are stored, so zero means absence from exact support
• contains_fact(fact) and annotation_of(fact) therefore agree on support: absent or zero-annotated facts return false and None
• unlike provenance::why, annotation_of(fact) returns the stored annotation value itself rather than a witness set
• support(), to_unary_relation(), to_binary_relation(), and to_nary_relation() forget annotations and materialize only exact support
• annotated relation algebra, valid-time fact storage, and broader weighted, fuzzy, or probabilistic families remain later work

G5 Valid-Time Notes

• in the current G5 terminology, an interval is one half-open window [start, end), support is the canonical interval set attached to one stored fact, and exact support is the set of facts that remains after forgetting time
• relmath::temporal::Interval<T> remains the executable interval foundation for deterministic half-open [start, end) semantics
• relmath::temporal::ValidTimeSupport<T> is the canonical interval support attached to one fact
• ValidTimeSupport::overlaps(interval) reports non-empty temporal overlap, while ValidTimeSupport::restrict_to(interval) returns canonical restricted support and becomes empty when overlap is absent
• relmath::temporal::ValidTimeRelation<F, T> stores facts in deterministic fact order and coalesces overlapping or directly adjacent support intervals for the same fact
• valid_time_of(fact) returns the canonical valid-time support for one fact and None when the fact is absent
• is_active_at(fact, point) checks whether one fact is active at one time point using half-open boundary semantics
• snapshot_at(point) returns the exact unary snapshot of facts active at one time point
• restrict_to(interval) keeps only facts whose support overlaps the interval and restricts each remaining fact to canonical overlap support
• support(), to_unary_relation(), to_binary_relation(), and to_nary_relation() forget time and materialize exact support only
• the relation does not store empty temporal support as a sentinel value, so absent facts return None rather than an empty support object
• transaction time, bitemporal correction histories, temporal join, and temporal composition remain later G5 or later-milestone work

G5 Example

use relmath::temporal::{Interval, ValidTimeRelation};

let assignments = ValidTimeRelation::from_facts([
    (("alice", "review"), Interval::new(1, 3).expect("expected valid interval")),
    (("alice", "review"), Interval::new(3, 5).expect("expected valid interval")),
    (("bob", "approve"), Interval::new(2, 4).expect("expected valid interval")),
]);
let audit_window = Interval::new(2, 4).expect("expected valid interval");

assert_eq!(
    assignments
        .valid_time_of(&("alice", "review"))
        .expect("expected support")
        .to_vec(),
    vec![Interval::new(1, 5).expect("expected valid interval")]
);
assert!(assignments.is_active_at(&("alice", "review"), &4));
assert!(!assignments.is_active_at(&("alice", "review"), &5));
assert_eq!(
    assignments.snapshot_at(&3).to_vec(),
    vec![("alice", "review"), ("bob", "approve")]
);
assert_eq!(
    assignments.to_binary_relation().to_vec(),
    vec![("alice", "review"), ("bob", "approve")]
);
assert_eq!(
    assignments
        .restrict_to(&audit_window)
        .valid_time_of(&("alice", "review"))
        .expect("expected support")
        .to_vec(),
    vec![Interval::new(2, 4).expect("expected valid interval")]
);

G4 Example

use relmath::{
    BinaryRelation,
    annotated::{AnnotatedRelation, Semiring},
};

#[derive(Clone, Debug, PartialEq, Eq)]
struct Count(u8);

impl Semiring for Count {
    fn zero() -> Self {
        Self(0)
    }

    fn one() -> Self {
        Self(1)
    }

    fn add(&self, rhs: &Self) -> Self {
        Self(self.0.saturating_add(rhs.0))
    }

    fn mul(&self, rhs: &Self) -> Self {
        Self(self.0.saturating_mul(rhs.0))
    }
}

let tasks = AnnotatedRelation::from_facts([
    (("Alice", "Review"), Count(1)),
    (("Alice", "Review"), Count(2)),
    (("Bob", "Approve"), Count(1)),
    (("Cara", "Archive"), Count(0)),
]);

assert_eq!(tasks.annotation_of(&("Alice", "Review")), Some(&Count(3)));
assert_eq!(tasks.annotation_of(&("Cara", "Archive")), None);
assert!(!tasks.contains_fact(&("Cara", "Archive")));

let support: BinaryRelation<_, _> = tasks.to_binary_relation();
assert_eq!(
    support.to_vec(),
    vec![("Alice", "Review"), ("Bob", "Approve")]
);

Status

This crate now contains the published G1 unary/binary core plus the first schema-aware n-ary building block for G2, including stricter schema validation for blank column names, a std-only named-row interchange boundary, an exact natural join primitive, exact keyed grouping with row counts, the first additive G3 provenance foundation and explanation query surface for exact fact tokens, the first additive G4 annotated relation foundation, and the first G5 valid-time relation and temporal operation foundation.