| المستخلص: |
تعزيز أداء نظم قواعد البيانات الكبيرة يعتمد بشكل كبير على تكلفة أداء عمليات الانضمام (Join Operations). فعندما يتم تنفيذ عملية ضم جدولين كبيرين فإن التنفيذ المثالي لتلك العملية يعد أحد مواضيع البحث التي تحوز على اهتمام العديد من الباحثين، خاصة عندما يكون الجدولين المراد ضمهما كبيرين جدا ولا يمكن وضعهما في الذاكرة الرئيسية. وفي هذه الحالة، يتم تنفيذ الضم باستخدام أي أسلوب آخر غير استخدام خوارزميات البعثرة للضم. في هذه الورقة، يتم تقديم خوارزم جديد للضم يقوم على استخدام شجرة الكواد (Quadtree). وقد تم إثبات أنه بتطبيق الخوارزم المقترح على اثنين من الجداول الكبيرة جدا والتي لا يمكن وضعهما في الذاكرة الرئيسية، فإن الضم يتم بسرعة وفعالية. وفي الخوارزم الجديد المقترح يتم تمثيل الجدولين المراد ضمهما بفاعلية باستخدام الـ Quadtree لتخزين الجدولين والتي تم تصميمها للتعامل مع المصفوفات ذات البعد الواحد أو المصفوفات الأحادية (1-D Arrays) لتنفيذ عملية الضم. وقد تم دراسة معدلات سرعة العمليات المساحة اللازمة لتنفيذ الخوارزم الجديد، وقد أظهرت الدراسات التجريبية أن هذا الخوارزم يمتاز بالكفاءة والتفوق. وخوارزم الضم المقترح يتطلب حدا أدنى من عمليات الإدخال والإخراج ويعمل في الذاكرة الرئيسية بمعدلات للزمن تتناسب مع (n log (n / k))O حيث k تمثل عدد المجموعات ذات المفاتيح والتي لها نفس الحرف الأول و (n / k) أصل بكثير من n.
Enhancing the performance of large database systems depends heavily on the cost of performing join operations. When two very large tables are joined, optimizing such operation is considered one of the interesting research topics to many researchers, especially when both tables, to be joined, are very large to fit in main memory. In such case, join is usually performed by any other method than hash join algorithms. In this paper, a novel join algorithm that is based on the use of quadtrees, is introduced. Applying the proposed algorithm on two very large tables, that are too large to fit in main memory, is proven to be fast and efficient. In the proposed new algorithm, both tables are represented by a storage efficient quadtree that is designed to handle one-dimensional arrays (1-D arrays). The algorithm works on the two 1-D arrays of the two tables to perform join operations. For the new algorithm, time and space complexities are studied. Experimental studies show the efficiency and superiority of this algorithm. The proposed join algorithm requires a minimum number of I/O operations and operates in main memory with O(n log (n/k)) time complexity, where k is the number of key groups with the same first letter, and (n/k) is much smaller than n.
|
