خوارزمية ضم الجداول لقواعد البيانات الضخمة باستخدام هياكل البيانات

Abstract

تعزيز أداء نظم قواعد البيانات الكبيرة يعتمد بشكل كبير على تكلفة أداء عمليات الانضمام (Join Operations). فعندما يتم تنفيذ عملية ضم جدولين كبيرين فإن التنفيذ المثالي لتلك العملية يعد أحد مواضيع البحث التي تحوز على اهتمام العديد من الباحثين، خاصة عندما يكون الجدولين المراد ضمهما كبيرين جداً ولا يمكن وضعهما في الذاكرة الرئيسة. وفي هذه الحالة، يتم تنفيذ الضم باستخدام أي أسلوب آخر غير استخدام خوارزميات البعثرة للضم. في هذه الورقة، يتم تقديم خوارزم جديد للضم يقوم على استخدام شجرة الكواد (Quadtree). وقد تم إثبات أنه بتطبيق الخوارزم المقترح على اثنين من الجداول الكبيرة جداً والتي لا يمكن وضعهما في الذاكرة الرئيسة، فإن الضم يتم بسرعة وفعالية. وفي الخوارزم الجديد المقترح يتم تمثيل الجدولين المراد ضمهما بفاعلية باستخدام الـQuadtree لتخزين الجدولين والتي تم تصميمها للتعامل مع المصفوفات ذات البعد الواحد أو المصفوفات الأحادية (1-D Arrays) لتنفيذ عملية الضم. وقد تم دراسة معدلات سرعة العمليات والمساحة اللازمة لتنفيذ الخوارزم الجديد، وقد أظهرت الدراسات التجريبية أن هذا الخوارزم يمتاز بالكفاءة والتفوق.وخوارزم الضم المقترح يتطلب حداً أدنى من عمليات الإدخال والإخراج ويعمل في الذاكرة الرئيسة بمعدلات للزمن تتناسب مع O(n log (n/k)) حيث k تمثل عدد المجموعات ذات المفاتيح والتي لها نفس الحرف الأول، و(n/k) أصغر بكثير من n.