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:

• 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 and the first additive G3 provenance 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
• no typed row derives or schema macros yet
• no weighted or temporal relations
• 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

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

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, and the first additive G3 provenance foundation and explanation query surface for exact fact tokens.