Chapter08 Functional Dependencies And Normalization For Relational Databases

8-1

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

บทที่ 8* ฟงกชันนัลดีเพนเดนซีและ นอรมาไลเซชันสําหรับฐานขอมูลเชิงสัมพันธ Functional Dependencies and Normalization for Relational Databases วัตถุประสงค 1. 2. 3. 4. 5. 6. 7.

8.1

เพื่อใหมีความเขาใจในนอรมาไลเซชัน เพื่อใหมีความเขาใจในเรื่องความซ้ําซอนของขอมูลในทูเพิล และการอัพเดทอะนอรมาลี เพื่อใหมีความเขาใจในเรื่องของ Functional Dependency เพื่อใหมีความเขาใจและสามารถจัดทํา First Normal form ได เพื่อใหมีความเขาใจและสามารถจัดทํา Second Normal form ได เพื่อใหมีความเขาใจและสามารถจัดทํา Third Normal form ได เพื่อใหมีความเขาใจและสามารถจัดทํา Boyce-Codd Normal form ได

แนวทางการออกแบบสําหรับฐานขอมูลเชิงสัมพันธ (Informal Design Guidelines for Relational Database) เมื่อคิดวาการออกแบบฐานขอมูลเชิงสัมพันธ (Relational database design) คืออะไร อาจจะกลาวไดวาคือการ พยายามจัดกลุมของแอทตริบิวต (Grouping of attributes) เพื่อจะทําการรวม relation schemas ที่ดี โดย สามารถที่จะแบง relation schemas ออกเปนสองระดับนั้นคือ • •

ระดับมุมมองเชิงตรรกะของผูใชงาน (The logical “user view” level) ระดับความสัมพันธพื้นฐานของถังขอมูล (The storage “base relation” level)

โดยการออกแบบหลัก ๆ แลวจะคํานึงถึงความสัมพันธพื้นฐาน หรือ base relations และนอกจากนั้นจะตองหา ปจจัยหรือ criteria สําหรับ good base relations ทั้งนี้อาจเริ่มพิจารณาถึงแนวทางอยางไมเปนทางการในการออกแบบเชิงสัมพันธที่เหมาะสมกอน หลังจากนั้นจะทํา การพิจารณาถึงแนวทางอยางเปนทางการในการเชื่อมโยงฟงกชัน (Functional dependencies) และ นอรมัล ฟอรม (Normal forms) โดยจะแบงออกไดดังนี้ • • • •

1NF (First Normal Form) 2NF (Second Normal Form) 3NF (Third Normal Form) BCNF (Boyce-Codd Normal Form)

โดยการเชื่อมโยงประเภทอื่น ๆ นอกจากนอรมัลฟอรม นั่นคือ อัลกอริทึมในการออกแบบเชิงสัมพันธ (Relational design algorithms) โดยใชวิธีการสังเคราะหที่จะไดกลาวถึงในบทตอไป

* อางอิงจากบทที่ 10 ของเอกสารอางอิง [1]

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8.2

8-2

ซีแมนติคของแอทตริบิวตเชิงสัมพันธ (Semantics of Relation

Attributes)

8.2.1

แนวทางที่ 1

เมื่อพิจารณาอยางไมเปนทางการ จะเห็นไดวาในแตละทูเพิลของรีเลชันควรจะแสดงถึงคาเอนทิตี หรืออินสแตนซ ของความสัมพันธ (Relationship instance) ซึ่งจะนําไปประยุกตใชไดกับความสัมพันธเดี่ยว (individual relations) และแอทตริบิวตของรีเลชันนั้น โดยแอทตริบิวตของเอนทิตีที่ตางกันไมควรที่จะถูกรวมเขาไวใน ความสัมพันธเดียวกัน เชน (EMPLOYEEs, DEPARTMENTs, PROJECTs) และจะนําคียนอกหรือ foreign key มาเพื่อใชอางถึงเอนทิตีอื่น ๆ นอกจากนั้นควรจะเก็บเอนทิตีและแอทตริบิวตความสัมพันธ (Relationship attributes) แยกกันใหไดมากที่สุด เทาที่จะเปนไปได โดยสุดทายแลวในการออกแบบ schema หนึ่งสามารถที่จะอธิบายดวยความสัมพันธอยางงาย ๆ โดย semantics ของแอทตริบิวต ควรที่จะสื่อไดงายๆ

รูปที่ 8.1 COMPANY relational database schema แบบงาย

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-3

รูปที่ 8.2 ตัวอยางของสถานะ ของฐานขอมูล สําหรับ relational database schema ในรูป 8.1

ความซ้ําซอนของขอมูลในทูเพิล และการอัพเดทอะนอรมาลี (Redundancy Information and Update Anomalies)

