restaurant/docs/adr-0001-menu-tree.md

ADR 0001 — Menu storage: adjacency list with materialized path

Status: Accepted Date: 2026-04-29 Supersedes: initial scaffold's flat categories + subcategories model.

Context

Real restaurant menus are nested: Drinks → Hot Beverages → Coffee-based → Espressos. The initial scaffold pinned a fixed two-level shape (categories + subcategories tables). That was a transcription of the LNbits "category + subcategory" idiom rather than a real data-model decision. The legacy Atitlan.io project we're carrying forward already used a self-FK tree (Category.parentId in Atitlan.io/Legacy/server-fastify/prisma/schema.prisma).

We also need:

• Items attaching to any node, not just leaves (a "Drinks" node can carry both children and its own items).
• A small maximum depth so the UI stays navigable (we picked 4 levels — root → kid → grandkid → great-grandkid).
• Cheap "subtree of X" reads (the customer webapp asks for an entire menu in one round trip).
• Cheap "move subtree" writes (operators reorganize menus).
• Cheap cycle + depth validation on move.
• Identical behavior on SQLite + Postgres, which LNbits both support.

Decision

Store the tree as an adjacency list (parent_id self-FK) plus denormalized materialized path (path TEXT, '/'-separated node ids) and depth (INTEGER, 0..3).

Indexes: (restaurant_id), (parent_id), (path).

menu_nodes
├── id              TEXT PK
├── restaurant_id   TEXT
├── parent_id       TEXT NULL  -- NULL = root of restaurant
├── name            TEXT
├── description     TEXT
├── sort_order      INTEGER
├── image_url       TEXT
├── depth           INTEGER    -- 0..3
├── path            TEXT       -- 'rootid' or 'rootid/childid/...'
└── time            TIMESTAMP

Menu items get node_id (replacing category_id + subcategory_id). MenuItem.node_id is Optional in the persisted shape (orphans allowed when a parent is deleted with cascade=False); the CreateMenuItem request body requires it (newly-created items must land somewhere).

What this gives us

Operation	Cost
Children of node X	WHERE parent_id = X — index hit
Subtree of node X	WHERE path LIKE X.path || '%' — index hit
Ancestors of node X	split path into ids, fetch by id (≤4)
Cycle check on move	node_id in new_parent.path.split('/') — O(depth)
Max-depth check on create / move	compare integers — O(1)
Move subtree (rewrite paths)	one UPDATE … SET path = new_prefix || SUBSTR(path, len(old)+1)
Build full tree	one SELECT * ordered by (depth, sort_order), assemble in O(n) Python

For the realistic scale (5–50 nodes per restaurant, depth ≤ 4), the "build full tree" pass takes microseconds. We never reach for recursive CTEs.

Alternatives considered

Closure table

A separate menu_node_paths table holding every (ancestor, descendant) pair. Best read characteristics for very deep trees with thousands of nodes — cheap descendant queries via a single join, no string matching. Rejected because:

• Maintenance overhead. Every insert writes one row per ancestor; every move deletes and rewrites the entire subtree's rows; every delete is a fan-out. At our scale (depth ≤ 4) this is pure overhead.
• Two sources of truth. The closure table can drift from parent_id on bugs. We'd have to test and lock both.
• No real win. Subtree queries on the path column are already index-backed and fast at this scale.

We'd revisit if a single instance ever hosted thousands of nodes per restaurant. Today it doesn't.

Postgres ltree

A first-class materialized-path type with GiST indexes. Lovely on Postgres. Rejected because LNbits also supports SQLite, which has no ltree. We don't want a per-backend code path.

A path TEXT column gives us the same query shape (LIKE prefix || '%') on both backends. If a deployment ever wanted GiST-indexed performance, an opt-in migration to ltree could be added later without changing the model API.

Pure adjacency list (no path / no depth)

Keep parent_id, drop the denormalized columns. Subtree queries require recursive CTEs (Postgres + SQLite both support them). Rejected because:

• Recursive CTE syntax is almost identical between SQLite and Postgres but not quite, and writing portable migrations becomes fiddly.
• Cycle detection on move requires walking with another CTE.
• Move's path rewrite isn't a single statement; you'd have to recompute every descendant's depth in app code.

The denormalized columns are cheap (one path: TEXT, one depth: INT per node) and remove all of these papercuts.

Nested set (lft / rgt)

Optimal subtree reads, terrible writes (every insert / move shifts half the tree's lft/rgt values). Rejected as obviously wrong-shaped for an interactive CMS where operators reorganize menus often.

Consequences

• Operators can build menus of any shape up to 4 levels, with items attachable at any depth.
• Subtree moves are a single SQL statement.
• The CMS uses Quasar's q-tree directly off the hydrated tree returned by GET /api/v1/restaurants/{id}/menu.
• Items can be orphaned (their node_id is nullable). The CMS UI surfaces orphans as "unfiled" so operators can re-home them.
• Nostr listings (NIP-99 kind 30402) carry one t tag per ancestor name (slugified, root-first). Renaming a node re-publishes every item in its subtree so the new tag set lands.

Migration

m002_menu_tree (shipped) backfills menu_nodes from the prior categories + subcategories tables, then drops them. See migrations.py for the SQL.