diff options
Diffstat (limited to '')
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | include/operations.hrl | 24 | ||||
| -rw-r--r-- | rebar-deps.nix | 10 | ||||
| -rw-r--r-- | rebar.config | 19 | ||||
| -rw-r--r-- | rebar.lock | 12 | ||||
| -rw-r--r-- | src/main.erl | 60 | ||||
| -rw-r--r-- | src/operations.erl | 593 | ||||
| -rw-r--r-- | src/query_planner.erl | 356 | ||||
| -rw-r--r-- | src/relational_operators.erl | 366 | ||||
| -rw-r--r-- | src/repl.erl | 49 | ||||
| -rw-r--r-- | src/xml_server.erl | 9 | ||||
| -rw-r--r-- | src/xml_server_app.erl | 2 | ||||
| -rw-r--r-- | test/function_relations_test.erl | 347 | ||||
| -rw-r--r-- | test/infinite_relations_test.erl | 128 | ||||
| -rw-r--r-- | test/join_test.erl | 273 | ||||
| -rw-r--r-- | test/operations_test.erl | 366 | ||||
| -rw-r--r-- | test/provenance_test.erl | 420 | ||||
| -rw-r--r-- | test/query_pipeline_test.erl | 183 |
18 files changed, 924 insertions, 2294 deletions
@@ -1,3 +1,4 @@ +.direnv _build Mnesia.* diff --git a/include/operations.hrl b/include/operations.hrl index b027bb0..dcaa287 100644 --- a/include/operations.hrl +++ b/include/operations.hrl @@ -11,15 +11,15 @@ cardinality, % {finite, N} | aleph_zero | continuum generator, % Generator function (immutable only), undefined for tree-based membership_criteria, % #{attribute_name => constraint_spec()} - domain membership test - mutability, % mutable | immutable - provenance % Provenance tracking for updatable views (future) + provenance, % attribute_provenance() - maps attribute to source relation + lineage % lineage_op() - operation tree showing derivation }). -record(tuple, {hash, relation, attribute_map}). -record(attribute, {hash, value}). %% Specification record for creating immutable relations --record(immutable_relation_spec, { +-record(domain, { name, % Atom - relation name schema, % #{attribute_name => relation_name} generator, % {module, function} - tuple generator @@ -33,11 +33,6 @@ | aleph_zero % Countably infinite (ℵ₀) | continuum. % Uncountably infinite (2^ℵ₀) -%%% Mutability Types - --type mutability() :: mutable % Supports insert/delete (tree-based) - | immutable. % Read-only (generator-based or protected) - %%% Constraint Types -type constraint_spec() :: @@ -108,16 +103,3 @@ | {take, pos_integer(), lineage_op()} % Limit operation | {aggregate, atom(), atom(), lineage_op()}. % Aggregation (future) -%% Tuple metadata (contains provenance, lineage, and other system-managed fields) --type tuple_metadata() :: #{ - provenance => attribute_provenance(), - lineage => lineage_op() - % Future: timestamp, version, etc. -}. - -%% Tuples with metadata use a nested 'meta' field: -%% #{id => 1, name => "Alice", -%% meta => #{ -%% provenance => #{id => {employees, id}, name => {employees, name}}, -%% lineage => {select, fun(T) -> maps:get(age, T) > 30 end, {base, employees}} -%% }} diff --git a/rebar-deps.nix b/rebar-deps.nix index 178f889..5e167a7 100644 --- a/rebar-deps.nix +++ b/rebar-deps.nix @@ -14,5 +14,15 @@ let }; beamDeps = [ ]; }; + uuid_erl = builder { + name = "uuid_erl"; + version = "2.0.7"; + src = fetchHex { + pkg = "uuid_erl"; + version = "2.0.7"; + sha256 = "sha256-Tkxco0YdxHxeFX7UKqOYGgU7ehhnkq+XKiexSpSJMk4="; + }; + beamDeps = [ ]; + }; }; in self diff --git a/rebar.config b/rebar.config index 8f364e6..b419da1 100644 --- a/rebar.config +++ b/rebar.config @@ -9,8 +9,9 @@ %% == Dependencies and Plugins == {deps, [ - {merklet, "2.0.0"}] -}. + {merklet, "2.0.0"}, + {uuid_erl, "2.0.7"} +]}. {plugins, [ {covertool, "2.0.7"}, @@ -23,7 +24,8 @@ %% == Releases == {relx, [ {release, {domino, "0.1.0"}, [ - merklet + merklet, + uuid_erl ]}, {mode, dev}, @@ -80,17 +82,10 @@ %% == Dialyzer Settings == {dialyzer, [ - {plt_extra_apps, [merklet]}, + {plt_extra_apps, [merklet, uuid_erl, quickrand]}, {warnings, [unknown]}, {exclude_mods, [ - query_planner_test, - repl_comprehensive_test, - function_relations_test, - infinite_relations_test, - join_test, - operations_test, - provenance_test, - query_pipeline_test + ]} ]}. @@ -1,8 +1,14 @@ {"1.2.0", -[{<<"merklet">>,{pkg,<<"merklet">>,<<"2.0.0">>},0}]}. +[{<<"merklet">>,{pkg,<<"merklet">>,<<"2.0.0">>},0}, + {<<"quickrand">>,{pkg,<<"quickrand">>,<<"2.0.7">>},1}, + {<<"uuid_erl">>,{pkg,<<"uuid_erl">>,<<"2.0.7">>},0}]}. [ {pkg_hash,[ - {<<"merklet">>, <<"9E53AA5F83B4CE33A8EE0BEDC798AA54A1750A8FD92D649FC04BA7F7B8E65E78">>}]}, + {<<"merklet">>, <<"9E53AA5F83B4CE33A8EE0BEDC798AA54A1750A8FD92D649FC04BA7F7B8E65E78">>}, + {<<"quickrand">>, <<"D2BD76676A446E6A058D678444B7FDA1387B813710D1AF6D6E29BB92186C8820">>}, + {<<"uuid_erl">>, <<"B2078D2CC814F53AFA52D36C91E08962C7E7373585C623F4C0EA6DFB04B2AF94">>}]}, {pkg_hash_ext,[ - {<<"merklet">>, <<"B5E868DA5979F9B3C3E4E8B8171AA5C167868E35495B81731C93D8382FDD3278">>}]} + {<<"merklet">>, <<"B5E868DA5979F9B3C3E4E8B8171AA5C167868E35495B81731C93D8382FDD3278">>}, + {<<"quickrand">>, <<"B8ACBF89A224BC217C3070CA8BEBC6EB236DBE7F9767993B274084EA044D35F0">>}, + {<<"uuid_erl">>, <<"4E4C5CA3461DC47C5E157ED42AA3981A053B7A186792AF972A27B14A9489324E">>}]} ]. diff --git a/src/main.erl b/src/main.erl index 5b8d6e3..d2fe0a7 100644 --- a/src/main.erl +++ b/src/main.erl @@ -1,7 +1,54 @@ -module(main). -behaviour(application). --export([start/2, stop/1]). +-export([start/2, stop/1, setup/0]). + +%% @doc Initialize Mnesia database schema and tables. +%% +%% Creates a fresh Mnesia schema with four tables for content-addressed storage: +%% <ul> +%% <li>`attribute' - Hash → Value mapping for deduplication</li> +%% <li>`tuple' - Hash → Tuple mapping with attribute references</li> +%% <li>`relation' - Hash → Relation with merkle tree and schema</li> +%% <li>`database_state' - Hash → Database with relation merkle tree</li> +%% </ul> +%% +%% <b>Warning:</b> This function deletes any existing schema and recreates it from scratch. +%% +%% @returns `ok' on success +%% @see operations:create_database/1 +setup() -> + mnesia:stop(), + mnesia:delete_schema([node()]), + mnesia:create_schema([node()]), + mnesia:start(), + mnesia:create_table(attribute, [ + {attributes, [hash, value]}, + {disc_copies, [node()]}, + {type, set} + ]), + mnesia:create_table(tuple, [ + {attributes, [hash, relation, attribute_map]}, + {disc_copies, [node()]}, + {type, set} + ]), + mnesia:create_table(relation, [ + {attributes, [hash, name, tree, schema, constraints, cardinality, generator, membership_criteria, mutability, provenance, lineage]}, + {disc_copies, [node()]}, + {type, set}, + {index, [name]} % Index on name for efficient lookup + ]), + mnesia:create_table(database_state, [ + {attributes, [hash, name, tree, relations, timestamp]}, + {disc_copies, [node()]}, + {type, set} + ]). + +uuid() -> + ok = application:load(quickrand), + ok = quickrand:seed(), + ok = quickrand_cache:init(), + quickrand_cache:new(). start(_StartType, _StartArgs) -> %% Start Mnesia (or other children) here @@ -9,18 +56,11 @@ start(_StartType, _StartArgs) -> %% Ensure Mnesia is started mnesia:start(), + setup(), + _ = uuid(), {ok, self()}. stop(_State) -> io:format("Stopping app...~n"), ok. - -%% setup() -> -%% mnesia:create_table(attributes, [{type, set}, -%% {attributes, [name, value, type]}, -%% {ram_copies, [node()]}, -%% {index, [name]} -%% ]). - - diff --git a/src/operations.erl b/src/operations.erl index 4a492f4..e224800 100644 --- a/src/operations.erl +++ b/src/operations.erl @@ -38,25 +38,24 @@ %%% @reference E. F. Codd (1970). "A Relational Model of Data for Large Shared Data Banks" -module(operations). --include("operations.hrl"). --export([setup/0, - hash/1, - create_database/1, +-include("../include/operations.hrl"). +-export([ + create_database/1, create_relation/3, create_immutable_relation/2, create_tuple/3, + create_all_tuples/3, retract_tuple/3, retract_tuple/4, clear_relation/2, clear_relation/3, retract_relation/2, retract_relation/3, - get_relations/1, - get_relation_hash/2, - hashes_from_tuple/1, - get_tuples_iterator/2, - get_tuples_iterator/3, - take/3, + get_relation_hash/2, + get_relations/1, + hashes_from_tuple/1, + get_tuples_iterator/2, + get_iterator_from_generator/2, next_tuple/1, close_iterator/1, collect_all/1, @@ -69,48 +68,10 @@ equijoin_iterator/3, theta_join_iterator/3, %% Materialization (eager) - materialize/3]). - -%% @doc Initialize Mnesia database schema and tables. -%% -%% Creates a fresh Mnesia schema with four tables for content-addressed storage: -%% <ul> -%% <li>`attribute' - Hash → Value mapping for deduplication</li> -%% <li>`tuple' - Hash → Tuple mapping with attribute references</li> -%% <li>`relation' - Hash → Relation with merkle tree and schema</li> -%% <li>`database_state' - Hash → Database with relation merkle tree</li> -%% </ul> -%% -%% <b>Warning:</b> This function deletes any existing schema and recreates it from scratch. -%% -%% @returns `ok' on success -%% @see create_database/1 -setup() -> - mnesia:stop(), - mnesia:delete_schema([node()]), - mnesia:create_schema([node()]), - mnesia:start(), - mnesia:create_table(attribute, [ - {attributes, [hash, value]}, - {disc_copies, [node()]}, - {type, set} - ]), - mnesia:create_table(tuple, [ - {attributes, [hash, relation, attribute_map]}, - {disc_copies, [node()]}, - {type, set} - ]), - mnesia:create_table(relation, [ - {attributes, [hash, name, tree, schema, constraints, cardinality, generator, membership_criteria, mutability, provenance]}, - {disc_copies, [node()]}, - {type, set} - ]), - mnesia:create_table(database_state, [ - {attributes, [hash, name, tree, relations, timestamp]}, - {disc_copies, [node()]}, - {type, set} - ]). + materialize/3 +]). +%% @private %% @doc Compute SHA-256 hash of an Erlang term. %% %% This is the foundational hashing function used throughout the system for @@ -157,18 +118,10 @@ create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Databa %% Check if relation is immutable before attempting insert CurrentRelationHash = maps:get(RelationName, Database#database_state.relations), [RelationRecord] = mnesia:dirty_read(relation, CurrentRelationHash), + create_tuple_internal(Database, RelationName, Tuple, RelationRecord). - case RelationRecord#relation.mutability of - immutable -> - {error, {immutable_relation, RelationName}}; - mutable -> - create_tuple_internal(Database, RelationName, Tuple, RelationRecord); - undefined -> - %% Backwards compatibility: treat undefined as mutable - create_tuple_internal(Database, RelationName, Tuple, RelationRecord) - end. - -%% Internal function for tuple creation (after mutability check) +%% @private +%% Internal function for tuple creation create_tuple_internal(Database, RelationName, Tuple, _RelationRecord) -> F = fun() -> %% Step 1: Store each attribute value and build attribute_map @@ -212,8 +165,13 @@ create_tuple_internal(Database, RelationName, Tuple, _RelationRecord) -> constraints = RelationRecord#relation.constraints, cardinality = NewCardinality, generator = RelationRecord#relation.generator, - provenance = RelationRecord#relation.provenance + provenance = RelationRecord#relation.provenance, + lineage = RelationRecord#relation.lineage, + membership_criteria = RelationRecord#relation.membership_criteria }, + %% Delete old relation record before writing new one + %% This ensures only one relation record exists per name + mnesia:delete({relation, CurrentRelationHash}), mnesia:write(relation, UpdatedRelation, write), %% Step 7: Update database relations map @@ -423,6 +381,20 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st %% Two relations might share definitions but their name gives another interpretation %% and therefore different tuples RelationHash = hash({Name, Definition, undefined}), + + %% Returns a generator function (not a PID) that yields tuples one at a time + %% TODO: investigate if a generator should or should not be bound to a specific DATABASE VERSION. If so, create the fun passing the DB as an attribute + GeneratorFun = fun() -> + [CurrentRelation] = mnesia:dirty_index_read(relation, Name, #relation.name), + CurrentHash = CurrentRelation#relation.hash, + TupleHashes = case CurrentRelation#relation.tree of + undefined -> []; + _ -> hashes_from_tuple(CurrentHash) + end, + InnerGen = make_finite_generator(TupleHashes), + spawn(fun() -> generator_iterator_loop(InnerGen) end) + end, + NewRelation = #relation{ hash = RelationHash, name = Name, @@ -430,10 +402,10 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st schema = Definition, constraints = #{}, % No constraints by default cardinality = {finite, 0}, % Empty relation - generator = undefined, % Finite relation has no generator + generator = GeneratorFun, % Function generator for finite relations membership_criteria = #{}, % No membership criteria by default - mutability = mutable, % Mutable by default - provenance = {base, Name} % Base relation + provenance = build_base_provenance(Definition, Name), % Base relation provenance + lineage = {base, Name} % Base relation lineage }, mnesia:write(relation, NewRelation, write), @@ -494,42 +466,42 @@ create_database(Name) -> %% Standard immutable relations (domains and their predicates) StandardTypeRelations = [ %% Boolean domain - finite, immutable - #immutable_relation_spec{ + #domain{ name = boolean, schema = #{value => boolean}, - generator = {generators, boolean}, + generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:boolean(#{})) end) end, membership_criteria = #{value => {in, [true, false]}}, cardinality = {finite, 2} }, %% Natural numbers - infinite, immutable - #immutable_relation_spec{ + #domain{ name = natural, schema = #{value => natural}, - generator = {generators, natural}, + generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:natural(#{})) end) end, membership_criteria = #{value => {'and', {gte, 0}, is_integer}}, cardinality = aleph_zero }, %% Integers - infinite, immutable - #immutable_relation_spec{ + #domain{ name = integer, schema = #{value => integer}, - generator = {generators, integer}, + generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:integer(#{})) end) end, membership_criteria = #{value => is_integer}, cardinality = aleph_zero }, %% Rationals - infinite, immutable - #immutable_relation_spec{ + #domain{ name = rational, schema = #{numerator => integer, denominator => integer}, - generator = {generators, rational}, + generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:rational(#{})) end) end, membership_criteria = #{denominator => {neq, 0}}, cardinality = aleph_zero } %% Reals - TODO: implement - %% #immutable_relation_spec{ + %% #domain{ %% name = reals, %% schema = #{value => reals}, - %% generator = {generators, reals}, + %% generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:reals(#{})) end) end, %% membership_criteria = #{value => is_float}, %% cardinality = continuum %% } @@ -561,7 +533,7 @@ create_database(Name) -> %% == Example == %% <pre> %% %% Create immutable relation of natural numbers -%% {DB1, Naturals} = operations:create_immutable_relation(DB, #immutable_relation_spec{ +%% {DB1, Naturals} = operations:create_immutable_relation(DB, #domain{ %% name = naturals, %% schema = #{value => naturals}, %% generator = {generators, naturals}, @@ -575,19 +547,19 @@ create_database(Name) -> %% </pre> %% %% @param Database `#database_state{}' record -%% @param Specification `#immutable_relation_spec{}' record +%% @param Specification `#domain{}' record %% @returns `{UpdatedDatabase, NewRelation}' %% %% @see create_relation/3 %% @see get_tuples_iterator/3 create_immutable_relation(Database, Specification) when is_record(Database, database_state) - andalso is_record(Specification, immutable_relation_spec) -> - Name = Specification#immutable_relation_spec.name, - Schema = Specification#immutable_relation_spec.schema, - Generator = Specification#immutable_relation_spec.generator, - MembershipCriteria = Specification#immutable_relation_spec.membership_criteria, - Cardinality = Specification#immutable_relation_spec.cardinality, + andalso is_record(Specification, domain) -> + Name = Specification#domain.name, + Schema = Specification#domain.schema, + Generator = Specification#domain.generator, + MembershipCriteria = Specification#domain.membership_criteria, + Cardinality = Specification#domain.cardinality, F = fun() -> RelationHash = hash({Name, Schema, undefined}), @@ -601,8 +573,8 @@ create_immutable_relation(Database, Specification) cardinality = Cardinality, generator = Generator, membership_criteria = MembershipCriteria, - mutability = immutable, % Always immutable - provenance = {base, Name} + provenance = build_base_provenance(Schema, Name), % Base relation provenance + lineage = {base, Name} % Base relation lineage }, mnesia:write(relation, NewRelation, write), @@ -627,19 +599,6 @@ create_immutable_relation(Database, Specification) {atomic, Result} = mnesia:transaction(F), Result. -%% @doc Get all relation names in a database. -%% -%% Returns a list of atoms representing all relation names currently -%% defined in the database. -%% -%% @param Database `#database_state{}' record -%% @returns List of atoms (relation names) -%% -%% @see get_relation_hash/2 -%% @see create_relation/3 -get_relations(Database) -> - maps:keys(Database#database_state.relations). - %% @doc Get relation hash by name. %% %% Looks up a relation's hash in the database's relation map. This hash @@ -657,6 +616,17 @@ get_relation_hash(Database, RelationName) -> X -> X end. +%% @doc Get list of all relation names in the database. +%% +%% Returns a list of all relation names (atoms) currently stored in the database. +%% This includes both user-defined relations and built-in infinite relations. +%% +%% @param Database `#database_state{}' record +%% @returns List of relation names (atoms) +-spec get_relations(#database_state{}) -> [atom()]. +get_relations(Database) -> + maps:keys(Database#database_state.relations). + %% @doc Resolve a tuple hash to actual values. %% %% This is an internal function that materializes a tuple by: @@ -699,75 +669,6 @@ 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 == -%% <pre> -%% %% 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). -%% </pre> -%% -%% @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)), - - TakeHash = hash({take, RelationName, N}), - - TakeRelation = #relation{ - hash = TakeHash, - name = TakeName, - tree = undefined, % Generated on-demand - schema = SourceRelation#relation.schema, - constraints = SourceRelation#relation.constraints, - cardinality = ResultCardinality, - generator = {take, RelationName, N}, - membership_criteria = #{}, - mutability = immutable, % Take relations are read-only - provenance = {take, SourceRelation#relation.provenance, N} - }, - - %% Register the take relation (ephemeral - not persisted to Mnesia disk) - %% This allows get_tuples_iterator to find it - UpdatedDatabase = Database#database_state{ - relations = maps:put(TakeName, TakeHash, Database#database_state.relations) - }, - - %% Store in Mnesia (in-memory transaction) - mnesia:dirty_write(relation, TakeRelation), - - {UpdatedDatabase, 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. @@ -818,83 +719,32 @@ take(Database, RelationName, N) when is_record(Database, database_state), is_int %% %% @param Database `#database_state{}' record %% @param RelationName Atom naming the relation to iterate -%% @param Options Map of constraints (nested or flat format) %% @returns Pid of iterator process %% %% @see get_tuples_iterator/2 %% @see take/3 -get_tuples_iterator(Database, RelationName, Options) when is_record(Database, database_state) -> +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}); + erlang:error({error_tuple_iterator_init, relation_not_found, RelationName}); RelationHash -> [Relation] = mnesia:dirty_read(relation, RelationHash), - - %% Extract constraints from options (support both nested and flat format) - Constraints = case maps:is_key(constraints, Options) of - true -> maps:get(constraints, Options); - false -> Options %% Flat format: entire map is constraints - end, - - %% Metadata tracking is ALWAYS enabled case Relation#relation.cardinality of {finite, _} when Relation#relation.tree =/= undefined -> - %% Finite relation with materialized tuples: use tuple hashes TupleHashes = hashes_from_tuple(RelationHash), - spawn(fun() -> tuple_iterator_loop(TupleHashes, RelationName, true) end); - + spawn(fun() -> tuple_iterator_loop(TupleHashes) end); _ -> - %% Relation with generator (infinite or take) or empty finite relation - case Relation#relation.generator of - undefined -> - %% Empty finite relation without materialized tuples - spawn(fun() -> tuple_iterator_loop([], RelationName, true) end); - - {take, SourceRelName, N} -> - %% Take relation: get source iterator and limit to N tuples - SourceIter = get_tuples_iterator(Database, SourceRelName, Constraints), - spawn(fun() -> take_iter_loop(SourceIter, N, 0, N) end); - - {GeneratorModule, GeneratorFunction} -> - %% Normal generator (naturals, integers, etc.) - Generator = erlang:apply(GeneratorModule, GeneratorFunction, [Constraints]), - spawn(fun() -> generator_iterator_loop(Generator, RelationName, true) end) - end + get_iterator_from_generator(Relation#relation.name, Relation#relation.generator) end end. -%% @doc Create an iterator for streaming tuples from a relation. -%% -%% Implements the Volcano Iterator Model: spawns an independent process that -%% lazily streams tuples from the relation. This enables: -%% <ul> -%% <li>Memory-bounded queries (tuples materialized on demand)</li> -%% <li>Composable query operators (future: select, project, join)</li> -%% <li>Process-based concurrency</li> -%% </ul> -%% -%% 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 == -%% <pre> -%% Iterator = operations:get_tuples_iterator(DB, users), -%% {ok, Tuple} = operations:next_tuple(Iterator), -%% operations:close_iterator(Iterator). -%% </pre> -%% -%% @param Database `#database_state{}' record -%% @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) -> - get_tuples_iterator(Database, RelationName, #{}). +%% @doc Get an iterator out of a generator. +get_iterator_from_generator(RelationName, GeneratorFun) -> + case GeneratorFun of + undefined -> spawn(fun() -> tuple_iterator_loop([]) end); + Generator when is_function(Generator) -> Generator(); + _ -> erlang:error({error_tuple_iterator_init, non_function_generator, RelationName}) + end. %% @doc Get next tuple from iterator. %% @@ -946,24 +796,20 @@ close_iterator(IteratorPid) -> %% </ul> %% %% @param TupleHashes List of binary tuple hashes to stream -%% @param RelationName Name of the source relation (for provenance) -%% @param EnableProvenance Boolean flag to enable provenance tracking -tuple_iterator_loop([], _RelationName, _EnableProvenance) -> +tuple_iterator_loop([]) -> receive {next, Caller} -> Caller ! done; stop -> ok end; -tuple_iterator_loop([TupleHash | Rest], RelationName, EnableProvenance) -> +tuple_iterator_loop([TupleHash | Rest]) -> receive {next, Caller} -> %% Resolve tuple on demand ResolvedTuple = resolve_tuple(TupleHash), - %% Add provenance tracking (always enabled) - FinalTuple = add_base_provenance(ResolvedTuple, RelationName), - Caller ! {tuple, FinalTuple}, - tuple_iterator_loop(Rest, RelationName, EnableProvenance); + Caller ! {tuple, ResolvedTuple}, + tuple_iterator_loop(Rest); stop -> ok end. @@ -1003,10 +849,6 @@ collect_all(IteratorPid, 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 @@ -1032,12 +874,9 @@ select_loop(ChildPid, Predicate) -> {ok, Tuple} -> case Predicate(Tuple) of true -> - %% Wrap lineage with select operation - TupleWithLineage = wrap_lineage(Tuple, {select, Predicate}), - Caller ! {tuple, TupleWithLineage}, + Caller ! {tuple, Tuple}, select_loop(ChildPid, Predicate); false -> - %% Skip this tuple, get next self() ! {next, Caller}, select_loop(ChildPid, Predicate) end; @@ -1076,30 +915,9 @@ project_loop(ChildPid, Attributes) -> {next, Caller} -> case next_tuple(ChildPid) of {ok, Tuple} -> - % Project data attributes + % Project data attributes only - no metadata handling ProjectedTuple = maps:with(Attributes, Tuple), - - % Preserve and update metadata - case maps:get(meta, Tuple, undefined) of - undefined -> - % No metadata, just return projected tuple - Caller ! {tuple, ProjectedTuple}; - Meta -> - % Filter provenance to only projected attributes - OldProv = maps:get(provenance, Meta, #{}), - NewProv = maps:with(Attributes, OldProv), - - % Build new metadata - UpdatedMeta = case NewProv of - Empty when map_size(Empty) =:= 0 -> maps:remove(provenance, Meta); - _ -> maps:put(provenance, NewProv, Meta) - end, - - % Add metadata back and wrap lineage - TupleWithMeta = maps:put(meta, UpdatedMeta, ProjectedTuple), - TupleWithLineage = wrap_lineage(TupleWithMeta, {project, Attributes}), - Caller ! {tuple, TupleWithLineage} - end, + Caller ! {tuple, ProjectedTuple}, project_loop(ChildPid, Attributes); done -> close_iterator(ChildPid), @@ -1135,17 +953,11 @@ project_loop(ChildPid, Attributes) -> %% @returns Iterator process (Pid) sort_iterator(ChildIterator, CompareFun) when is_function(CompareFun, 2) -> spawn(fun() -> - %% Phase 1: Consume all tuples (blocking!) + %% Sync all state blocking the pipeline AllTuples = collect_all(ChildIterator), - - %% Phase 2: Sort in memory + %% Sort in memory SortedTuples = lists:sort(CompareFun, AllTuples), - - %% Phase 3: Wrap lineage for all tuples - TuplesWithLineage = [wrap_lineage(T, {sort, CompareFun}) || T <- SortedTuples], - - %% Phase 4: Emit sorted tuples on demand - sorted_emit_loop(TuplesWithLineage) + sorted_emit_loop(SortedTuples) end). sorted_emit_loop([]) -> @@ -1184,9 +996,8 @@ take_iter_loop(ChildPid, Limit, Count, OriginalN) when Count < Limit -> {next, Caller} -> case next_tuple(ChildPid) of {ok, Tuple} -> - %% Wrap lineage with take operation - TupleWithLineage = wrap_lineage(Tuple, {take, OriginalN}), - Caller ! {tuple, TupleWithLineage}, + %% Pass through tuple without metadata injection + Caller ! {tuple, Tuple}, take_iter_loop(ChildPid, Limit, Count + 1, OriginalN); done -> close_iterator(ChildPid), @@ -1305,7 +1116,7 @@ materialize(Database, SourceIterator, ResultName) when is_record(Database, datab {DB1, _Relation} = create_relation(Database, ResultName, Schema), %% 4. Insert all tuples - {FinalDB, FinalRelation} = insert_all_tuples(DB1, ResultName, AllTuples), + {FinalDB, FinalRelation} = create_all_tuples(DB1, ResultName, AllTuples), {FinalDB, FinalRelation} end. @@ -1327,7 +1138,7 @@ infer_type(_) -> term. %% @private %% Insert multiple tuples into a relation. -insert_all_tuples(DB, RelationName, Tuples) -> +create_all_tuples(DB, RelationName, Tuples) -> lists:foldl( fun(Tuple, {DBacc, _RelAcc}) -> create_tuple(DBacc, RelationName, Tuple) @@ -1340,51 +1151,20 @@ insert_all_tuples(DB, RelationName, Tuples) -> %%% Generator Support Functions %%% ============================================================================ -%% Instantiate a generator from a generator specification (commented out). -%% 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 %% Generator iterator loop for infinite relations. %% Similar to tuple_iterator_loop but works with generator functions instead %% of tuple hashes. -generator_iterator_loop(Generator, RelationName, EnableProvenance) -> +generator_iterator_loop(Generator) -> receive {next, Caller} -> case Generator(next) of done -> Caller ! done; - {value, Tuple, NextGen} -> - %% Add provenance tracking (always enabled) - FinalTuple = add_base_provenance(Tuple, RelationName), - Caller ! {tuple, FinalTuple}, - generator_iterator_loop(NextGen, RelationName, EnableProvenance); + {value, Tuple, NextGenerator} -> + Caller ! {tuple, Tuple}, + generator_iterator_loop(NextGenerator); {error, Reason} -> Caller ! {error, Reason} end; @@ -1423,7 +1203,7 @@ equijoin_emit_loop(LeftIter, RightTuples, JoinAttr) -> equijoin_emit_loop(LeftIter, RightTuples, JoinAttr); LeftValue -> % Find matching right tuples - Matches = [merge_tuples(LeftTuple, RightTuple, {equijoin, JoinAttr}) + Matches = [merge_tuples(LeftTuple, RightTuple) || RightTuple <- RightTuples, maps:get(JoinAttr, RightTuple, undefined) =:= LeftValue], case Matches of @@ -1478,7 +1258,7 @@ theta_join_emit_loop(LeftIter, RightTuples, Pred) -> Caller ! done; {ok, LeftTuple} -> % Find all right tuples that satisfy predicate - Matches = [merge_tuples(LeftTuple, RightTuple, {theta_join, Pred}) + Matches = [merge_tuples(LeftTuple, RightTuple) || RightTuple <- RightTuples, Pred(LeftTuple, RightTuple)], case Matches of @@ -1512,133 +1292,64 @@ theta_join_emit_buffered(LeftIter, RightTuples, Pred, []) -> theta_join_emit_loop(LeftIter, RightTuples, Pred). %% @private -%% Wrap existing lineage with a new operation. -%% Takes a tuple with optional lineage and wraps it with a new operation node. -%% If the tuple has no lineage, does nothing. -%% -%% @param Tuple Tuple potentially with meta.lineage -%% @param OpInfo Operation info: {select, Pred} | {project, Attrs} | {sort, Cmp} | {take, N} -wrap_lineage(Tuple, OpInfo) -> - case maps:get(meta, Tuple, undefined) of - undefined -> - % No metadata, return as-is - Tuple; - Meta -> - case maps:get(lineage, Meta, undefined) of +%% @doc Simple tuple merge for joins +%% Equally named and typed attributes are not repeated. +%% +%% @param LeftTuple Left side tuple +%% @param RightTuple Right side tuple +merge_tuples(LeftTuple, RightTuple) -> + maps:fold( + fun(RightKey, RightValue, LeftTupleAcc) -> + case maps:get(RightKey, LeftTupleAcc, undefined) of + LeftValue when LeftValue =:= RightValue -> + % Equal attributes, keep single value + LeftTupleAcc; undefined -> - % No lineage, return as-is - Tuple; - ChildLineage -> - % Wrap existing lineage with new operation - NewLineage = case OpInfo of - {select, Pred} -> {select, Pred, ChildLineage}; - {project, Attrs} -> {project, Attrs, ChildLineage}; - {sort, CmpFun} -> {sort, CmpFun, ChildLineage}; - {take, N} -> {take, N, ChildLineage} - end, - maps:put(meta, maps:put(lineage, NewLineage, Meta), Tuple) + % No conflict, add right attribute + maps:put(RightKey, RightValue, LeftTupleAcc); + _ -> + % Different attributes + maps:put(RightKey, RightValue, LeftTupleAcc) end - end. - -%% @private -%% Add base provenance and lineage to a tuple from a relation. -%% Creates nested meta fields with both provenance and lineage. -%% Example: add_base_provenance(#{id => 1, name => "Alice"}, employees) -%% => #{id => 1, name => "Alice", -%% meta => #{provenance => #{id => {employees, id}, name => {employees, name}}, -%% lineage => {base, employees}}} -add_base_provenance(Tuple, RelationName) -> - % Build provenance map for all attributes (excluding existing meta) - DataAttrs = maps:remove(meta, Tuple), - Provenance = maps:fold( - fun(Key, _Value, Acc) -> - maps:put(Key, {RelationName, Key}, Acc) end, - #{}, - DataAttrs - ), - % Add metadata with provenance and lineage - maps:put(meta, #{ - provenance => Provenance, - lineage => {base, RelationName} - }, Tuple). + LeftTuple, + RightTuple + ). %% @private -%% Merge two tuples for join result, including metadata. -%% If attribute names conflict, right side attributes are prefixed with "right_". -%% Metadata (including provenance and lineage) is also merged. -%% -%% @param LeftTuple Left side tuple -%% @param RightTuple Right side tuple -%% @param JoinInfo Join information: {equijoin, Attr} | {theta_join, Predicate} -merge_tuples(LeftTuple, RightTuple, JoinInfo) -> - % Extract metadata from both sides (if present) - LeftMeta = maps:get(meta, LeftTuple, #{}), - RightMeta = maps:get(meta, RightTuple, #{}), - - % Extract provenance and lineage from metadata - LeftProv = maps:get(provenance, LeftMeta, #{}), - RightProv = maps:get(provenance, RightMeta, #{}), - LeftLineage = maps:get(lineage, LeftMeta, undefined), - RightLineage = maps:get(lineage, RightMeta, undefined), - - % Remove metadata from tuples for data merging - LeftData = maps:remove(meta, LeftTuple), - RightData = maps:remove(meta, RightTuple), - - % Merge data attributes - MergedData = maps:fold( - fun(Key, Value, Acc) -> - case maps:is_key(Key, Acc) of - true -> - % Conflict - prefix right attribute - RightKey = list_to_atom("right_" ++ atom_to_list(Key)), - maps:put(RightKey, Value, Acc); - false -> - maps:put(Key, Value, Acc) - end - end, - LeftData, - RightData - ), - - % Merge provenance (same conflict resolution) - MergedProv = maps:fold( - fun(Key, Source, Acc) -> - case maps:is_key(Key, Acc) of - true -> - % Conflict - prefix right attribute provenance - RightKey = list_to_atom("right_" ++ atom_to_list(Key)), - maps:put(RightKey, Source, Acc); - false -> - maps:put(Key, Source, Acc) - end +%% Build base provenance mapping for a relation. +%% Maps each attribute to its source relation and attribute name. +%% +%% @param Schema Map of attribute names to types +%% @param RelationName Name of the source relation +%% @returns Provenance map #{attr => {relation, attr}} +build_base_provenance(Schema, RelationName) -> + maps:fold( + fun(AttrName, _Type, Acc) -> + maps:put(AttrName, {RelationName, AttrName}, Acc) end, - LeftProv, - RightProv - ), - - % Build merged lineage if both sides have lineage - MergedLineage = case {LeftLineage, RightLineage, JoinInfo} of - {undefined, undefined, _} -> undefined; - {L, R, {equijoin, Attr}} when L =/= undefined, R =/= undefined -> - {join, Attr, L, R}; - {L, R, {theta_join, Pred}} when L =/= undefined, R =/= undefined -> - {theta_join, Pred, L, R}; - _ -> undefined - end, + #{}, + Schema + ). - % Build merged metadata - MergedMeta = case {maps:size(MergedProv), MergedLineage} of - {0, undefined} -> #{}; - {0, Lineage} -> #{lineage => Lineage}; - {_, undefined} -> #{provenance => MergedProv}; - {_, Lineage} -> #{provenance => MergedProv, lineage => Lineage} - end, +%% The issue here is that the creation of a generator on the create_relation is wrong. +%% I assume it was because of the fun(Constraints), which I believe should receive an +%% optional database version, or just build from the current relation attributes as a factory. - % Add merged metadata to result (only if non-empty) - case maps:size(MergedMeta) of - 0 -> MergedData; - _ -> maps:put(meta, MergedMeta, MergedData) +%% @private +%% @doc Create a generator function from a list of tuple hashes. +%% +%% Converts a list of tuple hashes into a generator function compatible +%% with the generator protocol used by infinite relations. The generator +%% reads tuples from Mnesia on demand. +%% +%% @param TupleHashes List of tuple hashes to iterate over +%% @returns Generator function that accepts 'next' and returns {value, Tuple, NextGen} or done +make_finite_generator([]) -> + fun(_) -> done end; +make_finite_generator([Hash | Rest]) -> + fun(next) -> + ResolvedTuple = resolve_tuple(Hash), + NextGen = make_finite_generator(Rest), + {value, ResolvedTuple, NextGen} end. - diff --git a/src/query_planner.erl b/src/query_planner.erl index 9d9d2bc..52bffda 100644 --- a/src/query_planner.erl +++ b/src/query_planner.erl @@ -8,43 +8,37 @@ %%% %%% The DSL uses nested tuples to represent relational operations: %%% <pre> -%%% % Scan relation (base case) -%%% {scan, employees} -%%% -%%% % Reference relation (synonym for scan) -%%% {relation, employees} +%%% % Base relation (just use the relation name) +%%% employees %%% %%% % Selection (filter) -%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end} +%%% {select, employees, fun(T) -> maps:get(age, T) > 30 end} %%% %%% % Projection -%%% {project, {scan, employees}, [name, age]} +%%% {project, employees, [name, age]} %%% %%% % Equijoin (natural join on common attribute) -%%% {join, {scan, employees}, {scan, departments}, dept_id} +%%% {join, employees, departments, dept_id} %%% %%% % Theta join (join with arbitrary predicate) %%% {theta_join, -%%% {scan, employees}, -%%% {scan, departments}, +%%% employees, +%%% departments, %%% fun(L, R) -> maps:get(dept_id, L) =:= maps:get(id, R) end} %%% %%% % Sort -%%% {sort, {scan, employees}, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end} +%%% {sort, employees, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end} %%% %%% % Take (limit) -%%% {take, {scan, employees}, 10} +%%% {take, employees, 10} %%% %%% % Rename attribute -%%% {rename, old_name, new_name, {scan, employees}} +%%% {rename, old_name, new_name, employees} %%% %%% % Composite query %%% {project, %%% {select, -%%% {join, -%%% {scan, employees}, -%%% {scan, departments}, -%%% dept_id}, +%%% {join, employees, departments, dept_id}, %%% fun(T) -> maps:get(age, T) > 30 end}, %%% [name, dept_name]} %%% </pre> @@ -52,7 +46,7 @@ %%% == Usage == %%% <pre> %%% % Prepare a query plan -%%% Plan = query_planner:prepare({select, {scan, employees}, +%%% Plan = query_planner:prepare({select, employees, %%% fun(T) -> maps:get(age, T) > 30 end}). %%% %%% % Execute and get iterator @@ -77,8 +71,7 @@ %%% Types -type query_plan() :: - {scan, atom()} % Scan relation - | {relation, atom()} % Reference relation + atom() % Relation name | {select, query_plan(), fun((map()) -> boolean())} % Filter | {project, query_plan(), [atom()]} % Projection | {join, query_plan(), query_plan(), atom()} % Equijoin @@ -111,21 +104,22 @@ prepare(Plan) -> %% @doc Execute a prepared query plan against a database. %% -%% Compiles the query plan into an iterator pipeline and returns -%% the iterator handle. The caller must consume the iterator using -%% operations:next_tuple/1 and close it with operations:close_iterator/1. +%% Returns an ephemeral relation for top-level operations that can spawn +%% multiple independent iterators. The relation's generator creates fresh +%% iterator pipelines on demand, allowing reproducible results. %% %% @param DB The database state %% @param Plan The prepared query plan -%% @returns Iterator process PID --spec execute(term(), query_plan()) -> pid(). +%% @returns Ephemeral relation record +-spec execute(term(), query_plan()) -> #relation{}. execute(DB, Plan) -> - compile_to_iterator(DB, Plan). + create_ephemeral_relation(DB, Plan). %% @doc Execute a query plan and collect all results. %% %% Convenience function that executes the plan and collects all -%% tuples into a list. Automatically closes the iterator. +%% tuples into a list. Uses the ephemeral relation to create an +%% iterator and automatically closes it. %% %% If the iterator times out (e.g., when sorting an infinite relation), %% returns partial results with a warning. @@ -135,7 +129,8 @@ execute(DB, Plan) -> %% @returns List of result tuples, or partial results on timeout -spec collect(term(), query_plan()) -> [map()]. collect(DB, Plan) -> - Iter = execute(DB, Plan), + EphemeralRelation = execute(DB, Plan), + Iter = (EphemeralRelation#relation.generator)(), Results = operations:collect_all(Iter), operations:close_iterator(Iter), case Results of @@ -165,11 +160,188 @@ explain(Plan) -> %%% Internal Functions +%% @doc Create an ephemeral relation for the top-level query plan. +%% +%% Uses pure relational operators from relational_operators module to construct +%% the query result. Returns an ephemeral relation with a generator closure that +%% can spawn fresh iterators, allowing reproducible query results. +%% +%% @param DB The database state (for looking up base relations only) +%% @param Plan The query plan +%% @returns Ephemeral relation record +-spec create_ephemeral_relation(term(), query_plan()) -> #relation{}. +create_ephemeral_relation(DB, Plan) -> + % Compile plan to ephemeral relation using pure operators + compile_to_relation(DB, Plan). + +%% @doc Compute the schema for a query plan. +%% +%% Recursively analyzes the query plan structure to determine the output schema. +%% The schema maps attribute names to their domain/type information. +%% +%% @param DB The database state +%% @param Plan The query plan +%% @returns Schema map +-spec compute_schema(term(), query_plan()) -> map(). +compute_schema(DB, RelationName) when is_atom(RelationName) -> + case maps:get(RelationName, DB#database_state.relations, undefined) of + undefined -> + % Relation not found, return empty schema + #{}; + RelationHash -> + [Relation] = mnesia:dirty_read(relation, RelationHash), + Relation#relation.schema + end; + +compute_schema(DB, {select, SubPlan, _Predicate}) -> + % Select doesn't change schema, just filters tuples + compute_schema(DB, SubPlan); + +compute_schema(DB, {project, SubPlan, Attributes}) -> + % Project filters the schema to only include selected attributes + SubSchema = compute_schema(DB, SubPlan), + maps:with(Attributes, SubSchema); + +compute_schema(DB, {join, LeftPlan, RightPlan, _Attribute}) -> + % Join combines schemas from both sides, handling attribute conflicts + LeftSchema = compute_schema(DB, LeftPlan), + RightSchema = compute_schema(DB, RightPlan), + merge_join_schemas(LeftSchema, RightSchema); + +compute_schema(DB, {theta_join, LeftPlan, RightPlan, _Predicate}) -> + % Theta join also combines schemas from both sides, handling attribute conflicts + LeftSchema = compute_schema(DB, LeftPlan), + RightSchema = compute_schema(DB, RightPlan), + merge_join_schemas(LeftSchema, RightSchema); + +compute_schema(DB, {sort, SubPlan, _Comparator}) -> + % Sort doesn't change schema + compute_schema(DB, SubPlan); + +compute_schema(DB, {take, SubPlan, _N}) -> + % Take doesn't change schema, just limits tuples + compute_schema(DB, SubPlan); + +compute_schema(DB, {rename, OldAttr, NewAttr, SubPlan}) -> + % Rename changes one attribute name in the schema + SubSchema = compute_schema(DB, SubPlan), + case maps:is_key(OldAttr, SubSchema) of + true -> + AttrType = maps:get(OldAttr, SubSchema), + SubSchema1 = maps:remove(OldAttr, SubSchema), + maps:put(NewAttr, AttrType, SubSchema1); + false -> + % Attribute doesn't exist, return unchanged schema + SubSchema + end; + +compute_schema(DB, {materialize, SubPlan}) -> + % Materialize doesn't change schema + compute_schema(DB, SubPlan); + +compute_schema(DB, {materialize, SubPlan, _N}) -> + % Materialize with limit doesn't change schema + compute_schema(DB, SubPlan); + +compute_schema(_DB, _UnknownPlan) -> + % Unknown plan type, return empty schema + #{}. + +%% @doc Merge schemas for join operations, handling attribute conflicts elegantly. +%% +%% Instead of prefixing conflicting attribute names, this approach maintains +%% both provenances in the schema value. For attributes that exist in both +%% relations, the schema value becomes a list of the original values. +%% This is especially important for natural joins where the join attribute +%% logically represents the same entity from both sides. +%% +%% @param LeftSchema Schema from left relation +%% @param RightSchema Schema from right relation +%% @returns Merged schema map with provenance lists for conflicts +-spec merge_join_schemas(map(), map()) -> map(). +merge_join_schemas(LeftSchema, RightSchema) -> + maps:fold( + fun(Key, RightValue, Acc) -> + case maps:get(Key, Acc, undefined) of + undefined -> + % No conflict, add the right attribute + maps:put(Key, RightValue, Acc); + LeftValue when LeftValue =:= RightValue -> + % Same type/domain, keep single value (common in natural joins) + maps:put(Key, LeftValue, Acc); + LeftValue when is_list(LeftValue) -> + % Left value is already a list, append if not already present + case lists:member(RightValue, LeftValue) of + true -> maps:put(Key, LeftValue, Acc); + false -> maps:put(Key, LeftValue ++ [RightValue], Acc) + end; + LeftValue -> + % Conflict with different types - create provenance list + maps:put(Key, [LeftValue, RightValue], Acc) + end + end, + LeftSchema, + RightSchema + ). + +%% @doc Compute provenance for a query plan. +%% +%% Recursively analyzes the query plan structure to determine the provenance, +%% following the provenance types defined in operations.hrl. +%% +%% @param Plan The query plan +%% @returns Provenance term +-spec compute_provenance(query_plan()) -> term(). +compute_provenance(RelationName) when is_atom(RelationName) -> + {base, RelationName}; + +compute_provenance({select, SubPlan, _Predicate}) -> + % For select, we'd need to represent the predicate constraints + % For now, simplified without constraint details + SubProvenance = compute_provenance(SubPlan), + {select, SubProvenance, #{}}; + +compute_provenance({project, SubPlan, Attributes}) -> + SubProvenance = compute_provenance(SubPlan), + {project, SubProvenance, Attributes}; + +compute_provenance({join, LeftPlan, RightPlan, _Attribute}) -> + LeftProvenance = compute_provenance(LeftPlan), + RightProvenance = compute_provenance(RightPlan), + {join, LeftProvenance, RightProvenance}; + +compute_provenance({theta_join, LeftPlan, RightPlan, _Predicate}) -> + LeftProvenance = compute_provenance(LeftPlan), + RightProvenance = compute_provenance(RightPlan), + {join, LeftProvenance, RightProvenance}; + +compute_provenance({sort, SubPlan, _Comparator}) -> + % Sort doesn't change provenance + compute_provenance(SubPlan); + +compute_provenance({take, SubPlan, N}) -> + SubProvenance = compute_provenance(SubPlan), + {take, SubProvenance, N}; + +compute_provenance({rename, _OldAttr, _NewAttr, SubPlan}) -> + % Rename preserves underlying provenance + compute_provenance(SubPlan); + +compute_provenance({materialize, SubPlan}) -> + % Materialize doesn't change provenance + compute_provenance(SubPlan); + +compute_provenance({materialize, SubPlan, _N}) -> + % Materialize with limit doesn't change provenance + compute_provenance(SubPlan); + +compute_provenance(_UnknownPlan) -> + % Unknown plan type + undefined. + %% Validate query plan structure -spec validate_plan(query_plan()) -> ok | {error, term()}. -validate_plan({scan, Name}) when is_atom(Name) -> - ok; -validate_plan({relation, Name}) when is_atom(Name) -> +validate_plan(Name) when is_atom(Name) -> ok; validate_plan({select, SubPlan, Pred}) when is_function(Pred, 1) -> validate_plan(SubPlan); @@ -205,10 +377,7 @@ validate_plan(Plan) -> %% Compile query plan to iterator pipeline -spec compile_to_iterator(term(), query_plan()) -> pid(). -compile_to_iterator(DB, {scan, Name}) -> - operations:get_tuples_iterator(DB, Name); - -compile_to_iterator(DB, {relation, Name}) -> +compile_to_iterator(DB, Name) when is_atom(Name) -> operations:get_tuples_iterator(DB, Name); compile_to_iterator(DB, {select, SubPlan, Predicate}) -> @@ -234,22 +403,16 @@ compile_to_iterator(DB, {sort, SubPlan, Comparator}) -> operations:sort_iterator(SubIter, Comparator); compile_to_iterator(DB, {take, SubPlan, N}) -> - %% Use relational take operator when possible (for scans) - case SubPlan of - {scan, RelationName} -> - %% Direct scan: use relational take operator - {DB2, TakeRelation} = operations:take(DB, RelationName, N), - %% Get iterator from the take relation (now properly registered) - operations:get_tuples_iterator(DB2, TakeRelation#relation.name, #{}); - _ -> - %% Complex plan: fall back to iterator-based take for composition - SubIter = compile_to_iterator(DB, SubPlan), - operations:take_iterator(SubIter, N) - end; + %% For iterator-based compilation, use take_iterator + SubIter = compile_to_iterator(DB, SubPlan), + operations:take_iterator(SubIter, N); compile_to_iterator(DB, {rename, OldAttr, NewAttr, SubPlan}) -> SubIter = compile_to_iterator(DB, SubPlan), - rename_iterator(SubIter, OldAttr, NewAttr); + %% Inline simple rename - no need for separate function + spawn(fun() -> + rename_loop_inline(SubIter, OldAttr, NewAttr) + end); compile_to_iterator(DB, {materialize, SubPlan}) -> % Materialize returns all tuples as a "static" iterator @@ -286,18 +449,14 @@ static_loop(Tuples) -> Caller ! ok end. -%% Rename iterator - renames an attribute in each tuple --spec rename_iterator(pid(), atom(), atom()) -> pid(). -rename_iterator(SourceIter, OldAttr, NewAttr) -> - spawn(fun() -> rename_loop(SourceIter, OldAttr, NewAttr) end). - -rename_loop(SourceIter, OldAttr, NewAttr) -> +%% @private +%% Inline helper for compile_to_iterator rename case +rename_loop_inline(SourceIter, OldAttr, NewAttr) -> receive {next, Caller} -> case operations:next_tuple(SourceIter) of done -> - Caller ! done, - rename_loop(SourceIter, OldAttr, NewAttr); + Caller ! done; {ok, Tuple} -> RenamedTuple = case maps:is_key(OldAttr, Tuple) of true -> @@ -308,7 +467,7 @@ rename_loop(SourceIter, OldAttr, NewAttr) -> Tuple end, Caller ! {tuple, RenamedTuple}, - rename_loop(SourceIter, OldAttr, NewAttr) + rename_loop_inline(SourceIter, OldAttr, NewAttr) end; {close, Caller} -> operations:close_iterator(SourceIter), @@ -317,10 +476,7 @@ rename_loop(SourceIter, OldAttr, NewAttr) -> %% Pretty-print query plan -spec explain_plan(query_plan(), non_neg_integer()) -> string(). -explain_plan({scan, Name}, Indent) -> - indent(Indent) ++ "Scan: " ++ atom_to_list(Name) ++ "\n"; - -explain_plan({relation, Name}, Indent) -> +explain_plan(Name, Indent) when is_atom(Name) -> indent(Indent) ++ "Relation: " ++ atom_to_list(Name) ++ "\n"; explain_plan({select, SubPlan, _Pred}, Indent) -> @@ -365,3 +521,81 @@ explain_plan({materialize, SubPlan, N}, Indent) -> %% Helper: indent string -spec indent(non_neg_integer()) -> string(). indent(N) -> lists:duplicate(N, $\s). + +%% Helper: get relation from database +-spec get_relation_from_db(term(), atom()) -> #relation{}. +get_relation_from_db(DB, RelationName) -> + case maps:get(RelationName, DB#database_state.relations, undefined) of + undefined -> + erlang:error({relation_not_found, RelationName}); + RelationHash -> + [Relation] = mnesia:dirty_read(relation, RelationHash), + Relation + end. + +%% @doc Compile query plan to ephemeral relation using pure relational operators. +%% +%% This is the new approach: build a relation tree using pure operators, +%% then return the final ephemeral relation. No iterators are created until +%% the generator is called. +-spec compile_to_relation(term(), query_plan()) -> #relation{}. +compile_to_relation(DB, RelationName) when is_atom(RelationName) -> + BaseRelation = get_relation_from_db(DB, RelationName), + GeneratorFun = fun() -> + operations:get_tuples_iterator(DB, RelationName) + end, + BaseRelation#relation{generator = GeneratorFun}; + +compile_to_relation(DB, {select, SubPlan, Predicate}) -> + SubRelation = compile_to_relation(DB, SubPlan), + relational_operators:select(SubRelation, Predicate); + +compile_to_relation(DB, {project, SubPlan, Attributes}) -> + SubRelation = compile_to_relation(DB, SubPlan), + relational_operators:project(SubRelation, Attributes); + +compile_to_relation(DB, {join, LeftPlan, RightPlan, Attribute}) -> + LeftRelation = compile_to_relation(DB, LeftPlan), + RightRelation = compile_to_relation(DB, RightPlan), + relational_operators:join(LeftRelation, RightRelation, Attribute); + +compile_to_relation(DB, {theta_join, LeftPlan, RightPlan, Predicate}) -> + LeftRelation = compile_to_relation(DB, LeftPlan), + RightRelation = compile_to_relation(DB, RightPlan), + relational_operators:theta_join(LeftRelation, RightRelation, Predicate); + +compile_to_relation(DB, {sort, SubPlan, Comparator}) -> + SubRelation = compile_to_relation(DB, SubPlan), + relational_operators:sort(SubRelation, Comparator); + +compile_to_relation(DB, {take, SubPlan, N}) -> + SubRelation = compile_to_relation(DB, SubPlan), + relational_operators:take(SubRelation, N); + +compile_to_relation(DB, {rename, OldAttr, NewAttr, SubPlan}) -> + SubRelation = compile_to_relation(DB, SubPlan), + relational_operators:rename(SubRelation, #{OldAttr => NewAttr}); + +compile_to_relation(DB, {materialize, SubPlan}) -> + GeneratorFun = fun() -> + compile_to_iterator(DB, SubPlan) + end, + EphemeralName = list_to_atom("materialized_" ++ integer_to_list(erlang:unique_integer([positive]))), + #relation{ + hash = crypto:hash(sha256, term_to_binary({materialize, SubPlan})), + name = EphemeralName, + tree = undefined, + schema = compute_schema(DB, SubPlan), + constraints = #{}, + cardinality = unknown, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = compute_provenance(SubPlan) + }; + +compile_to_relation(DB, {materialize, SubPlan, N}) -> + % Materialize with limit + SubRelation = compile_to_relation(DB, SubPlan), + TakeRelation = relational_operators:take(SubRelation, N), + % Then wrap in a materialized form (for now just return take) + TakeRelation. diff --git a/src/relational_operators.erl b/src/relational_operators.erl new file mode 100644 index 0000000..82e1a47 --- /dev/null +++ b/src/relational_operators.erl @@ -0,0 +1,366 @@ +%%% @doc Pure Relational Operators +%%% +%%% This module provides pure relational algebra operators that take relations +%%% as input and return new ephemeral relations as output. No database state +%%% is modified. Each operator returns a relation with a generator closure that +%%% can spawn fresh iterators on demand, allowing reproducible query results. +%%% +%%% == Architecture == +%%% +%%% Relational Operators (Pure Functions): +%%% - Input: One or more #relation{} records +%%% - Output: New ephemeral #relation{} with generator closure +%%% - No side effects, no DB modification +%%% - Generator can be called multiple times for same results +%%% +%%% Iterator Operators (Data Transport): +%%% - Input: Iterator PIDs +%%% - Output: Iterator PID +%%% - Used inside generator closures +%%% - Examples: select_iterator/2, project_iterator/2, take_iterator/2 +%%% +%%% @author Nekoma Team +%%% @copyright 2025 + +-module(relational_operators). + +-include("../include/operations.hrl"). + +-export([ + take/2, + select/2, + project/2, + join/3, + theta_join/3, + rename/2, + sort/2 +]). + +%%% ============================================================================ +%%% Internal Helper Functions +%%% ============================================================================ + +%% @private +%% Generate a random name for ephemeral relations. +generate_ephemeral_name() -> + {UUID, _} = uuid:get_v1(uuid:new(self(), erlang)), + [Base64UUID] = io_lib:format("~s", [base64:encode(UUID)]), + Base64UUID. + +%%% ============================================================================ +%%% Relational Operators +%%% ============================================================================ + +%% @doc Take operator (τ): Returns ephemeral relation with first N tuples. +%% +%% Creates an ephemeral relation containing N arbitrary elements from the +%% source relation. The generator closure captures the source relation and N, +%% spawning fresh iterators on each call. +%% +%% == Example == +%% <pre> +%% NaturalRel = get_relation(DB, natural), +%% Some100 = relational_operators:take(NaturalRel, 100), +%% +%% %% Can call generator multiple times +%% Iter1 = operations:get_iterator_from_generator(ephemeral, Some100#relation.generator), +%% Results1 = operations:collect_all(Iter1), +%% +%% Iter2 = operations:get_iterator_from_generator(ephemeral, Some100#relation.generator), +%% Results2 = operations:collect_all(Iter2), +%% %% Results1 =:= Results2 +%% </pre> +%% +%% @param SourceRelation Source #relation{} record +%% @param N Number of tuples to take +%% @returns Ephemeral #relation{} with generator +-spec take(#relation{}, pos_integer()) -> #relation{}. +take(SourceRelation, N) when is_record(SourceRelation, relation), is_integer(N), N > 0 -> + %% Compute result cardinality + ResultCardinality = case SourceRelation#relation.cardinality of + {finite, M} when M < N -> {finite, M}; + {finite, _} -> {finite, N}; + _ -> {finite, N} + end, + Name = generate_ephemeral_name(), + SourceGen = SourceRelation#relation.generator, + GeneratorFun = fun() -> + SourceIter = SourceGen(), + operations:take_iterator(SourceIter, N) + end, + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = SourceRelation#relation.schema, + constraints = SourceRelation#relation.constraints, + cardinality = ResultCardinality, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = SourceRelation#relation.provenance, + lineage = {take, N, SourceRelation#relation.lineage} + }. + +%% @doc Select operator (σ): Returns ephemeral relation filtered by predicate. +%% +%% Creates an ephemeral relation containing only tuples that satisfy the +%% predicate. The generator closure captures the source relation and predicate. +%% +%% @param SourceRelation Source #relation{} record +%% @param Predicate Function that takes a tuple and returns boolean +%% @returns Ephemeral #relation{} with generator +-spec select(#relation{}, fun((map()) -> boolean())) -> #relation{}. +select(SourceRelation, Predicate) when is_record(SourceRelation, relation), is_function(Predicate, 1) -> + Name = generate_ephemeral_name(), + + SourceGen = SourceRelation#relation.generator, + GeneratorFun = fun() -> + SourceIter = SourceGen(), + operations:select_iterator(SourceIter, Predicate) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = SourceRelation#relation.schema, + constraints = SourceRelation#relation.constraints, + cardinality = unknown, % Cannot determine without evaluation + generator = GeneratorFun, + membership_criteria = #{}, + provenance = SourceRelation#relation.provenance, + lineage = {select, Predicate, SourceRelation#relation.lineage} + }. + +%% @doc Project operator (π): Returns ephemeral relation with selected attributes. +%% +%% Creates an ephemeral relation containing only the specified attributes. +%% The generator closure captures the source relation and attribute list. +%% +%% @param SourceRelation Source #relation{} record +%% @param Attributes List of attribute names to keep +%% @returns Ephemeral #relation{} with generator +-spec project(#relation{}, [atom()]) -> #relation{}. +project(SourceRelation, Attributes) when is_record(SourceRelation, relation), is_list(Attributes) -> + Name = generate_ephemeral_name(), + + %% Compute projected schema + ProjectedSchema = maps:with(Attributes, SourceRelation#relation.schema), + + SourceGen = SourceRelation#relation.generator, + GeneratorFun = fun() -> + SourceIter = SourceGen(), + operations:project_iterator(SourceIter, Attributes) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = ProjectedSchema, + constraints = SourceRelation#relation.constraints, + cardinality = SourceRelation#relation.cardinality, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = SourceRelation#relation.provenance, + lineage = {project, Attributes, SourceRelation#relation.lineage} + }. + +%% @doc Join operator (⋈): Returns ephemeral relation from equijoin. +%% +%% Creates an ephemeral relation by joining two relations on a common attribute. +%% The generator closure captures both source relations and the join attribute. +%% +%% @param LeftRelation Left #relation{} record +%% @param RightRelation Right #relation{} record +%% @param JoinAttribute Attribute name to join on +%% @returns Ephemeral #relation{} with generator +-spec join(#relation{}, #relation{}, atom()) -> #relation{}. +join(LeftRelation, RightRelation, JoinAttribute) + when is_record(LeftRelation, relation), + is_record(RightRelation, relation), + is_atom(JoinAttribute) -> + + Name = list_to_atom( + "join_" ++ atom_to_list(LeftRelation#relation.name) ++ "_" ++ + atom_to_list(RightRelation#relation.name) ++ "_" ++ + integer_to_list(erlang:unique_integer([positive])) + ), + + %% Merge schemas + MergedSchema = maps:merge(LeftRelation#relation.schema, RightRelation#relation.schema), + + LeftGen = LeftRelation#relation.generator, + RightGen = RightRelation#relation.generator, + GeneratorFun = fun() -> + LeftIter = LeftGen(), + RightIter = RightGen(), + operations:equijoin_iterator(LeftIter, RightIter, JoinAttribute) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = MergedSchema, + constraints = #{}, + cardinality = unknown, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = {join, LeftRelation#relation.provenance, RightRelation#relation.provenance}, + lineage = {join, JoinAttribute, LeftRelation#relation.lineage, RightRelation#relation.lineage} + }. + +%% @doc Theta Join operator (⋈θ): Returns ephemeral relation from theta join. +%% +%% Creates an ephemeral relation by joining two relations with an arbitrary +%% predicate. The generator closure captures both source relations and predicate. +%% +%% @param LeftRelation Left #relation{} record +%% @param RightRelation Right #relation{} record +%% @param Predicate Function that takes two tuples and returns boolean +%% @returns Ephemeral #relation{} with generator +-spec theta_join(#relation{}, #relation{}, fun((map(), map()) -> boolean())) -> #relation{}. +theta_join(LeftRelation, RightRelation, Predicate) + when is_record(LeftRelation, relation), + is_record(RightRelation, relation), + is_function(Predicate, 2) -> + + Name = list_to_atom( + "theta_join_" ++ atom_to_list(LeftRelation#relation.name) ++ "_" ++ + atom_to_list(RightRelation#relation.name) ++ "_" ++ + integer_to_list(erlang:unique_integer([positive])) + ), + + MergedSchema = maps:merge(LeftRelation#relation.schema, RightRelation#relation.schema), + + LeftGen = LeftRelation#relation.generator, + RightGen = RightRelation#relation.generator, + GeneratorFun = fun() -> + LeftIter = LeftGen(), + RightIter = RightGen(), + operations:theta_join_iterator(LeftIter, RightIter, Predicate) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = MergedSchema, + constraints = #{}, + cardinality = unknown, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = {join, LeftRelation#relation.provenance, RightRelation#relation.provenance}, + lineage = {theta_join, Predicate, LeftRelation#relation.lineage, RightRelation#relation.lineage} + }. + +%% @doc Rename operator (ρ): Returns ephemeral relation with renamed attributes. +%% +%% Creates an ephemeral relation with attributes renamed according to the mapping. +%% The generator closure captures the source relation and rename mappings. +%% +%% @param SourceRelation Source #relation{} record +%% @param RenameMappings Map of old_name => new_name (atoms or strings) +%% @returns Ephemeral #relation{} with generator +-spec rename(#relation{}, #{atom() => atom()}) -> #relation{}. +rename(SourceRelation, RenameMappings) when is_record(SourceRelation, relation), is_map(RenameMappings) -> + Name = generate_ephemeral_name(), + + %% Compute renamed schema + RenamedSchema = maps:fold( + fun(OldAttr, NewAttr, SchemaAcc) -> + case maps:get(OldAttr, SchemaAcc, undefined) of + undefined -> SchemaAcc; + Type -> + SchemaAcc1 = maps:remove(OldAttr, SchemaAcc), + maps:put(NewAttr, Type, SchemaAcc1) + end + end, + SourceRelation#relation.schema, + RenameMappings + ), + + SourceGen = SourceRelation#relation.generator, + GeneratorFun = fun() -> + SourceIter = SourceGen(), + rename_iterator(SourceIter, RenameMappings) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = RenamedSchema, + constraints = SourceRelation#relation.constraints, + cardinality = SourceRelation#relation.cardinality, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = SourceRelation#relation.provenance, + lineage = {rename, RenameMappings, SourceRelation#relation.lineage} + }. + +%% @doc Sort operator: Returns ephemeral relation with sorted tuples. +%% +%% Creates an ephemeral relation with tuples sorted by the comparator. +%% WARNING: This is a blocking operation - it materializes all tuples. +%% +%% @param SourceRelation Source #relation{} record +%% @param Comparator Function that compares two tuples +%% @returns Ephemeral #relation{} with generator +-spec sort(#relation{}, fun((map(), map()) -> boolean())) -> #relation{}. +sort(SourceRelation, Comparator) when is_record(SourceRelation, relation), is_function(Comparator, 2) -> + Name = generate_ephemeral_name(), + + SourceGen = SourceRelation#relation.generator, + GeneratorFun = fun() -> + SourceIter = SourceGen(), + operations:sort_iterator(SourceIter, Comparator) + end, + + #relation{ + hash = <<>>, + name = Name, + tree = undefined, + schema = SourceRelation#relation.schema, + constraints = SourceRelation#relation.constraints, + cardinality = SourceRelation#relation.cardinality, + generator = GeneratorFun, + membership_criteria = #{}, + provenance = SourceRelation#relation.provenance, + lineage = {sort, Comparator, SourceRelation#relation.lineage} + }. + +%%% Helper Functions + +%% @private +%% @doc Rename iterator - applies rename mapping to each tuple +rename_iterator(SourceIter, RenameMappings) -> + spawn(fun() -> rename_loop(SourceIter, RenameMappings) end). + +rename_loop(SourceIter, RenameMappings) -> + receive + {next, Caller} -> + case operations:next_tuple(SourceIter) of + done -> + Caller ! done; + {ok, Tuple} -> + RenamedTuple = maps:fold( + fun(OldAttr, NewAttr, TupleAcc) -> + case maps:get(OldAttr, TupleAcc, undefined) of + undefined -> TupleAcc; + Value -> + TupleAcc1 = maps:remove(OldAttr, TupleAcc), + maps:put(NewAttr, Value, TupleAcc1) + end + end, + Tuple, + RenameMappings + ), + Caller ! {tuple, RenamedTuple}, + rename_loop(SourceIter, RenameMappings) + end; + {close, Caller} -> + operations:close_iterator(SourceIter), + Caller ! ok + end. diff --git a/src/repl.erl b/src/repl.erl index c61ebfe..599d721 100644 --- a/src/repl.erl +++ b/src/repl.erl @@ -21,30 +21,27 @@ %%% %%% == Query Syntax Examples == %%% <pre> -%%% % Scan relation -%%% {scan, employees} +%%% % Base relation (just use the name) +%%% employees %%% %%% % Filter -%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end} +%%% {select, employees, fun(T) -> maps:get(age, T) > 30 end} %%% %%% % Project -%%% {project, {scan, employees}, [name, age]} +%%% {project, employees, [name, age]} %%% %%% % Join -%%% {join, {scan, employees}, {scan, departments}, dept_id} +%%% {join, employees, departments, dept_id} %%% %%% % Rename -%%% {rename, age, years, {scan, employees}} +%%% {rename, age, years, employees} %%% %%% % Complex pipeline %%% {take, %%% {sort, %%% {project, %%% {select, -%%% {join, -%%% {scan, employees}, -%%% {scan, departments}, -%%% dept_id}, +%%% {join, employees, departments, dept_id}, %%% fun(T) -> maps:get(age, T) > 30 end}, %%% [name, dept_name, age]}, %%% fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end}, @@ -79,7 +76,7 @@ %% @returns ok -spec start() -> ok. start() -> - operations:setup(), + main:setup(), io:format("~n~s~n", [banner()]), io:format("Domino REPL started. Type repl:help() for usage.~n~n"), ok. @@ -250,10 +247,10 @@ help() -> io:format("Quick Start:~n"), io:format(" repl:start(). %% Initialize system~n"), io:format(" DB = repl:example_db(). %% Create example database~n"), - io:format(" repl:q(DB, {scan, employees}). %% Run a query~n~n"), + io:format(" repl:q(DB, employees). %% Run a query~n~n"), io:format("Query Operators (all lazy by default):~n"), - io:format(" {scan, Name} - Scan relation~n"), + io:format(" RelationName - Base relation~n"), io:format(" {select, Plan, Predicate} - Filter tuples~n"), io:format(" {project, Plan, [Attrs]} - Project attributes~n"), io:format(" {join, Left, Right, Attr} - Equijoin~n"), @@ -281,39 +278,41 @@ help() -> io:format(" repl:modes() - List all available modes~n~n"), io:format("Examples:~n"), + io:format(" %% Query all employees~n"), + io:format(" repl:q(DB, employees).~n~n"), + io:format(" %% Filter employees over 30~n"), - io:format(" repl:q(DB, {select, {scan, employees}, ~n"), + io:format(" repl:q(DB, {select, employees, ~n"), io:format(" fun(T) -> maps:get(age, T) > 30 end}).~n~n"), io:format(" %% Project name and age~n"), - io:format(" repl:q(DB, {project, {scan, employees}, [name, age]}).~n~n"), + io:format(" repl:q(DB, {project, employees, [name, age]}).~n~n"), io:format(" %% Join employees with departments~n"), - io:format(" repl:q(DB, {join, {scan, employees}, ~n"), - io:format(" {scan, departments}, dept_id}).~n~n"), + io:format(" repl:q(DB, {join, employees, departments, dept_id}).~n~n"), io:format(" %% Rename age to years~n"), - io:format(" repl:q(DB, {rename, age, years, {scan, employees}}).~n~n"), + io:format(" repl:q(DB, {rename, age, years, employees}).~n~n"), io:format(" %% Materialize first 10 tuples (eager evaluation)~n"), - io:format(" repl:q(DB, {materialize, {scan, employees}, 10}).~n~n"), + io:format(" repl:q(DB, {materialize, employees, 10}).~n~n"), io:format(" %% Nested materialize - select from materialized data~n"), - io:format(" repl:q(DB, {select, {materialize, {scan, employees}},~n"), + io:format(" repl:q(DB, {select, {materialize, employees},~n"), io:format(" fun(T) -> maps:get(age, T) > 30 end}).~n~n"), io:format(" %% Use different visualization modes~n"), - io:format(" repl:q(DB, {scan, employees}, tree).~n"), - io:format(" repl:q(DB, {scan, employees}, nested_table).~n"), - io:format(" repl:q(DB, {scan, employees}, outline).~n~n"), + io:format(" repl:q(DB, employees, tree).~n"), + io:format(" repl:q(DB, employees, nested_table).~n"), + io:format(" repl:q(DB, employees, outline).~n~n"), io:format(" %% Query without printing, then show results~n"), - io:format(" Results = repl:query(DB, {scan, employees}).~n"), + io:format(" Results = repl:query(DB, employees).~n"), io:format(" Filtered = lists:filter(fun(T) -> maps:get(age, T) > 30 end, Results).~n"), io:format(" repl:show(Filtered, tree).~n~n"), io:format(" %% Explain a query plan~n"), - io:format(" repl:explain({select, {scan, employees}, ~n"), + io:format(" repl:explain({select, employees, ~n"), io:format(" fun(T) -> maps:get(age, T) > 30 end}).~n~n"), ok. diff --git a/src/xml_server.erl b/src/xml_server.erl index 4eef4c9..eaa08f9 100644 --- a/src/xml_server.erl +++ b/src/xml_server.erl @@ -33,7 +33,7 @@ %%% xml_server:start(8080). %%% %%% % Client connects and sends: -%%% % QUERY {scan, employees}\n +%%% % QUERY employees\n %%% % NEXT <session-id> 10\n %%% % NEXT <session-id> 10\n %%% % CLOSE <session-id>\n @@ -209,9 +209,12 @@ handle_query(QueryStr, DB, Sessions) -> {ok, Exprs} = erl_parse:parse_exprs(Tokens), {value, QueryPlan, _} = erl_eval:exprs(Exprs, erl_eval:new_bindings()), - % Prepare and execute query to get iterator + % Prepare and execute query to get ephemeral relation PreparedPlan = query_planner:prepare(QueryPlan), - Iterator = query_planner:execute(DB, PreparedPlan), + EphemeralRelation = query_planner:execute(DB, PreparedPlan), + + % Create actual iterator from ephemeral relation's generator + Iterator = (EphemeralRelation#relation.generator)(), % Generate session ID SessionId = generate_session_id(), diff --git a/src/xml_server_app.erl b/src/xml_server_app.erl index d2e1c18..b7b9faa 100644 --- a/src/xml_server_app.erl +++ b/src/xml_server_app.erl @@ -12,7 +12,7 @@ start() -> %% @doc Start XML server on specified port. start(Port) -> % Initialize Domino - operations:setup(), + main:setup(), io:format("~nDomino initialized~n"), % Create example database diff --git a/test/function_relations_test.erl b/test/function_relations_test.erl deleted file mode 100644 index a6ab2d2..0000000 --- a/test/function_relations_test.erl +++ /dev/null @@ -1,347 +0,0 @@ --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), - - % Integers and naturals are now built-in to every database - % Just create the function relations using the new format - - % Create function relations - note how their schemas reference the domain relations - {DB1, _Plus} = operations:create_immutable_relation(DB, #immutable_relation_spec{ - name = plus, - schema = #{a => integer, b => integer, sum => integer}, - generator = {generators, plus}, - membership_criteria = #{}, - cardinality = aleph_zero - }), - - {DB2, _Times} = operations:create_immutable_relation(DB1, #immutable_relation_spec{ - name = times, - schema = #{a => integer, b => integer, product => integer}, - generator = {generators, times}, - membership_criteria = #{}, - cardinality = aleph_zero - }), - - {DB3, _Minus} = operations:create_immutable_relation(DB2, #immutable_relation_spec{ - name = minus, - schema = #{a => integer, b => integer, difference => integer}, - generator = {generators, minus}, - membership_criteria = #{}, - cardinality = aleph_zero - }), - - {DB4, _Divide} = operations:create_immutable_relation(DB3, #immutable_relation_spec{ - name = divide, - schema = #{a => integer, b => integer, quotient => integer, remainder => natural}, - generator = {generators, divide}, - membership_criteria = #{}, - cardinality = aleph_zero - }), - - DB4. - -cleanup(_DB) -> - ok. - -%%% Helper Functions - -%% Strip metadata from tuples for comparison -strip_meta(Tuple) when is_map(Tuple) -> - maps:remove(meta, Tuple); -strip_meta(Tuples) when is_list(Tuples) -> - [strip_meta(T) || T <- Tuples]. - -%%% 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), - DataOnly = strip_meta(Results), - - % 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}, DataOnly)), - ?_assert(lists:member(#{a => 2, b => 3, sum => 5}, DataOnly)), - ?_assert(lists:member(#{a => 3, b => 4, sum => 7}, DataOnly)), - ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> - S =:= A + B - end, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - % 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, DataOnly)), - ?_assert(lists:member(#{a => 1, b => 4, sum => 5}, DataOnly)), - ?_assert(lists:member(#{a => 3, b => 4, sum => 7}, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - [ - ?_assert(length(Results) > 0), - ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> - S =:= A + B andalso A >= 0 - end, DataOnly)), - ?_assert(lists:member(#{a => 3, b => 2, sum => 5}, DataOnly)), - ?_assert(lists:member(#{a => 2, b => 4, sum => 6}, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - [ - ?_assertEqual(6, length(Results)), - ?_assert(lists:member(#{a => 0, b => 5, sum => 5}, DataOnly)), - ?_assert(lists:member(#{a => 2, b => 3, sum => 5}, DataOnly)), - ?_assert(lists:member(#{a => 5, b => 0, sum => 5}, DataOnly)), - ?_assert(lists:all(fun(#{a := A, b := B, sum := S}) -> - S =:= A + B andalso S =:= 5 - end, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - % 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, DataOnly)), - ?_assert(lists:member(#{a => 0, b => 2, sum => 2}, DataOnly)), - ?_assert(lists:member(#{a => 3, b => 0, sum => 3}, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - % 3×3 = 9 tuples - [ - ?_assertEqual(9, length(Results)), - ?_assert(lists:member(#{a => 2, b => 3, product => 6}, DataOnly)), - ?_assert(lists:member(#{a => 3, b => 4, product => 12}, DataOnly)), - ?_assert(lists:member(#{a => 4, b => 5, product => 20}, DataOnly)), - ?_assert(lists:all(fun(#{a := A, b := B, product := P}) -> - P =:= A * B - end, DataOnly)) - ]. - -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), - DataOnly = strip_meta(Results), - - % 3 × 2 = 6 tuples - [ - ?_assertEqual(6, length(Results)), - ?_assert(lists:member(#{a => 5, b => 2, difference => 3}, DataOnly)), - ?_assert(lists:member(#{a => 7, b => 3, difference => 4}, DataOnly)), - ?_assert(lists:all(fun(#{a := A, b := B, difference := D}) -> - D =:= A - B - end, DataOnly)) - ]. - -%%% 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), - DataOnly = strip_meta(Results), - - % 3 × 2 = 6 tuples - [ - ?_assertEqual(6, length(Results)), - ?_assert(lists:member(#{a => 10, b => 3, quotient => 3, remainder => 1}, DataOnly)), - ?_assert(lists:member(#{a => 12, b => 4, quotient => 3, remainder => 0}, DataOnly)), - ?_assert(lists:all(fun(#{a := A, b := B, quotient := Q, remainder := R}) -> - A =:= B * Q + R andalso R >= 0 andalso R < abs(B) - end, DataOnly)) - ]. - -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 deleted file mode 100644 index 5f87acb..0000000 --- a/test/infinite_relations_test.erl +++ /dev/null @@ -1,128 +0,0 @@ --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. - -%%% Helper Functions - -%% Strip metadata from tuples for comparison -strip_meta(Tuple) when is_map(Tuple) -> - maps:remove(meta, Tuple); -strip_meta(Tuples) when is_list(Tuples) -> - [strip_meta(T) || T <- Tuples]. - -%%% Tests - -test_create_naturals(DB) -> - %% Naturals are now built-in to every database - %% Just retrieve the relation to verify it exists - {ok, NaturalsHash} = operations:get_relation_hash(DB, natural), - [NaturalsRel] = mnesia:dirty_read(relation, NaturalsHash), - - [ - ?_assert(is_record(NaturalsRel, relation)), - ?_assertEqual(natural, NaturalsRel#relation.name), - ?_assertEqual(aleph_zero, NaturalsRel#relation.cardinality), - ?_assertEqual({generators, natural}, NaturalsRel#relation.generator) - ]. - -test_naturals_with_constraints(DB) -> - %% Naturals are built-in, just query them - %% Query with range constraint [0, 9] - Iterator = operations:get_tuples_iterator(DB, natural, #{value => {range, 0, 9}}), - Tuples = operations:collect_all(Iterator), - DataOnly = strip_meta(Tuples), - - %% Should get exactly 10 tuples: {0, 1, 2, ..., 9} - [ - ?_assertEqual(10, length(Tuples)), - ?_assert(lists:member(#{value => 0}, DataOnly)), - ?_assert(lists:member(#{value => 5}, DataOnly)), - ?_assert(lists:member(#{value => 9}, DataOnly)) - ]. - -test_integers_generator(DB) -> - %% Integers are built-in - {ok, IntegersHash} = operations:get_relation_hash(DB, integer), - [Integers] = mnesia:dirty_read(relation, IntegersHash), - - %% Query with range constraint [-5, 5] - Iterator = operations:get_tuples_iterator(DB, integer, #{value => {range, -5, 5}}), - Tuples = operations:collect_all(Iterator), - DataOnly = strip_meta(Tuples), - - %% Should get 11 tuples: {-5, -4, ..., 0, ..., 4, 5} - [ - ?_assertEqual(aleph_zero, Integers#relation.cardinality), - ?_assertEqual(11, length(Tuples)), - ?_assert(lists:member(#{value => 0}, DataOnly)), - ?_assert(lists:member(#{value => -5}, DataOnly)), - ?_assert(lists:member(#{value => 5}, DataOnly)) - ]. - -test_rationals_generator(DB) -> - %% Rationals are built-in - {ok, RationalsHash} = operations:get_relation_hash(DB, rational), - [Rationals] = mnesia:dirty_read(relation, RationalsHash), - - %% Take first 10 rationals using constraints - Iterator = operations:get_tuples_iterator(DB, rational, #{}), - - %% 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) -> - %% Naturals are built-in, just use them - %% Take 100 naturals - {_DB2, Naturals100} = operations:take(DB, natural, 100), - - %% Verify result is finite - [ - ?_assertEqual({finite, 100}, Naturals100#relation.cardinality), - ?_assertEqual({take, natural, 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/join_test.erl b/test/join_test.erl deleted file mode 100644 index de62127..0000000 --- a/test/join_test.erl +++ /dev/null @@ -1,273 +0,0 @@ --module(join_test). --include_lib("eunit/include/eunit.hrl"). --include("operations.hrl"). - -%%% Join Operators Test Suite -%%% -%%% Tests for relational join operations: -%%% - Equijoin (natural join on attribute equality) -%%% - Theta-join (join with arbitrary predicate) - -join_test_() -> - {foreach, - fun setup/0, - fun cleanup/1, - [ - fun test_equijoin_simple/1, - fun test_equijoin_multiple_matches/1, - fun test_equijoin_no_matches/1, - fun test_equijoin_with_conflicts/1, - fun test_theta_join_greater_than/1, - fun test_theta_join_complex_predicate/1, - fun test_join_with_infinite_relation/1, - fun test_join_materialize_pipeline/1 - ]}. - -%%% Setup and Cleanup - -setup() -> - operations:setup(), - DB = operations:create_database(test_db), - - % Create employees relation - {DB1, _} = operations:create_relation(DB, employees, #{ - id => integer, - name => string, - dept_id => integer, - age => integer - }), - - {DB2, _} = operations:create_tuple(DB1, employees, #{id => 1, name => "Alice", dept_id => 10, age => 30}), - {DB3, _} = operations:create_tuple(DB2, employees, #{id => 2, name => "Bob", dept_id => 20, age => 35}), - {DB4, _} = operations:create_tuple(DB3, employees, #{id => 3, name => "Carol", dept_id => 10, age => 28}), - {DB5, _} = operations:create_tuple(DB4, employees, #{id => 4, name => "Dave", dept_id => 30, age => 42}), - - % Create departments relation - {DB6, _} = operations:create_relation(DB5, departments, #{ - dept_id => integer, - dept_name => string, - budget => integer - }), - - {DB7, _} = operations:create_tuple(DB6, departments, #{dept_id => 10, dept_name => "Engineering", budget => 100000}), - {DB8, _} = operations:create_tuple(DB7, departments, #{dept_id => 20, dept_name => "Sales", budget => 80000}), - {DB9, _} = operations:create_tuple(DB8, departments, #{dept_id => 30, dept_name => "Marketing", budget => 90000}), - - DB9. - -cleanup(_DB) -> - ok. - -%%% Equijoin Tests - -test_equijoin_simple(DB) -> - % Join employees with departments on dept_id - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - Results = operations:collect_all(JoinIter), - - % Should get 4 joined tuples (one for each employee) - [ - ?_assertEqual(4, length(Results)), - % Check Alice joined with Engineering - ?_assert(lists:any(fun(T) -> - maps:get(name, T, undefined) =:= "Alice" andalso - maps:get(dept_name, T, undefined) =:= "Engineering" - end, Results)), - % Check Bob joined with Sales - ?_assert(lists:any(fun(T) -> - maps:get(name, T, undefined) =:= "Bob" andalso - maps:get(dept_name, T, undefined) =:= "Sales" - end, Results)), - % All results should have both employee and department attributes - ?_assert(lists:all(fun(T) -> - maps:is_key(name, T) andalso - maps:is_key(dept_name, T) andalso - maps:is_key(dept_id, T) - end, Results)) - ]. - -test_equijoin_multiple_matches(DB) -> - % Multiple employees in same department should produce multiple results - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - Results = operations:collect_all(JoinIter), - - % Engineering dept (10) has 2 employees (Alice and Carol) - EngineeringResults = lists:filter(fun(T) -> - maps:get(dept_name, T, undefined) =:= "Engineering" - end, Results), - - [ - ?_assertEqual(2, length(EngineeringResults)), - ?_assert(lists:any(fun(T) -> maps:get(name, T) =:= "Alice" end, EngineeringResults)), - ?_assert(lists:any(fun(T) -> maps:get(name, T) =:= "Carol" end, EngineeringResults)) - ]. - -test_equijoin_no_matches(DB) -> - % Create a department with no employees - {DB1, _} = operations:create_tuple(DB, departments, #{dept_id => 40, dept_name => "HR", budget => 70000}), - - % Filter to only dept_id=40 which has no employees - DeptIter = operations:get_tuples_iterator(DB1, departments, #{}), - FilteredDept = operations:select_iterator(DeptIter, fun(D) -> maps:get(dept_id, D) =:= 40 end), - - EmpIter = operations:get_tuples_iterator(DB1, employees, #{}), - - JoinIter = operations:equijoin_iterator(EmpIter, FilteredDept, dept_id), - Results = operations:collect_all(JoinIter), - - % No employees in HR, so no results - [ - ?_assertEqual(0, length(Results)) - ]. - -test_equijoin_with_conflicts(DB) -> - % Create relations with conflicting attribute names - {DB1, _} = operations:create_relation(DB, table_a, #{ - id => integer, - value => integer - }), - {DB2, _} = operations:create_tuple(DB1, table_a, #{id => 1, value => 100}), - - {DB3, _} = operations:create_relation(DB2, table_b, #{ - id => integer, - value => integer % Same name as table_a.value - }), - {DB4, _} = operations:create_tuple(DB3, table_b, #{id => 1, value => 200}), - - AIter = operations:get_tuples_iterator(DB4, table_a, #{}), - BIter = operations:get_tuples_iterator(DB4, table_b, #{}), - - JoinIter = operations:equijoin_iterator(AIter, BIter, id), - Results = operations:collect_all(JoinIter), - - % Should have one result with both values - % Right side 'value' should be prefixed as 'right_value' - [ - ?_assertEqual(1, length(Results)), - ?_assertMatch([#{id := 1, value := 100, right_value := 200}], Results) - ]. - -%%% Theta-Join Tests - -test_theta_join_greater_than(DB) -> - % Join where employee.age > department.budget/1000 - % (contrived example for testing) - - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - Predicate = fun(Emp, Dept) -> - Age = maps:get(age, Emp), - Budget = maps:get(budget, Dept), - Age > (Budget div 2000) % Age > Budget/2000 - end, - - JoinIter = operations:theta_join_iterator(EmpIter, DeptIter, Predicate), - Results = operations:collect_all(JoinIter), - - % Should get some results based on predicate - [ - ?_assert(length(Results) > 0), - % Verify predicate holds for all results - ?_assert(lists:all(fun(T) -> - Age = maps:get(age, T), - Budget = maps:get(budget, T), - Age > (Budget div 2000) - end, Results)) - ]. - -test_theta_join_complex_predicate(DB) -> - % Join with multiple conditions - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - % Join where employee is in department AND age > 30 - Predicate = fun(Emp, Dept) -> - maps:get(dept_id, Emp) =:= maps:get(dept_id, Dept) andalso - maps:get(age, Emp) > 30 - end, - - JoinIter = operations:theta_join_iterator(EmpIter, DeptIter, Predicate), - Results = operations:collect_all(JoinIter), - - % Should get Bob (35) and Dave (42), not Alice (30) or Carol (28) - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> maps:get(age, T) > 30 end, Results)), - ?_assert(lists:any(fun(T) -> maps:get(name, T) =:= "Bob" end, Results)), - ?_assert(lists:any(fun(T) -> maps:get(name, T) =:= "Dave" end, Results)) - ]. - -%%% Integration Tests - -test_join_with_infinite_relation(DB) -> - % Integers are built-in, no need to create them - - % Get small set of integers - IntIter = operations:get_tuples_iterator(DB, integer, #{value => {range, 1, 5}}), - - % Get employees - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - - % Join where employee.id matches integer.value - Predicate = fun(Emp, Int) -> - maps:get(id, Emp) =:= maps:get(value, Int) - end, - - JoinIter = operations:theta_join_iterator(EmpIter, IntIter, Predicate), - Results = operations:collect_all(JoinIter), - - % Should get employees with id in [1,5] (all 4 employees) - [ - ?_assertEqual(4, length(Results)), - ?_assert(lists:all(fun(T) -> - Id = maps:get(id, T), - Value = maps:get(value, T), - Id =:= Value andalso Id >= 1 andalso Id =< 5 - end, Results)) - ]. - -test_join_materialize_pipeline(DB) -> - % Complex pipeline: join, filter, project, materialize - - % 1. Join employees with departments - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - - % 2. Filter to high-budget departments - FilteredIter = operations:select_iterator(JoinIter, fun(T) -> - maps:get(budget, T) >= 90000 - end), - - % 3. Project to [name, dept_name, budget] - ProjectedIter = operations:project_iterator(FilteredIter, [name, dept_name, budget]), - - % 4. Materialize - {DB1, HighBudgetEmps} = operations:materialize(DB, ProjectedIter, high_budget_employees), - - % Verify materialized relation - ResultIter = operations:get_tuples_iterator(DB1, high_budget_employees, #{}), - Results = operations:collect_all(ResultIter), - - % Engineering (100k) has Alice and Carol - % Marketing (90k) has Dave - % Sales (80k) is excluded - [ - ?_assertEqual({finite, 3}, HighBudgetEmps#relation.cardinality), - ?_assertEqual(3, length(Results)), - ?_assert(lists:all(fun(T) -> - maps:is_key(name, T) andalso - maps:is_key(dept_name, T) andalso - maps:is_key(budget, T) andalso - not maps:is_key(id, T) andalso % Projected out - not maps:is_key(age, T) % Projected out - end, Results)), - ?_assert(lists:all(fun(T) -> maps:get(budget, T) >= 90000 end, Results)) - ]. diff --git a/test/operations_test.erl b/test/operations_test.erl deleted file mode 100644 index 31bde43..0000000 --- a/test/operations_test.erl +++ /dev/null @@ -1,366 +0,0 @@ --module(operations_test). --include("operations.hrl"). --include_lib("eunit/include/eunit.hrl"). - -%% Test fixtures and setup -setup_test_env() -> - operations:setup(), - ok. - -cleanup_test_env() -> - mnesia:stop(), - ok. - -%% Fixture: Create a sample database with a users relation -sample_database() -> - DB = operations:create_database(test_db), - {DB1, _Relation} = operations:create_relation(DB, users, #{ - name => string, - age => integer - }), - DB1. - -%% Fixture: Add sample tuples to a database -sample_database_with_tuples() -> - DB = sample_database(), - {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), - {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), - DB2. - -%%==================================================================== -%% Database Creation Tests -%%==================================================================== - -database_creation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = operations:create_database(my_db), - ?assertEqual(my_db, DB#database_state.name), - % Database now comes with built-in infinite relations - Relations = operations:get_relations(DB), - ?assert(lists:member(natural, Relations)), - ?assert(lists:member(integer, Relations)), - ?assert(lists:member(rational, Relations)), - ?assertNotEqual(undefined, DB#database_state.timestamp) - end)]}. - -%%==================================================================== -%% Relation Creation Tests -%%==================================================================== - -relation_creation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = operations:create_database(test_db), - Schema = #{name => string, email => string}, - {DB1, Relation} = operations:create_relation(DB, users, Schema), - - % Verify relation was created - ?assertEqual(users, Relation#relation.name), - ?assertEqual(Schema, Relation#relation.schema), - - % Verify database was updated (includes built-in relations) - Relations = operations:get_relations(DB1), - ?assert(lists:member(users, Relations)), - ?assert(lists:member(natural, Relations)), - ?assert(lists:member(integer, Relations)), - ?assert(lists:member(rational, Relations)), - {ok, RelationHash} = operations:get_relation_hash(DB1, users), - ?assertEqual(Relation#relation.hash, RelationHash) - end)]}. - -%%==================================================================== -%% Tuple Operations Tests -%%==================================================================== - -tuple_creation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database(), - InitialHash = DB#database_state.hash, - - % Add a tuple - {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), - - % Verify database hash changed - ?assertNotEqual(InitialHash, DB1#database_state.hash), - - % Verify tuple can be retrieved - Iterator = operations:get_tuples_iterator(DB1, users), - Tuples = operations:collect_all(Iterator), - ?assertEqual(1, length(Tuples)), - [Tuple] = Tuples, - ?assertEqual("Alice", maps:get(name, Tuple)), - ?assertEqual(30, maps:get(age, Tuple)) - end)]}. - -tuple_multiple_insertions_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database(), - - % Add multiple tuples - {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), - {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), - {DB3, _} = operations:create_tuple(DB2, users, #{name => "Charlie", age => 35}), - - % Verify all tuples can be retrieved - Iterator = operations:get_tuples_iterator(DB3, users), - Tuples = operations:collect_all(Iterator), - ?assertEqual(3, length(Tuples)), - - % Verify hashes changed with each insertion - ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash), - ?assertNotEqual(DB1#database_state.hash, DB2#database_state.hash), - ?assertNotEqual(DB2#database_state.hash, DB3#database_state.hash) - end)]}. - -%%==================================================================== -%% Hash Comparison Tests (Time-based) -%%==================================================================== - -database_state_hash_comparison_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database(), - Hash0 = DB#database_state.hash, - - % State 1: Add first tuple - {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), - Hash1 = DB1#database_state.hash, - - % State 2: Add second tuple - {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), - Hash2 = DB2#database_state.hash, - - % State 3: Add third tuple - {DB3, _} = operations:create_tuple(DB2, users, #{name => "Charlie", age => 35}), - Hash3 = DB3#database_state.hash, - - % Verify all hashes are unique - ?assertNotEqual(Hash0, Hash1), - ?assertNotEqual(Hash1, Hash2), - ?assertNotEqual(Hash2, Hash3), - ?assertNotEqual(Hash0, Hash2), - ?assertNotEqual(Hash0, Hash3), - ?assertNotEqual(Hash1, Hash3) - end)]}. - -relation_hash_comparison_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database(), - {ok, RelationHash0} = operations:get_relation_hash(DB, users), - - % Add tuple and get new relation hash - {DB1, Relation1} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), - RelationHash1 = Relation1#relation.hash, - - % Add another tuple - {DB2, Relation2} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), - RelationHash2 = Relation2#relation.hash, - - % Verify relation hashes changed over time - ?assertNotEqual(RelationHash0, RelationHash1), - ?assertNotEqual(RelationHash1, RelationHash2), - ?assertNotEqual(RelationHash0, RelationHash2), - - % Verify we can still get relation hash from database - {ok, CurrentHash} = operations:get_relation_hash(DB2, users), - ?assertEqual(RelationHash2, CurrentHash) - end)]}. - -%%==================================================================== -%% Tuple Retraction Tests -%%==================================================================== - -retract_tuple_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database_with_tuples(), - {ok, RelationHash} = operations:get_relation_hash(DB, users), - - % Get tuple hashes - TupleHashes = operations:hashes_from_tuple(RelationHash), - ?assertEqual(2, length(TupleHashes)), - - % Retract one tuple - [TupleHash | _] = TupleHashes, - {atomic, {DB1, _}} = operations:retract_tuple(DB, RelationHash, TupleHash), - - % Verify tuple was removed - {ok, NewRelationHash} = operations:get_relation_hash(DB1, users), - NewTupleHashes = operations:hashes_from_tuple(NewRelationHash), - ?assertEqual(1, length(NewTupleHashes)), - - % Verify database hash changed - ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) - end)]}. - -%%==================================================================== -%% Relation Operations Tests -%%==================================================================== - -clear_relation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database_with_tuples(), - {ok, RelationHash} = operations:get_relation_hash(DB, users), - - % Verify tuples exist - TupleHashes = operations:hashes_from_tuple(RelationHash), - ?assertEqual(2, length(TupleHashes)), - - % Clear relation - {atomic, {DB1, ClearedRelation}} = operations:clear_relation(DB, RelationHash), - - % Verify relation is empty - ?assertEqual(undefined, ClearedRelation#relation.tree), - NewTupleHashes = operations:hashes_from_tuple(ClearedRelation#relation.hash), - ?assertEqual([], NewTupleHashes), - - % Verify database hash changed - ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) - end)]}. - -retract_relation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database_with_tuples(), - - % Verify relation exists (along with built-in relations) - Relations = operations:get_relations(DB), - ?assert(lists:member(users, Relations)), - - % Retract relation - {atomic, DB1} = operations:retract_relation(DB, users), - - % Verify users relation was removed (built-in relations remain) - Relations1 = operations:get_relations(DB1), - ?assertNot(lists:member(users, Relations1)), - ?assert(lists:member(natural, Relations1)), - ?assert(lists:member(integer, Relations1)), - ?assert(lists:member(rational, Relations1)), - ?assertEqual({error, not_found}, operations:get_relation_hash(DB1, users)), - - % Verify database hash changed - ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) - end)]}. - -%%==================================================================== -%% Iterator Tests -%%==================================================================== - -iterator_basic_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database_with_tuples(), - - % Get iterator and retrieve tuples one by one - Iterator = operations:get_tuples_iterator(DB, users), - - % Get first tuple - {ok, Tuple1} = operations:next_tuple(Iterator), - ?assert(is_map(Tuple1)), - ?assert(maps:is_key(name, Tuple1)), - ?assert(maps:is_key(age, Tuple1)), - - % Get second tuple - {ok, Tuple2} = operations:next_tuple(Iterator), - ?assert(is_map(Tuple2)), - - % No more tuples - ?assertEqual(done, operations:next_tuple(Iterator)), - - operations:close_iterator(Iterator) - end)]}. - -iterator_collect_all_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database_with_tuples(), - - Iterator = operations:get_tuples_iterator(DB, users), - Tuples = operations:collect_all(Iterator), - - ?assertEqual(2, length(Tuples)), - - % Verify both tuples are present - Names = [maps:get(name, T) || T <- Tuples], - ?assert(lists:member("Alice", Names)), - ?assert(lists:member("Bob", Names)) - end)]}. - -iterator_empty_relation_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - DB = sample_database(), - - Iterator = operations:get_tuples_iterator(DB, users), - Tuples = operations:collect_all(Iterator), - - ?assertEqual([], Tuples) - end)]}. - -%%==================================================================== -%% Hash Consistency Tests -%%==================================================================== - -hash_determinism_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - % Same value should produce same hash - Hash1 = operations:hash(<<"test">>), - Hash2 = operations:hash(<<"test">>), - ?assertEqual(Hash1, Hash2), - - % Different values should produce different hashes - Hash3 = operations:hash(<<"different">>), - ?assertNotEqual(Hash1, Hash3) - end)]}. - -database_state_consistency_test_() -> - {setup, - fun setup_test_env/0, - fun(_) -> cleanup_test_env() end, - [?_test(begin - % Create two identical databases with same operations - DB1 = operations:create_database(db1), - {DB1_1, _} = operations:create_relation(DB1, users, #{name => string}), - {DB1_2, _} = operations:create_tuple(DB1_1, users, #{name => "Alice"}), - - DB2 = operations:create_database(db2), - {DB2_1, _} = operations:create_relation(DB2, users, #{name => string}), - {DB2_2, _} = operations:create_tuple(DB2_1, users, #{name => "Alice"}), - - % Relations should have the same hash (same schema and tuples) - {ok, RelHash1} = operations:get_relation_hash(DB1_2, users), - {ok, RelHash2} = operations:get_relation_hash(DB2_2, users), - ?assertEqual(RelHash1, RelHash2) - end)]}. diff --git a/test/provenance_test.erl b/test/provenance_test.erl deleted file mode 100644 index c98e372..0000000 --- a/test/provenance_test.erl +++ /dev/null @@ -1,420 +0,0 @@ --module(provenance_test). --include_lib("eunit/include/eunit.hrl"). --include("operations.hrl"). - -%%% Provenance & Lineage Tracking Test Suite -%%% -%%% Tests for tuple metadata tracking in relational operations. -%%% Metadata is ALWAYS tracked and included in every tuple via the nested 'meta' field: -%%% - Provenance: Tracks the immediate source of each attribute -%%% - Lineage: Tracks the complete operational history of tuple creation -%%% -%%% NOTE ON TUPLE ORDERING: -%%% These tests observe tuples in a specific order (e.g., Alice before Bob) because -%%% collect_all/1 currently returns results in Merkle tree traversal order for finite -%%% relations. This ordering is an IMPLEMENTATION DETAIL and is NOT guaranteed. -%%% Relations are unordered sets - the current order is based on how tuples were -%%% inserted and hashed into the Merkle tree. Future implementations may return tuples -%%% in different orders. Tests use lists:all/2 to verify properties hold for ALL tuples -%%% rather than relying on specific ordering. - -provenance_test_() -> - {foreach, - fun setup/0, - fun cleanup/1, - [ - fun test_base_provenance/1, - fun test_join_provenance/1, - fun test_join_with_conflicts_provenance/1, - fun test_equijoin_preserves_both_sources/1, - fun test_base_lineage/1, - fun test_join_lineage/1, - fun test_select_lineage/1, - fun test_project_lineage/1, - fun test_sort_lineage/1, - fun test_take_lineage/1, - fun test_multi_operation_pipeline_lineage/1, - fun test_theta_join_lineage/1, - fun test_complex_nested_lineage/1 - ]}. - -%%% Setup and Cleanup - -setup() -> - operations:setup(), - DB = operations:create_database(test_db), - - % Create employees relation - {DB1, _} = operations:create_relation(DB, employees, #{ - id => integer, - name => string, - dept_id => integer - }), - - {DB2, _} = operations:create_tuple(DB1, employees, #{id => 1, name => "Alice", dept_id => 10}), - {DB3, _} = operations:create_tuple(DB2, employees, #{id => 2, name => "Bob", dept_id => 20}), - - % Create departments relation - {DB4, _} = operations:create_relation(DB3, departments, #{ - dept_id => integer, - dept_name => string, - budget => integer - }), - - {DB5, _} = operations:create_tuple(DB4, departments, #{dept_id => 10, dept_name => "Engineering", budget => 100000}), - {DB6, _} = operations:create_tuple(DB5, departments, #{dept_id => 20, dept_name => "Sales", budget => 80000}), - - DB6. - -cleanup(_DB) -> - ok. - -%%% Base Provenance Tests - -test_base_provenance(DB) -> - % Query tuples (metadata always included) - Iter = operations:get_tuples_iterator(DB, employees, #{}), - Results = operations:collect_all(Iter), - - % All tuples should have correct provenance structure - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - maps:is_key(meta, T) andalso - begin - Meta = maps:get(meta, T), - maps:is_key(provenance, Meta) - end - end, Results)), - % Check ALL tuples have correct provenance mapping - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Prov = maps:get(provenance, Meta), - % All attributes should map to {employees, attr_name} - maps:get(id, Prov) =:= {employees, id} andalso - maps:get(name, Prov) =:= {employees, name} andalso - maps:get(dept_id, Prov) =:= {employees, dept_id} - end, Results)) - ]. - -%%% Join Provenance Tests - -test_join_provenance(DB) -> - % Create iterators (metadata always included) - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - % Join them - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - Results = operations:collect_all(JoinIter), - - % All results should have metadata with provenance - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> maps:is_key(meta, T) end, Results)), - % Check that ALL tuples have correct provenance structure - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Prov = maps:get(provenance, Meta), - % Employee attributes should come from employees - maps:get(id, Prov) =:= {employees, id} andalso - maps:get(name, Prov) =:= {employees, name} andalso - % Department attributes should come from departments - maps:get(dept_name, Prov) =:= {departments, dept_name} andalso - maps:get(budget, Prov) =:= {departments, budget} - end, Results)) - ]. - -test_join_with_conflicts_provenance(DB) -> - % Create relations with conflicting attribute names - {DB1, _} = operations:create_relation(DB, table_a, #{ - id => integer, - value => integer - }), - {DB2, _} = operations:create_tuple(DB1, table_a, #{id => 1, value => 100}), - - {DB3, _} = operations:create_relation(DB2, table_b, #{ - id => integer, - value => integer % Conflict! - }), - {DB4, _} = operations:create_tuple(DB3, table_b, #{id => 1, value => 200}), - - % Create iterators with provenance - AIter = operations:get_tuples_iterator(DB4, table_a, #{}), - BIter = operations:get_tuples_iterator(DB4, table_b, #{}), - - JoinIter = operations:equijoin_iterator(AIter, BIter, id), - Results = operations:collect_all(JoinIter), - - % Should be exactly one result tuple - ?_assertEqual(1, length(Results)), - - % Check provenance handles conflicts correctly - [Result] = Results, - Meta = maps:get(meta, Result), - Prov = maps:get(provenance, Meta), - - [ - % Left 'value' provenance - ?_assertEqual({table_a, value}, maps:get(value, Prov)), - % Right 'value' provenance (prefixed) - ?_assertEqual({table_b, value}, maps:get(right_value, Prov)), - % Join attribute from left side - ?_assertEqual({table_a, id}, maps:get(id, Prov)), - % Join attribute from right side (prefixed) - ?_assertEqual({table_b, id}, maps:get(right_id, Prov)) - ]. - -test_equijoin_preserves_both_sources(DB) -> - % Even though equijoin only keeps one dept_id value, - % provenance should track both sources - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - Results = operations:collect_all(JoinIter), - - % Check that ALL tuples have both dept_id sources in provenance - [ - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Prov = maps:get(provenance, Meta), - % Left side dept_id - maps:is_key(dept_id, Prov) andalso - % Right side dept_id (prefixed) - maps:is_key(right_dept_id, Prov) - end, Results)), - % Verify the sources are correct for ALL tuples - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Prov = maps:get(provenance, Meta), - maps:get(dept_id, Prov) =:= {employees, dept_id} andalso - maps:get(right_dept_id, Prov) =:= {departments, dept_id} - end, Results)) - ]. - -%%% Lineage Tests - -test_base_lineage(DB) -> - % Query tuples (metadata always included) - Iter = operations:get_tuples_iterator(DB, employees, #{}), - Results = operations:collect_all(Iter), - - % All tuples should have lineage showing base relation - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - Lineage =:= {base, employees} - end, Results)) - ]. - -test_join_lineage(DB) -> - % Create iterators (metadata always included) - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - % Join them - JoinIter = operations:equijoin_iterator(EmpIter, DeptIter, dept_id), - Results = operations:collect_all(JoinIter), - - % All results should have lineage showing join operation - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - % Should be a join of two base relations - case Lineage of - {join, dept_id, {base, employees}, {base, departments}} -> true; - _ -> false - end - end, Results)) - ]. - -%%% Comprehensive Lineage Tests - -test_select_lineage(DB) -> - % Test lineage through select (filter) operation - Iter = operations:get_tuples_iterator(DB, employees, #{}), - - Predicate = fun(T) -> maps:get(id, T, 0) =:= 1 end, - FilteredIter = operations:select_iterator(Iter, Predicate), - Results = operations:collect_all(FilteredIter), - - % Should have lineage: select wrapping base - [ - ?_assertEqual(1, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {select, Pred, {base, employees}} when is_function(Pred) -> true; - _ -> false - end - end, Results)) - ]. - -test_project_lineage(DB) -> - % Test lineage through project operation - Iter = operations:get_tuples_iterator(DB, employees, #{}), - ProjectedIter = operations:project_iterator(Iter, [name, dept_id]), - Results = operations:collect_all(ProjectedIter), - - % Should have lineage: project wrapping base - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {project, [name, dept_id], {base, employees}} -> true; - _ -> false - end - end, Results)) - ]. - -test_sort_lineage(DB) -> - % Test lineage through sort operation - Iter = operations:get_tuples_iterator(DB, employees, #{}), - - CompareFun = fun(A, B) -> maps:get(id, A, 0) =< maps:get(id, B, 0) end, - SortedIter = operations:sort_iterator(Iter, CompareFun), - Results = operations:collect_all(SortedIter), - - % Should have lineage: sort wrapping base - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {sort, Cmp, {base, employees}} when is_function(Cmp) -> true; - _ -> false - end - end, Results)) - ]. - -test_take_lineage(DB) -> - % Test lineage through take (limit) operation - Iter = operations:get_tuples_iterator(DB, employees, #{}), - TakeIter = operations:take_iterator(Iter, 1), - Results = operations:collect_all(TakeIter), - - % Should have lineage: take wrapping base - [ - ?_assertEqual(1, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {take, 1, {base, employees}} -> true; - _ -> false - end - end, Results)) - ]. - -test_multi_operation_pipeline_lineage(DB) -> - % Test complex pipeline: employees → select(id=1) → join(departments) → project([name, dept_name]) - - % 1. Start with employees base relation - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - - % 2. Filter to Alice (id=1) - Predicate = fun(T) -> maps:get(id, T, 0) =:= 1 end, - FilteredEmp = operations:select_iterator(EmpIter, Predicate), - - % 3. Join with departments - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - JoinedIter = operations:equijoin_iterator(FilteredEmp, DeptIter, dept_id), - - % 4. Project to [name, dept_name] - ProjectedIter = operations:project_iterator(JoinedIter, [name, dept_name]), - - Results = operations:collect_all(ProjectedIter), - - % Expected lineage: - % {project, [name, dept_name], - % {join, dept_id, - % {select, Pred, {base, employees}}, - % {base, departments}}} - - [ - ?_assertEqual(1, length(Results)), % Only Alice - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {project, [name, dept_name], - {join, dept_id, - {select, Pred, {base, employees}}, - {base, departments}}} when is_function(Pred) -> true; - _ -> false - end - end, Results)) - ]. - -test_theta_join_lineage(DB) -> - % Test lineage for theta-join operation - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - - Predicate = fun(Emp, Dept) -> - maps:get(dept_id, Emp) =:= maps:get(dept_id, Dept) - end, - - JoinIter = operations:theta_join_iterator(EmpIter, DeptIter, Predicate), - Results = operations:collect_all(JoinIter), - - % Should have theta_join lineage - [ - ?_assertEqual(2, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {theta_join, Pred, {base, employees}, {base, departments}} - when is_function(Pred) -> true; - _ -> false - end - end, Results)) - ]. - -test_complex_nested_lineage(DB) -> - % Test deeply nested lineage: - % employees → select(id=1) → project([name, dept_id]) → join(departments → select(budget>50000)) → take(1) - - % Left side: employees → select → project - EmpIter = operations:get_tuples_iterator(DB, employees, #{}), - FilteredEmp = operations:select_iterator(EmpIter, fun(T) -> maps:get(id, T, 0) =:= 1 end), - ProjectedEmp = operations:project_iterator(FilteredEmp, [name, dept_id]), - - % Right side: departments → select - DeptIter = operations:get_tuples_iterator(DB, departments, #{}), - FilteredDept = operations:select_iterator(DeptIter, fun(D) -> maps:get(budget, D, 0) > 50000 end), - - % Join both sides - JoinedIter = operations:equijoin_iterator(ProjectedEmp, FilteredDept, dept_id), - - % Take first result - TakeIter = operations:take_iterator(JoinedIter, 1), - - Results = operations:collect_all(TakeIter), - - % Expected lineage should be deeply nested - [ - ?_assertEqual(1, length(Results)), - ?_assert(lists:all(fun(T) -> - Meta = maps:get(meta, T), - Lineage = maps:get(lineage, Meta), - case Lineage of - {take, 1, - {join, dept_id, - {project, [name, dept_id], - {select, _, {base, employees}}}, - {select, _, {base, departments}}}} -> true; - _ -> false - end - end, Results)) - ]. diff --git a/test/query_pipeline_test.erl b/test/query_pipeline_test.erl deleted file mode 100644 index a76c2ff..0000000 --- a/test/query_pipeline_test.erl +++ /dev/null @@ -1,183 +0,0 @@ --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) -> - %% Naturals are built-in, no need to create them - - %% Take 100 and materialize - Pipeline = operations:get_tuples_iterator(DB, natural, #{value => {range, 0, 99}}), - {_DB2, Naturals100} = operations:materialize(DB, 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) - ]. |