Bài 63: Categories Tree CRUD — Adjacency List + Materialized Path

Sau bài học, bạn sẽ:

• Hiểu 4 cách model tree trong relational database: adjacency list, materialized path, nested set, closure table.
• So sánh trade-off mỗi cách theo trục read vs write performance, Postgres support, complexity implementation.
• Implement adjacency list + materialized path hybrid cho Shop API categories table.
• Dùng Postgres CTE recursive (WITH RECURSIVE + UNION ALL) query lấy subtree theo node root.
• Implement GET /api/v1/categories trả nested JSON tree dạng CategoryNode với children: Vec<CategoryNode> đệ quy.
• Implement POST /api/v1/categories với validate parent exists qua FK + transaction pattern compute path.
• Tạo bridge table product_categories (M:N) làm foundation cho endpoint assign categories ở B64.

Tree (cây) là cấu trúc phân cấp phổ biến: file system, category catalog, comment thread, org chart, BOM (bill of materials). Quan hệ RDBMS bản chất phẳng (table với row + column), cần pattern riêng để encode tree. 4 cách industry-standard:

Adjacency list — mỗi row có cột parent_id trỏ row cha (NULL = root). Đơn giản nhất, intuitive nhất với developer. Insert/update chỉ touch 1 row.

-- Adjacency list shape
id | parent_id | name
1  | NULL      | Electronics
2  | 1         | Smartphones
3  | 2         | iPhone
4  | 2         | Samsung

Vấn đề: lấy toàn bộ subtree (con cháu của 1 node) cần đệ quy. Postgres có CTE recursive (WITH RECURSIVE) giải quyết tốt; MySQL 8+ cũng có. SQLite cũ + MySQL 5.x không hỗ trợ — phải đệ quy ứng dụng N round-trip query.

Materialized path — mỗi row lưu chuỗi định danh tổ tiên trong cột TEXT, ví dụ "1.5.12" nghĩa là node id 12, parent id 5, grandparent id 1. Query subtree thành WHERE path LIKE '1.5.%' — index B-tree đủ tốc độ.

-- Materialized path shape
id | path     | name
1  | 1        | Electronics
2  | 1.2      | Smartphones
3  | 1.2.3    | iPhone
4  | 1.2.4    | Samsung

Vấn đề: đổi parent của 1 node trung gian → phải UPDATE path của toàn bộ subtree (vài chục đến hàng nghìn row tùy độ sâu). Insert chỉ tốn 2 statement (INSERT row + UPDATE path).

Nested set — mỗi row có 2 cột lft + rgt đánh số preorder traversal. Lấy subtree O(1) qua WHERE lft BETWEEN parent.lft AND parent.rgt. Vấn đề: insert/update phải relabel lft/rgt của nhiều row (toàn bộ row sau vị trí insert) — chi phí ghi cao, không phù hợp tree biến động.

Closure table — tạo bảng phụ ancestors(ancestor_id, descendant_id, depth) lưu mọi cặp ancestor-descendant cho mọi cấp độ. Query đủ loại (ancestor, descendant, sibling, depth filter) qua JOIN. Trade-off: storage tăng theo độ sâu × số node — worst case O(N²), insert tốn N statement (insert mọi cặp tới root).

Bảng so sánh nhanh:

Pattern              | Read   | Write  | Postgres support  | Complexity
Adjacency list       | Medium | Fast   | CTE recursive     | Low
Materialized path    | Fast   | Medium | LIKE / @>         | Low
Nested set           | Fast   | Slow   | Manual            | High
Closure table        | Fast   | Medium | JOIN              | Medium

Lock decision Shop API: dùng adjacency list + materialized path hybrid. Lý do cụ thể:

• parent_id adjacency giữ insert/update đơn giản 1 row, dễ hiểu cho developer mới onboard.
• path TEXT materialized cho phép query whole tree với ORDER BY path tree-sorted natural, sub-tree với WHERE path LIKE 'X.%' dùng index B-tree.
• Workload Shop API read-heavy (user browse catalog gấp 50-100 lần admin sửa category), redundant 2 field chấp nhận đổi lấy read performance.
• Compute path trong transaction lúc insert tránh inconsistency: INSERT row → lấy id auto-generated → UPDATE path = parent_path + "." + id cùng transaction.

