From c4e1b573dacd67277ea9df1751574ef2dfb44601 Mon Sep 17 00:00:00 2001 From: Marcos Magueta Date: Thu, 4 Dec 2025 00:44:06 -0300 Subject: Infinite domains and membership rework (#22) --- src/generators.erl | 73 +++++++---- src/operations.erl | 351 ++++++++++++++++++++++++++++++-------------------- src/poc.erl | 167 ------------------------ src/query_planner.erl | 34 +++-- src/repl.erl | 46 +++---- src/visualizer.erl | 15 +-- src/xml_server.erl | 47 ++++--- 7 files changed, 327 insertions(+), 406 deletions(-) delete mode 100644 src/poc.erl (limited to 'src') diff --git a/src/generators.erl b/src/generators.erl index 9e682d3..37facc3 100644 --- a/src/generators.erl +++ b/src/generators.erl @@ -25,18 +25,18 @@ %%% %%% %%% Function relations reference domain relations in their schemas: -%%% ``` -%%% schema => #{a => integers, b => integers, sum => integers} -%%% ''' +%%% 
+%%% schema => #{a => integers, b => integers, sum => integers}
+%%%
%%% %%% == Reversibility == %%% %%% Function relations support bidirectional querying (like Prolog): %%% %%% %%% The generators use constraint analysis to determine which arguments @@ -45,9 +45,9 @@ %%% == Relational Composition == %%% %%% In the future, function relations will be used through joins: -%%% ``` +%%% 
 %%% Integer[A], Integer[B], Plus[A, B, Sum]
-%%% '''
+%%%
%%% %%% This corresponds to a three-way join where the join conditions %%% provide the constraints to each relation. @@ -62,12 +62,13 @@ -include("operations.hrl"). -export([ - naturals/1, - integers/1, - rationals/1, + boolean/1, + natural/1, + integer/1, + rational/1, make_range_generator/3, - constrained_naturals/2, - constrained_integers/2, + constrained_natural/2, + constrained_integer/2, %% Function relations plus/1, times/1, @@ -79,6 +80,28 @@ %%% Primitive Generators %%% ============================================================================ +%% @doc Generator for boolean domain (𝔹 = {true, false}). +%% +%% Generates the two boolean values. This is a finite immutable relation. +%% If constraints specify equality, only generates that value. +%% +%% @param Constraints Map of attribute constraints +%% @returns Generator function producing booleans +boolean(Constraints) -> + case maps:get(value, Constraints, unbounded) of + {eq, true} -> + make_singleton_generator(#{value => true}); + {eq, false} -> + make_singleton_generator(#{value => false}); + {in, Values} -> + %% Filter to only boolean values + BoolValues = [V || V <- Values, V =:= true orelse V =:= false], + make_membership_generator(BoolValues, fun(V) -> #{value => V} end); + _ -> + %% Enumerate all booleans: true, false + make_membership_generator([true, false], fun(V) -> #{value => V} end) + end. + %% @doc Generator for natural numbers (ℕ = {0, 1, 2, 3, ...}). %% %% Enumerates natural numbers starting from 0. If constraints specify a range, @@ -86,7 +109,7 @@ %% %% @param Constraints Map of attribute constraints %% @returns Generator function producing naturals -naturals(Constraints) -> +natural(Constraints) -> case extract_bounds(Constraints, value) of {range, Min, Max} when Min >= 0 -> make_range_generator(Min, Max, fun(N) -> #{value => N} end); @@ -130,7 +153,7 @@ naturals(Constraints) -> %% %% @param Constraints Map of attribute constraints %% @returns Generator function producing integers -integers(Constraints) -> +integer(Constraints) -> case extract_bounds(Constraints, value) of {range, Min, Max} -> make_integer_range_generator(Min, Max); @@ -158,7 +181,7 @@ integers(Constraints) -> %% %% @param Constraints Map of attribute constraints %% @returns Generator function producing rationals -rationals(Constraints) -> +rational(Constraints) -> %% Stern-Brocot tree enumeration %% Start with mediant tree: 0/1, 1/1, then generate mediants InitialState = {queue:from_list([{0, 1}, {1, 1}]), {0, 1}, {1, 0}}, @@ -320,15 +343,15 @@ make_sb_gen({Queue, {LA, LB}, {RA, RB}}) -> %%% Constrained Generators (Public API) %%% ============================================================================ -%% @doc Create a constrained naturals generator. --spec constrained_naturals(non_neg_integer(), non_neg_integer()) -> generator_fun(). -constrained_naturals(Min, Max) -> - naturals(#{value => {range, Min, Max}}). +%% @doc Create a constrained natural generator. +-spec constrained_natural(non_neg_integer(), non_neg_integer()) -> generator_fun(). +constrained_natural(Min, Max) -> + natural(#{value => {range, Min, Max}}). -%% @doc Create a constrained integers generator. --spec constrained_integers(integer(), integer()) -> generator_fun(). -constrained_integers(Min, Max) -> - integers(#{value => {range, Min, Max}}). +%% @doc Create a constrained integer generator. +-spec constrained_integer(integer(), integer()) -> generator_fun(). +constrained_integer(Min, Max) -> + integer(#{value => {range, Min, Max}}). %%% ============================================================================ %%% Function Relations diff --git a/src/operations.erl b/src/operations.erl index 36fb7e2..4a492f4 100644 --- a/src/operations.erl +++ b/src/operations.erl @@ -43,7 +43,7 @@ hash/1, create_database/1, create_relation/3, - create_infinite_relation/2, + create_immutable_relation/2, create_tuple/3, retract_tuple/3, retract_tuple/4, @@ -101,7 +101,7 @@ setup() -> {type, set} ]), mnesia:create_table(relation, [ - {attributes, [hash, name, tree, schema, constraints, cardinality, generator, provenance]}, + {attributes, [hash, name, tree, schema, constraints, cardinality, generator, membership_criteria, mutability, provenance]}, {disc_copies, [node()]}, {type, set} ]), @@ -140,11 +140,11 @@ hash(Value) -> %% All operations execute within a Mnesia transaction for ACID guarantees. %% %% == Example == -%% ``` +%% 
 %% DB = operations:create_database(my_db),
 %% {DB1, _} = operations:create_relation(DB, users, #{name => string, age => integer}),
 %% {DB2, _} = operations:create_tuple(DB1, users, #{name => "Alice", age => 30}).
-%% '''
+%%
%% %% @param Database `#database_state{}' record %% @param RelationName Atom naming the relation @@ -154,6 +154,22 @@ hash(Value) -> %% @see create_relation/3 %% @see get_tuples_iterator/2 create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Database, database_state) -> + %% Check if relation is immutable before attempting insert + CurrentRelationHash = maps:get(RelationName, Database#database_state.relations), + [RelationRecord] = mnesia:dirty_read(relation, CurrentRelationHash), + + 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) +create_tuple_internal(Database, RelationName, Tuple, _RelationRecord) -> F = fun() -> %% Step 1: Store each attribute value and build attribute_map AttributeMap = maps:map(fun(_AttrName, Value) -> @@ -385,11 +401,11 @@ retract_relation(Database, Name, Transact) -> %% contain different tuples. %% %% == Example == -%% ``` +%% 
 %% DB = operations:create_database(my_db),
 %% Schema = #{name => string, age => integer, email => string},
 %% {DB1, _Rel} = operations:create_relation(DB, users, Schema).
-%% '''
+%%
%% %% @param Database `#database_state{}' record %% @param Name Atom naming the new relation @@ -412,10 +428,12 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st name = Name, tree = undefined, schema = Definition, - constraints = #{}, % No constraints by default - cardinality = {finite, 0}, % Empty relation - generator = undefined, % Finite relation has no generator - provenance = {base, Name} % Base relation + constraints = #{}, % No constraints by default + cardinality = {finite, 0}, % Empty relation + generator = undefined, % Finite relation has no generator + membership_criteria = #{}, % No membership criteria by default + mutability = mutable, % Mutable by default + provenance = {base, Name} % Base relation }, mnesia:write(relation, NewRelation, write), @@ -456,9 +474,9 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st %% All changes are committed to Mnesia within a transaction. %% %% == Example == -%% ``` +%% 
 %% DB = operations:create_database(my_app).
-%% '''
+%%
%% %% @param Name Atom identifying the database %% @returns `#database_state{}' record @@ -466,17 +484,65 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st %% @see setup/0 %% @see create_relation/3 create_database(Name) -> - Entry = #database_state{ + DB = #database_state{ name = Name, hash = <<>>, tree = undefined, relations = #{}, timestamp = erlang:timestamp() }, + %% Standard immutable relations (domains and their predicates) + StandardTypeRelations = [ + %% Boolean domain - finite, immutable + #immutable_relation_spec{ + name = boolean, + schema = #{value => boolean}, + generator = {generators, boolean}, + membership_criteria = #{value => {in, [true, false]}}, + cardinality = {finite, 2} + }, + %% Natural numbers - infinite, immutable + #immutable_relation_spec{ + name = natural, + schema = #{value => natural}, + generator = {generators, natural}, + membership_criteria = #{value => {'and', {gte, 0}, is_integer}}, + cardinality = aleph_zero + }, + %% Integers - infinite, immutable + #immutable_relation_spec{ + name = integer, + schema = #{value => integer}, + generator = {generators, integer}, + membership_criteria = #{value => is_integer}, + cardinality = aleph_zero + }, + %% Rationals - infinite, immutable + #immutable_relation_spec{ + name = rational, + schema = #{numerator => integer, denominator => integer}, + generator = {generators, rational}, + membership_criteria = #{denominator => {neq, 0}}, + cardinality = aleph_zero + } + %% Reals - TODO: implement + %% #immutable_relation_spec{ + %% name = reals, + %% schema = #{value => reals}, + %% generator = {generators, reals}, + %% membership_criteria = #{value => is_float}, + %% cardinality = continuum + %% } + ], + Folder = fun (Elem, AccDB) -> + {NextDB, _} = operations:create_immutable_relation(AccDB, Elem), + NextDB + end, + StandardDB = lists:foldl(Folder, DB, StandardTypeRelations), {atomic, ok} = mnesia:transaction(fun () -> - mnesia:write(database_state, Entry, write) - end), - Entry. + mnesia:write(database_state, StandardDB, write) + end), + StandardDB. %% @doc Create an infinite relation with a generator. %% @@ -493,46 +559,49 @@ create_database(Name) -> %% %% %% == Example == -%% ``` -%% %% Create infinite relation of natural numbers -%% {DB1, Naturals} = operations:create_infinite_relation(DB, #{ -%% name => naturals, -%% schema => #{value => natural}, -%% cardinality => aleph_zero, -%% generator => {primitive, naturals}, -%% constraints => #{value => {gte, 0}} +%% 
+%% %% Create immutable relation of natural numbers
+%% {DB1, Naturals} = operations:create_immutable_relation(DB, #immutable_relation_spec{
+%%     name = naturals,
+%%     schema = #{value => naturals},
+%%     generator = {generators, naturals},
+%%     membership_criteria = #{value => {'and', {gte, 0}, is_integer}},
+%%     cardinality = aleph_zero
 %% }).
 %%
 %% %% Query with bounds
 %% Iterator = operations:get_tuples_iterator(DB1, naturals,
 %%     #{value => {range, 0, 100}}).
-%% '''
+%%
%% %% @param Database `#database_state{}' record -%% @param Spec Map with keys: name, schema, cardinality, generator, constraints -%% @returns `{UpdatedDatabase, NewRelation}' tuple +%% @param Specification `#immutable_relation_spec{}' record +%% @returns `{UpdatedDatabase, NewRelation}' %% %% @see create_relation/3 %% @see get_tuples_iterator/3 -create_infinite_relation(Database, Spec) when is_record(Database, database_state) -> - Name = maps:get(name, Spec), - Schema = maps:get(schema, Spec), - Cardinality = maps:get(cardinality, Spec, aleph_zero), - GeneratorSpec = maps:get(generator, Spec), - Constraints = maps:get(constraints, Spec, #{}), +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, F = fun() -> - %% Hash is based on generator specification - RelationHash = hash({Name, Schema, GeneratorSpec, Cardinality}), + RelationHash = hash({Name, Schema, undefined}), NewRelation = #relation{ hash = RelationHash, name = Name, - tree = undefined, % Infinite relations have no merkle tree + tree = undefined, % Immutable relations have no merkle tree schema = Schema, - constraints = Constraints, + constraints = #{}, % No constraints by default cardinality = Cardinality, - generator = GeneratorSpec, + generator = Generator, + membership_criteria = MembershipCriteria, + mutability = immutable, % Always immutable provenance = {base, Name} }, mnesia:write(relation, NewRelation, write), @@ -641,13 +710,13 @@ hashes_from_tuple(RelationHash) -> %% For infinite relations, returns first N elements by generator order. %% %% == Example == -%% ``` +%% 
 %% %% Take 100 naturals (returns {0, 1, 2, ..., 99})
 %% {DB1, Naturals100} = operations:take(DB, naturals, 100).
 %%
 %% %% Can compose with other operators
 %% Iterator = operations:get_tuples_iterator(DB1, naturals100).
-%% '''
+%%
%% %% @param Database `#database_state{}' record %% @param RelationName Atom naming the source relation @@ -672,20 +741,31 @@ take(Database, RelationName, N) when is_record(Database, database_state), is_int %% Create take relation TakeName = list_to_atom(atom_to_list(RelationName) ++ "_take_" ++ integer_to_list(N)), + TakeHash = hash({take, RelationName, N}), + TakeRelation = #relation{ - hash = hash({take, RelationName, N}), + 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} }, - %% Note: We don't persist take relations to Mnesia for now - %% They are ephemeral views - {Database, TakeRelation} + %% 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. @@ -702,14 +782,14 @@ take(Database, RelationName, N) when is_record(Database, database_state), is_int %% == Options Format == %% %% Nested format (preferred): -%% ``` +%% 
 %% #{constraints => #{age => {gt, 30}}}
-%% '''
+%%
%% %% Flat format (backward compatible): -%% ``` +%% 
 %% #{age => {gt, 30}}
-%% '''
+%%
%% %% == Constraints == %% @@ -723,7 +803,7 @@ take(Database, RelationName, N) when is_record(Database, database_state), is_int %% %% %% == Example == -%% ``` +%% 
 %% %% Iterate employees with age > 30 (metadata always included)
 %% Iterator = operations:get_tuples_iterator(DB, employees,
 %%     #{constraints => #{age => {gt, 30}}}).
@@ -734,7 +814,7 @@ take(Database, RelationName, N) when is_record(Database, database_state), is_int
 %% %%     provenance => #{id => {employees, id}, ...},
 %% %%     lineage => {select, Fun, {base, employees}}
 %% %%   }}
-%% '''
+%%
%% %% @param Database `#database_state{}' record %% @param RelationName Atom naming the relation to iterate @@ -758,15 +838,28 @@ get_tuples_iterator(Database, RelationName, Options) when is_record(Database, da %% Metadata tracking is ALWAYS enabled case Relation#relation.cardinality of - {finite, _} -> - %% Finite relation: use tuple hashes + {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); _ -> - %% Infinite relation: use generator - Generator = instantiate_generator(Relation#relation.generator, Constraints), - spawn(fun() -> generator_iterator_loop(Generator, RelationName, true) 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 end end. @@ -786,11 +879,11 @@ get_tuples_iterator(Database, RelationName, Options) when is_record(Database, da %% Note: For infinite relations, use `get_tuples_iterator/3' with constraints. %% %% == Example == -%% ``` +%% 
 %% Iterator = operations:get_tuples_iterator(DB, users),
 %% {ok, Tuple} = operations:next_tuple(Iterator),
 %% operations:close_iterator(Iterator).
-%% '''
+%%
%% %% @param Database `#database_state{}' record %% @param RelationName Atom naming the relation to iterate @@ -842,8 +935,7 @@ close_iterator(IteratorPid) -> ok. %% @private -%% @doc Iterator loop implementation (internal). -%% +%% Iterator loop implementation (internal). %% This is the process loop for the Volcano Iterator Model. It maintains a list %% of tuple hashes and resolves them lazily when requested. %% @@ -886,11 +978,11 @@ tuple_iterator_loop([TupleHash | Rest], RelationName, EnableProvenance) -> %% of lazy evaluation. Only use for small relations or testing. %% %% == Example == -%% ``` +%% 
 %% Iterator = operations:get_tuples_iterator(DB, users),
 %% AllTuples = operations:collect_all(Iterator).
 %% %% Iterator is automatically closed
-%% '''
+%%
%% %% @param IteratorPid Pid returned from `get_tuples_iterator/2' %% @returns List of tuple maps, `{error, Reason, PartialResults}' on timeout @@ -921,11 +1013,11 @@ collect_all(IteratorPid, Acc) -> %% satisfy the predicate function. %% %% == Example == -%% ``` +%% 
 %% BaseIter = get_tuples_iterator(DB, employees, #{}),
-%% FilteredIter = select_iterator(BaseIter, fun(E) -> maps:get(age, E) > 30 end),
+%% FilteredIter = select_iterator(BaseIter, fun(E) -> maps:get(age, E) > 30 end),
 %% Tuples = collect_all(FilteredIter).
-%% '''
+%%
%% %% @param ChildIterator Iterator process to filter %% @param Predicate Function: tuple() -> boolean() @@ -967,11 +1059,11 @@ select_loop(ChildPid, Predicate) -> %% attributes. This is the relational projection operator (π). %% %% == Example == -%% ``` +%% 
 %% BaseIter = get_tuples_iterator(DB, employees, #{}),
 %% ProjectedIter = project_iterator(BaseIter, [name, age]),
 %% Tuples = collect_all(ProjectedIter).
-%% '''
+%%
%% %% @param ChildIterator Iterator process to project %% @param Attributes List of attribute names to keep @@ -1030,13 +1122,13 @@ project_loop(ChildPid, Attributes) -> %% produces finite tuples (via constraints or take). %% %% == Example == -%% ``` +%% 
 %% BaseIter = get_tuples_iterator(DB, employees, #{}),
-%% SortedIter = sort_iterator(BaseIter, fun(A, B) ->
-%%     maps:get(age, A) =< maps:get(age, B)
+%% SortedIter = sort_iterator(BaseIter, fun(A, B) ->
+%%     maps:get(age, A) =< maps:get(age, B)
 %% end),
 %% Tuples = collect_all(SortedIter).
-%% '''
+%%
%% %% @param ChildIterator Iterator process to sort %% @param CompareFun Function: (tuple(), tuple()) -> boolean() @@ -1075,11 +1167,11 @@ sorted_emit_loop([Tuple | Rest]) -> %% then closes the child and signals done. %% %% == Example == -%% ``` +%% 
 %% BaseIter = get_tuples_iterator(DB, naturals, #{value => {range, 0, 1000}}),
 %% LimitedIter = take_iterator(BaseIter, 10),
 %% Tuples = collect_all(LimitedIter).  % Gets exactly 10 tuples
-%% '''
+%%
%% %% @param ChildIterator Iterator process to limit %% @param N Maximum number of tuples to emit @@ -1132,12 +1224,12 @@ take_iter_loop(ChildPid, _Limit, _Count, _OriginalN) -> %% Future: Hash join for better performance. %% %% == Example == -%% ``` +%% 
 %% %% Join employees with departments on dept_id
 %% LeftIter = operations:get_tuples_iterator(DB, employees, #{}),
 %% RightIter = operations:get_tuples_iterator(DB, departments, #{}),
 %% JoinIter = operations:equijoin_iterator(LeftIter, RightIter, dept_id)
-%% '''
+%%
%% %% @param LeftIterator Iterator for left relation %% @param RightIterator Iterator for right relation @@ -1153,13 +1245,13 @@ equijoin_iterator(LeftIterator, RightIterator, JoinAttribute) -> %% is evaluated. If true, the tuples are merged and emitted. %% %% == Example == -%% ``` -%% %% Join where employee.age > department.min_age -%% Predicate = fun(EmpTuple, DeptTuple) -> -%% maps:get(age, EmpTuple) > maps:get(min_age, DeptTuple) +%% 
+%% %% Join where employee.age > department.min_age
+%% Predicate = fun(EmpTuple, DeptTuple) ->
+%%     maps:get(age, EmpTuple) > maps:get(min_age, DeptTuple)
 %% end,
 %% JoinIter = operations:theta_join_iterator(LeftIter, RightIter, Predicate)
-%% '''
+%%
%% %% @param LeftIterator Iterator for left relation %% @param RightIterator Iterator for right relation @@ -1179,17 +1271,17 @@ theta_join_iterator(LeftIterator, RightIterator, Predicate) -> %% iterator and stores them as a new finite relation in the database. %% %% == Example == -%% ``` +%% 
 %% %% Build lazy pipeline
 %% Pipeline = get_tuples_iterator(DB, employees, #{})
-%%            |> select_iterator(fun(E) -> maps:get(age, E) > 30 end)
-%%            |> sort_iterator(fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end)
-%%            |> take_iterator(10)
-%%            |> project_iterator([name, age]),
+%%            |> select_iterator(fun(E) -> maps:get(age, E) > 30 end)
+%%            |> sort_iterator(fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end)
+%%            |> take_iterator(10)
+%%            |> project_iterator([name, age]),
 %%
 %% %% Materialize into new relation
 %% {DB1, SeniorEmployees} = materialize(DB, Pipeline, senior_employees).
-%% '''
+%%
%% %% @param Database Current database state %% @param SourceIterator Iterator process (pipeline endpoint) @@ -1219,12 +1311,12 @@ materialize(Database, SourceIterator, ResultName) when is_record(Database, datab end. %% @private -%% @doc Infer schema from a tuple. +%% Infer schema from a tuple. infer_schema_from_tuple(Tuple) when is_map(Tuple) -> maps:map(fun(_AttrName, Value) -> infer_type(Value) end, Tuple). %% @private -%% @doc Infer type from value. +%% Infer type from value. infer_type(Value) when is_integer(Value) -> integer; infer_type(Value) when is_float(Value) -> float; infer_type(Value) when is_binary(Value) -> binary; @@ -1234,7 +1326,7 @@ infer_type(Value) when is_boolean(Value) -> boolean; infer_type(_) -> term. %% @private -%% @doc Insert multiple tuples into a relation. +%% Insert multiple tuples into a relation. insert_all_tuples(DB, RelationName, Tuples) -> lists:foldl( fun(Tuple, {DBacc, _RelAcc}) -> @@ -1248,45 +1340,40 @@ insert_all_tuples(DB, RelationName, Tuples) -> %%% Generator Support Functions %%% ============================================================================ -%% @private -%% @doc Instantiate a generator from a generator specification. -%% +%% 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}). +%% instantiate_generator({primitive, naturals}, Constraints) -> +%% generators:naturals(Constraints); +%% instantiate_generator({primitive, integers}, Constraints) -> +%% generators:integers(Constraints); +%% instantiate_generator({primitive, rationals}, Constraints) -> +%% generators:rationals(Constraints); +%% instantiate_generator({primitive, plus}, Constraints) -> +%% generators:plus(Constraints); +%% instantiate_generator({primitive, times}, Constraints) -> +%% generators:times(Constraints); +%% instantiate_generator({primitive, minus}, Constraints) -> +%% generators:minus(Constraints); +%% instantiate_generator({primitive, divide}, Constraints) -> +%% generators:divide(Constraints); +%% instantiate_generator({custom, GeneratorFun}, Constraints) -> +%% GeneratorFun(Constraints); +%% instantiate_generator({take, RelationName, N}, Constraints) -> +%% %% Take generator: wrap another generator with limit +%% %% This is a simplified version - full implementation would look up the base relation +%% make_take_generator(RelationName, N, Constraints); +%% instantiate_generator(Other, _) -> +%% erlang:error({unknown_generator, Other}). %% @private -%% @doc Generator iterator loop for infinite relations. -%% +%% Generator iterator loop for infinite relations. %% Similar to tuple_iterator_loop but works with generator functions instead %% of tuple hashes. -%% -%% @param Generator Generator function generator_iterator_loop(Generator, RelationName, EnableProvenance) -> receive {next, Caller} -> @@ -1306,8 +1393,7 @@ generator_iterator_loop(Generator, RelationName, EnableProvenance) -> end. %% @private -%% @doc Equijoin loop: nested loop join on attribute equality. -%% +%% Equijoin loop: nested loop join on attribute equality. %% Strategy: %% 1. Collect all tuples from right iterator into memory %% 2. For each left tuple, scan right tuples for matches @@ -1375,8 +1461,7 @@ equijoin_emit_buffered(LeftIter, RightTuples, JoinAttr, []) -> equijoin_emit_loop(LeftIter, RightTuples, JoinAttr). %% @private -%% @doc Theta-join loop: nested loop join with predicate. -%% +%% Theta-join loop: nested loop join with predicate. %% @param LeftIter Left iterator process %% @param RightIter Right iterator process %% @param Pred Predicate function fun(LeftTuple, RightTuple) -> boolean() @@ -1427,8 +1512,7 @@ theta_join_emit_buffered(LeftIter, RightTuples, Pred, []) -> theta_join_emit_loop(LeftIter, RightTuples, Pred). %% @private -%% @doc Wrap existing lineage with a new operation. -%% +%% 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. %% @@ -1457,8 +1541,7 @@ wrap_lineage(Tuple, OpInfo) -> end. %% @private -%% @doc Add base provenance and lineage to a tuple from a relation. -%% +%% 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", @@ -1481,8 +1564,7 @@ add_base_provenance(Tuple, RelationName) -> }, Tuple). %% @private -%% @doc Merge two tuples for join result, including metadata. -%% +%% 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. %% @@ -1560,18 +1642,3 @@ merge_tuples(LeftTuple, RightTuple, JoinInfo) -> _ -> maps:put(meta, MergedMeta, MergedData) end. -%% @private -%% @doc Create a take generator that limits another generator. -make_take_generator(_RelationName, N, _Constraints) -> - %% Simplified version: just count to N - make_take_gen(0, N). - -make_take_gen(Current, Max) when Current < Max -> - fun(next) -> - Tuple = #{value => Current}, - NextGen = make_take_gen(Current + 1, Max), - {value, Tuple, NextGen} - end; -make_take_gen(_, _) -> - fun(_) -> done end. - diff --git a/src/poc.erl b/src/poc.erl deleted file mode 100644 index cee0965..0000000 --- a/src/poc.erl +++ /dev/null @@ -1,167 +0,0 @@ --module(poc). --export([test/0, setup/0]). - -test() -> - io:format("~nVolcano Iterator~n~n"), - %% Setup in-memory "database" (simulating Mnesia) - io:format("Setting up content-addressed storage...~n"), - Storage = setup(), - %% Insert data with automatic deduplication - io:format("Inserting products (note 'Soap' is stored only once)...~n"), - {Storage2, SoapHash} = store_value(Storage, "Soap"), - {Storage3, Price1Hash} = store_value(Storage2, 1.0), - {Storage4, BazookaHash} = store_value(Storage3, "Bazooka"), - {Storage5, Price2Hash} = store_value(Storage4, 413.0), - {Storage6, _SoapHash2} = store_value(Storage5, "Soap"), % Duplicate on purpose - {Storage7, Price3Hash} = store_value(Storage6, 50.0), - io:format("Unique values stored: ~p~n", [maps:size(maps:get(values, Storage7))]), - io:format("(Expected: 5, not 6 becase 'Soap' got deduplicated)~n~n"), - - Tuple1 = #{name => SoapHash, price => Price1Hash}, - Tuple2 = #{name => BazookaHash, price => Price2Hash}, - Tuple3 = #{name => SoapHash, price => Price3Hash}, - Tuples = [Tuple1, Tuple2, Tuple3], - - io:format("Created 3 product tuples (referencing hashes)~n"), - io:format("Tuple1: #{name => ~s, price => ~s}~n", - [short_hash(SoapHash), short_hash(Price1Hash)]), - io:format("Tuple2: #{name => ~s, price => ~s}~n", - [short_hash(BazookaHash), short_hash(Price2Hash)]), - io:format("Tuple3: #{name => ~s, price => ~s}~n~n", - [short_hash(SoapHash), short_hash(Price3Hash)]), - - io:format("Building query pipeline (Volcano Model):~n"), - io:format("Scan -> SELECT(price =< 100) -> Project(name)~n~n"), - - ScanPid = spawn(fun() -> scan_iterator(Tuples, Storage7) end), - - SelectPid = spawn(fun() -> - select_iterator(ScanPid, Storage7, fun(#{price := P}) -> P =< 100.0 end) - end), - - ProjectPid = spawn(fun() -> - project_iterator(SelectPid, [name]) - end), - - io:format("Pulling results (on-demand, lazy evaluation):~n"), - Results = pull_all(ProjectPid), - - io:format("~n"), - lists:foreach(fun(#{name := Name}) -> - io:format("-> #{name => ~p}~n", [Name]) - end, Results), - ok. - -setup() -> - #{values => #{}}. % Hash => Value map - -store_value(Storage, Value) -> - Hash = value_hash(Value), - Values = maps:get(values, Storage), - case maps:is_key(Hash, Values) of - true -> - io:format("[DEDUP] Value ~p already exists (hash: ~s)~n", - [Value, short_hash(Hash)]), - {Storage, Hash}; - false -> - io:format("[STORE] Value ~p (hash: ~s)~n", - [Value, short_hash(Hash)]), - NewValues = maps:put(Hash, Value, Values), - {Storage#{values => NewValues}, Hash} - end. - -get_value(Storage, Hash) -> - Values = maps:get(values, Storage), - maps:get(Hash, Values). - -value_hash(Value) -> - %% Simple hash for demo (in production: crypto:hash(sha256, term_to_binary(Value))) - erlang:phash2(Value). - -short_hash(Hash) -> - lists:flatten(io_lib:format("~8.16.0B", [Hash])). - -scan_iterator([], _Storage) -> - receive - {next, Caller} -> Caller ! done - end; -scan_iterator([TupleWithHashes | Rest], Storage) -> - receive - {next, Caller} -> - %% Unpacks all the hashes from each tuple - %% later we gotta use this on the merkle tree - %% for now it's just silly and inneficient - ResolvedTuple = maps:map(fun(_Attr, Hash) -> - get_value(Storage, Hash) - end, TupleWithHashes), - io:format("[SCAN] Emitting tuple: ~p~n", [ResolvedTuple]), - Caller ! {tuple, ResolvedTuple}, - scan_iterator(Rest, Storage) - end. - -select_iterator(SourcePid, Storage, Predicate) -> - receive - {next, Caller} -> - SourcePid ! {next, self()}, - receive - done -> - Caller ! done; - {tuple, Tuple} -> - case Predicate(Tuple) of - true -> - io:format("[SELECT] Pass: ~p~n", [Tuple]), - Caller ! {tuple, Tuple}, - select_iterator(SourcePid, Storage, Predicate); - false -> - io:format("[SELECT] Reject: ~p~n", [Tuple]), - %% Ignore this dude, and lock the process again - select_iterator_loop(SourcePid, Storage, Predicate, Caller) - end - end - end. - -select_iterator_loop(SourcePid, Storage, Predicate, Caller) -> - SourcePid ! {next, self()}, - receive - done -> - Caller ! done; - {tuple, Tuple} -> - case Predicate(Tuple) of - true -> - io:format("[SELECT] Pass: ~p~n", [Tuple]), - Caller ! {tuple, Tuple}, - select_iterator(SourcePid, Storage, Predicate); - false -> - io:format("[SELECT] Reject: ~p~n", [Tuple]), - select_iterator_loop(SourcePid, Storage, Predicate, Caller) - end - end. - -project_iterator(SourcePid, Attributes) -> - receive - {next, Caller} -> - SourcePid ! {next, self()}, - receive - done -> - Caller ! done; - {tuple, Tuple} -> - ProjectedTuple = maps:with(Attributes, Tuple), - io:format("[PROJECT] ~p -> ~p~n", [Tuple, ProjectedTuple]), - Caller ! {tuple, ProjectedTuple}, - project_iterator(SourcePid, Attributes) - end - end. - -pull_all(IteratorPid) -> - pull_all(IteratorPid, []). - -pull_all(IteratorPid, Acc) -> - IteratorPid ! {next, self()}, - receive - done -> - lists:reverse(Acc); - {tuple, Tuple} -> - pull_all(IteratorPid, [Tuple | Acc]) - after 1000 -> - {error, timeout} - end. diff --git a/src/query_planner.erl b/src/query_planner.erl index e6f2324..9d9d2bc 100644 --- a/src/query_planner.erl +++ b/src/query_planner.erl @@ -7,8 +7,7 @@ %%% == Query DSL Syntax == %%% %%% The DSL uses nested tuples to represent relational operations: -%%% -%%% ``` +%%% 
 %%% % Scan relation (base case)
 %%% {scan, employees}
 %%%
@@ -16,7 +15,7 @@
 %%% {relation, employees}
 %%%
 %%% % Selection (filter)
-%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end}
+%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end}
 %%%
 %%% % Projection
 %%% {project, {scan, employees}, [name, age]}
@@ -28,10 +27,10 @@
 %%% {theta_join,
 %%%   {scan, employees},
 %%%   {scan, departments},
-%%%   fun(L, R) -> maps:get(dept_id, L) =:= maps:get(id, R) end}
+%%%   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, {scan, employees}, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end}
 %%%
 %%% % Take (limit)
 %%% {take, {scan, employees}, 10}
@@ -46,23 +45,22 @@
 %%%       {scan, employees},
 %%%       {scan, departments},
 %%%       dept_id},
