diff options
| -rw-r--r-- | .github/workflows/ci.yml | 43 | ||||
| -rw-r--r-- | .github/workflows/docs.yml | 67 | ||||
| -rw-r--r-- | .gitignore | 4 | ||||
| -rw-r--r-- | README.org | 120 | ||||
| -rw-r--r-- | docs/code.org | 272 | ||||
| -rw-r--r-- | docs/features.org | 305 | ||||
| -rw-r--r-- | include/operations.hrl | 4 | ||||
| -rw-r--r-- | rebar.config | 17 | ||||
| -rw-r--r-- | src/operations.erl | 482 | ||||
| -rw-r--r-- | test/operations_test.erl | 353 |
10 files changed, 1540 insertions, 127 deletions
diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml new file mode 100644 index 0000000..b2ec401 --- /dev/null +++ b/.github/workflows/ci.yml @@ -0,0 +1,43 @@ +name: CI + +on: + pull_request: + +jobs: + test: + name: Test on OTP ${{matrix.otp}} / rebar3 ${{matrix.rebar3}} + runs-on: ubuntu-latest + + strategy: + matrix: + otp: ['26', '27'] + rebar3: ['3.23'] + + steps: + - name: Checkout code + uses: actions/checkout@v4 + + - name: Setup Erlang/OTP + uses: erlef/setup-beam@v1 + with: + otp-version: ${{matrix.otp}} + rebar3-version: ${{matrix.rebar3}} + + - name: Restore dependencies cache + uses: actions/cache@v4 + with: + path: | + _build + rebar.lock + key: ${{ runner.os }}-rebar3-${{ hashFiles('rebar.config') }} + restore-keys: | + ${{ runner.os }}-rebar3- + + - name: Compile + run: rebar3 compile + + - name: Run tests + run: rebar3 eunit + + - name: Run dialyzer + run: rebar3 dialyzer diff --git a/.github/workflows/docs.yml b/.github/workflows/docs.yml new file mode 100644 index 0000000..e659d8e --- /dev/null +++ b/.github/workflows/docs.yml @@ -0,0 +1,67 @@ +name: Documentation + +on: + push: + branches: + - master + +permissions: + contents: read + pages: write + id-token: write + +concurrency: + group: "pages" + cancel-in-progress: false + +jobs: + build: + name: Build documentation + runs-on: ubuntu-latest + + steps: + - name: Checkout code + uses: actions/checkout@v4 + + - name: Setup Erlang/OTP + uses: erlef/setup-beam@v1 + with: + otp-version: '27' + rebar3-version: '3.23' + + - name: Restore dependencies cache + uses: actions/cache@v4 + with: + path: | + _build + rebar.lock + key: ${{ runner.os }}-rebar3-${{ hashFiles('rebar.config') }} + restore-keys: | + ${{ runner.os }}-rebar3- + + - name: Compile + run: rebar3 compile + + - name: Generate EDoc + run: rebar3 edoc + + - name: Setup Pages + uses: actions/configure-pages@v4 + + - name: Upload artifact + uses: actions/upload-pages-artifact@v3 + with: + path: 'doc' + + deploy: + name: Deploy to GitHub Pages + environment: + name: github-pages + url: ${{ steps.deployment.outputs.page_url }} + runs-on: ubuntu-latest + needs: build + + steps: + - name: Deploy to GitHub Pages + id: deployment + uses: actions/deploy-pages@v4 @@ -1,2 +1,6 @@ _build Mnesia.* + +# EDoc generated files +doc/ +!doc/overview.edoc @@ -2,9 +2,21 @@ * About -Domino is a **Relational Algebra Engine** implements relational -algebra in its strict, theoretical form, adhering rigorously to the -principles of relational theory as articulated by E. F. Codd. +Domino is an *Extended Relational Database Engine* based on E. F. Codd's +RM/T (Relational Model/Tasmania, 1979). It implements relational algebra +in its strict, theoretical form while extending it to capture more of the +meaning of data through semantic modeling concepts. + +** Theoretical Foundation + +The engine builds upon two seminal works by E. F. Codd: + +1. *"A Relational Model of Data for Large Shared Data Banks"* (1970) — + The foundation of relational theory +2. *"Extending the Database Relational Model to Capture More Meaning"* (1979) — + RM/T extensions for semantic modeling + +** Core Principles A relation is modeled as a set of tuples, each tuple being a set of attributes. Each attribute is a pairing of a name with a value drawn @@ -12,9 +24,99 @@ from a domain. All operations are defined on entire relations as sets, with no recourse to the compromises typical of SQL or other practical implementations. -The engine is intended as a study in correctness: each operation, from -projection to join, is executed in a manner consistent with the -classical definition of relational algebra. It is a platform for -exploring the consequences of relational theory in a low-level -programming context, providing both a tool for experimentation and a -concrete realization of the abstract model. +** What Makes Domino Extended? + +*** Content-Addressed Storage +Entities are identified by system-controlled *surrogates* — cryptographic +hashes (SHA-256) that provide permanent, unique identification. This +enables: +- Automatic deduplication +- Immutable versioning +- Merkle tree-based diffing +- Distributed synchronization + +*** Entity Types (RM/T) +Three fundamental entity classifications: +- *Kernel Entities* — Independent entities (e.g., Employee, Supplier) +- *Characteristic Entities* — Multi-valued properties (e.g., Job History) +- *Associative Entities* — Relationships as first-class entities + +*** Four Dimensions of Molecular Semantics +1. *Cartesian Aggregation* — Properties, characteristics, and associations +2. *Generalization* — Subtyping and inheritance hierarchies +3. *Cover Aggregation* — Collections and groupings (e.g., teams, convoys) +4. *Event Precedence* — Temporal ordering of events + +*** Immutable Architecture +All data structures are immutable. Every modification creates a new version +with a new hash, enabling: +- Temporal queries +- Audit trails +- Safe concurrent access +- Version control for data + +** Current Implementation + +*** What's Built +- Content-addressed storage with SHA-256 surrogates +- E-relations for entity type management +- P-relations for immediate properties +- Merkle tree integration for efficient versioning +- Volcano iterator model for lazy evaluation +- Transactional ACID operations via Mnesia +- Comprehensive EUnit test suite + +*** What's Planned +- Full relational algebra operators (σ, π, ⋈, ∪, ∩, −) +- Characteristic entities and CG-relation +- Associative entities and AG-relation +- Generalization hierarchies (UGI/AGI) +- Cover aggregation (KG-relation) +- Event precedence (US/AS/UP/AP) +- Extended operators (OUTER JOIN, MAYBE operators) +- RM/T catalog relations +- Null value handling (three-valued logic) +- Infinite relations (aleph₀) +- High-level query language + +** Design Philosophy + +The engine is intended as a study in correctness and semantic richness: +each operation is executed in a manner consistent with the classical +definition of relational algebra, while the RM/T extensions provide a +framework for capturing more meaning about entities, their properties, +and their relationships. + +It is a platform for exploring the consequences of relational theory in +a low-level programming context, providing both a tool for experimentation +and a concrete realization of Codd's vision for semantic data modeling. + +** Why RM/T? + +Most database systems today are compromises — they sacrifice theoretical +purity for practical performance. Domino takes a different approach: +implement the theory *correctly* first, then optimize. RM/T provides: + +- *Atomic Semantics* — What constitutes a minimal meaningful unit? +- *Molecular Semantics* — What larger clusters constitute meaningful units? +- *Systematic Design* — Principled approach to database schema design +- *Intelligent Behavior* — System understands more about data meaning + +** Documentation + +See =docs/= directory: +- =code.org= — Comprehensive code documentation +- =features.org= — Feature roadmap and RM/T extensions +- =ci.org= — Continuous integration setup + +** References + +- Codd, E. F. (1970). "A Relational Model of Data for Large Shared Data Banks." + /Communications of the ACM/ 13(6): 377-387. +- Codd, E. F. (1979). "Extending the Database Relational Model to Capture More Meaning." + /ACM Transactions on Database Systems/ 4(4): 397-434. +- Date, C. J. & Darwen, H. "Foundation for Future Database Systems: The Third Manifesto." + +** License + +See LICENSE file. diff --git a/docs/code.org b/docs/code.org new file mode 100644 index 0000000..30ff9c9 --- /dev/null +++ b/docs/code.org @@ -0,0 +1,272 @@ +#+TITLE: Code Documentation + +* Overview + +Domino is a content-addressed, immutable relational database engine written in Erlang. The system uses cryptographic hashing (SHA-256) and Merkle trees to provide version control, deduplication, and efficient synchronization capabilities. + +* Architecture + +** Design Patterns + +- *Content-Addressed Storage* :: All data (attributes, tuples, relations, databases) are identified by their cryptographic hash +- *Immutable Data Structures* :: All operations create new versions rather than modifying existing data +- *Merkle Trees* :: Relations and databases use merkle trees for efficient diffing and synchronization +- *Volcano Iterator Model* :: Query execution uses lazy evaluation with process-based iterators +- *Actor Model* :: Iterators are implemented as independent Erlang processes +- *Transactional Storage* :: Mnesia provides ACID guarantees for all mutations + +* Module Structure + +** operations.erl + +The core database operations module and main API. + +*** Public API + +**** Database & Relation Management +- =setup/0= :: Initialize Mnesia schema and create all tables +- =create_database/1= :: Create a new database state +- =create_relation/3= :: Add a relation to a database with schema +- =get_relations/1= :: List all relation names in a database +- =get_relation_hash/2= :: Get relation hash by name + +**** Tuple Operations +- =create_tuple/3= :: Insert a tuple into a relation (transactional) +- =retract_tuple/3= :: Remove a tuple from a relation (default: transactional) +- =retract_tuple/4= :: Remove a tuple with optional transaction control + +**** Relation Operations +- =clear_relation/2= :: Remove all tuples from a relation (default: transactional) +- =clear_relation/3= :: Clear relation with optional transaction control +- =retract_relation/2= :: Remove a relation from database (default: transactional) +- =retract_relation/3= :: Remove relation with optional transaction control + +**** Iterator Pattern (Volcano Model) +- =get_tuples_iterator/2= :: Create lazy iterator process for relation tuples +- =next_tuple/1= :: Pull next tuple from iterator (returns ={ok, Tuple} | done=) +- =close_iterator/1= :: Terminate iterator process +- =collect_all/1= :: Helper to consume entire iterator into list + +**** Utility Functions +- =hash/1= :: SHA-256 hash of term +- =hashes_from_tuple/1= :: Extract all tuple hashes from a relation + +** relation.erl + +Simple helper module for building tuples and relations conceptually. + +*** Public API +- =new_attribute/2= :: Create attribute map: =#{name => Name, value => Value}= +- =new_tuple/1= :: Convert list of attributes to map +- =new_relation/1= :: Convert list of tuples to sets:set + +** poc.erl + +Proof-of-concept demonstrating the Volcano Iterator Model for query execution. + +*** Key Concepts +- Content-addressed storage simulation using in-memory maps +- Lazy iterator chain: Scan → Select → Project +- Message-passing protocol for tuple streaming +- Automatic deduplication via hashing + +** main.erl + +OTP application entry point. Starts Mnesia on application startup. + +* Data Structures + +All core records are defined in =include/operations.hrl=. + +** attribute +#+BEGIN_SRC erlang +-record(attribute, { + hash, % SHA-256 hash of value + value % Actual value (any Erlang term) +}). +#+END_SRC + +** tuple +#+BEGIN_SRC erlang +-record(tuple, { + hash, % SHA-256 hash of entire tuple + relation, % Relation name (atom) + attribute_map % #{attr_name => value_hash} +}). +#+END_SRC + +** relation +#+BEGIN_SRC erlang +-record(relation, { + hash, % hash({name, schema, tree_root}) + name, % Relation name (atom) + tree, % Merkle tree of tuple hashes + schema % Schema definition map +}). +#+END_SRC + +** database_state +#+BEGIN_SRC erlang +-record(database_state, { + hash, % Merkle tree root hash + name, % Database name (atom) + tree, % Merkle tree of relations + relations, % #{relation_name => relation_hash} + timestamp % Creation/modification timestamp +}). +#+END_SRC + +* Data Flow + +** Creating a Tuple + +1. Store each attribute value separately (enables deduplication) +2. Build attribute_map with hashes: =#{name => AttrHash1, age => AttrHash2}= +3. Create tuple record with hash +4. Insert tuple hash into relation's merkle tree +5. Compute new relation hash from tree root +6. Update database merkle tree +7. Return updated database and relation + +All operations occur within a Mnesia transaction. + +** Querying Tuples + +1. Lookup relation hash from database +2. Read relation from Mnesia +3. Extract tuple hashes from merkle tree +4. Spawn iterator process with hash list +5. Client pulls tuples via message passing +6. Iterator resolves: hash → tuple → attribute hashes → actual values +7. Return materialized tuple map + +* Usage Examples + +** Basic Workflow + +#+BEGIN_SRC erlang +%% Setup +operations:setup(). + +%% Create database +DB = operations:create_database(my_app). + +%% Create relation with schema +{DB1, _Rel} = operations:create_relation(DB, users, #{ + name => string, + age => integer +}). + +%% Insert tuples +{DB2, _} = operations:create_tuple(DB1, users, #{name => "Alice", age => 30}). +{DB3, _} = operations:create_tuple(DB2, users, #{name => "Bob", age => 25}). + +%% Query tuples +Iterator = operations:get_tuples_iterator(DB3, users). +Tuples = operations:collect_all(Iterator). +%% Returns: [#{name => "Alice", age => 30}, #{name => "Bob", age => 25}] + +%% Remove tuple +{ok, RelHash} = operations:get_relation_hash(DB3, users). +[TupleHash|_] = operations:hashes_from_tuple(RelHash). +{atomic, {DB4, _}} = operations:retract_tuple(DB3, RelHash, TupleHash). + +%% Clear relation (remove all tuples, keep schema) +{atomic, {DB5, _}} = operations:clear_relation(DB4, RelHash). + +%% Remove relation entirely +{atomic, DB6} = operations:retract_relation(DB5, users). +#+END_SRC + +** Iterator Protocol + +#+BEGIN_SRC erlang +Iterator = operations:get_tuples_iterator(DB, users). + +%% Pull tuples one by one +case operations:next_tuple(Iterator) of + {ok, Tuple} -> process_tuple(Tuple); + done -> io:format("No more tuples~n") +end. + +%% Or collect all at once +AllTuples = operations:collect_all(Iterator). + +%% Clean up +operations:close_iterator(Iterator). +#+END_SRC + +* Key Implementation Details + +** Immutability & Versioning + +Every modification creates a new hash. Old versions remain accessible via their hash. Database evolution is tracked via timestamp and hash chain. + +** Deduplication + +Identical attribute values are stored once (content-addressed). Example: 1000 users with age=30 store the value "30" only once. + +** Transaction Semantics + +All mutations are wrapped in =mnesia:transaction/1=. Dirty reads are used for immutable data lookups. + +** Merkle Tree Strategy + +- Relations store tuple hashes as keys: ={TupleHash, <<>>}= +- Databases store relation names → hashes: ={RelationName, RelationHash}= +- Enables efficient diff computation between versions +- Foundation for distributed synchronization + +** Iterator Pattern + +- Decouples query execution from data access +- Enables pipelined query operators (future: select, project, join) +- Memory bounded (doesn't materialize entire relation) +- Process-based concurrency via Erlang actors + +** Schema Flexibility + +Schema stored as map (e.g., =#{name => string, age => integer}=). Currently not enforced, but provides foundation for future domain validation. + +* Dependencies + +- =merklet= (2.0.0) :: Merkle tree implementation for set reconciliation +- =mnesia= :: Distributed database for persistent storage +- =crypto= :: SHA-256 hashing + +* Testing + +The test suite (=test/operations_test.erl=) validates: + +- Functional correctness (CRUD operations) +- Hash determinism and consistency +- Transactional integrity +- Iterator protocol compliance +- State evolution tracking +- Cross-database consistency + +Run tests with: + +#+BEGIN_SRC sh +rebar3 eunit +#+END_SRC + +* Current State + +** Implemented +- Core data model (attribute, tuple, relation, database) +- Content-addressed storage with SHA-256 +- Immutable versioning +- Merkle tree integration +- Iterator-based lazy evaluation +- Transactional CRUD operations +- Comprehensive test suite + +** Not Yet Implemented +- Relational algebra operators (σ, π, ⋈, ∪, ∩, −) +- Schema validation and type checking +- Infinite relations (aleph₀) +- Join indexing +- Query optimization +- Distributed synchronization +- REPL/query console diff --git a/docs/features.org b/docs/features.org index a6e592e..945bfaf 100644 --- a/docs/features.org +++ b/docs/features.org @@ -1,96 +1,271 @@ -* Relational Algebra Engine +#+TITLE: Domino Features & Roadmap + +* Extended Relational Model (RM/T) :PROPERTIES: - :CATEGORY: relational-algebra + :CATEGORY: semantic-modeling :END: - A pure Erlang implementation of E. F. Codd’s relational algebra. - Relations are treated as mathematical sets of tuples; operations are defined exactly - as in relational theory, with optional aleph₀ (infinite) relations. + 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 + +** 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 -** Core Specification - The theoretical backbone of the system. +*** TODO Cover Aggregation + Collections and groupings. + - [ ] Cover membership relation (KG-relation) + - [ ] Cover entity types + - [ ] Dynamic membership + - [ ] Heterogeneous covers + - [ ] Example: Convoys, Teams, Departments -*** TODO Define relation as a strict mathematical set - - [ ] Each tuple is a set of attributes (no duplicates, no ordering) - - [ ] Each attribute = (name, value) pair - - [ ] Attribute domains are strongly typed +*** 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 Enforce "Codd's axioms" in implementation - - [ ] No duplicate tuples in any relation - - [ ] No implicit ordering of tuples or attributes - - [ ] All operations closed over the relation type - - [ ] Proper domain checking in all operations +*** TODO Extended Operators + Operators for molecular semantics. + - [ ] OUTER NATURAL JOIN + - [ ] OUTER UNION + - [ ] OUTER THETA-JOIN + - [ ] MAYBE operators (null handling) + - [ ] Graph operators (OPEN, CLOSE, STEP) -** Data Model Layer (`relation.erl`) - Fundamental constructs of the relational model. +*** 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 Implement attributes, tuples, relations, and schemas -*** TODO Add schema validation for domain and arity -*** TODO Add conversion helpers: - - [ ] tuple <-> map - - [ ] schema validation checks +*** TODO Property Graph (PG-relation) + Link P-relations to E-relations. + - [ ] Property molecule types + - [ ] Dynamic property schema + - [ ] Property graph traversal -** Algebraic Operations (`operations.erl`) - The complete set of classical relational algebra operators. +** 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 + *** TODO Natural Join (⋈) + Join on common attributes. + - [ ] Equi-join with duplicate removal + - [ ] Used in normalization + *** TODO Theta Join (⋈θ) + Join with arbitrary comparison. + - [ ] Support all theta operators + - [ ] Generalizes natural join + *** 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 (ρ) -*** TODO Set semantics enforcement (remove duplicates after each op) + Attribute renaming. + - [ ] Enable self-joins + +** Advanced Features + +*** 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 -** Infinite Relations (`aleph0.erl`) - Representation of aleph₀-relations (countably infinite generators). +*** TODO View Integration + Merging multiple perspectives. + - [ ] View definition language + - [ ] Automatic view maintenance + - [ ] View update translation -*** TODO Implement integer() generator -*** TODO Implement plus(), minus(), multiply(), neg() relations -*** TODO Add constraints and modes for partially bound arguments -*** TODO Implement lazy generation using streams or coroutines -*** TODO Support user-defined infinite relations +*** TODO Temporal Support + Time-varying databases. + - [ ] Transaction time + - [ ] Valid time + - [ ] Bitemporal support + - [ ] Non-forgetting mode -** Unified Relation Abstraction (`unified_relation.erl`) - A bridge between finite and infinite relations. +*** TODO Distributed Synchronization + Merkle tree-based replication. + - [ ] Efficient diff protocol + - [ ] Conflict resolution + - [ ] Eventual consistency -*** TODO Implement unified type for finite and aleph₀ -*** TODO Implement unified select, project, join, union, etc. -*** TODO Support type checking between finite and infinite relations -*** TODO Add automatic materialization with configurable limits -*** TODO Implement caching/memoization for aleph₀ evaluations +** Developer Experience -** Backend Integration (Mnesia) - Persistent storage and retrieval of finite relations. +*** TODO Query Language + High-level relational query language. + - [ ] Algebraic syntax + - [ ] Tuple calculus variant + - [ ] Domain calculus variant -*** TODO Map finite relations to Mnesia tables -*** TODO Support schema registration and domain enforcement -*** TODO Add persistence for partially materialized aleph₀ relations -*** TODO Add atomic transactional updates -*** TODO Add indexing support for joins +*** TODO REPL Console + Interactive query environment. + - [ ] Live query evaluation + - [ ] Schema introspection + - [ ] Query history -** Correctness and Validation - Ensuring theoretical fidelity. +*** TODO Visualization Tools + Graphical representation. + - [ ] Relation browser + - [ ] Join graph visualization + - [ ] Generalization hierarchy diagrams + - [ ] Query execution plans -*** TODO Implement relational algebra test suite -*** TODO Verify closure and idempotence of all operations -*** TODO Add property-based tests with PropEr or QuickCheck -*** TODO Compare semantics with formal definitions (e.g., Date & Darwen) +*** TODO Org Babel Integration + Literate programming support. + - [ ] Execute relational queries in org-mode + - [ ] Export results to tables + - [ ] Reproducible analysis -** Developer Tools - Optional but desirable tools for exploration and testing. +** Documentation & Validation -*** TODO Add REPL-like console for interactive relational queries -*** TODO Add pretty-printer for relations and schemas -*** TODO Add visualization of join graphs and operation pipelines -*** TODO Add Org Babel integration for relational queries +*** DONE Code Documentation + CLOSED: [2025-01-21] + - [X] Module architecture overview + - [X] Data structure specifications + - [X] Usage examples + - [X] Implementation details -** Documentation - Literate and theoretical exposition. +*** 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 Write README with theoretical introduction -*** TODO Add module-level comments summarizing relational definitions -*** TODO Include examples of finite and aleph₀ joins -*** TODO Provide link to E. F. Codd’s original papers +*** 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" diff --git a/include/operations.hrl b/include/operations.hrl new file mode 100644 index 0000000..fcd2d83 --- /dev/null +++ b/include/operations.hrl @@ -0,0 +1,4 @@ +-record(database_state, {hash, name, tree, relations, timestamp}). +-record(relation, {hash, name, tree, schema}). +-record(tuple, {hash, relation, attribute_map}). +-record(attribute, {hash, value}). diff --git a/rebar.config b/rebar.config index 7efc3fd..e994dbf 100644 --- a/rebar.config +++ b/rebar.config @@ -3,4 +3,21 @@ {shell, [ {apps, [main]} +]}. + +{dialyzer, [ + {plt_extra_apps, [merklet]}, + {warnings, [unknown]} +]}. + +{edoc_opts, [ + {doclet, edoc_doclet}, + {source_path, ["src"]}, + {app_default, "https://www.erlang.org/doc/man"}, + {preprocess, true}, + {includes, ["include"]}, + {dir, "doc"}, + {overview, "doc/overview.edoc"}, + {title, "Domino - Extended Relational Database Engine"}, + {pretty_printer, erl_pp} ]}.
\ No newline at end of file diff --git a/src/operations.erl b/src/operations.erl index 24256d1..1dd152b 100644 --- a/src/operations.erl +++ b/src/operations.erl @@ -1,17 +1,77 @@ +%%% @doc Extended Relational Database Operations (RM/T) +%%% +%%% This module implements core database operations for Domino, an extended +%%% relational database engine based on E. F. Codd's RM/T (1979). +%%% +%%% == Architecture == +%%% +%%% The system uses: +%%% <ul> +%%% <li><b>Content-Addressed Storage</b> - All entities identified by SHA-256 hashes</li> +%%% <li><b>Immutable Data Structures</b> - Operations create new versions</li> +%%% <li><b>Merkle Trees</b> - Efficient versioning and diffing via merklet</li> +%%% <li><b>Mnesia Backend</b> - ACID transactions and persistent storage</li> +%%% <li><b>Volcano Iterator Model</b> - Lazy evaluation with process-based iterators</li> +%%% </ul> +%%% +%%% == Data Model == +%%% +%%% The system maintains four tables in Mnesia: +%%% <ul> +%%% <li>`attribute' - Stores atomic values with their hashes</li> +%%% <li>`tuple' - Stores tuples as maps from attribute names to value hashes</li> +%%% <li>`relation' - Stores relations with merkle trees of tuple hashes</li> +%%% <li>`database_state' - Stores database snapshots with relation merkle trees</li> +%%% </ul> +%%% +%%% == RM/T Integrity Rules == +%%% +%%% <ul> +%%% <li><b>Rule 3 (Entity Integrity)</b> - E-relations accept insertions/deletions, not updates</li> +%%% <li><b>Rule 4 (Property Integrity)</b> - Tuples require entity existence in E-relation</li> +%%% </ul> +%%% +%%% @author Nekoma Team +%%% @copyright 2025 +%%% @version 0.1.0 +%%% @reference E. F. Codd (1979). "Extending the Database Relational Model to Capture More Meaning" +%%% @reference E. F. Codd (1970). "A Relational Model of Data for Large Shared Data Banks" + -module(operations). --export([setup/0, - hash/1, +-include("operations.hrl"). +-export([setup/0, + hash/1, create_database/1, - create_relation/3, - create_tuple/3, - get_relations/1, + create_relation/3, + create_tuple/3, + retract_tuple/3, + retract_tuple/4, + clear_relation/2, + clear_relation/3, + retract_relation/2, + retract_relation/3, + get_relations/1, get_relation_hash/2, hashes_from_tuple/1, get_tuples_iterator/2, next_tuple/1, - close_iterator/1, + close_iterator/1, collect_all/1]). +%% @doc Initialize Mnesia database schema and tables. +%% +%% Creates a fresh Mnesia schema with four tables for content-addressed storage: +%% <ul> +%% <li>`attribute' - Hash → Value mapping for deduplication</li> +%% <li>`tuple' - Hash → Tuple mapping with attribute references</li> +%% <li>`relation' - Hash → Relation with merkle tree and schema</li> +%% <li>`database_state' - Hash → Database with relation merkle tree</li> +%% </ul> +%% +%% <b>Warning:</b> This function deletes any existing schema and recreates it from scratch. +%% +%% @returns `ok' on success +%% @see create_database/1 setup() -> mnesia:stop(), mnesia:delete_schema([node()]), @@ -38,19 +98,48 @@ setup() -> {type, set} ]). --record(database_state, {hash, name, tree, relations, timestamp}). --record(relation, {hash, name, tree, schema}). --record(tuple, {hash, relation, attribute_map}). --record(attribute, {hash, value}). - +%% @doc Compute SHA-256 hash of an Erlang term. +%% +%% This is the foundational hashing function used throughout the system for +%% content addressing. All entities (attributes, tuples, relations, databases) +%% are identified by hashes computed with this function. +%% +%% @param Value Any Erlang term to hash +%% @returns Binary SHA-256 hash (32 bytes) +%% +%% @see create_tuple/3 +%% @see create_relation/3 hash(Value) -> crypto:hash(sha256, term_to_binary(Value)). -%% @doc Store a tuple into a relation and update database state -%% Database: #database_state{} record -%% Relation: relation name (atom) -%% Tuple: (map) #{name => "John", age => 18} -%% Returns: {UpdatedDatabase, UpdatedRelation} +%% @doc Insert a tuple into a relation and update the database state. +%% +%% This is the primary operation for adding data to the database. It: +%% <ol> +%% <li>Stores each attribute value with its hash (automatic deduplication)</li> +%% <li>Creates a tuple record mapping attribute names to value hashes</li> +%% <li>Inserts the tuple hash into the relation's merkle tree</li> +%% <li>Computes new relation hash from updated tree</li> +%% <li>Updates database merkle tree with new relation hash</li> +%% <li>Computes new database hash</li> +%% </ol> +%% +%% All operations execute within a Mnesia transaction for ACID guarantees. +%% +%% == Example == +%% ``` +%% DB = operations:create_database(my_db), +%% {DB1, _} = operations:create_relation(DB, users, #{name => string, age => integer}), +%% {DB2, _} = operations:create_tuple(DB1, users, #{name => "Alice", age => 30}). +%% ''' +%% +%% @param Database `#database_state{}' record +%% @param RelationName Atom naming the relation +%% @param Tuple Map of attribute names to values (e.g., `#{name => "Alice", age => 30}') +%% @returns `{UpdatedDatabase, UpdatedRelation}' tuple +%% +%% @see create_relation/3 +%% @see get_tuples_iterator/2 create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Database, database_state) -> F = fun() -> %% Step 1: Store each attribute value and build attribute_map @@ -77,7 +166,8 @@ create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Databa NewRelationTree = merklet:insert({TupleHash, <<>>}, RelationRecord#relation.tree), %% Step 6: Compute new relation hash as the root of the new merkle tree and store - {_,NewRelationHash,_,_} = NewRelationTree, + {_,NewRelationTreeHash,_,_} = NewRelationTree, + NewRelationHash = hash({RelationRecord#relation.name, RelationRecord#relation.schema, NewRelationTreeHash}), UpdatedRelation = #relation{ hash = NewRelationHash, name = RelationName, @@ -110,34 +200,181 @@ create_tuple(Database, RelationName, Tuple) when is_map(Tuple), is_record(Databa {atomic, Result} = mnesia:transaction(F), Result. -retract_tuple(Database, RelationHash, TupleHashes) - when is_record(Database, database_state) andalso is_list(TupleHashes) -> - todo; -retract_tuple(Database, RelationHash, TupleHash) when is_record(Database, database_state) -> +%% @doc Clear all tuples from a relation (truncate). +%% +%% Wrapper for `clear_relation/3' with transactions enabled. +%% +%% @param Database `#database_state{}' record +%% @param RelationHash Binary hash identifying the relation +%% @returns `{atomic, {UpdatedDatabase, UpdatedRelation}}' or `{aborted, Reason}' +%% +%% @see clear_relation/3 +%% @see retract_relation/2 +clear_relation(Database, RelationHash) -> + clear_relation(Database, RelationHash, true). + +%% @doc Clear all tuples from a relation with optional transaction control. +%% +%% Removes all tuples from the relation but preserves its schema. The relation's +%% merkle tree is set to `undefined', and a new relation hash is computed. +%% +%% @param Database `#database_state{}' record +%% @param RelationHash Binary hash identifying the relation +%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction +%% @returns When `Transact =:= true': `{atomic, {UpdatedDatabase, UpdatedRelation}}' +%% When `Transact =:= false': `{UpdatedDatabase, UpdatedRelation}' +%% +%% @see retract_relation/2 +clear_relation(Database, RelationHash, Transact) -> + [Relation] = mnesia:dirty_read(relation, RelationHash), + NewRelationHash = hash({Relation#relation.name, Relation#relation.schema, undefined}), + UpdatedRelation = + Relation#relation{hash = NewRelationHash, + tree = undefined}, + DatabaseTreeWithoutTuples = merklet:insert({atom_to_binary(Relation#relation.name, utf8), NewRelationHash}, Database#database_state.tree), + {_,NewDatabaseHash,_,_} = DatabaseTreeWithoutTuples, + NewRelations = maps:put(Relation#relation.name, NewRelationHash, Database#database_state.relations), + UpdatedDatabase = + Database#database_state{timestamp = erlang:timestamp(), + hash = NewDatabaseHash, + tree = DatabaseTreeWithoutTuples, + relations = NewRelations}, + TX = fun () -> + mnesia:write(relation, UpdatedRelation, write), + mnesia:write(database_state, UpdatedDatabase, write), + {UpdatedDatabase, UpdatedRelation} + end, + case Transact of + true -> mnesia:transaction(TX); + false -> {UpdatedDatabase, UpdatedRelation} + end. + +%% @doc Remove a tuple from a relation. +%% +%% Wrapper for `retract_tuple/4' with transactions enabled. +%% +%% @param Database `#database_state{}' record +%% @param RelationHash Binary hash identifying the relation +%% @param TupleHash Binary hash identifying the tuple to remove +%% @returns `{atomic, {UpdatedDatabase, UpdatedRelation}}' or `{aborted, Reason}' +%% +%% @see retract_tuple/4 +%% @see create_tuple/3 +retract_tuple(Database, RelationHash, TupleHash) -> + retract_tuple(Database, RelationHash, TupleHash, true). + +%% @doc Remove a tuple from a relation with optional transaction control. +%% +%% Deletes a specific tuple from the relation's merkle tree and recomputes +%% the relation and database hashes. +%% +%% @param Database `#database_state{}' record +%% @param RelationHash Binary hash identifying the relation +%% @param TupleHash Binary hash identifying the tuple to remove +%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction +%% @returns When `Transact =:= true': `{atomic, {UpdatedDatabase, UpdatedRelation}}' +%% When `Transact =:= false': `{UpdatedDatabase, UpdatedRelation}' +%% +%% @see create_tuple/3 +retract_tuple(Database, RelationHash, TupleHash, Transact) + when is_record(Database, database_state) -> [Relation] = mnesia:dirty_read(relation, RelationHash), RelationTreeWithoutTuple = merklet:delete(TupleHash, Relation#relation.tree), - {_,NewRelationHash,_,_} = RelationTreeWithoutTuple, - DatabaseTreeWithoutTuple = merklet:delete(RelationHash, Database#database_state.tree), + {_,NewRelationTreeHash,_,_} = RelationTreeWithoutTuple, + NewRelationHash = hash({Relation#relation.name, Relation#relation.schema, NewRelationTreeHash}), + DatabaseTreeWithoutTuple = merklet:insert({atom_to_binary(Relation#relation.name, utf8), NewRelationHash}, Database#database_state.tree), {_,NewDatabaseHash,_,_} = DatabaseTreeWithoutTuple, + NewRelations = maps:put(Relation#relation.name, NewRelationHash, Database#database_state.relations), UpdatedDatabase = Database#database_state{timestamp = erlang:timestamp(), hash = NewDatabaseHash, - tree = DatabaseTreeWithoutTuple}, + tree = DatabaseTreeWithoutTuple, + relations = NewRelations}, UpdatedRelation = Relation#relation{hash = NewRelationHash, tree = RelationTreeWithoutTuple}, TX = fun () -> mnesia:write(relation, UpdatedRelation, write), - mnesia:write(database_state, UpdatedDatabase, write) + mnesia:write(database_state, UpdatedDatabase, write), + {UpdatedDatabase, UpdatedRelation} end, - case mnesia:is_transaction() of - true -> TX(); - false -> mnesia:transaction(TX) + case Transact of + true -> mnesia:transaction(TX); + false -> {UpdatedDatabase, UpdatedRelation} end. +%% @doc Remove a relation from the database. +%% +%% Wrapper for `retract_relation/3' with transactions enabled. +%% +%% @param Database `#database_state{}' record +%% @param Name Atom naming the relation to remove +%% @returns `{atomic, UpdatedDatabase}' or `{aborted, Reason}' +%% +%% @see retract_relation/3 +%% @see clear_relation/2 retract_relation(Database, Name) -> - todo. + retract_relation(Database, Name, true). + +%% @doc Remove a relation from the database with optional transaction control. +%% +%% First clears all tuples from the relation, then removes the relation entirely +%% from the database's relation map and merkle tree. +%% +%% @param Database `#database_state{}' record +%% @param Name Atom naming the relation to remove +%% @param Transact Boolean - if `true', wraps operation in Mnesia transaction +%% @returns When `Transact =:= true': `{atomic, UpdatedDatabase}' +%% When `Transact =:= false': `UpdatedDatabase' +%% +%% @see create_relation/3 +retract_relation(Database, Name, Transact) -> + RelationHash = maps:get(Name, Database#database_state.relations, {error, retract_relation_could_not_find}), + {DatabaseWithClearedRelation, _ClearedRelation} = clear_relation(Database, RelationHash, false), + NewTree = merklet:delete(atom_to_binary(Name, utf8), DatabaseWithClearedRelation#database_state.tree), + NewHash = case NewTree of + undefined -> <<>>; + {_,H,_,_} -> H + end, + UpdatedDatabase = + DatabaseWithClearedRelation#database_state{relations = maps:remove(Name, DatabaseWithClearedRelation#database_state.relations), + hash = NewHash, + tree = NewTree, + timestamp = erlang:timestamp()}, + TX = fun () -> + mnesia:write(database_state, UpdatedDatabase, write), + UpdatedDatabase + end, + case Transact of + true -> mnesia:transaction(TX); + false -> UpdatedDatabase + end. +%% @doc Create a new relation in the database with a schema definition. +%% +%% Creates an empty relation (no tuples) with the specified schema. The schema +%% is stored but not yet enforced - it serves as documentation and provides a +%% foundation for future domain validation. +%% +%% <b>Important:</b> The relation's identity is tied to its name. Two relations +%% with identical schemas but different names are semantically distinct and can +%% contain different tuples. +%% +%% == Example == +%% ``` +%% DB = operations:create_database(my_db), +%% Schema = #{name => string, age => integer, email => string}, +%% {DB1, _Rel} = operations:create_relation(DB, users, Schema). +%% ''' +%% +%% @param Database `#database_state{}' record +%% @param Name Atom naming the new relation +%% @param Definition Map specifying schema (e.g., `#{name => string, age => integer}') +%% @returns `{UpdatedDatabase, NewRelation}' tuple +%% +%% @see create_database/1 +%% @see create_tuple/3 +%% @see retract_relation/2 create_relation(Database, Name, Definition) when is_record(Database, database_state) -> F = fun() -> %% Create relation with empty tree @@ -145,7 +382,7 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st %% It may sound nominalistic but that is a physical concern. %% Two relations might share definitions but their name gives another interpretation %% and therefore different tuples - RelationHash = hash({Name, Definition}), + RelationHash = hash({Name, Definition, undefined}), NewRelation = #relation{ hash = RelationHash, name = Name, @@ -178,32 +415,87 @@ create_relation(Database, Name, Definition) when is_record(Database, database_st {atomic, Result} = mnesia:transaction(F), Result. +%% @doc Create a new database state. +%% +%% Initializes an empty database with no relations. The database starts with: +%% <ul> +%% <li>Empty relation map</li> +%% <li>Undefined merkle tree (will be created when first relation is added)</li> +%% <li>Empty hash</li> +%% <li>Timestamp of creation</li> +%% </ul> +%% +%% All changes are committed to Mnesia within a transaction. +%% +%% == Example == +%% ``` +%% DB = operations:create_database(my_app). +%% ''' +%% +%% @param Name Atom identifying the database +%% @returns `#database_state{}' record +%% +%% @see setup/0 +%% @see create_relation/3 create_database(Name) -> Entry = #database_state{ - name = Name, - hash = <<>>, + name = Name, + hash = <<>>, tree = undefined, relations = #{}, timestamp = erlang:timestamp() }, - {atomic, ok} = mnesia:transaction(fun () -> - mnesia:write(database_state, Entry, write) + {atomic, ok} = mnesia:transaction(fun () -> + mnesia:write(database_state, Entry, write) end), Entry. -%% @doc Get all relation names in a database +%% @doc Get all relation names in a database. +%% +%% Returns a list of atoms representing all relation names currently +%% defined in the database. +%% +%% @param Database `#database_state{}' record +%% @returns List of atoms (relation names) +%% +%% @see get_relation_hash/2 +%% @see create_relation/3 get_relations(Database) -> maps:keys(Database#database_state.relations). -%% @doc Get relation hash by name +%% @doc Get relation hash by name. +%% +%% Looks up a relation's hash in the database's relation map. This hash +%% can be used to retrieve the full relation record from Mnesia. +%% +%% @param Database `#database_state{}' record +%% @param RelationName Atom naming the relation +%% @returns `{ok, Hash}' on success, `{error, not_found}' if relation doesn't exist +%% +%% @see get_relations/1 +%% @see hashes_from_tuple/1 get_relation_hash(Database, RelationName) -> case maps:find(RelationName, Database#database_state.relations) of error -> {error, not_found}; X -> X end. -%% @doc Resolve a tuple hash to actual values -%% Returns map with attribute names and actual values +%% @doc Resolve a tuple hash to actual values. +%% +%% This is an internal function that materializes a tuple by: +%% <ol> +%% <li>Reading the tuple record from Mnesia (contains attribute_map)</li> +%% <li>For each attribute, reading the actual value using its hash</li> +%% <li>Building a map with attribute names and materialized values</li> +%% </ol> +%% +%% Uses dirty reads since all data is immutable. +%% +%% @param TupleHash Binary hash identifying the tuple +%% @returns Map with attribute names and actual values (e.g., `#{name => "Alice", age => 30}') +%% +%% @see get_tuples_iterator/2 +%% @see create_tuple/3 resolve_tuple(TupleHash) -> [#tuple{attribute_map = AttributeMap}] = mnesia:dirty_read(tuple, TupleHash), maps:map(fun(_AttrName, ValueHash) -> @@ -211,8 +503,18 @@ resolve_tuple(TupleHash) -> Value end, AttributeMap). -%% All reads can be dirty as it is all immutable -%% Writes need to be transactional +%% @doc Extract all tuple hashes from a relation. +%% +%% Retrieves the list of all tuple hashes stored in the relation's merkle tree. +%% Returns an empty list if the relation has no tuples (tree is `undefined'). +%% +%% Uses dirty reads since the relation data is immutable. +%% +%% @param RelationHash Binary hash identifying the relation +%% @returns List of binary tuple hashes, or empty list `[]' if relation is empty +%% +%% @see get_tuples_iterator/2 +%% @see create_tuple/3 hashes_from_tuple(RelationHash) -> [Relation] = mnesia:dirty_read(relation, RelationHash), case Relation#relation.tree of @@ -220,8 +522,33 @@ hashes_from_tuple(RelationHash) -> Tree -> merklet:keys(Tree) end. -%% @doc Create an iterator for streaming tuples from a relation -%% Returns: Pid of iterator process +%% @doc Create an iterator for streaming tuples from a relation. +%% +%% Implements the Volcano Iterator Model: spawns an independent process that +%% lazily streams tuples from the relation. This enables: +%% <ul> +%% <li>Memory-bounded queries (tuples materialized on demand)</li> +%% <li>Composable query operators (future: select, project, join)</li> +%% <li>Process-based concurrency</li> +%% </ul> +%% +%% The iterator process responds to `{next, Caller}' messages and sends back +%% either `{tuple, Tuple}' or `done' when exhausted. +%% +%% == Example == +%% ``` +%% Iterator = operations:get_tuples_iterator(DB, users), +%% {ok, Tuple} = operations:next_tuple(Iterator), +%% operations:close_iterator(Iterator). +%% ''' +%% +%% @param Database `#database_state{}' record +%% @param RelationName Atom naming the relation to iterate +%% @returns Pid of iterator process +%% +%% @see next_tuple/1 +%% @see close_iterator/1 +%% @see collect_all/1 get_tuples_iterator(Database, RelationName) when is_record(Database, database_state) -> case maps:get(RelationName, Database#database_state.relations, error) of error -> erlang:error({error_tuple_iterator_init, RelationName}); @@ -229,12 +556,20 @@ get_tuples_iterator(Database, RelationName) when is_record(Database, database_st spawn(fun() -> tuple_iterator_loop(TupleHashes) end) end. -%% X = (a, b, c, d) -%% Y = (a, x, y) -%% Z = project (a, c, y, natural_join(X, Y)) - -%% @doc Get next tuple from iterator1 -%% Returns: {ok, Tuple} | done | {error, timeout} +%% @doc Get next tuple from iterator. +%% +%% Sends a `{next, self()}' message to the iterator process and waits for +%% the response. The iterator will materialize the tuple on demand. +%% +%% Timeout is set to 5 seconds to prevent indefinite blocking. +%% +%% @param IteratorPid Pid returned from `get_tuples_iterator/2' +%% @returns `{ok, Tuple}' with materialized tuple map, +%% `done' when no more tuples remain, or +%% `{error, timeout}' if iterator doesn't respond +%% +%% @see get_tuples_iterator/2 +%% @see close_iterator/1 next_tuple(IteratorPid) -> IteratorPid ! {next, self()}, receive @@ -244,17 +579,38 @@ next_tuple(IteratorPid) -> {error, timeout} end. -%% @doc Close iterator process +%% @doc Close iterator process. +%% +%% Sends a `stop' message to terminate the iterator process. This should be +%% called when you're done consuming tuples to avoid leaving processes running. +%% +%% @param IteratorPid Pid returned from `get_tuples_iterator/2' +%% @returns `ok' +%% +%% @see get_tuples_iterator/2 +%% @see collect_all/1 close_iterator(IteratorPid) -> IteratorPid ! stop, ok. -%% Iterator loop: streams tuples one at a time +%% @private +%% @doc Iterator loop implementation (internal). +%% +%% This is the process loop for the Volcano Iterator Model. It maintains a list +%% of tuple hashes and resolves them lazily when requested. +%% +%% Protocol: +%% <ul> +%% <li>`{next, Caller}' - Resolve next tuple and send `{tuple, ResolvedTuple}' or `done'</li> +%% <li>`stop' - Terminate the process</li> +%% </ul> +%% +%% @param TupleHashes List of binary tuple hashes to stream tuple_iterator_loop([]) -> receive - {next, Caller} -> + {next, Caller} -> Caller ! done; - stop -> + stop -> ok end; tuple_iterator_loop([TupleHash | Rest]) -> @@ -268,7 +624,27 @@ tuple_iterator_loop([TupleHash | Rest]) -> ok end. -%% @doc Helper to collect all tuples from iterator (for testing) +%% @doc Helper to collect all tuples from an iterator into a list. +%% +%% This is a convenience function primarily used for testing. It exhausts the +%% iterator by repeatedly calling `next_tuple/1' until `done' is received, +%% accumulating all tuples into a list. +%% +%% <b>Warning:</b> This materializes all tuples in memory, defeating the purpose +%% of lazy evaluation. Only use for small relations or testing. +%% +%% == Example == +%% ``` +%% Iterator = operations:get_tuples_iterator(DB, users), +%% AllTuples = operations:collect_all(Iterator). +%% %% Iterator is automatically closed +%% ''' +%% +%% @param IteratorPid Pid returned from `get_tuples_iterator/2' +%% @returns List of tuple maps, `{error, Reason, PartialResults}' on timeout +%% +%% @see get_tuples_iterator/2 +%% @see next_tuple/1 collect_all(IteratorPid) -> collect_all(IteratorPid, []). diff --git a/test/operations_test.erl b/test/operations_test.erl new file mode 100644 index 0000000..a69c4fa --- /dev/null +++ b/test/operations_test.erl @@ -0,0 +1,353 @@ +-module(operations_test). +-include("operations.hrl"). +-include_lib("eunit/include/eunit.hrl"). + +%% Test fixtures and setup +setup_test_env() -> + operations:setup(), + ok. + +cleanup_test_env() -> + mnesia:stop(), + ok. + +%% Fixture: Create a sample database with a users relation +sample_database() -> + DB = operations:create_database(test_db), + {DB1, _Relation} = operations:create_relation(DB, users, #{ + name => string, + age => integer + }), + DB1. + +%% Fixture: Add sample tuples to a database +sample_database_with_tuples() -> + DB = sample_database(), + {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), + {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), + DB2. + +%%==================================================================== +%% Database Creation Tests +%%==================================================================== + +database_creation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = operations:create_database(my_db), + ?assertEqual(my_db, DB#database_state.name), + ?assertEqual(#{}, DB#database_state.relations), + ?assertNotEqual(undefined, DB#database_state.timestamp) + end)]}. + +%%==================================================================== +%% Relation Creation Tests +%%==================================================================== + +relation_creation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = operations:create_database(test_db), + Schema = #{name => string, email => string}, + {DB1, Relation} = operations:create_relation(DB, users, Schema), + + % Verify relation was created + ?assertEqual(users, Relation#relation.name), + ?assertEqual(Schema, Relation#relation.schema), + + % Verify database was updated + ?assertEqual([users], operations:get_relations(DB1)), + {ok, RelationHash} = operations:get_relation_hash(DB1, users), + ?assertEqual(Relation#relation.hash, RelationHash) + end)]}. + +%%==================================================================== +%% Tuple Operations Tests +%%==================================================================== + +tuple_creation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database(), + InitialHash = DB#database_state.hash, + + % Add a tuple + {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), + + % Verify database hash changed + ?assertNotEqual(InitialHash, DB1#database_state.hash), + + % Verify tuple can be retrieved + Iterator = operations:get_tuples_iterator(DB1, users), + Tuples = operations:collect_all(Iterator), + ?assertEqual(1, length(Tuples)), + [Tuple] = Tuples, + ?assertEqual("Alice", maps:get(name, Tuple)), + ?assertEqual(30, maps:get(age, Tuple)) + end)]}. + +tuple_multiple_insertions_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database(), + + % Add multiple tuples + {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), + {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), + {DB3, _} = operations:create_tuple(DB2, users, #{name => "Charlie", age => 35}), + + % Verify all tuples can be retrieved + Iterator = operations:get_tuples_iterator(DB3, users), + Tuples = operations:collect_all(Iterator), + ?assertEqual(3, length(Tuples)), + + % Verify hashes changed with each insertion + ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash), + ?assertNotEqual(DB1#database_state.hash, DB2#database_state.hash), + ?assertNotEqual(DB2#database_state.hash, DB3#database_state.hash) + end)]}. + +%%==================================================================== +%% Hash Comparison Tests (Time-based) +%%==================================================================== + +database_state_hash_comparison_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database(), + Hash0 = DB#database_state.hash, + + % State 1: Add first tuple + {DB1, _} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), + Hash1 = DB1#database_state.hash, + + % State 2: Add second tuple + {DB2, _} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), + Hash2 = DB2#database_state.hash, + + % State 3: Add third tuple + {DB3, _} = operations:create_tuple(DB2, users, #{name => "Charlie", age => 35}), + Hash3 = DB3#database_state.hash, + + % Verify all hashes are unique + ?assertNotEqual(Hash0, Hash1), + ?assertNotEqual(Hash1, Hash2), + ?assertNotEqual(Hash2, Hash3), + ?assertNotEqual(Hash0, Hash2), + ?assertNotEqual(Hash0, Hash3), + ?assertNotEqual(Hash1, Hash3) + end)]}. + +relation_hash_comparison_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database(), + {ok, RelationHash0} = operations:get_relation_hash(DB, users), + + % Add tuple and get new relation hash + {DB1, Relation1} = operations:create_tuple(DB, users, #{name => "Alice", age => 30}), + RelationHash1 = Relation1#relation.hash, + + % Add another tuple + {DB2, Relation2} = operations:create_tuple(DB1, users, #{name => "Bob", age => 25}), + RelationHash2 = Relation2#relation.hash, + + % Verify relation hashes changed over time + ?assertNotEqual(RelationHash0, RelationHash1), + ?assertNotEqual(RelationHash1, RelationHash2), + ?assertNotEqual(RelationHash0, RelationHash2), + + % Verify we can still get relation hash from database + {ok, CurrentHash} = operations:get_relation_hash(DB2, users), + ?assertEqual(RelationHash2, CurrentHash) + end)]}. + +%%==================================================================== +%% Tuple Retraction Tests +%%==================================================================== + +retract_tuple_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database_with_tuples(), + {ok, RelationHash} = operations:get_relation_hash(DB, users), + + % Get tuple hashes + TupleHashes = operations:hashes_from_tuple(RelationHash), + ?assertEqual(2, length(TupleHashes)), + + % Retract one tuple + [TupleHash | _] = TupleHashes, + {atomic, {DB1, _}} = operations:retract_tuple(DB, RelationHash, TupleHash), + + % Verify tuple was removed + {ok, NewRelationHash} = operations:get_relation_hash(DB1, users), + NewTupleHashes = operations:hashes_from_tuple(NewRelationHash), + ?assertEqual(1, length(NewTupleHashes)), + + % Verify database hash changed + ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) + end)]}. + +%%==================================================================== +%% Relation Operations Tests +%%==================================================================== + +clear_relation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database_with_tuples(), + {ok, RelationHash} = operations:get_relation_hash(DB, users), + + % Verify tuples exist + TupleHashes = operations:hashes_from_tuple(RelationHash), + ?assertEqual(2, length(TupleHashes)), + + % Clear relation + {atomic, {DB1, ClearedRelation}} = operations:clear_relation(DB, RelationHash), + + % Verify relation is empty + ?assertEqual(undefined, ClearedRelation#relation.tree), + NewTupleHashes = operations:hashes_from_tuple(ClearedRelation#relation.hash), + ?assertEqual([], NewTupleHashes), + + % Verify database hash changed + ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) + end)]}. + +retract_relation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database_with_tuples(), + + % Verify relation exists + ?assertEqual([users], operations:get_relations(DB)), + + % Retract relation + {atomic, DB1} = operations:retract_relation(DB, users), + + % Verify relation was removed + ?assertEqual([], operations:get_relations(DB1)), + ?assertEqual({error, not_found}, operations:get_relation_hash(DB1, users)), + + % Verify database hash changed + ?assertNotEqual(DB#database_state.hash, DB1#database_state.hash) + end)]}. + +%%==================================================================== +%% Iterator Tests +%%==================================================================== + +iterator_basic_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database_with_tuples(), + + % Get iterator and retrieve tuples one by one + Iterator = operations:get_tuples_iterator(DB, users), + + % Get first tuple + {ok, Tuple1} = operations:next_tuple(Iterator), + ?assert(is_map(Tuple1)), + ?assert(maps:is_key(name, Tuple1)), + ?assert(maps:is_key(age, Tuple1)), + + % Get second tuple + {ok, Tuple2} = operations:next_tuple(Iterator), + ?assert(is_map(Tuple2)), + + % No more tuples + ?assertEqual(done, operations:next_tuple(Iterator)), + + operations:close_iterator(Iterator) + end)]}. + +iterator_collect_all_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database_with_tuples(), + + Iterator = operations:get_tuples_iterator(DB, users), + Tuples = operations:collect_all(Iterator), + + ?assertEqual(2, length(Tuples)), + + % Verify both tuples are present + Names = [maps:get(name, T) || T <- Tuples], + ?assert(lists:member("Alice", Names)), + ?assert(lists:member("Bob", Names)) + end)]}. + +iterator_empty_relation_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + DB = sample_database(), + + Iterator = operations:get_tuples_iterator(DB, users), + Tuples = operations:collect_all(Iterator), + + ?assertEqual([], Tuples) + end)]}. + +%%==================================================================== +%% Hash Consistency Tests +%%==================================================================== + +hash_determinism_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + % Same value should produce same hash + Hash1 = operations:hash(<<"test">>), + Hash2 = operations:hash(<<"test">>), + ?assertEqual(Hash1, Hash2), + + % Different values should produce different hashes + Hash3 = operations:hash(<<"different">>), + ?assertNotEqual(Hash1, Hash3) + end)]}. + +database_state_consistency_test_() -> + {setup, + fun setup_test_env/0, + fun(_) -> cleanup_test_env() end, + [?_test(begin + % Create two identical databases with same operations + DB1 = operations:create_database(db1), + {DB1_1, _} = operations:create_relation(DB1, users, #{name => string}), + {DB1_2, _} = operations:create_tuple(DB1_1, users, #{name => "Alice"}), + + DB2 = operations:create_database(db2), + {DB2_1, _} = operations:create_relation(DB2, users, #{name => string}), + {DB2_2, _} = operations:create_tuple(DB2_1, users, #{name => "Alice"}), + + % Relations should have the same hash (same schema and tuples) + {ok, RelHash1} = operations:get_relation_hash(DB1_2, users), + {ok, RelHash2} = operations:get_relation_hash(DB2_2, users), + ?assertEqual(RelHash1, RelHash2) + end)]}. |