diff options
Diffstat (limited to 'docs/features.org')
| -rw-r--r-- | docs/features.org | 172 |
1 files changed, 165 insertions, 7 deletions
diff --git a/docs/features.org b/docs/features.org index 945bfaf..98350c5 100644 --- a/docs/features.org +++ b/docs/features.org @@ -58,6 +58,18 @@ - [X] Hash consistency validation - [X] Iterator protocol tests - [X] Retraction and truncate tests + - [X] Join operation tests + - [X] Provenance tracking tests + +*** DONE Attribute-Level Provenance Tracking + CLOSED: [2025-01-22] + - [X] Nested metadata structure (meta.provenance) + - [X] Track immediate source of each attribute + - [X] Always enabled - every tuple includes metadata + - [X] Automatic provenance merging in joins + - [X] Conflict resolution for duplicate attributes + - [X] Clean separation of data attributes and metadata + - [X] Foundation for tuple-level lineage tracking (implemented) ** Planned RM/T Extensions @@ -146,15 +158,22 @@ - [ ] Unrestricted concatenation - [ ] Basis for joins -*** TODO Natural Join (⋈) +*** DONE Natural Join (⋈) + CLOSED: [2025-01-22] Join on common attributes. - - [ ] Equi-join with duplicate removal - - [ ] Used in normalization - -*** TODO Theta Join (⋈θ) + - [X] Equi-join with duplicate removal (equijoin_iterator) + - [X] Nested loop join strategy + - [X] Attribute conflict resolution (right_ prefix) + - [X] Attribute-level provenance tracking + - [X] Comprehensive test coverage + +*** DONE Theta Join (⋈θ) + CLOSED: [2025-01-22] Join with arbitrary comparison. - - [ ] Support all theta operators - - [ ] Generalizes natural join + - [X] Support all theta operators via predicate functions + - [X] Generalizes natural join + - [X] Nested loop join with custom predicates + - [X] Provenance merging from both sides *** TODO Union (∪) Set union of compatible relations. @@ -179,6 +198,145 @@ ** Advanced Features +*** DONE Tuple-Level Lineage Tracking + CLOSED: [2025-01-23] + Track complete operational history of each tuple through query pipelines. + +**** Status: IMPLEMENTED + +**** API Usage + + Metadata tracking is ALWAYS enabled. All tuples include the 'meta' field: + #+BEGIN_SRC erlang + %% Simple query (metadata automatically included) + Iter = operations:get_tuples_iterator(DB, employees, #{}). + + %% With constraints (metadata still included) + Iter = operations:get_tuples_iterator(DB, employees, + #{constraints => #{age => {gt, 30}}}). + + %% Results always have: + %% #{id => 1, name => "Alice", + %% meta => #{ + %% provenance => #{id => {employees, id}, name => {employees, name}}, + %% lineage => {base, employees} + %% }} + #+END_SRC + +**** Provenance vs. Lineage + + - *Provenance* (IMPLEMENTED): Tracks immediate source of each attribute + #+BEGIN_SRC erlang + meta => #{ + provenance => #{ + name => {employees, name}, + dept_name => {departments, dept_name} + } + } + #+END_SRC + + - *Lineage* (IMPLEMENTED): Tracks complete operation tree that created the tuple + #+BEGIN_SRC erlang + meta => #{ + provenance => #{...}, % Attribute sources + lineage => {project, [name, dept_name], + {join, dept_id, + {select, fun(T) -> maps:get(age, T) > 30 end, + {base, employees}}, + {base, departments}}} + } + #+END_SRC + +**** Type Definition + + #+BEGIN_SRC erlang + -type lineage_op() :: + {base, atom()} % Base relation + | {select, fun(), lineage_op()} % Filter operation + | {project, [atom()], lineage_op()} % Projection + | {join, atom(), lineage_op(), lineage_op()} % Join on attribute + | {theta_join, fun(), lineage_op(), lineage_op()} % Join with predicate + | {sort, fun(), lineage_op()} % Sort operation + | {take, pos_integer(), lineage_op()} % Limit operation + | {aggregate, atom(), atom(), lineage_op()}. % Aggregation (future) + #+END_SRC + +**** Use Cases + + - [ ] *Updatable Views*: Propagate updates back to base relations + - Example: =UPDATE view SET name = "Bob"= → trace lineage → =UPDATE employees SET name = "Bob"= + + - [ ] *Incremental View Maintenance*: Identify affected tuples when base data changes + - Example: If employees tuple changes, lineage identifies which view tuples need recomputation + + - [ ] *Audit Trails*: Track how sensitive data was transformed + - Example: "This salary came from: employees → join(departments) → aggregate(avg)" + + - [ ] *Query Explanation*: Debug complex pipelines + - Example: "Why is this tuple here?" → inspect lineage to see operations applied + + - [ ] *Provenance Queries*: Query the lineage itself + - Example: "Show all tuples derived from employees.id=5" + +**** Implementation Plan + + 1. [X] Extend =tuple_metadata()= type with lineage field + 2. [X] Add lineage construction to each iterator operator + - [X] select_iterator: ={select, Predicate, ChildLineage}= + - [X] project_iterator: ={project, Attributes, ChildLineage}= + - [X] equijoin_iterator: ={join, Attr, LeftLineage, RightLineage}= + - [X] theta_join_iterator: ={theta_join, Pred, LeftLineage, RightLineage}= + - [X] sort_iterator: ={sort, CompareFun, ChildLineage}= + - [X] take_iterator: ={take, N, ChildLineage}= + 3. [X] Implement lineage merging in joins (combine operation trees) + 4. [ ] Add lineage querying API for provenance analysis (future) + 5. [ ] Use lineage for updatable view update propagation (future) + 6. [X] Add comprehensive lineage tests + +**** Relation to Existing Code + + Relation-level provenance already exists in =#relation.provenance=: + #+BEGIN_SRC erlang + -type provenance() :: + {base, atom()} + | {join, provenance(), provenance()} + | {select, provenance(), constraints()} + | {project, provenance(), [atom()]} + | {take, provenance(), pos_integer()}. + #+END_SRC + + This tracks where *relations* come from. Lineage is the *tuple-level* + equivalent, tracking operational history of individual tuples through + query pipelines. + +**** Example: Complete Lineage Chain + + #+BEGIN_SRC erlang + % Query: employees → select(age>30) → join(departments) → project([name, dept_name]) + + % Resulting tuple with full lineage: + #{name => "Alice", + dept_name => "Engineering", + meta => #{ + provenance => #{ + name => {employees, name}, + dept_name => {departments, dept_name} + }, + lineage => { + project, [name, dept_name], + {join, dept_id, + {select, fun(T) -> maps:get(age, T) > 30 end, + {base, employees}}, + {base, departments}}} + }} + + % From this lineage, we can: + % 1. Trace "Alice" back to employees.name + % 2. Know she passed the age>30 filter + % 3. See she was joined with departments on dept_id + % 4. Understand the projection removed other attributes + #+END_SRC + *** TODO Null Value Handling Three-valued logic for incomplete information. - [ ] "Value unknown" null type |