ตาราง Closure สำหรับคำนวณความสัมพันธ์

การค้นหาความสัมพันธ์ในครอบครัวดูเหมือนง่าย แต่คำถามว่า “สองคนนี้เป็นญาติกันไหม” “เชื่อมโยงกันผ่านความสัมพันธ์กี่ขั้น” หรือ “บรรพบุรุษร่วมที่ใกล้ที่สุดคือใคร” มีต้นทุนสูงเมื่อเก็บข้อมูลแบบรายการความสัมพันธ์โดยตรง (adjacency list) ซึ่งแต่ละแถวบันทึกเพียงคู่พ่อแม่กับลูก การตอบต้องไล่โครงสร้างต้นไม้แบบเรียกซ้ำ ใน SQL จึงใช้ recursive CTE ซึ่งให้คำตอบถูกต้องแต่ช้าเมื่อโครงสร้างลึกและนำมาประกอบกันได้ยาก

ตารางความสัมพันธ์แบบครบทุกเส้นทาง (closure table) แก้ปัญหาด้วยการคำนวณและเก็บความสัมพันธ์ทุกเส้นทางไว้ล่วงหน้า โดยบันทึกทุกคู่บรรพบุรุษกับลูกหลานพร้อมความลึกตั้งแต่ตอนเขียนข้อมูล ทำให้อ่านเร็วขึ้นมากโดยแลกกับการเขียนที่ซับซ้อนขึ้น สำหรับแอปผังเครือญาติที่อ่านบ่อยกว่าเขียนมาก ข้อแลกเปลี่ยนนี้แทบจะเหมาะสมเสมอ

ปัญหาของ adjacency list

วิธีมาตรฐานในการเก็บต้นไม้ในฐานข้อมูลเชิงสัมพันธ์คือ adjacency list ซึ่งเป็นตารางที่แต่ละแถวมี id และ parent_id เข้าใจง่ายและเขียนข้อมูลง่าย การเพิ่มคนใหม่ใช้เพียงแถวเดียว การเปลี่ยนความสัมพันธ์กับพ่อแม่ใช้การอัปเดตครั้งเดียว

แต่การตอบคำถามว่า “บรรพบุรุษทั้งหมดของบุคคล X คือใคร” ต้องไล่ย้อนขึ้นไปในต้นไม้แบบเรียกซ้ำ ใน PostgreSQL และฐานข้อมูล SQL สมัยใหม่ส่วนใหญ่ ใช้ recursive CTE ดังนี้:

WITH RECURSIVE ancestors AS (
  SELECT id, parent_id, 0 AS depth
  FROM people
  WHERE id = :person_id

  UNION ALL

  SELECT p.id, p.parent_id, a.depth + 1
  FROM people p
  JOIN ancestors a ON p.id = a.parent_id
)
SELECT * FROM ancestors;

วิธีนี้ใช้ได้ แต่ในโครงสร้างที่ลึก recursive CTE จะสแกนแถวในแต่ละระดับ ต้นทุนจึงเพิ่มตามความลึก สำหรับโครงสร้างตื้นที่มีสามหรือสี่รุ่น วิธีนี้เร็วพอ แต่เมื่อครอบคลุมสิบหรือสิบห้ารุ่นและมีหลายร้อยโหนด ประสิทธิภาพจะลดลงชัดเจน ยิ่งกว่านั้น การประกอบ recursive CTE สองชุดเพื่อตอบคำถามอย่าง “หาบรรพบุรุษร่วมของ X กับ Y” ต้องเรียกซ้ำทั้งสองชุดแล้วเชื่อมผลลัพธ์ ทำให้ต้นทุนเพิ่มอีก

โครงสร้างของ closure table

