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:

• traits::FiniteRelation and traits::RelationView for shared tuple-count inspection and deterministic read-only iteration across the exact unary, binary, and n-ary relation types
• traits::ExactSupport, traits::ToExactUnaryRelation, traits::ToExactBinaryRelation, and traits::ToExactNaryRelation for shared exact-support materialization across the released add-on surfaces
• 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
• FiniteCarrier<T> for deterministic explicit finite carriers distinct from support inferred from stored tuples
• 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 released G2 schema-aware n-ary surface, the released G3 provenance surface, the released G4 annotated relation surface, the released G5 valid-time relation surface, the released G6 shared-core convergence layer, and the first executable G7 carrier slices:

• 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
• RelationView plus ExactSupport and the ToExact*Relation materialization traits have landed in G6, while broader common core types and typed-row or macro ergonomics remain planning-only
• FiniteCarrier<T> has landed as the first explicit carrier boundary, and additive carrier-aware exact operations now integrate it directly without changing the published UnaryRelation<T>-based carrier arguments
• no complement, total-relation, or public Universe<T> API has landed yet; ADR 0015 keeps that broader carrier-domain work planning-only for now
• no typed row derives or schema macros yet; G6 currently fixes only the adapter-first planning boundary for that later work
• 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
• carrier for explicit finite carriers distinct from relation-induced support
• 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
• relation_view for the first shared read-only exact-relation boundary
• capability_boundaries for the first shared exact-support capability layer

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

G6 Relation View Notes

• RelationView is the first additive G6 shared-core boundary
• the first landed scope covers only len, is_empty, and deterministic tuple iteration through tuples()
• RelationView currently applies to UnaryRelation<T>, BinaryRelation<A, B>, and NaryRelation<T>
• this first shared view does not normalize tuple shape across arities and does not replace concrete APIs such as membership checks, schema access, domain/range inspection, support materialization, provenance, annotations, or temporal support
• backend abstraction, capability-specific shared traits, common core types, and typed-row ergonomics remain later G6 work

G6 Capability Boundary Notes

• ExactSupport::exact_support is the shared relation-level boundary for forgetting provenance witnesses, annotation values, or valid-time interval support and keeping only exact facts
• ToExactUnaryRelation, ToExactBinaryRelation, and ToExactNaryRelation make the released exact support materialization paths explicit for generic code without changing the existing concrete methods
• provenance still uses why(fact) and provenance_of(fact) for witnesses
• annotated relations still use annotation_of(fact) for stored annotation values
• valid-time relations still use valid_time_of(fact) for fact-level interval support
• ValidTimeSupport<T> is fact-level temporal support for one fact, not the exact support of a whole relation
• exact n-ary materialization still requires an explicit schema and still reuses current NaryRelation validation rules

G6 Common Core-Type Notes

• G6-C is planning-only: no public Universe<T>, RelError, or EvalConfig has landed yet
• the first common core-type candidate is an explicit finite carrier boundary because current exact APIs already use carrier-relative semantics
• any later carrier type must stay explicit, deterministic, and semantically distinct from support inferred from stored tuples
• module-local errors such as NaryRelationError and IntervalError remain the current public error surface
• a shared RelError waits for genuinely shared fallible behavior across shipped modules
• a shared EvalConfig waits for real optimizer, backend, parallel, timeout, or resource-budget choices rather than placeholder configuration knobs

G7 Carrier Notes