Trade-off chính: 2 field redundant (parent_id + path) + chi phí maintain khi đổi parent (phải UPDATE path subtree). Workflow shop e-commerce hiếm khi re-parent category (admin tạo cây 1 lần, chỉnh trong vài tuần đầu, sau đó stable) — chi phí maintain hiếm khi kích hoạt.

Tạo migration thứ 8 trong workspace Shop API (7 migration đã có sau B62: products, products tags, orders, payments, products metadata, products soft delete, audit log):

sqlx migrate add --source crates/shop-db/migrations create_categories
# Creating crates/shop-db/migrations/20260615170000_create_categories.sql

Mở file SQL vừa tạo và viết schema:

-- File: crates/shop-db/migrations/20260615170000_create_categories.sql

CREATE TABLE categories (
    id BIGSERIAL PRIMARY KEY,
    parent_id BIGINT REFERENCES categories(id) ON DELETE RESTRICT,
    name TEXT NOT NULL,
    slug TEXT NOT NULL UNIQUE,
    path TEXT NOT NULL,                      -- materialized "1.5.12"
    depth INT NOT NULL DEFAULT 0,
    display_order INT NOT NULL DEFAULT 0,
    deleted_at TIMESTAMPTZ,                  -- soft delete pattern B62
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    updated_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Index materialized path cho query subtree + sort
CREATE INDEX categories_path_idx ON categories(path);

-- Index adjacency cho lookup children theo parent
CREATE INDEX categories_parent_idx ON categories(parent_id)
    WHERE deleted_at IS NULL;

-- Partial index active row (pattern lock B62 continued)
CREATE INDEX categories_active_idx ON categories(deleted_at)
    WHERE deleted_at IS NULL;

-- Trigger updated_at reuse function B62
CREATE TRIGGER categories_updated_at
    BEFORE UPDATE ON categories
    FOR EACH ROW
    EXECUTE FUNCTION update_updated_at_column();

-- Bridge table product ↔ category (M:N)
CREATE TABLE product_categories (
    product_id BIGINT NOT NULL
        REFERENCES products(id) ON DELETE CASCADE,
    category_id BIGINT NOT NULL
        REFERENCES categories(id) ON DELETE RESTRICT,
    created_at TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    PRIMARY KEY (product_id, category_id)
);

CREATE INDEX product_categories_category_idx
    ON product_categories(category_id);

Apply migration:

sqlx migrate run --source crates/shop-db/migrations
# Applied 20260615170000/migrate create_categories

8 quyết định lock vĩnh viễn từ schema này:

• parent_id BIGINT NULL — adjacency reference. NULL = root category, có giá trị = node con. FK self-reference với ON DELETE RESTRICT cấm xóa parent khi còn children (defense in depth ngoài check tại app layer).
• slug TEXT NOT NULL UNIQUE — natural key cho URL /api/v1/categories/{slug}, pattern reuse lock B51 (products slug). UNIQUE constraint defense conflict 409 qua From<sqlx::Error> mapping B55.
• path TEXT NOT NULL — materialized path dạng chuỗi id ngăn cách dấu chấm (1.5.12). Index B-tree riêng categories_path_idx phục vụ ORDER BY path tree-sorted natural + WHERE path LIKE 'X.%' subtree query.
• depth INT NOT NULL DEFAULT 0 — redundant (= số dấu chấm trong path), nhưng tiện sort + filter "chỉ lấy level 2" mà không cần parse path string trong SQL. Trade-off storage 4 bytes/row đổi lấy query đơn giản — đáng.
• display_order INT NOT NULL DEFAULT 0 — admin sort thủ công order các sibling trong cùng level (vd "Smartphones" hiển thị trước "Laptops" trong "Electronics"). Default 0 cho row mới.
• deleted_at TIMESTAMPTZ NULLABLE — soft delete pattern lock B62 reuse. Partial index categories_active_idx WHERE deleted_at IS NULL giảm size index.
• Trigger categories_updated_at reuse function update_updated_at_column() — đã tạo ở B62, không define lại. Bài học từ B62 pay off ngay: chỉ cần 1 dòng CREATE TRIGGER ... EXECUTE FUNCTION update_updated_at_column() cho mọi bảng có updated_at.
• Bridge product_categories — composite PK (product_id, category_id) guarantee 1 product không assign 2 lần cùng category. FK CASCADE product (xóa product xóa relation tự động) + FK RESTRICT category (cấm xóa category nếu còn product trỏ tới — bảo vệ analytics report lịch sử).

3 index cho bảng categories phục vụ 3 query pattern phổ biến: (a) categories_path_idx cho list whole tree ORDER BY path + subtree filter WHERE path LIKE 'X.%'; (b) categories_parent_idx cho lookup children "list các category con của parent X" qua WHERE parent_id = X; (c) categories_active_idx partial index active row pattern B62 lock. Bridge có 1 index phụ product_categories_category_idx cho query reverse "danh sách product thuộc category X" — composite PK đã cover query "categories của product X" theo thứ tự khóa.

PostgreSQL hỗ trợ Common Table Expression (CTE) recursive qua từ khóa WITH RECURSIVE. Cấu trúc gồm 2 phần ghép bằng UNION ALL: anchor (truy vấn cơ sở, không đệ quy) + recursive term (truy vấn đệ quy, tham chiếu chính CTE).

Lấy subtree của 1 node theo id (descendants + chính node):

WITH RECURSIVE category_tree AS (
    -- Anchor: node gốc theo id $1
    SELECT id, parent_id, name, slug, path, depth
    FROM categories
    WHERE id = $1 AND deleted_at IS NULL

    UNION ALL

    -- Recursive: con của các node đã thấy
    SELECT c.id, c.parent_id, c.name, c.slug, c.path, c.depth
    FROM categories c
    INNER JOIN category_tree ct ON c.parent_id = ct.id
    WHERE c.deleted_at IS NULL
)
SELECT * FROM category_tree
ORDER BY depth, display_order;

Lấy ancestors (đường đi từ node tới root) bằng materialized path approach (không cần đệ quy):

-- Tách chuỗi path "1.5.12" thành 3 id rồi JOIN
WITH path_parts AS (
    SELECT regexp_split_to_table($1, '\.')::BIGINT AS ancestor_id
)
SELECT c.*
FROM categories c
JOIN path_parts p ON c.id = p.ancestor_id
ORDER BY c.depth;

Lấy whole tree (mọi category active) — 2 cách:

-- Cách 1: CTE recursive xuất phát từ root
WITH RECURSIVE all_tree AS (
    SELECT id, parent_id, name, slug, path, depth
    FROM categories
    WHERE parent_id IS NULL AND deleted_at IS NULL

    UNION ALL

    SELECT c.id, c.parent_id, c.name, c.slug, c.path, c.depth
    FROM categories c
    INNER JOIN all_tree at ON c.parent_id = at.id
    WHERE c.deleted_at IS NULL
)
SELECT * FROM all_tree ORDER BY path;

-- Cách 2: ORDER BY path tự nhiên đã tree-sorted
SELECT id, parent_id, name, slug, path, depth, display_order
FROM categories
WHERE deleted_at IS NULL
ORDER BY path;

Lock pattern Shop API: dùng materialized path approach (cách 2) cho query whole tree — 1 query đơn giản với index categories_path_idx đã sort sẵn theo lexicographic order trên path string, kết quả trả về theo đúng thứ tự traversal cây (depth-first). Dùng CTE recursive cho query subtree theo node cụ thể — đáng dùng vì index path chỉ phục vụ tốt khi biết prefix exact, lookup descendant chính xác có CTE recursive là rõ ràng nhất.

Một pitfall của CTE recursive: nếu data có cycle (do bug hoặc thiếu cycle detection), UNION ALL sẽ chạy vô hạn cho đến khi Postgres hit work_mem limit và crash query. Phòng thủ qua cycle detection ở app layer mỗi lần đổi parent_id (xem Bước 7) + UNION thay UNION ALL (auto deduplicate) cho production critical query.

Tạo module mới crates/shop-db/src/categories.rs chứa CategoryRow + 3 function chính:

// File: crates/shop-db/src/categories.rs

use chrono::{DateTime, Utc};
use sqlx::PgPool;

#[derive(Debug, Clone, sqlx::FromRow)]
pub struct CategoryRow {
    pub id: i64,
    pub parent_id: Option<i64>,
    pub name: String,
    pub slug: String,
    pub path: String,
    pub depth: i32,
    pub display_order: i32,
    pub deleted_at: Option<DateTime<Utc>>,
    pub created_at: DateTime<Utc>,
    pub updated_at: DateTime<Utc>,
}

Function list whole tree dùng materialized path:

// File: crates/shop-db/src/categories.rs (extend)

pub async fn list_all_categories(
    pool: &PgPool,
) -> Result<Vec<CategoryRow>, sqlx::Error> {
    sqlx::query_as!(
        CategoryRow,
        r#"
        SELECT id, parent_id, name, slug, path, depth, display_order,
               deleted_at, created_at, updated_at
        FROM categories
        WHERE deleted_at IS NULL
        ORDER BY path
        "#,
    )
    .fetch_all(pool)
    .await
}

Function get subtree CTE recursive:

// File: crates/shop-db/src/categories.rs (extend)

pub async fn get_subtree(
    pool: &PgPool,
    root_id: i64,
) -> Result<Vec<CategoryRow>, sqlx::Error> {
    sqlx::query_as!(
        CategoryRow,
        r#"
        WITH RECURSIVE subtree AS (
            SELECT id, parent_id, name, slug, path, depth, display_order,
                   deleted_at, created_at, updated_at
            FROM categories
            WHERE id = $1 AND deleted_at IS NULL

            UNION ALL

            SELECT c.id, c.parent_id, c.name, c.slug, c.path, c.depth,
                   c.display_order, c.deleted_at, c.created_at, c.updated_at
            FROM categories c
            INNER JOIN subtree s ON c.parent_id = s.id
            WHERE c.deleted_at IS NULL
        )
        SELECT id, parent_id, name, slug, path, depth, display_order,
               deleted_at, created_at, updated_at
        FROM subtree
        ORDER BY path
        "#,
        root_id,
    )
    .fetch_all(pool)
    .await
}

Function create category với transaction pattern compute path atomic:

// File: crates/shop-db/src/categories.rs (extend)

pub async fn create_category(
    pool: &PgPool,
    parent_id: Option<i64>,
    name: &str,
    slug: &str,
) -> Result<CategoryRow, sqlx::Error> {
    let mut tx = pool.begin().await?;

    // Step 1 — fetch parent path + depth (NULL cho root)
    let (parent_path, parent_depth) = if let Some(pid) = parent_id {
        let parent = sqlx::query!(
            "SELECT path, depth FROM categories
             WHERE id = $1 AND deleted_at IS NULL",
            pid,
        )
        .fetch_optional(&mut *tx)
        .await?
        .ok_or(sqlx::Error::RowNotFound)?;
        (Some(parent.path), parent.depth)
    } else {
        (None, -1)
    };

    // Step 2 — INSERT row với path placeholder rỗng
    let row = sqlx::query_as!(
        CategoryRow,
        r#"
        INSERT INTO categories (parent_id, name, slug, path, depth)
        VALUES ($1, $2, $3, '', $4)
        RETURNING id, parent_id, name, slug, path, depth, display_order,
                  deleted_at, created_at, updated_at
        "#,
        parent_id,
        name,
        slug,
        parent_depth + 1,
    )
    .fetch_one(&mut *tx)
    .await?;

    // Step 3 — compute path = parent_path + "." + id (hoặc id nếu root)
    let new_path = match parent_path {
        Some(pp) => format!("{}.{}", pp, row.id),
        None => row.id.to_string(),
    };

    // Step 4 — UPDATE path bằng giá trị thật vừa compute
    let updated = sqlx::query_as!(
        CategoryRow,
        r#"
        UPDATE categories SET path = $1
        WHERE id = $2
        RETURNING id, parent_id, name, slug, path, depth, display_order,
                  deleted_at, created_at, updated_at
        "#,
        new_path,
        row.id,
    )
    .fetch_one(&mut *tx)
    .await?;

    tx.commit().await?;
    Ok(updated)
}

Wire module trong crates/shop-db/src/lib.rs:

// File: crates/shop-db/src/lib.rs (extend)
pub mod audit;
pub mod categories;     // ← NEW B63
pub mod orders;
pub mod payments;
pub mod pool;
pub mod products;

Pattern create_category 4 step transaction lock vĩnh viễn Shop API: insert với placeholder rỗng → fetch id auto-generated → compute path từ parent_path + "." + id → UPDATE path bằng giá trị thật → commit atomic. Nếu bất cứ step nào fail (parent không tồn tại, slug duplicate, ...) transaction tự rollback — không bao giờ có row với path rỗng leak ra DB.

Tạo DTO mới crates/shop-common/src/dto/category.rs:

// File: crates/shop-common/src/dto/category.rs

use serde::{Deserialize, Serialize};
use validator::Validate;

use super::CategoryId;

#[derive(Debug, Clone, Deserialize, Validate)]
pub struct CreateCategoryDto {
    #[validate(length(min = 1, max = 200,
        message = "tên category dài 1-200 ký tự"))]
    pub name: String,

    #[validate(regex(path = *super::SLUG_REGEX,
        message = "slug chỉ chứa chữ thường, số và dấu gạch ngang"))]
    pub slug: String,

    pub parent_id: Option<CategoryId>,
}

