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
• 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, and the first additive G4 annotated relation 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 and temporal operators have not
• no temporal relation API has landed yet; the current G4 plan is valid-time first with deterministic half-open intervals and exact-support erasure of time
• 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

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, temporal intervals, and broader weighted, fuzzy, or probabilistic families remain later work

G4 Temporal Planning Notes

• no public temporal API has landed in the crate yet
• the current temporal surface is docs-only planning rather than executable code
• the first executable temporal layer is planned as valid-time first, not bitemporal first
• the planned first interval model is deterministic half-open intervals [start, end) over totally ordered endpoint domains
• exact support for later temporal relations should forget time and keep only facts whose interval annotation is not empty
• transaction time, bitemporal correction histories, temporal join, and temporal composition remain later G4 or later-milestone work

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, and the first additive G4 annotated relation foundation.