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:

• 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
• 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:

• natural join plus exact keyed grouping with row counts have landed so far; broader join families, richer aggregation, and division are still later work
• no typed row derives or schema macros yet
• no weighted or temporal relations
• 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

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

Example

use std::collections::BTreeMap;

use relmath::NaryRelation;

let completed = NaryRelation::from_named_rows(
    ["student", "course"],
    [
        BTreeMap::from([("course", "Math"), ("student", "Alice")]),
        BTreeMap::from([("course", "Physics"), ("student", "Alice")]),
        BTreeMap::from([("course", "Math"), ("student", "Bob")]),
    ],
)?;
let rooms = NaryRelation::from_named_rows(
    ["course", "room"],
    [
        BTreeMap::from([("course", "Math"), ("room", "R101")]),
        BTreeMap::from([("course", "Physics"), ("room", "R201")]),
    ],
)?;

let scheduled = completed.natural_join(&rooms);
let by_room = scheduled.group_by(["room"])?;

assert_eq!(
    scheduled.schema(),
    &["student".to_string(), "course".to_string(), "room".to_string()]
);
assert_eq!(by_room.counts(), vec![(vec!["R101"], 2), (vec!["R201"], 1)]);
assert_eq!(
    scheduled.to_rows(),
    vec![
        vec!["Alice", "Math", "R101"],
        vec!["Alice", "Physics", "R201"],
        vec!["Bob", "Math", "R101"],
    ]
);
# Ok::<(), relmath::NaryRelationError>(())

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, and exact keyed grouping with row counts.