ในการรวมแอทตริบิวตของเอนทิตีหลายๆ ตัวเขาไวดวยกันอาจจะทําใหเกิดปญหาได กลาวคือ มีการเก็บขอมูล ซ้ําซอนทําใหสิ้นเปลืองเนื้อที่ นอกจากนั้นจะมีปญหาเรื่องการอัพเดทอะนอรมาลี ซึ่งเราจะสามารถแบงออกไดเปน สามประเภท นั่นคือ • อะนอรมาลีในการเพิ่ม (Insertion anomalies) • อะนอรมาลีในการลบ (Deletion anomalies) • อะนอรมาลีในการปรับปรุง (Modification anomalies) ตัวอยาง เมื่อพิจารณาความสัมพันธดังตอไปนี้ EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours) อะนอรมาลีในการแทรก (Insertion Anomalies) ไมสามารถที่จะแทรก Project ใหมเขาไป นอกจากวา Employee จะถูก assign เขาไปใน Project หรือในทาง กลับกัน ไมสามารถที่จะเพิ่ม Employee เขาไปนอกจากวา Employee จะถูก assign เขาไปใน Project อะนอรมาลีในการลบ (Deletion Anomalies) เมื่อมีการลบ Project หนึ่งออกไปจะสงผลใหมีการลบ Employee ที่ทํางานอยูใน Project นั้น หรือ อีกทางหนึ่ง ถา Employee นั้นทํางานอยูเพียง Project เดียว การลบ Employee นั้นจะสงผลใหตองลบ Project ที่เกี่ยวของ อะนอรมาลีในการปรับปรุง (Modification Anomalies) เมื่อมีการเปลี่ยนชื่อของ Project P1 จาก “Billing” เปน “Customer-Accounting” ขอมูลจําเปนตอง ถูกนําไปแกไขในอีก 100 employees ที่ทํางานใน Project P1

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-4

รูปที่ 8.3 ตัวอยางของ Relation schema

สองอันที่ไดผล กระทบจากการ อัพเดทอะนอรมาลี

รูปที่ 8.4 ตัวอยางของ สถานะ หรือ state ของ EMP_DEPT

และ EMP_PROJ

รูปที่ 8.4 แสดงตัวอยางของสถานะ หรือ state ของ EMP_DEPT และ EMP_PROJ ที่เปนผลลัพธจากการ ประยุกตใช Natural Join ในความสัมพันธในรูป 10.2 ซึ่งอาจจะถูกเก็บไวในความสัมพันธพื้นฐานเพื่อเหตุผลดาน ประสิทธิภาพ

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8.2.2

8-5

แนวทางที่ 2

การออกแบบ Schema ที่ไมทําใหไดรับผลกระทบจากการอัพเดทอะนอรมาลีในการแทรก การลบ หรือการปรับปรุง โดยหากเปนเชนนั้น หากมีการเกิดอะนอรมาลีอยางใดอยางหนึ่งในขางตน เราจําเปนที่จะตองคํานึงถึงเมื่อทําการ สรางแอปพลิเคชัน

8.2.3

แนวทางที่ 3

เมื่อคํานึงถึงคานัล (Null value) ในทูเพิล พบวาในการออกแบบอาจเปนไปไดที่จะมีแอทตริบิวตของทูเพิลมักมีคา เปนนัล แอทตริบิวตที่มักจะพบคานัลดังกลาวสามารถนําไปสรางความสัมพันธหรือรีเลชันใหมพรอมกับคาคียหลัก (Primary key) ได เนื่องจากการมีคานัล (Null) อาจทําใหไมสามารถใชแอทตริบิวตได หรือใชไดแตไมถูกตอง นอกจากนั้นอาจเกิดแอทตริบิวตที่มีคาแตไมทราบคาเกิดขึ้น หรืออาจมีคาเกิดขึ้นแตไมสามารถนํามาใชงานได หรือ มีลักษณะที่เรียกวาทูเพิลแบบ Spurious คือ การออกแบบที่ไมดีนักของฐานขอมูลเชิงสัมพันธจะกอใหเกิดผลลัพธที่ ผิดพลาดสําหรับโอเปอเรชัน JOIN อาจจะนําคุณสมบัติที่เรียกวา "lossless join" ไปใชสําหรับยืนยันผลลัพธที่มี ความสําคัญสําหรับโอเปอเรชัน JOIN

8.2.4

แนวทางที่ 4

ไมควรออกแบบรีเลชันเพื่อสนองความตองการแคในสวนของเงื่อนไข JOIN และการทํา Natural Join ของรีเลชัน ใดๆ ไมควรสรางทูเพิลแบบ spurious จะมีคุณสมบัติที่สําคัญสองประการในการทําดีคอมโพสิชัน นั่นคือ • Non-additive หรือ losslessness ของ corresponding join • Preservation ของ functional dependencies. หมายเหตุ ไมสามารถที่จะทิ้งคุณสมบติ (a) ที่มีความสําคัญอยางมาก และในขณะเดียวกันอาจละทิ้งคุณสมบัติ (b) ที่ยืดหยุนนอยกวา ทั้งนี้ใหดูตอในบทที่ 11