• FiniteCarrier<T> is the first executable G7 carrier boundary
• explicit carriers stay semantically distinct from support inferred from stored tuples such as BinaryRelation::carrier()
• BinaryRelation::carrier() still returns an inferred UnaryRelation<T>, not a FiniteCarrier<T>
• deterministic construction, membership checks, len, is_empty, and iteration have landed for explicit finite carriers
• empty carriers stay empty, singleton carriers stay singleton, and disconnected values remain visible even when no stored pair mentions them
• BinaryRelation::identity_on, reflexive_transitive_closure_on, is_reflexive_on, is_irreflexive_on, is_equivalence_on, and is_partial_order_on are the first direct carrier-aware exact operations
• the published UnaryRelation<T> carrier arguments still coexist unchanged through identity, reflexive_transitive_closure, is_reflexive, is_irreflexive, is_equivalence, and is_partial_order
• to_unary_relation() remains the explicit bridge into older or generic unary-carrier call sites
• ADR 0015 now fixes the broader planning direction: complement and total relation still require explicit finite carriers, a public Universe<T> is still deferred, and the first later executable carrier-domain algebra should likely start with binary exact relations

G7 Example

use relmath::{BinaryRelation, FiniteCarrier};

let step = BinaryRelation::from_pairs([("Draft", "Review")]);
let states = FiniteCarrier::from_values(["Draft", "Review", "Archived"]);
let inferred = step.carrier();

assert_eq!(inferred.to_vec(), vec!["Draft", "Review"]);
assert_eq!(states.to_vec(), vec!["Archived", "Draft", "Review"]);

let inferred_identity = BinaryRelation::identity(&inferred);
let explicit_identity = BinaryRelation::identity_on(&states);
let reachable = step.reflexive_transitive_closure_on(&states);

assert_eq!(inferred_identity.to_vec(), vec![("Draft", "Draft"), ("Review", "Review")]);
assert!(explicit_identity.contains(&"Archived", &"Archived"));
assert!(reachable.contains(&"Archived", &"Archived"));
assert!(reachable.is_reflexive_on(&states));
assert_eq!(
    reachable.to_vec(),
    step.reflexive_transitive_closure(&states.to_unary_relation())
        .to_vec()
);

G6 Typed-Row And Macro Notes

• G6-D is planning-only: no public RelRow, #[derive(RelRow)], set!, nrel!, or related macro surface has landed yet
• the released exact schema-aware n-ary core remains NaryRelation<T> with explicit schema order and deterministic row order
• future typed-row work should start with explicit adapters or conversion traits over the current NaryRelation<T> semantics rather than replacing the exact core with a second row model
• any later typed-row conversion must be lossless or explicitly fallible and must not silently reorder, drop, or invent columns
• the smallest future executable adapter work should stay aligned with the current homogeneous cell-type model of NaryRelation<T>
• broader heterogeneous typed-record support and proc-macro derives remain later work after the conversion boundary is stable
• any later literal macros should be thin constructor sugar over already- shipped semantics, and their token grammar and schema expansion rules should be treated as versioned public API

G6 Example

use relmath::{
    FiniteRelation, RelationView, ToExactBinaryRelation,
    annotated::{AnnotatedRelation, BooleanSemiring},
};

let permissions = AnnotatedRelation::from_facts([
    (("alice", "read"), BooleanSemiring::TRUE),
    (("bob", "approve"), BooleanSemiring::TRUE),
    (("carol", "audit"), BooleanSemiring::FALSE),
]);

let exact = permissions.to_binary_relation();

assert_eq!(exact.len(), 2);
assert_eq!(
    exact.tuples().copied().collect::<Vec<_>>(),
    vec![("alice", "read"), ("bob", "approve")]
);

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 released G2 schema-aware n-ary surface, including stricter schema validation for blank column names, a std-only named-row interchange boundary, an exact natural join primitive, and exact keyed grouping with row counts; the released G3 provenance foundation and explanation query surface for exact fact tokens; the released G4 annotated relation foundation; the released G5 valid-time relation and temporal operation foundation; and the released G6 shared relation-view boundary for exact unary, binary, and n-ary relations together with the explicit exact-support capability boundary for the shipped provenance, annotated, and valid-time surfaces. The first executable G7 slice now adds FiniteCarrier<T> together with additive carrier-aware exact operations for identity, reflexive-transitive closure, and carrier-relative property checks, while complement, total relation, and a broader Universe<T> remain planning-only through ADR 0015.