#[derive(Debug, Clone, Serialize)]
pub struct CategoryNode {
    pub id: CategoryId,
    pub parent_id: Option<CategoryId>,
    pub name: String,
    pub slug: String,
    pub depth: i32,
    pub display_order: i32,

    #[serde(skip_serializing_if = "Vec::is_empty")]
    pub children: Vec<CategoryNode>,
}

#[derive(Debug, Clone, Deserialize, Validate)]
pub struct AssignCategoriesDto {
    #[validate(length(min = 0, max = 20,
        message = "max 20 categories per product"))]
    pub category_ids: Vec<CategoryId>,
}

Wire module re-export trong crates/shop-common/src/dto/mod.rs:

// File: crates/shop-common/src/dto/mod.rs (extend)
pub mod category;      // ← NEW B63

pub use category::{
    AssignCategoriesDto, CategoryNode, CreateCategoryDto,
};

Tạo route file crates/shop-api/src/routes/categories.rs với 2 handler + helper build_tree:

// File: crates/shop-api/src/routes/categories.rs

use std::collections::HashMap;

use axum::extract::State;
use axum::routing::get;
use axum::{Json, Router};

use shop_common::dto::{CategoryId, CategoryNode, CreateCategoryDto};
use shop_common::error::AppError;
use shop_db::categories as db;