closure table เป็นตารางที่เพิ่มเข้ามาคู่กับตารางบุคคลหลัก แต่ละแถวระบุความสัมพันธ์ที่มีเส้นทางเชื่อมถึงกัน โดยเก็บคู่ (ancestor_id, descendant_id) พร้อมความลึก ซึ่งเป็นจำนวนเส้นเชื่อมระหว่างทั้งคู่ แต่ละคนยังเป็นบรรพบุรุษของตนเองที่ความลึกศูนย์ด้วย ตัวอย่างในบทความนี้สมมติว่าโครงสร้างเป็นต้นไม้อย่างเคร่งครัด โดยแต่ละคนมีพ่อหรือแม่ที่บันทึกไว้ไม่เกินหนึ่งคน ดังนั้นบรรพบุรุษกับลูกหลานแต่ละคู่จึงมีเส้นทางและความลึกเพียงค่าเดียว ผังเครือญาติจริงที่บันทึกทั้งพ่อและแม่ของแต่ละคน หรือเข้าถึงบรรพบุรุษคนเดียวกันผ่านหลายสาย ต้องใช้สคีมา (โครงสร้างข้อมูล) ที่ขยายเพิ่มเติม เช่น เก็บหนึ่งแถวต่อเส้นทาง หรือเก็บความลึกต่ำสุดของแต่ละคู่ และคิวรี LCA จะคืนค่าบรรพบุรุษร่วมที่ใกล้ที่สุดหนึ่งคนจากที่อาจมีหลายคน เช่น คนหนึ่งในคู่สามีภรรยาที่เป็นบรรพบุรุษ

