Design: Normalization & FDs التصميم: Normalization & FDs

The science of Good Design. Eliminating redundancy and anomalies using Functional Dependencies and Normal Forms. علم التصميم الجيد. القضاء على التكرار (Redundancy) والعيوب (Anomalies) باستخدام Functional Dependencies و Normal Forms.

Anomalies (Insert/Delete/Update) Anomalies (الإضافة/الحذف/التحديث) Functional Dependency ($X \to Y$) Functional Dependency ($X \to Y$) Armstrong's Axioms Armstrong's Axioms 1NF / 2NF / 3NF / BCNF 1NF / 2NF / 3NF / BCNF Prime Attributes Prime Attributes

Why Normalize? (Informal Rules) لماذا نستخدم Normalization؟ (قواعد غير رسمية)

Before math, we have intuitive "smells" of bad design. The goal is to measure quality and remove Redundancy. قبل الرياضيات، لدينا مؤشرات حدسية للتصميم السيء. الهدف هو قياس الجودة وإزالة Redundancy.

1. Semantics 1. Semantics (الدلالات)

Attributes in a table should belong together conceptually. Don't mix "Employee" facts with "Department" facts in one massive table. السمات في الجدول يجب أن تنتمي لبعضها مفاهيمياً. لا تخلط حقائق "Employee" مع حقائق "Department" في جدول ضخم واحد.

2. Redundancy & Anomalies 2. Redundancy & Anomalies (التكرار والعيوب)

Redundancy wastes space and causes Update Anomalies: التكرار يهدر المساحة ويسبب Update Anomalies (عيوب التحديث):

  • Insert:Insert: Cannot add a new Dept if no Employee works there yet. لا يمكن إضافة Dept جديد إذا لم يعمل به موظف بعد.
  • Delete:Delete: If the last Employee leaves, the Dept info is lost. إذا غادر آخر موظف، تضيع معلومات الـ Dept.
  • Modification:Modification: Updating Dept Manager requires changing 1000 Employee rows. تحديث مدير الـ Dept يتطلب تغيير 1000 صف للموظفين.

3. NULL Values 3. NULL Values (القيم الفارغة)

Avoid attributes that are frequently NULL. They waste space and complicate aggregation (COUNT, AVG). Place them in separate tables. تجنب السمات التي تكون NULL بشكل متكرر. فهي تهدر المساحة وتعقد عمليات التجميع (COUNT, AVG). ضعها في جداول منفصلة.

4. Spurious Tuples 4. Spurious Tuples (الصفوف الزائفة)

Design schemas so they can be joined with equality on Primary/Foreign Keys. Bad joins on non-keys create "fake" (spurious) data. صمم المخططات بحيث يمكن ربطها بالمساواة باستخدام Primary/Foreign Keys. الربط السيء على غير المفاتيح ينشئ بيانات "زائفة" (spurious).

Functional Dependencies Functional Dependencies (الاعتماد الوظيفي)

Definition: $X \to Y$ التعريف: $X \to Y$

A constraint between two sets of attributes $X$ and $Y$.
It states: If two tuples have the same value for $X$, they MUST have the same value for $Y$.
"X determines Y". قيد بين مجموعتين من السمات $X$ و $Y$.
ينص على: إذا كان لصفين نفس القيمة لـ $X$، يجب أن يكون لهما نفس القيمة لـ $Y$.
"X يحدد Y".

$\{SSN\} \to \{Ename, Bdate, Address\}$
$\{Vin\_Number\} \to \{CarModel, Year\}$

Inference Rules (Armstrong's Axioms) قواعد الاستنتاج (Armstrong's Axioms)

1. Reflexive 1. Reflexive (انعكاسي) If $Y \subseteq X$, then $X \to Y$.
(e.g., $\{SSN, Name\} \to SSN$) إذا كان $Y \subseteq X$، فإن $X \to Y$.
(مثال: $\{SSN, Name\} \to SSN$)
2. Augmentation 2. Augmentation (الزيادة) If $X \to Y$, then $XZ \to YZ$. إذا كان $X \to Y$، فإن $XZ \to YZ$.
3. Transitive 3. Transitive (التعدي) If $X \to Y$ and $Y \to Z$, then $X \to Z$. إذا كان $X \to Y$ و $Y \to Z$، فإن $X \to Z$.

Normalization Steps خطوات Normalization

Normalization is the process of decomposing bad relations into good ones by breaking FDs. Normalization هو عملية تفكيك العلاقات السيئة إلى علاقات جيدة عن طريق كسر الـ FDs.

1NF (First Normal Form) 1NF (First Normal Form)

The Foundation الأساس

Rule: All attribute values must be Atomic.
No composite attributes (Address), no multivalued attributes (Phones), no nested relations. القاعدة: جميع قيم السمات يجب أن تكون Atomic (ذرية).
لا سمات مركبة (Address)، لا سمات متعددة القيم (Phones)، لا علاقات متداخلة.

2NF (Second Normal Form) 2NF (Second Normal Form)