รูปที่ 8.5 ตัวอยางการ ออกแบบที่ไมดี สําหรับ ความสัมพันธ EMP_PROJ

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-6

รูปที่ 8.5 เปนตัวอยางการออกแบบที่ไมดีสําหรับความสัมพันธ EMP_PROJ ในรูป 8.3b (a) Relation schemas EMP_LOCS และ EMP_PROJ1 (b) ผลของการพิจารณาสวนเพิ่มเติมของ EMP_PROJ จากรูป 8.4 ตอจาก EMP_LOCS และ EMP_PROJ1.

รูปที่ 8.6 ผลจากการประยุกต NATURAL JOIN

รูปที่ 8.6 แสดงผลจากการประยุกต NATURAL JOIN เขากับทูเพิลขางบนเสนประ ใน EMP_PROJ1 และ EMP_LOCS จากรูป 8.5 ซึ่งจะสงผลใหเกิดการสรางทูเพิลแบบ spurious

8.3

ฟงกชันนัลดีเพนเดนซี (Functional dependencies: FDs) ฟงกชันนัลดีเพนเดนซี (Functional dependencies : FDs) ถูกนําไปใชในการกําหนดวิธีในการวัดความสมบูรณ ของการออกแบบเชิงสัมพันธอยางเปนทางการ หรือเรียกไดวาเปนการวัด "Goodness" ของการออกแบบนั่นเอง โดย FDs และ คียจะถูกนําไปใชในการกําหนดนอรมัลฟอรม (Normal Forms) สําหรับความสัมพันธใดๆ โดย

8-7

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย FDs ยังทําหนาที่เปนขอจํากัดที่ทําการดีไรฟ (interrelationships) ของแอทตริบิวตของขอมูล

(Derive)

มาจากความหมายและความสัมพันธภายใน

เซตของแอทตริบิวต X ในเชิงฟงกชันจะทําหนาที่กําหนดแอทตริบิวต ถาคาของ X สามารถกําหนดคาที่เปน เอกลักษณหรือ Unique value สําหรับ Y X -> Y ถือไดวาเมื่อไรก็ตามที่ทั้งสองทูเพิลมีคาเดียวกันสําหรับ X คาพวกนั้นจะตองมีคาเดียวกันสําหรับ Y สําหรับสองทูเพิล t1 และ t2 ซึ่งเปนอินสแตนซ r(R) ในรีเลชัน R ถา t1[X]=t2[X] แลว t1[Y]=t2[Y] X -> Y ใน R จะทําหนาที่กําหนดขอจํากัดในทุกๆ ความสัมพันธของอินสแตนซ r (R) FDs สามารถเขียนสัญกรณเชิงแผนภาพดังแสดงในรูปที่ 8.3 โดยแตละฟงกชันนัลดีเพนเดนซีจะเขียนแทนไดดวย เสนตรงแนวนอน ที่แอทตริบิวตดานซาย (Left-hand side) จะเชื่อมกับเสนตรงดังกลาวดวยเสนตรง และแอทตริ บิวตดานขวา (Right-hand side) จะเชื่อมดวยลูกศรที่ชี้ไปยังแอทตริบิวตนั้น

ตัวอยางของขอจํากัดของ FD Social security number เปนตัวกําหนด Employee name จะไดวา SSN -> ENAME Project number เปนตัวกําหนด Project name และ Location จะไดวา PNUMBER -> {PNAME, PLOCATION} Social security number ของ Employee และ Project number เปนตัวกําหนดจํานวนชั่วโมงตอสัปดาหที่ Employee ทํางานใน project {SSN, PNUMBER} -> HOURS

นอกจากนั้นฟงกชันนัลดีเพนเดนซียังเปนคุณสมบัติหรือขอจํากัดของแอทตริบิวตในเคารางรีเลชัน R โดยขอจํากัดจะ เปนตัวยึดคาของความสัมพันธในทุกอินสแตนซ r(R) เชน เมื่อกําหนด K เปนคียของ R ดังนั้น K ในเชิงฟงกชันจะ เปนตัวกําหนดทุกๆ แอทตริบิวตใน R ดวย อยางไรก็ตามฟงกชันนัลดีเพนเดนซีไมสามารถพิจารณาไดจากอินส แตนซของรีเลชัน R แตตองถูกกําหนดขึ้นอยางชัดเจนเพื่อใหตรงกับความหมายที่รีเลชันนั้นถูกสรางขึ้น

8.4

กฎการอางถึงของ FD (Inference rules of FD) เมื่อกําหนดเซตของฟงกชันนัลดีเพนเดนซี (FDs) F เราสามารถอางถึง FDs เพิ่มเติมจากการใชกฎการอางถึง (Inference rules) ของ Armstrong ดังนี้ • • •