CREATE TABLE family_closure (
  ancestor_id   INTEGER NOT NULL REFERENCES people(id),
  descendant_id INTEGER NOT NULL REFERENCES people(id),
  depth         INTEGER NOT NULL,
  PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX idx_closure_descendant ON family_closure (descendant_id);
CREATE INDEX idx_closure_ancestor   ON family_closure (ancestor_id);

เมื่อ X ไม่มีพ่อแม่ จะเพิ่มแถวเดียวคือ (X, X, 0) เมื่อเพิ่ม X เป็นลูกของ P ต้องเพิ่มบรรพบุรุษทั้งหมดของ P ให้ X ด้วย:

-- Self-reference
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
VALUES (:x_id, :x_id, 0);

-- All ancestors of parent P become ancestors of X, at depth + 1
INSERT INTO family_closure (ancestor_id, descendant_id, depth)
SELECT ancestor_id, :x_id, depth + 1
FROM family_closure
WHERE descendant_id = :parent_id;

การเพิ่มบุคคลที่ระดับรุ่นลึก N จึงต้องเพิ่ม N+1 แถวใน closure table สำหรับผังเครือญาติทั่วไปที่ความลึกไม่ค่อยเกิน 15 หรือ 20 รุ่น ภาระนี้จัดการได้ ต้นทุนการเขียนเพิ่มตามความลึก ไม่ใช่ขนาดรวมของต้นไม้

การค้นหาบรรพบุรุษทั้งหมด

เมื่อมี closure table แล้ว การหาบรรพบุรุษทั้งหมดของบุคคลใช้การเชื่อมตารางครั้งเดียวโดยไม่ต้องเรียกซ้ำ:

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.ancestor_id
WHERE fc.descendant_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

คิวรีนี้สามารถทำงานด้วยการสแกนดัชนี descendant_id ครั้งเดียว ต้นทุนเพิ่มตามจำนวนบรรพบุรุษ ไม่ใช่ความลึกของต้นไม้ สำหรับความลึกของผังเครือญาติทั่วไป โดยทั่วไปคิวรีนี้เร็วกว่า recursive CTE ที่ให้ผลเดียวกันมาก และความแตกต่างจะเพิ่มเมื่อโครงสร้างลึกขึ้น

คิวรีฝั่งตรงข้าม คือการหาลูกหลานทั้งหมดของบุคคล ใช้รูปแบบเดียวกันกับดัชนี ancestor_id:

SELECT p.*, fc.depth
FROM family_closure fc
JOIN people p ON p.id = fc.descendant_id
WHERE fc.ancestor_id = :person_id
  AND fc.depth > 0
ORDER BY fc.depth;

บรรพบุรุษร่วมที่ใกล้ที่สุด

บรรพบุรุษร่วมที่ใกล้ที่สุด หรือ Lowest Common Ancestor (LCA) คือบรรพบุรุษร่วมรุ่นล่าสุดของคนสองคน ในผังเครือญาติ นี่คือคำตอบของคำถามว่า “บรรพบุรุษร่วมรุ่นล่าสุดของสองคนนี้คือใคร” อาจเป็นปู่ย่าตายาย บรรพบุรุษรุ่นก่อนหน้า หรือไกลกว่านั้น ขึ้นอยู่กับความสัมพันธ์

เมื่อใช้ closure table คิวรี LCA จะเชื่อมชุดบรรพบุรุษของทั้งสองคน กรองเฉพาะบรรพบุรุษร่วม แล้วเรียงตามความลึกเพื่อหาคนที่ใกล้ที่สุด:

SELECT a.ancestor_id, a.depth + b.depth AS total_distance
FROM family_closure a
JOIN family_closure b ON a.ancestor_id = b.ancestor_id
WHERE a.descendant_id = :person_a
  AND b.descendant_id = :person_b
ORDER BY total_distance ASC
LIMIT 1;

ผลคือบรรพบุรุษร่วมที่มีระยะรวมจากทั้งสองคนสั้นที่สุด คิวรีสแกนดัชนี descendant_id สองครั้งและทำงานในระดับมิลลิวินาทีแม้ต้นไม้มีขนาดค่อนข้างใหญ่ ไม่ต้องเรียกซ้ำ ไล่ต้นไม้หลายรอบ หรือสร้างชุดบรรพบุรุษชั่วคราวนอกเหนือจากที่ดัชนีให้มา

คิวรีนี้ยังรองรับกรณีที่คนหนึ่งเป็นบรรพบุรุษของอีกคนโดยธรรมชาติ หาก A เป็นบรรพบุรุษโดยตรงของ B บรรพบุรุษร่วมที่ใกล้ที่สุดคือ A เอง และคิวรีให้ผลถูกต้องเพราะ A อยู่ในชุดบรรพบุรุษของตนเองที่ความลึก 0

จำนวนขั้นของความสัมพันธ์

จำนวนขั้นของความสัมพันธ์ระหว่างคนสองคนคือจำนวนเส้นเชื่อมในครอบครัวที่ต้องผ่านจากคนหนึ่งสู่อีกคนผ่านบรรพบุรุษร่วม ไม่ใช่ผลต่างความลึก แต่เป็นผลรวมระยะจากแต่ละคนถึง LCA

SELECT MIN(a.depth + b.depth) AS degrees_of_separation
FROM family_closure a
JOIN family_closure b ON a.ancestor_id = b.ancestor_id
WHERE a.descendant_id = :person_a
  AND b.descendant_id = :person_b;

นี่คือการเชื่อมตารางเดียวกับคิวรี LCA แต่ใช้ฟังก์ชันรวมค่า MIN() แทน ORDER BY ... LIMIT 1 ลูกพี่ลูกน้องชั้นแรกมีระยะ 4 ขั้น เพราะแต่ละคนห่างจากปู่ย่าตายายร่วมกันสองขั้น ลูกพี่ลูกน้องชั้นแรกที่ต่างกันหนึ่งรุ่นมีระยะ 5 ขั้น คิวรีให้ค่าเหล่านี้ได้ถูกต้องโดยไม่ต้องมีตรรกะไล่ความสัมพันธ์ในชั้นแอปพลิเคชัน

ชื่อความสัมพันธ์ เช่น “ลูกพี่ลูกน้องชั้นแรกที่ต่างกันสองรุ่น” หรือ “พี่น้องของปู่ย่าตายาย” ต้องใช้ตรรกะเพิ่มเติมที่แปลงค่าความลึกเป็นชื่อความสัมพันธ์ ฟังก์ชันที่รับความลึกจาก A ถึง LCA และจาก B ถึง LCA แล้วคืนชื่อความสัมพันธ์รองรับกรณีทั่วไปได้เกือบทั้งหมด ตรรกะนี้อยู่ในชั้นแอปพลิเคชัน ไม่ใช่ SQL และง่ายขึ้นมากเมื่อคิวรีให้ค่าความลึกเป็นจำนวนเต็มที่ชัดเจน

การดูแล closure table เมื่อข้อมูลเปลี่ยน

การเพิ่มข้อมูลทำได้ตรงไปตรงมาตามตัวอย่างข้างต้น แต่การลบและการเปลี่ยนความสัมพันธ์กับพ่อแม่ต้องระวังมากกว่า

การลบบุคคลจากต้นไม้หมายถึงการลบทุกแถวใน closure table ที่บุคคลนั้นเป็นบรรพบุรุษหรือลูกหลาน หากบุคคลนั้นมีลูกหลาน การลบเพียงเท่านี้ยังไม่พอ ต้องลบแถวที่เชื่อมบรรพบุรุษของบุคคลนั้นกับลูกหลานเหล่านั้นด้วย มิฉะนั้น closure table จะยังระบุว่าทั้งสองฝ่ายมีความเกี่ยวข้องกัน เมื่อลบแถวเหล่านั้นแล้ว ลูกหลานจึงจะขาดการเชื่อมต่อกับชุดบรรพบุรุษของบุคคลที่ลบ พฤติกรรมนี้ถูกต้องหรือไม่ขึ้นอยู่กับแอปพลิเคชัน ในระบบผังเครือญาติมักห้ามลบบุคคลที่มีลูกหลานบันทึกไว้ โดยตรวจเงื่อนไขในชั้นแอปพลิเคชัน

การเปลี่ยนความสัมพันธ์กับพ่อแม่ เช่น แก้พ่อแม่ที่บันทึกไว้เป็นคนอื่น ต้องลบแถว closure เก่าของต้นไม้ย่อยที่มีลูกเป็นราก แล้วเพิ่มใหม่ตามพ่อแม่คนใหม่ วิธีง่ายที่สุดใช้ธุรกรรมลบแถว closure ทั้งหมดของต้นไม้ย่อยที่ได้รับผลกระทบ แล้วเพิ่มกลับโดยไล่จากพ่อแม่ใหม่ วิธีนี้ถูกต้องแต่ล็อกแถวที่เกี่ยวข้องระหว่างธุรกรรม สำหรับแอปผังเครือญาติส่วนใหญ่ที่เขียนข้อมูลไม่บ่อย ข้อแลกเปลี่ยนนี้ยอมรับได้

การเปรียบเทียบประสิทธิภาพ

ความแตกต่างด้านประสิทธิภาพระหว่าง closure table กับ recursive CTE มีนัยสำคัญและเพิ่มตามขนาดต้นไม้ ในต้นไม้จำลอง 500 โหนดที่มีความลึกเฉลี่ย 12 รุ่น คิวรี LCA แบบ recursive CTE ช้าจนรู้สึกได้เล็กน้อยในส่วนติดต่อผู้ใช้ แต่คิวรีเดียวกันที่ใช้การเชื่อม closure table เร็วจนเวลารอส่วนใหญ่เกิดจากการรับส่งผ่านเครือข่าย ไม่ใช่การประมวลผลคิวรี

การดูแล closure table เพิ่มต้นทุนการเขียนต่อการเพิ่มข้อมูลแต่ละครั้งอย่างวัดได้ โดยเพิ่มตามความลึกของต้นไม้ แต่ในผังเครือญาติ การเพิ่มข้อมูลเกิดน้อยกว่าการอ่านมาก การเพิ่มคนหนึ่งคนอาจตามด้วยการค้นหาหลายพันครั้งเพื่อแสดงความสัมพันธ์และภาพ ข้อแลกเปลี่ยนจึงเอื้อให้เลือก closure table อย่างชัดเจน

ภาระพื้นที่จัดเก็บก็เป็นสิ่งที่ควรพิจารณา closure table สำหรับต้นไม้ 500 คนที่ลึกเฉลี่ย 12 รุ่นใช้ราว 6,500 แถว (ประมาณ 13 แถวต่อคน รวมแถวที่อ้างอิงถึงตนเอง) แม้รวมภาระเพิ่มเติมต่อแถวของ PostgreSQL (ส่วนหัวทูเพิลขนาด 23 ไบต์และตัวชี้แถว) และดัชนีทั้งสามแล้ว ก็ใช้พื้นที่ในระดับราวหนึ่งร้อยไบต์ต่อแถว หรือรวมทั้งหมดไม่ถึงหนึ่งเมกะไบต์ แม้ฐานข้อมูลเครือญาติขนาดใหญ่ที่มีคนหลายหมื่นคน ตาราง closure ก็ยังเก็บในหน่วยความจำของเซิร์ฟเวอร์ฐานข้อมูลสมัยใหม่ได้สบาย เพื่อแคชและค้นผ่านดัชนีอย่างรวดเร็ว