#+TITLE: Infinite Relations Design
#+AUTHOR: Nekoma Team
#+DATE: 2025-01-22
* Overview
This document specifies the design for infinite relations in Domino, enabling
countably infinite (ℵ₀) and uncountably infinite (continuum) relations alongside
finite relations.
** Core Principle
*Everything is a relation.* Types are relations. Functions are relations.
Numbers are relations. This unifies the type system with the data model.
* Cardinality System
** Cardinality Types
#+BEGIN_SRC erlang
-type cardinality() :: {finite, non_neg_integer()} % Finite set with N elements
| aleph_zero % Countably infinite (ℵ₀)
| continuum. % Uncountably infinite (2^ℵ₀)
#+END_SRC
** Properties
- Finite relations have explicit tuple count: ={finite, 1000}=
- Countably infinite relations: =aleph_zero=
- Uncountably infinite relations: =continuum=
* Extended Data Model
** Modified Relation Record
#+BEGIN_SRC erlang
-record(relation, {
hash, % Content hash (for finite) or generator hash (for infinite)
name, % Relation name (atom)
tree, % Merkle tree (finite only), undefined for infinite
schema, % Schema definition
cardinality, % {finite, N} | aleph_zero | continuum
generator, % Generator function (infinite only), undefined for finite
is_function % Boolean: true if relation represents a function
}).
#+END_SRC
** Generator Specification
Generators are functions that produce tuples on-demand based on constraints.
#+BEGIN_SRC erlang
-type generator_spec() ::
{primitive, atom()} % Built-in: naturals, integers, rationals
| {function_relation, atom(), arity()} % Built-in function: plus/3, times/3
| {custom, fun((constraints()) -> tuple())} % User-defined generator
| {derived, relational_operation()}. % Derived from other relations
-type constraints() :: #{
attribute_name() => constraint_spec()
}.
-type constraint_spec() ::
{eq, value()} % Equality: age = 30
| {neq, value()} % Inequality: age ≠ 30
| {lt, value()} % Less than: age < 30
| {lte, value()} % Less than or equal
| {gt, value()} % Greater than
| {gte, value()} % Greater than or equal
| {in, [value()]} % Membership: age in [20,30,40]
| {range, value(), value()} % Range: age in [20..30]
| {member_of, relation_name()}. % Type constraint: x ∈ Naturals
#+END_SRC
* Primitive Infinite Relations
** Naturals (ℕ)
#+BEGIN_SRC erlang
Schema: #{value => natural}
Cardinality: aleph_zero
Generator: Enumerates 0, 1, 2, 3, ...
Example tuples:
#{value => 0}
#{value => 1}
#{value => 2}
...
#+END_SRC
** Integers (ℤ)
#+BEGIN_SRC erlang
Schema: #{value => integer}
Cardinality: aleph_zero
Generator: Enumerates 0, 1, -1, 2, -2, 3, -3, ...
Enumeration strategy: Interleave positive and negative
f(0) = 0
f(2n) = n (for n > 0)
f(2n+1) = -n (for n > 0)
#+END_SRC
** Rationals (ℚ)
#+BEGIN_SRC erlang
Schema: #{numerator => integer, denominator => natural}
Cardinality: aleph_zero
Generator: Stern-Brocot tree or Calkin-Wilf sequence
Constraints:
- denominator > 0
- gcd(numerator, denominator) = 1 (reduced form)
Example tuples:
#{numerator => 0, denominator => 1} % 0/1
#{numerator => 1, denominator => 1} % 1/1
#{numerator => 1, denominator => 2} % 1/2
#{numerator => 2, denominator => 1} % 2/1
#{numerator => 1, denominator => 3} % 1/3
...
#+END_SRC
** Reals (ℝ) - Theoretical
#+BEGIN_SRC erlang
Schema: #{value => real}
Cardinality: continuum
Generator: Not fully enumerable (conceptual only)
Note: In practice, we can only represent computable reals or
algebraic reals (still countable but more expressive).
#+END_SRC
* Function Relations
A relation R is a *function* if: ∀a ∃!b : (a,b) ∈ R
That is, for every input, there exists exactly one output.
** Plus (addition)
#+BEGIN_SRC erlang
Name: plus
Schema: #{a => number, b => number, sum => number}
Cardinality: aleph_zero (when a,b ∈ ℤ or ℚ)
Is_function: false (it's a 3-way relation, not (a,b) → sum)
Function view: plus(a, b) = sum where (a, b, sum) ∈ Plus
Generator: For each (a, b) pair, yield #{a => A, b => B, sum => A + B}
Constraints required for iteration:
- At least two of {a, b, sum} must be bounded
Valid queries:
- plus where a ∈ [0..10], b ∈ [0..10] ✓ (finite result: 121 tuples)
- plus where a = 5, b ∈ Naturals ✓ (countable: {5,0,5}, {5,1,6}, ...)
- plus where sum = 10 ✓ (countable: infinitely many a+b=10)
- plus with no constraints ✗ (cannot enumerate)
#+END_SRC
** Times (multiplication)
#+BEGIN_SRC erlang
Name: times
Schema: #{a => number, b => number, product => number}
Cardinality: aleph_zero
Generator: For each (a, b) pair, yield #{a => A, b => B, product => A * B}
#+END_SRC
** Successor
#+BEGIN_SRC erlang
Name: successor
Schema: #{n => integer, succ => integer}
Cardinality: aleph_zero
Is_function: true (n → succ is a function)
Generator: For each n, yield #{n => N, succ => N + 1}
#+END_SRC
* Cardinality Algebra
Rules for computing cardinality of relational operations:
** Union (∪)
| Left | Right | Result | Notes |
|------------+------------+------------+--------------------------|
| {finite,m} | {finite,n} | {finite,≤m+n} | May have duplicates |
| {finite,n} | aleph_zero | aleph_zero | Finite + infinite = infinite |
| aleph_zero | aleph_zero | aleph_zero | ℵ₀ + ℵ₀ = ℵ₀ |
| aleph_zero | continuum | continuum | Continuum dominates |
| continuum | continuum | continuum | 2^ℵ₀ + 2^ℵ₀ = 2^ℵ₀ |
** Cartesian Product (×)
| Left | Right | Result | Notes |
|------------+------------+---------------+-----------------------|
| {finite,m} | {finite,n} | {finite,m·n} | Product of sizes |
| {finite,n} | aleph_zero | aleph_zero | n · ℵ₀ = ℵ₀ |
| aleph_zero | aleph_zero | aleph_zero | ℵ₀ · ℵ₀ = ℵ₀ |
| aleph_zero | continuum | continuum | ℵ₀ · 2^ℵ₀ = 2^ℵ₀ |
| continuum | continuum | continuum | 2^ℵ₀ · 2^ℵ₀ = 2^ℵ₀ |
** Natural Join (⋈)
Cardinality depends on join selectivity:
| Left | Right | Result | Notes |
|------------+------------+------------+------------------------------------|
| {finite,m} | {finite,n} | {finite,k} | k ≤ min(m,n) typically |
| {finite,n} | aleph_zero | varies | Could be finite or aleph_zero |
| aleph_zero | aleph_zero | varies | Depends on join condition |
*Examples:*
#+BEGIN_SRC erlang
%% Finite ⋈ Infinite (finite result)
Employees = {finite, 100} % 100 employees
Naturals = aleph_zero % Infinite numbers
Employees ⋈ Naturals on employee_id = value
⇒ {finite, 100} % At most 100 matches
%% Infinite ⋈ Infinite (infinite result)
Naturals ⋈ Plus on Naturals.value = Plus.a
⇒ aleph_zero % For each natural n, infinite (n,b,n+b) tuples
%% Infinite ⋈ Infinite (finite result with constraints)
(Naturals where value < 10) ⋈ (Naturals where value < 10)
⇒ {finite, 100} % 10 × 10 = 100
#+END_SRC
** Selection (σ)
| Input | Result | Notes |
|------------+------------+------------------------------------|
| {finite,n} | {finite,k} | k ≤ n (filtering reduces size) |
| aleph_zero | varies | Could be finite or aleph_zero |
| continuum | varies | Could be any cardinality |
*Examples:*
#+BEGIN_SRC erlang
σ(Naturals, value < 10) ⇒ {finite, 10} % Bounded selection
σ(Naturals, value > 5) ⇒ aleph_zero % Infinite result
σ(Naturals, value % 2 = 0) ⇒ aleph_zero % Even numbers (infinite)
#+END_SRC
** Projection (π)
| Input | Result | Notes |
|------------+------------+---------------------------------|
| {finite,n} | {finite,k} | k ≤ n (duplicates removed) |
| aleph_zero | aleph_zero | Typically preserves infinity |
| continuum | continuum | Typically preserves cardinality |
* Constraint System
** Mandatory Constraints
Queries on infinite relations *must* provide constraints that bound the iteration.
#+BEGIN_SRC erlang
%% INVALID: Cannot iterate infinite relation without constraints
Iterator = get_tuples_iterator(DB, naturals). ❌
%% VALID: Bounded by constraint
Iterator = get_tuples_iterator(DB, naturals, #{value => {range, 0, 100}}). ✓
#+END_SRC
** Constraint Validation
Before executing a query on an infinite relation, validate:
1. *Finite result check*: Do constraints guarantee finite result?
2. *Bounded iteration check*: Can we enumerate results in finite time?
#+BEGIN_SRC erlang
validate_constraints(Relation, Constraints) ->
case Relation#relation.cardinality of
{finite, _} ->
ok; % Finite relations don't need constraints
aleph_zero ->
case infers_finite_result(Relation, Constraints) of
true -> ok;
false -> {error, unbounded_iteration}
end;
continuum ->
{error, uncountable_relation} % Cannot iterate continuum
end.
#+END_SRC
** Constraint Inference
Smart inference of finiteness:
#+BEGIN_SRC erlang
%% These constraints imply finite results:
#{value => {range, 0, 100}} % Range is finite
#{value => {in, [1,2,3,4,5]}} % Membership in finite set
#{value => {lt, 10}} % Bounded above (if naturals)
%% These do NOT imply finite results:
#{value => {gt, 10}} % Unbounded above
#{value => {neq, 5}} % Excludes one element
#+END_SRC
* Implementation Strategy
** Phase 1: Core Infrastructure
1. Extend =relation= record with =cardinality= and =generator= fields
2. Implement cardinality algebra functions
3. Add constraint validation framework
** Phase 2: Primitive Relations
1. Implement =naturals= generator
2. Implement =integers= generator (interleaving strategy)
3. Implement =rationals= generator (Stern-Brocot or Calkin-Wilf)
** Phase 3: Function Relations
1. Implement =plus= relation
2. Implement =times= relation
3. Implement =successor=, =predecessor= relations
** Phase 4: Query Engine
1. Extend iterator model to support generators
2. Implement constraint-based enumeration
3. Add cardinality inference for query results
** Phase 5: Relational Operators
1. Extend join to handle infinite relations
2. Extend union with cardinality tracking
3. Extend selection with constraint propagation
* Open Questions
1. *Partial materialization*: Should we cache generated tuples?
2. *Generator composition*: How to compose generators for derived relations?
3. *Constraint solving*: Do we need a full constraint solver (CLP)?
4. *Termination guarantees*: How to prove queries terminate?
5. *Physical storage*: How to persist infinite relation definitions?
* References
- Codd, E. F. (1979). "Extending the Database Relational Model"
- Cantor, G. "On the Cardinality of Sets"
- Stern-Brocot Tree: Enumeration of rationals
- Calkin-Wilf Tree: Alternative rational enumeration
