Normalizationالتطبيع

الشريحة 1 من 19

مقدمة الفصل

ماذا ستتعلم في هذا الفصل

  1. The four informal design guidelines: semantics, redundancy and update anomalies, nulls, spurious tuples.
  2. Functional dependencies: definition, testing them on an instance, superkeys and candidate keys.
  3. First, second and third normal forms, full, partial and transitive dependencies.
  4. Boyce-Codd normal form, and normalizing example relations step by step.
تفاصيل المصدرالفصل 6 · الشرائح ⁦2–3⁩
المصدر
الفصل 6 · الشرائح ⁦2–3⁩

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.

  1. 1Semantics of the relation attributesدلالة الصفاتEasy to explain; **do not combine attributes from multiple entity and relationship types** into one relation.
  2. 2Reduce redundant informationتقليل التكرارRedundancy wastes storage and causes **insertion, deletion and modification anomalies**.
  3. 3Reduce null valuesتقليل القيم الفارغة**As few NULLs as possible**; frequently-NULL attributes can go to separate relations (with the primary key).
  4. 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.

A relation stores employee and department data together, so the department's manager is repeated for every employee. Which problem does this design invite?

تفاصيل المصدرالفصل 6 · الشرائح ⁦2, 3, 4, 7, 9, 10⁩
المصدر
الفصل 6 · الشرائح ⁦2, 3, 4, 7, 9, 10⁩

Examples: redundancy and update anomaliesأمثلة التكرار

Informal design guidelines

Slide 5 (no title): one table holding projects and employees. EMP_NUM 111 is printed in red in its three rows.
Project_NUMProject_nameEMP_NUMEMP_nameJob_classCHG_HourHours
10Evergreen103June E. ArboughEngineer8923
10لا تذكر الشرائح شيئًا هنا.104John G. NewsAnalyst7822
10لا تذكر الشرائح شيئًا هنا.111David h. SeniorGeneral support1212
12Amber Wave120Wliliam SmithApplication design (cut off on the slide)3356
12لا تذكر الشرائح شيئًا هنا.111David h. SeniorGeneral support4554
12لا تذكر الشرائح شيئًا هنا.123Alice K. Johonsonلا تذكر الشرائح شيئًا هنا.6512
13Rolling Tide111David h. SeniorGeneral support198
13لا تذكر الشرائح شيئًا هنا.100James FormmerProgrammer4428
13لا تذكر الشرائح شيئًا هنا.103June E. ArboughEngineer8911
nullnull140Darlene SmithDBMA100null
Slide 6: two designs. **Bold** = underlined; the slide marks P.K. and F.K.
RelationAttributes
EMPLOYEEEname, Ssn (P.K.), Bdate, Address, Dnumber (F.K.)
DEPARTMENTDname, Dnumber (P.K.), Dmgr_ssn (F.K.)
(a) EMP_DEPTEname, Ssn, Bdate, Address, Dnumber, Dname, Dmgr_ssn
(b) EMP_PROJSsn, Pnumber, Hours, Ename, Pname, Plocation
Base relation EMP_PROJ with redundant information (slide 8). The slide marks Ename, and Pname with Plocation, as "Redundancy" — examples of update anomalies.
SsnPnumberHoursEnamePnamePlocation
123456789132.5Smith, John B.ProductXBellaire
12345678927.5Smith, John B.ProductYSugarland
666884444340.0Narayan, Ramesh K.ProductZHouston
453453453120.0English, Joyce A.ProductXBellaire
453453453220.0English, Joyce A.ProductYSugarland
333445555210.0Wong, Franklin T.ProductYSugarland
333445555310.0Wong, Franklin T.ProductZHouston
3334455551010.0Wong, Franklin T.ComputerizationStafford
3334455552010.0Wong, Franklin T.ReorganizationHouston
9998877773030.0Zelaya, Alicia J.NewbenefitsStafford
9998877771010.0Zelaya, Alicia J.ComputerizationStafford
9879879871035.0Jabbar, Ahmad V.ComputerizationStafford
987987987305.0Jabbar, Ahmad V.NewbenefitsStafford
9876543213020.0Wallace, Jennifer S.NewbenefitsStafford
9876543212015.0Wallace, Jennifer S.ReorganizationHouston
88866555520NullBorg, James E.ReorganizationHouston
تفاصيل المصدرالفصل 6 · الشرائح ⁦5, 6, 8⁩
المصدر
الفصل 6 · الشرائح ⁦5, 6, 8⁩

