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.