Extern handles for embedded runtime

8 files changed, 649 insertions, 84 deletions

diff --git a/include/CursorManager.h b/include/CursorManager.h
index 092229c..839bf5e 100644
--- a/include/CursorManager.h
+++ b/include/CursorManager.h
@@ -6,6 +6,7 @@
 #include "Types.h"
 
 #include <cstddef>
+#include <string>
 #include <vector>
 
 /**
@@ -25,6 +26,11 @@ namespace nt
      * Tuples are never loaded all at once. Open() fetches the first page;
      * each subsequent Next() call transparently fetches the next page from
      * the backend once the current page is exhausted.
+     *
+     * Pagination is driven by the Merkle B-tree: each cursor carries the hex
+     * hash of the relation's Merkle root at open time, and LoadPage calls
+     * Merkle::Page(backend, merkle_root, fetch_offset, PAGE_SIZE) to retrieve
+     * the next page of tuple hashes without loading sibling subtrees.
      */
     class NT_API CursorManager
     {
@@ -43,10 +49,19 @@ namespace nt
          *
          * The pointer returned by Next() is valid only until the next Next()
          * or Close() call — a page replacement invalidates all prior pointers.
+         *
+         * merkle_root is seeded from ObjectManager::Relation::merkle_root at
+         * open time and does not change during iteration; the cursor reads the
+         * snapshot captured when it was opened.
          */
         struct cursor {
             HandlerManager::handle* handle = nullptr;
             /**
+             * Hex hash of the relation's Merkle B-tree root node.
+             * Empty string means the relation contains no tuples.
+             */
+            std::string merkle_root;
+            /**
              * Bound argument values for EPHEMERAL_RELATION cursors.
              * Written by the JOIN operator before each probe; ignored for
              * stored RELATION cursors.
@@ -54,17 +69,24 @@ namespace nt
             std::vector<std::string> args;
             std::vector<Tuple> page;
             std::size_t page_position = 0;
-            std::size_t fetch_offset  = 0;   // next TupleHashes() call starts here
+            std::size_t fetch_offset  = 0;   // next Merkle::Page() call starts here
             bool exhausted = false;
         };
 
         /**
          * @brief Opens a cursor on the relation referenced by the handle.
          *
-         * Fetches the first page immediately. Returns nullptr if the relation
-         * has no tuples or the handle does not refer to a RELATION.
+         * Fetches the first page immediately for non-empty relations. Returns
+         * a valid exhausted cursor when @p merkle_root is empty (empty relation).
+         * Returns nullptr when the handle does not refer to a RELATION or
+         * EPHEMERAL_RELATION.
+         *
+         * @param handle       Open RELATION or EPHEMERAL_RELATION handle.
+         * @param merkle_root  Hex hash of the relation's Merkle root at open
+         *                     time. Ignored for EPHEMERAL_RELATION handles.
          */
-        cursor* Open(HandlerManager::handle* handle);
+        cursor* Open(HandlerManager::handle* handle,
+                     const std::string& merkle_root = "");
 
         /**
          * @brief Pulls the next tuple from the cursor.
@@ -83,8 +105,12 @@ namespace nt
     private:
         IStorageBackend& backend_;
 
-        /** Fetches a page of hashes, resolves each from the KV store, and
-         *  deserializes them into cursor->page. Clears the existing page. */
-        void LoadPage(cursor* c, const std::vector<std::string>& path);
+        /**
+         * Fetches a page of hashes via Merkle::Page, resolves each from the
+         * KV store, and deserializes them into cursor->page. Clears the
+         * existing page.  Advances fetch_offset by the number of hashes
+         * returned; sets exhausted when fewer than PAGE_SIZE hashes come back.
+         */
+        void LoadPage(cursor* c);
     };
 }
