#+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"