การปรับปรุงและการแยกส่วนสกีมา

การปรับปรุงสกีมาคือกระบวนการแยกส่วนความสัมพันธ์ออกเป็นความสัมพันธ์ย่อยๆ เพื่อให้ได้รูปแบบบรรทัดฐานที่ต้องการ โดยมีข้อกำหนดว่าการแยกส่วนนั้นต้องไม่สูญเสียข้อมูล และโดยหลักการแล้วต้องรักษาการพึ่งพาข้อมูลเดิมไว้ได้

Definition

การแยกส่วน (Decomposition) คือการแทนที่สกีมาความสัมพันธ์ R ด้วยชุดของสกีมาที่มีแอตทริบิวต์รวมกันครอบคลุม R โดยที่ความสัมพันธ์เดิมสามารถกู้คืนได้โดยการเชื่อมต่อส่วนต่างๆ (การเชื่อมต่อแบบไม่สูญเสียข้อมูล) และเมื่อเป็นไปได้ การพึ่งพาเชิงฟังก์ชันเดิมทุกรายการสามารถบังคับใช้กับส่วนต่างๆ ได้ (การรักษาการพึ่งพาข้อมูล)

Scope

หัวข้อนี้ครอบคลุมอัลกอริทึมและเกณฑ์สำหรับการแยกส่วนสกีมาเชิงสัมพันธ์: คุณสมบัติการเชื่อมต่อแบบไม่สูญเสียข้อมูล (lossless-join property) และวิธีการทดสอบ, การรักษาการพึ่งพาข้อมูล (dependency preservation) และความขัดแย้งกับรูปแบบบรรทัดฐานที่สูงขึ้น, และอัลกอริทึมการสังเคราะห์และการแยกส่วนมาตรฐานที่สร้างการออกแบบ 3NF (ที่รักษาการพึ่งพาข้อมูลและไม่สูญเสียข้อมูล) หรือ BCNF (ที่ไม่สูญเสียข้อมูล) จากชุดของการพึ่งพาเชิงฟังก์ชัน (functional dependencies) หัวข้อนี้ไม่รวมคำจำกัดความของรูปแบบบรรทัดฐานเองและการพึ่งพาข้อมูลที่เป็นตัวขับเคลื่อนการแยกส่วน

Core questions

• อะไรทำให้การแยกส่วนไม่สูญเสียข้อมูล และจะทดสอบคุณสมบัตินี้ได้อย่างไร?
• การแยกส่วนที่รักษาการพึ่งพาข้อมูลหมายความว่าอย่างไร?
• เหตุใดการแยกส่วน BCNF จึงอาจไม่สามารถรักษาการพึ่งพาข้อมูลได้ ในขณะที่การสังเคราะห์ 3NF ทำได้?
• อัลกอริทึมการแยกส่วน BCNF และการสังเคราะห์ 3NF มาตรฐานทำงานอย่างไร?
• การเลือกระหว่าง BCNF และ 3NF ในทางปฏิบัติทำได้อย่างไร?

Key concepts

• การแยกส่วนของสกีมา
• คุณสมบัติการเชื่อมต่อแบบไม่สูญเสียข้อมูล
• การรักษาการพึ่งพาข้อมูล
• ทูเพิลปลอม (spurious tuples)
• อัลกอริทึมการแยกส่วน BCNF
• อัลกอริทึมการสังเคราะห์ 3NF
• การครอบคลุมน้อยที่สุด (minimal cover)
• การแลกเปลี่ยนระหว่าง BCNF และ 3NF

Key theories

การแยกส่วนแบบไม่สูญเสียข้อมูล

การแยกส่วนแบบไบนารีจะไม่สูญเสียข้อมูล หากแอตทริบิวต์ร่วมกันของทั้งสองส่วนประกอบเป็นคีย์ของอย่างน้อยหนึ่งส่วน การไม่สูญเสียข้อมูลรับประกันว่าการเชื่อมต่อส่วนต่างๆ จะสร้างความสัมพันธ์เดิมขึ้นมาใหม่ได้อย่างแม่นยำโดยไม่มีทูเพิลปลอม

