การออกแบบ database 2/2 [ Database the series ]

สำหรับ Part นี้เรามาต่อเนื้อหาการออกแบบ database กันใครที่ยังไม่ได้อ่าน Part ก่อนหน้าไปอ่านกันได้นะครับ โดยสำหรับ part นี้จะเป็นเรื่องของการทำ Normalization และ Normal form สำหรับ Relational Database

Normalization

คือ Process ในการแปลง ปรับ table ที่ไม่ดี ให้เล็กลง (decomposing) เพื่อให้มีคุณสมบัติตามต้องการโดยการเปลี่ยน table ใหญ่ เป็น table เล็ก

Normal forms

รูปแบบมาตรฐาน ที่ใช้ key และ FD ของ relation ใน table เพื่อตัดสินใจว่าโครงสร้างอยู่ใน normal form ที่ดีหรือเปล่า โดย มีรูปแบบดังนี้

• 2NF, 3NF, BCNF
  ใช้ key และ FD ในการพิจารณา
• 4NF
  ขึ้นอยู่กับ keys , multi-valued : MVDs
• 5NF
  ขึ้นอยู่กับ key , join dependencies : JDs

การนำ Normal forms ไปใช้งาน

Normalization : การออกแบบเพื่อที่จะให้มีคุณภาพสูงขึ้นเพื่อให้ได้ประสิทธิภาพตามที่ต้องการ ในการใช้งานจริงนิยมไปถึง 3NF และ BCNF โอกาศที่จะไปถึง 4NF มีน้อย

Denormalization : กระบวนการที่รวม Table เล็กมาเป็น table ใหญ่ๆจาก NF สูงๆ ลงมาสู่จุดเริ่มต้นใน NF ที่ต่ำกว่า

Definitions ของ Keys และ Attributes Participating

Superkey : คือกลุ่มของ attribute ที่สามารถใช้จำแนกความแตกต่างของแต่ tuple ได้ และ Unique

Key K : คือ superkey ที่มีคุณสมบัติที่ ถ้าลบ attribute ใดๆ ออกจาก K จะทำให้ K ไม่เป็น superkey อีกต่อไป หรือก็คือ minimal superkey

ใน relation schema มี key อยู่มากกว่า 1 key จะถูกเรียกว่า candidate key หนึ่งใน candidate key จะถูกนำไปใช้เป็น primary key และ ที่เหลือจะถูกเรียกว่า secondary keys

Prime attribute จะต้องเป็นหนึ่งใน candidate key

Nonprime attribute คือ attribute ที่ไม่เป็น prime attribute และไม่เป็น candidate key

First Normal Form (1NF)

• ไม่ให้มี
   - composite attributes
   - multivalued attributes
   - nested relations
• เป็นส่วนหนึ่งในการนิยาม relation
• DBMS ส่วนใหญ่จะอนุญาติให้เฉพาะ relation ใน First Normal Form

ตัวอย่าง

(a) DEPARTMENT คือ relational schema ที่ยังไม่อยู่ใน 1NF
(b) คือ state ของ (a) โดยจะเห็นได้ว่า ไม่เป็น 1NF เนื่องจาก Dlocations เป็น multivalued attributes โดย (b) สามารถแก้ไขให้เป็น 1NF ได้โดยการแยก Dlocations ออกมาเป็น Dlocation ตามในรูป (c)

Second Normal Form (2NF)

• ต้องเป็น 1NF ก่อน
• ใช้ FD , Primary key
• non-prime attribute ทุกตัว จะต้อง fully functionally dependent (Full FD) บน primary key
• แบ่ง table ออกมา (decomposed) ออกมาเป็น 2NF ผ่านวิธีการที่เรียกว่า 2NF normalization

ตัวอย่าง

จากรูป (a) ยังไม่เป็น 2NF เนื่องจาก Ename ซึ่งเป็น non-prime attribute สามารถ depent บน Ssn โดยไม่จำเป็นต้องมี Pnumber ได้ จึงไม่เป็น Full FD และไม่เป็น 2NF โดย normalization ให้เป็น 2NF โดยการแยก attribute ที่ไม่ Full FD ออกมา และทำให้ table ที่แยกออกมาที่เหลือ Full FD กัน

Third Normal Form (3NF)