use crate::extractors::ValidatedJson;
use crate::responses::Created;
use crate::state::AppState;

pub async fn list_categories(
    State(state): State<AppState>,
) -> Result<Json<Vec<CategoryNode>>, AppError> {
    let rows = db::list_all_categories(&state.db).await?;
    let tree = build_tree(rows);
    Ok(Json(tree))
}

pub async fn create_category(
    State(state): State<AppState>,
    ValidatedJson(dto): ValidatedJson<CreateCategoryDto>,
) -> Result<Created<CategoryNode>, AppError> {
    let parent_id = dto.parent_id.map(|c| c.0 as i64);
    let row = db::create_category(
        &state.db,
        parent_id,
        &dto.name,
        &dto.slug,
    )
    .await?;

    let node = CategoryNode {
        id: CategoryId(row.id as u64),
        parent_id: row.parent_id.map(|p| CategoryId(p as u64)),
        name: row.name,
        slug: row.slug.clone(),
        depth: row.depth,
        display_order: row.display_order,
        children: Vec::new(),
    };

    Ok(Created {
        location: format!("/api/v1/categories/{}", row.slug),
        data: node,
    })
}

pub fn routes() -> Router<AppState> {
    Router::new()
        .route(
            "/categories",
            get(list_categories).post(create_category),
        )
}

