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