diff --git a/include/IStorageBackend.h b/include/IStorageBackend.h
index 884af2d..e408c95 100644
--- a/include/IStorageBackend.h
+++ b/include/IStorageBackend.h
@@ -7,27 +7,27 @@
 
 /**
  * @file IStorageBackend.h
- * @brief Abstract KV storage backend consumed by CursorManager.
+ * @brief Abstract KV storage backend consumed by CursorManager and Merkle.
  *
  * Storage is strictly content-addressed: every value is stored under its
- * SHA256 hex digest. This mirrors the Sakura physical layer in which the
- * key is always `Sha256.to_hex (Sha256.string serialized_bytes)` and the
- * value is the raw serialized bytes.
- *
- * Relation membership (which tuple hashes belong to a given relation) is
- * tracked via a separate index managed by LinkTuple / TupleHashes. This
- * corresponds to Sakura's B+ tree of tuple hashes stored under each relation.
+ * SHA256 hex digest.  Relation membership (which tuple hashes belong to a
+ * given relation) is now tracked via the Merkle B-tree maintained by the
+ * Merkle class, not by this interface.  Only Put and Get are required.
  */
 
 namespace nt
 {
     /**
      * @interface IStorageBackend
-     * @brief Contract between CursorManager and a physical (or mock) storage engine.
+     * @brief Contract between CursorManager / Merkle and a physical storage engine.
+     *
+     * Two primitives are sufficient:
+     *   - Put: store bytes, get back the content-address (SHA256 hex).
+     *   - Get: retrieve bytes by content-address.
      *
-     * Storage is strictly content-addressed: every value lives under its own
-     * SHA256 digest. Relation membership is tracked separately via
-     * LinkTuple / TupleHashes, mirroring Sakura's per-relation B+ tree.
+     * Both are idempotent.  The Merkle class stores node blobs via Put/Get and
+     * maintains insertion-order-independent relation membership on top of these
+     * two primitives.
      */
     class IStorageBackend
     {
@@ -38,7 +38,7 @@ namespace nt
          * @brief Stores a serialized value and returns its SHA256 hex hash.
          *
          * Idempotent: storing the same bytes twice does not create a duplicate.
-         * The hash is the only valid key for subsequent Get calls.
+         * The returned hash is the only valid key for subsequent Get calls.
          */
         virtual std::string Put(std::vector<uint8_t> value) = 0;
 
@@ -47,30 +47,5 @@ namespace nt
          * @return The stored bytes, or std::nullopt when the hash is unknown.
          */
         virtual std::optional<std::vector<uint8_t>> Get(const std::string& hash) = 0;
-
-        /**
-         * @brief Records that a tuple (by hash) belongs to a relation (by path).
-         *
-         * Idempotent. Corresponds to appending a tuple hash to a relation's
-         * B+ tree in Sakura's physical layer.
-         */
-        virtual void LinkTuple(const std::vector<std::string>& relation_path,
-                               const std::string& tuple_hash) = 0;
-
-        /**
-         * @brief Returns a page of tuple hashes for a relation.
-         *
-         * Pagination is tuple-level: @p offset and @p limit count whole tuples.
-         * Hashes are returned in insertion order.
-         *
-         * @param relation_path Logical relation path.
-         * @param offset        Zero-based index of the first tuple to return.
-         * @param limit         Maximum number of tuple hashes to return.
-         * @return Ordered list of SHA256 hex hashes. Empty when past the end.
-         */
-        virtual std::vector<std::string> TupleHashes(
-            const std::vector<std::string>& relation_path,
-            std::size_t offset,
-            std::size_t limit) = 0;
     };
 }
diff --git a/include/InMemoryBackend.h b/include/InMemoryBackend.h
index 8f7f50a..55472a8 100644
--- a/include/InMemoryBackend.h
+++ b/include/InMemoryBackend.h
@@ -11,33 +11,23 @@
 
 /**
  * @file InMemoryBackend.h
- * @brief In-process KV storage backend backed by unordered_maps.
+ * @brief In-process KV storage backend backed by an unordered_map.
+ *
+ * Intended for unit tests where SQLite is not appropriate.  Data does not
+ * survive process exit and is not thread-safe.
+ *
+ * Relation membership is tracked by the Merkle class, not this backend.
  */
 
 namespace nt
 {
-    /**
-     * @interface InMemoryBackend
-     * @brief IStorageBackend implementation that keeps all data in process memory.
-     *
-     * Intended for unit tests where SQLite is not appropriate. Data does not
-     * survive process exit and is not thread-safe.
-     */
     class NT_API InMemoryBackend : public IStorageBackend
     {
     public:
         std::string Put(std::vector<uint8_t> value) override;
         std::optional<std::vector<uint8_t>> Get(const std::string& hash) override;
-        void LinkTuple(const std::vector<std::string>& relation_path,
-                       const std::string& tuple_hash) override;
-        std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path,
-                                             std::size_t offset,
-                                             std::size_t limit) override;
 
     private:
         std::unordered_map<std::string, std::vector<uint8_t>> kv_;
-        std::unordered_map<std::string, std::vector<std::string>> index_;
-
-        static std::string PathKey(const std::vector<std::string>& path);
     };
 }