Helper build_tree convert flat list từ DB thành nested CategoryNode. Thuật toán: HashMap key theo id, sort descending theo (depth, display_order), duyệt từ leaf lên — mỗi node remove khỏi map, nếu có parent thì insert vào children của parent, nếu không thì push vào danh sách root:

// File: crates/shop-api/src/routes/categories.rs (extend)

fn build_tree(rows: Vec<db::CategoryRow>) -> Vec<CategoryNode> {
    // Flat list rows → HashMap<id, CategoryNode>
    let mut nodes: HashMap<i64, CategoryNode> = rows
        .into_iter()
        .map(|r| {
            (
                r.id,
                CategoryNode {
                    id: CategoryId(r.id as u64),
                    parent_id: r.parent_id.map(|p| CategoryId(p as u64)),
                    name: r.name,
                    slug: r.slug,
                    depth: r.depth,
                    display_order: r.display_order,
                    children: Vec::new(),
                },
            )
        })
        .collect();

    // Sort id theo (depth, display_order) — duyệt từ leaf lên
    let mut keys: Vec<i64> = nodes.keys().copied().collect();
    keys.sort_by_key(|k| (nodes[k].depth, nodes[k].display_order));

    let mut roots: Vec<CategoryNode> = Vec::new();

    for key in keys.into_iter().rev() {
        let node = nodes.remove(&key).unwrap();
        match node.parent_id {
            Some(parent_id) => {
                if let Some(parent) = nodes.get_mut(&(parent_id.0 as i64))
                {
                    parent.children.insert(0, node);
                }
            }
            None => roots.push(node),
        }
    }

    roots.reverse();
    roots
}