IR1. (Reflexive) If Y subset-of X, then X -> Y IR2. (Augmentation) If X -> Y, then XZ -> YZ (XZ แทน X U Z) IR3. (Transitive) If X -> Y and Y -> Z, then X -> Z

Armstrong (1974) ไดแสดงใหเห็นวาในการใชกฎการอางถึงขอ IR1, IR2, IR3 เปนกฏที่เปนเสียงหนึ่ง (Sound) และมีความสมบูรณ (Complete) โดยความหมายของเสียง (Sound) คือ สําหรับเซตของ FDs F บน เคารางของรีเลชัน R ดีเพนเดนซีที่ไดจากการใชกฏการอางถึง IR1 ถึง IR3 บนเซต F จะสามารถใชไดกับทุกอินส แตนทของรีเลชัน R และความหมายของความสมบูรณ (Complete) คือ การใชกฏการอางถึง IR1 ถึง IR3 บน เซต F ซ้ําๆ จนไมมีดีเพนเดนซีใดๆที่สามารถอางถึงไดอีก ผลทั้งหมดจากการอางถึงจะไดเซตของดีเพนเดนซีที่ เปนไปไดทั้งหมด (All possible dependencies) หรือสวนปดของเซต F (Closure of F: F+)

สําหรับกฎอางถึงอื่น ๆ ที่มีการนําไปใช ไดแก • •

(Decomposition) If X -> YZ, then X -> Y and X -> Z (Union) If X -> Y and X -> Z, then X -> YZ

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย •

8-8

(Psuedotransitivity) If X -> Y and WY -> Z, then WX -> Z

โดยในกฎสามอันขางทายนึ้จะเหมือนกับขออื่น ๆ ที่สามารถแปลงไดจากการใชกฏ IR1, IR2 และ IR3 การออกแบบฐานขอมูลนั้นผูออกแบบจะกําหนดเซตของฟงกชันนัลดีเพนเดนซี F ตามความหมายของแอทตริบิวต ของรีเลชัน R ซึ่งสามารถใชกฏการอางถึงในการพิจารณาฟงกชันนัลดีเพนเดนซีเพิ่มเติมที่ยังคงใชไดสําหรับทุกอินส แตนซใน R อีกวิธีหนึ่งที่สามารถชวยในการพิจารณาฟงกชันนัลดีเพนเดนซีเพิ่มเติมจาก F นั่นคือการพิจารณาแตละ แอทตริบิวต X ที่อยูทางดานซายของฟงกชันนัลดีเพนเดนซีบางฟงกชัน แลวพิจารณาเซตของแอทตริบิวตทั้งหมดที่ ขึ้นกับ X หรือกลาวไดวาฟงกชันนัลดีเพนเดนซีเพิ่มเติมสามารถถูกพิจารณาไดจากการหาสวนปดของ X (Closure of X : X+) ของทุกแอทตริบิวต X นั่นเอง

8.4.1 เซตที่เทากันของ FDs (Equivalence of Sets of FDs) เซตของฟงกชันนัลดีเพนเดนซี F จะถูกเรียกวาครอบคลุม (Cover) เซตของฟงกชันนัลดีเพนเดนซี E ถาทุก ฟงกชันนัลดีเพนเดนซีใน E อยูใน F+ หรือกลาวไดวาทุกฟงกชันนัลดีเพนเดนซีใน E สามารถถูกอางถึงไดจาก F ได สองเซตของฟงกชันนัลดีเพนเดนซี E และ F จะมีคา เทากัน (Equivalent) ถา E+ = F+ โดยการมีคาเทากัน หมายความวาทุกฟงกชันนัลดีเพนเดนซีใน E สามารถถูกอางถึงไดจาก F และทุกฟงกชันนัลดีเพนเดนซีใน F จะถูก อางถึงไดจาก E นั่นคือเซตของฟงกชันนัลดีเพนเดนซี E และ F จะเทากัน ถา E ครอบคลุม F และ F ครอบคลุม E นั่นเอง

8.4.2 เซตฟงกชันนัลดีเพนเดนซีนอยสุด (Minimal sets of FDs) เซตฟงกชันนัลดีเพนเดนซีนอยสุด F ของเซตของฟงกชันนัลดีเพนเดนซี E ใดๆ จะรองรับคุณสมบัติที่ทุกฟงกชันนัลดี เพนเดนซีใน E อยูใน F+ ของ F และคุณสมบัติดังกลาวของ F จะหายไปเมื่อมีฟงกชันนัลดีเพนเดนซีหนึ่งของ F ถูก ตัดทิ้งไป โดย F จะตองไมมีฟงกชันนัลดีเพนเดนซีซ้ําซอนและ E จะตองอยูในรูปแบบมาตรฐาน (Standard Form) F จะถูกกลาวไดวาเปนเซตฟงกชันนัลดีเพนเดนซีนอยสุดของ E ได ถาเซต F สามารถรองรับเงื่อนไขตอไปนี้ • ทุกดีเพนเดนซีใน F มีแอทตริบิวตทางขวามือ (Right-hand side) เปนซิงเกิลแอทตริบิวต (Single attribute) • ไมสามารถที่จะแทนดีเพนเดนซี X->A ใน F ดวยดีเพนเดนซี Y->A โดย Y เปนซับเซตของ X แลวยังคงมี คาเซตของดีเพนเดนซีเทากับ F • ไมสามารถที่จะกําจัดคาดีเพนเดนซีใดๆ จาก F แลวยังคงมีคาเซตของดีเพนเดนซีเทากับ F

