مقدمة في قواعد البيانات: تصميم قواعد البيانات - الجزء الثاني
تغطي هذه الوحدة النماذج العيارية المتقدمة بما في ذلك نموذج بويس-كود (BCNF)، والاعتماديات متعددة القيم (4NF)، واعتماديات الربط (5NF)، بالإضافة إلى خوارزميات تصميم قواعد البيانات وخصائص التفكيك.
Introduction to Database: Database Design-2
This module covers advanced normal forms including Boyce-Codd Normal Form (BCNF), Multivalued Dependencies (4NF), Join Dependencies (5NF), along with database design algorithms and decomposition properties.
أهداف التعلم
- وصف اعتماديات الربط والاعتماديات متعددة القيم.
- تطبيق النماذج العيارية ذات الرتب العليا للتعامل مع الاعتماديات متعددة القيم واعتماديات الربط.
- فهم وتطبيق خوارزميات تصميم قواعد البيانات العلائقية لتحقيق التفكيك غير الفاقد وحفظ الاعتماديات.
- Describe Join dependencies and multivalued dependencies.
- Apply higher order normal forms to deal with multivalued and join dependencies.
- Understand and apply relational database design algorithms to achieve lossless decomposition and dependency preservation.
1 نموذج بويس-كود العياري (BCNF)
1 Boyce-Codd Normal Form (BCNF)
نموذج عياري أقوى من 3NF، يشترط أن يكون كل محدد (Determinant) مفتاحاً مرشحاً (Superkey).
A stronger normal form than 3NF, requiring every determinant to be a superkey.
يكون مخطط العلاقة R في نموذج بويس-كود العياري (BCNF) إذا كان لكل اعتمادية دالية X -> A متحققة في R، فإن X هو مفتاح مرشح (Superkey) لـ R.
كل علاقة في BCNF هي بالضرورة في 3NF، ولكن العكس غير صحيح.
الهدف هو الوصول إلى BCNF، ولكن قد نضطر أحياناً للتضحية بخاصية حفظ الاعتماديات لتحقيق ذلك.
A relation schema R is in Boyce-Codd Normal Form (BCNF) if whenever an FD X -> A holds in R, then X is a superkey of R.
Every BCNF relation is in 3NF, but there exist relations in 3NF that are not in BCNF.
The goal is to have each relation in BCNF, though sometimes dependency preservation must be sacrificed.
عند تفكيك علاقة للوصول إلى BCNF (باستخدام الخوارزمية 11.3)، نضمن خاصية الربط غير الفاقد (Lossless Join) ولكننا قد نفقد بعض الاعتماديات الدالية.
هذا يمثل مقايضة في تصميم قواعد البيانات: هل نفضل التخلص التام من التكرار (BCNF) أم الحفاظ على سهولة التحقق من القيود (3NF)؟
When decomposing a relation to achieve BCNF (using Algorithm 11.3), we guarantee the lossless (non-additive) join property, but we might lose dependency preservation.
This represents a fundamental trade-off in database design: strict redundancy elimination (BCNF) vs. efficient constraint checking (3NF).
| 3NF | BCNF | |
|---|---|---|
| قوة النموذجForm Strength | أضعف من BCNFWeaker than BCNF | أقوى بصرامة من 3NFStrictly stronger than 3NF |
| حفظ الاعتمادياتDependency Preservation | مضمون دائماً (خوارزمية 11.2/11.4)Always guaranteed (Alg 11.2/11.4) | قد يُفقد أثناء التفكيكMay be lost during decomposition |
| شرط المحدد (Determinant)Determinant Condition | يسمح بأن يكون المحدد غير مفتاح إذا كان التابع سمة أولية (Prime)Allows non-superkey determinant if dependent is prime | يجب أن يكون كل محدد مفتاحاً مرشحاً (Superkey)Every determinant MUST be a superkey |
لماذا قد نقبل بعلاقة في 3NF بدلاً من BCNF؟ Why might we accept a relation in 3NF instead of BCNF?
لأن التفكيك إلى BCNF قد يؤدي إلى فقدان بعض الاعتماديات الدالية، مما يجعل التحقق من قيود البيانات مكلفاً (يتطلب عمليات ربط).
Because decomposing into BCNF might cause the loss of functional dependencies, making constraint checking expensive as it would require joins.
2 خصائص التفكيك العلائقي
2 Properties of Relational Decompositions
القواعد الأساسية عند تقسيم جدول كبير إلى جداول أصغر: حفظ السمات، حفظ الاعتماديات، والربط غير الفاقد.
The core rules when splitting a large table: Attribute Preservation, Dependency Preservation, and Lossless Join.
عند تفكيك مخطط علاقة شامل (Universal Relation) إلى مجموعة من المخططات، يجب مراعاة ثلاث خصائص:
- حفظ السمات (Attribute Preservation): يجب أن تظهر كل سمة في علاقة واحدة على الأقل.
- حفظ الاعتماديات (Dependency Preservation): يجب أن يكون اتحاد إسقاطات الاعتماديات على الجداول الجديدة مكافئاً للاعتماديات الأصلية.
- الربط غير الفاقد (Lossless Join): وهو شرط إلزامي، يعني أن ربط الجداول المفككة يجب أن يعيد الجدول الأصلي تماماً دون إضافة صفوف وهمية (Spurious Tuples).
When decomposing a Universal Relation Schema into a set of schemas, three properties are evaluated:
- Attribute Preservation: Each attribute must appear in at least one relation.
- Dependency Preservation: The union of the projections of FDs on the decomposed relations must be equivalent to the original FDs.
- Lossless (Non-additive) Join: A MUST-have property ensuring that joining the decomposed tables reconstructs the exact original table without generating spurious tuples.
مصطلح 'Lossless' قد يكون مضللاً؛ فهو لا يعني عدم فقدان البيانات، بل يعني 'عدم إضافة معلومات وهمية' (Non-additive).
لاختبار التفكيك الثنائي (Binary Decomposition)، نستخدم الخاصية LJ1: يكون التفكيك غير فاقد إذا وفقط إذا كان تقاطع الجدولين يحدد وظيفياً (Functional Dependency) الأجزاء المتبقية من أحد الجدولين.
The term 'Lossless' is slightly misleading; it refers to the 'loss of information' via the 'addition of spurious information' (Non-additive).
For binary decompositions, we use Property LJ1: A decomposition {R1, R2} is lossless if and only if the intersection (R1 ∩ R2) functionally determines either (R1 - R2) or (R2 - R1).
ماذا يحدث إذا قمنا بتفكيك جدول ولم نحقق شرط الربط غير الفاقد؟ What happens if we decompose a table without satisfying the lossless join property?
عند إعادة دمج (Join) الجداول، سنحصل على صفوف إضافية غير صحيحة (Spurious Tuples) تمثل معلومات خاطئة لم تكن موجودة في الجدول الأصلي.
When joining the tables back together, we will generate spurious tuples, representing false information that did not exist in the original table.
3 الاعتماديات متعددة القيم والنموذج العياري الرابع (4NF)
3 Multivalued Dependencies and Fourth Normal Form (4NF)
يحدث عندما تحدد سمة واحدة مجموعة من القيم لسمة أخرى بشكل مستقل. 4NF يمنع هذا التكرار المستقل.
Occurs when one attribute determines a set of values for another independently. 4NF prevents this independent duplication.
الاعتمادية متعددة القيم (MVD): يُرمز لها بـ X ->> Y، وتعني أنه لقيمة معينة من X، توجد مجموعة من القيم لـ Y، وهذه المجموعة مستقلة تماماً عن السمات الأخرى في العلاقة.
النموذج العياري الرابع (4NF): تكون العلاقة في 4NF إذا كان لكل اعتمادية متعددة القيم غير بديهية (Nontrivial MVD) X ->> Y، يكون X مفتاحاً مرشحاً (Superkey).
Multivalued Dependency (MVD): Denoted as X ->> Y, it specifies that for a given value of X, there is a set of values for Y, and this set is completely independent of other attributes in the relation.
Fourth Normal Form (4NF): A relation is in 4NF if for every nontrivial MVD X ->> Y, X is a superkey.
تعتبر MVD بديهية (Trivial) إذا كان Y مجموعة جزئية من X، أو إذا كان اتحاد X و Y يساوي العلاقة بأكملها R.
لحل مشكلة الجداول التي ليست في 4NF، نستخدم خوارزمية التفكيك (Algorithm 11.5) التي تقسم العلاقة إلى علاقتين: (Q - Y) و (X ∪ Y)، مما يضمن خاصية الربط غير الفاقد.
An MVD is considered trivial if Y is a subset of X, or if X ∪ Y = R.
To normalize a relation not in 4NF, we use Algorithm 11.5, which decomposes the relation into two schemas: (Q - Y) and (X ∪ Y), ensuring the non-additive join property.
لماذا لا تكفي BCNF للتعامل مع الاعتماديات متعددة القيم؟ Why isn't BCNF sufficient to handle Multivalued Dependencies?
لأن BCNF تتعامل فقط مع الاعتماديات الدالية (FDs). الاعتماديات متعددة القيم لا تنتهك BCNF لأنها لا تحدد قيمة واحدة، بل مجموعة قيم، مما يسبب تكراراً هائلاً للبيانات المستقلة.
Because BCNF only deals with Functional Dependencies (FDs). MVDs do not violate BCNF since they determine a set of values rather than a single value, leading to massive redundancy of independent facts.
4 اعتماديات الربط والنموذج العياري الخامس (5NF)
4 Join Dependencies and Fifth Normal Form (5NF)
يتعامل مع الحالات التي لا يمكن فيها تقسيم الجدول إلى جدولين دون فقدان المعلومات، بل يجب تقسيمه إلى 3 جداول أو أكثر.
Deals with cases where a table cannot be split into two without losing info, but must be split into 3 or more tables.
اعتمادية الربط (JD): يُرمز لها بـ JD(R1, R2, ..., Rn)، وتعني أن العلاقة R يجب أن تمتلك تفكيكاً غير فاقد إلى n من العلاقات.
الاعتمادية متعددة القيم (MVD) هي حالة خاصة من JD حيث n = 2.
النموذج العياري الخامس (5NF): يُعرف أيضاً بـ PJNF، وتكون العلاقة في 5NF إذا كان لكل اعتمادية ربط غير بديهية، كل Ri هو مفتاح مرشح (Superkey) لـ R.
Join Dependency (JD): Denoted by JD(R1, R2, ..., Rn), it specifies that relation R must have a non-additive join decomposition into n relations.
An MVD is a special case of a JD where n = 2.
Fifth Normal Form (5NF): Also known as Project-Join Normal Form (PJNF). A relation is in 5NF if for every nontrivial JD, every Ri is a superkey of R.
تعتبر 5NF معقدة جداً في التطبيق العملي وتستخدم غالباً في الإطار النظري.
تحدث اعتمادية الربط عندما يكون هناك قيد دوري بين ثلاث سمات أو أكثر لا يمكن تمثيله بواسطة MVDs.
التفكيك إلى 5NF يضمن عدم وجود أي شذوذ ناتج عن عمليات الربط المتعددة.
5NF is highly complex in practical application and mostly theoretical.
A JD occurs when there is a cyclic constraint among three or more attributes that cannot be expressed by MVDs.
Decomposing to 5NF ensures no anomalies arise from multi-way joins.
ما هي العلاقة بين MVD و JD؟ What is the relationship between MVD and JD?
الاعتمادية متعددة القيم (MVD) هي ببساطة حالة خاصة من اعتمادية الربط (JD) حيث يتم تفكيك العلاقة إلى جزأين فقط (n=2).
A Multivalued Dependency (MVD) is simply a special case of a Join Dependency (JD) where the relation is decomposed into exactly two parts (n=2).
5 اعتماديات التضمين (Inclusion Dependencies)
5 Inclusion Dependencies
قواعد تضمن أن القيم الموجودة في عمود معين يجب أن تكون موجودة مسبقاً في عمود آخر (مثل المفاتيح الأجنبية).
Rules ensuring that values in one column must already exist in another column (like Foreign Keys).
اعتمادية التضمين: يُرمز لها بـ R.X < S.Y، وهي تحدد قيداً ينص على أن مجموعة القيم في سمات X من العلاقة R يجب أن تكون مجموعة جزئية من القيم في سمات Y من العلاقة S.
تُستخدم هذه الاعتماديات لإضفاء الطابع الرسمي على قيود التكامل المرجعي (Referential Integrity) وعلاقات الفئة/الفئة الفرعية (Class/Subclass).
Inclusion Dependency: Denoted as R.X < S.Y, it specifies a constraint that the set of values in attributes X of relation R must be a subset of the values in attributes Y of relation S.
These are used to formalize referential integrity constraints (Foreign Keys) and class/subclass relationships.
قواعد الاستدلال لاعتماديات التضمين تشمل:
- الانعكاسية (Reflexivity): R.X < R.X.
- تطابق السمات (Attribute Correspondence): إذا كان R.X < S.Y فإن كل سمة تقابل نظيرتها.
- التعدي (Transitivity): إذا كان R.X < S.Y و S.Y < T.Z فإن R.X < T.Z.
Inference rules for inclusion dependencies include:
- Reflexivity: R.X < R.X.
- Attribute Correspondence: If R.X < S.Y, corresponding attributes match.
- Transitivity: If R.X < S.Y and S.Y < T.Z, then R.X < T.Z.
كيف تختلف اعتمادية التضمين عن الاعتمادية الدالية؟ How does an inclusion dependency differ from a functional dependency?
الاعتمادية الدالية تفرض قيوداً داخل نفس الجدول (سمة تحدد سمة أخرى)، بينما اعتمادية التضمين تفرض قيوداً بين جدولين مختلفين (قيم في جدول يجب أن تظهر في جدول آخر).
A functional dependency enforces constraints within the SAME table (one attribute determines another), whereas an inclusion dependency enforces constraints BETWEEN two tables (values in one table must exist in another).
6 نموذج المجال والمفتاح العياري (DKNF)
6 Domain-Key Normal Form (DKNF)
النموذج العياري 'المثالي' حيث يتم فرض جميع القيود ببساطة عن طريق قيود المفاتيح والمجالات فقط.
The 'ultimate' normal form where all constraints are enforced simply by key and domain constraints.
تكون العلاقة في DKNF إذا كانت جميع القيود والاعتماديات التي يجب أن تتحقق يمكن فرضها ببساطة عن طريق فرض قيود المجال (Domain Constraints) وقيود المفاتيح (Key Constraints) على العلاقة.
الفكرة هي تحديد 'النموذج العياري النهائي' الذي يأخذ في الاعتبار جميع أنواع الاعتماديات.
A relation schema is in DKNF if all constraints and dependencies that should hold can be enforced simply by enforcing the domain constraints and key constraints on the relation.
The idea is to specify the 'ultimate normal form' that accounts for all possible types of dependencies.
على الرغم من أن DKNF يمثل الحالة المثالية لتصميم قواعد البيانات (حيث لا توجد شذوذ إدخال أو حذف أو تعديل)، إلا أن فائدته العملية محدودة جداً.
من الصعب، بل من المستحيل أحياناً، تحويل مخطط قاعدة بيانات معقد إلى DKNF في العالم الحقيقي.
Although DKNF represents the theoretical ideal for database design (guaranteeing no insertion, deletion, or modification anomalies), its practical utility is highly limited.
It is often difficult or impossible to convert a complex real-world database schema into DKNF.
لماذا لا نستخدم DKNF في جميع قواعد البيانات؟ Why don't we use DKNF in all databases?
لأنه نموذج نظري بحت، وتطبيقه على قواعد البيانات المعقدة في العالم الحقيقي غالباً ما يكون مستحيلاً أو غير عملي.
Because it is a purely theoretical model, and applying it to complex real-world databases is often impossible or highly impractical.