مطاردة (خوارزمية)

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

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

في أبسط تطبيقاتها، تُستخدم عملية المطاردة لاختبار ما إذا كان من الممكن استعادة إسقاط مخطط علاقة مقيد ببعض التبعيات الوظيفية على تفكيك معين عن طريق إعادة ضم الإسقاطات . ليكن t صفًا في${\displaystyle \pi _{S_{1}}(R)\bowtie \pi _{S_{2}}(R)\bowtie ...\bowtie \pi _{S_{k}}(R)}$حيث R علاقة و F مجموعة من التبعيات الوظيفية (FD). إذا تم تمثيل الصفوف في R على النحو التالي : t1 _، ...، _{tk ، فيجب} أن يتطابق ربط إسقاطات كل ti مع tk .${\displaystyle \pi _{S_{i}}(R)}$حيث i = 1، 2، ...، k . إذا لم يكن t _{i موجودًا}${\displaystyle \pi _{S_{i}}(R)}$، القيمة غير معروفة.

يمكن إجراء عملية البحث برسم جدول (وهو نفس الأسلوب المستخدم في استعلام الجدول ). لنفترض أن R يحتوي على السمات A وB و... وأن مكونات t هي a وb و... بالنسبة لـ tᵢ _، استخدم نفس الحرف المستخدم لـ t في المكونات الموجودة في Sᵢ _، ولكن ضع الرمز السفلي i أسفل الحرف إذا لم يكن المكون موجودًا في Sᵢ _. عندئذٍ، _{سيتطابق} tᵢ مع t إذا كان موجودًا في Sᵢ _، وسيكون له قيمة فريدة في غير ذلك.

عملية المطاردة متقاربة . توجد تطبيقات لخوارزمية المطاردة، ^{[ 3 ]} بعضها مفتوح المصدر أيضًا. ^{[ 4 ]}

ليكن R ( A , B , C , D ) مخطط علاقات معروفًا بأنه يتبع مجموعة التبعيات الوظيفية F = { A → B , B → C , CD → A }. لنفترض أن R مُقسَّم إلى ثلاثة مخططات علاقات S1 ₌ { A , D }، وS2 ₌ { A , C }، وS3 ₌ { B , C , D }. يمكن تحديد ما إذا كان هذا التقسيم غير مُفقِد للبيانات من خلال إجراء عملية تتبع كما هو موضح أدناه.

الجدول الأولي لهذا التفكيك هو:

يمثل الصف الأول S _1. مكونات السمات A و D غير مشفرة، ومكونات السمات B و C مشفرة برقم i = 1. يتم ملء الصفين الثاني والثالث بنفس الطريقة مع S ₂ و S ₃ على التوالي.

الهدف من هذا الاختبار هو استخدام الجدول F المُعطى لإثبات أن t = ( a , b , c , d ) ينتمي فعلاً إلى R. ولتحقيق ذلك، يمكن تتبع الجدول بتطبيق التبعيات الوظيفية (FDs) في F لمساواة الرموز فيه. الجدول النهائي الذي يحتوي على صف مطابق لـ t يعني أن أي مجموعة t في عملية ضم الإسقاطات هي في الواقع مجموعة من R. لإجراء اختبار التتبع، يتم أولاً تحليل جميع التبعيات الوظيفية في F بحيث تحتوي كل تبعية وظيفية على سمة واحدة على الجانب الأيمن من السهم. (في هذا المثال، يبقى F دون تغيير لأن جميع تبعياته الوظيفية تحتوي بالفعل على سمة واحدة على الجانب الأيمن: F = { A → B , B → C , CD → A }).

عند مساواة رمزين، إذا كان أحدهما بدون رمز سفلي، اجعل الآخر مثله بحيث يحتوي الجدول النهائي على صف مطابق تمامًا للجدول t = ( a , b , c , d ). إذا كان لكل منهما رمز سفلي خاص به، فغيّر أحدهما إلى الآخر. مع ذلك، لتجنب الالتباس، يجب تغيير جميع حالات ظهور الرمزين. أولًا، طبّق العملية A → B على الجدول. الصف الأول هو ( a , b1 , c1 , d ) حيث a بدون رمز سفلي و _{b1 برمز سفلي 1.} بمقارنة الصف الأول بالصف الثاني، غيّر _b2 إلى b1 . _بما أن الصف الثالث يحتوي على a _{= 3} ، فإن b في الصف الثالث يبقى كما هو. الجدول الناتج هو:

ثم لننظر إلى B → C. يحتوي كل من الصفين الأول والثاني على b _{= 1،} ونلاحظ أن الصف الثاني يحتوي على c بدون رمز سفلي . لذلك، يتغير الصف الأول إلى ( a , b _{= 1} , c , d ). وبالتالي، يكون الجدول الناتج كما يلي:

لننظر الآن إلى الجدول CD → A. يحتوي الصف الأول على c و d بدون رمز ، وهو نفس ما هو عليه في الصف الثالث. هذا يعني أن قيمة A في الصفين الأول والثالث يجب أن تكون متطابقة أيضًا. لذا، نستبدل ₃ في الصف الثالث بـ a . الجدول الناتج هو:

في هذه المرحلة، لاحظ أن الصف الثالث هو ( أ ، ب ، ج ، د ) وهو نفسه الصف t . لذلك، هذا هو الجدول النهائي لاختبار المطاردة مع R و F المعطاة . وبالتالي، كلما تم إسقاط R على _S1 وS2 _و S3 _وإعادة ضمها، تكون النتيجة في R. على وجه الخصوص، يكون الصف الناتج هو نفسه صف R الذي تم إسقاطه على { ب ، ج ، د }.

• سيرج أبيتبول ، ريتشارد ب. هول ، فيكتور فيانو : أسس قواعد البيانات. أديسون-ويسلي، 1995.
• AV Aho و C. Beeri و JD Ullman : نظرية الربط في قواعد البيانات العلائقية . معاملات ACM لأنظمة قواعد البيانات 4(3): 297-314، 1979.
• JD Ullman : مبادئ قواعد البيانات وأنظمة قواعد المعرفة، المجلد الأول . مطبعة علوم الحاسوب، نيويورك، 1988.
• جيه دي أولمان ، جيه ويدوم : دورة تمهيدية في أنظمة قواعد البيانات (الطبعة الثالثة). الصفحات  96-99. بيرسون برنتيس هول، 2008.
• مايكل بنديكت ، جورج كونستانتينيديس ، جيانسالفاتوري مكة ، بوريس موتيك ، باولو بابوتي ، دوناتيلو سانتورو ، إفثيميا تسامورا : قياس المطاردة . في بروك. القرون، 2017.

• سيرجيو جريكو؛ فرانشيسكا سبيتزانو؛ كريستيان مولينارو (2012). البيانات غير المكتملة والتبعيات بين البيانات في قواعد البيانات العلائقية . دار مورغان وكلايبول للنشر. ISBN 978-1-60845-926-1.