ربط الحلقات المتداخلة

تُعدّ عملية الربط الحلقي المتداخل خوارزمية بسيطة تربط علاقتين باستخدام حلقتين متداخلتين . ^{[ 1 ]} تُعتبر عمليات الربط مهمة لإدارة قواعد البيانات .

علاقتان${\displaystyle R}$و${\displaystyle S}$يتم ربطها على النحو التالي:

تُعرَّف خوارزمية nested_loop_join على النحو التالي: لكل صف r في R ، لكل صف s في S ، إذا حقق r و s شرط الربط ، فأنتج الصف < r , s >

ستتضمن هذه الخوارزمية عمليات نقل الكتل n _r *b _s + b _{r وعمليات البحث n r} +b _r ، حيث b _r و b _s هما عدد الكتل في العلاقات R و S على التوالي، و n _r هو عدد الصفوف في العلاقة R.

يتم تشغيل الخوارزمية في${\displaystyle O(|R||S|)}$وحدات الإدخال/الإخراج، حيث${\displaystyle |R|}$و${\displaystyle |S|}$يمثل عدد الصفوف الموجودة في${\displaystyle R}$و${\displaystyle S}$ويمكن تعميمها بسهولة لربط أي عدد من العلاقات ...

تُعد خوارزمية الربط الحلقي المتداخل ^{[ 2 ]} تعميمًا لخوارزمية الحلقات المتداخلة البسيطة، وهي تستفيد من ذاكرة إضافية لتقليل عدد مرات تكرار العملية.${\displaystyle S}$يتم فحص العلاقة. يقوم النظام بتحميل أجزاء كبيرة من العلاقة R إلى الذاكرة الرئيسية. لكل جزء، يقوم بفحص S وتقييم شرط الربط على جميع أزواج الصفوف الموجودة حاليًا في الذاكرة. هذا يقلل عدد مرات فحص S إلى مرة واحدة لكل جزء.

إذا كانت العلاقة الداخلية تحتوي على فهرس على السمات المستخدمة في الربط، فيمكن استبدال الربط الحلقي البسيط بربط الفهرس.

تقوم خوارزمية index_join بما يلي: لكل صف r في R ، لكل صف s في S في البحث عن الفهرس، قم بإرجاع الصف < r , s >

يتحسن التعقيد الزمني لهذا التباين من${\displaystyle O(|R||S|){\text{ to }}O(|R|\log |S|)}$

• انضمام التجزئة
• دمج الفرز