रिकर्सिव क्वेरी (WITH RECURSIVE): पदानुक्रम और ग्राफ़

WITH RECURSIVE से पेड़ों और ग्राफ़ों को पार करें, गहराई और चक्र पहचान में महारत हासिल करते हुए।

11 मिनट · 3 प्रश्न

एक रिकर्सिव CTE UNION ALL से जुड़े दो हिस्सों से बना होता है: एक एंकर टर्म जो शुरुआती रो प्रदान करता है, और एक रिकर्सिव टर्म जो स्वयं 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;

एक ग्राफ़ को एक एज टेबल (src, dst) से मॉडल किया जाता है। पारगमन उसी यांत्रिकी का पालन करता है, लेकिन एक ग्राफ़ में चक्र हो सकते हैं: 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 क्लॉज़ का उपयोग करें
   • मेमोरी कैश का आकार बढ़ाएँ