يتم استخدام العثور على التبعيات الوظيفية في البيانات في مجالات مختلفة لتحليل البيانات: إدارة قواعد البيانات، وتنظيف البيانات، والهندسة العكسية لقاعدة البيانات، واستكشاف البيانات. لقد نشرنا بالفعل عن التبعيات نفسها أناستاسيا بيريللو ونيكيتا بوبروف. هذه المرة، تشارك أناستازيا، خريجة مركز علوم الكمبيوتر هذا العام، تطوير هذا العمل كجزء من العمل البحثي الذي دافعت عنه في المركز.
اختيار المهمة
أثناء دراستي في مركز علوم الكمبيوتر، بدأت في دراسة قواعد البيانات بعمق، أي البحث عن التبعيات الوظيفية والاختلافية. كان هذا الموضوع مرتبطًا بموضوع مقرراتي الدراسية في الجامعة، لذلك أثناء العمل في المقرر الدراسي، بدأت في قراءة مقالات حول التبعيات المختلفة في قواعد البيانات. لقد كتبت مراجعة لهذه المنطقة - وهي واحدة من أولى تعليقاتي باللغة الإنجليزية وتقديمه إلى مؤتمر SEIM-2017. لقد كنت سعيدًا جدًا عندما علمت أنه تم قبولها بعد كل شيء، وقررت التعمق في الموضوع. المفهوم نفسه ليس جديدا - لقد بدأ استخدامه في التسعينيات، ولكن حتى الآن يتم استخدامه في العديد من المجالات.
خلال الفصل الدراسي الثاني في المركز، بدأت مشروعًا بحثيًا لتحسين الخوارزميات للعثور على التبعيات الوظيفية. عملت عليها مع نيكيتا بوبروف، طالب الدراسات العليا بجامعة سانت بطرسبرغ الحكومية، في أبحاث JetBrains.
التعقيد الحسابي للبحث عن التبعيات الوظيفية
المشكلة الرئيسية هي التعقيد الحسابي. يقتصر عدد التبعيات الدنيا وغير التافهة المحتملة أعلاه على القيمة حيث - عدد سمات الجدول. لا يعتمد وقت تشغيل الخوارزميات على عدد السمات فحسب، بل يعتمد أيضًا على عدد الصفوف. في التسعينيات، كان بإمكان خوارزميات البحث عن القانون الفيدرالي على جهاز كمبيوتر سطح المكتب العادي معالجة مجموعات البيانات التي تحتوي على ما يصل إلى 90 سمة وعشرات الآلاف من الصفوف في ما يصل إلى عدة ساعات. تكتشف الخوارزميات الحديثة التي تعمل على معالجات متعددة النواة تبعيات مجموعات البيانات التي تتكون من مئات السمات (حتى 20) ومئات الآلاف من الصفوف في نفس الوقت تقريبًا. ومع ذلك، هذا لا يكفي: مثل هذا الوقت غير مقبول بالنسبة لمعظم تطبيقات العالم الحقيقي. ولذلك، قمنا بتطوير أساليب لتسريع الخوارزميات الموجودة.
مخططات التخزين المؤقت لتقاطعات التقسيم
في الجزء الأول من العمل، قمنا بتطوير أنظمة التخزين المؤقت لفئة من الخوارزميات التي تستخدم طريقة تقاطع الأقسام. قسم السمة هو مجموعة من القوائم، حيث تحتوي كل قائمة على أرقام أسطر بنفس القيم لسمة معينة. وتسمى كل قائمة من هذا القبيل كتلة. تستخدم العديد من الخوارزميات الحديثة الأقسام لتحديد ما إذا كانت التبعية موجودة أم لا، أي أنها تلتزم بالمبادئ التالية: التبعية عقد إذا . هنا يتم تعيين القسم واستخدام مفهوم حجم القسم - عدد المجموعات الموجودة فيه. الخوارزميات التي تستخدم الأقسام، عند انتهاك التبعية، تضيف سمات إضافية إلى الجانب الأيسر من التبعية، ثم تعيد حسابها، وتقوم بعملية تقاطع الأقسام. وتسمى هذه العملية التخصص في المقالات. لكننا لاحظنا أنه يمكن إعادة استخدام أقسام التبعيات التي لن يتم الاحتفاظ بها إلا بعد بضع جولات من التخصص، مما قد يقلل بشكل كبير من وقت تشغيل الخوارزميات، نظرًا لأن عملية التقاطع مكلفة.
لذلك، اقترحنا أسلوبًا إرشاديًا يعتمد على شانون إنتروبيا وعدم يقين جيني، بالإضافة إلى مقياسنا الذي أطلقنا عليه إنتروبيا العكسية. إنه تعديل طفيف لـ Shannon Entropy ويزداد مع زيادة تفرد مجموعة البيانات. الاستدلال المقترح هو كما يلي:
ومن — درجة تفرد القسم المحسوب مؤخرًا و هو متوسط درجات التفرد للسمات الفردية. تم اختبار جميع المقاييس الثلاثة المذكورة أعلاه كمقياس فريد. يمكنك أيضًا ملاحظة وجود معدّلين في الاستدلال. يشير الأول إلى مدى قرب القسم الحالي من المفتاح الأساسي ويسمح لك بالتخزين المؤقت إلى حد أكبر لتلك الأقسام البعيدة عن المفتاح المحتمل. يسمح لك المعدل الثاني بمراقبة إشغال ذاكرة التخزين المؤقت وبالتالي يشجع على إضافة المزيد من الأقسام إلى ذاكرة التخزين المؤقت في حالة توفر مساحة خالية. سمح لنا الحل الناجح لهذه المشكلة بتسريع خوارزمية PYRO بنسبة 10-40%، اعتمادًا على مجموعة البيانات. ومن الجدير بالذكر أن خوارزمية PYRO هي الأكثر نجاحًا في هذا المجال.
في الشكل أدناه، يمكنك رؤية نتائج تطبيق الاستدلال المقترح مقارنةً بأسلوب التخزين المؤقت الأساسي لقلب العملة. المحور X لوغاريتمي.
طريقة بديلة لتخزين الأقسام
ثم اقترحنا طريقة بديلة لتخزين الأقسام. الأقسام عبارة عن مجموعة من العناقيد، تقوم كل منها بتخزين أعداد من الصفوف ذات قيم متطابقة لسمات معينة. قد تحتوي هذه المجموعات على تسلسلات طويلة من أرقام الصف، على سبيل المثال إذا كانت البيانات في الجدول مرتبة. لذلك، اقترحنا نظام ضغط لتخزين الأقسام، أي التخزين الفاصل للقيم في مجموعات من الأقسام:
$$display$$pi(X) = {{الفاصل السفلي{1، 2، 3، 4، 5}_ {الفاصل الزمني الأول}، القوس السفلي {7، 8} _ {الفاصل الثاني}، 10}}\ السهم السفلي {ضغط} \ pi(X) = {{الفاصل السفلي{$, 1, 5}_{الفاصل~الأول}، القوس السفلي{7, 8}_{الفاصل ~الثاني}, 10}}$$display$$
تمكنت هذه الطريقة من تقليل استهلاك الذاكرة أثناء تشغيل خوارزمية TANE من 1 إلى 25%. خوارزمية TANE هي خوارزمية كلاسيكية للبحث عن القوانين الفيدرالية، وتستخدم الأقسام أثناء عملها. كجزء من الممارسة، تم اختيار خوارزمية TANE، حيث كان تنفيذ التخزين الفاصل فيها أسهل بكثير من، على سبيل المثال، في PYRO من أجل تقييم ما إذا كان النهج المقترح يعمل. وترد النتائج التي تم الحصول عليها في الشكل أدناه. المحور X لوغاريتمي.
مؤتمر ADBIS-2019
وبناءً على نتائج البحث، قمت في سبتمبر 2019 بنشر مقال في المؤتمر الأوروبي الثالث والعشرون للتقدم في قواعد البيانات ونظم المعلومات (ADBIS-23). خلال العرض، تمت الإشارة إلى العمل من قبل بيرنهارد ثالهايم، وهو شخص مهم في مجال قواعد البيانات. شكلت نتائج البحث أساس رسالتي في درجة الماجستير في الرياضيات والميكانيكا في جامعة ولاية سانت بطرسبرغ، والتي تم خلالها تنفيذ كلا النهجين المقترحين (التخزين المؤقت والضغط) في كلا الخوارزميتين: TANE وPYRO. علاوة على ذلك، أظهرت النتائج أن الأساليب المقترحة عالمية، حيث لوحظ في كلا الخوارزميتين، مع كلا النهجين، انخفاض كبير في استهلاك الذاكرة، فضلا عن انخفاض كبير في وقت تشغيل الخوارزميات.
المصدر: www.habr.com