نموذج دو المتداخل

نموذج المجموعة المتداخلة هو أسلوب لتمثيل مجموعات المجموعات المتداخلة (المعروفة أيضًا بالأشجار أو التسلسلات الهرمية ) في قواعد البيانات العلائقية .

يعتمد هذا النظام على الفترات المتداخلة، التي "تتمتع بمناعة ضد مشكلة إعادة تنظيم التسلسل الهرمي، وتسمح بالإجابة على استعلامات التسلسل الهرمي لمسار السلف بشكل خوارزمي - دون الوصول إلى علاقة التسلسل الهرمي المخزنة". ^{[ 1 ]}

لا تستطيع الجبر العلائقي والحساب العلائقي القياسيان ، وعمليات SQL المبنية عليهما، التعبير مباشرةً عن جميع العمليات المطلوبة على التسلسلات الهرمية. ويُعدّ نموذج المجموعات المتداخلة حلاً لهذه المشكلة.

يُعدّ التعبير عن التسلسل الهرمي كعلاقة بين أب وابنه حلاً بديلاً. أطلق جو سيلكو على هذا النموذج اسم " نموذج قائمة التجاور" . إذا كان التسلسل الهرمي ذا عمق غير محدود، فإن نموذج قائمة التجاور لا يسمح بإجراء عمليات مثل مقارنة محتويات التسلسلات الهرمية لعنصرين، أو تحديد ما إذا كان عنصر ما يقع في التسلسل الهرمي الفرعي لعنصر آخر. أما عندما يكون التسلسل الهرمي ذا عمق ثابت أو محدود، فإن هذه العمليات ممكنة، ولكنها مكلفة، نظرًا لضرورة إجراء ربط علائقي واحد لكل مستوى. يُعرف هذا غالبًا باسم " مشكلة قائمة المواد" .

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

• دعم نوع بيانات هرمي مخصص، كما هو الحال في مرفق الاستعلام الهرمي في SQL ؛
• توسيع اللغة العلائقية من خلال عمليات التلاعب بالتسلسل الهرمي، كما هو الحال في الجبر العلائقي المتداخل .
• توسيع اللغة العلائقية مع الإغلاق المتعدي ، مثل عبارة CONNECT في SQL؛ وهذا يسمح باستخدام علاقة الأصل والفرع، ولكن التنفيذ يظل مكلفًا؛
• يمكن التعبير عن الاستعلامات بلغة تدعم التكرار وتُغلف العمليات العلائقية، مثل PL/SQL أو T-SQL أو لغة برمجة للأغراض العامة.

عندما لا تكون هذه الحلول متاحة أو غير مجدية، يجب اتباع نهج آخر.

يعتمد نموذج المجموعة المتداخلة على ترقيم العقد وفقًا لتسلسل اجتياز الشجرة ، حيث يتم زيارة كل عقدة مرتين، مع تخصيص أرقام حسب ترتيب الزيارة، وفي كلتا الزيارتين. ينتج عن ذلك رقمان لكل عقدة، يتم تخزينهما كسمتين. يصبح الاستعلام غير مكلف: إذ يمكن اختبار عضوية التسلسل الهرمي بمقارنة هذين الرقمين. يتطلب التحديث إعادة الترقيم، وبالتالي فهو مكلف. يمكن للتحسينات التي تستخدم الأعداد النسبية بدلًا من الأعداد الصحيحة تجنب إعادة الترقيم، وبالتالي يكون التحديث أسرع، على الرغم من أنه أكثر تعقيدًا. ^{[ 2 ]}

في كتالوج متجر الملابس، يمكن تصنيف الملابس وفقًا للتسلسل الهرمي الموضح على اليسار:

تُعدّ فئة "الملابس" الأعلى في التسلسل الهرمي، وتشمل جميع الفئات الفرعية. ولذلك، تُمنح قيم نطاق يساري ويميني تبلغ 1 و22 على التوالي، حيث تُساوي القيمة الأخيرة ضعف إجمالي عدد العُقد المُمثلة. يحتوي المستوى الهرمي التالي على فئتي "الرجال" و"النساء"، وكلتاهما تتضمن مستويات فرعية يجب أخذها في الحسبان. تُخصص قيم نطاق يساري ويميني لكل عقدة بيانات في كل مستوى وفقًا لعدد المستويات الفرعية التي تحتويها، كما هو موضح في بيانات الجدول.

من المتوقع أن تكون الاستعلامات التي تستخدم مجموعات متداخلة أسرع من الاستعلامات التي تستخدم إجراءً مخزنًا لاجتياز قائمة مجاورة، ولذا فهي الخيار الأسرع لقواعد البيانات التي تفتقر إلى بنى الاستعلامات التكرارية الأصلية، مثل MySQL 5.x. ^{[ 3 ]} مع ذلك، من المتوقع أن يكون أداء استعلامات SQL التكرارية مماثلاً لاستعلامات "البحث عن العناصر التابعة المباشرة"، وأسرع بكثير لاستعلامات البحث المتعمق الأخرى، ولذا فهي الخيار الأسرع لقواعد البيانات التي توفرها، مثل PostgreSQL ، ^{[ 4 ]} وOracle ، ^{[ 5 ]} و Microsoft SQL Server . ^{[ 6 ]} كان MySQL يفتقر إلى بنى الاستعلامات التكرارية، ولكنه أضاف هذه الميزات في الإصدار 8. ^{[ 7 ]}

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

