Infinite relations (#10)

2 files changed, 1090 insertions, 20 deletions

diff --git a/src/generators.erl b/src/generators.erl
new file mode 100644
index 0000000..1dc363c
--- /dev/null
+++ b/src/generators.erl
@@ -0,0 +1,541 @@
+%%% @doc Generators for Infinite Relations
+%%%
+%%% This module provides generator functions for primitive infinite relations.
+%%%
+%%% == Domain Relations (Base Types) ==
+%%%
+%%% Domain relations are unary relations representing mathematical sets:
+%%% <ul>
+%%%   <li>Naturals (ℕ): {(0), (1), (2), (3), ...}</li>
+%%%   <li>Integers (ℤ): {(0), (1), (-1), (2), (-2), ...}</li>
+%%%   <li>Rationals (ℚ): {(0/1), (1/1), (1/2), (2/1), ...}</li>
+%%% </ul>
+%%%
+%%% Domain relations have empty schemas (`schema => #{}') as they are the
+%%% base case in the type system.
+%%%
+%%% == Function Relations ==
+%%%
+%%% Function relations represent mathematical operations as infinite relations:
+%%% <ul>
+%%%   <li>Plus: {(a, b, sum) | a ∈ ℤ, b ∈ ℤ, sum = a + b}</li>
+%%%   <li>Times: {(a, b, product) | a ∈ ℤ, b ∈ ℤ, product = a × b}</li>
+%%%   <li>Minus: {(a, b, difference) | a ∈ ℤ, b ∈ ℤ, difference = a - b}</li>
+%%%   <li>Divide: {(a, b, q, r) | a ∈ ℤ, b ∈ ℤ\{0}, a = b×q + r}</li>
+%%% </ul>
+%%%
+%%% Function relations reference domain relations in their schemas:
+%%% ```
+%%% schema => #{a => integers, b => integers, sum => integers}
+%%% '''
+%%%
+%%% == Reversibility ==
+%%%
+%%% Function relations support bidirectional querying (like Prolog):
+%%% <ul>
+%%%   <li>`Plus[1, 2, ?]' → ? = 3 (forward)</li>
+%%%   <li>`Plus[1, ?, 3]' → ? = 2 (backward, solve for b)</li>
+%%%   <li>`Plus[?, 2, 3]' → ? = 1 (backward, solve for a)</li>
+%%%   <li>`Plus[?, ?, 5]' → all pairs (a,b) where a+b=5</li>
+%%% </ul>
+%%%
+%%% The generators use constraint analysis to determine which arguments
+%%% are bound and compute the missing values accordingly.
+%%%
+%%% == Relational Composition ==
+%%%
+%%% In the future, function relations will be used through joins:
+%%% ```
+%%% Integer[A], Integer[B], Plus[A, B, Sum]
+%%% '''
+%%%
+%%% This corresponds to a three-way join where the join conditions
+%%% provide the constraints to each relation.
+%%%
+%%% Generators produce tuples lazily based on constraints, enabling
+%%% memory-bounded iteration over infinite relations.
+%%%
+%%% @author Nekoma Team
+%%% @copyright 2025
+
+-module(generators).
+-include("operations.hrl").
+
+-export([
+    naturals/1,
+    integers/1,
+    rationals/1,
+    make_range_generator/3,
+    constrained_naturals/2,
+    constrained_integers/2,
+    %% Function relations
+    plus/1,
+    times/1,
+    minus/1,
+    divide/1
+]).
+
+%%% ============================================================================
+%%% Primitive Generators
+%%% ============================================================================
+
+%% @doc Generator for natural numbers (ℕ = {0, 1, 2, 3, ...}).
+%%
+%% Enumerates natural numbers starting from 0. If constraints specify a range,
+%% only generates numbers within that range.
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing naturals
+naturals(Constraints) ->
+    case extract_bounds(Constraints, value) of
+        {range, Min, Max} when Min >= 0 ->
+            make_range_generator(Min, Max, fun(N) -> #{value => N} end);
+        {gte, Min} when Min >= 0 ->
+            make_unbounded_generator(Min, fun(N) -> #{value => N} end);
+        {lte, Max} when Max >= 0 ->
+            make_range_generator(0, Max, fun(N) -> #{value => N} end);
+        {eq, Value} when Value >= 0 ->
+            make_singleton_generator(#{value => Value});
+        {in, List} ->
+            make_membership_generator(List, fun(N) -> #{value => N} end);
+        unbounded ->
+            make_unbounded_generator(0, fun(N) -> #{value => N} end);
+        {error, Reason} ->
+            fun(_) -> {error, Reason} end
+    end.
+
+%% @doc Generator for integers (ℤ = {..., -2, -1, 0, 1, 2, ...}).
+%%
+%% Enumerates integers using interleaving strategy:
+%% 0, 1, -1, 2, -2, 3, -3, ...
+%%
+%% Mapping: f(0) = 0
+%%          f(2n) = n      for n > 0
+%%          f(2n+1) = -n   for n > 0
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing integers
+integers(Constraints) ->
+    case extract_bounds(Constraints, value) of
+        {range, Min, Max} ->
+            make_integer_range_generator(Min, Max);
+        {gte, Min} ->
+            make_unbounded_integer_generator(Min, infinity);
+        {lte, Max} ->
+            make_unbounded_integer_generator(neg_infinity, Max);
+        {eq, Value} ->
+            make_singleton_generator(#{value => Value});
+        {in, List} ->
+            make_membership_generator(List, fun(N) -> #{value => N} end);
+        unbounded ->
+            make_interleaved_integer_generator();
+        {error, Reason} ->
+            fun(_) -> {error, Reason} end
+    end.
+
+%% @doc Generator for rational numbers (ℚ) using Stern-Brocot tree.
+%%
+%% Enumerates all rational numbers in reduced form (p/q where gcd(p,q) = 1)
+%% using the Stern-Brocot tree, which systematically generates all positive
+%% rationals without repetition.
+%%
+%% Schema: #{numerator => integer, denominator => natural}
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing rationals
+rationals(Constraints) ->
+    %% Stern-Brocot tree enumeration
+    %% Start with mediant tree: 0/1, 1/1, then generate mediants
+    InitialState = {queue:from_list([{0, 1}, {1, 1}]), {0, 1}, {1, 0}},
+    make_stern_brocot_generator(InitialState, Constraints).
+
+%%% ============================================================================
+%%% Helper: Constraint Extraction
+%%% ============================================================================
+
+%% @doc Extract bounds from constraints for a given attribute.
+%%
+%% @param Constraints Constraint map
+%% @param Attr Attribute name
+%% @returns {range, Min, Max} | {gte, Min} | {lte, Max} | {eq, Value} | unbounded
+extract_bounds(Constraints, Attr) ->
+    case maps:get(Attr, Constraints, undefined) of
+        undefined ->
+            unbounded;
+        {range, Min, Max} ->
+            {range, Min, Max};
+        {gte, Min} ->
+            {gte, Min};
+        {lte, Max} ->
+            {lte, Max};
+        {gt, Min} ->
+            {gte, Min + 1};
+        {lt, Max} ->
+            {lte, Max - 1};
+        {eq, Value} ->
+            {eq, Value};
+        {in, List} ->
+            {in, List};
+        Other ->
+            {error, {unsupported_constraint, Other}}
+    end.
+
+%%% ============================================================================
+%%% Generator Constructors
+%%% ============================================================================
+
+%% @doc Create a generator for a finite range [Min, Max].
+make_range_generator(Min, Max, MapFun) when Min =< Max ->
+    make_range_gen(Min, Max, MapFun).
+
+make_range_gen(Current, Max, MapFun) when Current =< Max ->
+    fun(next) ->
+        Tuple = MapFun(Current),
+        NextGen = make_range_gen(Current + 1, Max, MapFun),
+        {value, Tuple, NextGen}
+    end;
+make_range_gen(_, _, _) ->
+    fun(_) -> done end.
+
+%% @doc Create an unbounded generator starting from Min.
+make_unbounded_generator(Start, MapFun) ->
+    make_unbounded_gen(Start, MapFun).
+
+make_unbounded_gen(Current, MapFun) ->
+    fun(next) ->
+        Tuple = MapFun(Current),
+        NextGen = make_unbounded_gen(Current + 1, MapFun),
+        {value, Tuple, NextGen}
+    end.
+
+%% @doc Create a singleton generator (single value).
+make_singleton_generator(Tuple) ->
+    fun(next) -> {value, Tuple, fun(_) -> done end} end.
+
+%% @doc Create a generator from a membership list.
+make_membership_generator([], _MapFun) ->
+    fun(_) -> done end;
+make_membership_generator([H|T], MapFun) ->
+    fun(next) ->
+        Tuple = MapFun(H),
+        NextGen = make_membership_generator(T, MapFun),
+        {value, Tuple, NextGen}
+    end.
+
+%% @doc Create integer range generator.
+make_integer_range_generator(Min, Max) when Min =< Max ->
+    make_range_generator(Min, Max, fun(N) -> #{value => N} end);
+make_integer_range_generator(_, _) ->
+    fun(_) -> done end.
+
+%% @doc Create interleaved integer generator: 0, 1, -1, 2, -2, 3, -3, ...
+make_interleaved_integer_generator() ->
+    make_interleaved_gen(0).
+
+make_interleaved_gen(0) ->
+    fun(next) ->
+        {value, #{value => 0}, make_interleaved_gen(1)}
+    end;
+make_interleaved_gen(N) ->
+    fun(next) ->
+        Positive = #{value => N},
+        NextGen1 = fun(next) ->
+            Negative = #{value => -N},
+            NextGen2 = make_interleaved_gen(N + 1),
+            {value, Negative, NextGen2}
+        end,
+        {value, Positive, NextGen1}
+    end.
+
+%% @doc Unbounded integer generator with optional min/max bounds.
+make_unbounded_integer_generator(neg_infinity, infinity) ->
+    make_interleaved_integer_generator();
+make_unbounded_integer_generator(Min, infinity) when is_integer(Min) ->
+    make_unbounded_generator(Min, fun(N) -> #{value => N} end);
+make_unbounded_integer_generator(neg_infinity, Max) when is_integer(Max) ->
+    %% Generate from Max down to -infinity
+    make_decreasing_gen(Max);
+make_unbounded_integer_generator(Min, Max) when is_integer(Min), is_integer(Max) ->
+    make_integer_range_generator(Min, Max).
+
+make_decreasing_gen(Current) ->
+    fun(next) ->
+        Tuple = #{value => Current},
+        NextGen = make_decreasing_gen(Current - 1),
+        {value, Tuple, NextGen}
+    end.
+
+%% @doc Stern-Brocot tree generator for rationals.
+%%
+%% The Stern-Brocot tree enumerates all positive rationals exactly once.
+%% Each rational p/q is generated in reduced form.
+%%
+%% Algorithm:
+%% 1. Start with two fractions: 0/1 (left ancestor) and 1/0 (right ancestor)
+%% 2. The mediant of a/b and c/d is (a+c)/(b+d)
+%% 3. Build tree by computing mediants
+make_stern_brocot_generator(State, _Constraints) ->
+    make_sb_gen(State).
+
+make_sb_gen({Queue, {LA, LB}, {RA, RB}}) ->
+    fun(next) ->
+        case queue:out(Queue) of
+            {empty, _} ->
+                done;
+            {{value, {P, Q}}, RestQueue} ->
+                %% Current rational is P/Q
+                Tuple = #{numerator => P, denominator => Q},
+
+                %% Generate children (mediants)
+                %% Left child: mediant of left ancestor and current
+                %% Right child: mediant of current and right ancestor
+                LeftChild = {LA + P, LB + Q},
+                RightChild = {P + RA, Q + RB},
+
+                %% Enqueue children
+                NewQueue = queue:in(RightChild, queue:in(LeftChild, RestQueue)),
+
+                %% Continue with updated state
+                NextGen = make_sb_gen({NewQueue, {LA, LB}, {RA, RB}}),
+                {value, Tuple, NextGen}
+        end
+    end.
+
+%%% ============================================================================
+%%% Constrained Generators (Public API)
+%%% ============================================================================
+
+%% @doc Create a constrained naturals generator.
+-spec constrained_naturals(non_neg_integer(), non_neg_integer()) -> generator_fun().
+constrained_naturals(Min, Max) ->
+    naturals(#{value => {range, Min, Max}}).
+
+%% @doc Create a constrained integers generator.
+-spec constrained_integers(integer(), integer()) -> generator_fun().
+constrained_integers(Min, Max) ->
+    integers(#{value => {range, Min, Max}}).
+
+%%% ============================================================================
+%%% Function Relations
+%%% ============================================================================
+
+%% @doc Plus relation: {(a, b, sum) | sum = a + b}.
+%%
+%% Generates tuples for the addition relation. Requires at least 2 of 3
+%% attributes to be constrained for bounded generation.
+%%
+%% Constraint strategies:
+%% <ul>
+%%   <li>a, b constrained → compute sum</li>
+%%   <li>a, sum constrained → compute b = sum - a</li>
+%%   <li>b, sum constrained → compute a = sum - b</li>
+%%   <li>sum constrained only → generate all (a,b) pairs that sum to value</li>
+%%   <li>Less than 1 constrained → error (unbounded)</li>
+%% </ul>
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing plus tuples
+plus(Constraints) ->
+    ABounds = extract_bounds(Constraints, a),
+    BBounds = extract_bounds(Constraints, b),
+    SumBounds = extract_bounds(Constraints, sum),
+
+    case {ABounds, BBounds, SumBounds} of
+        %% Both operands constrained - generate sums
+        {{range, AMin, AMax}, {range, BMin, BMax}, _} ->
+            make_plus_ab_generator(AMin, AMax, BMin, BMax);
+
+        %% a and sum constrained - compute b
+        {{range, AMin, AMax}, _, {range, SMin, SMax}} ->
+            make_plus_a_sum_generator(AMin, AMax, SMin, SMax);
+
+        %% b and sum constrained - compute a
+        {_, {range, BMin, BMax}, {range, SMin, SMax}} ->
+            make_plus_b_sum_generator(BMin, BMax, SMin, SMax);
+
+        %% Only sum constrained - generate all pairs
+        {unbounded, unbounded, {eq, SumValue}} ->
+            make_plus_sum_only_generator(SumValue);
+
+        {unbounded, unbounded, {range, SMin, SMax}} ->
+            make_plus_sum_range_generator(SMin, SMax);
+
+        %% Insufficient constraints
+        _ ->
+            fun(_) -> {error, {unbounded_plus, Constraints}} end
+    end.
+
+%% @doc Times relation: {(a, b, product) | product = a * b}.
+%%
+%% Generates tuples for the multiplication relation.
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing times tuples
+times(Constraints) ->
+    ABounds = extract_bounds(Constraints, a),
+    BBounds = extract_bounds(Constraints, b),
+    ProductBounds = extract_bounds(Constraints, product),
+
+    case {ABounds, BBounds, ProductBounds} of
+        %% Both operands constrained - generate products
+        {{range, AMin, AMax}, {range, BMin, BMax}, _} ->
+            make_times_ab_generator(AMin, AMax, BMin, BMax);
+
+        %% Insufficient constraints
+        _ ->
+            fun(_) -> {error, {unbounded_times, Constraints}} end
+    end.
+
+%% @doc Minus relation: {(a, b, difference) | difference = a - b}.
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing minus tuples
+minus(Constraints) ->
+    ABounds = extract_bounds(Constraints, a),
+    BBounds = extract_bounds(Constraints, b),
+    DiffBounds = extract_bounds(Constraints, difference),
+
+    case {ABounds, BBounds, DiffBounds} of
+        {{range, AMin, AMax}, {range, BMin, BMax}, _} ->
+            make_minus_ab_generator(AMin, AMax, BMin, BMax);
+
+        _ ->
+            fun(_) -> {error, {unbounded_minus, Constraints}} end
+    end.
+
+%% @doc Divide relation: {(a, b, quotient) | quotient = a / b, b ≠ 0}.
+%%
+%% @param Constraints Map of attribute constraints
+%% @returns Generator function producing divide tuples
+divide(Constraints) ->
+    ABounds = extract_bounds(Constraints, a),
+    BBounds = extract_bounds(Constraints, b),
+
+    case {ABounds, BBounds} of
+        {{range, AMin, AMax}, {range, BMin, BMax}} when BMin =/= 0 orelse BMax =/= 0 ->
+            make_divide_ab_generator(AMin, AMax, BMin, BMax);
+
+        _ ->
+            fun(_) -> {error, {unbounded_divide, Constraints}} end
+    end.
+
+%%% ============================================================================
+%%% Function Relation Generator Helpers
+%%% ============================================================================
+
+%% Plus: a and b constrained
+make_plus_ab_generator(AMin, AMax, BMin, BMax) ->
+    Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)],
+    make_plus_pairs_gen(Pairs).
+
+make_plus_pairs_gen([]) ->
+    fun(_) -> done end;
+make_plus_pairs_gen([{A, B} | Rest]) ->
+    fun(next) ->
+        Tuple = #{a => A, b => B, sum => A + B},
+        NextGen = make_plus_pairs_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Plus: a and sum constrained, compute b
+make_plus_a_sum_generator(AMin, AMax, SMin, SMax) ->
+    Pairs = [{A, S} ||
+             A <- lists:seq(AMin, AMax),
+             S <- lists:seq(SMin, SMax),
+             (S - A) >= 0],  % b must be non-negative if we want naturals
+    make_plus_a_sum_gen(Pairs).
+
+make_plus_a_sum_gen([]) ->
+    fun(_) -> done end;
+make_plus_a_sum_gen([{A, Sum} | Rest]) ->
+    fun(next) ->
+        B = Sum - A,
+        Tuple = #{a => A, b => B, sum => Sum},
+        NextGen = make_plus_a_sum_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Plus: b and sum constrained, compute a
+make_plus_b_sum_generator(BMin, BMax, SMin, SMax) ->
+    Pairs = [{B, S} ||
+             B <- lists:seq(BMin, BMax),
+             S <- lists:seq(SMin, SMax),
+             (S - B) >= 0],
+    make_plus_b_sum_gen(Pairs).
+
+make_plus_b_sum_gen([]) ->
+    fun(_) -> done end;
+make_plus_b_sum_gen([{B, Sum} | Rest]) ->
+    fun(next) ->
+        A = Sum - B,
+        Tuple = #{a => A, b => B, sum => Sum},
+        NextGen = make_plus_b_sum_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Plus: only sum constrained - generate all non-negative pairs
+make_plus_sum_only_generator(SumValue) ->
+    Pairs = [{A, SumValue - A} || A <- lists:seq(0, SumValue)],
+    make_plus_pairs_gen(Pairs).
+
+%% Plus: sum range constrained
+make_plus_sum_range_generator(SMin, SMax) ->
+    Pairs = [{A, B, S} ||
+             S <- lists:seq(SMin, SMax),
+             A <- lists:seq(0, S),
+             B <- [S - A]],
+    make_plus_triple_gen(Pairs).
+
+make_plus_triple_gen([]) ->
+    fun(_) -> done end;
+make_plus_triple_gen([{A, B, Sum} | Rest]) ->
+    fun(next) ->
+        Tuple = #{a => A, b => B, sum => Sum},
+        NextGen = make_plus_triple_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Times: a and b constrained
+make_times_ab_generator(AMin, AMax, BMin, BMax) ->
+    Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)],
+    make_times_pairs_gen(Pairs).
+
+make_times_pairs_gen([]) ->
+    fun(_) -> done end;
+make_times_pairs_gen([{A, B} | Rest]) ->
+    fun(next) ->
+        Tuple = #{a => A, b => B, product => A * B},
+        NextGen = make_times_pairs_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Minus: a and b constrained
+make_minus_ab_generator(AMin, AMax, BMin, BMax) ->
+    Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)],
+    make_minus_pairs_gen(Pairs).
+
+make_minus_pairs_gen([]) ->
+    fun(_) -> done end;
+make_minus_pairs_gen([{A, B} | Rest]) ->
+    fun(next) ->
+        Tuple = #{a => A, b => B, difference => A - B},
+        NextGen = make_minus_pairs_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
+
+%% Divide: a and b constrained (integer division)
+make_divide_ab_generator(AMin, AMax, BMin, BMax) ->
+    Pairs = [{A, B} ||
+             A <- lists:seq(AMin, AMax),
+             B <- lists:seq(BMin, BMax),
+             B =/= 0],  % Avoid division by zero
+    make_divide_pairs_gen(Pairs).
+
+make_divide_pairs_gen([]) ->
+    fun(_) -> done end;
+make_divide_pairs_gen([{A, B} | Rest]) ->
+    fun(next) ->
+        Tuple = #{a => A, b => B, quotient => A div B, remainder => A rem B},
+        NextGen = make_divide_pairs_gen(Rest),
+        {value, Tuple, NextGen}
+    end.
diff --git a/src/operations.erl b/src/operations.erl
index 1dd152b..58beae8 100644
--- a/src/operations.erl
+++ b/src/operations.erl
@@ -43,6 +43,7 @@
 	 hash/1,
          create_database/1,
 	 create_relation/3,
+	 create_infinite_relation/2,
 	 create_tuple/3,
 	 retract_tuple/3,
 	 retract_tuple/4,
@@ -54,9 +55,18 @@
 	 get_relation_hash/2,
          hashes_from_tuple/1,
 	 get_tuples_iterator/2,
+	 get_tuples_iterator/3,
+	 take/3,
 	 next_tuple/1,
 	 close_iterator/1,
-	 collect_all/1]).
+	 collect_all/1,
+	 %% Iterator operators (lazy)
+	 select_iterator/2,
+	 project_iterator/2,
+	 sort_iterator/2,
+	 take_iterator/2,
+	 %% Materialization (eager)
+	 materialize/3]).
 
 %% @doc Initialize Mnesia database schema and tables.
 %%
@@ -88,7 +98,7 @@ setup() ->
         {type, set}
     ]),
     mnesia:create_table(relation, [
-        {attributes, [hash, name, tree, schema]},
+        {attributes, [hash, name, tree, schema, constraints, cardinality, generator, provenance]},
         {disc_copies, [node()]},
         {type, set}
     ]),
@@ -168,11 +178,22 @@ create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Databa
         %% Step 6: Compute new relation hash as the root of the new merkle tree and store
         {_,NewRelationTreeHash,_,_} = NewRelationTree,
 	NewRelationHash = hash({RelationRecord#relation.name, RelationRecord#relation.schema, NewRelationTreeHash}),
+
+        %% Update cardinality: increment by 1
+        NewCardinality = case RelationRecord#relation.cardinality of
+            {finite, N} -> {finite, N + 1};
+            Other -> Other  % Shouldn't happen for finite relations
+        end,
+
         UpdatedRelation = #relation{
-            hash = NewRelationHash, 
-            name = RelationName, 
-            tree = NewRelationTree, 
-            schema = RelationRecord#relation.schema
+            hash = NewRelationHash,
+            name = RelationName,
+            tree = NewRelationTree,
+            schema = RelationRecord#relation.schema,
+            constraints = RelationRecord#relation.constraints,
+            cardinality = NewCardinality,
+            generator = RelationRecord#relation.generator,
+            provenance = RelationRecord#relation.provenance
         },
         mnesia:write(relation, UpdatedRelation, write),
         
@@ -384,10 +405,14 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st
         %% and therefore different tuples
         RelationHash = hash({Name, Definition, undefined}),
         NewRelation = #relation{
-            hash = RelationHash, 
-            name = Name, 
-            tree = undefined, 
-            schema = Definition
+            hash = RelationHash,
+            name = Name,
+            tree = undefined,
+            schema = Definition,
+            constraints = #{},           % No constraints by default
+            cardinality = {finite, 0},   % Empty relation
+            generator = undefined,        % Finite relation has no generator
+            provenance = {base, Name}     % Base relation
         },
         mnesia:write(relation, NewRelation, write),
         
@@ -450,6 +475,86 @@ create_database(Name) ->
     end),
     Entry.
 
+%% @doc Create an infinite relation with a generator.
+%%
+%% Creates a relation with infinite cardinality (aleph_zero or continuum).
+%% The relation is defined by a generator function that produces tuples
+%% lazily based on constraints.
+%%
+%% == Primitive Infinite Relations ==
+%%
+%% <ul>
+%%   <li>`naturals' - Natural numbers: {0, 1, 2, 3, ...}</li>
+%%   <li>`integers' - Integers: {0, 1, -1, 2, -2, ...}</li>
+%%   <li>`rationals' - Rationals via Stern-Brocot tree</li>
+%% </ul>
+%%
+%% == Example ==
+%% ```
+%% %% Create infinite relation of natural numbers
+%% {DB1, Naturals} = operations:create_infinite_relation(DB, #{
+%%     name => naturals,
+%%     schema => #{value => natural},
+%%     cardinality => aleph_zero,
+%%     generator => {primitive, naturals},
+%%     constraints => #{value => {gte, 0}}
+%% }).
+%%
+%% %% Query with bounds
+%% Iterator = operations:get_tuples_iterator(DB1, naturals,
+%%     #{value => {range, 0, 100}}).
+%% '''
+%%
+%% @param Database `#database_state{}' record
+%% @param Spec Map with keys: name, schema, cardinality, generator, constraints
+%% @returns `{UpdatedDatabase, NewRelation}' tuple
+%%
+%% @see create_relation/3
+%% @see get_tuples_iterator/3
+create_infinite_relation(Database, Spec) when is_record(Database, database_state) ->
+    Name = maps:get(name, Spec),
+    Schema = maps:get(schema, Spec),
+    Cardinality = maps:get(cardinality, Spec, aleph_zero),
+    GeneratorSpec = maps:get(generator, Spec),
+    Constraints = maps:get(constraints, Spec, #{}),
+
+    F = fun() ->
+        %% Hash is based on generator specification
+        RelationHash = hash({Name, Schema, GeneratorSpec, Cardinality}),
+
+        NewRelation = #relation{
+            hash = RelationHash,
+            name = Name,
+            tree = undefined,  % Infinite relations have no merkle tree
+            schema = Schema,
+            constraints = Constraints,
+            cardinality = Cardinality,
+            generator = GeneratorSpec,
+            provenance = {base, Name}
+        },
+        mnesia:write(relation, NewRelation, write),
+
+        %% Update database relations map
+        NewRelations = maps:put(Name, RelationHash, Database#database_state.relations),
+
+        %% Update database tree
+        NewTree = merklet:insert({atom_to_binary(Name), RelationHash}, Database#database_state.tree),
+        {_,NewHash,_,_} = NewTree,
+
+        UpdatedDatabase = #database_state{
+            name = Database#database_state.name,
+            hash = NewHash,
+            tree = NewTree,
+            relations = NewRelations,
+            timestamp = erlang:timestamp()
+        },
+        mnesia:write(database_state, UpdatedDatabase, write),
+
+        {UpdatedDatabase, NewRelation}
+    end,
+    {atomic, Result} = mnesia:transaction(F),
+    Result.
+
 %% @doc Get all relation names in a database.
 %%
 %% Returns a list of atoms representing all relation names currently
@@ -522,6 +627,114 @@ hashes_from_tuple(RelationHash) ->
         Tree -> merklet:keys(Tree)
     end.
 
+%% @doc Take operator (τ): Returns N arbitrary elements from a relation.
+%%
+%% The take operator is a unary relational operator that produces a finite
+%% relation containing N arbitrary elements from the input relation. Since
+%% relations are sets (unordered), the specific elements returned are
+%% determined by the enumeration order.
+%%
+%% For finite relations smaller than N, returns all elements.
+%% For infinite relations, returns first N elements by generator order.
+%%
+%% == Example ==
+%% ```
+%% %% Take 100 naturals (returns {0, 1, 2, ..., 99})
+%% {DB1, Naturals100} = operations:take(DB, naturals, 100).
+%%
+%% %% Can compose with other operators
+%% Iterator = operations:get_tuples_iterator(DB1, naturals100).
+%% '''
+%%
+%% @param Database `#database_state{}' record
+%% @param RelationName Atom naming the source relation
+%% @param N Number of elements to take
+%% @returns `{UpdatedDatabase, TakeRelation}' where TakeRelation is finite
+%%
+%% @see get_tuples_iterator/3
+take(Database, RelationName, N) when is_record(Database, database_state), is_integer(N), N > 0 ->
+    case maps:get(RelationName, Database#database_state.relations, error) of
+        error ->
+            erlang:error({relation_not_found, RelationName});
+        RelationHash ->
+            [SourceRelation] = mnesia:dirty_read(relation, RelationHash),
+
+            %% Compute cardinality of result
+            ResultCardinality = case SourceRelation#relation.cardinality of
+                {finite, M} when M < N -> {finite, M};
+                {finite, _} -> {finite, N};
+                _ -> {finite, N}  % Taking from infinite yields finite
+            end,
+
+            %% Create take relation
+            TakeName = list_to_atom(atom_to_list(RelationName) ++ "_take_" ++ integer_to_list(N)),
+
+            TakeRelation = #relation{
+                hash = hash({take, RelationName, N}),
+                name = TakeName,
+                tree = undefined,  % Generated on-demand
+                schema = SourceRelation#relation.schema,
+                constraints = SourceRelation#relation.constraints,
+                cardinality = ResultCardinality,
+                generator = {take, RelationName, N},
+                provenance = {take, SourceRelation#relation.provenance, N}
+            },
+
+            %% Note: We don't persist take relations to Mnesia for now
+            %% They are ephemeral views
+            {Database, TakeRelation}
+    end.
+
+%% @doc Create an iterator for streaming tuples from a relation with constraints.
+%%
+%% Extended version of get_tuples_iterator/2 that accepts boundedness constraints.
+%% For infinite relations, constraints are mandatory to ensure termination.
+%%
+%% == Constraints ==
+%%
+%% Constraints bound the iteration over infinite relations:
+%% <ul>
+%%   <li>`{range, Min, Max}' - Range constraint</li>
+%%   <li>`{eq, Value}' - Equality constraint</li>
+%%   <li>`{lt, Value}', `{lte, Value}' - Upper bounds</li>
+%%   <li>`{gt, Value}', `{gte, Value}' - Lower bounds</li>
+%%   <li>`{in, List}' - Membership constraint</li>
+%% </ul>
+%%
+%% == Example ==
+%% ```
+%% %% Iterate naturals in range [0, 100]
+%% Iterator = operations:get_tuples_iterator(DB, naturals,
+%%     #{value => {range, 0, 100}}).
+%% '''
+%%
+%% @param Database `#database_state{}' record
+%% @param RelationName Atom naming the relation to iterate
+%% @param Constraints Map of attribute constraints
+%% @returns Pid of iterator process
+%%
+%% @see get_tuples_iterator/2
+%% @see take/3
+get_tuples_iterator(Database, RelationName, Constraints) when is_record(Database, database_state) ->
+    case maps:get(RelationName, Database#database_state.relations, error) of
+        error ->
+            erlang:error({error_tuple_iterator_init, RelationName});
+        RelationHash ->
+            [Relation] = mnesia:dirty_read(relation, RelationHash),
+
+            case Relation#relation.cardinality of
+                {finite, _} ->
+                    %% Finite relation: use tuple hashes
+                    TupleHashes = hashes_from_tuple(RelationHash),
+                    spawn(fun() -> tuple_iterator_loop(TupleHashes) end);
+
+                _ ->
+                    %% Infinite relation: use generator
+                    Generator = instantiate_generator(Relation#relation.generator, Constraints),
+                    spawn(fun() -> generator_iterator_loop(Generator) end)
+            end
+    end.
+
 %% @doc Create an iterator for streaming tuples from a relation.
 %%
 %% Implements the Volcano Iterator Model: spawns an independent process that
@@ -535,6 +748,8 @@ hashes_from_tuple(RelationHash) ->
 %% The iterator process responds to `{next, Caller}' messages and sends back
 %% either `{tuple, Tuple}' or `done' when exhausted.
 %%
+%% <b>Note:</b> For infinite relations, use `get_tuples_iterator/3' with constraints.
+%%
 %% == Example ==
 %% ```
 %% Iterator = operations:get_tuples_iterator(DB, users),
@@ -546,15 +761,12 @@ hashes_from_tuple(RelationHash) ->
 %% @param RelationName Atom naming the relation to iterate
 %% @returns Pid of iterator process
 %%
+%% @see get_tuples_iterator/3
 %% @see next_tuple/1
 %% @see close_iterator/1
 %% @see collect_all/1
 get_tuples_iterator(Database, RelationName) when is_record(Database, database_state) ->
-    case maps:get(RelationName, Database#database_state.relations, error) of
-	error -> erlang:error({error_tuple_iterator_init, RelationName});
-	RelationHash -> TupleHashes = hashes_from_tuple(RelationHash),
-			spawn(fun() -> tuple_iterator_loop(TupleHashes) end)
-    end.
+    get_tuples_iterator(Database, RelationName, #{}).
 
 %% @doc Get next tuple from iterator.
 %%
@@ -574,7 +786,8 @@ next_tuple(IteratorPid) ->
     IteratorPid ! {next, self()},
     receive
         {tuple, Tuple} -> {ok, Tuple};
-        done -> done
+        done -> done;
+        {error, Reason} -> {error, Reason}
     after 5000 ->
         {error, timeout}
     end.
@@ -651,11 +864,327 @@ collect_all(IteratorPid) ->
 collect_all(IteratorPid, Acc) ->
     case next_tuple(IteratorPid) of
         {ok, Tuple} -> collect_all(IteratorPid, [Tuple | Acc]);
-        done -> 
+        done ->
             close_iterator(IteratorPid),
-            Acc;
-        {error, Reason} -> 
+            lists:reverse(Acc);  % Preserve order
+        {error, Reason} ->
             close_iterator(IteratorPid),
-            {error, Reason, Acc}
+            {error, Reason, lists:reverse(Acc)}
+    end.
+
+%%% ============================================================================
+%%% Iterator Operators (Lazy - Volcano Model)
+%%% ============================================================================
+
+%% @doc Select iterator: Filters tuples based on a predicate.
+%%
+%% Lazy operator that wraps a child iterator and only emits tuples that
+%% satisfy the predicate function.
+%%
+%% == Example ==
+%% ```
+%% BaseIter = get_tuples_iterator(DB, employees, #{}),
+%% FilteredIter = select_iterator(BaseIter, fun(E) -> maps:get(age, E) > 30 end),
+%% Tuples = collect_all(FilteredIter).
+%% '''
+%%
+%% @param ChildIterator Iterator process to filter
+%% @param Predicate Function: tuple() -> boolean()
+%% @returns Iterator process (Pid)
+select_iterator(ChildIterator, Predicate) when is_function(Predicate, 1) ->
+    spawn(fun() -> select_loop(ChildIterator, Predicate) end).
+
+select_loop(ChildPid, Predicate) ->
+    receive
+        {next, Caller} ->
+            case next_tuple(ChildPid) of
+                {ok, Tuple} ->
+                    case Predicate(Tuple) of
+                        true ->
+                            Caller ! {tuple, Tuple},
+                            select_loop(ChildPid, Predicate);
+                        false ->
+                            %% Skip this tuple, get next
+                            self() ! {next, Caller},
+                            select_loop(ChildPid, Predicate)
+                    end;
+                done ->
+                    close_iterator(ChildPid),
+                    Caller ! done
+            end;
+        stop ->
+            close_iterator(ChildPid),
+            ok
     end.
 
+%% @doc Project iterator: Projects tuples onto specified attributes.
+%%
+%% Lazy operator that transforms tuples by keeping only the specified
+%% attributes. This is the relational projection operator (π).
+%%
+%% == Example ==
+%% ```
+%% BaseIter = get_tuples_iterator(DB, employees, #{}),
+%% ProjectedIter = project_iterator(BaseIter, [name, age]),
+%% Tuples = collect_all(ProjectedIter).
+%% '''
+%%
+%% @param ChildIterator Iterator process to project
+%% @param Attributes List of attribute names to keep
+%% @returns Iterator process (Pid)
+project_iterator(ChildIterator, Attributes) when is_list(Attributes) ->
+    spawn(fun() -> project_loop(ChildIterator, Attributes) end).
+
+project_loop(ChildPid, Attributes) ->
+    receive
+        {next, Caller} ->
+            case next_tuple(ChildPid) of
+                {ok, Tuple} ->
+                    ProjectedTuple = maps:with(Attributes, Tuple),
+                    Caller ! {tuple, ProjectedTuple},
+                    project_loop(ChildPid, Attributes);
+                done ->
+                    close_iterator(ChildPid),
+                    Caller ! done
+            end;
+        stop ->
+            close_iterator(ChildPid),
+            ok
+    end.
+
+%% @doc Sort iterator: Sorts all tuples from child iterator.
+%%
+%% <b>Blocking operator</b> - must consume ALL tuples from child before
+%% emitting any output. Materializes and sorts tuples in memory.
+%%
+%% <b>Warning:</b> Do not use on unbounded streams! Ensure child iterator
+%% produces finite tuples (via constraints or take).
+%%
+%% == Example ==
+%% ```
+%% BaseIter = get_tuples_iterator(DB, employees, #{}),
+%% SortedIter = sort_iterator(BaseIter, fun(A, B) ->
+%%     maps:get(age, A) =< maps:get(age, B)
+%% end),
+%% Tuples = collect_all(SortedIter).
+%% '''
+%%
+%% @param ChildIterator Iterator process to sort
+%% @param CompareFun Function: (tuple(), tuple()) -> boolean()
+%% @returns Iterator process (Pid)
+sort_iterator(ChildIterator, CompareFun) when is_function(CompareFun, 2) ->
+    spawn(fun() ->
+        %% Phase 1: Consume all tuples (blocking!)
+        AllTuples = collect_all(ChildIterator),
+
+        %% Phase 2: Sort in memory
+        SortedTuples = lists:sort(CompareFun, AllTuples),
+
+        %% Phase 3: Emit sorted tuples on demand
+        sorted_emit_loop(SortedTuples)
+    end).
+
+sorted_emit_loop([]) ->
+    receive
+        {next, Caller} -> Caller ! done;
+        stop -> ok
+    end;
+sorted_emit_loop([Tuple | Rest]) ->
+    receive
+        {next, Caller} ->
+            Caller ! {tuple, Tuple},
+            sorted_emit_loop(Rest);
+        stop -> ok
+    end.
+
+%% @doc Take iterator: Limits output to N tuples.
+%%
+%% Lazy operator that emits at most N tuples from the child iterator,
+%% then closes the child and signals done.
+%%
+%% == Example ==
+%% ```
+%% BaseIter = get_tuples_iterator(DB, naturals, #{value => {range, 0, 1000}}),
+%% LimitedIter = take_iterator(BaseIter, 10),
+%% Tuples = collect_all(LimitedIter).  % Gets exactly 10 tuples
+%% '''
+%%
+%% @param ChildIterator Iterator process to limit
+%% @param N Maximum number of tuples to emit
+%% @returns Iterator process (Pid)
+take_iterator(ChildIterator, N) when is_integer(N), N > 0 ->
+    spawn(fun() -> take_iter_loop(ChildIterator, N, 0) end).
+
+take_iter_loop(ChildPid, Limit, Count) when Count < Limit ->
+    receive
+        {next, Caller} ->
+            case next_tuple(ChildPid) of
+                {ok, Tuple} ->
+                    Caller ! {tuple, Tuple},
+                    take_iter_loop(ChildPid, Limit, Count + 1);
+                done ->
+                    close_iterator(ChildPid),
+                    Caller ! done
+            end;
+        stop ->
+            close_iterator(ChildPid),
+            ok
+    end;
+take_iter_loop(ChildPid, _Limit, _Count) ->
+    %% Reached limit - close child and signal done
+    close_iterator(ChildPid),
+    receive
+        {next, Caller} -> Caller ! done;
+        stop -> ok
+    end.
+
+%%% ============================================================================
+%%% Materialization (Eager - Relation Creation)
+%%% ============================================================================
+
+%% @doc Materialize an iterator pipeline into a new relation.
+%%
+%% This is the boundary between lazy evaluation (iterator pipeline) and
+%% eager materialization (stored relation). Consumes all tuples from the
+%% iterator and stores them as a new finite relation in the database.
+%%
+%% == Example ==
+%% ```
+%% %% Build lazy pipeline
+%% Pipeline = get_tuples_iterator(DB, employees, #{})
+%%            |> select_iterator(fun(E) -> maps:get(age, E) > 30 end)
+%%            |> sort_iterator(fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end)
+%%            |> take_iterator(10)
+%%            |> project_iterator([name, age]),
+%%
+%% %% Materialize into new relation
+%% {DB1, SeniorEmployees} = materialize(DB, Pipeline, senior_employees).
+%% '''
+%%
+%% @param Database Current database state
+%% @param SourceIterator Iterator process (pipeline endpoint)
+%% @param ResultName Atom naming the new relation
+%% @returns `{UpdatedDatabase, NewRelation}' tuple
+materialize(Database, SourceIterator, ResultName) when is_record(Database, database_state) ->
+    %% 1. Pull all tuples from pipeline
+    AllTuples = collect_all(SourceIterator),
+
+    case AllTuples of
+        [] ->
+            %% Empty result - create empty relation
+            Schema = #{},  % Empty schema
+            create_relation(Database, ResultName, Schema);
+
+        [FirstTuple | _] ->
+            %% 2. Infer schema from first tuple
+            Schema = infer_schema_from_tuple(FirstTuple),
+
+            %% 3. Create new relation
+            {DB1, _Relation} = create_relation(Database, ResultName, Schema),
+
+            %% 4. Insert all tuples
+            {FinalDB, FinalRelation} = insert_all_tuples(DB1, ResultName, AllTuples),
+
+            {FinalDB, FinalRelation}
+    end.
+
+%% @private
+%% @doc Infer schema from a tuple.
+infer_schema_from_tuple(Tuple) when is_map(Tuple) ->
+    maps:map(fun(_AttrName, Value) -> infer_type(Value) end, Tuple).
+
+%% @private
+%% @doc Infer type from value.
+infer_type(Value) when is_integer(Value) -> integer;
+infer_type(Value) when is_float(Value) -> float;
+infer_type(Value) when is_binary(Value) -> binary;
+infer_type(Value) when is_list(Value) -> string;
+infer_type(Value) when is_atom(Value) -> atom;
+infer_type(Value) when is_boolean(Value) -> boolean;
+infer_type(_) -> term.
+
+%% @private
+%% @doc Insert multiple tuples into a relation.
+insert_all_tuples(DB, RelationName, Tuples) ->
+    lists:foldl(
+        fun(Tuple, {DBacc, _RelAcc}) ->
+            create_tuple(DBacc, RelationName, Tuple)
+        end,
+        {DB, undefined},
+        Tuples
+    ).
+
+%%% ============================================================================
+%%% Generator Support Functions
+%%% ============================================================================
+
+%% @private
+%% @doc Instantiate a generator from a generator specification.
+%%
+%% Converts a generator spec (stored in relation record) into an actual
+%% generator function that can produce tuples.
+%%
+%% @param GeneratorSpec Generator specification
+%% @param Constraints Boundedness constraints
+%% @returns Generator function
+instantiate_generator({primitive, naturals}, Constraints) ->
+    generators:naturals(Constraints);
+instantiate_generator({primitive, integers}, Constraints) ->
+    generators:integers(Constraints);
+instantiate_generator({primitive, rationals}, Constraints) ->
+    generators:rationals(Constraints);
+instantiate_generator({primitive, plus}, Constraints) ->
+    generators:plus(Constraints);
+instantiate_generator({primitive, times}, Constraints) ->
+    generators:times(Constraints);
+instantiate_generator({primitive, minus}, Constraints) ->
+    generators:minus(Constraints);
+instantiate_generator({primitive, divide}, Constraints) ->
+    generators:divide(Constraints);
+instantiate_generator({custom, GeneratorFun}, Constraints) ->
+    GeneratorFun(Constraints);
+instantiate_generator({take, RelationName, N}, Constraints) ->
+    %% Take generator: wrap another generator with limit
+    %% This is a simplified version - full implementation would look up the base relation
+    make_take_generator(RelationName, N, Constraints);
+instantiate_generator(Other, _) ->
+    erlang:error({unknown_generator, Other}).
+
+%% @private
+%% @doc Generator iterator loop for infinite relations.
+%%
+%% Similar to tuple_iterator_loop but works with generator functions instead
+%% of tuple hashes.
+%%
+%% @param Generator Generator function
+generator_iterator_loop(Generator) ->
+    receive
+        {next, Caller} ->
+            case Generator(next) of
+                done ->
+                    Caller ! done;
+                {value, Tuple, NextGen} ->
+                    Caller ! {tuple, Tuple},
+                    generator_iterator_loop(NextGen);
+                {error, Reason} ->
+                    Caller ! {error, Reason}
+            end;
+        stop ->
+            ok
+    end.
+
+%% @private
+%% @doc Create a take generator that limits another generator.
+make_take_generator(_RelationName, N, _Constraints) ->
+    %% Simplified version: just count to N
+    make_take_gen(0, N).
+
+make_take_gen(Current, Max) when Current < Max ->
+    fun(next) ->
+        Tuple = #{value => Current},
+        NextGen = make_take_gen(Current + 1, Max),
+        {value, Tuple, NextGen}
+    end;
+make_take_gen(_, _) ->
+    fun(_) -> done end.
+