الكشف عن دورة مع العوامل الفرعية العودية

Question

يمكن لشركة Oracle SQL القيام باستفسارات هرمية منذ V2، باستخدام ملكية الملكية الخاصة بها بواسطة بناء جملة. وأضافوا بأحدث 11 جرام الإصدار 2، وأضافوا العوملة الاستقامة العودية، والمعروفة أيضا باسم التكريم مع البند. هذا هو معيار ANSI، وإذا فهمت بشكل صحيح، فقد تم تنفيذ هذا واحد من قبل بائعي RDBMS آخر أيضا.

عند مقارنة الاتصال مع المكاني، لاحظت اختلافا في مجموعة النتائج عند استخدام الكشف عن الدورة. إن الاتصال بالنتائج أكثر بديهية بالنسبة لي، لذلك أتساءل ما إذا كان تنفيذ Oracle يحتوي على خطأ، أو إذا كان هذا هو ANSI القياسي والسلوك المتوقع. لذلك سؤالي هو إذا كان يمكنك التحقق من الاستعلام المتكرر باستخدام قواعد بيانات أخرى مثل MySQL و DB2 و SQL Server وغيرها. شريطة أن تدعم قواعد البيانات تلك العودية بجملة بالطبع.

إليك كيفية عملها في Oracle 11.2.0.0.0

SQL> select *
  2    from t
  3  /

        ID  PARENT_ID
---------- ----------
         1          2
         2          1

2 rows selected.

الاستعلام باستخدام Connect by Somements:

SQL>  select id
  2        , parent_id
  3        , connect_by_iscycle
  4     from t
  5  connect by nocycle parent_id = prior id
  6    start with id = 1
  7  /

        ID  PARENT_ID CONNECT_BY_ISCYCLE
---------- ---------- ------------------
         1          2                  0
         2          1                  1

2 rows selected.

والتي تبدو بديهية لي. ومع ذلك، باستخدام بناء جملة ANSI الجديد، يقوم بإرجاع صف آخر آخر:

SQL> with tr (id,parent_id) as
  2  ( select id
  3         , parent_id
  4      from t
  5     where id = 1
  6     union all
  7    select t.id
  8         , t.parent_id
  9      from t
 10           join tr on t.parent_id = tr.id
 11  ) cycle id set is_cycle to '1' default '0'
 12  select id
 13       , parent_id
 14       , is_cycle
 15    from tr
 16  /

        ID  PARENT_ID I
---------- ---------- -
         1          2 0
         2          1 0
         1          2 1

3 rows selected.

هذا هو البرنامج النصي يمكنك استخدامه للتحقق:

create table t
( id        number
, parent_id number
);
insert into t values (1, 2);
insert into t values (2, 1);
commit;
with tr (id,parent_id) as
( select id
       , parent_id
    from t
   where id = 1
   union all
  select t.id
       , t.parent_id
    from t
         join tr on t.parent_id = tr.id
) cycle id set is_cycle to '1' default '0'
select id
     , parent_id
     , is_cycle
  from tr;

Answer 1

من الوثائق على ذلك CONNECT_BY_ISCYCLE:

ال CONNECT_BY_ISCYCLE عودة pseudocolumn 1 إذا كان الصف الحالي لديه طفل هو أيضا سلفها

وهذا في CYCLE:

يعتبر الصف يشكل دورة في حالة وجود أحد صفوف سلفها نفس القيم لأعمدة الدورة.

في مثالك، صف 2 هل لديك طفل وهو أيضا سلفها، ولكن id لم يتم إرجاعها بعد.

بعبارات أخرى، CONNECT_BY_ISCYCLE الشيكات الأطفال (الذي لم يتم إرجاعه بعد)، في حين CYCLE الشيكات الصف الحالي (الذي عاد بالفعل).

CONNECT BY هو الصف على أساس، في حين العودية CTEيتم تعيين تعيين.

لاحظ أن وثائق أوراكل على CYCLE يذكر "صف سلف". ومع ذلك، بشكل عام، لا يوجد مفهوم "صف سلف" في العودية CTE. وبعد إنها عملية مجموعة قائمة يمكن أن تسفر عن نتائج خارج الشجرة تماما. بشكل عام، يمكن أن يستخدم الجزء المرساة والجزء المتكرر الجداول المختلفة.

منذ العودية CTEهي مستخدم تستخدم لبناء الأشجار الهرمية، Oracle قررت إضافة فحص دورة. ولكن بسبب الطريقة التي تنتقلها المتكرر CTEتعمل بشكل عام، من المستحيل عموما أن تخبرها ستؤدي الخطوة التالية إلى إنشاء دورة أم لا، لأنه بدون تعريف واضح لنظام "صف الأسلاف" لا يمكن تعريفه إما.

لإجراء الخطوة التالية "التالية"، يجب أن تكون المجموعة "الحالية" بأكملها، ولكن لتوليد كل صف من المجموعة الحالية (والذي يتضمن عمود الدورة)، نحتاج فقط إلى الحصول على نتائج التشغيل "التالي".

