บอย

วันพุธที่ 9 กุมภาพันธ์ พ.ศ. 2554

การทำ normah zation

บทที่ 7
การนอร์มัลไลซ์ (Normalization)
7.1 ความหมายของคำ ที่เกี่ยวข้อง
7.1.1 FD (Functionally Dependent หรือ Function Dependency)
เป็นความสัมพันธ์ระหว่าง attribute แบบ m:1 หรือ 1:1 โดย attribute ทางขวามีฟังก์ชันขึ้นกับ
attribute ทางซ้าย
กรณี 1:1 ค่าของ attribute ทางซ้าย 1 ค่า จะสัมพันธ์กับค่าของ attribute ทางขวา 1 ค่า
กรณี m:1 ค่าของ attribute ทางซ้ายมากกว่า 1 ค่าจะสัมพันธ์กับค่าของ attributeทางขวา 1 ค่า
นิยาม
กำ หนดให้ x และ y เป็น attribute ของ relation R จะได้ว่า y มีฟังก์ชันขึ้นกับ x(y
เป็น FD กับ x) ก็ต่อเมื่อถ้า 2 tuples ใน R มีค่าของ x ตรงกันแล้ว ทั้ง 2 tuples นี้ จะต้องมีค่าของ y
ตรงกันด้วย
ถ้า relation R มี attribute x, y จะได้ว่า
R.x 􀃆 R.y
อ่านว่า x determine y
หรือ y depends on x
หมายความว่า x จะเป็นตัวกำ หนดค่า (determine) ของ y หรือค่าของ y จะขึ้นอยู่กับ
ค่าของ x (y depends on x หรือ y เป็น FD กับ x) เราจะเรียก x ว่า determinant
หลักในการเขียน Functional Dependency
FDs : determinant-attribute 􀃆 dependency-attribute
FDs : PERSON_ID 􀃆 PERSON_NAME
ประเภทของ Functional Dependency
- FD ที่เกิดจากความสัมพันธ์ระหว่าง Determinant และ Dependency อย่างละ 1 ค่า
PERSON_ID 􀃆 PERSON_NAME
- FD ที่เกิดจากความสัมพันธ์ระหว่าง Determinant 1 ค่า กับ Dependency หลายค่า
PERSON_ID 􀃆 FNAME, LNAME, ADDRESS, BIRTH_DATE, ISSUE_DATE
- FD ที่มีความสัมพันธ์ 2 ทาง ที่ทั้ง Determinant และ Dependency ต่างสามารถทำ หน้าที่
ของอีกฝ่ายหนึ่งได้
PROJECT_NO 􀃆 MANAGER
MANAGER 􀃆 PROJECT_NO
PROJECT_NO 􀃅 􀃆 MANAGER
- FD ที่ต้องใช้ Determinant มากกว่า 1 ค่าเพื่ออ้างถึง Dependency
PRODUCT_LINE, ITEM_NO 􀃆 USED_QTY
เอกสารประกอบการบรรยายวิชา 204204 การออกแบบและพัฒนาฐานข้อมูล 7 - 2
7.1.2 Full FD (Full Functional Dependence)
นิยาม
“attribute y ของ relation R จะเป็น Full FD บน attribute x ของ relation R ถ้า y เป็น
FD กับ x และไม่เป็น FD กับ subset ใด ของ x”
หรืออาจกล่าวได้ว่าเป็น FD ที่มี Determinant ที่มีขนาดเล็กที่สุดและสามารถระบุถึง
Dependency ได้ ดังตัวอย่างต่อไปนี้
- D1 : PERSON_ID 􀃆 ADDRESS
D2 : PERSON_ID, PERSON_NAME 􀃆 ADDRESS
- D3 : PRODUCT_LINE, ITEM_NO 􀃆 USE_QTY
D4 : PRODUCT_LINE, ITEM_NO, MANAGER 􀃆 USE_QTY
ดังนั้น จากตัวอย่างสามารถสรุปได้ว่า D1 กับ D3 ถือเป็น Full FD
7.1.3 Partial Dependency
ความสัมพันธ์แบบนี้จะเกิดขึ้นได้ก็ต่อเมื่อ relation หนึ่ง มีคีย์หลักเป็นคีย์ผสม
(composite key) นั่นคือ คีย์หลักของ relation นั้น ประกอบด้วย attribute หลาย attribute ความ
สัมพันธ์ระหว่างค่าของ attribute แบบบางส่วนเกิดขึ้นเมื่อ attribute บางส่วนของคีย์หลักสามารถระบุค่า
ของ attribute อื่น ที่ไม่ใช่คีย์หลักของ relation ได้ (Non-key attribute) ซึ่งความสัมพันธ์แบบนี้จะทำ
ให้เกิดปัญหาในเรื่องของความซํ้าซ้อน และการปรับปรุงข้อมูล
7.1.4 Transitive Dependency
attribute ที่มีคุณสมบัติเป็นคีย์หลักจะสามารถระบุค่าของทุก attribute ในแต่ละ tuples
ได้ อย่างไรก็ตาม ในบาง relation อาจจะมีกรณี attribute อื่น (Nonkey attribute) ที่สามารถระบุค่าของ
attribute อื่น ใน tuples ได้ ลักษณะของความสัมพันธ์ในการระบุค่า attribute แบบนี้ เรียกว่า ความ
สัมพันธ์ระหว่างค่าของ attribute แบบนี้ว่า Transitive Dependency ดังตัวอย่างเช่น
รหัสนักศึกษา 􀃆 รหัสสาขาวิชา
รหัสสาขาวิชา 􀃆 ชื่อสาขาวิชา
จะเห็นได้ว่า รหัสสาขาวิชา 􀃆 ชื่อสาขาวิชา เป็น Transitive Dependency ซึ่งถือว่า
เป็นส่วนที่เกินมาโดยไม่จำ เป็น เนื่องจาก รหัสนักศึกษา 􀃆 รหัสสาขาวิชา ก็สามารถดึงข้อมูลในส่วน
ของชื่อสาขาวิชาได้ ดังนั้น เราจะไม่เก็บชื่อสาขาวิชาไว้ในตารางนักศึกษา
7.1.5 Multivalued Dependency
การขึ้นต่อกันหลายค่า (Multivalued Dependency) ในความสัมพันธ์ R มี attribute A, B, C
เราจะกล่าวว่า attribute B เป็นการขึ้นต่อกันหลายค่าบน A ก็ต่อเมื่อเซทของค่าของ attribute B ใน
ความสัมพันธ์ R ที่มีความสัมพันธ์ตรงกับคู่ของ <A, C> นั้น จะไม่ขึ้นกับค่าของ C เขียนแทนด้วย
A ------->> B และจะมีลักษณะที่เห็นได้ดังนี้
บทที่ 7 การนอร์มัลไลซ์ (Normalization) 7 - 3
1 attribute A ค่าหนึ่ง จะเป็นตัวกำ หนดกลุ่มของค่า attribute B คือ เมื่อ 2 tuples
ในความสัมพันธ์ R มีค่า A เดียวกัน ไม่จำ เป็นต้องมีค่า B เหมือนกัน แต่ค่าของ B จะต้องอยู่ในกลุ่ม
ของค่า B ที่ถูกกำ หนดโดย A
2 การเปลี่ยนแปลงค่าใดใน attribute C จะไม่มีผลกระทบต่อค่า B
3 สอง tuples ในความสัมพันธ์ R ที่มีค่า B เหมือนกันไม่จำ เป็นต้องมีค่า A เดียว
กัน
4 ค่าของ attribute C สองค่าที่มีความสัมพันธ์กับค่า A เดียวกันจะต้องสัมพันธ์กับค่า
ของ B ในกลุ่มเดียวกันและเป็นกลุ่มที่ถูกกำ หนดโดยค่า A นั้น
หรืออาจกล่าวได้ว่า ค่าของ Determinant 1 ค่าสามารถระบุค่าของ attribute ที่ทำ หน้าที่เป็น
Dependency ได้ตั้งแต่ 2 attribute ขึ้นไป ซึ่งอยู่ในรูปของชุดข้อมูล
EMPLOYEE# 􀃆 􀃆 DEPARTMENT#, PROJECT#
7.1.6 Trivial FD’s
FD (Function Dependancy) เป็น Trivial FD’s ก็ต่อเมื่อ attribute ทางด้านขวาอยู่ใน attribute ทาง
ด้านซ้าย
ตัวอย่างเช่น
SUPPLIER(SNAME,ADDRESS,ITEM,PRICE)
SNAME 􀃆 ADDRESS
SNAME,ITEM 􀃆 PRICE
SNAME ---> SNAME
SNAME,ITEM ---> ITEM Trivial FD’s
7.2 การนอร์มัลไลซ์ (Normalization)
หลังจากที่ผู้ออกแบบได้ขอบเขตข้อมูลทั้งหมดที่ต้องการเก็บแล้ว ซึ่งโดยมากเกิดจากรูปแบบ
รายงานบ้าง รูปแบบใบเสร็จรับเงินบ้าง รูปแบบใบส่งสินค้าบ้าง โดยมากมักจะเหมารวมเอาว่านั้นคือ
รูปแบบของตารางที่ต้องการเก็บข้อมูล ซึ่งนำ มาซึ่งความซํ้าซ้อนของข้อมูลในรายกรณี และทำ ให้มีขนาด
ใหญ่เกินความจำ เป็น ส่วนที่ซํ้าซ้อน ปัญหาของรีเลชั่นที่เกิดขึ้นเหล่านี้ สามารถขจัดได้ด้วย ขบวน
การ Normalization” ซึ่งแนวคิดนี้ถูกคิดค้นโดย E.F.Codd ซึ่งเป็นกระบวนการที่นำ เค้าร่างของ
relation มาทำ ให้อยู่ในรูปแบบที่เป็นบรรทัดฐาน (Normal Form) เพื่อให้แน่ใจว่าการออกแบบเค้าร่าง
ของ relation เป็นการออกแบบที่เหมาะสม
ให้ทำ การตรวจสอบเอนทิตีต่าง ให้อยู่ในกฎนอร์มัลไลเซชันซึ่งประกอบด้วย 1NF, 2NF,
3NF, BCNF, 4NF, 5NF ซึ่งจะได้กล่าวในหัวข้อต่อไป ประโยชน์ก็คือ
1. ลดที่ว่างที่ต้องใช้ในการเก็บข้อมูล
เอกสารประกอบการบรรยายวิชา 204204 การออกแบบและพัฒนาฐานข้อมูล 7 - 4
2. ลดความผิดพลาด ความไม่ตรงกันของข้อมูลในฐานข้อมูล
3. ลดการเกิดอะนอร์มัลไลของการลบและแก้ไขข้อมูล
4. เพิ่มความคงทนแก่โครงสร้างฐานข้อมูล
ในทางปฏิบัติการทำ นอร์มอลไลซ์จะเริ่มจาก E-R Model ก่อน แล้วจึงทำ การ map จาก E-R
Model เป็น relation แบบ 1NF ก่อน โดยให้ attributes ที่เกี่ยวข้องกันจะอยู่ในตารางเดียวกัน สำ หรับ
application ใหญ่ มี attributes ประมาณ 500 attributes ใช้ E-R Model จะได้ 1NF ประมาณ 80 ตา
ราง เมื่อทำ ถึง 5NF จะได้ไม่เกิน 100 ตาราง ในกรณีได้ตารางเป็นนอมัลไลเซชันที่สมบูรณ์แล้ว สิ่งที่
ต้องระวังคือไม่แตกตารางนั้นย่อยลงไปอีก
ระดับนอร์มัลไลเซชัน
นอร์มัลไลเซชัน เป็นกระบวนการเพื่อพัฒนาการ เชื่อมต่อของข้อมูลเพื่อแก้ปัญหาของรีเลชั่น ที่
ว่าการออกแบบฐานข้อมูลทั้งทางตรรกะ และทางกายภาพที่ได้ออกมาใช้ได้หรือยัง การนอร์มัลไลเซชัน
แบ่งออกได้เป็นหลายระดับ ได้แก่
7.2.1 First Normal Form (1NF)
ทุก field ในแต่ละ record จะเป็น single value นั่นคือ ในตารางหนึ่ง จะไม่มี ค่าของกลุ่ม
ข้อมูลที่ซํ้ากัน (Repeating Group) ตัวอย่างเช่น ตารางดังต่อไปนี้
ตารางที่มีลักษณะข้อมูลเป็น Repeating group
รหัสนักศึกษา ชื่อ นามสกุล รหัสวิชาที่ลงทะเบียน
001 สมชาย สมใจนึก 204-101
204-204
204-205
002 ธีรชาย บุญมาศ 204-102
204-204
เราสามารถทำ ให้อยู่ในรูป 1NF ได้ดังนี้
รหัสนักศึกษา ชื่อ นามสกุล รหัสวิชาที่ลงทะเบียน
001 สมชาย สมใจนึก 204-100
001 สมชาย สมใจนึก 204-204
001 สมชาย สมใจนึก 204-125
002 ธีรชาย บุญมาศ 204-102
002 ธีรชาย บุญมาศ 204-204
บทที่ 7 การนอร์มัลไลซ์ (Normalization) 7 - 5
จะเห็นว่าการเก็บข้อมูลแบบนี้เป็นการสิ้นเปลืองโดยใช่เหตุ เพราะมีค่าของกลุ่มข้อมูลที่ซํ้ากัน
มากมาย เพราะนักศึกษาคนหนึ่ง สามารถลงทะเบียนได้มากกว่าหนึ่งวิชา
สรุปก็คือ นอร์มัลไลเซชันระดับที่ 1 (First normal form : 1NF) เปน็ การขจัดแอตตริบิว หรือกลุม่
แอตตริบิวที่ซํ้ากันไปอยู่ในเอนทิตีลูก เพื่อแต่ละรายการในเอนทิตี ไม่มีค่าของแอตตริบิวหรือค่าของกลุ่ม
แอตตริบิวที่ซํ้ากัน
สำ หรับ 1NF จะมีข้อเสียงในการแก้ไข การลบ และการเพิ่มข้อมูล ดังนี้
1) การแก้ไขข้อมูล (Update) เนื่องจากมีข้อมูลอยู่หลาย tuples จะต้องแก้ไขทุก tuples นั่นคือ
ต้องมีการแก้ไขข้อมูลมากกว่าหนึ่งแห่ง
2) การลบข้อมูล (Delete) ถ้าต้องการลบข้อมูลบางส่วนออกไป จะทำ ให้ลบข้อมูลอื่นออกไป
ด้วยโดยไม่ตั้งใจ
3) การเพิ่มข้อมูล (Insert) อาจจะทำ ให้ไม่สามารถเพิ่มข้อมูลบางอย่างไม่ได้ หรือเพิ่มแล้วขัด
แย้งกับข้อมูลเดิม
7.2.2 Second Normal Form (2NF)
ต้องเป็น First Normal Form (1NF) และต้องมี key (บางตำ รา อาจจะเรียกว่า index) ที่ทุก Non-key
จะต้องขึ้นอยู่ (depends on) กับ key นี้ และมีเพียง key เดียวในหนึ่งตาราง ซึ่งเรียกว่า Primary Key
การที่ทุกตาราง (Table) ต้องมี Key ก็เพราะเราต้องการให้แน่ใจว่าทุกข้อมูลใน record ต่าง สามารถ
ค้นหาได้โดยใช้ key
สรุปก็คือ นอร์มัลไลเซชันระดับที่ 2 (Second normal form : 2NF) เป็นการขจัดแอตตริบิวที่
ไม่ขึ้นกับทั้งส่วนของคีย์หลักออกไป เพื่อให้แอตตริบิวอื่นทั้งหมดขึ้นตรงกับส่วนที่เป็นคีย์หลักทั้งหมด
เท่านั้น
นิยาม
เป็น First Normal Form (1NF) และทุก Non-key จะต้องขึ้นอยู่ (depends on) กับ key อย่าง
สมบูรณ์ (Full FD) หรืออาจกล่าวได้ว่าไม่มี Non-key ที่สามารถ imply ถึง Non-key ตัวอื่นได้ เช่น A
􀃆 (B , C) and B􀃆 C รวมไปถึง การที่ Non-Key บางตัวที่ขึ้นกับ บางส่วนของ Key
ตัวอย่างเช่น
ABC (ชิ้นส่วน , ชื่อโกดัง , จำ นวน , ที่อยู่โกดัง)
FD = { ชิ้นส่วน และ ชื่อโกดัง 􀃆 จำ นวน , ชื่อโกดัง 􀃆 ที่อยู่โกดัง }
เนื่องจาก (ชิ้นส่วน และชื่อโกดัง) เป็น key แต่ (ที่อยู่โกดัง) ไม่ได้ขึ้นตรงกับ key (fullydepended
on key) ดังนั้น จึงไม่ใช่ 2NF ดังนั้น จะต้องทำ การแตกรีเลชั่น เพื่อลดปัญหาความซํ้าซ้อน
ของข้อมูลเป็นดังนี้
สินค้า (ชิ้นส่วน, ชื่อโกดัง , จำ นวน) โดยให้ ชิ้นส่วนและชื่อโกดัง เป็นคีย์หลัก
โกดัง (ชื่อโกดัง , ที่อยู่โกดัง) โดยให้ ชื่อโกดัง เป็นคีย์หลัก
เอกสารประกอบการบรรยายวิชา 204204 การออกแบบและพัฒนาฐานข้อมูล 7 - 6
7.2.3 Third Normal Form (3NF)
นอร์มัลไลเซชันระดับที่ 3 (Third normal form : 3NF) คือ ขบวนการที่พยายามขจัดสภาพ
ของ Transitive Dependency ออกไป
นิยาม นอร์มัลไลเซชันระดับที่ 3 (Third normal form : 3NF)
ต้องเป็น Second Normal Form (2NF) และ ไม่มี Transitive dependence หรือ เป็นการ
ขจัดแอตตริบิวที่ไม่เป็นคีย์ที่ขึ้น ( Transitive dependent ) ตรงกับแอตตริบิวอื่นที่ไม่ใช่คีย์หลักออกไป
เพื่อให้แอตตริบิวที่ไม่ใช่คีย์หลักต้องขึ้นตรงกับทั้งส่วนที่เป็นคีย์หลัก และไม่ขึ้นกับแอตตริบิวอื่นที่ไม่ใช่
คีย์หลัก
นิยาม ของ Transitive dependency
การไม่ขึ้นตรงกับคีย์หลัก (Transitively Dependency) ถ้าในความสัมพันธ์ R มีคีย์หลักคือ K
และแอตตริบิว A และ B จะกล่าวว่าแอตตริบิว B ไม่ขึ้นตรงกับคีย์หลัก
เมื่อ K -----------> A และ A ----------> B และ A ---/--> K
ตัวอย่างการทำ ตารางให้เป็น 3NF
ผู้บริหาร (เลขประจำ ตัว , ชื่อนามสกุล , ที่อยู่ , ตำ แหน่ง, ยี่__________ห้อรถประจำ ตำ แหน่ง)
FD = { เลขประจำ ตัว 􀃆 ชื่อนามสกุล , ที่อยู่ , ตำ แหน่ง
ตำ แหน่ง 􀃆 ยี่ห้อรถประจำ ตำ แหน่ง }
ในตัวอย่างจะเห็นได้ว่า set ของ ผู้บริหาร (เลขประจำ ตัว , ชื่อนามสกุล , ที่อยู่, ตำ แหน่ง, ยี่ห้อ
รถประจำ ตำ แหน่ง) นี้ ยังไม่ใช่ 3NF เพราะ เลขประจำ ตัว􀃆ตำ แหน่ง ตำ แหน่ง􀃆 ยี่ห้อรถประจำ
ตำ แหน่ง ดังนั้น ควรจะแยก เซ็ทผู้บริหาร ออกเป็น 2 เซ็ท คือ
3NF: ผู้บริหาร (เลขประจำ ตัว , ชื่อนามสกุล , ที่อยู่, ตำ แหน่ง)
ตำ แหน่งบริหาร (ตำ แหน่ง , ยี่ห้อรถประจำ ตำ แหน่ง)
7.2.4 BCNF (Boyce/Codd Normal Form)
นิยาม
ต้องเป็น 3NF และไม่มี attribute อื่นในรีเลชันที่สามารถระบุค่าของ attribute ที่เป็นคีย์
หลัก หรือส่วนหนึ่งส่วนใดของคีย์หลักในกรณีที่คีย์หลักเป็นคีย์ผสม
โดยทั่วไปรูปแบบ BCNF จะอยู่ในรูปแบบ 3NF แต่ไม่จำ เป็นเสมอไปที่รูปแบบ 3NF จะอยู่ในรูป
แบบ BCNF ทั้งนี้เนื่องจากรูปแบบนี้เป็นการขยายขอบเขตของรูปแบบ 3NF ให้เหมาะสมยิ่งขึ้น โดยรูป
แบบที่ต้องทำ ให้เป็น BCNF มักจะมีคุณสมบัติ ดังนี้
เป็นรีเลชันที่มีคีย์คู่แข่งหลายคีย์ (Multiple Candidate Key) โดยที่
คีย์คู่แข่งเป็นคีย์ผสม (Composite Key) และ
คีย์คู่แข่งนั้นมีบางส่วนซํ้าซ้อนกัน (Overlapped) ๖มี attribute บางตัวร่วมกันอยู่)
บทที่ 7 การนอร์มัลไลซ์ (Normalization) 7 - 7
จากตัวอย่างตารางต่อไปนี้
รหัสนักศึกษา ชื่อนักศึกษา รหัสวิชา เกรด
001
001
002
002
002
003
Jane
Jane
Timmy
Timmy
Timmy
Nan
C01
C02
C01
C02
C03
C04
ABC
BDD
จากตารางนี้จะได้ว่า
รหัสนักศึกษา, รหัสวิชา 􀃆 เกรด
ชื่อนักศึกษา, รหัสวิชา 􀃆 เกรด
รหัสนักศึกษา 􀃆 ชื่อนักศึกษา
รหัสพนักงาน 􀃆 ชื่อพนักงาน
ตารางนี้มี 4 determinants คือ (รหัสนักศึกษา, รหัสวิชา) (ชื่อนักศึกษา, รหัสวิชา) (รหัส
พนักงาน) และ (ชื่อพนักงาน) แต่ตารางนี้มีเพียง 2 candidate keys คือ (รหัสนักศึกษา, รหัสวิชา) และ
(ชื่อนักศึกษา, รหัสวิชา) สำ หรับรหัสนักศึกษา และชื่อนักศึกษาไม่ใช่ candidate key เราจะพบว่าตาราง
นี้เป็น 3NF ที่ไม่ดีพอเนื่องจากตารางนี้มี candidate key 2 keys ด้วยกัน เราสามารถเลือกอันใดอันหนึ่ง
เป็น primary key ได้ นอกจากนี้ candidate key ทั้งสองยังเป็น composite key และ overlap กันอยู่
เพราะมีรหัสวิชาร่วมกัน ทำ ให้มีข้อมูลหนึ่งชุดปรากฏหลายหนถึงแม้จะเป็น 3NF แล้วก็ตาม จึงควรปรับ
ต่อไปเพื่อลดความซํ้าซ้อนนี้ลง และเพื่อแก้ปัญหาการ insert delete และ update ข้อมูลในตาราง โดย
ใช้วิธีการของ BCNF ดังนี้
1. ถ้ามี Transitive FD ให้ขจัด Transitive FD ทิ้งไป
2. attribute ตัวใดที่เป็น determinant ทำ ให้เป็น candidate key
จากตารางข้างต้นเราสามารถแยกออกเป็นตารางใหม่ ได้ 2 ตาราง ดังนี้
นักศึกษา (รหัสนักศึกษา, ชื่อนักศึกษา)
เกรด (รหัสนักศึกษา, รหัสวิชา, เกรด)
หรือ
นักศึกษา (รหัสนักศึกษา, ชื่อนักศึกษา)
เกรด (ชื่อนักศึกษา, รหัสวิชา, เกรด)__

ไม่มีความคิดเห็น:

แสดงความคิดเห็น