Spurious tuplesالصفوف الزائفة

Informal design guidelines

EMP_LOCS (slide 11)
EnamePlocation
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
EMP_PROJ1 (slide 11)
SsnPnumberHoursPnamePlocation
123456789132.5ProductXBellaire
12345678927.5ProductYSugarland
666884444340.0ProductZHouston
453453453120.0ProductXBellaire
453453453220.0ProductYSugarland
333445555210.0ProductYSugarland
333445555310.0ProductZHouston
3334455551010.0ComputerizationStafford
3334455552010.0ReorganizationHouston
Result of applying NATURAL JOIN to the tuples above the dashed lines in EMP_PROJ1 and EMP_LOCS (slide 11). The last column marks the generated spurious tuples (asterisks on the slide).
SsnPnumberHoursPnamePlocationEnameSpurious
123456789132.5ProductXBellaireSmith, John B.
123456789132.5ProductXBellaireEnglish, Joyce A.*
12345678927.5ProductYSugarlandSmith, John B.
12345678927.5ProductYSugarlandEnglish, Joyce A.*
12345678927.5ProductYSugarlandWong, Franklin T.*
666884444340.0ProductZHoustonNarayan, Ramesh K.
666884444340.0ProductZHoustonWong, Franklin T.*
تفاصيل المصدرالفصل 6 · الشرائح ⁦10–11⁩
المصدر
الفصل 6 · الشرائح ⁦10–11⁩

What normalization isالتطبيع

Normalization and normal forms

Normalizationالتطبيع
The process of decomposing unsatisfactory "bad" relations by breaking up their attributes into smaller relations.
Normal formالصيغة الطبيعية
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

What is normalization?

تفاصيل المصدرالفصل 6 · الشرائح ⁦12, 14⁩
المصدر
الفصل 6 · الشرائح ⁦12, 14⁩

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.
Functional dependency α → β
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.

من الشرائح

  • SSN → ENAME
  • PNUMBER → {PNAME, PLOCATION}
  • {SSN, PNUMBER} → HOURS

المسألة

r(A, B) = (1, 4), (1, 5), (3, 7). Does A → B hold? Does B → A hold? (slide 16)

r(A, B) has the tuples (1, 4), (1, 5) and (3, 7). Which statement is correct?

تفاصيل المصدرالفصل 6 · الشرائح ⁦13, 15, 16, 19⁩
المصدر
الفصل 6 · الشرائح ⁦13, 15, 16, 19⁩

Testing FDs on an instanceاختبار الاعتماديات

Functional dependencies

Slide 17: which of A → B, A → C, A → D, B → C, B → D, C → D hold on this instance?
ABCD
a1b1c1d1
a1b2c1d2
a2b2c2d2
a2b3c2d3
a3b3c2d4
The second instance on slide 17 (no question is asked about it)
buildingroom_numbercapacity
Packard101500
Painter51410
Taylor312870
Watson10030
Watson12050

المسألة

Check each candidate FD against the five tuples.

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.

r(A, B, C, D) = (a1, b1, c1, d1), (a1, b2, c1, d2), (a2, b2, c2, d2), (a2, b3, c2, d3), (a3, b3, c2, d4). Which FD holds on this instance?

تفاصيل المصدرالفصل 6 · الشرائح ⁦17, 20⁩
المصدر
الفصل 6 · الشرائح ⁦17, 20⁩

FDs and keysالاعتماديات والمفاتيح

Superkeyمفتاح فائق
K is a superkey for R if and only if K → R.
Candidate keyمفتاح مرشح
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)

Using functional dependencies, when is K a candidate key of R?

تفاصيل المصدرالفصل 6 · الشريحة ⁦18⁩
المصدر
الفصل 6 · الشريحة ⁦18⁩

