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