إنها ليست مشكلة إذا كانت المجموعة الحالية تتكون دائما من صف واحد (مثل في CONNECT BY)، لكنها مشكلة إذا كانت العملية العودية المحددة على مجموعة ككل.

لم ننظر إلى Oracle 11 ومع ذلك، ولكن SQL Server تنفذ العودية CTEعن طريق إخفاء مجرد CONNECT BY وراءهم، الأمر الذي يتطلب وضع قيود عديدة (كل ما يمنع بفعالية جميع العمليات القائمة على المجموعة).

PostgreSQLالتنفيذ، من ناحية أخرى، يتم ضبطه حقا: يمكنك القيام بأي عملية مع جزء المرساة في الجزء المتكرر. ليس لديه أي وسيلة للكشف عن الدورات، لأن الدورات غير محددة في المقام الأول.

كما ذكر من قبل، MySQL لا ينفذ CTEعلى الإطلاق (لا ينفذ HASH JOINأو MERGE JOINS أيضا، فقط الحلقات المتداخلة، لذلك لا تفاجأ كثيرا).

ومن المفارقات، تلقيت خطابا اليوم في هذا الموضوع، الذي سأغطي في مدونتي.

تحديث:

العودية CTEفي SQL Server ليست أكثر من CONNECT BY متنكر. انظر هذه المقالة في مدونتي للحصول على تفاصيل صدمة:

• SQL Server: هل تعتمد مجموعة CTE المتراكبة حقا؟

Answer 2

يدعم PostgresQL استفسارات التسلسل الهرمي على غرار، ولكن ليس لديها أي اكتشاف دورة تلقائية. هذا يعني أنك بحاجة إلى كتابة طعامك وعدد عدد الصفوف التي تم إرجاعها وفقا للطريقة التي تحددها في ظروف الانضمام في الجزء المتكرر من الاستعلام.

كلا الأمثلة تستخدم صفيف إذا كانت المعرفات (تسمى All_IDs) للكشف عن الحلقات:

WITH recursive tr (id, parent_id, all_ids, cycle) AS (
    SELECT id, parent_id, ARRAY[id], false
    FROM t
    WHERE id = 1
    UNION ALL
    SELECT t.id, t.parent_id, all_ids || t.id, t.id = ANY(all_ids)
    FROM t
    JOIN tr ON t.parent_id = tr.id AND NOT cycle)
SELECT id, parent_id, cycle
FROM tr;

 id | parent_id | cycle
----+-----------+-------
  1 |         2 | f
  2 |         1 | f
  1 |         2 | t


WITH recursive tr (id, parent_id, all_ids, cycle) AS (
    SELECT id, parent_id, ARRAY[id], false
    FROM t
    WHERE id = 1
    UNION ALL
    SELECT t.id, t.parent_id, all_ids || t.id, (EXISTS(SELECT 1 FROM t AS x WHERE x.id = t.parent_id))
    FROM t
    JOIN tr ON t.parent_id = tr.id
    WHERE NOT t.id = ANY(all_ids))
SELECT id, parent_id, cycle
FROM tr;

 id | parent_id | cycle
----+-----------+-------
  1 |         2 | f
  2 |         1 | t

Answer 3

بقدر ما أعلم:

• MySQL لا يدعم CTE المتراكبة
• SQL Sever لا يدعم الكشف عن الدورة في CTE Recursive

Answer 4

MySQL Server الإصدار 5.0.45 with:

خطأ 1064 (42000): لديك خطأ في بناء جملة SQL الخاص بك؛ حدد الدليل الذي يتوافق مع إصدار خادم MySQL الخاص بك للحصول على بناء الجملة الصحيح لاستخدامه بالقرب من "مع TR (ID، PARTER_ID) ك (المعرف المحدد، PARTER_ID من T WHERE = 1 UNION ALL S 'في السطر 1.

Answer 5

WITH RECURSIVE s (master, slave, all_ids, cycle) AS
(
    SELECT master, slave, ARRAY[master], false FROM binding WHERE master=3477

    UNION ALL

    SELECT d.master, d.slave, all_ids || d.master, d.slave = ANY(all_ids)
    FROM
        binding AS d
    JOIN
        s
    ON (d.master = s.slave)
    WHERE NOT d.master = ANY(all_ids)
)
SELECT *
FROM s;

أعتقد أن هذا الشرط أفضل d.slave = ANY(all_ids)

Answer 6

نتائج الاتصال عن طريق قد لا تكون دائما بديهية.

أدناه الاستفسارات توضح طرق مختلفة للكشف عن الدورات التي تبدأ id = 3 الرسم البياني على الصورة.

create table graph (id, id_parent) as
(select 2, 1 from dual
union all select 3, 1 from dual
union all select 4, 3 from dual
union all select 5, 4 from dual
union all select 3, 5 from dual)

SQL> select level lvl, graph.*, connect_by_iscycle cycle
  2    from graph
  3   start with id = 3
  4  connect by nocycle prior id = id_parent;

       LVL         ID  ID_PARENT      CYCLE
---------- ---------- ---------- ----------
         1          3          1          0
         2          4          3          0
         3          5          4          1
         1          3          5          0
         2          4          3          0
         3          5          4          1