diff --git a/include/Merkle.h b/include/Merkle.h
new file mode 100644
index 0000000..8380093
--- /dev/null
+++ b/include/Merkle.h
@@ -0,0 +1,164 @@
+#pragma once
+
+#include "IStorageBackend.h"
+
+#include <array>
+#include <cstddef>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+/**
+ * @file Merkle.h
+ * @brief Sorted content-addressed B-tree over SHA-256 tuple hash hex strings.
+ *
+ * Each node is stored as an immutable blob in IStorageBackend via Put/Get.
+ * All three operations load only the nodes on the path from root to the target
+ * leaf — O(log_B(n)) nodes in memory at once, never the whole tree.
+ *
+ * **Branching factor B = 64**: leaves hold up to 64 hashes; internal nodes hold
+ * up to 64 child entries.  At B=64 and 1 billion tuples the tree is at most
+ * 5 levels deep (~20 KB peak working set).
+ *
+ * **Immutability**: nodes are never overwritten once written (content-addressed).
+ * Insert and Remove produce new nodes only along the modified path; old nodes
+ * remain valid for any snapshot that still holds their root hash.
+ *
+ * **Internal node entry layout** (leaf_count | min_hash | child_hash):
+ *   - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page()
+ *     without loading sibling subtrees.
+ *   - `min_hash` (smallest tuple hash in the subtree) is the routing key.
+ *   - `child_hash` is the content-addressed hash of the child node blob.
+ *
+ * **Invariants** (asserted in debug builds):
+ *   - No leaf or internal node is ever empty.
+ *   - Internal node entries are sorted ascending by min_hash.
+ *   - All public entry points that accept a hex hash throw `std::invalid_argument`
+ *     when the string is not exactly 64 lowercase hex characters.
+ *
+ * @todo Add bounds checking in decode_leaf / decode_internal: validate that the
+ *       reported entry count does not exceed the actual blob size before reading.
+ *       Currently a truncated or corrupt blob causes out-of-bounds reads.
+ */
+
+namespace nt {
+
+class Merkle {
+public:
+    static constexpr size_t B = 64;
+
+    /**
+     * @brief Insert a tuple hash into the tree.
+     * @param store     KV backend for node serialization.
+     * @param root_hex  Current root hash (empty string = empty tree).
+     * @param hash_hex  64-char hex SHA-256 of the tuple to insert.
+     * @return New root hash.  Equal to root_hex when the hash was already present.
+     */
+    static std::string Insert(IStorageBackend& store,
+                               const std::string& root_hex,
+                               const std::string& hash_hex);
+
+    /**
+     * @brief Remove a tuple hash from the tree.
+     * @param store     KV backend.
+     * @param root_hex  Current root hash.
+     * @param hash_hex  64-char hex SHA-256 of the tuple to remove.
+     * @return New root hash.  Empty string when the tree becomes empty.
+     */
+    static std::string Remove(IStorageBackend& store,
+                               const std::string& root_hex,
+                               const std::string& hash_hex);
+
+    /**
+     * @brief Page through tuple hashes in sorted order.
+     *
+     * Descends to the leaf at logical position @p offset using cumulative
+     * leaf_counts stored in internal nodes, then walks forward collecting at
+     * most @p limit hashes.  Only the nodes on the active path are loaded;
+     * sibling subtrees are never touched.
+     *
+     * @param store     KV backend.
+     * @param root_hex  Current root hash.
+     * @param offset    Zero-based logical tuple offset.
+     * @param limit     Maximum number of hashes to return.
+     * @return Hex hash strings in sorted order.  Empty when past the end.
+     */
+    static std::vector<std::string> Page(IStorageBackend& store,
+                                          const std::string& root_hex,
+                                          size_t offset,
+                                          size_t limit);
+
+private:
+    using Hash32 = std::array<uint8_t, 32>;
+
+    struct LeafNode {
+        std::vector<Hash32> hashes;  // sorted ascending, len ≤ B
+    };
+
+    // Wire: 8-byte leaf_count | 32-byte min_hash | 32-byte child_hash
+    struct ChildEntry {
+        uint64_t leaf_count;  // number of tuple hashes in this subtree
+        Hash32   min_hash;    // smallest tuple hash in the subtree
+        Hash32   child_hash;  // content-addressed hash of the child node
+    };
+
+    struct InternalNode {
+        std::vector<ChildEntry> entries;  // sorted by min_hash, len ≤ B
+    };
+
+    // Wire format
+    static std::vector<uint8_t> encode_leaf(const LeafNode& n);
+    static std::vector<uint8_t> encode_internal(const InternalNode& n);
+    static LeafNode             decode_leaf(const std::vector<uint8_t>& bytes);
+    static InternalNode         decode_internal(const std::vector<uint8_t>& bytes);
+    static bool                 is_leaf_bytes(const std::vector<uint8_t>& bytes);
+
+    // Hex / binary
+    static Hash32      hex_to_bin(const std::string& hex);
+    static std::string bin_to_hex(const Hash32& bin);
+
+    // Storage helpers
+    static std::vector<uint8_t> load_node(IStorageBackend& store,
+                                           const std::string& hash_hex);
+    static std::string store_leaf(IStorageBackend& store, const LeafNode& n);
+    static std::string store_internal(IStorageBackend& store, const InternalNode& n);
+
+    // Returns the minimum hash of the subtree rooted at node_hex.
+    static Hash32 subtree_min(IStorageBackend& store, const std::string& node_hex);
+
+    // Recursive insert result: new node hash, subtree leaf count, optional split.
+    struct InsertResult {
+        std::string new_hash;
+        uint64_t    leaf_count = 0;
+        bool        did_split  = false;
+        uint64_t    split_leaf_count = 0;
+        Hash32      split_min_hash   = {};
+        std::string split_hash;
+    };
+
+    static InsertResult insert_into(IStorageBackend& store,
+                                     const std::string& node_hex,
+                                     const Hash32& tuple_hash);
+
+    // Recursive remove result: new node hash (empty = node gone), leaf count.
+    struct RemoveResult {
+        std::string new_hash;
+        uint64_t    leaf_count = 0;
+    };
+
+    static RemoveResult remove_from(IStorageBackend& store,
+                                     const std::string& node_hex,
+                                     const Hash32& tuple_hash);
+
+    // Page collection — offset consumed as we descend.
+    static void page_from(IStorageBackend& store,
+                           const std::string& node_hex,
+                           size_t& offset,
+                           size_t limit,
+                           std::vector<Hash32>& out);
+
+    // Find which child to route into (rightmost whose min_hash ≤ target).
+    static size_t route(const InternalNode& node, const Hash32& target);
+};
+
+} // namespace nt
diff --git a/include/ObjectManager.h b/include/ObjectManager.h
index 32b3ae9..e30ff1b 100644
--- a/include/ObjectManager.h
+++ b/include/ObjectManager.h
@@ -35,12 +35,35 @@ namespace nt
 
         /** @brief Abstract registry object representing a multigroup. */
         class Multigroup : public IObject {};
