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