6 rows selected.

SQL> select level lvl, graph.*, connect_by_iscycle cycle
  2    from graph
  3   start with id = 3
  4  connect by nocycle prior id = id_parent
  5         and prior id_parent is not null;

       LVL         ID  ID_PARENT      CYCLE
---------- ---------- ---------- ----------
         1          3          1          0
         2          4          3          0
         3          5          4          0
         4          3          5          1
         1          3          5          0
         2          4          3          0
         3          5          4          1

7 rows selected.

SQL> with t(id, id_parent) as
  2   (select *
  3      from graph
  4     where id = 3
  5    union all
  6    select g.id, g.id_parent
  7      from t
  8      join graph g
  9        on t.id = g.id_parent)
 10  search depth first by id set ord
 11  cycle id set cycle to 1 default 0
 12  select * from t;

        ID  ID_PARENT        ORD C
---------- ---------- ---------- -
         3          1          1 0
         4          3          2 0
         5          4          3 0
         3          5          4 1
         3          5          5 0
         4          3          6 0
         5          4          7 0
         3          5          8 1

8 rows selected.

عقدة مع id = 3 لديه واويندان، لذا اجتاز أوراكل دورتين في هذا المثال.

(1, 3) -> (3, 4) -> (4, 5) -> (5, 3)

و

(5, 3) -> (3, 4) -> (4, 5)

حافة (5، 3) مفقود من نتيجة الاستعلام الأول والدورة الأولى. في نفس الوقت الحال (5، 3) يظهر في النتيجة للاستعلام الثالث والدورة الثانية مرتين.

لما ذلك؟ يمكنك التحقق من الوصف لمنطق الكشف عن الدورة في الجواب المقدم من Quassnoi. في اللغة الإنجليزية العادية وهذا يعني ذلك

(1) الاتصال من خلال الكشف عن دورة إذا معرف الطفل للصف الحالي هو جزء من المعرفات التي تمت زيارتها حتى الآن

(2) REC مع الكشف عن دورة إذا معرف للصف الحالي هو جزء من المعرفات التي تمت زيارتها حتى الآن

نتيجة الاستعلام الثاني تبدو أكثر طبيعية على الرغم من وجود مسند إضافي and prior id_parent is not null. وبعد في هذه الحالة

(3) يكتشف دورة إذا معرف للصف الحالي هو جزء من معرفات الوالدينزار حتى الآن

يتم تنفيذ كل هذه الشروط في الأعمدة CNT1، CNT2، CNT3 في الاستعلام أدناه.

SQL> with t(id, id_parent, path_id, path_id_parent, cnt1, cnt2, cnt3) as
  2   (select g.*,
  3           cast('->' || g.id as varchar2(4000)),
  4           cast('->' || g.id_parent as varchar2(4000)),
  5           0,
  6           0,
  7           0
  8      from graph g
  9     where id = 3
 10    union all
 11    select g.id,
 12           g.id_parent,
 13           t.path_id || '->' || g.id,
 14           t.path_id_parent || '->' || g.id_parent,
 15           regexp_count(t.path_id || '->', '->' ||
 16            (select id from graph c where c.id_parent = g.id) || '->'),
 17           regexp_count(t.path_id || '->', '->' || g.id || '->'),
 18           regexp_count(t.path_id_parent || '->', '->' || g.id || '->')
 19      from t
 20      join graph g
 21        on t.id = g.id_parent
 22    -- and t.cnt1 = 0
 23    -- and t.cnt2 = 0
 24    -- and t.cnt3 = 0
 25    )
 26  search depth first by id set ord
 27  cycle id set cycle to 1 default 0
 28  select * from t;

        ID  ID_PARENT PATH_ID         PATH_ID_PARENT  CNT1 CNT2 CNT3        ORD C
---------- ---------- --------------- --------------- ---- ---- ---- ---------- -
         3          1 ->3             ->1                0    0    0          1 0
         4          3 ->3->4          ->1->3             0    0    0          2 0
         5          4 ->3->4->5       ->1->3->4          1    0    0          3 0
         3          5 ->3->4->5->3    ->1->3->4->5       1    1    1          4 1
         3          5 ->3             ->5                0    0    0          5 0
         4          3 ->3->4          ->5->3             0    0    0          6 0
         5          4 ->3->4->5       ->5->3->4          1    0    1          7 0
         3          5 ->3->4->5->3    ->5->3->4->5       1    1    1          8 1

8 rows selected.

إذا قمت بتصفية غير مرشح بواسطة CNT1 / CNT2 / CNT3 وإزالة "دورة معرف الدورة إلى 1 الافتراضي 0"، فسيتم إرجاع الاستعلام نتيجة الاستعلام المقابلة أعلاه. بعبارات أخرى يمكنك تجنب ذلك cycle clause وتنفيذ أي منطق الكشف عن الدورة تجد أكثر بديهية.

يمكن العثور على تفاصيل إضافية حول Traversing الهرمي والكشف عن الدورة في الكتاب كشف أوراكل SQL.