إذا لم يكن من المتوقع تغيير بنية الشجرة بشكل متكرر، فيمكن إنشاء تسلسل هرمي مُنظّم بشكل صحيح لجداول السمات في التصميم الأولي للنظام، مما يؤدي إلى عبارات SQL أبسط وأكثر قابلية للنقل؛ وتحديدًا تلك التي لا تتطلب عددًا عشوائيًا من الجداول التي يتم إنشاؤها أو حذفها برمجيًا أثناء التشغيل لإجراء تغييرات على الشجرة. بالنسبة للأنظمة الأكثر تعقيدًا، يمكن تطوير التسلسل الهرمي من خلال النماذج العلائقية بدلًا من بنية شجرة رقمية ضمنية. يُعد عمق العنصر مجرد سمة أخرى وليس أساسًا لبنية قاعدة بيانات كاملة. كما ورد في كتاب "أنماط SQL المضادة" : ^{[ 8 ]}

تُعدّ المجموعات المتداخلة حلاً ذكياً، وربما أكثر من اللازم. كما أنها لا تدعم سلامة البيانات المرجعية. يُفضّل استخدامها عندما تحتاج إلى الاستعلام عن شجرة بشكل متكرر أكثر من حاجتك إلى تعديلها. ^{[ 9 ]}

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

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

لا يعاني نموذج الفترات المتداخلة من هذه المشكلة، ولكنه أكثر تعقيدًا في التنفيذ، وأقل شيوعًا. ومع ذلك، لا يزال يعاني من مشكلة جدول المفتاح الخارجي العلائقي. يخزن نموذج الفترات المتداخلة مواقع العقد كأعداد نسبية معبر عنها كحاصل قسمة (n/d).

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

حدد العقدة الفرعية ، والعقدة اليسرى ، والعقدة اليمنى من الشجرة كـ "الأصل" ، والشجرة كـ " الأصل " حيث تقع العقدة اليسرى للعقدة الفرعية بين العقدة اليسرى للأصل والعقدة اليمنى للأصل ، ولا يوجد ( -- لا توجد عقدة وسطى SELECT * FROM Tree as Mid WHERE العقدة الوسطى اليسرى بين العقدة اليسرى للأصل والعقدة اليمنى للأصل ، والعقدة اليسرى للعقدة الفرعية بين العقدة الوسطى اليسرى والعقدة الوسطى اليمنى ، والعقدة الوسطى غير موجودة في ( العقدة الأصلية ، العقدة الفرعية ) ) و العقدة اليسرى للأصل = 1 -- فهرس العقدة الأصلية اليسرى المعطى

أو بعبارة أخرى:

حدد العقدة الفرعية ، والعقدة اليسرى ، والعقدة اليمنى المميزة من الشجرة (Tree as Child , Tree as Parent ) حيث تكون العقدة اليسرى للشجرة الأبوية أصغر من العقدة اليسرى للشجرة الفرعية ، والعقدة اليمنى للشجرة الأبوية أكبر من العقدة اليمنى للشجرة الفرعية . ثم قم بتجميع النتائج حسب العقدة الفرعية ، والعقدة اليسرى ، والعقدة اليمنى للشجرة الفرعية ، مع تحديد العقدة اليسرى للشجرة الأبوية كأقرب سلف .

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

في هذا النموذج، يمكن إيجاد الأبناء المباشرين بالنظر إلى عقدة أصلية باستخدام كود SQL التالي :

SELECT Child.Node , Child.Left , Child.Right FROM Tree as Child , Tree as Parent WHERE Child.Depth = Parent.Depth + 1 AND Child.Left > Parent.Left AND Child.Right < Parent.Right AND Parent.Left = 1 -- معطى فهرس العقدة اليسرى للعقدة الأب​​​​​​​​​​​​​​

• قائمة الجوار
• شجرة كالكين-ويلف
• اجتياز الأشجار
• الشجرة (بنية البيانات)

• روابط ترولز بالبيانات الهرمية في أنظمة إدارة قواعد البيانات العلائقية
• إدارة البيانات الهرمية في قواعد البيانات العلائقية
• تطبيق PHP PEAR للمجموعات المتداخلة - بقلم دانيال خان
• تحويل أي قائمة مجاورة إلى مجموعات متداخلة باستخدام الإجراءات المخزنة في MySQL
• تطبيق PHP Doctrine DBAL للمجموعات المتداخلة - بواسطة PreviousNext
• مجموعة R المتداخلة – مثال على مجموعة متداخلة في R