diff options
Diffstat (limited to '')
| -rw-r--r-- | docs/features.org | 429 |
1 files changed, 0 insertions, 429 deletions
diff --git a/docs/features.org b/docs/features.org deleted file mode 100644 index 98350c5..0000000 --- a/docs/features.org +++ /dev/null @@ -1,429 +0,0 @@ -#+TITLE: Domino Features & Roadmap - -* Extended Relational Model (RM/T) - :PROPERTIES: - :CATEGORY: semantic-modeling - :END: - An extended relational database engine based on E. F. Codd's RM/T (1979). - Captures more meaning through entity types, surrogates, and molecular semantics. - -** Implemented Features - -*** DONE Content-Addressed Storage - CLOSED: [2025-01-21] - - [X] SHA-256 surrogates for all entities - - [X] System-controlled entity identifiers (E-domain) - - [X] Automatic deduplication via content addressing - - [X] Immutable data structures - -*** DONE Entity Types (E-Relations) - CLOSED: [2025-01-21] - - [X] Kernel entity types (database, relation) - - [X] E-relations for entity existence assertion - - [X] Surrogate-based entity identification - - [X] Entity integrity enforcement - -*** DONE Property Relations (P-Relations) - CLOSED: [2025-01-21] - - [X] Immediate property storage - - [X] Single-valued property support - - [X] Property integrity (Rule 4) - - [X] Foreign key references via surrogates - -*** DONE Merkle Tree Integration - CLOSED: [2025-01-21] - - [X] Relations as Merkle trees - - [X] Database state versioning - - [X] Efficient state diffing - - [X] Content-addressed relation hashing - -*** DONE Volcano Iterator Model - CLOSED: [2025-01-21] - - [X] Lazy tuple evaluation - - [X] Process-based iterators - - [X] Message-passing protocol - - [X] Memory-bounded queries - -*** DONE Transactional Operations - CLOSED: [2025-01-21] - - [X] ACID guarantees via Mnesia - - [X] Atomic tuple insertion - - [X] Tuple retraction with transactions - - [X] Relation clear and retract operations - -*** DONE Comprehensive Test Suite - CLOSED: [2025-01-21] - - [X] Database creation tests - - [X] Relation and tuple operations - - [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 - -*** TODO Characteristic Entities - Multi-valued properties as subordinate entities. - - [ ] Characteristic entity types (C-relations) - - [ ] Characteristic graph (CG-relation) - - [ ] Characteristic tree hierarchy - - [ ] Characteristic integrity (Rule 5) - - [ ] Example: Job history as characteristic of Employee - -*** TODO Associative Entities - Relationships as first-class entities with properties. - - [ ] Associative entity types (A-relations) - - [ ] Association graph (AG-relation) - - [ ] Association integrity (Rule 6) - - [ ] Higher-order associations - - [ ] Example: Assignment(employee, project, start_date) - -*** TODO Generalization Hierarchies - Entity subtyping and inheritance. - - [ ] Unconditional gen inclusion (UGI-relation) - - [ ] Alternative gen inclusion (AGI-relation) - - [ ] Subtype integrity (Rule 7) - - [ ] Property inheritance - - [ ] Multiple inheritance support - - [ ] Example: Engineer/Secretary/Trucker subtypes of Employee - -*** TODO Cover Aggregation - Collections and groupings. - - [ ] Cover membership relation (KG-relation) - - [ ] Cover entity types - - [ ] Dynamic membership - - [ ] Heterogeneous covers - - [ ] Example: Convoys, Teams, Departments - -*** TODO Event Precedence - Temporal ordering and scripts. - - [ ] Event entity types (T-relations) - - [ ] Unconditional successor (US-relation) - - [ ] Alternative successor (AS-relation) - - [ ] Unconditional predecessor (UP-relation) - - [ ] Alternative predecessor (AP-relation) - - [ ] Example: Order → Shipment → Invoice - -*** TODO Extended Operators - Operators for molecular semantics. - - [ ] OUTER NATURAL JOIN - - [ ] OUTER UNION - - [ ] OUTER THETA-JOIN - - [ ] MAYBE operators (null handling) - - [ ] Graph operators (OPEN, CLOSE, STEP) - -*** TODO RM/T Catalog - Extensible schema catalog. - - [ ] CATR (relations catalog) - - [ ] CATRA (relation-attribute) - - [ ] CATA (attributes catalog) - - [ ] CATAD (attribute-domain) - - [ ] CATD (domains catalog) - - [ ] CATC (categories catalog) - - [ ] CATRC (relation-category) - -*** TODO Property Graph (PG-relation) - Link P-relations to E-relations. - - [ ] Property molecule types - - [ ] Dynamic property schema - - [ ] Property graph traversal - -** Classical Relational Algebra - -*** TODO Selection (σ) - Filter tuples by predicate. - - [ ] THETA-SELECT with comparison operators - - [ ] Support for <, ≤, =, ≥, >, ≠ - - [ ] TRUE and MAYBE versions (null handling) - -*** TODO Projection (π) - Project relation onto subset of attributes. - - [ ] Remove specified columns - - [ ] Eliminate duplicate rows - - [ ] Preserve set semantics - -*** TODO Cartesian Product (×) - Cross product of two relations. - - [ ] Unrestricted concatenation - - [ ] Basis for joins - -*** DONE Natural Join (⋈) - CLOSED: [2025-01-22] - Join on common attributes. - - [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. - - [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. - - [ ] Union-compatible constraint - - [ ] Duplicate removal - -*** TODO Intersection (∩) - Set intersection. - - [ ] Union-compatible constraint - -*** TODO Difference (−) - Set difference. - - [ ] Union-compatible constraint - -*** TODO Divide (÷) - Relational division. - - [ ] Algebraic universal quantifier - -*** TODO Rename (ρ) - Attribute renaming. - - [ ] Enable self-joins - -** 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 - - [ ] "Property inapplicable" null type - - [ ] E-null for "entity unknown" - - [ ] Null substitution principle - - [ ] MAYBE operators - -*** TODO Infinite Relations (Aleph₀) - Countably infinite relation generators. - - [ ] Integer generator - - [ ] Arithmetic relations (plus, minus, multiply) - - [ ] Lazy evaluation with constraints - - [ ] Partially materialized storage - - [ ] User-defined generators - -*** TODO View Integration - Merging multiple perspectives. - - [ ] View definition language - - [ ] Automatic view maintenance - - [ ] View update translation - -*** TODO Temporal Support - Time-varying databases. - - [ ] Transaction time - - [ ] Valid time - - [ ] Bitemporal support - - [ ] Non-forgetting mode - -*** TODO Distributed Synchronization - Merkle tree-based replication. - - [ ] Efficient diff protocol - - [ ] Conflict resolution - - [ ] Eventual consistency - -** Developer Experience - -*** TODO Query Language - High-level relational query language. - - [ ] Algebraic syntax - - [ ] Tuple calculus variant - - [ ] Domain calculus variant - -*** TODO REPL Console - Interactive query environment. - - [ ] Live query evaluation - - [ ] Schema introspection - - [ ] Query history - -*** TODO Visualization Tools - Graphical representation. - - [ ] Relation browser - - [ ] Join graph visualization - - [ ] Generalization hierarchy diagrams - - [ ] Query execution plans - -*** TODO Org Babel Integration - Literate programming support. - - [ ] Execute relational queries in org-mode - - [ ] Export results to tables - - [ ] Reproducible analysis - -** Documentation & Validation - -*** DONE Code Documentation - CLOSED: [2025-01-21] - - [X] Module architecture overview - - [X] Data structure specifications - - [X] Usage examples - - [X] Implementation details - -*** TODO Theoretical Validation - Ensure correctness. - - [ ] Formal proofs of operator properties - - [ ] Closure verification - - [ ] Idempotence tests - - [ ] Property-based testing with PropEr - - [ ] Comparison with Date & Darwen semantics - -*** TODO Research Papers - Link to foundational theory. - - [ ] Codd 1970: "A Relational Model" - - [ ] Codd 1979: "Extending the Database Relational Model" (RM/T) - - [ ] Codd 1985: "Does AlOL Need the Relational Algebra?" - - [ ] Date & Darwen: "Foundation for Future Database Systems" - -** References - - E. F. Codd (1979). "Extending the Database Relational Model to Capture More Meaning" - - E. F. Codd (1970). "A Relational Model of Data for Large Shared Data Banks" - - C. J. Date & Hugh Darwen. "Foundation for Future Database Systems: The Third Manifesto" |