# 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
```rust
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.