-%%%     fun(T) -> maps:get(age, T) > 30 end},
+%%%     fun(T) -> maps:get(age, T) > 30 end},
 %%%   [name, dept_name]}
-%%% ```
+%%%
%%% %%% == Usage == -%%% -%%% ``` +%%% 
 %%% % Prepare a query plan
 %%% Plan = query_planner:prepare({select, {scan, employees},
-%%%                                fun(T) -> maps:get(age, T) > 30 end}).
+%%%                                fun(T) -> maps:get(age, T) > 30 end}).
 %%%
 %%% % Execute and get iterator
 %%% Iter = query_planner:execute(DB, Plan).
 %%%
 %%% % Collect all results
 %%% Results = query_planner:collect(DB, Plan).
-%%% ```
+%%%
%%% %%% @author Nekoma Team %%% @copyright 2025 @@ -236,8 +234,18 @@ compile_to_iterator(DB, {sort, SubPlan, Comparator}) -> operations:sort_iterator(SubIter, Comparator); compile_to_iterator(DB, {take, SubPlan, N}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:take_iterator(SubIter, 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; compile_to_iterator(DB, {rename, OldAttr, NewAttr, SubPlan}) -> SubIter = compile_to_iterator(DB, SubPlan), diff --git a/src/repl.erl b/src/repl.erl index dc1e2c6..c61ebfe 100644 --- a/src/repl.erl +++ b/src/repl.erl @@ -5,8 +5,7 @@ %%% results and working with prepared statements. %%% %%% == Quick Start == -%%% -%%% ``` +%%% 
 %%% % Start the system
 %%% repl:start().
 %%%
