مفتاح المرشح

المفتاح المرشح ، أو ببساطة المفتاح ، لقاعدة البيانات العلائقية هو أي مجموعة من الأعمدة التي تحتوي على مجموعة فريدة من القيم في كل صف، مع القيد الإضافي المتمثل في أن إزالة أي عمود يمكن أن ينتج عنه مجموعات مكررة من القيم.

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

تُسمى مفاتيح المرشح المحددة أحيانًا بالمفاتيح الأساسية أو المفاتيح الثانوية أو المفاتيح البديلة . تُسمى الأعمدة في مفتاح المرشح بالسمات الأساسية ، ^{[ 3 ]} ويُسمى العمود الذي لا يظهر في أي مفتاح مرشح بالسمات غير الأساسية .

كل علاقة بدون قيم فارغة سيكون لها مفتاح مرشح واحد على الأقل: بما أنه لا يمكن أن تكون هناك صفوف مكررة، فإن مجموعة جميع الأعمدة هي مفتاح فائق، وإذا لم يكن ذلك الحد الأدنى، فستكون هناك مجموعة فرعية من ذلك الحد الأدنى.

توجد تبعية وظيفية من المفتاح المرشح إلى جميع السمات في العلاقة.

المفاتيح الفائقة للعلاقة هي جميع الطرق الممكنة لتحديد صف معين. أما المفاتيح المرشحة فهي أصغر مجموعة فرعية من كل مفتاح فائق، ولذلك فهي مفهوم مهم لتصميم مخطط قاعدة البيانات .

يمكن توضيح تعريف المفاتيح المرشحة بالمثال (المجرد) التالي. لنفترض متغير علاقة ( relvar ) R ذو سمات ( A ، B ، C ، D ) والذي لا يحتوي إلا على القيمتين القانونيتين التاليتين r1 و r2 :

هنا يختلف r2 عن r1 فقط في قيم A و D للصف الأخير.

بالنسبة لـ r1، تتمتع المجموعات التالية بخاصية التفرد، أي أنه لا يوجد صفان مختلفان في المثال لهما نفس قيم السمات في المجموعة:

{أ، ب}، {أ، ج}، {ب، ج}، {أ، ب، ج}، {أ، ب، د}، {أ، ج، د}، {ب، ج، د}، {أ، ب، ج، د}

بالنسبة لـ r2، تنطبق خاصية التفرد على المجموعات التالية؛

{ب، ج}، {ب، د}، {ج، د}، {أ، ب، ج}، {أ، ب، د}، {أ، ج، د}، {ب، ج، د}، {أ، ب، ج، د}

بما أن المفاتيح الفائقة لمتغير علائقي هي مجموعات السمات التي تتمتع بخاصية التفرد لجميع القيم القانونية لهذا المتغير، ولأننا نفترض أن r1 و r2 هما جميع القيم القانونية التي يمكن أن يأخذها R ، فيمكننا تحديد مجموعة المفاتيح الفائقة لـ R عن طريق أخذ تقاطع القائمتين:

{ب، ج}، {أ، ب، ج}، {أ، ب، د}، {أ، ج، د}، {ب، ج، د}، {أ، ب، ج، د}

وأخيرًا، نحتاج إلى تحديد تلك المجموعات التي لا يوجد لها مجموعة فرعية مناسبة في القائمة، وهي في هذه الحالة:

{ب، ج}، {أ، ب، د}، {أ، ج، د}

هذه هي بالفعل المفاتيح المرشحة لـ relvar R.

علينا مراعاة جميع العلاقات التي يمكن إسنادها إلى متغير العلاقة لتحديد ما إذا كانت مجموعة معينة من السمات مفتاحًا مرشحًا. على سبيل المثال، لو اقتصرنا على العلاقة r1 فقط ، لاستنتجنا أن {A,B} مفتاح مرشح، وهذا غير صحيح. مع ذلك، قد نستنتج من هذه العلاقة أن مجموعة معينة ليست مفتاحًا مرشحًا، لأنها لا تتمتع بخاصية التفرد (مثال: {A,D} للعلاقة r1 ). تجدر الإشارة إلى أن وجود مجموعة جزئية فعلية من مجموعة تتمتع بخاصية التفرد لا يُعدّ دليلًا قاطعًا على أن المجموعة الكلية ليست مفتاحًا مرشحًا. على وجه الخصوص، في حالة العلاقة الفارغة، تتمتع كل مجموعة جزئية من العنوان بخاصية التفرد، بما في ذلك المجموعة الفارغة نفسها.

يمكن حساب مجموعة جميع المفاتيح المرشحة، على سبيل المثال، من مجموعة التبعيات الوظيفية . ولتحقيق هذه الغاية، نحتاج إلى تعريف إغلاق السمة.${\displaystyle \alpha ^{+}}$لمجموعة سمات${\displaystyle \alpha }$المجموعة${\displaystyle \alpha ^{+}}$يحتوي على جميع السمات التي تتضمنها وظيفيًا${\displaystyle \alpha }$.