Wire vào router trong crates/shop-api/src/router.rs:

// File: crates/shop-api/src/router.rs (extend)
let api_v1 = Router::new()
    .merge(routes::products::routes())
    .merge(routes::categories::routes());   // ← NEW B63

Wire module trong crates/shop-api/src/routes/mod.rs:

// File: crates/shop-api/src/routes/mod.rs (extend)
pub mod categories;    // ← NEW B63

Tree implementation phải defend 2 invariant cốt lõi:

• Parent tồn tại — parent_id phải trỏ vào row có thật và chưa soft deleted. FK self-reference đã defense (Postgres reject INSERT với 23503 foreign_key_violation), app layer thêm check deleted_at IS NULL trong query fetch parent (Bước 5 đã làm).
• Không cycle — không tồn tại đường A → B → ... → A. Create category mới không thể tạo cycle (node mới chưa có ai trỏ vào). Update parent_id mới là rủi ro: nếu chuyển category A làm con của descendant B của chính A, cây trở thành chu trình, CTE recursive crash.

Pattern cycle detection cho update parent (sẽ implement chi tiết B65):

// File: crates/shop-db/src/categories.rs (preview B65)

pub async fn update_parent(
    pool: &PgPool,
    category_id: i64,
    new_parent_id: Option<i64>,
) -> Result<(), CategoryError> {
    if let Some(npid) = new_parent_id {
        // Check new parent KHÔNG phải descendant của category hiện tại
        let is_desc = sqlx::query!(
            r#"
            WITH RECURSIVE subtree AS (
                SELECT id FROM categories WHERE id = $1
                UNION ALL
                SELECT c.id FROM categories c
                INNER JOIN subtree s ON c.parent_id = s.id
            )
            SELECT EXISTS(
                SELECT 1 FROM subtree WHERE id = $2
            ) AS "is_desc!"
            "#,
            category_id,
            npid,
        )
        .fetch_one(pool)
        .await?;

        if is_desc.is_desc {
            return Err(CategoryError::CycleDetected);
        }
    }

    // ... UPDATE parent_id + recompute path subtree (B65 deep)
    Ok(())
}

Lock pattern Shop API: cycle detection MANDATORY cho mọi endpoint update parent (B65 sẽ implement đầy đủ). Cách: query CTE recursive lấy subtree của category đang update, check EXISTS xem new parent có thuộc subtree không. Nếu có → reject với CategoryError::CycleDetected map sang 422 Validation envelope qua impl From<CategoryError> for AppError.

Khi đổi parent thành công, phải recompute path + depth của toàn bộ subtree (mọi node có path chứa prefix cũ). SQL pattern:

UPDATE categories
SET path = $new_prefix || SUBSTRING(path FROM LENGTH($old_prefix) + 1),
    depth = depth + ($new_depth - $old_depth)
WHERE path LIKE $old_prefix || '%';

Chi tiết phép tính prefix + transaction wrap sẽ ở B65 (update endpoint). B63 chỉ tạo nền tảng create + read.