การรักษาการพึ่งพาข้อมูล

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

การแยกส่วน BCNF เทียบกับการสังเคราะห์ 3NF

อัลกอริทึมการแยกส่วน BCNF รับประกันการไม่สูญเสียข้อมูล แต่อาจเสียสละการรักษาการพึ่งพาข้อมูล ในขณะที่อัลกอริทึมการสังเคราะห์ 3NF จากการครอบคลุมน้อยที่สุดรับประกันทั้งการเชื่อมต่อแบบไม่สูญเสียข้อมูลและการรักษาการพึ่งพาข้อมูล โดยมีค่าใช้จ่ายที่อาจหยุดอยู่ที่ 3NF

Clinical relevance

อัลกอริทึมการแยกส่วนเป็นวิธีที่ทฤษฎีการทำให้เป็นบรรทัดฐานกลายเป็นขั้นตอนการออกแบบที่นำไปปฏิบัติได้: การประยุกต์ใช้อัลกอริทึมเหล่านี้จะให้สกีมาที่หลีกเลี่ยงความซ้ำซ้อน แต่ยังคงสามารถสร้างใหม่และตรวจสอบได้อย่างมีประสิทธิภาพ ซึ่งส่งผลโดยตรงต่อความถูกต้องและการบำรุงรักษาฐานข้อมูลที่ใช้งานจริง

History

ทฤษฎีการแยกส่วนแบบไม่สูญเสียข้อมูลและการรักษาการพึ่งพาข้อมูลได้รับการพัฒนาตลอดช่วงทศวรรษ 1970 ในขณะที่นักวิจัยได้กำหนดอย่างเป็นทางการว่าเมื่อใดที่การแยกความสัมพันธ์จะปลอดภัย อัลกอริทึมการสังเคราะห์ที่สร้างการออกแบบ 3NF ที่รักษาการพึ่งพาข้อมูล และการรับรู้ว่า BCNF อาจขัดแย้งกับการรักษาการพึ่งพาข้อมูล ได้กลายเป็นเนื้อหามาตรฐานในตำราฐานข้อมูลและยังคงเป็นหัวใจสำคัญของการออกแบบสกีมา

Key figures

• Edgar F. Codd
• Jeffrey D. Ullman
• Philip Bernstein

Seminal works

• silberschatz2019
• ramakrishnan2003
• garciamolina2008

Frequently asked questions

ทูเพิลปลอมคืออะไร และทำไมจึงสำคัญ?

ทูเพิลปลอมคือแถวที่ปรากฏขึ้นเมื่อคุณเชื่อมต่อส่วนต่างๆ ของการแยกส่วนที่เลือกไม่ดี แต่ไม่สอดคล้องกับทูเพิลจริงใดๆ ของความสัมพันธ์เดิม การแยกส่วนแบบไม่สูญเสียข้อมูลคือการแยกส่วนที่ไม่สร้างทูเพิลปลอม ซึ่งเป็นเหตุผลว่าทำไมการไม่สูญเสียข้อมูลจึงเป็นข้อกำหนดที่ไม่อาจต่อรองได้

เหตุใดฉันจึงอาจเลือก 3NF แทน BCNF?

การแยกส่วนเป็น BCNF จะรักษาคุณสมบัติการเชื่อมต่อแบบไม่สูญเสียข้อมูลเสมอ แต่อาจทำให้การรักษาการพึ่งพาข้อมูลเสียหายได้ ซึ่งหมายความว่าข้อจำกัดบางอย่างสามารถตรวจสอบได้โดยการเชื่อมต่อตารางเท่านั้น อัลกอริทึมการสังเคราะห์ 3NF รับประกันทั้งการไม่สูญเสียข้อมูลและการรักษาการพึ่งพาข้อมูล ดังนั้นผู้ออกแบบจึงยอมรับ 3NF เมื่อไม่มีการออกแบบ BCNF ที่รักษาการพึ่งพาข้อมูลอยู่