path: root/docs/features.org

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