# 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
- `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
- `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, the first additive G4
annotated relation step, and the first G5 valid-time foundation and temporal
operation 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 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
- 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
- `intervals` for deterministic half-open temporal interval reasoning
- `valid_time` for deterministic valid-time fact support, snapshots, and
restriction workflows
## 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
## 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 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, the first additive G4 annotated relation foundation, and the first G5
valid-time relation and temporal operation foundation.