Codd's relational model — the query algebra over typed, intensional Sets and Relations (σ select, π-elided, ⋈ join, ∪, ∖, ∩). More...

#include <concepts>
#include <functional>
#include <tuple>
#include <type_traits>
#include <utility>
import dedekind.relational:dyadic;
import dedekind.sets;
import dedekind.category;

Include dependency graph for tables.cppm:

Classes
struct	dedekind::relational::CanonicalPairPredicate

Typedefs
using	dedekind::relational::CanonicalIntRelation = Relation<int, int, Boole, CanonicalPairPredicate>
using	dedekind::relational::CanonicalIntRelationDomain = typename CanonicalIntRelation::Domain
using	dedekind::relational::CanonicalNaturalJoin
using	dedekind::relational::CanonicalNaturalJoinDomain = typename CanonicalNaturalJoin::Domain

Functions
template<dedekind::sets::IsSetObject S, typename Pred> requires std::invocable<const std::decay_t<Pred>&, const typename S::Domain&> && requires(std::invoke_result_t<const std::decay_t<Pred>&, const typename S::Domain&> v) { { dedekind::category::lift_logic<typename S::logic_species>(v) } -> std::same_as<typename S::logic_species::Ω>; }
constexpr auto	dedekind::relational::select (const S &s, Pred pred)
	Selection (σ): filter elements of a set by an additional predicate.
template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B> requires std::same_as<typename A::Domain, typename B::Domain>
constexpr auto	dedekind::relational::set_union (const A &a, const B &b)
	Union (∪): elements belonging to at least one of two same-typed sets.
template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B> requires std::same_as<typename A::Domain, typename B::Domain>
constexpr auto	dedekind::relational::set_difference (const A &a, const B &b)
	Difference (∖): elements of A that are absent from B.
template<typename A, typename B> requires dedekind::category::IsLSet<std::remove_cvref_t<A>> && dedekind::category::IsLSet<std::remove_cvref_t<B>> && requires(const A& a, const B& b) { a & ~b; }
constexpr auto	dedekind::relational::operator- (const A &a, const B &b)
	`operator-` : the set-difference operator, \(A \setminus B = A \cap \sim\! B\).
template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B> requires std::same_as<typename A::Domain, typename B::Domain>
constexpr auto	dedekind::relational::set_intersection (const A &a, const B &b)
	Intersection (∩): elements common to both sets.
template<dedekind::sets::IsSetObject R1, dedekind::sets::IsSetObject R2> requires IsPairLike<typename R1::Domain> && IsPairLike<typename R2::Domain> && std::same_as<typename R1::Domain::second_type, typename R2::Domain::first_type> && std::same_as<typename R1::logic_species, typename R2::logic_species>
constexpr auto	dedekind::relational::natural_join (const R1 &r1, const R2 &r2)
	Natural join (⋈): compose two binary relations on a shared middle type.
constexpr auto	dedekind::relational::σ (auto &&... a)
constexpr auto	dedekind::relational::join (auto &&... a)

Detailed Description

Codd's relational model — the query algebra over typed, intensional Sets and Relations (σ select, π-elided, ⋈ join, ∪, ∖, ∩).

@partition :tables

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

relational__Description

This partition provides the five primitive operators of Codd's relational algebra, lifted to the typed, intensional Set model of dedekind.sets:

select (σ) – filter elements of a set by an additional predicate.
set_union (∪) – elements belonging to either of two same-typed sets.
set_difference (∖) – elements of A that are absent from B.
set_intersection (∩) – elements common to both sets (derived operator).
natural_join (⋈) – composition of two binary relations on a shared type.

Cross-product (×) is already provided by :expressions as cartesian_product. Projection (π) requires existential quantification over an infinite domain and is therefore intentionally omitted from this MVP. Rename (ρ) reduces to a type alias in C++ and requires no runtime support.

relational__Canonical_Examples

// Two relations: parent ⊆ Person × Person, ancestor ⊆ Person × Person
const auto grandparent = natural_join(parent, parent);       // ⋈
const auto either = set_union(mother, father);               // ∪
const auto adults = select(people, [](const Person& p) {     // σ
  return p.age >= 18;
});
const auto adults_only = set_difference(people, minors);     // ∖

relational__References

Codd, E.F. (1970) "A Relational Model of Data for Large Shared Data Banks", Comm. ACM 13(6). https://doi.org/10.1145/362384.362685
Wikipedia: Relational algebra https://en.wikipedia.org/wiki/Relational_algebra

@quote "Matter does not engage their attention, they are interested in form alone." – Henri Poincare, Science and Hypothesis (1901)

Note: "All laws are deduced from experiment; but to enunciate them, a special language is needful." – Henri Poincare, The Value of Science (1905)

Typedef Documentation

◆ CanonicalNaturalJoin

using dedekind::relational::CanonicalNaturalJoin