-        /** @brief Abstract registry object representing a relation. */
-        class Relation : public IObject {};
+        /**
+         * @brief Registry object representing a stored relation.
+         *
+         * merkle_root is the hex hash of the Merkle B-tree root node stored in
+         * the KV backend.  Empty string means the relation contains no tuples.
+         * Updated atomically by rnt_link_tuple / rnt_unlink_tuple / rnt_clear_relation.
+         */
+        class Relation : public IObject {
+        public:
+            std::string merkle_root;
+        };
         /** @brief Abstract registry object representing a transaction. */
         class Transaction : public IObject {};
 
         /**
+         * @brief A named mutable reference to a multigroup state.
+         *
+         * The payload field carries the serialized multigroup bytes in whatever
+         * format the caller registered them with. The C API returns these bytes
+         * verbatim when a handle to the branch is opened; Sakura is responsible
+         * for deserializing them into a Multigroup object.
+         */
+        class Branch : public IObject {
+        public:
+            std::string name;
+            std::vector<uint8_t> payload;
+        };
+
+        /**
          * @brief Describes the behavior and capabilities of an object category.
          *
          * @todo Replace `methods` with typed callback fields: `OpenProcedure`,
diff --git a/include/RNT_C_API.h b/include/RNT_C_API.h
new file mode 100644
index 0000000..ddf6a97
--- /dev/null
+++ b/include/RNT_C_API.h
@@ -0,0 +1,378 @@
+#pragma once
+
+/**
+ * @file RNT_C_API.h
+ * @brief C-callable surface over the RNT manager pipeline for OCaml ctypes.
+ *
+ * All types are opaque void pointers on the C side; the implementation casts
+ * them to the appropriate C++ types internally. Callers must never dereference
+ * handle or cursor pointers directly.
+ *
+ * ## Memory contract
+ *   - Strings returned via out-parameters (char**) are heap-allocated by the
+ *     API and must be released with rnt_free_string().
+ *   - Payloads returned via (uint8_t**, size_t*) are heap-allocated and must
+ *     be released with rnt_free_bytes().
+ *   - Handles and cursors are owned by the caller and must be closed before
+ *     the program exits.
+ *
+ * ## Error convention
+ *   - Functions returning int use 0 for success and a negative value for error.
+ *   - Functions returning a pointer return NULL on failure.
+ *
+ * ## Thread safety
+ *   This API is **not thread-safe**. The global runtime (g_rt) is a single
+ *   in-process instance; all callers share the same ObjectManager and storage
+ *   backend. The expected usage model is a single OCaml thread (or domain)
+ *   driving the API at a time. If concurrent access is needed in the future,
+ *   a per-object or per-relation mutex strategy should be introduced.
+ *
+ * @todo Implement AUTH_CLAIM::READ/WRITE enforcement in rnt_open_handle once
+ *       PermissionsManager::Access is wired to a real policy engine. Currently
+ *       all handles open with full access regardless of the claims parameter.
+ */
+
+#include <stddef.h>
+#include <stdint.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** Opaque handle to a registry object opened through HandlerManager. */
+typedef void* rnt_handle_t;
+
+/** Opaque cursor over a relation, driven by the VM or used directly. */
+typedef void* rnt_cursor_t;
+
+/* ------------------------------------------------------------------ */
+/* Runtime lifecycle                                                    */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Initialises the RNT runtime with the selected storage backend.
+ *
+ * Must be called before any other API function. Once the runtime is
+ * successfully initialised, subsequent calls are no-ops and return 0.
+ * If initialisation fails (returns negative), the call may be retried
+ * with corrected parameters — the runtime is left in a clean state.
+ *
+ * @param driver        Storage driver to use: "sqlite" or "memory".
+ *                      "sqlite" persists data to @p storage_path.
+ *                      "memory" keeps all data in process memory (ignores
+ *                      @p storage_path); intended for tests.
+ * @param storage_path  File path for the SQLite database, or ":memory:" for
+ *                      an ephemeral SQLite store. Ignored when driver is
+ *                      "memory".
+ * @return 0 on success, negative on error.
+ */
+int rnt_init(const char* driver, const char* storage_path);
+
+/* ------------------------------------------------------------------ */
+/* Authentication                                                       */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Runs PermissionsManager::Firewall for a connection.
+ *
+ * @param auth_method  "plain_text" or "certificate".
+ * @param claims_out   Set to a heap-allocated, newline-separated claim string.
+ *                     Release with rnt_free_string(). NULL on error.
+ * @return 0 on success, negative when authentication is rejected.
+ */
+int rnt_firewall(const char* auth_method, char** claims_out);
+
+/* ------------------------------------------------------------------ */
+/* Handle lifecycle                                                     */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Opens a handle to the object at the given slash-separated path.
+ *
+ * Runs the full HandlerManager::Open pipeline:
+ * ObjectManager::Find → PermissionsManager::Access →
+ * IdentityManager::CanOpen → LifecycleManager::Contention →
+ * LifecycleManager::Monitor.
+ *
+ * @param path    Slash-separated logical path, e.g. "/system/branches/main".
+ * @param claims  Claim string returned by rnt_firewall (may be NULL).
+ * @return Handle pointer, or NULL when the path is not found or access is denied.
+ */
+rnt_handle_t rnt_open_handle(const char* path, const char* claims);
+
+/**
+ * @brief Closes a handle, running HandlerManager::Close and Unmonitor.
+ * @return 0 on success, negative on error.
+ */
+int rnt_close_handle(rnt_handle_t handle);
+
+/**
+ * @brief Reads the raw payload bytes stored in a BRANCH object.
+ *
+ * Only valid for handles opened on BRANCH objects. The caller uses the bytes
+ * to reconstruct the in-memory multigroup (e.g. via Sakura's deserializer).
+ *
+ * @param handle       Handle to a BRANCH object.
+ * @param payload_out  Set to a heap-allocated copy of the payload bytes.
+ *                     Release with rnt_free_bytes().
+ * @param len_out      Set to the number of bytes in payload_out.
+ * @return 0 on success, negative when the handle is not a BRANCH.
+ */
+int rnt_branch_payload(rnt_handle_t handle,
+                       uint8_t**   payload_out,
+                       size_t*     len_out);
+
+/**
+ * @brief Writes new payload bytes into the BRANCH object referenced by handle.
+ *
+ * Updates the in-memory branch object. Callers are responsible for persisting
+ * the multigroup state to the storage backend separately via tuple link
+ * operations.
+ *
+ * Write exclusion is structural: BRANCH objects carry @c exclusive=true in
+ * their object_type, so LifecycleManager::Contention prevents a second handle
+ * from being opened while a writer holds the branch. AUTH_CLAIM::WRITE is not
+ * checked at the C API boundary.
+ *
+ * @param handle   Open BRANCH handle.
+ * @param payload  New serialized multigroup bytes.
+ * @param len      Number of bytes in payload.
+ * @return 0 on success, negative on error.
+ */
+int rnt_branch_set_payload(rnt_handle_t handle,
+                           const uint8_t* payload,
+                           size_t         len);
+
+/* ------------------------------------------------------------------ */
+/* Object registration                                                  */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Registers a RELATION object at the given path.
+ *
+ * Idempotent: if an object already exists at the path, the call succeeds
+ * without re-registering.
+ *
+ * @param path Slash-separated path, e.g. "/system/branches/main/relations/foo".
+ * @return 0 on success, negative on error.
+ */
+int rnt_register_relation(const char* path);
+
+/**
+ * @brief Registers a BRANCH object at the given path with an initial payload.
+ *
+ * If a BRANCH already exists at this path, returns 0 without modifying it.
+ *
+ * @param path        Slash-separated path, e.g. "/system/branches/main".
+ * @param payload     Initial serialized multigroup bytes (may be NULL for empty).
+ * @param payload_len Byte count of payload.
+ * @return 0 on success, negative on error.
+ */
+int rnt_register_branch(const char* path,
+                        const uint8_t* payload,
+                        size_t         payload_len);
+
+/* ------------------------------------------------------------------ */
+/* Tuple storage                                                        */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Stores a tuple and links it to the relation at the given path.
+ *
+ * Tuples are encoded as a flat key=value string, one attribute per line:
+ *   "name=Blathers\nprofession=Museum Curator\n"
+ * Attributes are sorted by name before hashing to ensure content-addressing
+ * is order-independent.
+ *
+ * @param relation_path  Slash-separated relation path.
+ * @param kv_attrs       Newline-delimited "key=value" attribute string.
+ * @param hash_out       Set to the 64-character hex SHA-256 hash of the tuple.
+ *                       Release with rnt_free_string(). NULL on error.
+ * @return 0 on success, negative on error.
+ */
+int rnt_link_tuple(const char* relation_path,
+                   const char* kv_attrs,
+                   char**      hash_out);
+
+/**
+ * @brief Removes a tuple from the relation's Merkle tree and tuple store.
+ *
+ * Calls Merkle::Remove on the relation's current root and updates
+ * ObjectManager::Relation::merkle_root atomically.  The tuple bytes remain in
+ * the KV store (they may be referenced by older snapshots); only the
+ * membership in the current tree is removed.
+ *
+ * @param relation_path  Slash-separated relation path.
+ * @param tuple_hash     64-character hex SHA-256 of the tuple to remove.
+ * @return 0 on success, negative when the relation is not found.
+ */
+int rnt_unlink_tuple(const char* relation_path, const char* tuple_hash);
+
+/**
+ * @brief Resets a relation's Merkle root to the empty-tree state.
+ *
+ * Sets ObjectManager::Relation::merkle_root to the empty string.  Existing
+ * tuple bytes remain in the KV store.  After this call the relation contains
+ * no tuples from the perspective of cursor iteration.
+ *
+ * @param relation_path  Slash-separated relation path.
+ * @return 0 on success, negative when the relation is not found.
+ */
+int rnt_clear_relation(const char* relation_path);
+
+/**
+ * @brief Returns the current Merkle root hash for a relation.
+ *
+ * OCaml calls this after rnt_link_tuple or rnt_unlink_tuple to read the
+ * updated root back and store it in the in-memory multigroup (tree_pointer).
+ * An empty string is returned for a relation that contains no tuples.
+ *
+ * @param relation_path  Slash-separated relation path.
+ * @param root_hash_out  Set to the 64-character hex root hash, or to an empty
+ *                       heap-allocated string for an empty relation.
+ *                       Release with rnt_free_string().
+ * @return 0 on success, negative when the relation is not found.
+ */
+int rnt_relation_root(const char* relation_path, char** root_hash_out);
+
+/**
+ * @brief Writes a Merkle root hash into a relation's ObjectManager entry.
+ *
+ * Called by Sakura's open_branch during multigroup reconstruction: after
+ * deserializing the branch payload, OCaml calls this function once per
+ * relation to restore the persisted Merkle root into the in-memory
+ * ObjectManager so that subsequent cursors see the correct tuple set.
+ *
+ * @param relation_path  Slash-separated relation path.
+ * @param root_hash      64-character hex Merkle root, or empty string to mark
+ *                       the relation as empty.
+ * @return 0 on success, negative when the relation is not found.
+ */
+int rnt_set_relation_root(const char* relation_path, const char* root_hash);
+
+/* ------------------------------------------------------------------ */
+/* Cursor and VM                                                        */
+/* ------------------------------------------------------------------ */
+
+/**
+ * @brief Opens a cursor on the relation referenced by handle.
+ *
+ * The returned cursor is positioned before the first tuple. Advance it with
+ * rnt_cursor_next(). The cursor must be closed with rnt_cursor_close() before
+ * closing the handle.
+ *
+ * @param handle  Open RELATION handle.
+ * @return Cursor pointer, or NULL on error.
+ */
+rnt_cursor_t rnt_cursor_open(rnt_handle_t handle);
+
+/**
+ * @brief Advances the cursor and returns the next tuple as a kv string.
+ *
+ * The tuple is encoded as a newline-delimited "key=value" string matching the
+ * format accepted by rnt_link_tuple:
+ *   "name=Blathers\nprofession=Museum Curator\n"
+ *
+ * @param cursor       Open cursor.
+ * @param tuple_out    Set to a heap-allocated kv string, or NULL when exhausted.
+ *                     Release with rnt_free_string() when non-NULL.
+ * @return 1 when a tuple was returned, 0 when exhausted, negative on error.
+ */
+int rnt_cursor_next(rnt_cursor_t cursor, char** tuple_out);
+
+/**
+ * @brief Closes a cursor and releases its resources.
+ * @return 0 on success, negative on error.
+ */
+int rnt_cursor_close(rnt_cursor_t cursor);
+
+/* ------------------------------------------------------------------ */
+/* VM plan builder                                                      */
+/* ------------------------------------------------------------------ */
+
+/** Opaque plan node tree, built incrementally via rnt_plan_* calls. */
+typedef void* rnt_plan_t;
+
+/**
+ * @brief Creates a SCAN plan node that reads all tuples from a stored relation.
+ *
+ * Opens a RELATION handle and cursor internally. Both are transferred to the
+ * plan and released when the resulting VM cursor is closed.
+ *
+ * @param relation_path  Absolute slash-separated path to the relation, e.g.
+ *                       "/system/branches/main/relations/public:users".
+ * @return Plan node, or NULL when the relation does not exist or cannot be opened.
+ */
+rnt_plan_t rnt_plan_scan(const char* relation_path);
+
+/**
+ * @brief Creates a nested-loop JOIN plan node.
+ *
+ * Takes ownership of both @p left and @p right. On success the caller must not
+ * free either child; they are released when the returned plan is freed or
+ * executed. On failure (NULL return) both children are freed.
+ *
+ * @return Plan node, or NULL on error.
+ */
+rnt_plan_t rnt_plan_join(rnt_plan_t left, rnt_plan_t right);
+
+/**
+ * @brief Creates a TAKE plan node that limits output to at most @p limit tuples.
+ *
+ * Takes ownership of @p source. On failure @p source is freed.
+ *
+ * @return Plan node, or NULL on error.
+ */
+rnt_plan_t rnt_plan_take(rnt_plan_t source, size_t limit);
+
+/**
+ * @brief Releases a plan that was built but not yet executed.
+ *
+ * Closes any open cursors and handles owned by the plan tree, then frees all
+ * nodes. Safe to call with NULL. Do NOT call after rnt_vm_execute_plan —
+ * that function takes ownership.
+ */
+void rnt_plan_free(rnt_plan_t plan);
+
+/**
+ * @brief Executes a plan tree and returns a streaming VM cursor.
+ *
+ * Takes ownership of @p plan; the caller must not call rnt_plan_free after this.
+ * The returned cursor is advanced with rnt_vm_cursor_next() and must be closed
+ * with rnt_vm_cursor_close(), which also releases all plan resources.
+ *
+ * @return VM cursor, or NULL when the plan is NULL.
+ */
+rnt_cursor_t rnt_vm_execute_plan(rnt_plan_t plan);
+
+/**
+ * @brief Advances a VM cursor and returns the next merged tuple as a kv string.
+ *
+ * Same encoding and return-value semantics as rnt_cursor_next.
+ *
+ * @param vm_cursor  Cursor returned by rnt_vm_execute_plan.
+ * @param tuple_out  Set to a heap-allocated kv string, or NULL when exhausted.
+ *                   Release with rnt_free_string() when non-NULL.
+ * @return 1 when a tuple was returned, 0 when exhausted, negative on error.
+ */
+int rnt_vm_cursor_next(rnt_cursor_t vm_cursor, char** tuple_out);
+
+/**
+ * @brief Closes a VM cursor, releases all plan nodes, cursors, and handles.
+ * @return 0 on success, negative on error.
+ */
+int rnt_vm_cursor_close(rnt_cursor_t vm_cursor);
+
+/* ------------------------------------------------------------------ */
+/* Memory management                                                    */
+/* ------------------------------------------------------------------ */
+
+/** @brief Releases a string allocated by the API. Safe to call with NULL. */
+void rnt_free_string(char* s);
+
+/** @brief Releases a byte buffer allocated by the API. Safe to call with NULL. */
+void rnt_free_bytes(uint8_t* p);
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/include/SqliteBackend.h b/include/SqliteBackend.h
index 0b21925..ce4e465 100644
--- a/include/SqliteBackend.h
+++ b/include/SqliteBackend.h
@@ -16,23 +16,13 @@
  *   kv(hash TEXT PRIMARY KEY, value BLOB NOT NULL)
  *     — content-addressed store; key is the SHA256 hex digest of value.
  *
