Crate relmath

Source

Expand description

§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

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

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

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

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

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.

Re-exports§

pub use crate::core::BinaryRelation;
pub use crate::core::FiniteCarrier;
pub use crate::core::GroupedRelation;
pub use crate::core::NaryRelation;
pub use crate::core::NaryRelationError;
pub use crate::core::UnaryRelation;
pub use crate::traits::ExactSupport;
pub use crate::traits::FiniteRelation;
pub use crate::traits::RelationView;
pub use crate::traits::ToExactBinaryRelation;
pub use crate::traits::ToExactNaryRelation;
pub use crate::traits::ToExactUnaryRelation;

Modules§

annotated: Additive annotation domains and deterministic annotated relation support. Additive annotation-domain and annotated-relation foundations.
core: Core unary, binary, and n-ary relation types. Core relation types and algorithms.
prelude: Prelude with the most commonly used imports. Common imports for relation-first programming.
provenance: Deterministic provenance support for exact facts. Deterministic exact provenance support.
temporal: Deterministic temporal interval and valid-time foundations. Deterministic temporal interval and valid-time foundations.
traits: Traits shared by relation types. Shared traits for relation types and explicit capability boundaries.

Crate relmath

Crate relmath Copy item path

§relmath

§Current Surface

§Current Limits

§N-ary Row Algebra Notes

§N-ary Interchange Notes

§N-ary Join Notes

§N-ary Grouping Notes

§G3 Provenance Notes

§G3 Example

§G3 Rule Planning Notes

§G4 Annotated Notes

§G5 Valid-Time Notes

§G6 Relation View Notes

§G6 Capability Boundary Notes

§G6 Common Core-Type Notes

§G7 Carrier Notes

§G7 Example

§G6 Typed-Row And Macro Notes

§G6 Example

§G5 Example

§G4 Example

§Status

Re-exports§

Modules§

Crate relmath