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:

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

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

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 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.

Re-exports§

pub use crate::core::BinaryRelation;
pub use crate::core::GroupedRelation;
pub use crate::core::NaryRelation;
pub use crate::core::NaryRelationError;
pub use crate::core::UnaryRelation;
pub use crate::traits::FiniteRelation;

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.

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

§G5 Example

§G4 Example

§Status

Re-exports§

Modules§

Crate relmath