Removes Partial Dep يزيل Partial Dep

Prerequisite: Must be in 1NF.
Rule: Every Non-Prime attribute must be Fully Functionally Dependent on the Primary Key.
Violation: If PK is $\{A, B\}$ and $A \to C$, then $C$ is partially dependent. Move $C$ to a new table with $A$. المتطلب السابق: يجب أن يكون في 1NF.
القاعدة: كل سمة Non-Prime يجب أن تكون معتمدة وظيفياً بالكامل (Fully Functionally Dependent) على الـ Primary Key.
انتهاك: إذا كان PK هو $\{A, B\}$ و $A \to C$، فإن $C$ يعتمد جزئياً. انقل $C$ إلى جدول جديد مع $A$.

3NF (Third Normal Form) 3NF (Third Normal Form)

Removes Transitive Dep يزيل Transitive Dep

Prerequisite: Must be in 2NF.
Rule: No Transitive Dependency.
Violation: If $X \to Y$ and $Y \to Z$ (where $Y$ is not a key), then $Z$ depends transitively on $X$. Move $Z$ to a new table with $Y$. المتطلب السابق: يجب أن يكون في 2NF.
القاعدة: لا يوجد Transitive Dependency (اعتماد متعدي).
انتهاك: إذا كان $X \to Y$ و $Y \to Z$ (حيث $Y$ ليس مفتاحاً)، فإن $Z$ يعتمد بشكل متعدي على $X$. انقل $Z$ إلى جدول جديد مع $Y$.

BCNF (Boyce-Codd) BCNF (Boyce-Codd)

Stricter 3NF 3NF أكثر صرامة

Rule: For every functional dependency $X \to A$, $X$ must be a Superkey.
Handles cases where a prime attribute depends on a non-prime attribute (rare but possible in 3NF). القاعدة: لكل اعتماد وظيفي $X \to A$، يجب أن يكون $X$ عبارة عن Superkey.
يعالج الحالات التي تعتمد فيها سمة أولية (prime) على سمة غير أولية (نادرة ولكن ممكنة في 3NF).

Key Terminology مصطلحات رئيسية

Superkey Superkey A set of attributes that uniquely identifies a tuple. (Can contain extra/redundant attributes). مجموعة من السمات التي تحدد الصف بشكل فريد. (يمكن أن تحتوي على سمات إضافية/زائدة).
Candidate Key Candidate Key A minimal Superkey. If you remove any attribute, it's no longer unique. هو minimal Superkey. إذا أزلت أي سمة، لم يعد فريداً.
Primary Key Primary Key The Candidate Key chosen to identify tuples in the schema. الـ Candidate Key المختار لتعريف الصفوف في المخطط.
Prime Attribute Prime Attribute An attribute that is part of ANY Candidate Key.
Non-Prime: Not part of any candidate key. سمة تكون جزءاً من أي Candidate Key.
Non-Prime: ليست جزءاً من أي candidate key.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: 2NF on Single Keys فخ: 2NF مع المفاتيح الفردية

"Check if this table with PK `UserID` is in 2NF."
Shortcut: If the Primary Key is a single attribute (not composite), the table is automatically in 2NF. Partial dependency requires a composite key. "تحقق مما إذا كان هذا الجدول مع PK `UserID` في 2NF."
اختصار: إذا كان الـ Primary Key سمة واحدة (ليس مركباً)، فإن الجدول تلقائياً في 2NF. الاعتماد الجزئي يتطلب مفتاحاً مركباً.

TRAP: 3NF vs BCNF فخ: 3NF مقابل BCNF

Most tables in 3NF are also in BCNF. The only time they differ is if:
1. There are multiple candidate keys.
2. The keys are composite.
3. They overlap. معظم الجداول في 3NF هي أيضاً في BCNF. الحالة الوحيدة التي يختلفان فيها هي إذا:
1. كان هناك عدة candidate keys.
2. المفاتيح مركبة.
3. تتداخل فيما بينها.

SECRET: The "Prime" Trick سر: خدعة "Prime"

In 3NF, $X \to A$ is allowed if $A$ is a Prime Attribute (part of a candidate key), even if $X$ is not a key.
BCNF removes this loophole: $X$ MUST be a Superkey, even if $A$ is prime. في 3NF، يُسمح بـ $X \to A$ إذا كان $A$ عبارة عن Prime Attribute (جزء من candidate key)، حتى لو لم يكن $X$ مفتاحاً.
BCNF تزيل هذه الثغرة: $X$ يجب أن يكون Superkey، حتى لو كان $A$ أولياً.

KEY CONCEPT: Decomposition مفهوم أساسي: Decomposition

Normalization is a decomposition process.
Rule: Always decompose into tables that preserve the original data (Lossless Join) and preserve the dependencies (Dependency Preservation). التطبيع (Normalization) هو عملية تفكيك.
قاعدة: قم دائماً بالتفكيك إلى جداول تحفظ البيانات الأصلية (Lossless Join) وتحفظ التبعيات (Dependency Preservation).