เซตของดีเพนเดนซีหนึ่งอาจมีเซตฟงกชันนัลดีเพนเดนซีนอยสุดไดหลายเซต จึงอาจตองมีการกําหนดเงื่อนไข เพิ่มเติมในการพิจารณาเซตฟงกชันนัลดีเพนเดนซีนอยสุด เชน การกําหนดใหเซตฟงกชันนัลดีเพนเดนซีนอยสุดตอง มีจํานวนของดีเพนเดนซีในเซตนอยที่สุด เปนตน (ตัวอยาง พิจารณาอัลกอริทึม8.2 และ 8.4)

8.5

นอรมาไลเซชันของรีเลชัน (Normalization of Relation) นอรมาไลเซชัน (Normalization) คือ กระบวนการพิจารณาเคารางรีเลชันจาก FDs และคียหลัก เพื่อลดความ ซ้ําซอนของขอมูล และลดอัพเดทอะนอรมาลี โดยรีเลชันที่ไมดีหรือไมนาพึงพอใจจะถูกแตกออกเปนรีเลชันที่เล็กลง เพื่อใหรีเลชันมีลักษณะเปนรีเลชันที่ดี นอรมัลฟอรมจะมีพื้นฐานอยูบนคียหลัก หรือ Primary Key โดยมีประเด็นที่ตองสนใจดังนี้

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย • • • •

8-9

นอรมาไลเซชันของความสัมพันธ การใชงานของนอรมัลฟอรม คําจํากัดความของคียและแอทตริบิวต การเขารวมของคีย ใน -

First Normal Form (1NF) Second Normal Form (2NF) Third Normal Form (3NF)

นอรมัลฟอรม (Normal Form) ของรีเลชันหนึ่งๆ คือเงื่อนไขที่ระบุวารีเลชันมีนอรมัลฟอรมสูงสุดที่ดิกรีใด หรือดิก รีของการนอรมาไลเซชันที่รีเลชันนั้นผานการนอรมัลไลซแลว โดย 2NF, 3NF, BCNF มีพื้นฐานอยูบนคีย และ FDs ของเคารางรีเลชันหนึ่ง ในขณะที่ 4NF มีพื้นฐานอยูบนคีย และ Multi-valued dependencies : MVDs และ 5NF มีพื้นฐานอยูบนคีย และ Join dependencies : JDs (อางถึงในบทที่ 11) นอกจากนั้นยังตองการสวน ของคุณสมบัติเพิ่มเติม (Additional properties) เพื่อเปนตัวการันตีการออกแบบความสัมพันธที่ดี (Good relation design)

8.5.1

การใชงานของนอรมลั ฟอรม

นอรมาไลเซชันจะถูกนําไปใชในการทํางานเพื่อใหไดผลลัพธของการออกแบบที่มีคุณภาพดี และตรงตามคุณสมบัติที่ ตองการ โดยนอรมัลฟอรมจะชวยใหนักออกแบบหรือผูใชฐานขอมูลเขาใจขอจํากัด (Constraints) ของฐานขอมูลได ชัดเจนมากยิ่งขึ้น ดังนั้นในการออกแบบฐานขอมูลในอุตสาหกรรมในปจจุบันจึงใหความสนใจกับการนอรมาไลเซชัน ในนอรมัลฟอรมลําดับสูง คือ 3NF BCNF หรือ 4NF อยางไรก็ตาม การออกแบบฐานขอมูลนั้นไมจําเปนที่จะตองทําการนอรมาไลซใหไดนอรมัลฟอรมลําดับสูงสุด รีเลชัน อาจคงไวที่นอรมัลฟอรมระดับไมสูงนัก เพื่อเพิ่มประสิทธิภาพใหฐานขอมูล โดยกระบวนการในการรวม (Join) รีเล ชันที่มีนอรมัลฟอรมระดับสูงใหเปนนอรมัลฟอรมระดับต่ําลงนั้นเรียกวาการดีนอรมาไลเซชัน (Denormalization)

8.5.2

คําจํากัดของคียและแอทริบวิตที่เขารวมในคีย