• ต้องเป็น 2NF ก่อน
• ไม่มี non-prime attribute ตัวไหน transitively dependent บน the primary key
• แบ่ง table ออกมา (decomposed) ออกมาเป็น 3NF ผ่านวิธีการที่เรียกว่า 3NF normalization

ตัวอย่าง

จากรูป (b) ยังไม่เป็น 3NF เพราะ Ssn -> Dname เป็น Transitive FD เนื่องจาก Ssn -> Dnumber , Dnumber -> Dname โดย normalization ให้เป็น 3NF โดยการแยก attribute ที่ Transitive FD กับ Primary key ออกมาเป็นอีก 1 table

Boyce-Codd Normal Form (BCNF)

• เมื่อไหร่ก็ตามที่ nontrivial functional dependency ทั้งหมด X -> A และ X ไม่เป็น superkey

ตัวอย่าง

จากรูป (a) ไม่เป็น BCNF เพราะ County_name -> Area , Area -> County_name และ Area ไม่เป็น superkey ซึ่งเป็น trivial dependency จึงไม่เป็น BCNF แก้ให้เป็น BCNF โดยการ decomposition

จากรูป {Student , Course} -> Instructor และ Instructor -> Course ซึ่ง schema นี้เป็น 3NF แต่ไม่เป็น BCNF คำถามคือจากรูปจะ decomposition อย่างไร

ความเป็นไปได้ในการ decomposition มี 3 วิธี
 - D1: {student, instructor} and {student, course}
 - D2: {course, instructor } and {course, student}
 - D3: {instructor, course } and {instructor, student}
คำถามต่อไปคือจะเลือกแบบไหน?

วิธีในการเลือกคือ checking non-additivity of Binary Relational Decompositions

ถ้า R แยกออกเป็น R1 , R2 เมื่อ join กลับมาข้อมูลจะต้องเหมือนเดิม เมื่อ

ทดสอบ decomposition ทั้ง 3 วิธี
 - D1: {student, instructor} and {student, course}
  Student -> Instructor or Student -> Course
 - D2: {course, instructor } and {course, student}
  Course -> Instructor or Course -> Student
 - D3: {instructor, course } and {instructor, student}
  Instructor -> Course or Instructor -> Student

จากทั้งหมด เป็นจริงเมื่อ Instructor -> Course เท่านั้น ดังนั้น D3 จึงเป็นการ decomposition ที่ดี

Multivalued Dependencies and Fourth Normal Form (4NF)

จากรูป ใน EMP เป็น all-key relation จึงไม่มี FD และเป็น BCNF ด้วย แต่ใน EMP มีความซ้ำซ้อนของข้อมูลอย่างเห็นได้ชัด

ใช้ multivalued dependency (MVD) ถูกนำมาใช้ในรูปแบบนี้ และ มีการกำหนด Fourth Normal Form (4NF) ขึ้นมา

เมื่อ X ->> Y เรียกว่า X multidetermines Y

X ->> Y ใน R จะเรียกว่า trivial MVD ถ้า
 - Y เป็น subset ของ X หรือ X ∪ Y = R

• จะเป็น 4NF เมื่อ set of dependencies F (รวม FD และ MVD) ถ้า nontrivial multivalued dependency X ↠ Y in F+ , X  เป็น superkey ของ R

ตัวอย่าง

จากรูป (a) ไม่เป็น 4NF เพราะ non-trivial Ename ->> Pname|Dname แก้โดยการ Decompose ออกมาเป็น trivial MVD Ename ->> Pname และ Ename ->> Dname

Join Dependencies and Fifth Normal Form (5NF)

• เป็น 5NF เมื่อ set F of functional, multivalued, and join dependencies if,
  for every nontrivial join dependency JD (R1 , R2 , ... , Rn) in F+ (that is, implied by F) และ Ri เป็น superkey ของ R

ตัวอย่าง

จบไปแล้วสำหรับเนื้อหาในเรื่องนี้นะครับ โดยในเรื่องนี้คิดว่าค่อนข้างยากมากๆ ถ้าผิดพลาดตรงไหนขออภัยด้วยนะครับ หวังว่าจะมีประโยชน์กับคนที่ได้เข้ามาอ่านนะครับ ขอบคุณทุกคนที่อ่านจนจบนะครับ