Initial value:

 
    decltype(natural_join(CanonicalIntRelation{CanonicalPairPredicate{}},
                          CanonicalIntRelation{CanonicalPairPredicate{}}))

Function Documentation

◆ natural_join()

template<dedekind::sets::IsSetObject R1, dedekind::sets::IsSetObject R2>
requires IsPairLike<typename R1::Domain> && IsPairLike<typename R2::Domain> && std::same_as<typename R1::Domain::second_type, typename R2::Domain::first_type> && std::same_as<typename R1::logic_species, typename R2::logic_species>

auto dedekind::relational::natural_join	(	const R1 &	r1,
		const R2 &	r2 )

constexprexport

Natural join (⋈): compose two binary relations on a shared middle type.

Given R1 ⊆ T1 × T2 and R2 ⊆ T2 × T3, R1 ⋈ R2 = {(t1, t2, t3) | (t1, t2) ∈ R1 ∧ (t2, t3) ∈ R2}

The result is a comprehension over 𝔸<std::tuple<T1,T2,T3>, L>. Membership of a triple (t1,t2,t3) is the conjunction of membership of (t1,t2) in R1 and (t2,t3) in R2.

Template Parameters

T1	Type of the first component (left relation domain).
T2	Shared join type (right component of R1, left component of R2).
T3	Type of the third component (right relation codomain).
L	Logic species shared by both relations.

◆ operator-()

template<typename A, typename B>
requires dedekind::category::IsLSet<std::remove_cvref_t<A>> && dedekind::category::IsLSet<std::remove_cvref_t<B>> && requires(const A& a, const B& b) { a & ~b; }

auto dedekind::relational::operator-	(	const A &	a,
		const B &	b )

constexprexport

operator- : the set-difference operator, \(A \setminus B = A \cap \sim\! B\).

The operator spelling of set_difference, completing the bitwise set-operator surface (& = \(\cap\), | = \(\cup\), ~ = complement, ^ = \(\triangle\), - = \(\setminus\)). Defined via ~ (the bitwise complement, aligned with the bitwise set semantics) rather than the logical !. Gated on IsSet for both operands (so it never shadows arithmetic operator- on numeric carriers) and on a & ~b being well formed, so it also accepts a 𝔸 minuend (U - B collapses through the universal-set identity to ~B). There is no C++ set-minus glyph; this is the idiomatic stand-in for the blackboard \(\setminus\).

◆ select()

template<dedekind::sets::IsSetObject S, typename Pred>
requires std::invocable<const std::decay_t<Pred>&, const typename S::Domain&> && requires(std::invoke_result_t<const std::decay_t<Pred>&, const typename S::Domain&> v) { { dedekind::category::lift_logic<typename S::logic_species>(v) } -> std::same_as<typename S::logic_species::Ω>; }

auto dedekind::relational::select	(	const S &	s,
		Pred	pred )

constexprexport

Selection (σ): filter elements of a set by an additional predicate.

σ_f(S) = {x ∈ S | f(x)}

Constructs a comprehension whose membership is the conjunction of membership in s and satisfaction of pred. Predicate outputs are normalized through dedekind::category::lift_logic<L>, so both native logical witnesses (L::Ω) and bool-valued predicates are accepted.

Template Parameters

T	Element type.
L	Logic species.
P	Existing predicate type of `s`.
Pred	Additional filter predicate type.

◆ set_difference()

template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B>
requires std::same_as<typename A::Domain, typename B::Domain>

auto dedekind::relational::set_difference	(	const A &	a,
		const B &	b )

constexprexport

Difference (∖): elements of A that are absent from B.

A ∖ B = {x | x ∈ A ∧ x ∉ B}

Expressed as the conjunction of membership in a and non-membership in b.

◆ set_intersection()

template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B>
requires std::same_as<typename A::Domain, typename B::Domain>

auto dedekind::relational::set_intersection	(	const A &	a,
		const B &	b )

constexprexport

Intersection (∩): elements common to both sets.

A ∩ B = {x | x ∈ A ∧ x ∈ B}

Named alias for the operator& on Set. Intersection is a derived operator in minimal relational algebra (A ∩ B = A ∖ (A ∖ B)), but is provided here for ergonomics.

◆ set_union()

template<dedekind::sets::IsSetObject A, dedekind::sets::IsSetObject B>
requires std::same_as<typename A::Domain, typename B::Domain>

auto dedekind::relational::set_union	(	const A &	a,
		const B &	b )

constexprexport

Union (∪): elements belonging to at least one of two same-typed sets.

A ∪ B = {x | x ∈ A ∨ x ∈ B}

Named alias for the operator| on Set, provided for relational-algebra readability.

Classes

Typedefs

Functions

Detailed Description

relational__Description

relational__Canonical_Examples

relational__References

Typedef Documentation

◆ CanonicalNaturalJoin

Function Documentation

◆ natural_join()

◆ operator-()

◆ select()

◆ set_difference()

◆ set_intersection()

◆ set_union()