First normal form (1NF)الصيغة الأولى

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.
Bringing relations into 1NF (slide 23)
Not in 1NFليست في 1NFIn 1NFفي 1NF
EMP_PROJ (Ssn, Ename, {Phone#}) — multivalued
  • EMP_PROJ1 (Ssn, Ename)
  • EMP_PROJ2 (Ssn, Phone#)
EMP_PROJ (Ssn, Ename (Fname, Lname)) — compositeEMP_PROJ (Ssn, Fname, Lname)
EMP_PROJ (Ssn, Ename, {PROJS (Pnumber, Hours)}) — nested
  • EMP_PROJ1 (Ssn, Ename)
  • EMP_PROJ2 (Ssn, Pnumber, Hours)
Figure 10.8 (slide 22): (a) DEPARTMENT (Dname, **Dnumber**, Dmgr_ssn, Dlocations), not in 1NF; (b) an example state
DnameDnumberDmgr_ssnDlocations
Research5333445555{Bellaire, Sugarland, Houston}
Administration4987654321{Stafford}
Headquarters1888665555{Houston}
(c) 1NF version of the same relation with redundancy (slide 22); key **Dnumber**, **Dlocation**
DnameDnumberDmgr_ssnDlocation
Research5333445555Bellaire
Research5333445555Sugarland
Research5333445555Houston
Administration4987654321Stafford
Headquarters1888665555Houston
EMP_PROJ with a nested relation (slide 24): each employee lists several (Pnumber, Hours) pairs; (c) splits it into EMP_PROJ1 (**Ssn**, Ename) and EMP_PROJ2 (**Ssn**, **Pnumber**, Hours)
SsnEnamePnumber, Hours
123456789Smith, John B.
  • 1, 32.5
  • 2, 7.5
666884444Narayan, Ramesh K.3, 40.0
453453453English, Joyce A.
  • 1, 20.0
  • 2, 20.0
333445555Wong, Franklin T.
  • 2, 10.0
  • 3, 10.0
  • 10, 10.0
  • 20, 10.0
999887777Zelaya, Alicia J.
  • 30, 30.0
  • 10, 10.0
987987987Jabbar, Ahmad V.
  • 10, 35.0
  • 30, 5.0
987654321Wallace, Jennifer S.
  • 30, 20.0
  • 20, 15.0
888665555Borg, James E.20, NULL

EMP_PROJ (Ssn, Ename, {Phone#}) has a multivalued attribute. How is it brought into 1NF?

تفاصيل المصدرالفصل 6 · الشرائح ⁦21–24⁩
المصدر
الفصل 6 · الشرائح ⁦21–24⁩

Full and partial dependenciesالاعتماد الكامل والجزئي

Second normal form

Prime attributeصفة أساسية
An attribute that is a member of the primary key K.
Full functional dependencyاعتماد كامل
Y → Z where removal of any attribute from Y means the FD no longer holds.
Partial dependencyاعتماد جزئي
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.

The key of a relation is {SSN, PNUMBER}, and SSN → ENAME holds. What is {SSN, PNUMBER} → ENAME?

تفاصيل المصدرالفصل 6 · الشرائح ⁦25, 26, 28⁩
المصدر
الفصل 6 · الشرائح ⁦25, 26, 28⁩

Second normal form (2NF)الصيغة الثانية

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. 1

    Start with a 1NF relation.

  2. 2

    Find the FDs of the relation.

  3. 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.

2NF normalization of EMP_PROJ (slide 29) — FD1 {Ssn, Pnumber} → Hours; FD2 Ssn → Ename; FD3 Pnumber → Pname, Plocation
RelationAttributesIts FD
EP1Ssn, Pnumber, HoursFD1
EP2Ssn, EnameFD2
EP3Pnumber, Pname, PlocationFD3
  • 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).

Which statement defines 2NF?

تفاصيل المصدرالفصل 6 · الشرائح ⁦27–30⁩
المصدر
الفصل 6 · الشرائح ⁦27–30⁩

Transitive dependency and 3NFالصيغة الثالثة

Third normal form

Transitive functional dependency
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.
3NF
R is in 3NF if it is in 2NF and no non-prime attribute is transitively dependent on the primary key — no transitive dependency.
3NF normalization of EMP_DEPT (Ename, **Ssn**, Bdate, Address, Dnumber, Dname, Dmgr_ssn) (slide 33)
RelationAttributes
ED1Ename, Ssn, Bdate, Address, Dnumber
ED2Dnumber, Dname, Dmgr_ssn

SSN → DNUMBER and DNUMBER → DMGRSSN hold, and DNUMBER is not a key of the relation. What kind of FD is SSN → DMGRSSN?

تفاصيل المصدرالفصل 6 · الشرائح ⁦31–33⁩
المصدر
الفصل 6 · الشرائح ⁦31–33⁩

Summary of normal forms based on primary keysملخص الصيغ

Third normal form

Table 10.1 (slide 34): summary of normal forms based on primary keys and corresponding normalization
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).
تفاصيل المصدرالفصل 6 · الشريحة ⁦34⁩
المصدر
الفصل 6 · الشريحة ⁦34⁩

Boyce-Codd normal form (BCNF)صيغة بويس-كود

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

When is a relation R in BCNF?

تفاصيل المصدرالفصل 6 · الشرائح ⁦35–37⁩
المصدر
الفصل 6 · الشرائح ⁦35–37⁩

BCNF examplesأمثلة BCNF

Boyce-Codd normal form

TEACH (slide 38); STUDENT and COURSE are underlined
STUDENTCOURSEINSTRUCTOR
NarayanDatabaseMark
SmithDatabaseNavathe
SmithOperating SystemsAmmar
SmithTheorySchulman
WallaceDatabaseMark
WallaceOperating SystemsAhamad
WongDatabaseOmiecinski
ZelayaDatabaseNavathe

المسألة

FDs: {Student, course} → Instructor; Instructor → Course. (slide 39)

من الشرائح

  • R (**Client#**, **Problem**, Consultant_name), FDs as drawn: {Client#, Problem} → Consultant_name; Consultant_name → Problem. → R1 (**Client#**, **Consultant_name**); R2 (**Consultant_name**, Problem)
  • R (**Stud#**, **Class#**, Instructor, Grade), FDs as drawn: {Stud#, Class#} → Instructor, Grade; Instructor → Class#. → R1 (**Stud#**, **Instructor**, Grade); R2 (**Instructor**, Class#)

A relation (Student, course, Instructor) has {Student, course} → Instructor and Instructor → Course. Which statement is correct?

تفاصيل المصدرالفصل 6 · الشرائح ⁦38–40⁩
المصدر
الفصل 6 · الشرائح ⁦38–40⁩

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.

Car_Sale (Car#, Salesman#, Date_sold, Commission%, Discount_amt) has Date_sold → Discount_amt, Salesman# → Commission% and Car# → Date_sold. In which highest normal form is it?

تفاصيل المصدرالفصل 6 · الشرائح ⁦43–44⁩
المصدر
الفصل 6 · الشرائح ⁦43–44⁩
ملاحظات حول المصدر (1)
  • الشريحة 44 عنوانها «Answer» لكنها فارغة تحت 2NF و3NF.

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.

تفاصيل المصدرالفصل 6 · الشرائح ⁦41–42⁩
المصدر
الفصل 6 · الشرائح ⁦41–42⁩
ملاحظات حول المصدر (1)
  • الشريحة 42 عنوانها «Answer» لكنها تعيد كتابة العلاقة فقط (وتكتب Authorname بلا شرطة سفلية).

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.

تفاصيل المصدرالفصل 6 · الشرائح ⁦45–47⁩
المصدر
الفصل 6 · الشرائح ⁦45–47⁩
ملاحظات حول المصدر (1)
  • الشريحة 46 تعرض حلًا لعلاقة أخرى (مريض ودواء وجناح) لا لعلاقة Dentist-patient، والشريحة 47 فارغة تحت BCNF.

الخلاصة

تفاصيل المصدر
المصدر
الفصل 6

خريطة الفصل