- *   relation_index(path TEXT NOT NULL, tuple_hash TEXT NOT NULL,
- *                  UNIQUE(path, tuple_hash))
- *     — maps a relation's logical path to the ordered set of tuple hashes
- *       it contains. Corresponds to Sakura's per-relation B+ tree of
- *       tuple hashes stored in the physical layer.
+ * Relation membership is tracked by the Merkle B-tree maintained in-process.
+ * The former relation_index table has been removed; tuple hashes are looked up
+ * via Merkle::Page which reads only the KV store.
  */
 
 namespace nt
 {
-    /**
-     * @class SqliteBackend
-     * @brief IStorageBackend that persists data in a SQLite database.
-     *
-     * Constructed with a file path or ":memory:" for an in-process database.
-     * All KV values are opaque blobs; callers are responsible for serialization
-     * (see TupleCodec).
-     */
     class NT_API SqliteBackend : public IStorageBackend
     {
     public:
@@ -46,15 +36,8 @@ namespace nt
 
         std::string Put(std::vector<uint8_t> value) override;
         std::optional<std::vector<uint8_t>> Get(const std::string& hash) override;
-        void LinkTuple(const std::vector<std::string>& relation_path,
-                       const std::string& tuple_hash) override;
-        std::vector<std::string> TupleHashes(const std::vector<std::string>& relation_path,
-                                             std::size_t offset,
-                                             std::size_t limit) override;
 
     private:
         sqlite3* db_ = nullptr;
-
-        static std::string PathKey(const std::vector<std::string>& path);
     };
 }
