From 09be36e5f5e2c5714b9542df8ccc363ab86ac6da Mon Sep 17 00:00:00 2001 From: Marcos Magueta Date: Sat, 22 Nov 2025 22:32:04 -0300 Subject: Infinite relations (#10) --- .github/workflows/docs.yml | 3 + docs/infinite_relations_design.org | 348 +++++++++++++++++++++++ include/operations.hrl | 71 ++++- src/generators.erl | 541 +++++++++++++++++++++++++++++++++++ src/operations.erl | 569 +++++++++++++++++++++++++++++++++++-- test/function_relations_test.erl | 339 ++++++++++++++++++++++ test/infinite_relations_test.erl | 147 ++++++++++ test/query_pipeline_test.erl | 190 +++++++++++++ 8 files changed, 2187 insertions(+), 21 deletions(-) create mode 100644 docs/infinite_relations_design.org create mode 100644 src/generators.erl create mode 100644 test/function_relations_test.erl create mode 100644 test/infinite_relations_test.erl create mode 100644 test/query_pipeline_test.erl diff --git a/.github/workflows/docs.yml b/.github/workflows/docs.yml index e659d8e..ca59856 100644 --- a/.github/workflows/docs.yml +++ b/.github/workflows/docs.yml @@ -45,6 +45,9 @@ jobs: - name: Generate EDoc run: rebar3 edoc + - name: Fix index.html for GitHub Pages + run: cp doc/overview-summary.html doc/index.html + - name: Setup Pages uses: actions/configure-pages@v4 diff --git a/docs/infinite_relations_design.org b/docs/infinite_relations_design.org new file mode 100644 index 0000000..c13e783 --- /dev/null +++ b/docs/infinite_relations_design.org @@ -0,0 +1,348 @@ +#+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 diff --git a/include/operations.hrl b/include/operations.hrl index fcd2d83..6d481ad 100644 --- a/include/operations.hrl +++ b/include/operations.hrl @@ -1,4 +1,73 @@ +%%% Core Records + -record(database_state, {hash, name, tree, relations, timestamp}). --record(relation, {hash, name, tree, schema}). + +-record(relation, { + hash, % Content hash (finite) or generator hash (infinite) + name, % Relation name (atom) + tree, % Merkle tree (finite only), undefined for infinite + schema, % #{attribute_name => type} + constraints, % #{attribute_name => constraint_spec()} - integrity constraints + cardinality, % {finite, N} | aleph_zero | continuum + generator, % Generator function (infinite only), undefined for finite + provenance % Provenance tracking for updatable views (future) +}). + -record(tuple, {hash, relation, attribute_map}). -record(attribute, {hash, value}). + +%%% Cardinality Types + +-type cardinality() :: {finite, non_neg_integer()} % Finite set with N elements + | aleph_zero % Countably infinite (ℵ₀) + | continuum. % Uncountably infinite (2^ℵ₀) + +%%% Constraint Types + +-type constraint_spec() :: + {eq, term()} % Equality: attr = value + | {neq, term()} % Inequality: attr ≠ value + | {lt, number()} % Less than: attr < value + | {lte, number()} % Less than or equal: attr ≤ value + | {gt, number()} % Greater than: attr > value + | {gte, number()} % Greater than or equal: attr ≥ value + | {in, [term()]} % Membership: attr ∈ list + | {range, number(), number()} % Range: attr ∈ [min, max] + | {member_of, atom()}. % Type constraint: attr ∈ Relation + +-type constraints() :: #{atom() => constraint_spec()}. + +-type boundedness_constraints() :: #{atom() => constraints()}. + +%%% Generator Types + +-type generator_fun() :: fun((constraints()) -> generator_result()). + +-type generator_result() :: + done % No more tuples + | {value, map(), generator_fun()} % Tuple and continuation + | {error, term()}. % Error + +-type generator_spec() :: + {primitive, atom()} % Built-in: naturals, integers, rationals + | {custom, generator_fun()} % User-defined generator + | {take, atom(), pos_integer()} % Take N from relation + | {derived, relational_op()}. % Derived from relational operation + +-type relational_op() :: + {select, atom(), constraints()} + | {project, atom(), [atom()]} + | {join, atom(), atom(), join_spec()}. + +-type join_spec() :: + {equijoin, atom()} % Natural join on attribute + | {theta, atom(), atom(), atom()}. % Theta join: op(attr1, attr2) + +%%% Provenance Types (for updatable views) + +-type provenance() :: undefined + | {base, atom()} % Base relation + | {join, provenance(), provenance()} + | {select, provenance(), constraints()} + | {project, provenance(), [atom()]} + | {take, provenance(), pos_integer()}. 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: +%%% +%%% +%%% 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: +%%% +%%% +%%% Function relations reference domain relations in their schemas: +%%% ``` +%%% schema => #{a => integers, b => integers, sum => integers} +%%% ''' +%%% +%%% == Reversibility == +%%% +%%% Function relations support bidirectional querying (like Prolog): +%%% +%%% +%%% 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: +%% +%% +%% @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 == +%% +%% +%% +%% == 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: +%% +%% +%% == 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. %% +%% Note: 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. +%% +%% Blocking operator - must consume ALL tuples from child before +%% emitting any output. Materializes and sorts tuples in memory. +%% +%% Warning: 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. + diff --git a/test/function_relations_test.erl b/test/function_relations_test.erl new file mode 100644 index 0000000..78c9ec3 --- /dev/null +++ b/test/function_relations_test.erl @@ -0,0 +1,339 @@ +-module(function_relations_test). +-include_lib("eunit/include/eunit.hrl"). +-include("operations.hrl"). + +%%% Function Relations Test Suite +%%% +%%% Testing infinite relations that represent arithmetic operations. +%%% These work like functions but backwards too (Prolog-style) +%%% +%%% - Plus: {(a, b, sum) | sum = a + b } +%%% - Times: {(a, b, product) | product = a * b} +%%% - Minus: {(a, b, difference) | difference = a - b} +%%% - Divide: {(a, b, quotient, remainder) | a = b*quotient + remainder} + +function_relations_test_() -> + {foreach, + fun setup/0, + fun cleanup/1, + [ + fun test_plus_both_operands_constrained/1, + fun test_plus_a_and_sum_constrained/1, + fun test_plus_b_and_sum_constrained/1, + fun test_plus_only_sum_constrained/1, + fun test_plus_sum_range_constrained/1, + fun test_plus_insufficient_constraints/1, + fun test_times_both_operands_constrained/1, + fun test_times_insufficient_constraints/1, + fun test_minus_both_operands_constrained/1, + fun test_divide_both_operands_constrained/1, + fun test_divide_avoids_zero/1, + fun test_plus_join_with_finite/1, + fun test_materialized_plus_relation/1 + ]}. + +%%% Setup and Cleanup + +setup() -> + operations:setup(), + DB = operations:create_database(test_db), + + % First set up the basic number types (integers, naturals, etc) + {DB1, _Integers} = operations:create_infinite_relation(DB, #{ + name => integers, + schema => #{}, % empty schema - this is a base type + cardinality => aleph_zero, + generator => {primitive, integers} + }), + + {DB2, _Naturals} = operations:create_infinite_relation(DB1, #{ + name => naturals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, naturals} + }), + + % Now create the function relations - note how their schemas reference the domain relations above + {DB3, _Plus} = operations:create_infinite_relation(DB2, #{ + name => plus, + schema => #{a => integers, b => integers, sum => integers}, + cardinality => aleph_zero, + generator => {primitive, plus} + }), + + {DB4, _Times} = operations:create_infinite_relation(DB3, #{ + name => times, + schema => #{a => integers, b => integers, product => integers}, + cardinality => aleph_zero, + generator => {primitive, times} + }), + + {DB5, _Minus} = operations:create_infinite_relation(DB4, #{ + name => minus, + schema => #{a => integers, b => integers, difference => integers}, + cardinality => aleph_zero, + generator => {primitive, minus} + }), + + {DB6, _Divide} = operations:create_infinite_relation(DB5, #{ + name => divide, + schema => #{a => integers, b => integers, quotient => integers, remainder => naturals}, + cardinality => aleph_zero, + generator => {primitive, divide} + }), + + DB6. + +cleanup(_DB) -> + ok. + +%%% Plus Relation Tests + +test_plus_both_operands_constrained(DB) -> + % Both operands bounded: a ∈ [1,3], b ∈ [2,4] + % TODO: eventually this should be a proper join like Integer[A], Integer[B], Plus[A,B,Sum] + % but for now just pass constraints directly + Iterator = operations:get_tuples_iterator(DB, plus, #{ + a => {range, 1, 3}, + b => {range, 2, 4} + }), + Results = operations:collect_all(Iterator), + + % should get 9 tuples total (3 × 3 = 9) + % like (1,2,3), (1,3,4), (1,4,5), (2,2,4), ..., (3,4,7) + [ + ?_assertEqual(9, length(Results)), + ?_assert(lists:member(#{a => 1, b => 2, sum => 3}, Results)), + ?_assert(lists:member(#{a => 2, b => 3, sum => 5}, Results)), + ?_assert(lists:member(#{a => 3, b => 4, sum => 7}, Results)), + ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> + S =:= A + B + end, Results)) + ]. + +test_plus_a_and_sum_constrained(DB) -> + % Test reversibility - given A and Sum, compute B + % a ∈ [1,3], sum ∈ [5,7], so b = sum - a + % This is like asking: Plus[A, ?, Sum] + Iterator = operations:get_tuples_iterator(DB, plus, #{ + a => {range, 1, 3}, + sum => {range, 5, 7} + }), + Results = operations:collect_all(Iterator), + + % Expected tuples: (1,4,5), (1,5,6), (1,6,7), (2,3,5), (2,4,6), (2,5,7), (3,2,5), (3,3,6), (3,4,7) + % (filtered to only keep where b >= 0) + [ + ?_assert(length(Results) > 0), + ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> + S =:= A + B andalso B >= 0 + end, Results)), + ?_assert(lists:member(#{a => 1, b => 4, sum => 5}, Results)), + ?_assert(lists:member(#{a => 3, b => 4, sum => 7}, Results)) + ]. + +test_plus_b_and_sum_constrained(DB) -> + % Another reversibility test - now given B and Sum, find A + % b ∈ [2,4], sum ∈ [5,6] → a = sum - b + % Like: Plus[?, B, Sum] + Iterator = operations:get_tuples_iterator(DB, plus, #{ + b => {range, 2, 4}, + sum => {range, 5, 6} + }), + Results = operations:collect_all(Iterator), + + [ + ?_assert(length(Results) > 0), + ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> + S =:= A + B andalso A >= 0 + end, Results)), + ?_assert(lists:member(#{a => 3, b => 2, sum => 5}, Results)), + ?_assert(lists:member(#{a => 2, b => 4, sum => 6}, Results)) + ]. + +test_plus_only_sum_constrained(DB) -> + % Only constrain the sum - should give us all ways to add up to 5 + % Plus[?, ?, 5] generates: (0,5), (1,4), (2,3), (3,2), (4,1), (5,0) + Iterator = operations:get_tuples_iterator(DB, plus, #{ + sum => {eq, 5} + }), + Results = operations:collect_all(Iterator), + + [ + ?_assertEqual(6, length(Results)), + ?_assert(lists:member(#{a => 0, b => 5, sum => 5}, Results)), + ?_assert(lists:member(#{a => 2, b => 3, sum => 5}, Results)), + ?_assert(lists:member(#{a => 5, b => 0, sum => 5}, Results)), + ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> + S =:= A + B andalso S =:= 5 + end, Results)) + ]. + +test_plus_sum_range_constrained(DB) -> + % sum in a range [2,3] instead of single value + Iterator = operations:get_tuples_iterator(DB, plus, #{ + sum => {range, 2, 3} + }), + Results = operations:collect_all(Iterator), + + % For sum=2: (0,2), (1,1), (2,0) → 3 pairs + % For sum=3: (0,3), (1,2), (2,1), (3,0) → 4 pairs + % Total = 7 + [ + ?_assertEqual(7, length(Results)), + ?_assert(lists:all(fun(#{sum := S}) -> S >= 2 andalso S =< 3 end, Results)), + ?_assert(lists:member(#{a => 0, b => 2, sum => 2}, Results)), + ?_assert(lists:member(#{a => 3, b => 0, sum => 3}, Results)) + ]. + +test_plus_insufficient_constraints(DB) -> + % Try querying with zero constraints - should fail since we'd get infinite results + Iterator = operations:get_tuples_iterator(DB, plus, #{}), + Result = operations:next_tuple(Iterator), + + [ + ?_assertMatch({error, {unbounded_plus, _}}, Result) + ]. + +%%% Times (multiplication) Tests + +test_times_both_operands_constrained(DB) -> + % Basic multiplication with both inputs bounded + Iterator = operations:get_tuples_iterator(DB, times, #{ + a => {range, 2, 4}, + b => {range, 3, 5} + }), + Results = operations:collect_all(Iterator), + + % 3×3 = 9 tuples + [ + ?_assertEqual(9, length(Results)), + ?_assert(lists:member(#{a => 2, b => 3, product => 6}, Results)), + ?_assert(lists:member(#{a => 3, b => 4, product => 12}, Results)), + ?_assert(lists:member(#{a => 4, b => 5, product => 20}, Results)), + ?_assert(lists:all(fun(#{a := A, b := B, product := P}) -> + P =:= A * B + end, Results)) + ]. + +test_times_insufficient_constraints(DB) -> + % Times doesn't support full reversibility yet (would need factorization) + % So constraining just one operand should error + Iterator = operations:get_tuples_iterator(DB, times, #{a => {range, 1, 5}}), + Result = operations:next_tuple(Iterator), + + [ + ?_assertMatch({error, {unbounded_times, _}}, Result) + ]. + +%%% Minus (subtraction) Tests + +test_minus_both_operands_constrained(DB) -> + % subtraction with both operands bounded + Iterator = operations:get_tuples_iterator(DB, minus, #{ + a => {range, 5, 7}, + b => {range, 2, 3} + }), + Results = operations:collect_all(Iterator), + + % 3 × 2 = 6 tuples + [ + ?_assertEqual(6, length(Results)), + ?_assert(lists:member(#{a => 5, b => 2, difference => 3}, Results)), + ?_assert(lists:member(#{a => 7, b => 3, difference => 4}, Results)), + ?_assert(lists:all(fun(#{a := A, b := B, difference := D}) -> + D =:= A - B + end, Results)) + ]. + +%%% Divide (integer division) Tests + +test_divide_both_operands_constrained(DB) -> + % Integer division with quotient and remainder + Iterator = operations:get_tuples_iterator(DB, divide, #{ + a => {range, 10, 12}, + b => {range, 3, 4} + }), + Results = operations:collect_all(Iterator), + + % 3 × 2 = 6 tuples + [ + ?_assertEqual(6, length(Results)), + ?_assert(lists:member(#{a => 10, b => 3, quotient => 3, remainder => 1}, Results)), + ?_assert(lists:member(#{a => 12, b => 4, quotient => 3, remainder => 0}, Results)), + ?_assert(lists:all(fun(#{a := A, b := B, quotient := Q, remainder := R}) -> + A =:= B * Q + R andalso R >= 0 andalso R < abs(B) + end, Results)) + ]. + +test_divide_avoids_zero(DB) -> + % Make sure we don't try to divide by zero + % even if the range includes 0 + Iterator = operations:get_tuples_iterator(DB, divide, #{ + a => {range, 5, 7}, + b => {range, 0, 2} + }), + Results = operations:collect_all(Iterator), + + % 3 × 2 = 6 (skips b=0, only uses b=1,2) + [ + ?_assertEqual(6, length(Results)), + ?_assert(lists:all(fun(#{b := B}) -> B =/= 0 end, Results)) + ]. + +%%% Integration Tests + +test_plus_join_with_finite(DB) -> + % Simulate joining an infinite relation with a finite one + {DB1, _Employees} = operations:create_relation(DB, employees, #{ + name => string, + age => integer + }), + + {DB2, _} = operations:create_tuple(DB1, employees, #{name => "Alice", age => 30}), + {DB3, _} = operations:create_tuple(DB2, employees, #{name => "Bob", age => 35}), + + EmployeeIter = operations:get_tuples_iterator(DB3, employees, #{}), + Employees = operations:collect_all(EmployeeIter), + + % For each employee's age, find all the ways to add up to it + % (simulating: Employee JOIN Plus ON Plus.sum = Employee.age) + Results = lists:flatmap(fun(#{age := Age}) -> + PlusIter = operations:get_tuples_iterator(DB3, plus, #{ + a => {range, 0, 15}, + b => {range, 0, 15}, + sum => {eq, Age} + }), + Tuples = operations:collect_all(PlusIter), + [#{age => Age, plus_tuple => T} || T <- Tuples] + end, Employees), + + % verify we got some results + [ + ?_assert(length(Results) > 0), + ?_assert(lists:any(fun(#{age := Age, plus_tuple := #{sum := S}}) -> + Age =:= S + end, Results)) + ]. + +test_materialized_plus_relation(DB) -> + % Take an infinite relation, constrain it, and materialize into a finite one + PlusIter = operations:get_tuples_iterator(DB, plus, #{ + a => {range, 0, 2}, + b => {range, 0, 2} + }), + + % Turn it into an actual stored relation + {DB1, SmallPlus} = operations:materialize(DB, PlusIter, small_plus), + + % check that it worked + ResultIter = operations:get_tuples_iterator(DB1, small_plus, #{}), + Results = operations:collect_all(ResultIter), + + [ + ?_assertEqual({finite, 9}, SmallPlus#relation.cardinality), + ?_assertEqual(9, length(Results)), + ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> + S =:= A + B andalso A >= 0 andalso A =< 2 andalso B >= 0 andalso B =< 2 + end, Results)) + ]. diff --git a/test/infinite_relations_test.erl b/test/infinite_relations_test.erl new file mode 100644 index 0000000..cafd325 --- /dev/null +++ b/test/infinite_relations_test.erl @@ -0,0 +1,147 @@ +-module(infinite_relations_test). +-include_lib("eunit/include/eunit.hrl"). +-include("operations.hrl"). + +%%% Test Suite for Infinite Relations + +infinite_relations_test_() -> + {foreach, + fun setup/0, + fun cleanup/1, + [ + fun test_create_naturals/1, + fun test_naturals_with_constraints/1, + fun test_integers_generator/1, + fun test_rationals_generator/1, + fun test_take_operator/1, + fun test_finite_relation_cardinality/1 + ]}. + +%%% Setup and Cleanup + +setup() -> + operations:setup(), + operations:create_database(test_db). + +cleanup(_DB) -> + ok. + +%%% Tests + +test_create_naturals(DB) -> + %% Create infinite relation of natural numbers + %% Domain relations have empty schemas (base case) + {DB1, Naturals} = operations:create_infinite_relation(DB, #{ + name => naturals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, naturals}, + constraints => #{value => {gte, 0}} + }), + + [ + ?_assert(is_record(Naturals, relation)), + ?_assertEqual(naturals, Naturals#relation.name), + ?_assertEqual(aleph_zero, Naturals#relation.cardinality), + ?_assertEqual({primitive, naturals}, Naturals#relation.generator) + ]. + +test_naturals_with_constraints(DB) -> + %% Create naturals relation + {DB1, _Naturals} = operations:create_infinite_relation(DB, #{ + name => naturals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, naturals}, + constraints => #{value => {gte, 0}} + }), + + %% Query with range constraint [0, 9] + Iterator = operations:get_tuples_iterator(DB1, naturals, #{value => {range, 0, 9}}), + Tuples = operations:collect_all(Iterator), + + %% Should get exactly 10 tuples: {0, 1, 2, ..., 9} + [ + ?_assertEqual(10, length(Tuples)), + ?_assert(lists:member(#{value => 0}, Tuples)), + ?_assert(lists:member(#{value => 5}, Tuples)), + ?_assert(lists:member(#{value => 9}, Tuples)) + ]. + +test_integers_generator(DB) -> + %% Create integers relation + {DB1, Integers} = operations:create_infinite_relation(DB, #{ + name => integers, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, integers} + }), + + %% Query with range constraint [-5, 5] + Iterator = operations:get_tuples_iterator(DB1, integers, #{value => {range, -5, 5}}), + Tuples = operations:collect_all(Iterator), + + %% Should get 11 tuples: {-5, -4, ..., 0, ..., 4, 5} + [ + ?_assertEqual(aleph_zero, Integers#relation.cardinality), + ?_assertEqual(11, length(Tuples)), + ?_assert(lists:member(#{value => 0}, Tuples)), + ?_assert(lists:member(#{value => -5}, Tuples)), + ?_assert(lists:member(#{value => 5}, Tuples)) + ]. + +test_rationals_generator(DB) -> + %% Create rationals relation + {DB1, Rationals} = operations:create_infinite_relation(DB, #{ + name => rationals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, rationals} + }), + + %% Take first 10 rationals using constraints + Iterator = operations:get_tuples_iterator(DB1, rationals, #{}), + + %% Just get a few tuples to verify generator works + {ok, First} = operations:next_tuple(Iterator), + {ok, Second} = operations:next_tuple(Iterator), + operations:close_iterator(Iterator), + + [ + ?_assertEqual(aleph_zero, Rationals#relation.cardinality), + ?_assert(is_map(First)), + ?_assert(maps:is_key(numerator, First)), + ?_assert(maps:is_key(denominator, First)), + ?_assert(is_map(Second)) + ]. + +test_take_operator(DB) -> + %% Create naturals + {DB1, _} = operations:create_infinite_relation(DB, #{ + name => naturals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, naturals}, + constraints => #{value => {gte, 0}} + }), + + %% Take 100 naturals + {_DB2, Naturals100} = operations:take(DB1, naturals, 100), + + %% Verify result is finite + [ + ?_assertEqual({finite, 100}, Naturals100#relation.cardinality), + ?_assertEqual({take, naturals, 100}, Naturals100#relation.generator) + ]. + +test_finite_relation_cardinality(DB) -> + %% Create finite relation + {DB1, _} = operations:create_relation(DB, users, #{name => string, age => integer}), + + %% Add tuple + {DB2, UpdatedRel} = operations:create_tuple(DB1, users, #{name => "Alice", age => 30}), + + %% Cardinality should be 1 + [ + ?_assertEqual({finite, 1}, UpdatedRel#relation.cardinality) + ]. diff --git a/test/query_pipeline_test.erl b/test/query_pipeline_test.erl new file mode 100644 index 0000000..389ff7c --- /dev/null +++ b/test/query_pipeline_test.erl @@ -0,0 +1,190 @@ +-module(query_pipeline_test). +-include_lib("eunit/include/eunit.hrl"). +-include("operations.hrl"). + +%%% Test Suite for Query Pipeline (Volcano Iterator Model) + +query_pipeline_test_() -> + {foreach, + fun setup/0, + fun cleanup/1, + [ + fun test_select_iterator/1, + fun test_project_iterator/1, + fun test_take_iterator/1, + fun test_sort_iterator/1, + fun test_composed_pipeline/1, + fun test_materialize_finite/1, + fun test_materialize_infinite/1, + fun test_complete_query_pipeline/1 + ]}. + +%%% Setup and Cleanup + +setup() -> + operations:setup(), + DB = operations:create_database(test_db), + + %% Create employees relation with test data + {DB1, _} = operations:create_relation(DB, employees, #{ + name => string, + age => integer, + department => string + }), + + {DB2, _} = operations:create_tuple(DB1, employees, #{name => "Alice", age => 35, department => "Engineering"}), + {DB3, _} = operations:create_tuple(DB2, employees, #{name => "Bob", age => 28, department => "Sales"}), + {DB4, _} = operations:create_tuple(DB3, employees, #{name => "Carol", age => 42, department => "Engineering"}), + {DB5, _} = operations:create_tuple(DB4, employees, #{name => "Dave", age => 31, department => "Marketing"}), + {DB6, _} = operations:create_tuple(DB5, employees, #{name => "Eve", age => 29, department => "Engineering"}), + + DB6. + +cleanup(_DB) -> + ok. + +%%% Tests + +test_select_iterator(DB) -> + %% Filter employees age > 30 + BaseIter = operations:get_tuples_iterator(DB, employees, #{}), + FilteredIter = operations:select_iterator(BaseIter, + fun(E) -> maps:get(age, E) > 30 end), + Results = operations:collect_all(FilteredIter), + + %% Should get 3 employees: Alice (35), Carol (42), Dave (31) + [ + ?_assertEqual(3, length(Results)), + ?_assert(lists:all(fun(E) -> maps:get(age, E) > 30 end, Results)) + ]. + +test_project_iterator(DB) -> + %% Project to [name, age] only + BaseIter = operations:get_tuples_iterator(DB, employees, #{}), + ProjectedIter = operations:project_iterator(BaseIter, [name, age]), + Results = operations:collect_all(ProjectedIter), + + %% Should have only name and age fields + [ + ?_assertEqual(5, length(Results)), + ?_assert(lists:all(fun(E) -> + maps:is_key(name, E) andalso + maps:is_key(age, E) andalso + not maps:is_key(department, E) + end, Results)) + ]. + +test_take_iterator(DB) -> + %% Take first 3 employees + BaseIter = operations:get_tuples_iterator(DB, employees, #{}), + LimitedIter = operations:take_iterator(BaseIter, 3), + Results = operations:collect_all(LimitedIter), + + [ + ?_assertEqual(3, length(Results)) + ]. + +test_sort_iterator(DB) -> + %% Sort by age ascending + BaseIter = operations:get_tuples_iterator(DB, employees, #{}), + SortedIter = operations:sort_iterator(BaseIter, + fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end), + Results = operations:collect_all(SortedIter), + + Ages = [maps:get(age, E) || E <- Results], + + [ + ?_assertEqual(5, length(Results)), + ?_assertEqual([28, 29, 31, 35, 42], Ages) + ]. + +test_composed_pipeline(DB) -> + %% Complex pipeline: filter age > 30, sort by age, take 2, project [name] + Iter1 = operations:get_tuples_iterator(DB, employees, #{}), + Iter2 = operations:select_iterator(Iter1, fun(E) -> maps:get(age, E) > 30 end), + Iter3 = operations:sort_iterator(Iter2, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end), + Iter4 = operations:take_iterator(Iter3, 2), + Pipeline = operations:project_iterator(Iter4, [name]), + + Results = operations:collect_all(Pipeline), + + %% Should get 2 oldest employees over 30: Dave (31), Alice (35) + Names = [maps:get(name, R) || R <- Results], + + [ + ?_assertEqual(2, length(Results)), + ?_assertEqual(["Dave", "Alice"], Names), + ?_assert(lists:all(fun(R) -> not maps:is_key(age, R) end, Results)) + ]. + +test_materialize_finite(DB) -> + %% Build pipeline and materialize + Iter1 = operations:get_tuples_iterator(DB, employees, #{}), + Iter2 = operations:select_iterator(Iter1, fun(E) -> + maps:get(department, E) =:= "Engineering" + end), + Pipeline = operations:project_iterator(Iter2, [name, age]), + + {DB1, EngineersRel} = operations:materialize(DB, Pipeline, engineers), + + %% Verify new relation + [ + ?_assert(is_record(EngineersRel, relation)), + ?_assertEqual(engineers, EngineersRel#relation.name), + ?_assertEqual({finite, 3}, EngineersRel#relation.cardinality), + + %% Can query the materialized relation + ?_assertMatch([_,_,_], + operations:collect_all(operations:get_tuples_iterator(DB1, engineers, #{}))) + ]. + +test_materialize_infinite(DB) -> + %% Create infinite naturals + {DB1, _} = operations:create_infinite_relation(DB, #{ + name => naturals, + schema => #{}, + cardinality => aleph_zero, + generator => {primitive, naturals}, + constraints => #{value => {gte, 0}} + }), + + %% Take 100 and materialize + Pipeline = operations:get_tuples_iterator(DB1, naturals, #{value => {range, 0, 99}}), + {_DB2, Naturals100} = operations:materialize(DB1, Pipeline, naturals_100), + + [ + ?_assertEqual({finite, 100}, Naturals100#relation.cardinality), + ?_assertEqual(naturals_100, Naturals100#relation.name) + ]. + +test_complete_query_pipeline(DB) -> + %% Realistic query: + %% SELECT name, age FROM employees + %% WHERE age > 28 + %% ORDER BY age DESC + %% LIMIT 3 + + Iter1 = operations:get_tuples_iterator(DB, employees, #{}), + Iter2 = operations:select_iterator(Iter1, fun(E) -> maps:get(age, E) > 28 end), + Iter3 = operations:sort_iterator(Iter2, fun(A, B) -> + maps:get(age, A) >= maps:get(age, B) % DESC + end), + Iter4 = operations:take_iterator(Iter3, 3), + Pipeline = operations:project_iterator(Iter4, [name, age]), + + {DB1, TopEmployees} = operations:materialize(DB, Pipeline, top_3_employees), + + %% Verify result - NOTE: Relations are unordered sets! + %% After materialization, tuples come back in hash order, not sort order + Results = operations:collect_all(operations:get_tuples_iterator(DB1, top_3_employees, #{})), + Ages = lists:sort(fun(A, B) -> A >= B end, [maps:get(age, R) || R <- Results]), + + [ + ?_assertEqual(3, length(Results)), + ?_assertEqual([42, 35, 31], Ages), % Verify we have the right ages (sorted DESC for check) + ?_assert(lists:all(fun(R) -> + Age = maps:get(age, R), + lists:member(Age, [42, 35, 31]) + end, Results)), + ?_assertEqual({finite, 3}, TopEmployees#relation.cardinality) + ]. -- cgit v1.2.3