diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/constraint.erl | 1179 | ||||
| -rw-r--r-- | src/generators.erl | 584 | ||||
| -rw-r--r-- | src/main.app.src | 15 | ||||
| -rw-r--r-- | src/main.erl | 66 | ||||
| -rw-r--r-- | src/operations.erl | 1484 | ||||
| -rw-r--r-- | src/query_planner.erl | 601 | ||||
| -rw-r--r-- | src/relation.erl | 42 | ||||
| -rw-r--r-- | src/relational_operators.erl | 490 | ||||
| -rw-r--r-- | src/repl.erl | 326 | ||||
| -rw-r--r-- | src/visualizer.erl | 348 |
10 files changed, 0 insertions, 5135 deletions
diff --git a/src/constraint.erl b/src/constraint.erl deleted file mode 100644 index 6391217..0000000 --- a/src/constraint.erl +++ /dev/null @@ -1,1179 +0,0 @@ --module(constraint). - --include("../include/operations.hrl"). - --export([ - less_than/2, - less_than_or_equal/2, - greater_than/2, - greater_than_or_equal/2, - equal/2, - not_equal/2, - plus/2, - times/2, - minus/2, - divide/2, - member/2, - member/3, - 'not'/2, - 'and'/2, - 'or'/2, - resolve/4, - validate_tuple/3, - validate_tuple_against_schema/3, - build_membership_criteria/2, - lt/2, - lte/2, - gt/2, - gte/2, - eq/2, - neq/2, - between/2, - example_supertype_exclusive_constraints/0, - example_order_item_references_constraints/0, - example_manager_constraints/0, - example_ticket_status_exclusive_constraints/0, - example_weak_entity_dependency_constraints/0, - example_department_has_employee_constraints/0, - example_symmetry_antisymmetry_constraints/0, - run_example_supertype_exclusive/0, - run_example_order_item_references/0, - run_example_manager_constraints/0, - run_example_ticket_status_exclusive/0, - run_example_weak_entity_dependency/0, - run_example_department_has_employee/0, - run_example_symmetry_antisymmetry/0, - run_all_examples/0, - empty_constraints/0, - merge_constraints/2, - filter_constraints/2, - rename_constraint_attrs/2, - infer_constraints_from_pred/2, - get_domain_from_db/2 -]). - --type relational_constraint() :: - {member_of, relation_name() | #relation{} | #domain{}, binding()} - | {'not', relational_constraint()} - | {'not', relational_constraint(), relation_name()} - | {'and', [relational_constraint()]} - | {'or', [relational_constraint()]} - | {exists, atom(), relation_name(), relational_constraint()} - | {forall, atom(), relation_name(), relational_constraint()}. - --type relation_name() :: atom(). --type binding() :: #{atom() => term() | {var, atom()} | {const, term()}}. - --export_type([relational_constraint/0, binding/0]). - --spec less_than(atom(), cardinality()) -> #relation{}. -less_than(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = less_than, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '<', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L < R end - }, - provenance = undefined, - lineage = {base, less_than} - }. - --spec less_than_or_equal(atom(), cardinality()) -> #relation{}. -less_than_or_equal(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = less_than_or_equal, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '=<', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L =< R end - }, - provenance = undefined, - lineage = {base, less_than_or_equal} - }. - --spec greater_than(atom(), cardinality()) -> #relation{}. -greater_than(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = greater_than, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '>', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L > R end - }, - provenance = undefined, - lineage = {base, greater_than} - }. - --spec greater_than_or_equal(atom(), cardinality()) -> #relation{}. -greater_than_or_equal(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = greater_than_or_equal, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '>=', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L >= R end - }, - provenance = undefined, - lineage = {base, greater_than_or_equal} - }. - --spec equal(atom(), cardinality()) -> #relation{}. -equal(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = equal, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '=:=', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L =:= R end - }, - provenance = undefined, - lineage = {base, equal} - }. - --spec not_equal(atom(), cardinality()) -> #relation{}. -not_equal(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = not_equal, - tree = undefined, - schema = #{left => DomainName, right => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {comparison, '/=', DomainName}, - membership_criteria = #{ - intension => fun(#{left := L, right := R}) -> L /= R end - }, - provenance = undefined, - lineage = {base, not_equal} - }. - --spec plus(atom(), cardinality()) -> #relation{}. -plus(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = plus, - tree = undefined, - schema = #{a => DomainName, b => DomainName, sum => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {arithmetic, plus, DomainName}, - membership_criteria = #{ - intension => fun(#{a := A, b := B, sum := S}) -> - is_number(A) andalso is_number(B) andalso is_number(S) andalso (A + B =:= S) - end - }, - provenance = undefined, - lineage = {base, plus} - }. - --spec times(atom(), cardinality()) -> #relation{}. -times(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = times, - tree = undefined, - schema = #{a => DomainName, b => DomainName, product => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {arithmetic, times, DomainName}, - membership_criteria = #{ - intension => fun(#{a := A, b := B, product := P}) -> - is_number(A) andalso is_number(B) andalso is_number(P) andalso (A * B =:= P) - end - }, - provenance = undefined, - lineage = {base, times} - }. - --spec minus(atom(), cardinality()) -> #relation{}. -minus(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = minus, - tree = undefined, - schema = #{a => DomainName, b => DomainName, difference => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {arithmetic, minus, DomainName}, - membership_criteria = #{ - intension => fun(#{a := A, b := B, difference := D}) -> - is_number(A) andalso is_number(B) andalso is_number(D) andalso (A - B =:= D) - end - }, - provenance = undefined, - lineage = {base, minus} - }. - --spec divide(atom(), cardinality()) -> #relation{}. -divide(DomainName, Cardinality) -> - #relation{ - hash = undefined, - name = divide, - tree = undefined, - schema = #{a => DomainName, b => DomainName, quotient => DomainName, remainder => DomainName}, - constraints = empty_constraints(), - cardinality = Cardinality, - generator = {arithmetic, divide, DomainName}, - membership_criteria = #{ - intension => fun(#{a := A, b := B, quotient := Q, remainder := R}) -> - is_integer(A) andalso is_integer(B) andalso is_integer(Q) andalso is_integer(R) - andalso B =/= 0 - andalso (A div B =:= Q) - andalso (A rem B =:= R) - end - }, - provenance = undefined, - lineage = {base, divide} - }. - --spec member(map(), #domain{} | #relation{}) -> boolean(). -member(Tuple, #relation{membership_criteria = #{intension := Intension}}) -> - Intension(Tuple); -member(Tuple, #relation{membership_criteria = #{test := TestFun}}) -> - TestFun(Tuple); -member(Tuple, #relation{hash = RelationHash, tree = Tree}) when Tree =/= undefined -> - BindingHashes = binding_to_hashes(Tuple), - TupleHashes = operations:hashes_from_tuple(RelationHash), - lists:any( - fun(TupleHash) -> - tuple_hash_matches_binding(TupleHash, BindingHashes) - end, - TupleHashes); -member(_Tuple, #relation{tree = undefined, generator = Generator}) when Generator =/= undefined -> - false; -member(_Tuple, #relation{}) -> - false; -member(Tuple, #domain{membership_criteria = #{test := TestFun}}) -> - TestFun(Tuple); -member(Tuple, #domain{membership_criteria = Criteria}) when is_map(Criteria) -> - validate_tuple_against_criteria(Tuple, Criteria). - -binding_to_hashes(Binding) when is_map(Binding) -> - maps:map( - fun(_Attr, Value) -> - operations:value_hash(Value) - end, - Binding). - -tuple_hash_matches_binding(TupleHash, BindingHashes) -> - [#tuple{attribute_map = AttributeMap}] = mnesia:dirty_read(tuple, TupleHash), - tuple_matches_binding_hashes(BindingHashes, AttributeMap). - -tuple_matches_binding_hashes(BindingHashes, TupleAttributeMap) - when is_map(BindingHashes), is_map(TupleAttributeMap) -> - maps:fold( - fun(Key, ValueHash, Acc) -> - Acc andalso maps:get(Key, TupleAttributeMap, undefined) =:= ValueHash - end, - true, - BindingHashes). - --spec member(binding(), #domain{} | #relation{}, map()) -> {true, map()} | false. -member(Binding, Relation, Substitution) -> - BoundTuple = apply_substitution(Binding, Substitution), - case find_variables(BoundTuple) of - [] -> - case member(BoundTuple, Relation) of - true -> {true, Substitution}; - false -> false - end; - _ -> - false - end. - --spec 'not'(#relation{}, #relation{}) -> #relation{}. -'not'(R, Universe) -> - RName = get_name(R), - UniverseName = get_name(Universe), - ResultName = list_to_atom("not_" ++ atom_to_list(RName) ++ "_in_" ++ atom_to_list(UniverseName)), - #relation{ - hash = undefined, - name = ResultName, - tree = undefined, - schema = get_schema(R), - constraints = empty_constraints(), - cardinality = complement_cardinality(R, Universe), - generator = {complement, R, Universe}, - membership_criteria = #{ - intension => fun(Tuple) -> - member(Tuple, Universe) andalso not member(Tuple, R) - end - }, - provenance = undefined, - lineage = {complement, get_lineage(R), get_lineage(Universe)} - }. - --spec 'and'(#relation{}, #relation{}) -> #relation{}. -'and'(R1, R2) -> - Schema1 = get_schema(R1), - Schema2 = get_schema(R2), - case schemas_compatible(Schema1, Schema2) of - false -> - error({incompatible_schemas, Schema1, Schema2}); - true -> - R1Name = get_name(R1), - R2Name = get_name(R2), - ResultName = list_to_atom(atom_to_list(R1Name) ++ "_and_" ++ atom_to_list(R2Name)), - #relation{ - hash = undefined, - name = ResultName, - tree = undefined, - schema = merge_schemas(Schema1, Schema2), - constraints = empty_constraints(), - cardinality = intersection_cardinality(R1, R2), - generator = {intersection, R1, R2}, - membership_criteria = #{ - intension => fun(Tuple) -> - member(Tuple, R1) andalso member(Tuple, R2) - end - }, - provenance = undefined, - lineage = {intersection, get_lineage(R1), get_lineage(R2)} - } - end. - --spec 'or'(#relation{}, #relation{}) -> #relation{}. -'or'(R1, R2) -> - Schema1 = get_schema(R1), - Schema2 = get_schema(R2), - case schemas_compatible(Schema1, Schema2) of - false -> - error({incompatible_schemas, Schema1, Schema2}); - true -> - R1Name = get_name(R1), - R2Name = get_name(R2), - ResultName = list_to_atom(atom_to_list(R1Name) ++ "_or_" ++ atom_to_list(R2Name)), - #relation{ - hash = undefined, - name = ResultName, - tree = undefined, - schema = merge_schemas(Schema1, Schema2), - constraints = empty_constraints(), - cardinality = union_cardinality(R1, R2), - generator = {union, R1, R2}, - membership_criteria = #{ - intension => fun(Tuple) -> - member(Tuple, R1) orelse member(Tuple, R2) - end - }, - provenance = undefined, - lineage = {union, get_lineage(R1), get_lineage(R2)} - } - end. - --spec resolve(#database_state{}, atom(), #domain{} | #relation{} | relational_constraint(), map()) -> - {ok, boolean()} | {error, term()}. -resolve(_Database, domain, #domain{} = Domain, Values) -> - {ok, member(Values, Domain)}; -resolve(_Database, relation, #relation{} = Relation, Values) -> - {ok, member(Values, Relation)}; -resolve(Database, constraint, Constraint, Binding) -> - evaluate_constraint(Database, Constraint, Binding). - --spec validate_tuple(#database_state{}, map(), #relation{}) -> ok | {error, term()}. -validate_tuple(Database, Tuple, #relation{schema = Schema, constraints = Constraints}) -> - case validate_tuple_against_schema(Database, Tuple, Schema) of - ok -> - validate_tuple_against_constraints(Database, Tuple, Constraints); - Error -> - Error - end. - --spec validate_tuple_against_schema(#database_state{}, map(), map()) -> ok | {error, term()}. -validate_tuple_against_schema(Database, Tuple, Schema) -> - SchemaAttrs = maps:keys(Schema), - TupleAttrs = maps:keys(Tuple), - Missing = SchemaAttrs -- TupleAttrs, - case Missing of - [] -> - Extra = TupleAttrs -- SchemaAttrs, - case Extra of - [] -> - validate_all_attributes(Database, Tuple, Schema); - _ -> - {error, {extra_attributes, Extra}} - end; - _ -> - {error, {missing_attributes, Missing}} - end. - -validate_all_attributes(Database, Tuple, Schema) -> - maps:fold( - fun(AttrName, DomainName, Acc) -> - case Acc of - {error, _} = Err -> - Err; - ok -> - Value = maps:get(AttrName, Tuple), - case get_domain_from_db(Database, DomainName) of - {ok, Domain} -> - case member(#{value => Value}, Domain) of - true -> ok; - false -> {error, {not_in_domain, AttrName, Value, DomainName}} - end; - {error, not_found} -> - {error, {unknown_domain, AttrName, DomainName}} - end - end - end, - ok, - Schema - ). - -validate_tuple_against_constraints(_Database, _Tuple, undefined) -> - ok; -validate_tuple_against_constraints(Database, Tuple, Constraints) -> - Normalized = normalize_constraints(Constraints), - NamedConstraints = Normalized#relation_constraints.constraints, - case evaluate_named_constraints(Database, NamedConstraints, Tuple) of - {true, _Violations} -> - ok; - {false, Violations} -> - {error, {constraint_violations, Violations}} - end. - -evaluate_named_constraints(_Database, [], _Context) -> - {true, []}; -evaluate_named_constraints(Database, NamedConstraints, Context) -> - ViolationsRev = lists:foldl( - fun({Name, Formula}, Acc) -> - {Result, Diagnostics} = evaluate_constraint_with_diagnostics(Database, Formula, Context), - case Result of - true -> - Acc; - false -> - [#{constraint_name => Name, - formula => Formula, - diagnostics => Diagnostics} | Acc] - end - end, - [], - NamedConstraints), - case ViolationsRev of - [] -> {true, []}; - _ -> {false, lists:reverse(ViolationsRev)} - end. - --spec evaluate_constraint_list(#database_state{}, [term()], map()) -> {boolean(), [map()]}. -evaluate_constraint_list(_Database, [], _Context) -> - {true, []}; -evaluate_constraint_list(Database, Constraints, Context) -> - {AllTrue, DiagnosticsRev} = lists:foldl( - fun(ConstraintTerm, {AccTrue, AccDiags}) -> - {Result, Diags} = evaluate_constraint_with_diagnostics(Database, ConstraintTerm, Context), - {AccTrue andalso Result, lists:reverse(Diags) ++ AccDiags} - end, - {true, []}, - Constraints - ), - {AllTrue, lists:reverse(DiagnosticsRev)}. - --spec evaluate_constraint_with_diagnostics(#database_state{}, term(), map()) -> {boolean(), [map()]}. -evaluate_constraint_with_diagnostics(Database, {member_of, RelName, Binding}, Context) - when is_atom(RelName), is_map(Binding) -> - BoundBinding = bind_variables(Binding, Context), - case get_domain_from_db(Database, RelName) of - {ok, Relation} -> - case member(BoundBinding, Relation) of - true -> {true, []}; - false -> - {false, [#{kind => member_of_false, relation => RelName, binding => BoundBinding}]} - end; - {error, not_found} -> - {false, [#{kind => relation_not_found, relation => RelName, binding => BoundBinding}]} - end; -evaluate_constraint_with_diagnostics(_Database, {member_of, #relation{} = Rel, Binding}, Context) -> - BoundBinding = bind_variables(Binding, Context), - case member(BoundBinding, Rel) of - true -> {true, []}; - false -> {false, [#{kind => member_of_false, relation => get_name(Rel), binding => BoundBinding}]} - end; -evaluate_constraint_with_diagnostics(_Database, {member_of, #domain{} = Rel, Binding}, Context) -> - BoundBinding = bind_variables(Binding, Context), - case member(BoundBinding, Rel) of - true -> {true, []}; - false -> {false, [#{kind => member_of_false, relation => get_name(Rel), binding => BoundBinding}]} - end; -evaluate_constraint_with_diagnostics(Database, {'and', Constraints}, Context) -> - evaluate_constraint_list(Database, Constraints, Context); -evaluate_constraint_with_diagnostics(Database, {'or', Constraints}, Context) -> - {AnyTrue, DiagnosticsRev} = lists:foldl( - fun(ConstraintTerm, {AccTrue, AccDiags}) -> - {Result, Diags} = evaluate_constraint_with_diagnostics(Database, ConstraintTerm, Context), - {AccTrue orelse Result, lists:reverse(Diags) ++ AccDiags} - end, - {false, []}, - Constraints - ), - {AnyTrue, lists:reverse(DiagnosticsRev)}; -evaluate_constraint_with_diagnostics(Database, {'not', Constraint}, Context) -> - {Result, Diagnostics} = evaluate_constraint_with_diagnostics(Database, Constraint, Context), - {not Result, Diagnostics}; -evaluate_constraint_with_diagnostics(Database, {'not', Constraint, _Universe}, Context) -> - {Result, Diagnostics} = evaluate_constraint_with_diagnostics(Database, Constraint, Context), - {not Result, Diagnostics}; -evaluate_constraint_with_diagnostics(Database, {exists, VarName, QuantifierRel, Constraint}, Context) - when is_atom(VarName), is_atom(QuantifierRel) -> - evaluate_quantifier_with_diagnostics(Database, exists, VarName, QuantifierRel, Constraint, Context); -evaluate_constraint_with_diagnostics(Database, {forall, VarName, QuantifierRel, Constraint}, Context) - when is_atom(VarName), is_atom(QuantifierRel) -> - evaluate_quantifier_with_diagnostics(Database, forall, VarName, QuantifierRel, Constraint, Context); -evaluate_constraint_with_diagnostics(_Database, Constraint, _Context) -> - {false, [#{kind => unsupported_constraint, constraint => Constraint}]}. - -evaluate_quantifier_with_diagnostics(Database, Quantifier, VarName, QuantifierRel, Constraint, Context) -> - case get_domain_from_db(Database, QuantifierRel) of - {error, not_found} -> - {false, [#{kind => quantifier_relation_not_found, - quantifier => Quantifier, - variable => VarName, - relation => QuantifierRel}]}; - {ok, Relation} -> - case Relation#relation.cardinality of - {finite, _} -> - evaluate_finite_quantifier(Database, Quantifier, VarName, QuantifierRel, Constraint, Context); - _ -> - {false, [#{kind => unbounded_quantifier, - quantifier => Quantifier, - variable => VarName, - relation => QuantifierRel}]} - end - end. - -evaluate_finite_quantifier(Database, Quantifier, VarName, QuantifierRel, Constraint, Context) -> - Iterator = operations:get_tuples_iterator(Database, QuantifierRel), - case operations:collect_all(Iterator) of - {error, Reason, _Partial} -> - {false, [#{kind => quantifier_iteration_error, - quantifier => Quantifier, - variable => VarName, - relation => QuantifierRel, - reason => Reason}]}; - Tuples when is_list(Tuples) -> - evaluate_quantifier_tuples(Database, Quantifier, VarName, Constraint, Context, Tuples) - end. - -evaluate_quantifier_tuples(_Database, exists, _VarName, _Constraint, _Context, []) -> - {false, []}; -evaluate_quantifier_tuples(_Database, forall, _VarName, _Constraint, _Context, []) -> - {true, []}; -evaluate_quantifier_tuples(Database, Quantifier, VarName, Constraint, Context, Tuples) -> - {ResultsRev, DiagnosticsRev} = lists:foldl( - fun(TupleValueMap, {AccResults, AccDiags}) -> - case extract_quantifier_value(TupleValueMap) of - {ok, QuantifiedValue} -> - ScopedContext = Context#{VarName => QuantifiedValue}, - {Result, Diags} = evaluate_constraint_with_diagnostics(Database, Constraint, ScopedContext), - {[Result | AccResults], lists:reverse(Diags) ++ AccDiags}; - {error, Reason} -> - {[false | AccResults], [#{kind => invalid_quantifier_tuple, - variable => VarName, - tuple => TupleValueMap, - reason => Reason} | AccDiags]} - end - end, - {[], []}, - Tuples - ), - Results = lists:reverse(ResultsRev), - Diagnostics = lists:reverse(DiagnosticsRev), - case Quantifier of - exists -> {lists:any(fun(X) -> X end, Results), Diagnostics}; - forall -> {lists:all(fun(X) -> X end, Results), Diagnostics} - end. - -extract_quantifier_value(TupleValueMap) when is_map(TupleValueMap) -> - case maps:to_list(TupleValueMap) of - [{_Attr, Value}] -> - {ok, Value}; - [] -> - {error, empty_tuple}; - _ -> - {error, non_unary_quantifier_relation} - end. - --spec build_membership_criteria(#database_state{}, map()) -> map(). -build_membership_criteria(Database, Schema) -> - maps:fold( - fun(AttrName, DomainName, Acc) -> - case get_domain_from_db(Database, DomainName) of - {ok, Domain} -> - Test = case Domain#relation.membership_criteria of - #{test := TestFun} -> TestFun; - _ -> fun(_) -> true end - end, - Acc#{AttrName => #{domain => DomainName, test => Test}}; - {error, not_found} -> - Acc#{AttrName => #{domain => DomainName, test => fun(_) -> true end}} - end - end, - #{}, - Schema - ). - --spec lt(term(), term()) -> relational_constraint(). -lt(Left, Right) -> - {member_of, less_than, #{left => Left, right => Right}}. - --spec lte(term(), term()) -> relational_constraint(). -lte(Left, Right) -> - {member_of, less_than_or_equal, #{left => Left, right => Right}}. - --spec gt(term(), term()) -> relational_constraint(). -gt(Left, Right) -> - {member_of, greater_than, #{left => Left, right => Right}}. - --spec gte(term(), term()) -> relational_constraint(). -gte(Left, Right) -> - {member_of, greater_than_or_equal, #{left => Left, right => Right}}. - --spec eq(term(), term()) -> relational_constraint(). -eq(Left, Right) -> - {member_of, equal, #{left => Left, right => Right}}. - --spec neq(term(), term()) -> relational_constraint(). -neq(Left, Right) -> - {member_of, not_equal, #{left => Left, right => Right}}. - --spec between(term(), term()) -> relational_constraint(). -between(Min, Max) -> - {'and', [gte({var, value}, Min), lt({var, value}, Max)]}. - --spec empty_constraints() -> #relation_constraints{}. -empty_constraints() -> - #relation_constraints{constraints = []}. - --spec example_supertype_exclusive_constraints() -> #{atom() => #relation_constraints{}}. -example_supertype_exclusive_constraints() -> - #{ - b => #relation_constraints{constraints = [ - {b_requires_a, {member_of, a, #{id => {var, id}}}}, - {b_excludes_c, {'not', {member_of, c, #{id => {var, id}}}}} - ]}, - c => #relation_constraints{constraints = [ - {c_requires_a, {member_of, a, #{id => {var, id}}}}, - {c_excludes_b, {'not', {member_of, b, #{id => {var, id}}}}} - ]} - }. - --spec example_order_item_references_constraints() -> #relation_constraints{}. -example_order_item_references_constraints() -> - #relation_constraints{constraints = [ - {order_item_order_fk, {member_of, order, #{id => {var, order_id}}}}, - {order_item_product_fk, {member_of, product, #{id => {var, product_id}}}} - ]}. - --spec example_manager_constraints() -> #relation_constraints{}. -example_manager_constraints() -> - #relation_constraints{constraints = [ - {managed_employee_exists, {member_of, employee, #{id => {var, employee_id}}}}, - {manager_exists, {member_of, employee, #{id => {var, manager_id}}}}, - {no_self_management, neq({var, employee_id}, {var, manager_id})} - ]}. - --spec example_ticket_status_exclusive_constraints() -> #{atom() => #relation_constraints{}}. -example_ticket_status_exclusive_constraints() -> - #{ - open_ticket => #relation_constraints{constraints = [ - {open_excludes_closed, {'not', {member_of, closed_ticket, #{ticket_id => {var, ticket_id}}}}} - ]}, - closed_ticket => #relation_constraints{constraints = [ - {closed_excludes_open, {'not', {member_of, open_ticket, #{ticket_id => {var, ticket_id}}}}} - ]} - }. - --spec example_weak_entity_dependency_constraints() -> #relation_constraints{}. -example_weak_entity_dependency_constraints() -> - #relation_constraints{constraints = [ - {dependent_person_fk, {member_of, person, #{id => {var, person_id}}}} - ]}. - --spec example_department_has_employee_constraints() -> #relation_constraints{}. -example_department_has_employee_constraints() -> - #relation_constraints{constraints = [ - {department_has_employee, {member_of, employee_dept, #{dept_id => {var, id}}}} - ]}. - --spec example_symmetry_antisymmetry_constraints() -> #{atom() => #relation_constraints{}}. -example_symmetry_antisymmetry_constraints() -> - #{ - married_to => #relation_constraints{constraints = [ - {marriage_is_symmetric, {member_of, married_to, #{person_a => {var, person_b}, person_b => {var, person_a}}}} - ]}, - reports_to => #relation_constraints{constraints = [ - {reports_to_no_self, neq({var, employee_id}, {var, manager_id})}, - {reports_to_antisymmetric, - {'or', [ - eq({var, employee_id}, {var, manager_id}), - {'not', {member_of, reports_to, - #{employee_id => {var, manager_id}, manager_id => {var, employee_id}}}} - ]}} - ]} - }. - --spec run_example_supertype_exclusive() -> map(). -run_example_supertype_exclusive() -> - main:setup(), - DB0 = operations:create_database(example_supertype_exclusive), - {DB1, _} = operations:create_relation(DB0, a, #{id => integer}), - {DB2, _} = operations:create_relation(DB1, b, #{id => integer}), - {DB3, _} = operations:create_relation(DB2, c, #{id => integer}), - ConstraintsByRel = example_supertype_exclusive_constraints(), - {DB4, _} = operations:update_relation_constraints(DB3, b, maps:get(b, ConstraintsByRel)), - {DB5, _} = operations:update_relation_constraints(DB4, c, maps:get(c, ConstraintsByRel)), - {DB6, _} = operations:create_tuple(DB5, a, #{id => 1}), - InB = operations:create_tuple(DB6, b, #{id => 1}), - DBAfterB = db_after(InB), - InCWithB = operations:create_tuple(DBAfterB, c, #{id => 1}), - {DB7, _} = operations:create_tuple(DBAfterB, a, #{id => 3}), - InCWithAAndNoB = operations:create_tuple(DB7, c, #{id => 3}), - InCWithoutA = operations:create_tuple(DBAfterB, c, #{id => 2}), - #{accepted_in_b => InB, - accepted_in_c_with_a_only => InCWithAAndNoB, - rejected_c_overlap_b => InCWithB, - rejected_c_missing_a => InCWithoutA}. - --spec run_example_order_item_references() -> map(). -run_example_order_item_references() -> - main:setup(), - DB0 = operations:create_database(example_order_item_references), - {DB1, _} = operations:create_relation(DB0, order, #{id => integer}), - {DB2, _} = operations:create_relation(DB1, product, #{id => integer}), - {DB3, _} = operations:create_relation(DB2, order_item, #{order_id => integer, product_id => integer}), - {DB4, _} = operations:update_relation_constraints(DB3, order_item, example_order_item_references_constraints()), - {DB5, _} = operations:create_tuple(DB4, order, #{id => 10}), - {DB6, _} = operations:create_tuple(DB5, product, #{id => 20}), - Valid = operations:create_tuple(DB6, order_item, #{order_id => 10, product_id => 20}), - DBAfterValid = db_after(Valid), - MissingOrder = operations:create_tuple(DBAfterValid, order_item, #{order_id => 999, product_id => 20}), - MissingProduct = operations:create_tuple(DBAfterValid, order_item, #{order_id => 10, product_id => 999}), - #{accepted_valid_order_item => Valid, - rejected_missing_order => MissingOrder, - rejected_missing_product => MissingProduct}. - --spec run_example_manager_constraints() -> map(). -run_example_manager_constraints() -> - main:setup(), - DB0 = operations:create_database(example_manager_constraints), - {DB1, _} = operations:create_relation(DB0, employee, #{id => integer}), - {DB2, _} = operations:create_relation(DB1, manager_of, #{employee_id => integer, manager_id => integer}), - {DB3, _} = operations:update_relation_constraints(DB2, manager_of, example_manager_constraints()), - {DB4, _} = operations:create_tuple(DB3, employee, #{id => 1}), - {DB5, _} = operations:create_tuple(DB4, employee, #{id => 2}), - Valid = operations:create_tuple(DB5, manager_of, #{employee_id => 1, manager_id => 2}), - DBAfterValid = db_after(Valid), - Self = operations:create_tuple(DBAfterValid, manager_of, #{employee_id => 1, manager_id => 1}), - MissingEmployee = operations:create_tuple(DBAfterValid, manager_of, #{employee_id => 3, manager_id => 2}), - MissingManager = operations:create_tuple(DBAfterValid, manager_of, #{employee_id => 1, manager_id => 3}), - #{accepted_valid_manager_pair => Valid, - rejected_self_management => Self, - rejected_missing_employee => MissingEmployee, - rejected_missing_manager => MissingManager}. - --spec run_example_ticket_status_exclusive() -> map(). -run_example_ticket_status_exclusive() -> - main:setup(), - DB0 = operations:create_database(example_ticket_status_exclusive), - {DB1, _} = operations:create_relation(DB0, open_ticket, #{ticket_id => integer}), - {DB2, _} = operations:create_relation(DB1, closed_ticket, #{ticket_id => integer}), - ConstraintsByRel = example_ticket_status_exclusive_constraints(), - {DB3, _} = operations:update_relation_constraints(DB2, open_ticket, maps:get(open_ticket, ConstraintsByRel)), - {DB4, _} = operations:update_relation_constraints(DB3, closed_ticket, maps:get(closed_ticket, ConstraintsByRel)), - Open7 = operations:create_tuple(DB4, open_ticket, #{ticket_id => 7}), - DBAfterOpen7 = db_after(Open7), - Closed7 = operations:create_tuple(DBAfterOpen7, closed_ticket, #{ticket_id => 7}), - Closed8 = operations:create_tuple(DBAfterOpen7, closed_ticket, #{ticket_id => 8}), - DBAfterClosed8 = db_after(Closed8), - Open8 = operations:create_tuple(DBAfterClosed8, open_ticket, #{ticket_id => 8}), - #{accepted_open_7 => Open7, - rejected_closed_7 => Closed7, - accepted_closed_8 => Closed8, - rejected_open_8 => Open8}. - --spec run_example_weak_entity_dependency() -> map(). -run_example_weak_entity_dependency() -> - main:setup(), - DB0 = operations:create_database(example_weak_entity_dependency), - {DB1, _} = operations:create_relation(DB0, person, #{id => integer}), - {DB2, _} = operations:create_relation(DB1, dependent, #{person_id => integer, dep_name => string}), - {DB3, _} = operations:update_relation_constraints(DB2, dependent, example_weak_entity_dependency_constraints()), - {DB4, _} = operations:create_tuple(DB3, person, #{id => 1}), - Valid = operations:create_tuple(DB4, dependent, #{person_id => 1, dep_name => "kid"}), - DBAfterValid = db_after(Valid), - MissingParent = operations:create_tuple(DBAfterValid, dependent, #{person_id => 2, dep_name => "kid2"}), - #{accepted_existing_parent => Valid, - rejected_missing_parent => MissingParent}. - --spec run_example_department_has_employee() -> map(). -run_example_department_has_employee() -> - main:setup(), - DB0 = operations:create_database(example_department_has_employee), - {DB1, _} = operations:create_relation(DB0, employee_dept, #{dept_id => integer, employee_id => integer}), - {DB2, _} = operations:create_relation(DB1, department, #{id => integer}), - {DB3, _} = operations:update_relation_constraints(DB2, department, example_department_has_employee_constraints()), - {DB4, _} = operations:create_tuple(DB3, employee_dept, #{dept_id => 1, employee_id => 99}), - Dept1 = operations:create_tuple(DB4, department, #{id => 1}), - DBAfterDept1 = db_after(Dept1), - Dept2 = operations:create_tuple(DBAfterDept1, department, #{id => 2}), - #{accepted_department_with_employee => Dept1, - rejected_department_without_employee => Dept2}. - --spec run_example_symmetry_antisymmetry() -> map(). -run_example_symmetry_antisymmetry() -> - main:setup(), - DB0 = operations:create_database(example_symmetry_antisymmetry), - {DB1, _} = operations:create_relation(DB0, married_to, #{person_a => integer, person_b => integer}), - {DB2, _} = operations:create_relation(DB1, reports_to, #{employee_id => integer, manager_id => integer}), - {DB3, _} = operations:create_tuple(DB2, married_to, #{person_a => 2, person_b => 1}), - {DB4, _} = operations:create_tuple(DB3, married_to, #{person_a => 1, person_b => 2}), - ConstraintsByRel = example_symmetry_antisymmetry_constraints(), - {DB5, _} = operations:update_relation_constraints(DB4, married_to, maps:get(married_to, ConstraintsByRel)), - {DB6, _} = operations:update_relation_constraints(DB5, reports_to, maps:get(reports_to, ConstraintsByRel)), - MissingReverseMarriage = operations:create_tuple(DB6, married_to, #{person_a => 3, person_b => 4}), - AcceptedWithReverse = operations:create_tuple(DB6, married_to, #{person_a => 2, person_b => 1}), - Reports12 = operations:create_tuple(DB6, reports_to, #{employee_id => 1, manager_id => 2}), - DBAfterReports12 = db_after(Reports12), - Reports21 = operations:create_tuple(DBAfterReports12, reports_to, #{employee_id => 2, manager_id => 1}), - Reports33 = operations:create_tuple(DBAfterReports12, reports_to, #{employee_id => 3, manager_id => 3}), - #{rejected_missing_reverse_marriage => MissingReverseMarriage, - accepted_with_existing_reverse_marriage => AcceptedWithReverse, - accepted_reports_1_to_2 => Reports12, - rejected_reports_2_to_1 => Reports21, - rejected_reports_3_to_3 => Reports33}. - --spec run_all_examples() -> map(). -run_all_examples() -> - #{ - supertype_exclusive => run_example_supertype_exclusive(), - order_item_references => run_example_order_item_references(), - manager_constraints => run_example_manager_constraints(), - ticket_status_exclusive => run_example_ticket_status_exclusive(), - weak_entity_dependency => run_example_weak_entity_dependency(), - department_has_employee => run_example_department_has_employee(), - symmetry_antisymmetry => run_example_symmetry_antisymmetry() - }. - -db_after({DB, _Relation}) -> DB. - --spec merge_constraints(#relation_constraints{} | undefined, #relation_constraints{} | undefined) -> #relation_constraints{}. -merge_constraints(C1, C2) -> - N1 = normalize_constraints(C1), - N2 = normalize_constraints(C2), - #relation_constraints{constraints = N1#relation_constraints.constraints ++ N2#relation_constraints.constraints}. - --spec filter_constraints(#relation_constraints{} | undefined, [atom()]) -> #relation_constraints{}. -filter_constraints(Constraints, Attrs) -> - Normalized = normalize_constraints(Constraints), - Keep = [ - {Name, Formula} || {Name, Formula} <- Normalized#relation_constraints.constraints, - lists:all(fun(V) -> lists:member(V, Attrs) end, vars_in_constraint(Formula)) - ], - #relation_constraints{constraints = Keep}. - --spec rename_constraint_attrs(#relation_constraints{} | undefined, map()) -> #relation_constraints{}. -rename_constraint_attrs(Constraints, RenameMappings) -> - Normalized = normalize_constraints(Constraints), - Renamed = [{Name, rename_vars_in_constraint(Formula, RenameMappings)} || - {Name, Formula} <- Normalized#relation_constraints.constraints], - #relation_constraints{constraints = Renamed}. - --spec infer_constraints_from_pred(term(), map()) -> #relation_constraints{}. -infer_constraints_from_pred(Predicate, _Schema) when is_function(Predicate) -> - empty_constraints(); -infer_constraints_from_pred({attr, AttrName, Op, Value}, _Schema) -> - Name = list_to_atom(atom_to_list(AttrName) ++ "_" ++ atom_to_list(Op)), - #relation_constraints{constraints = [{Name, op_to_constraint(Op, AttrName, Value)}]}; -infer_constraints_from_pred({'and', Predicates}, Schema) -> - lists:foldl( - fun(Pred, Acc) -> - merge_constraints(Acc, infer_constraints_from_pred(Pred, Schema)) - end, - empty_constraints(), - Predicates - ); -infer_constraints_from_pred({'or', Predicates}, Schema) -> - OrParts = [ - constraint_from_predicate(P, Schema) || P <- Predicates, - constraint_from_predicate(P, Schema) =/= undefined - ], - case OrParts of - [] -> empty_constraints(); - _ -> #relation_constraints{constraints = [{inferred_or, {'or', OrParts}}]} - end; -infer_constraints_from_pred(_, _Schema) -> - empty_constraints(). - -constraint_from_predicate({attr, AttrName, Op, Value}, _Schema) -> - op_to_constraint(Op, AttrName, Value); -constraint_from_predicate({'and', Predicates}, Schema) -> - {'and', [C || C <- [constraint_from_predicate(P, Schema) || P <- Predicates], C =/= undefined]}; -constraint_from_predicate({'or', Predicates}, Schema) -> - {'or', [C || C <- [constraint_from_predicate(P, Schema) || P <- Predicates], C =/= undefined]}; -constraint_from_predicate(_, _Schema) -> - undefined. - -op_to_constraint(lt, Attr, Value) -> lt({var, Attr}, Value); -op_to_constraint(lte, Attr, Value) -> lte({var, Attr}, Value); -op_to_constraint(gt, Attr, Value) -> gt({var, Attr}, Value); -op_to_constraint(gte, Attr, Value) -> gte({var, Attr}, Value); -op_to_constraint(eq, Attr, Value) -> eq({var, Attr}, Value); -op_to_constraint(neq, Attr, Value) -> neq({var, Attr}, Value); -op_to_constraint(between, Attr, {Min, Max}) -> {'and', [gte({var, Attr}, Min), lt({var, Attr}, Max)]}; -op_to_constraint(_, _Attr, _Value) -> {'and', []}. - -normalize_constraints(undefined) -> - empty_constraints(); -normalize_constraints(#relation_constraints{} = Constraints) -> - NormalizedEntries = normalize_named_constraints(Constraints#relation_constraints.constraints), - assert_unique_constraint_names(NormalizedEntries), - Constraints#relation_constraints{constraints = NormalizedEntries}; -normalize_constraints(_) -> - empty_constraints(). - -normalize_named_constraints(Entries) -> - [normalize_named_constraint(Entry) || Entry <- Entries]. - -normalize_named_constraint({Name, Formula}) when is_atom(Name) -> - {Name, Formula}; -normalize_named_constraint(InvalidEntry) -> - error({invalid_constraint_entry, InvalidEntry}). - -assert_unique_constraint_names(NamedConstraints) -> - Names = [Name || {Name, _Formula} <- NamedConstraints], - case has_duplicates(Names) of - true -> - error({duplicate_constraint_names, Names}); - false -> - ok - end. - -has_duplicates([]) -> - false; -has_duplicates([Name | Rest]) -> - lists:member(Name, Rest) orelse has_duplicates(Rest). - -vars_in_constraint({member_of, _Rel, Binding}) when is_map(Binding) -> - maps:fold( - fun(_K, V, Acc) -> - Acc ++ vars_in_term(V) - end, - [], - Binding); -vars_in_constraint({'and', Cs}) -> lists:usort(lists:flatmap(fun vars_in_constraint/1, Cs)); -vars_in_constraint({'or', Cs}) -> lists:usort(lists:flatmap(fun vars_in_constraint/1, Cs)); -vars_in_constraint({'not', C}) -> vars_in_constraint(C); -vars_in_constraint({'not', C, _}) -> vars_in_constraint(C); -vars_in_constraint({exists, Var, _Rel, C}) -> lists:delete(Var, vars_in_constraint(C)); -vars_in_constraint({forall, Var, _Rel, C}) -> lists:delete(Var, vars_in_constraint(C)); -vars_in_constraint(_) -> []. - -vars_in_term({var, Name}) when is_atom(Name) -> [Name]; -vars_in_term({const, _}) -> []; -vars_in_term(T) when is_tuple(T) -> - lists:flatmap(fun vars_in_term/1, tuple_to_list(T)); -vars_in_term(T) when is_list(T) -> - lists:flatmap(fun vars_in_term/1, T); -vars_in_term(T) when is_map(T) -> - maps:fold(fun(_K, V, Acc) -> Acc ++ vars_in_term(V) end, [], T); -vars_in_term(_) -> []. - -rename_vars_in_constraint({member_of, RelName, Binding}, Mappings) -> - RenamedBinding = maps:map( - fun(_K, {var, VarName}) -> - {var, maps:get(VarName, Mappings, VarName)}; - (_K, V) -> - V - end, - Binding - ), - {member_of, RelName, RenamedBinding}; -rename_vars_in_constraint({'and', Constraints}, Mappings) -> - {'and', [rename_vars_in_constraint(C, Mappings) || C <- Constraints]}; -rename_vars_in_constraint({'or', Constraints}, Mappings) -> - {'or', [rename_vars_in_constraint(C, Mappings) || C <- Constraints]}; -rename_vars_in_constraint({'not', Constraint}, Mappings) -> - {'not', rename_vars_in_constraint(Constraint, Mappings)}; -rename_vars_in_constraint({'not', Constraint, Universe}, Mappings) -> - {'not', rename_vars_in_constraint(Constraint, Mappings), Universe}; -rename_vars_in_constraint({exists, Var, Rel, Constraint}, Mappings) -> - {exists, maps:get(Var, Mappings, Var), Rel, rename_vars_in_constraint(Constraint, Mappings)}; -rename_vars_in_constraint({forall, Var, Rel, Constraint}, Mappings) -> - {forall, maps:get(Var, Mappings, Var), Rel, rename_vars_in_constraint(Constraint, Mappings)}; -rename_vars_in_constraint(Other, _Mappings) -> - Other. - -validate_tuple_against_criteria(Tuple, Criteria) when is_map(Criteria) -> - maps:fold( - fun(Attr, Constraint, Acc) -> - Acc andalso validate_attribute(maps:get(Attr, Tuple, undefined), Constraint) - end, - true, - Criteria - ). - -validate_attribute(undefined, _) -> false; -validate_attribute(Value, #{test := Test}) -> Test(#{value => Value}); -validate_attribute(Value, Constraint) when is_function(Constraint, 1) -> Constraint(Value); -validate_attribute(_, _) -> true. - -apply_substitution(Binding, Substitution) -> - maps:map( - fun(_K, {var, VarName}) -> - maps:get(VarName, Substitution, {var, VarName}); - (_K, V) -> - V - end, - Binding - ). - -find_variables(Binding) -> - maps:fold( - fun(_K, {var, VarName}, Acc) -> [VarName | Acc]; - (_K, _, Acc) -> Acc - end, - [], - Binding - ). - -get_schema(#domain{schema = S}) -> S; -get_schema(#relation{schema = S}) -> S. - -get_name(#domain{name = N}) -> N; -get_name(#relation{name = N}) -> N. - -get_lineage(#relation{lineage = L}) -> L; -get_lineage(#domain{name = N}) -> {base, N}. - -schemas_compatible(S1, S2) -> - maps:keys(S1) =:= maps:keys(S2). - -merge_schemas(S1, _S2) -> - S1. - -get_cardinality(#domain{cardinality = C}) -> C; -get_cardinality(#relation{cardinality = C}) -> C. - -complement_cardinality(R, Universe) -> - RC = get_cardinality(R), - UC = get_cardinality(Universe), - case {RC, UC} of - {{finite, N}, {finite, M}} -> {finite, max(0, M - N)}; - {{finite, _}, Infinite} -> Infinite; - _ -> UC - end. - -intersection_cardinality(R1, R2) -> - C1 = get_cardinality(R1), - C2 = get_cardinality(R2), - case {C1, C2} of - {{finite, N}, _} -> {finite, N}; - {_, {finite, M}} -> {finite, M}; - _ -> min_cardinality(C1, C2) - end. - -union_cardinality(R1, R2) -> - C1 = get_cardinality(R1), - C2 = get_cardinality(R2), - case {C1, C2} of - {{finite, N}, {finite, M}} -> {finite, N + M}; - _ -> max_cardinality(C1, C2) - end. - -min_cardinality({finite, N}, {finite, M}) -> {finite, min(N, M)}; -min_cardinality({finite, N}, _) -> {finite, N}; -min_cardinality(_, {finite, M}) -> {finite, M}; -min_cardinality(aleph_zero, _) -> aleph_zero; -min_cardinality(_, aleph_zero) -> aleph_zero; -min_cardinality(continuum, continuum) -> continuum. - -max_cardinality({finite, N}, {finite, M}) -> {finite, max(N, M)}; -max_cardinality(continuum, _) -> continuum; -max_cardinality(_, continuum) -> continuum; -max_cardinality(aleph_zero, _) -> aleph_zero; -max_cardinality(_, aleph_zero) -> aleph_zero. - -evaluate_constraint(Database, {member_of, RelName, Binding}, Context) when is_atom(RelName) -> - BoundBinding = bind_variables(Binding, Context), - case get_domain_from_db(Database, RelName) of - {ok, Relation} -> - {ok, member(BoundBinding, Relation)}; - {error, not_found} -> - {error, {relation_not_found, RelName}} - end; -evaluate_constraint(_Database, {member_of, #relation{} = Rel, Binding}, Context) -> - BoundBinding = bind_variables(Binding, Context), - {ok, member(BoundBinding, Rel)}; -evaluate_constraint(_Database, {member_of, #domain{} = Rel, Binding}, Context) -> - BoundBinding = bind_variables(Binding, Context), - {ok, member(BoundBinding, Rel)}; -evaluate_constraint(Database, {'not', Constraint, _Universe}, Context) -> - case evaluate_constraint(Database, Constraint, Context) of - {ok, Bool} -> {ok, not Bool}; - Error -> Error - end; -evaluate_constraint(Database, {'and', Constraints}, Context) -> - Results = [evaluate_constraint(Database, C, Context) || C <- Constraints], - case lists:all(fun({ok, true}) -> true; (_) -> false end, Results) of - true -> {ok, true}; - false -> {ok, false} - end; -evaluate_constraint(Database, {'or', Constraints}, Context) -> - Results = [evaluate_constraint(Database, C, Context) || C <- Constraints], - case lists:any(fun({ok, true}) -> true; (_) -> false end, Results) of - true -> {ok, true}; - false -> {ok, false} - end; -evaluate_constraint(Database, {'not', Constraint}, Context) -> - {Result, _Diagnostics} = evaluate_constraint_with_diagnostics(Database, {'not', Constraint}, Context), - {ok, Result}; -evaluate_constraint(Database, {exists, VarName, QuantifierRel, Constraint}, Context) -> - {Result, _Diagnostics} = evaluate_constraint_with_diagnostics(Database, {exists, VarName, QuantifierRel, Constraint}, Context), - {ok, Result}; -evaluate_constraint(Database, {forall, VarName, QuantifierRel, Constraint}, Context) -> - {Result, _Diagnostics} = evaluate_constraint_with_diagnostics(Database, {forall, VarName, QuantifierRel, Constraint}, Context), - {ok, Result}; -evaluate_constraint(_Database, _, _) -> - {error, unsupported_constraint}. - -bind_variables(Binding, Context) -> - maps:map( - fun(_K, {var, VarName}) -> - maps:get(VarName, Context, maps:get(value, Context, undefined)); - (_K, {const, Value}) -> - Value; - (_K, V) -> - V - end, - Binding - ). - --spec get_domain_from_db(#database_state{}, atom()) -> {ok, #relation{}} | {error, not_found}. -get_domain_from_db(Database, DomainName) -> - case maps:find(DomainName, Database#database_state.relations) of - {ok, DomainHash} -> - [Domain] = mnesia:dirty_read(relation, DomainHash), - {ok, Domain}; - error -> - {error, not_found} - end. diff --git a/src/generators.erl b/src/generators.erl deleted file mode 100644 index 37facc3..0000000 --- a/src/generators.erl +++ /dev/null @@ -1,584 +0,0 @@ -%%% @doc Generators for Infinite Relations -%%% -%%% This module provides generator functions for primitive infinite relations. -%%% -%%% == Domain Relations (Base Types) == -%%% -%%% Domain relations are unary relations representing mathematical sets: -%%% <ul> -%%% <li>Naturals (ℕ): {(0), (1), (2), (3), ...}</li> -%%% <li>Integers (ℤ): {(0), (1), (-1), (2), (-2), ...}</li> -%%% <li>Rationals (ℚ): {(0/1), (1/1), (1/2), (2/1), ...}</li> -%%% </ul> -%%% -%%% Domain relations have empty schemas (`schema => #{}') as they are the -%%% base case in the type system. -%%% -%%% == Function Relations == -%%% -%%% Function relations represent mathematical operations as infinite relations: -%%% <ul> -%%% <li>Plus: {(a, b, sum) | a ∈ ℤ, b ∈ ℤ, sum = a + b}</li> -%%% <li>Times: {(a, b, product) | a ∈ ℤ, b ∈ ℤ, product = a × b}</li> -%%% <li>Minus: {(a, b, difference) | a ∈ ℤ, b ∈ ℤ, difference = a - b}</li> -%%% <li>Divide: {(a, b, q, r) | a ∈ ℤ, b ∈ ℤ\{0}, a = b×q + r}</li> -%%% </ul> -%%% -%%% Function relations reference domain relations in their schemas: -%%% <pre> -%%% schema => #{a => integers, b => integers, sum => integers} -%%% </pre> -%%% -%%% == Reversibility == -%%% -%%% Function relations support bidirectional querying (like Prolog): -%%% <ul> -%%% <li>Plus[1, 2, ?] yields ? = 3 (forward)</li> -%%% <li>Plus[1, ?, 3] yields ? = 2 (backward, solve for b)</li> -%%% <li>Plus[?, 2, 3] yields ? = 1 (backward, solve for a)</li> -%%% <li>Plus[?, ?, 5] yields all pairs (a,b) where a+b=5</li> -%%% </ul> -%%% -%%% The generators use constraint analysis to determine which arguments -%%% are bound and compute the missing values accordingly. -%%% -%%% == Relational Composition == -%%% -%%% In the future, function relations will be used through joins: -%%% <pre> -%%% Integer[A], Integer[B], Plus[A, B, Sum] -%%% </pre> -%%% -%%% This corresponds to a three-way join where the join conditions -%%% provide the constraints to each relation. -%%% -%%% Generators produce tuples lazily based on constraints, enabling -%%% memory-bounded iteration over infinite relations. -%%% -%%% @author Nekoma Team -%%% @copyright 2025 - --module(generators). --include("operations.hrl"). - --export([ - boolean/1, - natural/1, - integer/1, - rational/1, - make_range_generator/3, - constrained_natural/2, - constrained_integer/2, - %% Function relations - plus/1, - times/1, - minus/1, - divide/1 -]). - -%%% ============================================================================ -%%% 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, -%% only generates numbers within that range. -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing naturals -natural(Constraints) -> - case extract_bounds(Constraints, value) of - {range, Min, Max} when Min >= 0 -> - make_range_generator(Min, Max, fun(N) -> #{value => N} end); - {range, Min, Max} when Min < 0, Max >= 0 -> - %% Negative min for naturals: adjust to start at 0 - make_range_generator(0, Max, fun(N) -> #{value => N} end); - {range, _Min, Max} when Max < 0 -> - %% Entire range is negative: no naturals exist - fun(_) -> done end; - {gte, Min} when Min >= 0 -> - make_unbounded_generator(Min, fun(N) -> #{value => N} end); - {gte, Min} when Min < 0 -> - %% Negative lower bound for naturals: start at 0 - make_unbounded_generator(0, fun(N) -> #{value => N} end); - {lte, Max} when Max >= 0 -> - make_range_generator(0, Max, fun(N) -> #{value => N} end); - {lte, Max} when Max < 0 -> - %% Upper bound is negative: no naturals exist - fun(_) -> done end; - {eq, Value} when Value >= 0 -> - make_singleton_generator(#{value => Value}); - {eq, _Value} -> - %% Negative value: not a natural - fun(_) -> done end; - {in, List} -> - make_membership_generator(List, fun(N) -> #{value => N} end); - unbounded -> - make_unbounded_generator(0, fun(N) -> #{value => N} end); - {error, Reason} -> - fun(_) -> {error, Reason} end - end. - -%% @doc Generator for integers (ℤ = {..., -2, -1, 0, 1, 2, ...}). -%% -%% Enumerates integers using interleaving strategy: -%% 0, 1, -1, 2, -2, 3, -3, ... -%% -%% Mapping: f(0) = 0 -%% f(2n) = n for n > 0 -%% f(2n+1) = -n for n > 0 -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing integers -integer(Constraints) -> - case extract_bounds(Constraints, value) of - {range, Min, Max} -> - make_integer_range_generator(Min, Max); - {gte, Min} -> - make_unbounded_integer_generator(Min, infinity); - {lte, Max} -> - make_unbounded_integer_generator(neg_infinity, Max); - {eq, Value} -> - make_singleton_generator(#{value => Value}); - {in, List} -> - make_membership_generator(List, fun(N) -> #{value => N} end); - unbounded -> - make_interleaved_integer_generator(); - {error, Reason} -> - fun(_) -> {error, Reason} end - end. - -%% @doc Generator for rational numbers (ℚ) using Stern-Brocot tree. -%% -%% Enumerates all rational numbers in reduced form (p/q where gcd(p,q) = 1) -%% using the Stern-Brocot tree, which systematically generates all positive -%% rationals without repetition. -%% -%% Schema: #{numerator => integer, denominator => natural} -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing rationals -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}}, - make_stern_brocot_generator(InitialState, Constraints). - -%%% ============================================================================ -%%% Helper: Constraint Extraction -%%% ============================================================================ - -%% @doc Extract bounds from constraints for a given attribute. -%% -%% @param Constraints Constraint map -%% @param Attr Attribute name -%% @returns {range, Min, Max} | {gte, Min} | {lte, Max} | {eq, Value} | unbounded -extract_bounds(Constraints, Attr) -> - case maps:get(Attr, Constraints, undefined) of - undefined -> - unbounded; - {range, Min, Max} -> - {range, Min, Max}; - {gte, Min} -> - {gte, Min}; - {lte, Max} -> - {lte, Max}; - {gt, Min} -> - {gte, Min + 1}; - {lt, Max} -> - {lte, Max - 1}; - {eq, Value} -> - {eq, Value}; - {in, List} -> - {in, List}; - Other -> - {error, {unsupported_constraint, Other}} - end. - -%%% ============================================================================ -%%% Generator Constructors -%%% ============================================================================ - -%% @doc Create a generator for a finite range [Min, Max]. -make_range_generator(Min, Max, MapFun) when Min =< Max -> - make_range_gen(Min, Max, MapFun). - -make_range_gen(Current, Max, MapFun) when Current =< Max -> - fun(next) -> - Tuple = MapFun(Current), - NextGen = make_range_gen(Current + 1, Max, MapFun), - {value, Tuple, NextGen} - end; -make_range_gen(_, _, _) -> - fun(_) -> done end. - -%% @doc Create an unbounded generator starting from Min. -make_unbounded_generator(Start, MapFun) -> - make_unbounded_gen(Start, MapFun). - -make_unbounded_gen(Current, MapFun) -> - fun(next) -> - Tuple = MapFun(Current), - NextGen = make_unbounded_gen(Current + 1, MapFun), - {value, Tuple, NextGen} - end. - -%% @doc Create a singleton generator (single value). -make_singleton_generator(Tuple) -> - fun(next) -> {value, Tuple, fun(_) -> done end} end. - -%% @doc Create a generator from a membership list. -make_membership_generator([], _MapFun) -> - fun(_) -> done end; -make_membership_generator([H|T], MapFun) -> - fun(next) -> - Tuple = MapFun(H), - NextGen = make_membership_generator(T, MapFun), - {value, Tuple, NextGen} - end. - -%% @doc Create integer range generator. -make_integer_range_generator(Min, Max) when Min =< Max -> - make_range_generator(Min, Max, fun(N) -> #{value => N} end); -make_integer_range_generator(_, _) -> - fun(_) -> done end. - -%% @doc Create interleaved integer generator: 0, 1, -1, 2, -2, 3, -3, ... -make_interleaved_integer_generator() -> - make_interleaved_gen(0). - -make_interleaved_gen(0) -> - fun(next) -> - {value, #{value => 0}, make_interleaved_gen(1)} - end; -make_interleaved_gen(N) -> - fun(next) -> - Positive = #{value => N}, - NextGen1 = fun(next) -> - Negative = #{value => -N}, - NextGen2 = make_interleaved_gen(N + 1), - {value, Negative, NextGen2} - end, - {value, Positive, NextGen1} - end. - -%% @doc Unbounded integer generator with optional min/max bounds. -make_unbounded_integer_generator(neg_infinity, infinity) -> - make_interleaved_integer_generator(); -make_unbounded_integer_generator(Min, infinity) when is_integer(Min) -> - make_unbounded_generator(Min, fun(N) -> #{value => N} end); -make_unbounded_integer_generator(neg_infinity, Max) when is_integer(Max) -> - %% Generate from Max down to -infinity - make_decreasing_gen(Max); -make_unbounded_integer_generator(Min, Max) when is_integer(Min), is_integer(Max) -> - make_integer_range_generator(Min, Max). - -make_decreasing_gen(Current) -> - fun(next) -> - Tuple = #{value => Current}, - NextGen = make_decreasing_gen(Current - 1), - {value, Tuple, NextGen} - end. - -%% @doc Stern-Brocot tree generator for rationals. -%% -%% The Stern-Brocot tree enumerates all positive rationals exactly once. -%% Each rational p/q is generated in reduced form. -%% -%% Algorithm: -%% 1. Start with two fractions: 0/1 (left ancestor) and 1/0 (right ancestor) -%% 2. The mediant of a/b and c/d is (a+c)/(b+d) -%% 3. Build tree by computing mediants -make_stern_brocot_generator(State, _Constraints) -> - make_sb_gen(State). - -make_sb_gen({Queue, {LA, LB}, {RA, RB}}) -> - fun(next) -> - case queue:out(Queue) of - {empty, _} -> - done; - {{value, {P, Q}}, RestQueue} -> - %% Current rational is P/Q - Tuple = #{numerator => P, denominator => Q}, - - %% Generate children (mediants) - %% Left child: mediant of left ancestor and current - %% Right child: mediant of current and right ancestor - LeftChild = {LA + P, LB + Q}, - RightChild = {P + RA, Q + RB}, - - %% Enqueue children - NewQueue = queue:in(RightChild, queue:in(LeftChild, RestQueue)), - - %% Continue with updated state - NextGen = make_sb_gen({NewQueue, {LA, LB}, {RA, RB}}), - {value, Tuple, NextGen} - end - end. - -%%% ============================================================================ -%%% Constrained Generators (Public API) -%%% ============================================================================ - -%% @doc Create a constrained 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 integer generator. --spec constrained_integer(integer(), integer()) -> generator_fun(). -constrained_integer(Min, Max) -> - integer(#{value => {range, Min, Max}}). - -%%% ============================================================================ -%%% Function Relations -%%% ============================================================================ - -%% @doc Plus relation: {(a, b, sum) | sum = a + b}. -%% -%% Generates tuples for the addition relation. Requires at least 2 of 3 -%% attributes to be constrained for bounded generation. -%% -%% Constraint strategies: -%% <ul> -%% <li>a, b constrained → compute sum</li> -%% <li>a, sum constrained → compute b = sum - a</li> -%% <li>b, sum constrained → compute a = sum - b</li> -%% <li>sum constrained only → generate all (a,b) pairs that sum to value</li> -%% <li>Less than 1 constrained → error (unbounded)</li> -%% </ul> -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing plus tuples -plus(Constraints) -> - ABounds = extract_bounds(Constraints, a), - BBounds = extract_bounds(Constraints, b), - SumBounds = extract_bounds(Constraints, sum), - - case {ABounds, BBounds, SumBounds} of - %% Both operands constrained - generate sums - {{range, AMin, AMax}, {range, BMin, BMax}, _} -> - make_plus_ab_generator(AMin, AMax, BMin, BMax); - - %% a and sum constrained - compute b - {{range, AMin, AMax}, _, {range, SMin, SMax}} -> - make_plus_a_sum_generator(AMin, AMax, SMin, SMax); - - %% b and sum constrained - compute a - {_, {range, BMin, BMax}, {range, SMin, SMax}} -> - make_plus_b_sum_generator(BMin, BMax, SMin, SMax); - - %% Only sum constrained - generate all pairs - {unbounded, unbounded, {eq, SumValue}} -> - make_plus_sum_only_generator(SumValue); - - {unbounded, unbounded, {range, SMin, SMax}} -> - make_plus_sum_range_generator(SMin, SMax); - - %% Insufficient constraints - _ -> - fun(_) -> {error, {unbounded_plus, Constraints}} end - end. - -%% @doc Times relation: {(a, b, product) | product = a * b}. -%% -%% Generates tuples for the multiplication relation. -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing times tuples -times(Constraints) -> - ABounds = extract_bounds(Constraints, a), - BBounds = extract_bounds(Constraints, b), - ProductBounds = extract_bounds(Constraints, product), - - case {ABounds, BBounds, ProductBounds} of - %% Both operands constrained - generate products - {{range, AMin, AMax}, {range, BMin, BMax}, _} -> - make_times_ab_generator(AMin, AMax, BMin, BMax); - - %% Insufficient constraints - _ -> - fun(_) -> {error, {unbounded_times, Constraints}} end - end. - -%% @doc Minus relation: {(a, b, difference) | difference = a - b}. -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing minus tuples -minus(Constraints) -> - ABounds = extract_bounds(Constraints, a), - BBounds = extract_bounds(Constraints, b), - DiffBounds = extract_bounds(Constraints, difference), - - case {ABounds, BBounds, DiffBounds} of - {{range, AMin, AMax}, {range, BMin, BMax}, _} -> - make_minus_ab_generator(AMin, AMax, BMin, BMax); - - _ -> - fun(_) -> {error, {unbounded_minus, Constraints}} end - end. - -%% @doc Divide relation: {(a, b, quotient) | quotient = a / b, b ≠ 0}. -%% -%% @param Constraints Map of attribute constraints -%% @returns Generator function producing divide tuples -divide(Constraints) -> - ABounds = extract_bounds(Constraints, a), - BBounds = extract_bounds(Constraints, b), - - case {ABounds, BBounds} of - {{range, AMin, AMax}, {range, BMin, BMax}} when BMin =/= 0 orelse BMax =/= 0 -> - make_divide_ab_generator(AMin, AMax, BMin, BMax); - - _ -> - fun(_) -> {error, {unbounded_divide, Constraints}} end - end. - -%%% ============================================================================ -%%% Function Relation Generator Helpers -%%% ============================================================================ - -%% Plus: a and b constrained -make_plus_ab_generator(AMin, AMax, BMin, BMax) -> - Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)], - make_plus_pairs_gen(Pairs). - -make_plus_pairs_gen([]) -> - fun(_) -> done end; -make_plus_pairs_gen([{A, B} | Rest]) -> - fun(next) -> - Tuple = #{a => A, b => B, sum => A + B}, - NextGen = make_plus_pairs_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Plus: a and sum constrained, compute b -make_plus_a_sum_generator(AMin, AMax, SMin, SMax) -> - Pairs = [{A, S} || - A <- lists:seq(AMin, AMax), - S <- lists:seq(SMin, SMax), - (S - A) >= 0], % b must be non-negative if we want naturals - make_plus_a_sum_gen(Pairs). - -make_plus_a_sum_gen([]) -> - fun(_) -> done end; -make_plus_a_sum_gen([{A, Sum} | Rest]) -> - fun(next) -> - B = Sum - A, - Tuple = #{a => A, b => B, sum => Sum}, - NextGen = make_plus_a_sum_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Plus: b and sum constrained, compute a -make_plus_b_sum_generator(BMin, BMax, SMin, SMax) -> - Pairs = [{B, S} || - B <- lists:seq(BMin, BMax), - S <- lists:seq(SMin, SMax), - (S - B) >= 0], - make_plus_b_sum_gen(Pairs). - -make_plus_b_sum_gen([]) -> - fun(_) -> done end; -make_plus_b_sum_gen([{B, Sum} | Rest]) -> - fun(next) -> - A = Sum - B, - Tuple = #{a => A, b => B, sum => Sum}, - NextGen = make_plus_b_sum_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Plus: only sum constrained - generate all non-negative pairs -make_plus_sum_only_generator(SumValue) when SumValue >= 0 -> - Pairs = [{A, SumValue - A} || A <- lists:seq(0, SumValue)], - make_plus_pairs_gen(Pairs); -make_plus_sum_only_generator(_SumValue) -> - %% Negative sum: no non-negative pairs exist - fun(_) -> done end. - -%% Plus: sum range constrained -make_plus_sum_range_generator(SMin, SMax) -> - %% Adjust range to non-negative values (naturals only) - AdjustedMin = max(0, SMin), - Pairs = [{A, B, S} || - S <- lists:seq(AdjustedMin, SMax), - A <- lists:seq(0, S), - B <- [S - A]], - make_plus_triple_gen(Pairs). - -make_plus_triple_gen([]) -> - fun(_) -> done end; -make_plus_triple_gen([{A, B, Sum} | Rest]) -> - fun(next) -> - Tuple = #{a => A, b => B, sum => Sum}, - NextGen = make_plus_triple_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Times: a and b constrained -make_times_ab_generator(AMin, AMax, BMin, BMax) -> - Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)], - make_times_pairs_gen(Pairs). - -make_times_pairs_gen([]) -> - fun(_) -> done end; -make_times_pairs_gen([{A, B} | Rest]) -> - fun(next) -> - Tuple = #{a => A, b => B, product => A * B}, - NextGen = make_times_pairs_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Minus: a and b constrained -make_minus_ab_generator(AMin, AMax, BMin, BMax) -> - Pairs = [{A, B} || A <- lists:seq(AMin, AMax), B <- lists:seq(BMin, BMax)], - make_minus_pairs_gen(Pairs). - -make_minus_pairs_gen([]) -> - fun(_) -> done end; -make_minus_pairs_gen([{A, B} | Rest]) -> - fun(next) -> - Tuple = #{a => A, b => B, difference => A - B}, - NextGen = make_minus_pairs_gen(Rest), - {value, Tuple, NextGen} - end. - -%% Divide: a and b constrained (integer division) -make_divide_ab_generator(AMin, AMax, BMin, BMax) -> - Pairs = [{A, B} || - A <- lists:seq(AMin, AMax), - B <- lists:seq(BMin, BMax), - B =/= 0], % Avoid division by zero - make_divide_pairs_gen(Pairs). - -make_divide_pairs_gen([]) -> - fun(_) -> done end; -make_divide_pairs_gen([{A, B} | Rest]) -> - fun(next) -> - Tuple = #{a => A, b => B, quotient => A div B, remainder => A rem B}, - NextGen = make_divide_pairs_gen(Rest), - {value, Tuple, NextGen} - end. diff --git a/src/main.app.src b/src/main.app.src deleted file mode 100644 index 34e2f46..0000000 --- a/src/main.app.src +++ /dev/null @@ -1,15 +0,0 @@ -{application, main, [ - {description, "A relational algebra engine"}, - {vsn, "0.1.0"}, - {registered, []}, - {mod, {main, []}}, - {applications, [ - kernel, - stdlib, - mnesia - ]}, - {env, []}, - {modules, []}, - {licenses, ["Apache-2.0"]}, - {links, []} - ]}. diff --git a/src/main.erl b/src/main.erl deleted file mode 100644 index 323d054..0000000 --- a/src/main.erl +++ /dev/null @@ -1,66 +0,0 @@ --module(main). --behaviour(application). - --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, 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 - io:format("Starting app...~n"), - - %% Ensure Mnesia is started - mnesia:start(), - setup(), - _ = uuid(), - - {ok, self()}. - -stop(_State) -> - io:format("Stopping app...~n"), - ok. diff --git a/src/operations.erl b/src/operations.erl deleted file mode 100644 index de61fd8..0000000 --- a/src/operations.erl +++ /dev/null @@ -1,1484 +0,0 @@ -%%% @doc Extended Relational Database Operations (RM/T) -%%% -%%% This module implements core database operations for Sakura, an extended -%%% relational database engine based on E. F. Codd's RM/T (1979). -%%% -%%% == Architecture == -%%% -%%% The system uses: -%%% <ul> -%%% <li><b>Content-Addressed Storage</b> - All entities identified by SHA-256 hashes</li> -%%% <li><b>Immutable Data Structures</b> - Operations create new versions</li> -%%% <li><b>Merkle Trees</b> - Efficient versioning and diffing via merklet</li> -%%% <li><b>Mnesia Backend</b> - ACID transactions and persistent storage</li> -%%% <li><b>Volcano Iterator Model</b> - Lazy evaluation with process-based iterators</li> -%%% </ul> -%%% -%%% == Data Model == -%%% -%%% The system maintains four tables in Mnesia: -%%% <ul> -%%% <li>`attribute' - Stores atomic values with their hashes</li> -%%% <li>`tuple' - Stores tuples as maps from attribute names to value hashes</li> -%%% <li>`relation' - Stores relations with merkle trees of tuple hashes</li> -%%% <li>`database_state' - Stores database snapshots with relation merkle trees</li> -%%% </ul> -%%% -%%% == RM/T Integrity Rules == -%%% -%%% <ul> -%%% <li><b>Rule 3 (Entity Integrity)</b> - E-relations accept insertions/deletions, not updates</li> -%%% <li><b>Rule 4 (Property Integrity)</b> - Tuples require entity existence in E-relation</li> -%%% </ul> -%%% -%%% @author Nekoma Team -%%% @copyright 2025 -%%% @version 0.1.0 -%%% @reference E. F. Codd (1979). "Extending the Database Relational Model to Capture More Meaning" -%%% @reference E. F. Codd (1970). "A Relational Model of Data for Large Shared Data Banks" - --module(operations). --include("../include/operations.hrl"). --export([ - create_database/1, - value_hash/1, - create_relation/3, - create_immutable_relation/2, - update_relation_constraints/3, - 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_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, - %% Iterator operators (lazy) - select_iterator/2, - project_iterator/2, - sort_iterator/2, - take_iterator/2, - %% Join operators - equijoin_iterator/3, - theta_join_iterator/3, - %% Materialization (eager) - materialize/3 - ]). - -%% @private -%% @doc Compute SHA-256 hash of an Erlang term. -%% -%% This is the foundational hashing function used throughout the system for -%% content addressing. All entities (attributes, tuples, relations, databases) -%% are identified by hashes computed with this function. -%% -%% @param Value Any Erlang term to hash -%% @returns Binary SHA-256 hash (32 bytes) -%% -%% @see create_tuple/3 -%% @see create_relation/3 -hash(Value) -> - crypto:hash(sha256, term_to_binary(Value)). - -%% @doc Hash a value using Sakura's canonical content hash. -%% -%% Public wrapper around the internal hash function, used by other modules -%% that need to compare values against stored attribute hashes. -%% -%% @param Value Any Erlang term -%% @returns Binary SHA-256 hash --spec value_hash(term()) -> binary(). -value_hash(Value) -> - hash(Value). - -%% @doc Insert a tuple into a relation and update the database state. -%% -%% This is the primary operation for adding data to the database. It: -%% <ol> -%% <li>Stores each attribute value with its hash (automatic deduplication)</li> -%% <li>Creates a tuple record mapping attribute names to value hashes</li> -%% <li>Inserts the tuple hash into the relation's merkle tree</li> -%% <li>Computes new relation hash from updated tree</li> -%% <li>Updates database merkle tree with new relation hash</li> -%% <li>Computes new database hash</li> -%% </ol> -%% -%% All operations execute within a Mnesia transaction for ACID guarantees. -%% -%% == Example == -%% <pre> -%% 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}). -%% </pre> -%% -%% @param Database `#database_state{}' record -%% @param RelationName Atom naming the relation -%% @param Tuple Map of attribute names to values (e.g., `#{name => "Alice", age => 30}') -%% @returns `{UpdatedDatabase, UpdatedRelation}' tuple -%% -%% @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), - %% Validate tuple against relation schema before insertion - case constraint:validate_tuple(Database, Tuple, RelationRecord) of - ok -> - create_tuple_internal(Database, RelationName, Tuple, RelationRecord); - {error, Reason} -> - {error, {constraint_violation, Reason}} - end. - -%% @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 - AttributeMap = maps:map(fun(_AttrName, Value) -> - ValueHash = hash(Value), - mnesia:write(attribute, #attribute{hash = ValueHash, value = Value}, write), - ValueHash - end, Tuple), - - %% Step 2: Compute tuple hash and store tuple - TupleHash = hash(Tuple), - mnesia:write(tuple, #tuple{hash = TupleHash, relation = RelationName, attribute_map = AttributeMap}, write), - - %% Step 3: Get current relation hash from database - CurrentRelationHash = maps:get(RelationName, Database#database_state.relations), - - %% Step 4: Read current relation - [RelationRecord] = mnesia:read(relation, CurrentRelationHash), - - %% Step 5: Insert tuple hash into relation merkle tree - %% We don't need to store the content of a tuple hash, just the key - %% merklet can spot the difference in both keys and values - %% sets:set follows the same strategy of an empty value - NewRelationTree = merklet:insert({TupleHash, <<>>}, RelationRecord#relation.tree), - - %% Step 6: Compute new relation hash as the root of the new merkle tree and store - {_,NewRelationTreeHash,_,_} = NewRelationTree, - NewRelationHash = hash({RelationRecord#relation.name, RelationRecord#relation.schema, NewRelationTreeHash}), - - %% Update cardinality: increment by 1 - NewCardinality = case RelationRecord#relation.cardinality of - {finite, N} -> {finite, N + 1}; - Other -> Other % Shouldn't happen for finite relations - end, - - UpdatedRelation = #relation{ - hash = NewRelationHash, - name = RelationName, - tree = NewRelationTree, - schema = RelationRecord#relation.schema, - constraints = RelationRecord#relation.constraints, - cardinality = NewCardinality, - generator = RelationRecord#relation.generator, - provenance = RelationRecord#relation.provenance, - lineage = RelationRecord#relation.lineage, - membership_criteria = RelationRecord#relation.membership_criteria - }, - mnesia:write(relation, UpdatedRelation, write), - - %% Step 7: Update database relations map - NewRelations = maps:put(RelationName, NewRelationHash, Database#database_state.relations), - - %% Step 8: Update database tree (for diffing) - RelationKey = atom_to_binary(RelationName, utf8), - NewDatabaseTree = merklet:insert({RelationKey, NewRelationHash}, Database#database_state.tree), - - %% Step 9: Compute new database hash and store - {_,NewDatabaseHash,_,_} = NewDatabaseTree, - UpdatedDatabase = #database_state{ - name = Database#database_state.name, - hash = NewDatabaseHash, - tree = NewDatabaseTree, - relations = NewRelations, - timestamp = erlang:timestamp() - }, - mnesia:write(database_state, UpdatedDatabase, write), - - {UpdatedDatabase, UpdatedRelation} - end, - - {atomic, Result} = mnesia:transaction(F), - Result. - -%% @doc Clear all tuples from a relation (truncate). -%% -%% Wrapper for `clear_relation/3' with transactions enabled. -%% -%% @param Database `#database_state{}' record -%% @param RelationHash Binary hash identifying the relation -%% @returns `{atomic, {UpdatedDatabase, UpdatedRelation}}' or `{aborted, Reason}' -%% -%% @see clear_relation/3 -%% @see retract_relation/2 -clear_relation(Database, RelationHash) -> - clear_relation(Database, RelationHash, true). - -%% @doc Clear all tuples from a relation with optional transaction control. -%% -%% Removes all tuples from the relation but preserves its schema. The relation's -%% merkle tree is set to `undefined', and a new relation hash is computed. -%% -%% @param Database `#database_state{}' record -%% @param RelationHash Binary hash identifying the relation -%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction -%% @returns When `Transact =:= true': `{atomic, {UpdatedDatabase, UpdatedRelation}}' -%% When `Transact =:= false': `{UpdatedDatabase, UpdatedRelation}' -%% -%% @see retract_relation/2 -clear_relation(Database, RelationHash, Transact) -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - NewRelationHash = hash({Relation#relation.name, Relation#relation.schema, undefined}), - UpdatedRelation = - Relation#relation{hash = NewRelationHash, - tree = undefined}, - DatabaseTreeWithoutTuples = merklet:insert({atom_to_binary(Relation#relation.name, utf8), NewRelationHash}, Database#database_state.tree), - {_,NewDatabaseHash,_,_} = DatabaseTreeWithoutTuples, - NewRelations = maps:put(Relation#relation.name, NewRelationHash, Database#database_state.relations), - UpdatedDatabase = - Database#database_state{timestamp = erlang:timestamp(), - hash = NewDatabaseHash, - tree = DatabaseTreeWithoutTuples, - relations = NewRelations}, - TX = fun () -> - mnesia:write(relation, UpdatedRelation, write), - mnesia:write(database_state, UpdatedDatabase, write), - {UpdatedDatabase, UpdatedRelation} - end, - case Transact of - true -> mnesia:transaction(TX); - false -> {UpdatedDatabase, UpdatedRelation} - end. - -%% @doc Remove a tuple from a relation. -%% -%% Wrapper for `retract_tuple/4' with transactions enabled. -%% -%% @param Database `#database_state{}' record -%% @param RelationHash Binary hash identifying the relation -%% @param TupleHash Binary hash identifying the tuple to remove -%% @returns `{atomic, {UpdatedDatabase, UpdatedRelation}}' or `{aborted, Reason}' -%% -%% @see retract_tuple/4 -%% @see create_tuple/3 -retract_tuple(Database, RelationHash, TupleHash) -> - retract_tuple(Database, RelationHash, TupleHash, true). - -%% @doc Remove a tuple from a relation with optional transaction control. -%% -%% Deletes a specific tuple from the relation's merkle tree and recomputes -%% the relation and database hashes. -%% -%% @param Database `#database_state{}' record -%% @param RelationHash Binary hash identifying the relation -%% @param TupleHash Binary hash identifying the tuple to remove -%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction -%% @returns When `Transact =:= true': `{atomic, {UpdatedDatabase, UpdatedRelation}}' -%% When `Transact =:= false': `{UpdatedDatabase, UpdatedRelation}' -%% -%% @see create_tuple/3 -retract_tuple(Database, RelationHash, TupleHash, Transact) - when is_record(Database, database_state) -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - RelationTreeWithoutTuple = merklet:delete(TupleHash, Relation#relation.tree), - {_,NewRelationTreeHash,_,_} = RelationTreeWithoutTuple, - NewRelationHash = hash({Relation#relation.name, Relation#relation.schema, NewRelationTreeHash}), - DatabaseTreeWithoutTuple = merklet:insert({atom_to_binary(Relation#relation.name, utf8), NewRelationHash}, Database#database_state.tree), - {_,NewDatabaseHash,_,_} = DatabaseTreeWithoutTuple, - NewRelations = maps:put(Relation#relation.name, NewRelationHash, Database#database_state.relations), - UpdatedDatabase = - Database#database_state{timestamp = erlang:timestamp(), - hash = NewDatabaseHash, - tree = DatabaseTreeWithoutTuple, - relations = NewRelations}, - UpdatedRelation = - Relation#relation{hash = NewRelationHash, - tree = RelationTreeWithoutTuple}, - TX = fun () -> - mnesia:write(relation, UpdatedRelation, write), - mnesia:write(database_state, UpdatedDatabase, write), - {UpdatedDatabase, UpdatedRelation} - end, - case Transact of - true -> mnesia:transaction(TX); - false -> {UpdatedDatabase, UpdatedRelation} - end. - -%% @doc Remove a relation from the database. -%% -%% Wrapper for `retract_relation/3' with transactions enabled. -%% -%% @param Database `#database_state{}' record -%% @param Name Atom naming the relation to remove -%% @returns `{atomic, UpdatedDatabase}' or `{aborted, Reason}' -%% -%% @see retract_relation/3 -%% @see clear_relation/2 -retract_relation(Database, Name) -> - retract_relation(Database, Name, true). - -%% @doc Remove a relation from the database with optional transaction control. -%% -%% First clears all tuples from the relation, then removes the relation entirely -%% from the database's relation map and merkle tree. -%% -%% @param Database `#database_state{}' record -%% @param Name Atom naming the relation to remove -%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction -%% @returns When `Transact =:= true': `{atomic, UpdatedDatabase}' -%% When `Transact =:= false': `UpdatedDatabase' -%% -%% @see create_relation/3 -retract_relation(Database, Name, Transact) -> - RelationHash = maps:get(Name, Database#database_state.relations, {error, retract_relation_could_not_find}), - {DatabaseWithClearedRelation, _ClearedRelation} = clear_relation(Database, RelationHash, false), - NewTree = merklet:delete(atom_to_binary(Name, utf8), DatabaseWithClearedRelation#database_state.tree), - NewHash = case NewTree of - undefined -> <<>>; - {_,H,_,_} -> H - end, - UpdatedDatabase = - DatabaseWithClearedRelation#database_state{relations = maps:remove(Name, DatabaseWithClearedRelation#database_state.relations), - hash = NewHash, - tree = NewTree, - timestamp = erlang:timestamp()}, - TX = fun () -> - mnesia:write(database_state, UpdatedDatabase, write), - UpdatedDatabase - end, - case Transact of - true -> mnesia:transaction(TX); - false -> UpdatedDatabase - end. - -%% @doc Create a new relation in the database with a schema definition. -%% -%% Creates an empty relation (no tuples) with the specified schema. The schema -%% is stored but not yet enforced - it serves as documentation and provides a -%% foundation for future domain validation. -%% -%% <b>Important:</b> The relation's identity is tied to its name. Two relations -%% with identical schemas but different names are semantically distinct and can -%% contain different tuples. -%% -%% == Example == -%% <pre> -%% DB = operations:create_database(my_db), -%% Schema = #{name => string, age => integer, email => string}, -%% {DB1, _Rel} = operations:create_relation(DB, users, Schema). -%% </pre> -%% -%% @param Database `#database_state{}' record -%% @param Name Atom naming the new relation -%% @param Definition Map specifying schema (e.g., `#{name => string, age => integer}') -%% @returns `{UpdatedDatabase, NewRelation}' tuple -%% -%% @see create_database/1 -%% @see create_tuple/3 -%% @see retract_relation/2 -create_relation(Database, Name, Definition) -> - F = fun() -> - %% Create relation with empty tree - %% The meaning of a relation needs to be attached to its name - %% It may sound nominalistic but that is a physical concern. - %% 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, - - %% Build membership criteria from schema (1OPiC declarations) - MembershipCriteria = constraint:build_membership_criteria(Database, Definition), - - NewRelation = #relation{ - hash = RelationHash, - name = Name, - tree = undefined, - schema = Definition, - constraints = constraint:empty_constraints(), % No constraints by default - cardinality = {finite, 0}, % Empty relation - generator = GeneratorFun, % Function generator for finite relations - membership_criteria = MembershipCriteria, % Domain membership from schema - provenance = build_base_provenance(Definition, Name), % Base relation provenance - lineage = {base, Name} % Base relation lineage - }, - mnesia:write(relation, NewRelation, write), - - %% Update database relations map - %% TODO: maybe we can purge this later after including the name on the merkle trees - NewRelations = maps:put(Name, RelationHash, Database#database_state.relations), - - %% Update database tree (for diffing) - %% Note that the name here is important as a key because - %% we gotta go from a name to a hash within a database state - NewTree = merklet:insert({atom_to_binary(Name), RelationHash}, Database#database_state.tree), - {_,NewHash,_,_} = NewTree, - - UpdatedDatabase = #database_state{ - name = Database#database_state.name, - hash = NewHash, - tree = NewTree, - relations = NewRelations, - timestamp = erlang:timestamp() - }, - mnesia:write(database_state, UpdatedDatabase, write), - - {UpdatedDatabase, NewRelation} - end, - {atomic, Result} = mnesia:transaction(F), - Result. - -%% @doc Update a relation's constraints. -%% -%% This function updates the constraints on an existing relation and returns -%% an updated database state with the new relation version. The merklet tree -%% automatically replaces the old relation hash with the new one. -%% -%% == Example == -%% <pre> -%% %% Create constraints -%% AgeConstraint = constraint:create_1op(age, integer, [constraint:gte(18), constraint:lt(70)]), -%% SalaryConstraint = constraint:create_1op(salary, integer, [constraint:between(30000, 200000)]), -%% C1 = constraint:add_attribute_constraint(undefined, age, AgeConstraint), -%% C2 = constraint:add_attribute_constraint(C1, salary, SalaryConstraint), -%% -%% %% Update relation with constraints -%% {DB2, UpdatedRel} = operations:update_relation_constraints(DB1, employees, C2). -%% </pre> -%% -%% @param Database Current database state -%% @param RelationName Name of the relation to update -%% @param Constraints The #relation_constraints{} record to set -%% @returns {UpdatedDatabase, UpdatedRelation} -update_relation_constraints(Database, RelationName, Constraints) - when is_record(Database, database_state), - is_atom(RelationName), - is_record(Constraints, relation_constraints) -> - F = fun() -> - %% Get current relation hash from database state - CurrentRelationHash = maps:get(RelationName, Database#database_state.relations), - - %% Read current relation from mnesia - case mnesia:read(relation, CurrentRelationHash) of - [] -> - %% Relation not found, might be using wrong database version - mnesia:abort({relation_not_found, RelationName, CurrentRelationHash}); - [CurrentRelation] -> - update_relation_with_constraints(CurrentRelation, RelationName, Constraints, Database) - end - end, - {atomic, Result} = mnesia:transaction(F), - Result. - -%% @private -update_relation_with_constraints(CurrentRelation, RelationName, Constraints, Database) -> - %% Create updated relation with new constraints - %% The hash changes because constraints are part of the relation definition - NewRelationHash = hash({CurrentRelation#relation.name, - CurrentRelation#relation.schema, - Constraints}), - - UpdatedRelation = CurrentRelation#relation{ - hash = NewRelationHash, - constraints = Constraints - }, - - %% Write updated relation - mnesia:write(relation, UpdatedRelation, write), - - %% Update database relations map - NewRelations = maps:put(RelationName, NewRelationHash, Database#database_state.relations), - - %% Update database tree (merklet:insert automatically replaces old value) - NewTree = merklet:insert({atom_to_binary(RelationName), NewRelationHash}, - Database#database_state.tree), - {_, NewHash, _, _} = NewTree, - - UpdatedDatabase = #database_state{ - name = Database#database_state.name, - hash = NewHash, - tree = NewTree, - relations = NewRelations, - timestamp = erlang:timestamp() - }, - mnesia:write(database_state, UpdatedDatabase, write), - - {UpdatedDatabase, UpdatedRelation}. - -%% @doc Create a new database state. -%% -%% Initializes an empty database with no relations. The database starts with: -%% <ul> -%% <li>Empty relation map</li> -%% <li>Undefined merkle tree (will be created when first relation is added)</li> -%% <li>Empty hash</li> -%% <li>Timestamp of creation</li> -%% </ul> -%% -%% All changes are committed to Mnesia within a transaction. -%% -%% == Example == -%% <pre> -%% DB = operations:create_database(my_app). -%% </pre> -%% -%% @param Name Atom identifying the database -%% @returns `#database_state{}' record -%% -%% @see setup/0 -%% @see create_relation/3 -create_database(Name) -> - DB = #database_state{ - name = Name, - hash = <<>>, - tree = undefined, - relations = #{}, - timestamp = erlang:timestamp() - }, - %% Standard immutable relations (domains and their predicates) - %% TODO: Since 1OP constraints were added, the constraints passed to the base models now must be supported. - %% The idea is to have the generators be able to produce the constrained subsets - StandardTypeRelations = [ - #domain{ - name = integer, - schema = #{value => integer}, - generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:integer(#{})) end) end, - membership_criteria = #{test => fun(#{value := V}) -> is_integer(V) end}, - cardinality = aleph_zero - }, - #domain{ - name = natural, - schema = #{value => natural}, - generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:natural(#{})) end) end, - membership_criteria = #{test => fun(#{value := V}) -> is_integer(V) andalso V >= 0 end}, - cardinality = aleph_zero - }, - #domain{ - name = rational, - schema = #{numerator => integer, denominator => integer}, - generator = fun() -> spawn(fun() -> generator_iterator_loop(generators:rational(#{})) end) end, - membership_criteria = #{test => fun(#{numerator := N, denominator := D}) -> - is_integer(N) andalso is_integer(D) andalso D /= 0 - end - }, - cardinality = aleph_zero - }, - #domain{ - name = string, - schema = #{value => string}, - generator = undefined, - membership_criteria = #{test => fun(#{value := V}) -> is_list(V) orelse is_binary(V) end}, - cardinality = aleph_zero - }, - #domain{ - name = atom, - schema = #{value => atom}, - generator = undefined, - membership_criteria = #{test => fun(#{value := V}) -> is_atom(V) end}, - cardinality = aleph_zero - }, - #domain{ - name = term, - schema = #{value => term}, - generator = undefined, - membership_criteria = #{test => fun(_) -> true end}, - cardinality = aleph_zero - }, - constraint:less_than(term, aleph_zero), - constraint:less_than_or_equal(term, aleph_zero), - constraint:greater_than(term, aleph_zero), - constraint:greater_than_or_equal(term, aleph_zero), - constraint:equal(term, aleph_zero), - constraint:not_equal(term, aleph_zero), - constraint:plus(integer, aleph_zero), - constraint:times(integer, aleph_zero), - constraint:minus(integer, aleph_zero), - constraint:divide(integer, aleph_zero) - ], - 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, StandardDB, write) - end), - StandardDB. - -%% @doc Create an infinite relation with a generator. -%% -%% Creates a relation with infinite cardinality (aleph_zero or continuum). -%% The relation is defined by a generator function that produces tuples -%% lazily based on constraints. -%% -%% == Primitive Infinite Relations == -%% -%% <ul> -%% <li>`naturals' - Natural numbers: {0, 1, 2, 3, ...}</li> -%% <li>`integers' - Integers: {0, 1, -1, 2, -2, ...}</li> -%% <li>`rationals' - Rationals via Stern-Brocot tree</li> -%% </ul> -%% -%% == Example == -%% <pre> -%% %% Create immutable relation of natural numbers -%% {DB1, Naturals} = operations:create_immutable_relation(DB, #domain{ -%% 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}}). -%% </pre> -%% -%% @param Database `#database_state{}' 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, 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}), - NewRelation = #relation{ - hash = RelationHash, - name = Name, - tree = undefined, % Immutable 'relations' have no merkle tree - schema = Schema, - constraints = constraint:empty_constraints(), % TODO: No constraints unless by domain extension - cardinality = Cardinality, - generator = Generator, - membership_criteria = MembershipCriteria, - provenance = build_base_provenance(Schema, Name), % Base relation provenance - lineage = {base, Name} % Base relation lineage - }, - mnesia:write(relation, NewRelation, write), - NewRelations = maps:put(Name, RelationHash, Database#database_state.relations), - NewTree = merklet:insert({atom_to_binary(Name), RelationHash}, Database#database_state.tree), - {_,NewHash,_,_} = NewTree, - UpdatedDatabase = #database_state{ - name = Database#database_state.name, - hash = NewHash, - tree = NewTree, - relations = NewRelations, - timestamp = erlang:timestamp() - }, - mnesia:write(database_state, UpdatedDatabase, write), - {UpdatedDatabase, NewRelation} - end, - {atomic, Result} = mnesia:transaction(F), - Result; - -create_immutable_relation(Database, Specification) - when is_record(Database, database_state) - andalso is_record(Specification, relation) -> - F = fun() -> - RelationHash = hash({Specification#relation.name, Specification#relation.schema, undefined}), - UpdatedRelation = Specification#relation{hash = RelationHash}, - mnesia:write(relation, UpdatedRelation, write), - NewRelations = maps:put(Specification#relation.name, RelationHash, Database#database_state.relations), - NewTree = merklet:insert({atom_to_binary(Specification#relation.name), RelationHash}, Database#database_state.tree), - {_,NewHash,_,_} = NewTree, - UpdatedDatabase = #database_state{ - name = Database#database_state.name, - hash = NewHash, - tree = NewTree, - relations = NewRelations, - timestamp = erlang:timestamp() - }, - mnesia:write(database_state, UpdatedDatabase, write), - - {UpdatedDatabase, Specification} - end, - {atomic, Result} = mnesia:transaction(F), - Result. - -%% @doc Get relation hash by name. -%% -%% Looks up a relation's hash in the database's relation map. This hash -%% can be used to retrieve the full relation record from Mnesia. -%% -%% @param Database `#database_state{}' record -%% @param RelationName Atom naming the relation -%% @returns `{ok, Hash}' on success, `{error, not_found}' if relation doesn't exist -%% -%% @see get_relations/1 -%% @see hashes_from_tuple/1 -get_relation_hash(Database, RelationName) -> - case maps:find(RelationName, Database#database_state.relations) of - error -> {error, not_found}; - 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: -%% <ol> -%% <li>Reading the tuple record from Mnesia (contains attribute_map)</li> -%% <li>For each attribute, reading the actual value using its hash</li> -%% <li>Building a map with attribute names and materialized values</li> -%% </ol> -%% -%% Uses dirty reads since all data is immutable. -%% -%% @param TupleHash Binary hash identifying the tuple -%% @returns Map with attribute names and actual values (e.g., `#{name => "Alice", age => 30}') -%% -%% @see get_tuples_iterator/2 -%% @see create_tuple/3 -resolve_tuple(TupleHash) -> - [#tuple{attribute_map = AttributeMap}] = mnesia:dirty_read(tuple, TupleHash), - maps:map(fun(_AttrName, ValueHash) -> - [#attribute{value = Value}] = mnesia:dirty_read(attribute, ValueHash), - Value - end, AttributeMap). - -%% @doc Extract all tuple hashes from a relation. -%% -%% Retrieves the list of all tuple hashes stored in the relation's merkle tree. -%% Returns an empty list if the relation has no tuples (tree is `undefined'). -%% -%% Uses dirty reads since the relation data is immutable. -%% -%% @param RelationHash Binary hash identifying the relation -%% @returns List of binary tuple hashes, or empty list `[]' if relation is empty -%% -%% @see get_tuples_iterator/2 -%% @see create_tuple/3 -hashes_from_tuple(RelationHash) -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - case Relation#relation.tree of - undefined -> []; - Tree -> merklet:keys(Tree) - end. - -%% @doc Create an iterator for streaming tuples from a relation with constraints. -%% -%% Extended version of get_tuples_iterator/2 that accepts boundedness constraints. -%% For infinite relations, constraints are mandatory to ensure termination. -%% -%% <b>All tuples include metadata tracking</b> with a nested `meta' field containing: -%% <ul> -%% <li>`provenance' - Tracks immediate source of each attribute</li> -%% <li>`lineage' - Tracks complete operational history</li> -%% </ul> -%% -%% == Options Format == -%% -%% Nested format (preferred): -%% <pre> -%% #{constraints => #{age => {gt, 30}}} -%% </pre> -%% -%% Flat format (backward compatible): -%% <pre> -%% #{age => {gt, 30}} -%% </pre> -%% -%% == Constraints == -%% -%% Constraints bound the iteration over infinite relations: -%% <ul> -%% <li>`{range, Min, Max}' - Range constraint</li> -%% <li>`{eq, Value}' - Equality constraint</li> -%% <li>`{lt, Value}', `{lte, Value}' - Upper bounds</li> -%% <li>`{gt, Value}', `{gte, Value}' - Lower bounds</li> -%% <li>`{in, List}' - Membership constraint</li> -%% </ul> -%% -%% == Example == -%% <pre> -%% %% Iterate employees with age > 30 (metadata always included) -%% Iterator = operations:get_tuples_iterator(DB, employees, -%% #{constraints => #{age => {gt, 30}}}). -%% -%% %% Results will have: -%% %% #{id => 1, name => "Alice", age => 35, -%% %% meta => #{ -%% %% provenance => #{id => {employees, id}, ...}, -%% %% lineage => {select, Fun, {base, employees}} -%% %% }} -%% </pre> -%% -%% @param Database `#database_state{}' record -%% @param RelationName Atom naming the relation to iterate -%% @returns Pid of iterator process -%% -%% @see get_tuples_iterator/2 -%% @see take/3 -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, relation_not_found, RelationName}); - RelationHash -> - [Relation] = mnesia:dirty_read(relation, RelationHash), - case Relation#relation.cardinality of - {finite, _} when Relation#relation.tree =/= undefined -> - TupleHashes = hashes_from_tuple(RelationHash), - spawn(fun() -> tuple_iterator_loop(TupleHashes) end); - _ -> - get_iterator_from_generator(Relation#relation.name, Relation#relation.generator) - end - end. - -%% @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. -%% -%% Sends a `{next, self()}' message to the iterator process and waits for -%% the response. The iterator will materialize the tuple on demand. -%% -%% Timeout is set to 5 seconds to prevent indefinite blocking. -%% -%% @param IteratorPid Pid returned from `get_tuples_iterator/2' -%% @returns `{ok, Tuple}' with materialized tuple map, -%% `done' when no more tuples remain, or -%% `{error, timeout}' if iterator doesn't respond -%% -%% @see get_tuples_iterator/2 -%% @see close_iterator/1 -next_tuple(IteratorPid) -> - IteratorPid ! {next, self()}, - receive - {tuple, Tuple} -> {ok, Tuple}; - done -> done; - {error, Reason} -> {error, Reason} - after 5000 -> - {error, timeout} - end. - -%% @doc Close iterator process. -%% -%% Sends a `stop' message to terminate the iterator process. This should be -%% called when you're done consuming tuples to avoid leaving processes running. -%% -%% @param IteratorPid Pid returned from `get_tuples_iterator/2' -%% @returns `ok' -%% -%% @see get_tuples_iterator/2 -%% @see collect_all/1 -close_iterator(IteratorPid) -> - IteratorPid ! stop, - ok. - -%% @private -%% 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. -%% -%% Protocol: -%% <ul> -%% <li>`{next, Caller}' - Resolve next tuple and send `{tuple, ResolvedTuple}' or `done'</li> -%% <li>`stop' - Terminate the process</li> -%% </ul> -%% -%% @param TupleHashes List of binary tuple hashes to stream -tuple_iterator_loop([]) -> - receive - {next, Caller} -> - Caller ! done; - stop -> - ok - end; -tuple_iterator_loop([TupleHash | Rest]) -> - receive - {next, Caller} -> - %% Resolve tuple on demand - ResolvedTuple = resolve_tuple(TupleHash), - Caller ! {tuple, ResolvedTuple}, - tuple_iterator_loop(Rest); - stop -> - ok - end. - -%% @doc Helper to collect all tuples from an iterator into a list. -%% -%% This is a convenience function primarily used for testing. It exhausts the -%% iterator by repeatedly calling `next_tuple/1' until `done' is received, -%% accumulating all tuples into a list. -%% -%% <b>Warning:</b> This materializes all tuples in memory, defeating the purpose -%% of lazy evaluation. Only use for small relations or testing. -%% -%% == Example == -%% <pre> -%% Iterator = operations:get_tuples_iterator(DB, users), -%% AllTuples = operations:collect_all(Iterator). -%% %% Iterator is automatically closed -%% </pre> -%% -%% @param IteratorPid Pid returned from `get_tuples_iterator/2' -%% @returns List of tuple maps, `{error, Reason, PartialResults}' on timeout -%% -%% @see get_tuples_iterator/2 -%% @see next_tuple/1 -collect_all(IteratorPid) -> - collect_all(IteratorPid, []). - -collect_all(IteratorPid, Acc) -> - case next_tuple(IteratorPid) of - {ok, Tuple} -> collect_all(IteratorPid, [Tuple | Acc]); - done -> - close_iterator(IteratorPid), - lists:reverse(Acc); % Preserve order - {error, Reason} -> - close_iterator(IteratorPid), - {error, Reason, lists:reverse(Acc)} - end. - -%% @doc Select iterator: Filters tuples based on a predicate. -%% -%% Lazy operator that wraps a child iterator and only emits tuples that -%% satisfy the predicate function. -%% -%% == Example == -%% <pre> -%% BaseIter = get_tuples_iterator(DB, employees, #{}), -%% FilteredIter = select_iterator(BaseIter, fun(E) -> maps:get(age, E) > 30 end), -%% Tuples = collect_all(FilteredIter). -%% </pre> -%% -%% @param ChildIterator Iterator process to filter -%% @param Predicate Function: tuple() -> boolean() -%% @returns Iterator process (Pid) -select_iterator(ChildIterator, Predicate) when is_function(Predicate, 1) -> - spawn(fun() -> select_loop(ChildIterator, Predicate) end). - -select_loop(ChildPid, Predicate) -> - receive - {next, Caller} -> - case next_tuple(ChildPid) of - {ok, Tuple} -> - case Predicate(Tuple) of - true -> - Caller ! {tuple, Tuple}, - select_loop(ChildPid, Predicate); - false -> - self() ! {next, Caller}, - select_loop(ChildPid, Predicate) - end; - done -> - close_iterator(ChildPid), - Caller ! done; - {error, Reason} -> - close_iterator(ChildPid), - Caller ! {error, Reason} - end; - stop -> - close_iterator(ChildPid), - ok - end. - -%% @doc Project iterator: Projects tuples onto specified attributes. -%% -%% Lazy operator that transforms tuples by keeping only the specified -%% attributes. This is the relational projection operator (π). -%% -%% == Example == -%% <pre> -%% BaseIter = get_tuples_iterator(DB, employees, #{}), -%% ProjectedIter = project_iterator(BaseIter, [name, age]), -%% Tuples = collect_all(ProjectedIter). -%% </pre> -%% -%% @param ChildIterator Iterator process to project -%% @param Attributes List of attribute names to keep -%% @returns Iterator process (Pid) -project_iterator(ChildIterator, Attributes) when is_list(Attributes) -> - spawn(fun() -> project_loop(ChildIterator, Attributes) end). - -project_loop(ChildPid, Attributes) -> - receive - {next, Caller} -> - case next_tuple(ChildPid) of - {ok, Tuple} -> - % Project data attributes only - no metadata handling - ProjectedTuple = maps:with(Attributes, Tuple), - Caller ! {tuple, ProjectedTuple}, - project_loop(ChildPid, Attributes); - done -> - close_iterator(ChildPid), - Caller ! done; - {error, Reason} -> - close_iterator(ChildPid), - Caller ! {error, Reason} - end; - stop -> - close_iterator(ChildPid), - ok - end. - -%% @doc Sort iterator: Sorts all tuples from child iterator. -%% -%% <b>Blocking operator</b> - must consume ALL tuples from child before -%% emitting any output. Materializes and sorts tuples in memory. -%% -%% <b>Warning:</b> Do not use on unbounded streams! Ensure child iterator -%% produces finite tuples (via constraints or take). -%% -%% == Example == -%% <pre> -%% BaseIter = get_tuples_iterator(DB, employees, #{}), -%% SortedIter = sort_iterator(BaseIter, fun(A, B) -> -%% maps:get(age, A) =< maps:get(age, B) -%% end), -%% Tuples = collect_all(SortedIter). -%% </pre> -%% -%% @param ChildIterator Iterator process to sort -%% @param CompareFun Function: (tuple(), tuple()) -> boolean() -%% @returns Iterator process (Pid) -sort_iterator(ChildIterator, CompareFun) when is_function(CompareFun, 2) -> - spawn(fun() -> - %% Sync all state blocking the pipeline - AllTuples = collect_all(ChildIterator), - %% Sort in memory - SortedTuples = lists:sort(CompareFun, AllTuples), - sorted_emit_loop(SortedTuples) - end). - -sorted_emit_loop([]) -> - receive - {next, Caller} -> Caller ! done; - stop -> ok - end; -sorted_emit_loop([Tuple | Rest]) -> - receive - {next, Caller} -> - Caller ! {tuple, Tuple}, - sorted_emit_loop(Rest); - stop -> ok - end. - -%% @doc Take iterator: Limits output to N tuples. -%% -%% Lazy operator that emits at most N tuples from the child iterator, -%% then closes the child and signals done. -%% -%% == Example == -%% <pre> -%% BaseIter = get_tuples_iterator(DB, naturals, #{value => {range, 0, 1000}}), -%% LimitedIter = take_iterator(BaseIter, 10), -%% Tuples = collect_all(LimitedIter). % Gets exactly 10 tuples -%% </pre> -%% -%% @param ChildIterator Iterator process to limit -%% @param N Maximum number of tuples to emit -%% @returns Iterator process (Pid) -take_iterator(ChildIterator, N) when is_integer(N), N > 0 -> - spawn(fun() -> take_iter_loop(ChildIterator, N, 0, N) end). - -take_iter_loop(ChildPid, Limit, Count, OriginalN) when Count < Limit -> - receive - {next, Caller} -> - case next_tuple(ChildPid) of - {ok, Tuple} -> - %% Pass through tuple without metadata injection - Caller ! {tuple, Tuple}, - take_iter_loop(ChildPid, Limit, Count + 1, OriginalN); - done -> - close_iterator(ChildPid), - Caller ! done; - {error, Reason} -> - close_iterator(ChildPid), - Caller ! {error, Reason} - end; - stop -> - close_iterator(ChildPid), - ok - end; -take_iter_loop(ChildPid, _Limit, _Count, _OriginalN) -> - %% Reached limit - close child and signal done - close_iterator(ChildPid), - receive - {next, Caller} -> Caller ! done; - stop -> ok - end. - -%%% ============================================================================ -%%% Join Operators -%%% ============================================================================ - -%% @doc Equijoin iterator: Natural join on matching attribute values. -%% -%% Performs an equijoin between two relations on a common attribute. -%% For each tuple from the left iterator, finds all matching tuples from -%% the right iterator where the specified attributes are equal. -%% -%% The result tuples merge attributes from both sides. If attribute names -%% conflict, right side attributes are prefixed with "right_". -%% -%% Implementation: Nested loop join (simple but works for small-medium datasets). -%% Future: Hash join for better performance. -%% -%% == Example == -%% <pre> -%% %% 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) -%% </pre> -%% -%% @param LeftIterator Iterator for left relation -%% @param RightIterator Iterator for right relation -%% @param JoinAttribute Attribute name to join on (must exist in both relations) -%% @returns Iterator process that emits joined tuples -equijoin_iterator(LeftIterator, RightIterator, JoinAttribute) -> - spawn(fun() -> equijoin_loop(LeftIterator, RightIterator, JoinAttribute) end). - -%% @doc Theta-join iterator: Join with arbitrary predicate. -%% -%% Performs a theta-join between two relations using a user-provided -%% predicate function. For each pair of tuples (left, right), the predicate -%% is evaluated. If true, the tuples are merged and emitted. -%% -%% == Example == -%% <pre> -%% %% 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) -%% </pre> -%% -%% @param LeftIterator Iterator for left relation -%% @param RightIterator Iterator for right relation -%% @param Predicate Function `fun(LeftTuple, RightTuple) -> boolean()' -%% @returns Iterator process that emits joined tuples -theta_join_iterator(LeftIterator, RightIterator, Predicate) -> - spawn(fun() -> theta_join_loop(LeftIterator, RightIterator, Predicate) end). - -%%% ============================================================================ -%%% Materialization (Eager - Relation Creation) -%%% ============================================================================ - -%% @doc Materialize an iterator pipeline into a new relation. -%% -%% This is the boundary between lazy evaluation (iterator pipeline) and -%% eager materialization (stored relation). Consumes all tuples from the -%% iterator and stores them as a new finite relation in the database. -%% -%% == Example == -%% <pre> -%% %% Build lazy pipeline -%% Pipeline = get_tuples_iterator(DB, employees, #{}) -%% |> select_iterator(fun(E) -> maps:get(age, E) > 30 end) -%% |> sort_iterator(fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end) -%% |> take_iterator(10) -%% |> project_iterator([name, age]), -%% -%% %% Materialize into new relation -%% {DB1, SeniorEmployees} = materialize(DB, Pipeline, senior_employees). -%% </pre> -%% -%% @param Database Current database state -%% @param SourceIterator Iterator process (pipeline endpoint) -%% @param ResultName Atom naming the new relation -%% @returns `{UpdatedDatabase, NewRelation}' tuple -materialize(Database, SourceIterator, ResultName) when is_record(Database, database_state) -> - %% 1. Pull all tuples from pipeline - AllTuples = collect_all(SourceIterator), - - case AllTuples of - [] -> - %% Empty result - create empty relation - Schema = #{}, % Empty schema - create_relation(Database, ResultName, Schema); - - [FirstTuple | _] -> - %% 2. Infer schema from first tuple - Schema = infer_schema_from_tuple(FirstTuple), - - %% 3. Create new relation - {DB1, _Relation} = create_relation(Database, ResultName, Schema), - - %% 4. Insert all tuples - {FinalDB, FinalRelation} = create_all_tuples(DB1, ResultName, AllTuples), - - {FinalDB, FinalRelation} - end. - -%% @private -%% 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 -%% Infer type from value. -infer_type(Value) when is_integer(Value) -> integer; -infer_type(Value) when is_float(Value) -> float; -infer_type(Value) when is_binary(Value) -> binary; -infer_type(Value) when is_list(Value) -> string; -infer_type(Value) when is_atom(Value) -> atom; -infer_type(Value) when is_boolean(Value) -> boolean; -infer_type(_) -> term. - -%% @private -%% Insert multiple tuples into a relation. -create_all_tuples(DB, RelationName, Tuples) -> - lists:foldl( - fun(Tuple, {DBacc, _RelAcc}) -> - create_tuple(DBacc, RelationName, Tuple) - end, - {DB, undefined}, - Tuples - ). - -%%% ============================================================================ -%%% Generator Support Functions -%%% ============================================================================ - - -%% @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) -> - receive - {next, Caller} -> - case Generator(next) of - done -> - Caller ! done; - {value, Tuple, NextGenerator} -> - Caller ! {tuple, Tuple}, - generator_iterator_loop(NextGenerator); - {error, Reason} -> - Caller ! {error, Reason} - end; - stop -> - ok - end. - -%% @private -%% 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 -%% 3. Emit merged tuple when join attribute values match -%% -%% @param LeftIter Left iterator process -%% @param RightIter Right iterator process -%% @param JoinAttr Attribute to join on -equijoin_loop(LeftIter, RightIter, JoinAttr) -> - % Materialize right side (for nested loop) - RightTuples = collect_all(RightIter), - equijoin_emit_loop(LeftIter, RightTuples, JoinAttr). - -equijoin_emit_loop(LeftIter, RightTuples, JoinAttr) -> - receive - {next, Caller} -> - case next_tuple(LeftIter) of - done -> - Caller ! done, - ok; % Stop after sending done - {ok, LeftTuple} -> - % Find all right tuples that match on join attribute - case maps:get(JoinAttr, LeftTuple, undefined) of - undefined -> - % Left tuple doesn't have join attribute - try next - self() ! {next, Caller}, - equijoin_emit_loop(LeftIter, RightTuples, JoinAttr); - LeftValue -> - % Find matching right tuples - Matches = [merge_tuples(LeftTuple, RightTuple) - || RightTuple <- RightTuples, - maps:get(JoinAttr, RightTuple, undefined) =:= LeftValue], - case Matches of - [] -> - % No matches - try next left tuple - self() ! {next, Caller}, - equijoin_emit_loop(LeftIter, RightTuples, JoinAttr); - [FirstMatch | RestMatches] -> - % Emit first match, buffer rest - Caller ! {tuple, FirstMatch}, - equijoin_emit_buffered(LeftIter, RightTuples, JoinAttr, RestMatches) - end - end; - {error, Reason} -> - close_iterator(LeftIter), - Caller ! {error, Reason}, - ok % Stop after sending error - end; - stop -> - close_iterator(LeftIter), - ok - end. - -equijoin_emit_buffered(LeftIter, RightTuples, JoinAttr, [Match | Rest]) -> - receive - {next, Caller} -> - Caller ! {tuple, Match}, - equijoin_emit_buffered(LeftIter, RightTuples, JoinAttr, Rest); - stop -> - close_iterator(LeftIter), - ok - end; -equijoin_emit_buffered(LeftIter, RightTuples, JoinAttr, []) -> - % Buffer empty - continue with next left tuple - equijoin_emit_loop(LeftIter, RightTuples, JoinAttr). - -%% @private -%% 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() -theta_join_loop(LeftIter, RightIter, Pred) -> - % Materialize right side - RightTuples = collect_all(RightIter), - theta_join_emit_loop(LeftIter, RightTuples, Pred). - -theta_join_emit_loop(LeftIter, RightTuples, Pred) -> - receive - {next, Caller} -> - case next_tuple(LeftIter) of - done -> - Caller ! done; - {ok, LeftTuple} -> - % Find all right tuples that satisfy predicate - Matches = [merge_tuples(LeftTuple, RightTuple) - || RightTuple <- RightTuples, - Pred(LeftTuple, RightTuple)], - case Matches of - [] -> - % No matches - continue - self() ! {next, Caller}, - theta_join_emit_loop(LeftIter, RightTuples, Pred); - [FirstMatch | RestMatches] -> - Caller ! {tuple, FirstMatch}, - theta_join_emit_buffered(LeftIter, RightTuples, Pred, RestMatches) - end; - {error, Reason} -> - close_iterator(LeftIter), - Caller ! {error, Reason} - end; - stop -> - close_iterator(LeftIter), - ok - end. - -theta_join_emit_buffered(LeftIter, RightTuples, Pred, [Match | Rest]) -> - receive - {next, Caller} -> - Caller ! {tuple, Match}, - theta_join_emit_buffered(LeftIter, RightTuples, Pred, Rest); - stop -> - close_iterator(LeftIter), - ok - end; -theta_join_emit_buffered(LeftIter, RightTuples, Pred, []) -> - theta_join_emit_loop(LeftIter, RightTuples, Pred). - -%% @private -%% @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 conflict, add right attribute - maps:put(RightKey, RightValue, LeftTupleAcc); - _ -> - % Different attributes - maps:put(RightKey, RightValue, LeftTupleAcc) - end - end, - LeftTuple, - RightTuple - ). - -%% @private -%% 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, - #{}, - Schema - ). - -%% 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. - -%% @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 deleted file mode 100644 index d995f88..0000000 --- a/src/query_planner.erl +++ /dev/null @@ -1,601 +0,0 @@ -%%% @doc Query Planner and Prepared Statement Execution -%%% -%%% Provides a Lisp-inspired tuple-based DSL for constructing and executing -%%% relational algebra queries. Queries are represented as nested Erlang tuples -%%% that can be validated, optimized, and compiled into iterator pipelines. -%%% -%%% == Query DSL Syntax == -%%% -%%% The DSL uses nested tuples to represent relational operations: -%%% <pre> -%%% % Base relation (just use the relation name) -%%% employees -%%% -%%% % Selection (filter) -%%% {select, employees, fun(T) -> maps:get(age, T) > 30 end} -%%% -%%% % Projection -%%% {project, employees, [name, age]} -%%% -%%% % Equijoin (natural join on common attribute) -%%% {join, employees, departments, dept_id} -%%% -%%% % Theta join (join with arbitrary predicate) -%%% {theta_join, -%%% employees, -%%% departments, -%%% fun(L, R) -> maps:get(dept_id, L) =:= maps:get(id, R) end} -%%% -%%% % Sort -%%% {sort, employees, fun(A, B) -> maps:get(age, A) =< maps:get(age, B) end} -%%% -%%% % Take (limit) -%%% {take, employees, 10} -%%% -%%% % Rename attribute -%%% {rename, old_name, new_name, employees} -%%% -%%% % Composite query -%%% {project, -%%% {select, -%%% {join, employees, departments, dept_id}, -%%% fun(T) -> maps:get(age, T) > 30 end}, -%%% [name, dept_name]} -%%% </pre> -%%% -%%% == Usage == -%%% <pre> -%%% % Prepare a query plan -%%% Plan = query_planner:prepare({select, employees, -%%% 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). -%%% </pre> -%%% -%%% @author Nekoma Team -%%% @copyright 2025 - --module(query_planner). - --export([prepare/1, - execute/2, - collect/2, - explain/1]). - --include("operations.hrl"). - -%%% Types - --type query_plan() :: - atom() % Relation name - | {select, query_plan(), fun((map()) -> boolean())} % Filter - | {project, query_plan(), [atom()]} % Projection - | {join, query_plan(), query_plan(), atom()} % Equijoin - | {theta_join, query_plan(), query_plan(), - fun((map(), map()) -> boolean())} % Theta join - | {sort, query_plan(), fun((map(), map()) -> boolean())} % Sort - | {take, query_plan(), pos_integer()} % Limit - | {rename, atom(), atom(), query_plan()} % Rename attribute - | {materialize, query_plan()} % Materialize all - | {materialize, query_plan(), pos_integer()}. % Materialize N tuples - --export_type([query_plan/0]). - -%%% Public API - -%% @doc Prepare and validate a query plan. -%% -%% Takes a query plan tuple and validates its structure. Returns the -%% plan unchanged if valid, or throws an error if invalid. -%% -%% @param Plan The query plan to prepare -%% @returns The validated query plan -%% @throws {invalid_plan, Reason} --spec prepare(query_plan()) -> query_plan(). -prepare(Plan) -> - case validate_plan(Plan) of - ok -> Plan; - {error, Reason} -> error({invalid_plan, Reason}) - end. - -%% @doc Execute a prepared query plan against a database. -%% -%% 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 Ephemeral relation record --spec execute(term(), query_plan()) -> #relation{}. -execute(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. 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. -%% -%% @param DB The database state -%% @param Plan The prepared query plan -%% @returns List of result tuples, or partial results on timeout --spec collect(term(), query_plan()) -> [map()]. -collect(DB, Plan) -> - EphemeralRelation = execute(DB, Plan), - Iter = (EphemeralRelation#relation.generator)(), - Results = operations:collect_all(Iter), - operations:close_iterator(Iter), - case Results of - {error, timeout, PartialResults} -> - io:format("~nWarning: Query timed out. Returning partial results (~b tuples).~n", - [length(PartialResults)]), - io:format("Tip: For infinite relations, use 'take' before operations like 'sort'.~n~n"), - PartialResults; - {error, Reason, PartialResults} -> - io:format("~nWarning: Query failed (~p). Returning partial results (~b tuples).~n~n", - [Reason, length(PartialResults)]), - PartialResults; - _ -> - Results - end. - -%% @doc Explain a query plan in human-readable form. -%% -%% Converts the query plan to a readable string representation -%% showing the operation tree. -%% -%% @param Plan The query plan to explain -%% @returns String representation of the plan --spec explain(query_plan()) -> string(). -explain(Plan) -> - explain_plan(Plan, 0). - -%%% 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(Name) when is_atom(Name) -> - ok; -validate_plan({select, SubPlan, Pred}) when is_function(Pred, 1) -> - validate_plan(SubPlan); -validate_plan({project, SubPlan, Attrs}) when is_list(Attrs) -> - case lists:all(fun is_atom/1, Attrs) of - true -> validate_plan(SubPlan); - false -> {error, {invalid_attributes, Attrs}} - end; -validate_plan({join, Left, Right, Attr}) when is_atom(Attr) -> - case {validate_plan(Left), validate_plan(Right)} of - {ok, ok} -> ok; - {{error, _} = Error, _} -> Error; - {_, {error, _} = Error} -> Error - end; -validate_plan({theta_join, Left, Right, Pred}) when is_function(Pred, 2) -> - case {validate_plan(Left), validate_plan(Right)} of - {ok, ok} -> ok; - {{error, _} = Error, _} -> Error; - {_, {error, _} = Error} -> Error - end; -validate_plan({sort, SubPlan, Comp}) when is_function(Comp, 2) -> - validate_plan(SubPlan); -validate_plan({take, SubPlan, N}) when is_integer(N), N > 0 -> - validate_plan(SubPlan); -validate_plan({rename, OldAttr, NewAttr, SubPlan}) when is_atom(OldAttr), is_atom(NewAttr) -> - validate_plan(SubPlan); -validate_plan({materialize, SubPlan}) -> - validate_plan(SubPlan); -validate_plan({materialize, SubPlan, N}) when is_integer(N), N > 0 -> - validate_plan(SubPlan); -validate_plan(Plan) -> - {error, {unknown_operator, Plan}}. - -%% Compile query plan to iterator pipeline --spec compile_to_iterator(term(), query_plan()) -> pid(). -compile_to_iterator(DB, Name) when is_atom(Name) -> - operations:get_tuples_iterator(DB, Name); - -compile_to_iterator(DB, {select, SubPlan, Predicate}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:select_iterator(SubIter, Predicate); - -compile_to_iterator(DB, {project, SubPlan, Attributes}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:project_iterator(SubIter, Attributes); - -compile_to_iterator(DB, {join, LeftPlan, RightPlan, Attribute}) -> - LeftIter = compile_to_iterator(DB, LeftPlan), - RightIter = compile_to_iterator(DB, RightPlan), - operations:equijoin_iterator(LeftIter, RightIter, Attribute); - -compile_to_iterator(DB, {theta_join, LeftPlan, RightPlan, Predicate}) -> - LeftIter = compile_to_iterator(DB, LeftPlan), - RightIter = compile_to_iterator(DB, RightPlan), - operations:theta_join_iterator(LeftIter, RightIter, Predicate); - -compile_to_iterator(DB, {sort, SubPlan, Comparator}) -> - SubIter = compile_to_iterator(DB, SubPlan), - operations:sort_iterator(SubIter, Comparator); - -compile_to_iterator(DB, {take, SubPlan, N}) -> - %% 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), - %% 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 - SubIter = compile_to_iterator(DB, SubPlan), - Results = operations:collect_all(SubIter), - operations:close_iterator(SubIter), - static_iterator(Results); - -compile_to_iterator(DB, {materialize, SubPlan, Limit}) -> - % Materialize with limit - SubIter = compile_to_iterator(DB, SubPlan), - LimitedIter = operations:take_iterator(SubIter, Limit), - Results = operations:collect_all(LimitedIter), - operations:close_iterator(LimitedIter), - static_iterator(Results). - -%% Static iterator - serves pre-materialized tuples --spec static_iterator([map()]) -> pid(). -static_iterator(Tuples) -> - spawn(fun() -> static_loop(Tuples) end). - -static_loop(Tuples) -> - receive - {next, Caller} -> - case Tuples of - [] -> - Caller ! done, - static_loop([]); - [Tuple | Rest] -> - Caller ! {tuple, Tuple}, - static_loop(Rest) - end; - {close, Caller} -> - Caller ! ok - end. - -%% @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; - {ok, Tuple} -> - RenamedTuple = case maps:is_key(OldAttr, Tuple) of - true -> - Value = maps:get(OldAttr, Tuple), - Tuple1 = maps:remove(OldAttr, Tuple), - maps:put(NewAttr, Value, Tuple1); - false -> - Tuple - end, - Caller ! {tuple, RenamedTuple}, - rename_loop_inline(SourceIter, OldAttr, NewAttr) - end; - {close, Caller} -> - operations:close_iterator(SourceIter), - Caller ! ok - end. - -%% Pretty-print query plan --spec explain_plan(query_plan(), non_neg_integer()) -> string(). -explain_plan(Name, Indent) when is_atom(Name) -> - indent(Indent) ++ "Relation: " ++ atom_to_list(Name) ++ "\n"; - -explain_plan({select, SubPlan, _Pred}, Indent) -> - indent(Indent) ++ "Select (filter)\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({project, SubPlan, Attrs}, Indent) -> - AttrStr = string:join([atom_to_list(A) || A <- Attrs], ", "), - indent(Indent) ++ "Project [" ++ AttrStr ++ "]\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({join, LeftPlan, RightPlan, Attr}, Indent) -> - indent(Indent) ++ "Join on " ++ atom_to_list(Attr) ++ "\n" ++ - explain_plan(LeftPlan, Indent + 2) ++ - explain_plan(RightPlan, Indent + 2); - -explain_plan({theta_join, LeftPlan, RightPlan, _Pred}, Indent) -> - indent(Indent) ++ "Theta Join\n" ++ - explain_plan(LeftPlan, Indent + 2) ++ - explain_plan(RightPlan, Indent + 2); - -explain_plan({sort, SubPlan, _Comp}, Indent) -> - indent(Indent) ++ "Sort\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({take, SubPlan, N}, Indent) -> - indent(Indent) ++ "Take " ++ integer_to_list(N) ++ "\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({rename, OldAttr, NewAttr, SubPlan}, Indent) -> - indent(Indent) ++ "Rename " ++ atom_to_list(OldAttr) ++ " -> " ++ atom_to_list(NewAttr) ++ "\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({materialize, SubPlan}, Indent) -> - indent(Indent) ++ "Materialize (all)\n" ++ - explain_plan(SubPlan, Indent + 2); - -explain_plan({materialize, SubPlan, N}, Indent) -> - indent(Indent) ++ "Materialize (" ++ integer_to_list(N) ++ " tuples)\n" ++ - explain_plan(SubPlan, Indent + 2). - -%% 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 = constraint:empty_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/relation.erl b/src/relation.erl deleted file mode 100644 index 66930d2..0000000 --- a/src/relation.erl +++ /dev/null @@ -1,42 +0,0 @@ --module(relation). --export([new_attribute/2, new_tuple/1, new_relation/1]). - -%% Attribute: A pair of (Name, Value), eg. ("Name", "Augusto") -%% Tuple: A set of attributes, eg. (("Name", "Augusto"), ("Age", 20), ("Surname", "Rengel")) -%% Relation: A set of tuples organized through some selector -%% Example Relation: f(x: Nat) = x + 1 -%% |{(0, 1), (1, 2), (2, 3), ...}| = |N| -%% RelationCustomer = [(Username, Text), (Password, Text)] -%% RelationProduct = [(Name, Text), (Price, Real)] -%% RelationOrder = [(OrderId, Natural), ((Username, Text), -%% (Password, Text), RelationCustomer), ((Name, Text), -%% (Price, Real), RelationProduct)] - -new_attribute(Name, Value) -> - #{name => Name, value => Value}. - -new_tuple(Attributes) when is_list(Attributes) -> - Fun = fun (#{name := Name, value := Value}, Acc) -> - maps:put(Name, Value, Acc) - end, - lists:foldl(Fun, #{}, Attributes). - -new_relation(Tuples) when is_list(Tuples) -> - sets:from_list(Tuples, [{version, 2}]). - -%% SoapName1 = relation:new_attribute(name, "ABC"). -%% SoapPrice1 = relation:new_attribute(price, 1.0). -%% SoapName2 = relation:new_attribute(name, "XYZ"). -%% SoapPrice2 = relation:new_attribute(price, 1.25). -%% BazookaName = relation:new_attribute(name, "Bazzum"). -%% BazookaPrice = relation:new_attribute(price, 413.0). -%% SwordName = relation:new_attribute(name, "Sword"). -%% SwordPrice = relation:new_attribute(price, 100.0). -%% relation:new_relation([relation:new_tuple([SoapName, SoapPrice]), relation:new_tuple([BazookaName, BazookaPrice]), relation:new_tuple([SwordName, SwordPrice])]). - -%% Jules = relation:new_attribute(customer_name, "Jules"). -%% Emily = relation:new_attribute(customer_name, "Emily"). -%% Customers = relation:new_relation([relation:new_tuple([Jules]), -%% relation:new_tuple([Emily])]). - -%% operations:project(operations:select(operations:cartesian_product(relation:new_relation([relation:new_tuple([SoapName1, SoapPrice1]), relation:new_tuple([SoapName2, SoapPrice2]), relation:new_tuple([BazookaName, BazookaPrice]), relation:new_tuple([SwordName, SwordPrice])]), Customers), fun (Tuple) -> maps:get(price, Tuple) =< 1.0 end), [name, customer_name]). diff --git a/src/relational_operators.erl b/src/relational_operators.erl deleted file mode 100644 index 93bdf6d..0000000 --- a/src/relational_operators.erl +++ /dev/null @@ -1,490 +0,0 @@ -%%% @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. -%% -%% Constraints are propagated: source constraints are preserved, and new -%% constraints may be inferred from declarative predicates. -%% -%% Predicate formats: -%% - fun((map()) -> boolean()) - opaque function, no inference -%% - {attr, AttrName, Op, Value} - declarative, infers constraints -%% - {'and', [Pred1, ...]} - conjunction of declarative predicates -%% -%% @param SourceRelation Source #relation{} record -%% @param Predicate Function or declarative term -%% @returns Ephemeral #relation{} with generator and propagated constraints --spec select(#relation{}, fun((map()) -> boolean()) | term()) -> #relation{}. -select(SourceRelation, Predicate) when is_record(SourceRelation, relation) -> - Name = generate_ephemeral_name(), - - %% Build actual filter function from predicate - FilterFun = predicate_to_function(Predicate), - - SourceGen = SourceRelation#relation.generator, - GeneratorFun = fun() -> - SourceIter = SourceGen(), - operations:select_iterator(SourceIter, FilterFun) - end, - - %% Infer constraints from predicate and merge with source constraints - Schema = SourceRelation#relation.schema, - InferredConstraints = constraint:infer_constraints_from_pred(Predicate, Schema), - MergedConstraints = constraint:merge_constraints( - SourceRelation#relation.constraints, - InferredConstraints - ), - - #relation{ - hash = <<>>, - name = Name, - tree = undefined, - schema = Schema, - constraints = MergedConstraints, - 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. -%% -%% Constraints are filtered to only include those for projected attributes. -%% Constraints on attributes that are projected away are dropped. -%% -%% @param SourceRelation Source #relation{} record -%% @param Attributes List of attribute names to keep -%% @returns Ephemeral #relation{} with generator and filtered constraints --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), - - %% Filter constraints to only projected attributes - FilteredConstraints = constraint:filter_constraints( - SourceRelation#relation.constraints, - Attributes - ), - - SourceGen = SourceRelation#relation.generator, - GeneratorFun = fun() -> - SourceIter = SourceGen(), - operations:project_iterator(SourceIter, Attributes) - end, - - #relation{ - hash = <<>>, - name = Name, - tree = undefined, - schema = ProjectedSchema, - constraints = FilteredConstraints, - 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. -%% -%% Constraints from both relations are merged with AND semantics. -%% If both relations have constraints on the same attribute, both are kept. -%% -%% @param LeftRelation Left #relation{} record -%% @param RightRelation Right #relation{} record -%% @param JoinAttribute Attribute name to join on -%% @returns Ephemeral #relation{} with generator and merged constraints --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), - - %% Merge constraints from both relations (AND semantics) - MergedConstraints = constraint:merge_constraints( - LeftRelation#relation.constraints, - RightRelation#relation.constraints - ), - - 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 = MergedConstraints, - 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. -%% -%% Constraints are merged from both relations, and additional constraints may -%% be inferred from declarative predicates. -%% -%% @param LeftRelation Left #relation{} record -%% @param RightRelation Right #relation{} record -%% @param Predicate Function or declarative term -%% @returns Ephemeral #relation{} with generator and merged constraints --spec theta_join(#relation{}, #relation{}, fun((map(), map()) -> boolean()) | term()) -> #relation{}. -theta_join(LeftRelation, RightRelation, Predicate) - when is_record(LeftRelation, relation), - is_record(RightRelation, relation) -> - - 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), - - %% Merge constraints from both relations - MergedConstraints = constraint:merge_constraints( - LeftRelation#relation.constraints, - RightRelation#relation.constraints - ), - - %% Infer additional constraints from predicate - InferredConstraints = constraint:infer_constraints_from_pred(Predicate, MergedSchema), - FinalConstraints = constraint:merge_constraints(MergedConstraints, InferredConstraints), - - %% Build filter function from predicate (for theta join, needs 2-arity) - %% The theta_join_iterator expects a 2-arity function - FilterFun = theta_predicate_to_function(Predicate), - - LeftGen = LeftRelation#relation.generator, - RightGen = RightRelation#relation.generator, - GeneratorFun = fun() -> - LeftIter = LeftGen(), - RightIter = RightGen(), - operations:theta_join_iterator(LeftIter, RightIter, FilterFun) - end, - - #relation{ - hash = <<>>, - name = Name, - tree = undefined, - schema = MergedSchema, - constraints = FinalConstraints, - 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. -%% -%% Constraints are updated: both the map keys and any {var, AttrName} references -%% inside constraint terms are renamed according to the mapping. -%% -%% @param SourceRelation Source #relation{} record -%% @param RenameMappings Map of old_name => new_name (atoms or strings) -%% @returns Ephemeral #relation{} with generator and renamed constraints --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 - ), - - %% Rename constraint attributes (both keys and internal variable references) - RenamedConstraints = constraint:rename_constraint_attrs( - SourceRelation#relation.constraints, - RenameMappings - ), - - SourceGen = SourceRelation#relation.generator, - GeneratorFun = fun() -> - SourceIter = SourceGen(), - rename_iterator(SourceIter, RenameMappings) - end, - - #relation{ - hash = <<>>, - name = Name, - tree = undefined, - schema = RenamedSchema, - constraints = RenamedConstraints, - 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. - -%% @private -%% @doc Convert a predicate (function or declarative term) to a filter function. -%% -%% Supports: -%% - fun((map()) -> boolean()) - returns as-is -%% - {attr, AttrName, Op, Value} - single attribute comparison -%% - {'and', [Pred1, ...]} - conjunction -%% - {'or', [Pred1, ...]} - disjunction -predicate_to_function(Predicate) when is_function(Predicate, 1) -> - Predicate; -predicate_to_function({attr, AttrName, Op, Value}) -> - fun(Tuple) -> - AttrValue = maps:get(AttrName, Tuple, undefined), - apply_comparison(Op, AttrValue, Value) - end; -predicate_to_function({'and', Predicates}) -> - Funs = [predicate_to_function(P) || P <- Predicates], - fun(Tuple) -> - lists:all(fun(F) -> F(Tuple) end, Funs) - end; -predicate_to_function({'or', Predicates}) -> - Funs = [predicate_to_function(P) || P <- Predicates], - fun(Tuple) -> - lists:any(fun(F) -> F(Tuple) end, Funs) - end; -predicate_to_function(_) -> - %% Unknown format - accept all - fun(_) -> true end. - -%% @private -%% @doc Apply a comparison operation. -apply_comparison(lt, A, B) -> A < B; -apply_comparison(lte, A, B) -> A =< B; -apply_comparison(gt, A, B) -> A > B; -apply_comparison(gte, A, B) -> A >= B; -apply_comparison(eq, A, B) -> A =:= B; -apply_comparison(neq, A, B) -> A =/= B; -apply_comparison(between, A, {Min, Max}) -> A >= Min andalso A < Max; -apply_comparison(_, _, _) -> true. - -%% @private -%% @doc Convert a theta predicate to a 2-arity filter function. -%% -%% Theta join predicates operate on merged tuples from both relations. -%% For declarative predicates, we convert to a function that works on -%% the merged tuple (left and right tuples combined). -theta_predicate_to_function(Predicate) when is_function(Predicate, 2) -> - Predicate; -theta_predicate_to_function(Predicate) when is_function(Predicate, 1) -> - %% Convert 1-arity function to 2-arity by merging tuples - fun(LeftTuple, RightTuple) -> - MergedTuple = maps:merge(LeftTuple, RightTuple), - Predicate(MergedTuple) - end; -theta_predicate_to_function(DeclarativePred) -> - %% Convert declarative predicate to 1-arity first, then wrap - OneTupleFun = predicate_to_function(DeclarativePred), - fun(LeftTuple, RightTuple) -> - MergedTuple = maps:merge(LeftTuple, RightTuple), - OneTupleFun(MergedTuple) - end. diff --git a/src/repl.erl b/src/repl.erl deleted file mode 100644 index b26a418..0000000 --- a/src/repl.erl +++ /dev/null @@ -1,326 +0,0 @@ -%%% @doc Interactive REPL Helper for Sakura Query Planner -%%% -%%% Provides convenience functions for working with the query planner -%%% in the Erlang shell (REPL). Includes utilities for pretty-printing -%%% results and working with prepared statements. -%%% -%%% == Quick Start == -%%% <pre> -%%% % Start the system -%%% repl:start(). -%%% -%%% % Create a database with sample data -%%% DB = repl:example_db(). -%%% -%%% % Execute a query -%%% 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]}). -%%% </pre> -%%% -%%% == Query Syntax Examples == -%%% <pre> -%%% % Base relation (just use the name) -%%% employees -%%% -%%% % Filter -%%% {select, employees, fun(T) -> maps:get(age, T) > 30 end} -%%% -%%% % Project -%%% {project, employees, [name, age]} -%%% -%%% % Join -%%% {join, employees, departments, dept_id} -%%% -%%% % Rename -%%% {rename, age, years, employees} -%%% -%%% % Complex pipeline -%%% {take, -%%% {sort, -%%% {project, -%%% {select, -%%% {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}, -%%% 5} -%%% </pre> -%%% -%%% @author Nekoma Team -%%% @copyright 2025 - --module(repl). - --export([start/0, - example_db/0, - q/2, - q/3, - query/2, - show/1, - show/2, - explain/1, - pretty/1, - modes/0, - help/0]). - --include("operations.hrl"). - -%%% Public API - -%% @doc Start the Sakura system and initialize Mnesia. -%% -%% Call this first when starting a new REPL session. -%% -%% @returns ok --spec start() -> ok. -start() -> - main:setup(), - io:format("~n~s~n", [banner()]), - io:format("Sakura REPL started. Type repl:help() for usage.~n~n"), - ok. - -%% @doc Create an example database with sample data. -%% -%% Creates a database with employees and departments relations -%% for testing and experimentation. -%% -%% @returns Database state --spec example_db() -> term(). -example_db() -> - DB = operations:create_database(example_db), - - % Create employees relation - {DB1, _} = operations:create_relation(DB, employees, #{ - id => integer, - name => string, - dept_id => integer, - age => integer, - salary => integer - }), - - {DB2, _} = operations:create_tuple(DB1, employees, #{id => 1, name => "Alice", dept_id => 10, age => 30, salary => 80000}), - {DB3, _} = operations:create_tuple(DB2, employees, #{id => 2, name => "Bob", dept_id => 20, age => 35, salary => 90000}), - {DB4, _} = operations:create_tuple(DB3, employees, #{id => 3, name => "Carol", dept_id => 10, age => 28, salary => 75000}), - {DB5, _} = operations:create_tuple(DB4, employees, #{id => 4, name => "Dave", dept_id => 30, age => 42, salary => 95000}), - {DB6, _} = operations:create_tuple(DB5, employees, #{id => 5, name => "Eve", dept_id => 20, age => 25, salary => 70000}), - - % Create departments relation - {DB7, _} = operations:create_relation(DB6, departments, #{ - dept_id => integer, - dept_name => string, - budget => integer - }), - - {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}), - - %% 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"), - io:format(" - Built-in immutable relations: boolean, natural, integer, rational~n~n"), - - DB10. - -%% @doc Execute a query and pretty-print results (default table mode). -%% -%% Convenience function that prepares, executes, and displays -%% query results in a readable format. Returns `ok' to avoid -%% duplicate output in the Erlang shell. -%% -%% If you need the results for further processing, use `query/2'. -%% -%% @param DB Database state -%% @param Plan Query plan tuple -%% @returns ok --spec q(term(), query_planner:query_plan()) -> ok. -q(DB, Plan) -> - q(DB, Plan, table). - -%% @doc Execute a query with specified visualization mode. -%% -%% Displays query results using the specified visualization mode. -%% Returns `ok' to avoid duplicate output in the Erlang shell. -%% -%% If you need the results for further processing, use `query/2'. -%% -%% @param DB Database state -%% @param Plan Query plan tuple -%% @param Mode Visualization mode (table, tree, nested_table, etc.) -%% @returns ok --spec q(term(), query_planner:query_plan(), visualizer:render_mode()) -> ok. -q(DB, Plan, Mode) -> - PreparedPlan = query_planner:prepare(Plan), - Results = query_planner:collect(DB, PreparedPlan), - visualizer:render(Results, Mode). - -%% @doc Execute a query without printing results. -%% -%% This function executes a query and returns the raw results without -%% any visualization. Use this when you want to work with the results -%% programmatically or decide later how to display them. -%% -%% @param DB Database state -%% @param Plan Query plan tuple -%% @returns List of result tuples -%% -%% == Example == -%% <pre> -%% Results = repl:query(DB, {scan, employees}). -%% FilteredResults = lists:filter(fun(T) -> maps:get(age, T) > 30 end, Results). -%% repl:show(FilteredResults, tree). -%% </pre> --spec query(term(), query_planner:query_plan()) -> [map()]. -query(DB, Plan) -> - PreparedPlan = query_planner:prepare(Plan), - query_planner:collect(DB, PreparedPlan). - -%% @doc Display results using default visualization mode (table). -%% -%% Takes a list of tuples (e.g., from query/2) and displays them -%% using the table visualization mode. -%% -%% @param Results List of result tuples -%% @returns ok --spec show([map()]) -> ok. -show(Results) -> - show(Results, table). - -%% @doc Display results using specified visualization mode. -%% -%% Takes a list of tuples (e.g., from query/2) and displays them -%% using the specified visualization mode. -%% -%% @param Results List of result tuples -%% @param Mode Visualization mode (table, tree, nested_table, etc.) -%% @returns ok -%% -%% == Example == -%% <pre> -%% Results = repl:query(DB, {scan, employees}), -%% repl:show(Results, tree). -%% </pre> --spec show([map()], visualizer:render_mode()) -> ok. -show(Results, Mode) -> - visualizer:render(Results, Mode). - -%% @doc Explain a query plan. -%% -%% Displays the query execution plan in a readable tree format. -%% -%% @param Plan Query plan tuple -%% @returns ok --spec explain(query_planner:query_plan()) -> ok. -explain(Plan) -> - Explanation = query_planner:explain(Plan), - io:format("~nQuery Plan:~n~s~n", [Explanation]), - ok. - -%% @doc List available visualization modes. -%% -%% @returns List of available render modes --spec modes() -> [visualizer:render_mode()]. -modes() -> - visualizer:modes(). - -%% @doc Pretty-print a list of tuples. -%% -%% Displays tuples using the visualizer module (default table mode). -%% -%% @param Results List of result tuples -%% @returns ok --spec pretty([map()]) -> ok. -pretty(Results) -> - visualizer:render(Results, table). - -%% @doc Display help message with query examples. -%% -%% @returns ok --spec help() -> ok. -help() -> - io:format("~n~s~n~n", [banner()]), - io:format("Sakura Query REPL - Lisp-inspired tuple-based query language~n~n"), - 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, employees). %% Run a query~n~n"), - - io:format("Query Operators (all lazy by default):~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"), - io:format(" {theta_join, Left, Right, Predicate} - Theta join~n"), - io:format(" {sort, Plan, Comparator} - Sort tuples~n"), - io:format(" {take, Plan, N} - Limit results~n"), - io:format(" {rename, OldAttr, NewAttr, Plan} - Rename attribute~n"), - io:format(" {materialize, Plan} - Force evaluation (all)~n"), - io:format(" {materialize, Plan, N} - Force evaluation (N tuples)~n~n"), - - io:format("Lazy vs Eager:~n"), - io:format(" All operators return lazy iterators (relations)~n"), - io:format(" Use 'materialize' to force eager evaluation~n"), - io:format(" Materialize can be nested anywhere in the query~n~n"), - - io:format("Query Execution:~n"), - io:format(" repl:q(DB, Plan) - Execute and display (returns ok)~n"), - io:format(" repl:q(DB, Plan, Mode) - Execute and display with mode (returns ok)~n"), - io:format(" repl:query(DB, Plan) - Execute without display (returns results)~n"), - io:format(" repl:show(Results) - Display results (returns ok)~n"), - io:format(" repl:show(Results, Mode) - Display results with mode (returns ok)~n~n"), - - io:format("Visualization Modes:~n"), - io:format(" Modes: table, tree, nested_table, linked_tables, outline~n"), - 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, 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, employees, [name, age]}).~n~n"), - - io:format(" %% Join employees with departments~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, employees}).~n~n"), - - io:format(" %% Materialize first 10 tuples (eager evaluation)~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, 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, 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, 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, employees, ~n"), - io:format(" fun(T) -> maps:get(age, T) > 30 end}).~n~n"), - - ok. - -%%% Internal Functions - -banner() -> - "========================================\n" - " Sakura - Extended Relational DB\n" - " Tasmania / RM/T Implementation\n" - "========================================". diff --git a/src/visualizer.erl b/src/visualizer.erl deleted file mode 100644 index 75f85d1..0000000 --- a/src/visualizer.erl +++ /dev/null @@ -1,348 +0,0 @@ -%%% @doc Relation Visualizer - Multiple Rendering Modes -%%% -%%% Provides various visual representations for nested relational data. -%%% Supports different modes optimized for different use cases. -%%% -%%% == 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 -%%% -%%% == Usage == -%%% <pre> -%%% Results = query_planner:collect(DB, Plan), -%%% visualizer:render(Results, tree). -%%% visualizer:render(Results, nested_table). -%%% </pre> -%%% -%%% @author Nekoma Team -%%% @copyright 2025 - --module(visualizer). - --export([render/1, - render/2, - modes/0]). - --type render_mode() :: table - | nested_table - | tree - | linked_tables - | outline. - --export_type([render_mode/0]). - -%%% Public API - -%% @doc Render tuples with default mode (table). --spec render([map()]) -> ok. -render(Tuples) -> - render(Tuples, table). - -%% @doc Render tuples with specified visualization mode. --spec render([map()], render_mode()) -> ok. -render([], _Mode) -> - io:format("(no results)~n"), - ok; -render(Tuples, table) -> - render_table(Tuples); -render(Tuples, nested_table) -> - render_nested_table(Tuples); -render(Tuples, tree) -> - render_tree(Tuples); -render(Tuples, linked_tables) -> - render_linked_tables(Tuples); -render(Tuples, outline) -> - render_outline(Tuples). - -%% @doc List available rendering modes. --spec modes() -> [render_mode()]. -modes() -> - [table, nested_table, tree, linked_tables, outline]. - -%%% Rendering Implementations - -%% Mode 1: Table with proper column width calculation -render_table(Tuples) -> - AllKeys = get_all_keys(Tuples), - - % Calculate column widths based on content - Widths = calculate_column_widths(Tuples, AllKeys), - - io:format("~n"), - print_separator_with_widths(Widths), - print_row_with_widths([atom_to_list(K) || K <- AllKeys], Widths), - print_separator_with_widths(Widths), - - lists:foreach( - fun(Tuple) -> - Values = [format_value_for_table(maps:get(K, Tuple, undefined)) || K <- AllKeys], - print_row_with_widths(Values, Widths) - end, - Tuples - ), - print_separator_with_widths(Widths), - io:format("~n~b tuple(s)~n~n", [length(Tuples)]), - ok. - -calculate_column_widths(Tuples, Keys) -> - lists:map( - fun(Key) -> - % Start with header width - HeaderWidth = length(atom_to_list(Key)), - - % Find max value width in this column - MaxValueWidth = lists:foldl( - fun(Tuple, MaxW) -> - Value = maps:get(Key, Tuple, undefined), - ValueStr = format_value_for_table(Value), - max(MaxW, length(ValueStr)) - end, - HeaderWidth, - Tuples - ), - - max(12, MaxValueWidth) % Minimum width of 12 - end, - Keys - ). - -format_value_for_table(V) when is_map(V) -> - % Format nested map as inline representation - Keys = [K || K <- maps:keys(V), K =/= meta], - Parts = [atom_to_list(K) ++ ":" ++ format_value(maps:get(K, V)) || K <- Keys], - "[" ++ string:join(Parts, ", ") ++ "]"; -format_value_for_table(V) -> - format_value(V). - -print_separator_with_widths(Widths) -> - io:format("+"), - lists:foreach( - fun(W) -> - io:format("~s+", [lists:duplicate(W + 2, $-)]) - end, - Widths - ), - io:format("~n"). - -print_row_with_widths(Values, Widths) -> - io:format("| "), - lists:foreach( - fun({Val, Width}) -> - io:format("~*s | ", [-Width, Val]) - end, - lists:zip(Values, Widths) - ), - io:format("~n"). - -%% Mode 2: Nested tables (tables within cells) -render_nested_table(Tuples) -> - io:format("~n=== Nested Table View ===~n~n"), - lists:foreach( - fun(Tuple) -> - render_tuple_nested(Tuple, 0) - end, - Tuples - ), - io:format("~n~b tuple(s)~n~n", [length(Tuples)]), - ok. - -render_tuple_nested(Tuple, Indent) -> - Keys = [K || K <- maps:keys(Tuple), K =/= meta], - IndentStr = lists:duplicate(Indent, $\s), - - io:format("~s+-- Tuple~n", [IndentStr]), - lists:foreach( - fun(Key) -> - Value = maps:get(Key, Tuple), - case is_map(Value) andalso (Key =/= meta) of - true -> - % Nested tuple - render as inner table - io:format("~s| ~s:~n", [IndentStr, atom_to_list(Key)]), - io:format("~s| +-------------------------+~n", [IndentStr]), - NestedKeys = maps:keys(Value), - lists:foreach( - fun(NK) -> - NV = format_value(maps:get(NK, Value)), - io:format("~s| | ~-10s : ~-10s |~n", - [IndentStr, atom_to_list(NK), NV]) - end, - NestedKeys - ), - io:format("~s| +-------------------------+~n", [IndentStr]); - false -> - % Simple value - io:format("~s| ~-15s : ~s~n", - [IndentStr, atom_to_list(Key), format_value(Value)]) - end - end, - Keys - ), - io:format("~s+--~n", [IndentStr]). - -%% Mode 3: Tree view with hierarchy -render_tree(Tuples) -> - io:format("~n=== Tree View ===~n~n"), - io:format("+-- Relation (~b tuples)~n", [length(Tuples)]), - render_tuples_as_tree(Tuples, "| ", length(Tuples)), - io:format("~n"), - ok. - -render_tuples_as_tree([], _Prefix, _Total) -> - ok; -render_tuples_as_tree([Tuple], Prefix, Total) -> - io:format("~s~n~s+-- Row ~b~n", [Prefix, Prefix, Total]), - render_tuple_as_tree(Tuple, Prefix ++ " "); -render_tuples_as_tree([Tuple | Rest], Prefix, Total) -> - Index = Total - length(Rest), - io:format("~s~n~s+-- Row ~b~n", [Prefix, Prefix, Index]), - render_tuple_as_tree(Tuple, Prefix ++ "| "), - render_tuples_as_tree(Rest, Prefix, Total). - -render_tuple_as_tree(Tuple, Prefix) -> - Keys = [K || K <- maps:keys(Tuple), K =/= meta], - render_attrs_as_tree(Keys, Tuple, Prefix). - -render_attrs_as_tree([], _Tuple, _Prefix) -> - ok; -render_attrs_as_tree([Key], Tuple, Prefix) -> - Value = maps:get(Key, Tuple), - case is_map(Value) andalso (Key =/= meta) of - true -> - io:format("~s+-- ~s:~n", [Prefix, atom_to_list(Key)]), - render_tuple_as_tree(Value, Prefix ++ " "); - false -> - io:format("~s+-- ~s: ~s~n", - [Prefix, atom_to_list(Key), format_value(Value)]) - end; -render_attrs_as_tree([Key | Rest], Tuple, Prefix) -> - Value = maps:get(Key, Tuple), - case is_map(Value) andalso (Key =/= meta) of - true -> - io:format("~s+-- ~s:~n", [Prefix, atom_to_list(Key)]), - render_tuple_as_tree(Value, Prefix ++ "| "), - render_attrs_as_tree(Rest, Tuple, Prefix); - false -> - io:format("~s+-- ~s: ~s~n", - [Prefix, atom_to_list(Key), format_value(Value)]), - render_attrs_as_tree(Rest, Tuple, Prefix) - end. - -%% Mode 4: Linked tables (parent + separate child tables) -render_linked_tables(Tuples) -> - io:format("~n=== Linked Tables View ===~n~n"), - - % Collect nested relations with parent references - {FlatTuples, NestedRels} = extract_nested_relations_with_refs(Tuples), - - % Render main table - io:format("Main Relation:~n"), - render_table(FlatTuples), - - % Render nested tables with parent references - case NestedRels of - [] -> ok; - _ -> - io:format("~nNested Relations:~n"), - lists:foreach( - fun({RowIdx, AttrName, NestedTuple}) -> - io:format("~n[~s for Row ~b]:~n", [atom_to_list(AttrName), RowIdx]), - render_table([NestedTuple]) - end, - NestedRels - ) - end, - ok. - -extract_nested_relations_with_refs(Tuples) -> - % Process tuples with index tracking - {FlatTuples, NestedRels} = lists:foldl( - fun(Tuple, {FlatAcc, NestedAcc}) -> - RowIdx = length(FlatAcc) + 1, - - % Flatten this tuple - FlatTuple = maps:map( - fun(K, V) when is_map(V), K =/= meta -> - lists:flatten(io_lib:format("[~b]", [RowIdx])); - (_K, V) -> V - end, - Tuple - ), - - % Extract nested relations with parent reference - Nested = lists:filtermap( - fun(K) -> - case maps:get(K, Tuple) of - V when is_map(V), K =/= meta -> - {true, {RowIdx, K, V}}; - _ -> - false - end - end, - maps:keys(Tuple) - ), - - {[FlatTuple | FlatAcc], Nested ++ NestedAcc} - end, - {[], []}, - Tuples - ), - - {lists:reverse(FlatTuples), lists:reverse(NestedRels)}. - -%% Mode 5: Outline format (indented text) -render_outline(Tuples) -> - io:format("~n=== Outline View ===~n~n"), - lists:foreach( - fun(Tuple) -> - render_tuple_outline(Tuple, 0) - end, - Tuples - ), - io:format("~n~b tuple(s)~n~n", [length(Tuples)]), - ok. - -render_tuple_outline(Tuple, Indent) -> - Keys = [K || K <- maps:keys(Tuple), K =/= meta], - IndentStr = lists:duplicate(Indent, $\s), - - io:format("~s+-- Tuple~n", [IndentStr]), - lists:foreach( - fun(Key) -> - Value = maps:get(Key, Tuple), - case is_map(Value) andalso (Key =/= meta) of - true -> - io:format("~s| ~s:~n", [IndentStr, atom_to_list(Key)]), - render_tuple_outline(Value, Indent + 4); - false -> - io:format("~s| ~s: ~s~n", - [IndentStr, atom_to_list(Key), format_value(Value)]) - end - end, - Keys - ), - io:format("~s+--~n", [IndentStr]). - -%%% Helper Functions - -get_all_keys(Tuples) -> - lists:usort( - lists:flatmap( - fun(Tuple) -> - [K || K <- maps:keys(Tuple), K =/= meta] - end, - Tuples - ) - ). - -format_value(undefined) -> "(null)"; -format_value(V) when is_integer(V) -> integer_to_list(V); -format_value(V) when is_float(V) -> float_to_list(V, [{decimals, 2}]); -format_value(V) when is_atom(V) -> atom_to_list(V); -format_value(V) when is_binary(V) -> binary_to_list(V); -format_value(V) when is_list(V) -> V; -format_value(V) when is_map(V) -> "(nested)"; -format_value(_) -> "(complex)". |