ซูเปอรคีย (Superkey) ของเคารางรีเลชัน R = {A1, A2, ...., An} คือเซตของแอทตริบิวต S ซึ่งเปนซับเซต ของ R ที่มีคุณสมับิตคือไมมีสองทูเพิล t1 และ t2 ใด ๆ ใน legal relation state r ของ R ที่จะมีคา t1[S] = t2[S]

คีย (key) K คือซูเปอรคียหนึ่งที่มีคุณสมบัติเพิ่มเติม คือ เมื่อลบแอทตริบิวตใดๆ ออกจาก K จะทําให K ไม สามารถเปนซูเปอรคียไดอีกตอไป ถาในเคารางรีเลชันมีคียมากกวาหนึ่งคีย แตละคียจะถูกเรียกวา Candidate key โดยจะมี Candidate key หนึ่งในนั้นถูกเลือกใหเปนคียหลักหรือ Primary key นอกจากนั้นจะเปนคียสํารอง หรือ Secondary keys แอทตริบิวตของเคารางรีเลชัน R จะเปนแอทตริบิวตหลักหรือ Prime attribute ถาแอทตริบิวตนั้นเปนสมาชิกของ Candidate key ใดๆ และแอทตริบิวตจะไมเปนแอทตริบิวตหลักหรือ Nonprime attribute ถาแอทตริบิวตไม เปนสมาชิกของ Candidate key ใดเลย

8.5.3

First Normal Form

นอรมัลฟอรมอันดับหนึ่ง (1NF) จะไมอนุญาตรีเลชันมีแอทตริบิวตหลายคา (Multivalued attribute) แอทตริ บิวตผสม (Composite attribute) และแอทตริบิวตทั้งสองแบบรวมกัน โดยคาของแอทตริบิวตที่อนุญาตสําหรับ 1NF จะมีลักษณะเปน Single atomic value เทานั้น

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-10

รูปที่ 8.8 นอรมาไลเซชันของ 1NF

รูปที่ 8.8 แสดงนอรมาไลเซชัน ของ 1NF โดยที่ (a) Relation schema ที่ยังไมไดอยูใน 1NF (b) ตัวอยาง สถานะของความสัมพันธของ DEPARTMENT (c) 1NF เวอรชั่นของความสัมพันธเดิมพรอมกับคาซ้ําซอน สําหรับการทําใหรีเลชัน Department ในรูปที่ 8.8 อยูใน 1NF สามารถทําได 3 วิธีดังนี้ นํา DLOCATIONS แยกออกเปนอีกรีเลชันหนึ่งคือ DEPT_LOCATIONS (DNUMBER, DLOCATION) โดยใช DNUMBER เปนคียหลัก • ขยายคียหลักของรีเลชันใหเปน {DNUMBER, DLOCATION} แตวิธีนี้มีขอเสียคือจะทําใหมีการเก็บ ขอมูลซ้ําซอน • หากทราบจํานวนที่มากที่สุดของแอทตริบิวตหลายคา เชน หากทราบวา DEPARTMENT นั้นจะมี DLOCATION ไดมากที่สุดสามแหง สามารถทําไดโดยแทนที่ DLOCATION ดวย DLOCATION1 DLOCATION2 และ DLOCATION3 แตวิธีนี้จะมีขอเสียคือ อาจมีคานัลเกิดขึ้นได และทําใหการสืบคน ยากขึ้น •

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-11

รูปที่ 8.9 นอรมาไลเซชัน ของ 1NF ชอง Project

รูปที่ 8.9 แสดงนอรมาไลเซชัน ของ 1NF โดยที่ (a) Relation schema ที่ยังไมไดอยูใน 1NF (b) ตัวอยาง สถานะของความสัมพันธของ Project (c) 1NF เวอรชั่นของความสัมพันธ

8.5.4

Second Normal Form

นอรมัลฟอรมลําดับที่สอง (2NF) ขึ้นอยูกับฟงกชันนัลดีเพนเดนซีแบบสมบูรณ (Full functional dependency) โดย ฟงกชันนัลดีเพนเดนซี X -> Y จะเปนฟงกชันนัลดีเพนเดนซีแบบเต็ม ถามีการนําแอทตริบิวตใดๆออกจาก X แลวทําใหดีเพนเดนซีนั้นถูกทําลาย ฟงกชันนัลดีเพนเดนซี X -> Y จะเปนฟงกชันนัลดีเพนเดนซีแบบบางสวน (Partial functional dependency) ถามีการนําแอทตริบิวตใดๆออกจาก X แลวยังคงดีเพนเดนซีนั้นไว นั่นคือ สําหรับแอทตริบิวต A ที่อยูใน X ดีเพน เดนซี (X-{A}) -> Y สําหรับเคารางรีเลชัน R จะอยูใน 2NF ถาทุก Nonprime attribute ใน R เปนฟงกชันดีเพนเดนซีแบบเต็มที่ ขึ้นอยูกับคียหลัก ตัวอยาง

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-12