@@ -14,20 +13,19 @@
 %%% DB = repl:example_db().
 %%%
 %%% % Execute a query
-%%% repl:q(DB, {select, {relation, employees}, fun(T) -> maps:get(age, T) > 30 end}).
+%%% repl:q(DB, {select, {relation, employees}, fun(T) -> maps:get(age, T) > 30 end}).
 %%%
 %%% % Explain a query plan
 %%% repl:explain({project, {relation, employees}, [name, age]}).
-%%% ```
+%%%
%%% %%% == Query Syntax Examples == -%%% -%%% ``` +%%% 
 %%% % Scan relation
 %%% {scan, employees}
 %%%
 %%% % Filter
-%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end}
+%%% {select, {scan, employees}, fun(T) -> maps:get(age, T) > 30 end}
 %%%
 %%% % Project
 %%% {project, {scan, employees}, [name, age]}
@@ -47,11 +45,11 @@
 %%%           {scan, employees},
 %%%           {scan, departments},
 %%%           dept_id},
-%%%         fun(T) -> maps:get(age, T) > 30 end},
+%%%         fun(T) -> maps:get(age, T) > 30 end},
 %%%       [name, dept_name, age]},
-%%%     fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end},
+%%%     fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end},
 %%%   5}
-%%% ```
+%%%
%%% %%% @author Nekoma Team %%% @copyright 2025 @@ -121,19 +119,15 @@ example_db() -> {DB8, _} = operations:create_tuple(DB7, departments, #{dept_id => 10, dept_name => "Engineering", budget => 100000}), {DB9, _} = operations:create_tuple(DB8, departments, #{dept_id => 20, dept_name => "Sales", budget => 80000}), {DB10, _} = operations:create_tuple(DB9, departments, #{dept_id => 30, dept_name => "Marketing", budget => 90000}), - {DB11, _} = operations:create_infinite_relation(DB10, #{ - name => naturals, - schema => #{value => integer}, - cardinality => aleph_zero, - generator => {primitive, naturals}, - constraints => #{value => {gte, 0}} - }), + + %% Note: natural, integer, rational, and boolean are now built-in to every database io:format("Example database created with:~n"), io:format(" - employees (5 tuples)~n"), - io:format(" - departments (3 tuples)~n~n"), + io:format(" - departments (3 tuples)~n"), + io:format(" - Built-in immutable relations: boolean, natural, integer, rational~n~n"), - DB11. + DB10. %% @doc Execute a query and pretty-print results (default table mode). %% @@ -178,11 +172,11 @@ q(DB, Plan, Mode) -> %% @returns List of result tuples %% %% == Example == -%% ``` +%% 
 %% Results = repl:query(DB, {scan, employees}).
