بديهيات أرمسترونغ

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 43 صور
الموسوعة الحرة

تُعدّ بديهيات أرمسترونغ مجموعة من البديهيات (أو، بتعبير أدق، قواعد الاستدلال ) تُستخدم لاستنتاج جميع التبعيات الوظيفية في قاعدة بيانات علائقية . وقد طوّرها ويليام دبليو أرمسترونغ في بحثه المنشور عام 1974. [ 1 ] وتتميز هذه البديهيات بصحتها في توليد التبعيات الوظيفية فقط ضمن إغلاق مجموعة من التبعيات الوظيفية (يُشار إليها بـ F+{\displaystyle F^{+}}) عند تطبيقها على تلك المجموعة (المشار إليها بـF{\displaystyle F}كما أنها كاملة من حيث أن التطبيق المتكرر لهذه القواعد سيؤدي إلى توليد جميع التبعيات الوظيفية في الإغلاقF+{\displaystyle F^{+}}.

بشكل أكثر رسمية، دع⟨R(يو)،F⟩{\displaystyle \langle R(U),F\rangle }يشير إلى مخطط علائقي على مجموعة السماتيو{\displaystyle U}مع مجموعة من التبعيات الوظيفيةF{\displaystyle F}نقول إن التبعية الوظيفيةو{\displaystyle f}يُستنتج ذلك منطقياً منF{\displaystyle F}، وارمز إليه بـF⊨و{\displaystyle F\models f}إذا وفقط إذا كان لكل حالةر{\displaystyle r}لR{\displaystyle R}الذي يفي بالتبعيات الوظيفية فيF{\displaystyle F}،ر{\displaystyle r}كما أنه يرضيو{\displaystyle f}نرمز بـF+{\displaystyle F^{+}}مجموعة جميع التبعيات الوظيفية التي يُستدل عليها منطقيًا بواسطةF{\displaystyle F}.

علاوة على ذلك، فيما يتعلق بمجموعة من قواعد الاستدلالأ{\displaystyle A}نقول إن التبعية الوظيفيةو{\displaystyle f}يمكن اشتقاقها من التبعيات الوظيفية فيF{\displaystyle F}بواسطة مجموعة قواعد الاستدلالأ{\displaystyle A}ونرمز إليه بـF⊢أو{\displaystyle F\vdash _{A}f}إذا وفقط إذاو{\displaystyle f}يمكن الحصول على ذلك عن طريق تطبيق قواعد الاستدلال بشكل متكرر فيأ{\displaystyle A}إلى التبعيات الوظيفية فيF{\displaystyle F}نرمز بـFأ*{\displaystyle F_{A}^{*}}مجموعة جميع التبعيات الوظيفية التي يمكن اشتقاقها منF{\displaystyle F}عن طريق قواعد الاستدلال فيأ{\displaystyle A}.

ثم، مجموعة من قواعد الاستدلالأ{\displaystyle A}يكون سليماً إذا وفقط إذا تحققت الشروط التالية:

Fأ*⊆F+{\displaystyle F_{A}^{*}\subseteq F^{+}}

أي أننا لا نستطيع أن نستنتج عن طريقأ{\displaystyle A}التبعيات الوظيفية التي لا يُستدل عليها منطقيًا من خلالF{\displaystyle F}مجموعة قواعد الاستدلالأ{\displaystyle A}يُقال إنها مكتملة إذا تحقق ما يلي:

F+⊆Fأ*{\displaystyle F^{+}\subseteq F_{A}^{*}}

وبعبارة أبسط، يمكننا أن نستنتج من خلالأ{\displaystyle A}جميع التبعيات الوظيفية التي يُفترض منطقياً وجودها بواسطةF{\displaystyle F}.

البديهيات (القواعد الأساسية)

يتركR(يو){\displaystyle R(U)}ليكن مخطط علاقة على مجموعة السماتيو{\displaystyle U}من الآن فصاعدًا، سنرمز بالأحرف.X{\displaystyle X}،Y{\displaystyle Y}،Z{\displaystyle Z}أي مجموعة فرعية منيو{\displaystyle U}وباختصار، اتحاد مجموعتين من السماتX{\displaystyle X}وY{\displaystyle Y}بواسطةXY{\displaystyle XY}بدلاً من المعتادX∪Y{\displaystyle X\cup Y}; هذا الترميز قياسي إلى حد ما في نظرية قواعد البيانات عند التعامل مع مجموعات من السمات.

بديهية الانعكاسية

لوX{\displaystyle X}هي مجموعة من السمات وY{\displaystyle Y}هي مجموعة فرعية منX{\displaystyle X}، ثمX{\displaystyle X}البشرY{\displaystyle Y}. بموجب هذا،X{\displaystyle X}البشرY{\displaystyle Y}[X→Y{\displaystyle X\to Y}] تعني أنX{\displaystyle X}يحدد وظيفياًY{\displaystyle Y}.

لوY⊆X{\displaystyle Y\subseteq X}ثمX→Y{\displaystyle X\to Y}.

بديهية التضخيم

لوX{\displaystyle X}البشرY{\displaystyle Y}وZ{\displaystyle Z}هي مجموعة من السمات، إذنXZ{\displaystyle XZ}البشرYZ{\displaystyle YZ}وهذا يعني أن السمة في التبعيات لا تغير التبعيات الأساسية.

لوX→Y{\displaystyle X\to Y}، ثمXZ→YZ{\displaystyle XZ\to YZ}لأيZ{\displaystyle Z}.

بديهية التعدي

لوX{\displaystyle X}البشرY{\displaystyle Y}وY{\displaystyle Y}البشرZ{\displaystyle Z}، ثمX{\displaystyle X}البشرZ{\displaystyle Z}.

لوX→Y{\displaystyle X\to Y}وY→Z{\displaystyle Y\to Z}، ثمX→Z{\displaystyle X\to Z}.

قواعد إضافية (قواعد ثانوية)

يمكن استخلاص هذه القواعد من البديهيات المذكورة أعلاه.

التحلل

لوX→YZ{\displaystyle X\to YZ}ثمX→Y{\displaystyle X\to Y}وX→Z{\displaystyle X\to Z}.

دليل

1.X→YZ{\displaystyle X\to YZ}(منح)
2.YZ→Y{\displaystyle YZ\to Y}(الانعكاسية)
3.X→Y{\displaystyle X\to Y}(خاصية التعدي للعددين 1 و 2)

تعبير

لوX→Y{\displaystyle X\to Y}وأ→ب{\displaystyle A\to B}ثمXأ→Yب{\displaystyle XA\to YB}.

دليل

1.X→Y{\displaystyle X\to Y}(منح)
2.أ→ب{\displaystyle A\to B}(منح)
3.Xأ→Yأ{\displaystyle XA\to YA}(توسيع 1 و أ)
4.Yأ→Yب{\displaystyle YA\to YB}(زيادة العدد 2 و Y)
5.Xأ→Yب{\displaystyle XA\to YB}(خاصية التعدي للعددين 3 و 4)

الاتحاد

لوX→Y{\displaystyle X\to Y}وX→Z{\displaystyle X\to Z}ثمX→YZ{\displaystyle X\to YZ}.

دليل

1.X→Y{\displaystyle X\to Y}(منح)
2.X→Z{\displaystyle X\to Z}(منح)
3.X→XZ{\displaystyle X\to XZ}(زيادة العدد 2 و X)
4.XZ→YZ{\displaystyle XZ\to YZ}(زيادة العددين 1 و Z)
5.X→YZ{\displaystyle X\to YZ}(خاصية التعدي للعددين 3 و 4)

التعدي الزائف

لوX→Y{\displaystyle X\to Y}وYZ→دبليو{\displaystyle YZ\to W}ثمXZ→دبليو{\displaystyle XZ\to W}.

دليل

1.X→Y{\displaystyle X\to Y}(منح)
2.YZ→دبليو{\displaystyle YZ\to W}(منح)
3.XZ→YZ{\displaystyle XZ\to YZ}(زيادة العددين 1 و Z)
4.XZ→دبليو{\displaystyle XZ\to W}(خاصية التعدي للعددين 3 و 2)

تقرير المصير

أنا→أنا{\displaystyle I\to I}لأيأنا{\displaystyle I}وهذا يتبع مباشرة من بديهية الانعكاسية.

الشمولية

الخاصية التالية هي حالة خاصة من التوسيع عندماZ=X{\displaystyle Z=X}.

لوX→Y{\displaystyle X\to Y}، ثمX→XY{\displaystyle X\to XY}.

يمكن أن يحل مفهوم الشمولية محل مفهوم التوسيع كمسلمة بمعنى أنه يمكن إثبات التوسيع من خلال الشمولية جنبًا إلى جنب مع المسلمات الأخرى.

دليل

1.XZ→X{\displaystyle XZ\to X}(الانعكاسية)
2.X→Y{\displaystyle X\to Y}(منح)
3.XZ→Y{\displaystyle XZ\to Y}(خاصية التعدي للعددين 1 و 2)
4.XZ→XYZ{\displaystyle XZ\to XYZ}(امتداد من الدرجة 3)
5.XYZ→YZ{\displaystyle XYZ\to YZ}(الانعكاسية)
6.XZ→YZ{\displaystyle XZ\to YZ}(خاصية التعدي للعددين 4 و 5)

علاقة أرمسترونج

بالنظر إلى مجموعة من التبعيات الوظيفيةF{\displaystyle F}العلاقة أرمسترونغ هي علاقة تحقق جميع التبعيات الوظيفية في الإغلاقF+{\displaystyle F^{+}}وتلك التبعيات فقط. يمكن أن يكون لعلاقة أرمسترونغ ذات الحجم الأدنى لمجموعة معينة من التبعيات حجمٌ يتناسب طرديًا مع عدد السمات في التبعيات المعتبرة. [ 2 ]

مراجع

  1. ↑ ويليام وارد أرمسترونج: هياكل التبعية لعلاقات قواعد البيانات ، الصفحات 580-583. مؤتمر الاتحاد الدولي لمعالجة المعلومات، 1974.
  2. ↑ بيري، سي.؛ داود، إم.؛ فاجين، آر.؛ ستاتمان، آر. (1984). "حول بنية علاقات أرمسترونج للاعتمادات الوظيفية" (ملف PDF) . مجلة ACM . 31 : 30-46 . CiteSeerX 10.1.1.68.9320 . doi : 10.1145/2422.322414 . مؤرشف من الأصل (ملف PDF) بتاريخ 23 يوليو 2018.