Normalizationالتطبيع
مقدمة الفصل
ماذا ستتعلم في هذا الفصل
- The four informal design guidelines: semantics, redundancy and update anomalies, nulls, spurious tuples.
- Functional dependencies: definition, testing them on an instance, superkeys and candidate keys.
- First, second and third normal forms, full, partial and transitive dependencies.
- Boyce-Codd normal form, and normalizing example relations step by step.
أقسام الفصل
- 1Informal design guidelinesإرشادات التصميم غير الرسمية
- 2Normalization and normal formsالتطبيع والصيغ الطبيعية
- 3Functional dependenciesالاعتماديات الوظيفية
- 4FDs and keysالاعتماديات والمفاتيح
- 5First normal formالصيغة الطبيعية الأولى
- 6Second normal formالصيغة الطبيعية الثانية
- 7Third normal formالصيغة الطبيعية الثالثة
- 8Boyce-Codd normal formصيغة بويس-كود
- 9Worked normalization examplesأمثلة محلولة في التطبيع
تلميح: استخدم أسهم لوحة المفاتيح للتنقل بين الشرائح.
Four informal design guidelinesإرشادات التصميم
- Relational database design: the grouping of attributes to form "good" relation schemas (slide 2).
- Guideline 1 rests on: each tuple in a relation should represent one entity or relationship instance (slide 4).
Design goals: information preservation and minimum redundancy; a good design has minimum redundancy and minimum update anomalies.
- 1Semantics of the relation attributesدلالة الصفاتEasy to explain; **do not combine attributes from multiple entity and relationship types** into one relation.
- 2Reduce redundant informationتقليل التكرارRedundancy wastes storage and causes **insertion, deletion and modification anomalies**.
- 3Reduce null valuesتقليل القيم الفارغة**As few NULLs as possible**; frequently-NULL attributes can go to separate relations (with the primary key).
- 4Disallow spurious tuplesمنع الصفوف الزائفةSatisfy the **lossless join condition**: no spurious tuples from joining relations.
Reasons for nulls (slide 9)
- Attribute not applicable or invalid.
- Attribute value unknown (may exist).
- Value known to exist, but unavailable.
Examples: redundancy and update anomaliesأمثلة التكرار
Informal design guidelines
| Project_NUM | Project_name | EMP_NUM | EMP_name | Job_class | CHG_Hour | Hours |
|---|---|---|---|---|---|---|
| 10 | Evergreen | 103 | June E. Arbough | Engineer | 89 | 23 |
| 10 | لا تذكر الشرائح شيئًا هنا. | 104 | John G. News | Analyst | 78 | 22 |
| 10 | لا تذكر الشرائح شيئًا هنا. | 111 | David h. Senior | General support | 12 | 12 |
| 12 | Amber Wave | 120 | Wliliam Smith | Application design (cut off on the slide) | 33 | 56 |
| 12 | لا تذكر الشرائح شيئًا هنا. | 111 | David h. Senior | General support | 45 | 54 |
| 12 | لا تذكر الشرائح شيئًا هنا. | 123 | Alice K. Johonson | لا تذكر الشرائح شيئًا هنا. | 65 | 12 |
| 13 | Rolling Tide | 111 | David h. Senior | General support | 19 | 8 |
| 13 | لا تذكر الشرائح شيئًا هنا. | 100 | James Formmer | Programmer | 44 | 28 |
| 13 | لا تذكر الشرائح شيئًا هنا. | 103 | June E. Arbough | Engineer | 89 | 11 |
| null | null | 140 | Darlene Smith | DBMA | 100 | null |
| Relation | Attributes |
|---|---|
| EMPLOYEE | Ename, Ssn (P.K.), Bdate, Address, Dnumber (F.K.) |
| DEPARTMENT | Dname, Dnumber (P.K.), Dmgr_ssn (F.K.) |
| (a) EMP_DEPT | Ename, Ssn, Bdate, Address, Dnumber, Dname, Dmgr_ssn |
| (b) EMP_PROJ | Ssn, Pnumber, Hours, Ename, Pname, Plocation |
| Ssn | Pnumber | Hours | Ename | Pname | Plocation |
|---|---|---|---|---|---|
| 123456789 | 1 | 32.5 | Smith, John B. | ProductX | Bellaire |
| 123456789 | 2 | 7.5 | Smith, John B. | ProductY | Sugarland |
| 666884444 | 3 | 40.0 | Narayan, Ramesh K. | ProductZ | Houston |
| 453453453 | 1 | 20.0 | English, Joyce A. | ProductX | Bellaire |
| 453453453 | 2 | 20.0 | English, Joyce A. | ProductY | Sugarland |
| 333445555 | 2 | 10.0 | Wong, Franklin T. | ProductY | Sugarland |
| 333445555 | 3 | 10.0 | Wong, Franklin T. | ProductZ | Houston |
| 333445555 | 10 | 10.0 | Wong, Franklin T. | Computerization | Stafford |
| 333445555 | 20 | 10.0 | Wong, Franklin T. | Reorganization | Houston |
| 999887777 | 30 | 30.0 | Zelaya, Alicia J. | Newbenefits | Stafford |
| 999887777 | 10 | 10.0 | Zelaya, Alicia J. | Computerization | Stafford |
| 987987987 | 10 | 35.0 | Jabbar, Ahmad V. | Computerization | Stafford |
| 987987987 | 30 | 5.0 | Jabbar, Ahmad V. | Newbenefits | Stafford |
| 987654321 | 30 | 20.0 | Wallace, Jennifer S. | Newbenefits | Stafford |
| 987654321 | 20 | 15.0 | Wallace, Jennifer S. | Reorganization | Houston |
| 888665555 | 20 | Null | Borg, James E. | Reorganization | Houston |
Spurious tuplesالصفوف الزائفة
Informal design guidelines
| Ename | Plocation |
|---|---|
| Smith, John B. | Bellaire |
| Smith, John B. | Sugarland |
| Narayan, Ramesh K. | Houston |
| English, Joyce A. | Bellaire |
| English, Joyce A. | Sugarland |
| Wong, Franklin T. | Sugarland |
| Wong, Franklin T. | Houston |
| Wong, Franklin T. | Stafford |
| Ssn | Pnumber | Hours | Pname | Plocation |
|---|---|---|---|---|
| 123456789 | 1 | 32.5 | ProductX | Bellaire |
| 123456789 | 2 | 7.5 | ProductY | Sugarland |
| 666884444 | 3 | 40.0 | ProductZ | Houston |
| 453453453 | 1 | 20.0 | ProductX | Bellaire |
| 453453453 | 2 | 20.0 | ProductY | Sugarland |
| 333445555 | 2 | 10.0 | ProductY | Sugarland |
| 333445555 | 3 | 10.0 | ProductZ | Houston |
| 333445555 | 10 | 10.0 | Computerization | Stafford |
| 333445555 | 20 | 10.0 | Reorganization | Houston |
| Ssn | Pnumber | Hours | Pname | Plocation | Ename | Spurious |
|---|---|---|---|---|---|---|
| 123456789 | 1 | 32.5 | ProductX | Bellaire | Smith, John B. | |
| 123456789 | 1 | 32.5 | ProductX | Bellaire | English, Joyce A. | * |
| 123456789 | 2 | 7.5 | ProductY | Sugarland | Smith, John B. | |
| 123456789 | 2 | 7.5 | ProductY | Sugarland | English, Joyce A. | * |
| 123456789 | 2 | 7.5 | ProductY | Sugarland | Wong, Franklin T. | * |
| 666884444 | 3 | 40.0 | ProductZ | Houston | Narayan, Ramesh K. | |
| 666884444 | 3 | 40.0 | ProductZ | Houston | Wong, Franklin T. | * |
What normalization isالتطبيع
Normalization and normal forms
The process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations.
A condition using keys and functional dependencies of a relation to certify whether a relation schema is in a particular normal form.
- Normalization is done to achieve the desirable properties: minimum redundancy and minimum update anomalies (slide 12).
Normal forms (slide 14)
- 1NF
- 2NF
- 3NF
- BCNF
- 4NF
- 5NF
Functional dependenciesالاعتماديات الوظيفية
Functional dependencies (slide 13)
- FDs are used to specify formal measures of the "goodness" of relational designs.
- FDs and keys are used to define normal forms for relations.
- FDs are constraints that are derived from the meaning and interrelationships of the data attributes.
Holds on R if and only if for any legal relation r(R), whenever two tuples t1 and t2 agree on α, they also agree on β: t1[α] = t2[α] ⇒ t1[β] = t2[β]. Equivalently, each value of A is associated with exactly one value of B (A the determinant, B the dependent).
- Slide 15 draws them on EMP_PROJ (Ssn, Pnumber, Hours, Ename, Pname, Plocation): FD1 {Ssn, Pnumber} → Hours; FD2 Ssn → Ename; FD3 Pnumber → Pname, Plocation.
المسألة
r(A, B) = (1, 4), (1, 5), (3, 7). Does A → B hold? Does B → A hold? (slide 16)
خطوات الحل
- A → B: the two tuples with A = 1 have B = 4 and B = 5 — they agree on A but not on B.
- B → A: the B values 4, 5, 7 are all different, so no two tuples agree on B.
النتيجة
A → B does NOT hold; B → A does hold.
Testing FDs on an instanceاختبار الاعتماديات
Functional dependencies
| A | B | C | D |
|---|---|---|---|
| a1 | b1 | c1 | d1 |
| a1 | b2 | c1 | d2 |
| a2 | b2 | c2 | d2 |
| a2 | b3 | c2 | d3 |
| a3 | b3 | c2 | d4 |
| building | room_number | capacity |
|---|---|---|
| Packard | 101 | 500 |
| Painter | 514 | 10 |
| Taylor | 3128 | 70 |
| Watson | 100 | 30 |
| Watson | 120 | 50 |
المسألة
Check each candidate FD against the five tuples.
خطوات الحل
- A → B: a1 appears with b1 and b2 — fails. A → D: a1 with d1 and d2 — fails.
- A → C: a1 → c1, a2 → c2, a3 → c2 — every A value has one C value — holds.
- B → C: b2 with c1 and c2 — fails. B → D: b3 with d3 and d4 — fails. C → D: c1 with d1 and d2 — fails.
النتيجة
Only A → C holds on this instance.
Slide 20
- StaffNo → position — a 1:1 or M:1 relationship between attributes in a relation: SL21 → Manager. Position is functionally dependent on StaffNo.
- position does not determine StaffNo — a 1:M relationship: Manager → SL21 and SG5. StaffNo is NOT functionally dependent on position.
FDs and keysالاعتماديات والمفاتيح
K is a superkey for R if and only if K → R.
K is a candidate key if and only if K → R, and for no α ⊂ K, α → R.
- FDs express constraints that cannot be expressed using superkeys.
المسألة
inst_dept (ID, name, salary, dept_name, building, budget): write the FDs for — every instructor has one name and one salary; every department is in one building with one budget; every instructor belongs to only one department. (slide 18)
خطوات الحل
- "Every instructor (ID) has one name and one salary" → ID determines name and salary.
- "Every department is in one building and has one budget" → dept_name determines building and budget.
- "Every instructor belongs to only one department" → ID determines dept_name.
النتيجة
ID → name, salary; dept_name → building, budget; ID → dept_name
First normal form (1NF)الصيغة الأولى
Disallows composite attributes, multivalued attributes and nested relations; the only values permitted are single atomic values (values that cannot be divided). 1NF is considered part of the definition of relation.
| Not in 1NFليست في 1NF | In 1NFفي 1NF |
|---|---|
| EMP_PROJ (Ssn, Ename, {Phone#}) — multivalued |
|
| EMP_PROJ (Ssn, Ename (Fname, Lname)) — composite | EMP_PROJ (Ssn, Fname, Lname) |
| EMP_PROJ (Ssn, Ename, {PROJS (Pnumber, Hours)}) — nested |
|
| Dname | Dnumber | Dmgr_ssn | Dlocations |
|---|---|---|---|
| Research | 5 | 333445555 | {Bellaire, Sugarland, Houston} |
| Administration | 4 | 987654321 | {Stafford} |
| Headquarters | 1 | 888665555 | {Houston} |
| Dname | Dnumber | Dmgr_ssn | Dlocation |
|---|---|---|---|
| Research | 5 | 333445555 | Bellaire |
| Research | 5 | 333445555 | Sugarland |
| Research | 5 | 333445555 | Houston |
| Administration | 4 | 987654321 | Stafford |
| Headquarters | 1 | 888665555 | Houston |
| Ssn | Ename | Pnumber, Hours |
|---|---|---|
| 123456789 | Smith, John B. |
|
| 666884444 | Narayan, Ramesh K. | 3, 40.0 |
| 453453453 | English, Joyce A. |
|
| 333445555 | Wong, Franklin T. |
|
| 999887777 | Zelaya, Alicia J. |
|
| 987987987 | Jabbar, Ahmad V. |
|
| 987654321 | Wallace, Jennifer S. |
|
| 888665555 | Borg, James E. | 20, NULL |
Full and partial dependenciesالاعتماد الكامل والجزئي
Second normal form
An attribute that is a member of the primary key K.
Y → Z where removal of any attribute from Y means the FD no longer holds.
Some attributes can be removed from the determinant and the dependency still holds.
Slide 26
- B is fully functionally dependent on A if B is functionally dependent on A, but not on any proper subset of A.
- B is partially functionally dependent on A if some attributes can be removed from A and the dependency still holds.
{SSN, PNUMBER} → HOURSكامل
- Full: neither SSN → HOURS nor PNUMBER → HOURS holds.
{SSN, PNUMBER} → ENAMEجزئي
- Partial: SSN → ENAME also holds.
Second normal form (2NF)الصيغة الثانية
R is in 2NF if every non-prime attribute is fully functionally dependent on the primary key — no partial dependency on the primary key.
1NF → 2NF (slide 27)
- 1
Start with a 1NF relation.
- 2
Find the FDs of the relation.
- 3
Test the FDs whose determinant is part of the PK; move partially dependent attributes to their own relation with that part of the key.
| Relation | Attributes | Its FD |
|---|---|---|
| EP1 | Ssn, Pnumber, Hours | FD1 |
| EP2 | Ssn, Ename | FD2 |
| EP3 | Pnumber, Pname, Plocation | FD3 |
- R can be decomposed into 2NF relations via the process of 2NF normalization (slide 28).
- If the primary key contains a single attribute, the 2NF test need not be applied at all (slide 30).
Transitive dependency and 3NFالصيغة الثالثة
Third normal form
X → Y is transitive if there is a set of attributes Z, neither a primary nor a candidate key, with X → Z and Z → Y.
SSN → DMGRSSNمتعدٍّ
- Transitive: SSN → DNUMBER and DNUMBER → DMGRSSN.
SSN → ENAMEغير متعدٍّ
- Non-transitive: no X with SSN → X and X → ENAME.
R is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the primary key — no transitive dependency.
| Relation | Attributes |
|---|---|
| ED1 | Ename, Ssn, Bdate, Address, Dnumber |
| ED2 | Dnumber, Dname, Dmgr_ssn |
Summary of normal forms based on primary keysملخص الصيغ
Third normal form
| Normal formالصيغة | Testالاختبار | Remedy (normalization)العلاج |
|---|---|---|
| First (1NF) | Relation should have no multivalued attributes or nested relations. | Form new relations for each multivalued attribute or nested relation. |
| Second (2NF) | For relations where primary key contains multiple attributes, no nonkey attribute should be functionally dependent on a part of the primary key. | Decompose and set up a new relation for each partial key with its dependent attribute(s). Make sure to keep a relation with the original primary key and any attributes that are fully functionally dependent on it. |
| Third (3NF) | Relation should not have a nonkey attribute functionally determined by another nonkey attribute (or by a set of nonkey attributes). That is, there should be no transitive dependency of a nonkey attribute on the primary key. | Decompose and set up a relation that includes the nonkey attribute(s) that functionally determine(s) other nonkey attribute(s). |
Boyce-Codd normal form (BCNF)صيغة بويس-كود
Whenever an FD X → A holds in R, X is a superkey of R. Also stated: in 3NF and no prime attribute is dependent on a non-prime attribute.
- Each normal form is strictly stronger than the previous: every 2NF relation is in 1NF; every 3NF in 2NF; every BCNF in 3NF.
- There exist relations that are in 3NF but not in BCNF.
- The goal: each relation in BCNF (or 3NF).
المعطيات
- R
- (A, B, C), key {A, B}
- FD1
- {A, B} → C
- FD2
- C → B
خطوات الحل
- FD2's determinant C is not a superkey of R, so R is not in BCNF.
- Split off the attributes of FD2 and keep A with C.
النتيجة
R1(A, C) and R2(C, B) — slide 36
BCNF examplesأمثلة BCNF
Boyce-Codd normal form
| STUDENT | COURSE | INSTRUCTOR |
|---|---|---|
| Narayan | Database | Mark |
| Smith | Database | Navathe |
| Smith | Operating Systems | Ammar |
| Smith | Theory | Schulman |
| Wallace | Database | Mark |
| Wallace | Operating Systems | Ahamad |
| Wong | Database | Omiecinski |
| Zelaya | Database | Navathe |
المسألة
FDs: {Student, course} → Instructor; Instructor → Course. (slide 39)
خطوات الحل
- Instructor → Course: the determinant Instructor is not a superkey.
- The relation is in 3NF but not in BCNF.
النتيجة
Decompose into {Student, Instructor} and {Instructor, Course}.
Worked example: Car_Saleمثال Car_Sale
Worked normalization examples
Car_Sale (slide 43)
- Car_Sale (Car#, Salesman#, Date_sold, Commission%, Discount_amt) — bold = underlined (the primary key).
- FDs: Date_sold → Discount_amt; Salesman# → Commission%; Car# → Date_sold.
- The slide: this relation satisfies 1NF but not 2NF (Car# → Date_sold and Salesman# → Commission%), so these two attributes are not full FD on the primary key, and not 3NF.
Slide 44 ("Answer") prints "To normalize, 2NF:" and "3NF:" with nothing under them. The slides give no decomposition for this example, so none is shown here — apply the 2NF and 3NF definitions (slides 28 and 32) yourself and check your answer with your instructor.
Worked example: BOOKمثال BOOK
Worked normalization examples
BOOK (slides 41–42)
- BOOK (Book_title, Author_name, Book_type, Listprice, Author_affil, Publisher) — slide 41; Author_affil refers to the affiliation of the author.
- FDs: Book_title → Publisher, Book_type; Book_type → Listprice; Author_name -> Author-affil (as printed).
- (a) What normal form is the relation in? Explain your answer. (b) Apply normalization until you cannot decompose the relations further. State the reasons behind each decomposition.
Slide 42 ("Answer") prints only the relation again — BOOK (Book_title, Authorname, Book_type, Listprice, Author_affil, Publisher), with the key underlined — and no normal form or decomposition. None is shown here; apply the 2NF and 3NF definitions (slides 28 and 32) and check your answer with your instructor.
Question: Dentist-patientسؤال Dentist-patient
Worked normalization examples
Question (slide 45)
- Dentist-patient (staffNo, aDate, aTime, dentistName, patNo, patName, surgeryNo) — bold = underlined.
- Normalize the above relation, showing appropriate dependency diagrams to justify decomposition.
FDs list (slide 45)
- FD1: staffNo, aDate, aTime → patNo, patName
- FD2: staffNo → dentistName
- FD3: patNo → patName
- FD4: staffNo, aDate → surgeryNo
- FD5: aDate, aTime, patNo → dentistName, staffNo
The "Answer" on slide 46 normalizes a different relation (Patient No, Drug No, Start Date, Full Name, Ward No, Ward Name, Bed No, Name, Description, Dosage, Method of Admin, Units per Day, Finish Date), not Dentist-patient; slide 47 shows the heading BCNF and nothing else. The slides therefore give no answer to this question, and none is shown here.
الخلاصة
أنهيت الدرس
الخطوة التالية: ثبّت المعلومات بالبطاقات، ثم اختبر نفسك بالأسئلة.
ما راجعته في هذا الدرس
- Informal design guidelinesإرشادات التصميم غير الرسمية
- Normalization and normal formsالتطبيع والصيغ الطبيعية
- Functional dependenciesالاعتماديات الوظيفية
- FDs and keysالاعتماديات والمفاتيح
- First normal formالصيغة الطبيعية الأولى
- Second normal formالصيغة الطبيعية الثانية
- Third normal formالصيغة الطبيعية الثالثة
- Boyce-Codd normal formصيغة بويس-كود
- Worked normalization examplesأمثلة محلولة في التطبيع