Bảng product_categories đã tạo ở Bước 3 — bridge table M:N giữa products và categories. Endpoint assign categories cho product (chi tiết implement B64):

// File: crates/shop-api/src/routes/products.rs (preview B64)

// POST /api/v1/products/{slug}/categories
// Body: { "category_ids": [1, 5, 12] }
pub async fn assign_categories(
    State(state): State<AppState>,
    AppPath(slug): AppPath<String>,
    ValidatedJson(dto): ValidatedJson<AssignCategoriesDto>,
) -> Result<NoContent, AppError> {
    // Implementation B64 — transaction wrap 3 step:
    // 1. DELETE FROM product_categories WHERE product_id = $1
    // 2. INSERT batch new category_ids
    // 3. audit::log_action với action = "update_categories"
    Ok(NoContent)
}

DTO đã define ở Bước 6 (AssignCategoriesDto với category_ids: Vec<CategoryId>) với validate length(max = 20):

// Đã define Bước 6
#[derive(Debug, Clone, Deserialize, Validate)]
pub struct AssignCategoriesDto {
    #[validate(length(min = 0, max = 20))]
    pub category_ids: Vec<CategoryId>,
}

Implementation pattern transaction 3 step (B64 deep):

1. Resolve product theo slug, lấy product.id (lock B62 reuse find_by_slug false exclude soft deleted).
2. DELETE mọi row hiện có trong product_categories theo product_id — clean slate trước khi assign mới.
3. INSERT batch category_ids mới (loop hoặc UNNEST array).
4. Audit log action update_categories với changes JSONB ghi {"old": [...], "new": [...]}.
5. Commit atomic — assign + audit cùng commit hoặc cùng rollback.

Lock decision Shop API: max 20 categories per product qua validate length(max = 20). Lý do: catalog UX thực tế ít khi cần product thuộc >5 category (1 chính + vài cross-listing); cap 20 là hard limit chống abuse + giữ JSON payload nhỏ + giảm load JOIN product_categories ở list query.

Decision FK strategy bridge product_categories:

• FK products CASCADE — xóa product (hard delete admin operation hoặc cleanup script) tự xóa relation. Logic relation không tồn tại độc lập với product.
• FK categories RESTRICT — cấm xóa category nếu còn product assigned. Admin phải reassign products sang category khác trước khi xóa — bảo vệ accidental data loss.
• Composite PK (product_id, category_id) — guarantee 1 cặp không xuất hiện 2 lần (idempotent assign).

Apply migration + start service:

sqlx migrate run --source crates/shop-db/migrations
# Applied 20260615170000/migrate create_categories

cargo sqlx prepare --workspace
# query data written to .sqlx in the current directory

AUTO_MIGRATE=true cargo run -p shop-api
# shop-api listening on 0.0.0.0:3000

Test flow tạo cây 3 cấp:

# Tạo root category
curl -X POST http://localhost:3000/api/v1/categories \
  -H 'Content-Type: application/json' \
  -d '{"name":"Electronics","slug":"electronics"}'
# 201 Created
# { "id": 1, "parent_id": null, "name": "Electronics",
#   "slug": "electronics", "depth": 0, "display_order": 0,
#   "children": [] }

# Tạo child level 1
curl -X POST http://localhost:3000/api/v1/categories \
  -H 'Content-Type: application/json' \
  -d '{"name":"Smartphones","slug":"smartphones","parent_id":1}'
# 201 Created
# { "id": 2, "parent_id": 1, "depth": 1, ... }

# Tạo grandchild level 2
curl -X POST http://localhost:3000/api/v1/categories \
  -H 'Content-Type: application/json' \
  -d '{"name":"iPhone","slug":"iphone","parent_id":2}'
# 201 Created
# { "id": 3, "parent_id": 2, "depth": 2, ... }

# List tree nested
curl http://localhost:3000/api/v1/categories | jq

Response JSON nested tree:

[
  {
    "id": 1,
    "parent_id": null,
    "name": "Electronics",
    "slug": "electronics",
    "depth": 0,
    "display_order": 0,
    "children": [
      {
        "id": 2,
        "parent_id": 1,
        "name": "Smartphones",
        "slug": "smartphones",
        "depth": 1,
        "display_order": 0,
        "children": [
          {
            "id": 3,
            "parent_id": 2,
            "name": "iPhone",
            "slug": "iphone",
            "depth": 2,
            "display_order": 0
          }
        ]
      }
    ]
  }
]