diff --git a/include/Types.h b/include/Types.h
index 3e38829..f7eadff 100644
--- a/include/Types.h
+++ b/include/Types.h
@@ -24,7 +24,33 @@ enum OBJECT_TYPE {
      * a projected stored relation) or AlephZero (e.g. the eq builtin). The
      * object_type for this label must be an ephemeral_object_type.
      */
-    EPHEMERAL_RELATION
+    EPHEMERAL_RELATION,
+    /**
+     * A named mutable reference to a multigroup state, analogous to a git
+     * branch. A BRANCH object carries an opaque payload (serialized multigroup
+     * bytes) that the caller — in practice Sakura — deserializes on open.
+     *
+     * Branch objects are the entry point for database connections: a client
+     * opens a handle to /system/branches/<name>, reads the payload bytes to
+     * reconstruct the multigroup in memory, and holds the handle for the
+     * duration of the session.
+     *
+     * The `exclusive` flag on the object_type should be set to true so that
+     * LifecycleManager::Contention serializes concurrent writers.
+     */
+    BRANCH,
+    /**
+     * A named query plan stored in the object registry. A VIEW object carries
+     * the serialized plan definition and the multigroup hash at definition time.
+     * No handles to physical storage are kept open in the VIEW object itself.
+     * Each time the view is opened, fresh relation handles and cursors are
+     * created for the duration of that execution, then released on close.
+     *
+     * @todo Implement ObjectManager::View, rnt_register_view, and the
+     *       open-view path in HandlerManager. Views are reserved in the type
+     *       system but have no runtime support yet.
+     */
+    VIEW
 };
 
 /** @brief Operations that may be supported by an object type. */