Chapter09 Relational Database Design Algorithms And Further Dependencies

9-1

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

บทที่ 9* การออกแบบฐานขอมูลเชิงสัมพันธ อัลกอริทึม และสวนเชื่อมโยงอื่น ๆ Relational Database Design Algorithms and Further Dependencies วัตถุประสงค 1. เพื่อใหมีความเขาใจการเชื่อมโยงแบบหลายคา และนอรมัลฟอรมลําดับที่ 4 (Multivalued Dependencies และ 4NF) 2. เพื่อใหมีความเขาใจการเชื่อมโยงรวม และนอรมัลฟอรมลําดับที่ 5 (Join Dependencies และ 5NF) 3. เพื่อใหสามารถประยุกตใชความเขาใจในการจัดทําการเชื่อมโยงแบบหลายคาและการเชื่อมโยงรวม สําหรับ นอรมัลฟอรมลําดับที่ 4 และ 5 ไปใชในการออกแบบฐานขอมูลได

9.1

การออกแบบฐานขอมูลเชิงสัมพันธ ในการออกแบบฐานขอมูลเชิงสัมพันธจะประกอบดวยสองแนวคิดหลัก คือ การออกแบบในลักษณะของ Top-down Design ซึ่งเปนวิธีที่ใชแพรหลายสําหรับฐานขอมูลในเชิงธุรกิจ สวนอีกวิธีหนึ่งคือการออกแบบในลักษณะของ Bottom-up Design ซึ่งจะใหมุมมองที่คอนขางชัดเจน และทําใหลักษณะของการออกแบบที่คอนขางจะเปน ระเบียบและ strict ในเชิงของฟงกชัน นอกจากนี้สวนตางๆ ที่เชื่อมโยงหรือ Dependencies มีการนําเอา อัลกอริทึมสําหรับการทํานอรมาไลเซชัน (Normalization) เขามาใชเพื่อใหสามารถสังเคราะหรูปแบบของ ความสัมพันธ (Relation schemes) ไดมีประสิทธิภาพมากขึ้น ทั้งนี้ในบทนี้จะกลาวถึงอัลกอริทึมของการนอร มาไลเซชันโดยมีพื้นฐานจาก Functional dependencies เพียงอยางเดียว โดยสามารถนําไปใชในการสังเคราะห schema สําหรับ 3NF และ BCNF ทั้งนี้เราจะอธิบายในสวนของคุณสมบัติที่ตองการสองประการในการสลาย หรือดีคอมโพสิชัน (Decomposition) ทั้งนี้ในบทนี้จะเนนเฉพาะในสวนของการเชื่อมโยงแบบหลายคา (Multivalued Dependencies) และ 4NF และการเชื่อมโยงรวม (Join Dependencies) และ 5NF เทานั้น

9.2

การเชื่อมโยงแบบหลายคา (Multivalued Dependencies) และนอรมัลฟอรมลําดับที่ 4 (4NF) ในสวนของการเชื่อมโยงแบบ Multivalued dependency (MVD) และการกําหนด 4NF ซึ่งจะเปนสวนที่ตอ เนื่องมาจาก 1NF โดยจะไมอนุญาตใหแอทตริบิวตในทูเพิลหนึ่งสามารถที่จะมีเซตคา (Set of values) ได ถาเรามี อยางนอยสอง independent attributes ที่เปน multivalued ใน relation schema เดียวกัน

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

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

9-2