{SSN, PNUMBER} -> HOURS เปนฟงกัชันนัลดีเพนเดนซีแบบสมบูรณ เนื่องจากเมื่อตัด SSN หรือ PNUMBER ออกจาก {SSN, PNUMBER} จะไมมีดีเพนเดนซี SSN -> HOURS หรือ NUMBER -> HOURS {SSN, PNUMBER} -> ENAME เปนฟงกชันนัลดีเพนเดนซีแบบบางสวน เนื่องจากเมื่อตัด PNUMBER ออกจาก {SSN, PNUMBER} ยังคงมีดีเพนเดนซี SSN -> ENAME เหลืออยู

รูปที่ 8.10 นอรมาไลเซชัน ของ 1NF ชอง Project รูปที่ 8.10 แสดงนอรมาไลเซชัน ของ 2NF และ 3NF (a) Relation schema ที่ยังไมไดอยูใน 1NF (b) นอรมัลไลซ EMP PROJ เขาสู 2NF (c) นอรมัลไลซ EMP_DEPT เขาสู 3NF

8.5.5

Third Normal Form

นอรมัลฟอรมลําดับที่สาม (3NF) ขึ้นอยูกับ Transitive dependency นั่นคือฟงกชันนัลดีเพนเดนซี X -> Y ใน เคาราง R จะเปน Transitive dependency ถามีเซตของแอทตริบิวต Z ซึ่งไมใชทั้ง Candidate key และไมใช ซับเซตของคียใดๆของ R ที่มี X -> Z และ Z -> Y ตัวอยาง SSN -> DMGRSSN เปน Transitive dependency เนื่องจากมีดีเพนเดนซี SSN -> DNUMBER และ DNUMBER -> DMGRSSN

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-13

SSN -> ENAME ซึ่งเปน Non-transitive dependency เนื่องจากไมมีเซตของแอทตริบิวต Z ที่ทําใหมีดีเพน เดนซี SSN -> X และ X -> ENAME