-%% FilteredResults = lists:filter(fun(T) -> maps:get(age, T) > 30 end, Results).
+%% FilteredResults = lists:filter(fun(T) -> maps:get(age, T) > 30 end, Results).
 %% repl:show(FilteredResults, tree).
-%% ```
+%%
-spec query(term(), query_planner:query_plan()) -> [map()]. query(DB, Plan) -> PreparedPlan = query_planner:prepare(Plan), @@ -190,7 +184,7 @@ query(DB, Plan) -> %% @doc Display results using default visualization mode (table). %% -%% Takes a list of tuples (e.g., from `query/2`) and displays them +%% Takes a list of tuples (e.g., from query/2) and displays them %% using the table visualization mode. %% %% @param Results List of result tuples @@ -201,7 +195,7 @@ show(Results) -> %% @doc Display results using specified visualization mode. %% -%% Takes a list of tuples (e.g., from `query/2`) and displays them +%% Takes a list of tuples (e.g., from query/2) and displays them %% using the specified visualization mode. %% %% @param Results List of result tuples @@ -209,10 +203,10 @@ show(Results) -> %% @returns ok %% %% == Example == -%% ``` +%% 
 %% Results = repl:query(DB, {scan, employees}),
 %% repl:show(Results, tree).
-%% ```
+%%
-spec show([map()], visualizer:render_mode()) -> ok. show(Results, Mode) -> visualizer:render(Results, Mode). diff --git a/src/visualizer.erl b/src/visualizer.erl index 83080f1..75f85d1 100644 --- a/src/visualizer.erl +++ b/src/visualizer.erl @@ -5,19 +5,18 @@ %%% %%% == Modes == %%% -%%% - `table` - Classic flat table (default) -%%% - `nested_table` - Tables within table cells -%%% - `tree` - Hierarchical tree view with indentation -%%% - `linked_tables` - Separate linked tables for nested relations -%%% - `outline` - Indented outline format +%%% - table - Classic flat table (default) +%%% - nested_table - Tables within table cells +%%% - tree - Hierarchical tree view with indentation +%%% - linked_tables - Separate linked tables for nested relations +%%% - outline - Indented outline format %%% %%% == Usage == -%%% -%%% ``` +%%% 
 %%% Results = query_planner:collect(DB, Plan),
 %%% visualizer:render(Results, tree).
 %%% visualizer:render(Results, nested_table).