รูปที่ 9.1 การแปลง Multivalued Dependencies EMP เปน 4NF 9.1 ความสัมพันธในขอ (a) จะเห็นไดวา คาความสัมพันธ Multivalued ENAME ->>PNAME และ ENAME ->> DNAME ซึ่งอยูในรีเลชัน EMP จะเห็นไดวาลูกจางหรือ EMPLOYEE ที่มีชื่อ ENAME วา Smith ทํางานใน project กับ PNAME ‘X’ และ ‘Y’ โดยเชื่อมโยงไปยัง DNAME ‘John’ และ ‘Anna’ ถาเกิดวาเราเก็บขอมูลเพียงแคสองทูเพิลใน EMP (< ‘Smith’, ‘X’, ‘John’> และ < ‘Smith’, ‘Y’, ‘Anna’>) เราอาจจะแสดงความสัมพันธที่ผิดสําหรับ project X และ John และ Project Y และ Anna ดังนั้นจะเห็นไดวาเราไมสามารถที่จะทําการ convert เปนดังรูปได เพราะวาจะมีการสื่อไปยัง ความสัมพันธที่ไมมีความหมาย สิ่งที่เราทําคือ ตองทําการเก็บขอมูลอีกสอง tuples ไดเปน < ‘Smith’, ‘X’, ‘Anna’> และ < ‘Smith’, ‘Y’, ‘John’> เพื่อที่จะแสดงวา {‘X’, ‘Y’) และ (‘John’ , ‘Anna’) โดย เกี่ยวของกับ ‘Smith’ เทานั้น แตไมมีความเกี่ยวของกับ PNAME และ DNAME ซึ่งหมายความวาแอทตริบิวต

รูปที่

ทั้งสองนั้นเปนอิสระตอกัน สวนในรูป (b) เมื่อทําการดีคอมโพสิชันความสัมพันธของ EMP ในรูปแบบของ 4NF ของ EMP_PROJECTS และ EMP_DEPENDENTS หรืออาจกลาวไดวาความสัมพันธ EMP_PROJECTS ในรูป (b) แสดงใหเห็น ถึง MVD ENAME->>PNAME แบบ Trivial MVD ซึ่งถาหาก MVD ไมสามารถรองรับไดทั้ง (a) หรือ (b) เราจะเรียกวา nontrivial MVD สวนในรูป 9.2 (c) จะเห็นไดวาความสัมพันธของ SUPPLY โดยไมมี MVDs ใน 4NF แตไมมีใน 5NF หากวามี JD (R1,R2, R3) และในสวนของ (d) เปนการสลายความสัมพันธของ SUPPLY ใน 5NF สัมพันธกับ R1, R2, และ R3

รูปที่ 9.2 การแปลง Multivalued Dependencies SUPPLY เปน 4NF

9-3

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

9.2.1 คําจํากัดความของการเชื่อมโยงแบบหลายคา (Multivalued Dependency: MVD) การเชื่อมโยงแบบหลายคา หรือ Multivalued Dependency: MVD X—>> Y กําหนด schema ของ ความสัมพันธ R, ซึ่ง X และ Y ตางเปนซับเซตของ R, กําหนดเงื่อนไขบังคับในความสัมพันธตางๆเปน r ของ R: หากวาสอง tuples t1 and t2 อยูใน r ดังนั้น t1[X] = t2[X], ดังนั้นสอง tuples t3 and t4 ควรอยูใน r ดวย ดวย คุณสมบัติดังตอไปนี้ กรณีที่เราใช Z เพื่อแสดงถึง (R 2 (X υ Y)): t3[X] = t4[X] t3[Y] = t1[Y] t3[Z] = t2[Z]

=

และ และ

t1[X] = t2[X] t4[Y] = t2[Y] t4[Z] = t1[Z]

เมื่อ X->> Y ไดถูกกําหนดไวเราจะเรียกวา X Multidetermines Y เนื่องจากคําจํากัดความมีคาเทากันดังนั้นไม วาเมื่อใด ที่ X->>Y ใน R แลว X->> Z จะไดวา X->Y สามารถ imply ไดวา X->>Z ดังนั้นสามารถเขียนได วา X->Y|Z นอกจากนั้น MVD X—>> Y ใน R เรียกวา trivial MVD หาก (a) Y เปนซับเซ็ทของ X, หรือ (b) X υ Y = R.

9.2.2 คําจํากัดความของ Relation Schema R สําหรับ 4NF Relation Schema ของ R ใน 4NF เมื่อเทียบกับสวนเชื่อมโยง หรือ Dependency F (ที่รวม Functional dependencies และ Multivalued Dependencies) หากสําหรับทุก nontrivial multiple dependencies X—>> Y ใน F+, X เปนซูเปอรคียของ R.

