การขึ้นต่อกันเชิงฟังก์ชัน

การขึ้นต่อกันเชิงฟังก์ชัน (functional dependency) คือข้อจำกัดที่ระบุว่าค่าของชุดแอตทริบิวต์หนึ่งจะกำหนดค่าของอีกชุดหนึ่งโดยไม่ซ้ำกัน การขึ้นต่อกันเชิงฟังก์ชันเป็นข้อมูลนำเข้าเชิงความหมายที่ขับเคลื่อนการค้นหาคีย์และการทำให้เป็นบรรทัดฐาน (normalization)

Definition

การขึ้นต่อกันเชิงฟังก์ชัน X → Y บนโครงร่างความสัมพันธ์ (relation schema) จะเป็นจริงได้ก็ต่อเมื่อ ในทุกอินสแตนซ์ที่ถูกต้อง ทูเพิลสองทูเพิลใดๆ ที่มีค่าตรงกันในแอตทริบิวต์ทั้งหมดใน X จะต้องมีค่าตรงกันในแอตทริบิวต์ทั้งหมดใน Y ด้วย นั่นคือ X กำหนด Y ในเชิงฟังก์ชัน

Scope

หัวข้อนี้ครอบคลุมการขึ้นต่อกันเชิงฟังก์ชัน (FDs) และทฤษฎีที่เป็นทางการ: คำจำกัดความของ X → Y, การขึ้นต่อกันแบบไม่สำคัญและแบบไม่สำคัญ, สัจพจน์ของอาร์มสตรอง (Armstrong's axioms) (การสะท้อนกลับ, การเพิ่ม, การถ่ายทอด) และความสมเหตุสมผลและความสมบูรณ์ของสัจพจน์เหล่านี้, การปิดของชุดแอตทริบิวต์และของชุด FDs, การครอบคลุมแบบบัญญัติ (canonical/minimal covers) และการใช้ FDs เพื่อคำนวณคีย์ผู้สมัคร (candidate keys) หัวข้อนี้ไม่รวมการขึ้นต่อกันแบบหลายค่า (multivalued) และการรวม (join dependencies) และรูปแบบบรรทัดฐาน (normal forms) ที่ทดสอบโดยใช้ FDs ซึ่งจะกล่าวถึงในหัวข้อที่เกี่ยวข้อง

Core questions

• การที่ชุดแอตทริบิวต์หนึ่งกำหนดอีกชุดหนึ่งในเชิงฟังก์ชันหมายความว่าอย่างไร?
• กฎการอนุมานใดบ้าง (สัจพจน์ของอาร์มสตรอง) ที่สมเหตุสมผลและสมบูรณ์สำหรับการขึ้นต่อกันเชิงฟังก์ชัน?
• การปิดของชุดแอตทริบิวต์คำนวณอย่างไร และใช้เพื่ออะไร?
• คีย์ผู้สมัครได้มาจากการขึ้นต่อกันเชิงฟังก์ชันชุดหนึ่งได้อย่างไร?
• การครอบคลุมแบบน้อยที่สุด (canonical/minimal cover) คืออะไร และมีประโยชน์อย่างไร?

Key concepts

• การขึ้นต่อกันเชิงฟังก์ชัน X → Y
• การขึ้นต่อกันแบบไม่สำคัญเทียบกับแบบไม่สำคัญ
• สัจพจน์ของอาร์มสตรอง
• การปิดชุดแอตทริบิวต์
• การปิดของชุดการขึ้นต่อกันเชิงฟังก์ชัน
• คีย์ผู้สมัครและซูเปอร์คีย์
• การครอบคลุมแบบน้อยที่สุด (canonical/minimal cover)
• ความสมเหตุสมผลและความสมบูรณ์

Key theories

การขึ้นต่อกันเชิงฟังก์ชัน

X → Y จำกัดความสัมพันธ์เพื่อให้ค่า X กำหนดค่า Y การขึ้นต่อกันเชิงฟังก์ชันทำให้กฎเกณฑ์ในโลกแห่งความเป็นจริง (เช่น คีย์ที่กำหนดแอตทริบิวต์อื่นๆ ทั้งหมด) ที่โครงร่างต้องบังคับใช้เป็นทางการ

สัจพจน์ของอาร์มสตรอง

การสะท้อนกลับ (reflexivity), การเพิ่ม (augmentation) และการถ่ายทอด (transitivity) เป็นระบบการอนุมานที่สมเหตุสมผลและสมบูรณ์สำหรับการขึ้นต่อกันเชิงฟังก์ชัน ดังนั้นการขึ้นต่อกันที่อนุมานได้ตามตรรกะทั้งหมดและเฉพาะการขึ้นต่อกันเหล่านั้นเท่านั้นที่สามารถอนุมานได้จากชุดที่กำหนด

การปิดแอตทริบิวต์และการครอบคลุมแบบน้อยที่สุด

การปิดของชุดแอตทริบิวต์ภายใต้ชุดการขึ้นต่อกันเชิงฟังก์ชันจะเปิดเผยว่าแอตทริบิวต์ใดที่ชุดนั้นกำหนด (และด้วยเหตุนี้จึงเป็นซูเปอร์คีย์หรือไม่) และการครอบคลุมแบบน้อยที่สุดคือชุดการขึ้นต่อกันเชิงฟังก์ชันที่เทียบเท่ากันและไม่มีความซ้ำซ้อน ซึ่งใช้เป็นพื้นฐานสำหรับการทำให้เป็นบรรทัดฐาน

Clinical relevance

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

History

การขึ้นต่อกันเชิงฟังก์ชันถูกนำเสนอโดย Codd ควบคู่ไปกับแบบจำลองเชิงสัมพันธ์และการทำให้เป็นบรรทัดฐาน และ W. W. Armstrong ได้นำเสนอระบบสัจพจน์ที่ใช้ชื่อของเขาในปี 1974 โดยพิสูจน์ว่ามีความสมเหตุสมผลและสมบูรณ์ ผลลัพธ์เหล่านี้ทำให้การให้เหตุผลเกี่ยวกับการขึ้นต่อกันเป็นแบบอัลกอริทึมและเป็นรากฐานของทฤษฎีการทำให้เป็นบรรทัดฐานทั้งหมดในเวลาต่อมา

Key figures

• Edgar F. Codd
• William W. Armstrong

Seminal works

• codd1972
• armstrong1974
• silberschatz2019

Frequently asked questions

การขึ้นต่อกันเชิงฟังก์ชันแตกต่างจากคีย์อย่างไร?

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

ทำไมต้องคำนวณการครอบคลุมแบบน้อยที่สุด?

การครอบคลุมแบบน้อยที่สุด (canonical/minimal cover) คือชุดการขึ้นต่อกันเชิงฟังก์ชันที่เทียบเท่ากันโดยไม่มีการขึ้นต่อกันที่ซ้ำซ้อนหรือแอตทริบิวต์ที่ไม่จำเป็น การทำงานจากการครอบคลุมแบบน้อยที่สุดจะช่วยให้การค้นหาคีย์ง่ายขึ้นและสร้างการแยกส่วนที่สะอาดขึ้นในระหว่างการทำให้เป็นบรรทัดฐาน โดยเฉพาะอย่างยิ่งเมื่อต้องการออกแบบที่รักษาการขึ้นต่อกัน