-%%% ```
+%%%
%%% %%% @author Nekoma Team %%% @copyright 2025 diff --git a/src/xml_server.erl b/src/xml_server.erl index eee4771..4eef4c9 100644 --- a/src/xml_server.erl +++ b/src/xml_server.erl @@ -7,40 +7,37 @@ %%% == Protocol == %%% %%% Client sends commands as line-delimited strings: -%%% -%%% ``` -%%% QUERY - Execute a query plan, returns session ID -%%% NEXT - Get next N tuples from iterator -%%% CLOSE - Close iterator and free resources -%%% ``` +%%% 
+%%% QUERY <erlang-term-string>   - Execute a query plan, returns session ID
+%%% NEXT <session-id> <count>    - Get next N tuples from iterator
+%%% CLOSE <session-id>           - Close iterator and free resources
+%%%
%%% %%% Server responds with XML: -%%% -%%% ``` -%%% -%%% -%%% abc123 -%%% -%%% -%%% 1 -%%% Alice -%%% -%%% -%%% -%%% ``` +%%% 
+%%% <?xml version="1.0"?>
+%%% <response>
+%%%   <session>abc123</session>
+%%%   <tuples>
+%%%     <tuple>
+%%%       <attribute name="id">1</attribute>
+%%%       <attribute name="name">Alice</attribute>
+%%%     </tuple>
+%%%   </tuples>
+%%% </response>
+%%%
%%% %%% == Usage == -%%% -%%% ``` +%%% 
 %%% % Start server on port 8080
 %%% xml_server:start(8080).
 %%%
 %%% % Client connects and sends:
 %%% % QUERY {scan, employees}\n
-%%% % NEXT  10\n
-%%% % NEXT  10\n
-%%% % CLOSE \n
-%%% ```
+%%% % NEXT <session-id> 10\n
+%%% % NEXT <session-id> 10\n
+%%% % CLOSE <session-id>\n
+%%%
%%% %%% @author Nekoma Team %%% @copyright 2025 -- cgit v1.2.3