การสืบค้นแบบเรียกซ้ำ (WITH RECURSIVE): ลำดับชั้นและกราฟ

ท่องผ่านต้นไม้และกราฟด้วย WITH RECURSIVE พร้อมเชี่ยวชาญการวัดความลึกและการตรวจจับวัฏจักร

11 นาที · 3 คำถาม

CTE แบบเรียกซ้ำ (recursive CTE) ประกอบด้วยสองส่วนที่เชื่อมกันด้วย UNION ALL: พจน์ตั้งต้น (anchor term) ที่ให้แถวเริ่มต้น และ พจน์เรียกซ้ำ (recursive term) ที่อ้างอิงถึงตัว CTE เอง SQLite จะรันพจน์ตั้งต้นหนึ่งครั้ง จากนั้นนำพจน์เรียกซ้ำมาวนซ้ำบนแถวใหม่ ๆ จนกระทั่งไม่มีแถวใหม่เกิดขึ้น มาสร้างลำดับชั้นของผู้จัดการเพื่อแสดงให้เห็นกัน

CREATE TABLE employees (
  id INTEGER PRIMARY KEY,
  name TEXT NOT NULL,
  manager_id INTEGER
);

INSERT INTO employees (id, name, manager_id)
VALUES
  (1, 'Ada',    NULL),
  (2, 'Grace',  1),
  (3, 'Alan',   2),
  (4, 'Edsger', 2);

ในการคลี่แผนผังองค์กรใต้ Ada พจน์ตั้งต้นจะเลือกโหนดรากด้วยความลึก 0 และพจน์เรียกซ้ำจะเชื่อมพนักงานแต่ละคนเข้ากับผู้จัดการของตนที่มีอยู่แล้วใน CTE พร้อมเพิ่มค่าความลึกทีละหนึ่ง คอลัมน์ depth ที่คุณคำนวณเองคือวิธีที่ง่ายที่สุดในการวัดระดับต่าง ๆ ของลำดับชั้น

WITH RECURSIVE chain(id, name, depth) AS (
  SELECT id, name, 0
  FROM employees
  WHERE id = 1
  UNION ALL
  SELECT e.id, e.name, c.depth + 1
  FROM employees e
  JOIN chain c ON e.manager_id = c.id
)
SELECT id, name, depth FROM chain;

กราฟ (graph) จำลองด้วยตารางเส้นเชื่อม (src, dst) การท่องผ่านใช้กลไกเดียวกัน แต่กราฟอาจมี วัฏจักร (cycle) ได้: การตาม 1 -> 2 -> 3 -> 1 จะวนไม่รู้จบ วิธีแก้คือจดจำ เส้นทางที่ท่องผ่านมาแล้ว ไว้ในคอลัมน์ข้อความ และปฏิเสธโหนดใด ๆ ที่เคยเยือนแล้ว ฟังก์ชัน instr จะมองหาโหนดที่อยู่ระหว่างจุดสองจุดภายในเส้นทางนั้น

CREATE TABLE edges (
  src INTEGER NOT NULL,
  dst INTEGER NOT NULL
);

INSERT INTO edges (src, dst) VALUES
  (1, 2), (2, 3), (3, 1), (2, 4);

WITH RECURSIVE walk(node, path) AS (
  SELECT 1, '.1.'
  UNION ALL
  SELECT e.dst,
         w.path || e.dst || '.'
  FROM edges e
  JOIN walk w ON e.src = w.node
  WHERE instr(w.path, '.' || e.dst || '.') = 0
)
SELECT node, path FROM walk;

ทดสอบความรู้

ตรวจสอบว่าคุณจำประเด็นสำคัญของบทเรียนนี้ได้ครบถ้วน

1. ใน CTE แบบเรียกซ้ำ ตัวดำเนินการใดที่เชื่อมพจน์ตั้งต้นเข้ากับพจน์เรียกซ้ำ?
   • UNION ALL (หรือ UNION)
   • JOIN
   • INTERSECT
   • CROSS APPLY
2. เหตุใดกราฟที่มีวัฏจักรจึงเสี่ยงต่อการเรียกซ้ำไม่รู้จบเมื่อใช้ UNION ALL?
   • เพราะ UNION ALL เรียงลำดับผลลัพธ์อย่างเป็นระบบ
   • เพราะโหนดเดิม ๆ ถูกเยือนซ้ำโดยไม่มีการกำจัดตัวซ้ำ
   • เพราะ SQLite ปิดใช้งานดัชนีระหว่างการเรียกซ้ำ
   • เพราะพจน์ตั้งต้นถูกประเมินใหม่ในทุกรอบ
3. คุณจะหลีกเลี่ยงลูปไม่รู้จบเมื่อท่องผ่านกราฟที่มีวัฏจักรใน SQLite ได้อย่างไร?
   • เพิ่ม ORDER BY ในพจน์เรียกซ้ำ
   • จดจำเส้นทางที่ท่องผ่านมาแล้วและคัดโหนดที่เคยเยือนออก
   • ใช้ประโยค CYCLE มาตรฐาน
   • เพิ่มขนาดแคชในหน่วยความจำ