เคารางรีเลชัน R จะอยูใน 3NF ถา R เปน 2NF ที่ไมมีแอทตริบิวตแบบ Non-prime ที่เปน Transitive dependency ที่ขน ึ้ อยูกับคียหลัก หมายเหตุ ในการนอรมาไลซลําดับที่สามเมื่อมีดีเพนเดนซี X -> Y และ Y -> Z โดยมี X เปนคียหลัก เราพิจารณาปญหานี้ ในการนอรมาไลเซชันอันดับสามเมื่อ Y ไมไดเปน Candidate key เทานั้น แตถา Y เปน Candidate key จะไม จําเปนตองพิจารณาเรื่อง Transitive dependency ตัวอยาง พิจารณา EMP (SSN, Emp#, Salary ). ดังนั้น SSN -> Emp# -> Salary เมื่อ Emp# เปน Candidate key จะไมจําเปนตองพิจารณา Transitive dependency นี้ในการทํา 3NF

8.5.6

General Normal Form

ในนอรมัลฟอรมที่พิจารณาขางตนนั้นจะเปนการพิจารณาเฉพาะคียหลักเทานั้น โดยไมมีการนํา Candidate key มาพิจารณาดวย นอรมัลฟอรมทั่วไป (General normal form) จึงเปนการทํานอรมาไลซที่นําทุก Candidate key ในเคารางรีเลชันมาพิจารณา โดย Prime attribute คือแอทตริบิวตที่เปนสวนหนึ่งของ Candidate key ใดๆ ใน R และฟงกชนั นัลดีเพนเดนซีแบบสมบูรณและแบบบางสวน และ Transitive dependency จะถูกนํามาใช สําหรับทุก Candidate key General definition of second normal form เคารางรีเลชัน R จะอยูในนอรมัลฟอรมทั่วไปอันดับสอง (Second normal form) ถาทุก Nonprime attribute

ไมมีฟงกชันนัลดีเพนเดนซีแบบบางสวนที่ขึ้นอยูกับคียใดๆของรีเลชัน General definition of third normal form

เคารางรีเลชัน R จะอยูในนอรมัลฟอรมทั่วไปอันดับสอง (Third normal form) ถาฟงกชันนัลดีเพนเดนซี X -> A ใน R มี (a) X เปนซูเปอรคียของ R หรือ (b) A เปน Prime attribute ของ R หมายเหตุ Boyce-Codd normal form ไมอนุญาตใหเกิดเงื่อนไข (b) ขางตน

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-14

รูปที่ 8.11 นอรมาไลเซชัน ของ 2NF และ 3NF รูปที่ 8.11 แสดงนอรมาไลเซชัน ของ 2NF และ 3NF โดยที่ (a) ความสัมพันธ LOTS กับ functional dependencies FD1 ถึง FD4 (b) แยกเขาสู ความสัมพันธ 2NF LOTS และ LOTS (c) แยกเขาสู ความสัมพันธ LOTS เขาสู ความสัมพันธ 3NF ในรูป LOTS1A และ LOTS1B (d) ผลสรุปนอรมัลไลซเซชั่นตอเนื่อง (Progressive normalization ของ LOTS)

8.5.7

Boyce-Codd Normal Form (BCNF)

เคารางรีเลชัน R จะอยูใน Boyce-Codd Normal Form (BCNF) ถาฟงกชันนัลดีเพนเดนซี X -> A ใน R มี X เปนซูเปอรคียของ R ในแตละนอรมัลฟอรมจะถูกบังคับไวชัดเจน โดยทุกรีเลชัน 2NF จะตองอยูภายใน 1NF ในขณะเดียวกันทุก ๆ ความสัมพันธ 3NF จะอยูใน 2NF และนอกจากนั้นทุกๆ BCNF จะตองอยูภายใน 3NF ทั้งนี้ความสัมพันธที่มีอยู ที่อยูภายใต 3NF จะตองไมอยูใน BCNF โดยเปาหมายคือมีทุกๆ รีเลชันอยูใน BCNF (หรือ 3NF)

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-15

รูปที่ 8.12 นอรมาไลเซชัน ของ BCNF

รูปที่ 8.12 แสดงนอรมาไลเซชัน ของ BCNF โดยที่ (a) BCNF นอรมาไลเซชัน ของ LOTS1A พรอมดวย functional dependency FD2 ที่หายไปในการทํา Decomposition (b) A schematic relation พรอมกับ FDs; โดยที่อยูใน 3NF แตไมไดอยูใน BCNF.

รูปที่ 8.13 ความสัมพันธ TEACH

รูปที่ 8.13 แสดงรีเลชัน TEACH ที่อยูใน 3NF แตไมอยูใน BCNF ในการเขาถึง BCNF โดยการ decomposition จะพบวา FDs สองตัวที่ปรากฏในรีเลชัน TEACH fd1: {student, course} -> instructor fd2: instructor -> course {student, course} เปน Candidate key ของรีเลชันนี้ และสามารถแสดง FDs ดังแสดงในรูปที่ 8.12(b) โดย STUDENT คือ A COURSE เปน B และ INSTRUCTOR เปน C เมื่อพิจารณารูปแบบดีเพนเดนีจะเห็นวา

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-16

รีเลชันที่อยูใน 3NF แตไมอยูใน BCNF เมื่อทําการ Decomposition รีเลชัน (พิจารณาจาก อัลกอริทึ่มใน 11.3) จะสามารถแตกรีเลชันได 3 ลักษณะที่เปนไปได ไดแก {student, instructor} และ {student, course} {course, instructor } และ {course, student} {instructor, course } และ {instructor, student}

การแตกรีเลชันทั้ง 3 แบบขางตนจะทําใหสูญเสียดีเพนเดนซี FD1 ไป แตการแตกรีเลชันที่ตองการมีเพียงการแตก รีเลชันแบบที่สาม เพราะไมสราง spurious tuples หลังการ join (ซึ่งจะใหคุณสมบัติที่เรียกวา non-additivity property)

นอกจากนี้ยังมีการทดสอบเพื่อที่จะกําหนดวาในการทํา binary decomposition หรือ การทํา decomposition ไปเปนรีเลชัน หรือรีเลชันสองรีเลชันถือวาเปน nonadditve หรือ lossless ซึ่งจะไดกลาวถึงใน สวนที่ 11.1.4 ภายใตคุณสมบัติ LJ1 และนอกจากนั้นยังเปนการตรวจสอบวา third decomposition ขางตนรองรับคุณสมบัติ ตามที่ตองการ

2110422 การออกแบบระบบการจัดการฐานขอมูล ภาควิชาวิศวกรรมคอมพิวเตอร คณะวิศวกรรมศาสตร จุฬาลงกรณมหาวิทยาลัย

8-17

แบบฝกหัด 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

จงอธิบายแนวคิดของ Functional Dependency จงอธิบายแนวคิดของซีแมนติคของฐานขอมูลเชิงสัมพันธ จงแยกประเภทของอะนอรมาลีและอธิบายอะนอรมาลีแตละประเภท จงอธิบายความแตกตางของ คีย ซูเปอรคีย และ คียหลัก จงอธิบายความหมายของนอรมาไลเซชัน จงอธิบายประโยชนที่ไดจาก BCNF จงอธิบายความแตกตางระหวาง 1NF และ 2NF จงอธิบายความแตกตางระหวาง 2NF และ 3NF จงอธิบายความแตกตางระหวาง 3NF และ BCNF พิจารณาวาจะสามารถจัดทําในรูปแบบของ BCNF ไดหรือไม

11. จงอธิบายความหมายของ Transitive และ Non-transitive FD 12. จงอธิบายความหมาย และ ความแตกตางของ Equivalence sets of FDs และ Minimal sets of FDs