dedekind.relational — a first-class module for relations, popped out of :sets: Codd's relational model, Tarski's calculus of relations, and graphs (of arrows, binary relations). More...

import dedekind.relational:graph;

Include dependency graph for relational.cppm:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Detailed Description

dedekind.relational — a first-class module for relations, popped out of :sets: Codd's relational model, Tarski's calculus of relations, and graphs (of arrows, binary relations).

Copyright: 2026 The Dedekind Authors Licensed under the Apache License, Version 2.0.

relational__Why_A_Module

Relations are first-class in Trsk, so they deserve their own module rather than living as a scattering of :sets partitions (relational, graph) plus combinators buried in order/halfspace.cppm. This module is the Reification of RAlg (GH #792), the relational counterpart to the :sets reification of Set.

relational__Layering

category → sets → relational → order. The module sits above sets (it builds on the Set / Relation DSL) and below order: order/halfspace's ordered relation-algebra (converse, the relative product, diagonal) moves DOWN into relational__Partitions so the ordered predicates can consume it, not the other way around. The order-free relation combinators were consumed from below order (by sequences::path, linear_algebra::transfer), which is exactly why the whole surface belongs on this low rung and not above order.

relational__Partitions

:tables — Codd's relational model (1970): the query algebra σ select, ⋈ natural_join, ∪ set_union, ∖ set_difference, ∩; relations are n-ary tables of tuples.
:dyadic — Tarski's calculus of relations (1941): converse \(R^{\circ}\), relative product \(R;S\) (over a Boolean middle), diagonal \(\Delta\), union \(\cup\) (the set-grammar |) / meet \(\&\); relations are dyadic (binary), one carrier under a Boolean involutive monoid. The BASE the other two build on. (The reflexive-transitive closure \(R^{*}\) is not yet a provided operator; FIXME(#786).)
:graph — graphs of arrows as binary relations: \(\Gamma_f\), is_graph_of. A graph is a relation, so it tags along here.

relational__Namespace

All relational symbols — including the Relation / SetFunction aliases and the IsRelation concept — live in the dedekind::relational namespace, the module's OWN namespace (no dedekind::sets leftover). Only the underlying carriers stay in dedekind::sets: Set (the Set<pair> a relation is) and 𝔸 (the declared factor universals), brought in by a using-declaration inside each partition.

Migration impact of the namespace move (do NOT under-state it): ADL searches the namespaces of a call's ARGUMENT types, so every named API that takes a Set / Relation argument — converse, select, set_difference, natural_join, preimage, reflexive, symmetric — was ADL-reachable from dedekind::sets and now is not; those bare calls need qualification or a using. The infix operators (>> / & / the set-difference -) are the same story (union is the set-grammar |, a Set member, so it needs no using). The ONLY symbols that never ADL-reached sets are graph (called on an arrow, whose type is not in sets) and the relation/function concepts (used as type traits, not calls). In practice consumers add using namespace dedekind::relational once — the explicit price for a module whose namespace is honest about where its symbols live.

Roadmap (work in progress)

#319 undergraduate graph theory: graphs as relations (IsDirectedGraph in dedekind.category:cartesian) and path problems as semiring closures (star in linear_algebra:transfer); still open are degree and incidence, multigraphs, walks and cycles, traversals, components, trees and spanning trees, planarity, colouring, matchings and flows.
#330 undergraduate algorithms and data structures: the algorithms over them: traversals, topological sort, greedy and divide-and-conquer surfaces.