diff options
Diffstat (limited to '')
| -rw-r--r-- | docs/code.org | 272 |
1 files changed, 0 insertions, 272 deletions
diff --git a/docs/code.org b/docs/code.org deleted file mode 100644 index 30ff9c9..0000000 --- a/docs/code.org +++ /dev/null @@ -1,272 +0,0 @@ -#+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 |