หมายเหตุ: F+ เปนชุด )สมบูรณ (ชอง dependencies ทั้งหมด (ฟงกชัน หรือ Multivalued) ที่จะมีคาไม เปลี่ยนแปลงในทุกความสถานะ r ของ R ที่ F รับได หรือเรียกวา สวนปด ของ F (Closure of F) การดีคอมโพสิชันของสถานะความสัมพันธ (Relation State) ของ EMP ที่ไมอยูใน 4NF สามารถจะเขียนไดดัง รูปตอไปนี้ จากรูป 9.3 (a) เห็นไดวา EMP สัมพันธ กับ tuples ที่เพิ่มเขามา และในรูป (b) การตอบสนองสอง อยางของ 4NF จะสัมพันธกับ EMP_PROJECTS และ EMP_DEPENDENTS

รูปที่ 9.3 การแปลง Multivalued Dependencies EMP ที่ไมอยูในรูป ของ 4NF

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

9.3

9-4

การเชื่อมโยงแบบรวม (Join Dependencies) และ นอร มัลฟอรมลําดับที่ 5 (5NF) 9.3.1 คําจํากัดความของการเชื่อมโยงแบบรวม (Join Dependency) การเชื่อมโยงแบบรวม (Join Dependency: JD) สามารถแสดงไดในรูปของ JD(R1, R2, ..., Rn), กําหนดโดย Relation Schema ความสัมพันธ R และกําหนดเงื่อนไขบังคับของสถานะ r ของ R โดยมีขอจํากัดที่วาในสถานะ r ที่ถูกตอง ของ R ควรจะตองมีการดีคอมโพสิชัน แบบ non-additive join decomposition ในทุกๆ R1, R2, ..., Rn ซึ่งในทุก ๆ r จะเขียนไดวา (? R1(r), ? R2(r), ..., ? Rn(r)) = r

หมายเหตุ: MVD เปนกรณีพิเศษของ JD กรณีที่ n = 2. การเชื่อมโยงแบบรวม JD (R1, R2, ..., Rn), ยังไดกําหนดในแผนผังความสัมพันธ R เปน trivial JD หากวา หนึ่งในแผนผังความสัมพันธ Ri ใน JD(R1, R2, ..., Rn) มีคาเทากับ R.

9.3.2 คําจํากัดความของ Relation Schema R สําหรับ 5NF Relation Schema ของ R ใน fifth normal form (5NF) (หรือ Project-Join Normal Form (PJNF)) เมื่อเทียบกับชุดของ F ของ Functional Multivalued และ Join dependencies โดยถาหากวา สําหรับทุก ๆ nontrivial join dependency JD(R1, R2, ..., Rn) ใน F+ (และ imply ไปถึง F), ทุกๆ Ri เปน ซูเปอรคีย (Superkey) ของ R

รูปที่ 9.4 การแปลง SUPPLY ที่มี Joint dependencies เปน 5NF จากรูป 9.4 (c) จะเห็นไดวาความสัมพันธของ SUPPLY ไมมี MVD จะอยูในรูปของ 4NF ไมไดอยูในรูปของ 5NF ถาหาวามีความสัมพันธ JD(R1, R2, R3) ในขณะที่รูป d) จะเห็นไดวาทําการ Decomposition ความสัมพันธของ SUPPLY ไปสู 5NF โดยแยกเปน Relation สามตัว นั้นคือ R1, R2, R3

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

9-5

แบบฝกหัด 1. 2. 3. 4. 5. 6.

อธิบายแนวคิด การเชื่อมโยงแบบหลายคา หรือ Multivalued Dependency และ นอรมัลฟอรมลําดับที่ 4 อธิบายแนวคิด การเชื่อมโยงแบบรวม หรือ Join Dependency และ นอรมัลฟอรมลําดับที่ 5 อธิบายแนวคิดของ Join Dependency อธิบายความหมายของ MVD อธิบายความหมายของ Trivial และ non-trivial dependencies จากขอมูล ขางลางจะเห็นไดวามีการจัดทําเปน 5NF ขอใหเปรียบเทียบขอดี และ ขอเสียที่ได หากไมมีการ ปรับเปน 5NF แตไดมีการนําไปใชในการออกแบบฐานขอมูลจริง