Verify materialized path đã compute đúng trong DB:

docker compose exec postgres psql -U shop -d shop_dev -c \
  "SELECT id, name, path, depth
   FROM categories
   ORDER BY path;"
#  id |    name     |  path  | depth
# ----+-------------+--------+-------
#   1 | Electronics | 1      |     0
#   2 | Smartphones | 1.2    |     1
#   3 | iPhone      | 1.2.3  |     2

Verify constraint FK self-reference RESTRICT khi xóa category còn children (hard delete cho test, soft delete đã có sẵn từ B62):

docker compose exec postgres psql -U shop -d shop_dev -c \
  "DELETE FROM categories WHERE id = 1;"
# ERROR:  update or delete on table "categories" violates foreign key
# constraint "categories_parent_id_fkey" on table "categories"
# DETAIL:  Key (id)=(1) is still referenced from table "categories".

Suggested commit khi mọi bước verify pass: B63: categories tree adjacency + materialized path + CTE recursive.

• 4 cách model tree RDBMS: adjacency list (parent_id), materialized path (path TEXT), nested set (lft/rgt), closure table (ancestor-descendant bridge).
• Shop API hybrid lock: adjacency parent_id + materialized path TEXT — 2 field redundant nhưng đổi lấy read performance cho workload catalog read-heavy.
• Migration 8 create_categories: bảng categories 10 cột + 3 index (path, parent partial, active partial) + trigger updated_at reuse function B62 + bridge product_categories M:N 3 cột với composite PK.
• FK strategy: categories.parent_id self-ref RESTRICT (cấm xóa parent còn children); product_categories.product_id CASCADE; product_categories.category_id RESTRICT.
• CTE recursive Postgres (WITH RECURSIVE + UNION ALL) cho query subtree theo node — anchor + recursive term JOIN tới chính CTE.
• ORDER BY path tree-sorted natural — query whole tree không cần CTE recursive, materialized path advantage thuần.
• create_category transaction pattern 4 step: fetch parent → INSERT placeholder path → compute path = parent_path + "." + id → UPDATE path bằng giá trị thật → commit atomic.
• build_tree helper Rust: flat list → nested CategoryNode qua HashMap sort theo (depth, display_order) duyệt leaf-up insert vào children của parent.
• Cycle detection MANDATORY cho mọi update parent (B65 deep) — pattern CTE recursive subtree + EXISTS subquery reject 422 khi new parent ∈ subtree.
• Bridge product_categories M:N với composite PK (product_id, category_id) + max 20 categories/product validate constraint (preview B64 endpoint assign).
• File path lock: crates/shop-db/src/categories.rs, crates/shop-common/src/dto/category.rs, crates/shop-api/src/routes/categories.rs.
• Foundation cho B64 (assign endpoint M:N + GET products by category filter), B65 (update parent + cycle detection deep + path recompute subtree), B112 (admin auth gate write endpoint).

Tự trả lời, đáp án ở cuối:

1. 4 cách model tree (adjacency list, materialized path, nested set, closure table) — pros/cons mỗi cách theo trục read/write? Shop API chọn hybrid nào và lý do.
2. Materialized path path TEXT lưu chuỗi "1.5.12" — query subtree dùng operator gì? So sánh hiệu năng với CTE recursive adjacency list.
3. CTE recursive Postgres — pattern WITH RECURSIVE + UNION ALL ra sao? Cho ví dụ get_subtree. Pitfall khi data có cycle là gì.
4. create_category cần 2 SQL statement (INSERT row + UPDATE path) — tại sao transaction MANDATORY? Hậu quả nếu thiếu transaction là gì.
5. Cycle detection update parent_id — tại sao MANDATORY? Cho ví dụ scenario cụ thể tạo cycle và pattern CTE EXISTS reject 422.

Bài 64: Products ↔ Categories M:N Relation — chi tiết assign/unassign categories cho product qua bridge table product_categories, GET products by category với subtree filter dùng materialized path LIKE prefix, query optimization với JOIN + index, áp Shop API products-categories bridge endpoint hoàn chỉnh.