การเดินผ่านต้นไม้หมวดหมู่

ต้นไม้หมวดหมู่คืออะไร

CREATE TABLE categories (
  id       INT PRIMARY KEY,
  name     VARCHAR(100) NOT NULL,
  parent_id INT REFERENCES categories(id)
);

ข้อมูลหมวดหมู่ตัวอย่าง

INSERT INTO categories (id, name, parent_id) VALUES
  (1, 'Electronics',   NULL),
  (2, 'Phones',         1),
  (3, 'Laptops',        1),
  (4, 'Smartphones',    2),
  (5, 'Feature Phones', 2),
  (6, 'Gaming Laptops', 3),
  (7, 'Ultrabooks',     3);

ปัญหาของคิวรีแบบง่าย

-- This only shows direct children of Electronics (level 1)
SELECT id, name
FROM   categories
WHERE  parent_id = 1;

โครงสร้างของ WITH RECURSIVE

WITH RECURSIVE cte AS (
  -- Anchor: starting rows
  SELECT ...
  UNION ALL
  -- Recursive: join cte to base table
  SELECT ... FROM base_table JOIN cte ON ...
)
SELECT * FROM cte;

เดินสำรวจต้นไม้ทั้งหมดจากราก

WITH RECURSIVE category_tree AS (
  -- Anchor: root nodes
  SELECT id, name, parent_id, 1 AS depth
  FROM   categories
  WHERE  parent_id IS NULL

  UNION ALL

  -- Recursive: children of current level
  SELECT c.id, c.name, c.parent_id, ct.depth + 1
  FROM   categories      c
  JOIN   category_tree   ct ON ct.id = c.parent_id
)
SELECT id, name, depth
FROM   category_tree
ORDER  BY depth, id;

การติดตามเส้นทาง

WITH RECURSIVE category_tree AS (
  SELECT id, name, parent_id,
         name AS path
  FROM   categories
  WHERE  parent_id IS NULL

  UNION ALL

  SELECT c.id, c.name, c.parent_id,
         ct.path || ' / ' || c.name
  FROM   categories    c
  JOIN   category_tree ct ON ct.id = c.parent_id
)
SELECT id, name, path
FROM   category_tree
ORDER  BY path;

เริ่มจากโหนดที่ระบุ

WITH RECURSIVE subtree AS (
  SELECT id, name, parent_id, 0 AS depth
  FROM   categories
  WHERE  id = 2          -- start at Phones

  UNION ALL

  SELECT c.id, c.name, c.parent_id, s.depth + 1
  FROM   categories c
  JOIN   subtree    s ON s.id = c.parent_id
)
SELECT id, name, depth
FROM   subtree
ORDER  BY depth, id;

เดินสำรวจขึ้นด้านบน: ค้นหาบรรพบุรุษทั้งหมด

WITH RECURSIVE ancestors AS (
  SELECT id, name, parent_id
  FROM   categories
  WHERE  id = 4          -- start at Smartphones

  UNION ALL

  SELECT c.id, c.name, c.parent_id
  FROM   categories c
  JOIN   ancestors  a ON a.parent_id = c.id
)
SELECT id, name
FROM   ancestors
ORDER  BY id;

เพิ่มการแสดงผลแบบเยื้อง

WITH RECURSIVE category_tree AS (
  SELECT id, name, parent_id, 0 AS depth
  FROM   categories
  WHERE  parent_id IS NULL

  UNION ALL

  SELECT c.id, c.name, c.parent_id, ct.depth + 1
  FROM   categories    c
  JOIN   category_tree ct ON ct.id = c.parent_id
)
SELECT
  REPEAT('    ', depth) || name AS indented_name,
  depth
FROM   category_tree
ORDER  BY path;

ป้องกันวงวนไม่สิ้นสุด

WITH RECURSIVE safe_tree AS (
  SELECT id, name, parent_id,
         ARRAY[id] AS visited
  FROM   categories
  WHERE  parent_id IS NULL

  UNION ALL

  SELECT c.id, c.name, c.parent_id,
         st.visited || c.id
  FROM   categories c
  JOIN   safe_tree  st ON st.id = c.parent_id
  WHERE  c.id <> ALL(st.visited)   -- stop if already seen
)
SELECT id, name FROM safe_tree;

นับลูกหลานของแต่ละโหนด

WITH RECURSIVE category_tree AS (
  SELECT id, name, parent_id, id AS root_id
  FROM   categories
  WHERE  parent_id IS NULL

  UNION ALL

  SELECT c.id, c.name, c.parent_id, ct.root_id
  FROM   categories    c
  JOIN   category_tree ct ON ct.id = c.parent_id
)
SELECT
  root_id,
  COUNT(*) - 1 AS descendant_count
FROM   category_tree
GROUP  BY root_id
ORDER  BY root_id;

ตรวจสอบความเข้าใจ

ทบทวนบทเรียน