من السهل جدًا إيجاد مفتاح مرشح واحد. نبدأ بمجموعة${\displaystyle \alpha }$من السمات، حاول إزالة كل سمة على حدة. إذا بقي إغلاق السمة كما هو بعد إزالتها، فهذا يعني أن هذه السمة غير ضرورية ويمكننا إزالتها نهائيًا. نسمي النتيجة${\displaystyle {\text{minimize}}(\alpha )}$. لو${\displaystyle \alpha }$إذا كانت مجموعة جميع السمات${\displaystyle {\text{minimize}}(\alpha )}$هو مفتاح مرشح.

في الواقع، يمكننا اكتشاف كل مفتاح مرشح باستخدام هذه العملية ببساطة عن طريق تجربة كل ترتيب ممكن لإزالة السمات. ومع ذلك، هناك العديد من التباديل الأخرى للسمات (${\displaystyle n!}$) من المجموعات الفرعية (${\displaystyle 2^{n}}$). أي أن العديد من ترتيبات السمات ستؤدي إلى نفس المفتاح المرشح.

توجد صعوبة جوهرية أمام الخوارزميات الفعالة لحساب المفاتيح المرشحة: فبعض مجموعات التبعيات الوظيفية تؤدي إلى عدد هائل من المفاتيح المرشحة. لنأخذ على سبيل المثال...${\displaystyle 2\cdot n}$التبعيات الوظيفية ${\displaystyle \{A_{i}\rightarrow B_{i}:i\in \{1,\dots ,n\}\}\cup \{B_{i}\rightarrow A_{i}:i\in \{1,\dots ,n\}\}}$ مما ينتج عنه${\displaystyle 2^{n}}$مفاتيح المرشحين: ${\displaystyle \{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}}$أي أن أفضل ما يمكننا توقعه هو خوارزمية تتسم بالكفاءة فيما يتعلق بعدد المفاتيح المرشحة.

تعمل الخوارزمية التالية في وقت متعدد الحدود بالنسبة لعدد المفاتيح المرشحة والتبعيات الوظيفية: ^{[ 4 ]}

دالة البحث عن المفاتيح المرشحة (A، F) /* A هي مجموعة جميع السمات و F هي مجموعة التبعيات الوظيفية */ K[0] := minimize(A); n := 1; /* عدد المفاتيح المعروفة حتى الآن */ i := 0; /* المفتاح الذي تتم معالجته حاليًا */ بينما i < n ، لكل α → β ∈ F، نفّذ /* إنشاء مفتاح محتمل جديد من المفتاح المعروف السابق والملف الحالي */ S := α ∪ (K[i] − β); /* ابحث عما إذا كان المفتاح المحتمل الجديد جزءًا من المفاتيح المعروفة بالفعل */ تم العثور على := خطأ؛ for j := 0 to n-1 do if K[j] ⊆ S then found := true; /* إذا لم يكن موجودًا، فأضفه */ إذا لم يتم العثور عليه K[n] := minimize(S); n := n + 1; i := i + 1 إرجاع K

الفكرة وراء الخوارزمية هي أنه عند إعطاء مفتاح مرشح${\displaystyle K_{i}}$ والاعتماد الوظيفي${\displaystyle \alpha \rightarrow \beta }$، ويؤدي تطبيق التبعية الوظيفية بشكل عكسي إلى المجموعة ${\displaystyle \alpha \cup (K_{i}\setminus \beta )}$وهو مفتاح أيضًا. مع ذلك، قد يكون مُغطى بمفاتيح مرشحة أخرى معروفة مسبقًا. (تتحقق الخوارزمية من هذه الحالة باستخدام المتغير "found"). إذا لم يكن كذلك، فإن تقليل المفتاح الجديد يُنتج مفتاحًا مرشحًا جديدًا. الفكرة الأساسية هي أنه يمكن إنشاء جميع المفاتيح المرشحة بهذه الطريقة.

• المفتاح البديل ، هو مفتاح لم يتم اختياره كمفتاح أساسي من بين المفاتيح المرشحة لعلاقة ما
• مفتاح مركب
• تطبيع قاعدة البيانات
• المفتاح الأساسي
• قاعدة بيانات علائقية
• مفتاح فائق
• المُتضمن الأولي هو المفهوم المقابل للمفتاح المرشح في المنطق البولياني

• ديت، كريستوفر (2003). "5: النزاهة". مقدمة في أنظمة قواعد البيانات . أديسون-ويسلي. ص 268-276 . ISBN  978-0-321-18956-1.

• أنظمة إدارة قواعد البيانات العلائقية - تصميم قواعد البيانات - المصطلحات المرجعية - المفاتيح : نظرة عامة على الأنواع المختلفة من المفاتيح في نظام إدارة قواعد البيانات العلائقية (RDBMS).