ทฤษฎีบทของค็อดด์
ทฤษฎีบทของ Coddกล่าวว่าพีชคณิตเชิงสัมพันธ์ และการค้นหา ข้อมูลเชิงสัมพันธ์ที่ไม่ขึ้นกับโดเมนซึ่งเป็นภาษาการค้นหาข้อมูลพื้นฐานที่รู้จักกันดีสองภาษาสำหรับแบบจำลองเชิงสัมพันธ์นั้น มีความเทียบเท่ากันอย่างแม่นยำในด้านพลังการแสดงออก กล่าวคือ การค้นหาข้อมูลในฐานข้อมูลสามารถกำหนดได้ในภาษาหนึ่งก็ต่อเมื่อสามารถแสดงออกได้ในอีกภาษาหนึ่งเท่านั้น
ทฤษฎีบทนี้ตั้งชื่อตามเอ็ดการ์ เอฟ. คอดด์บิดาแห่งแบบจำลองเชิงสัมพันธ์สำหรับการจัดการฐานข้อมูล
แบบสอบถาม แคลคูลัสเชิงสัมพันธ์ที่ไม่ขึ้นกับโดเมนคือแบบสอบถามแคลคูลัสเชิงสัมพันธ์ที่ไม่เปลี่ยนแปลงไปตามการเลือกโดเมนของค่าที่อยู่นอกเหนือจากที่ปรากฏในฐานข้อมูล กล่าวคือ แบบสอบถามที่อาจให้ผลลัพธ์ที่แตกต่างกันสำหรับโดเมนที่แตกต่างกันจะถูกยกเว้น ตัวอย่างของแบบสอบถามที่ต้องห้ามดังกล่าวคือแบบสอบถาม "เลือกทูเปิลทั้งหมดที่ไม่ใช่ทูเปิลที่ปรากฏในความสัมพันธ์ R" โดยที่ R เป็นความสัมพันธ์ในฐานข้อมูล หากสมมติว่ามีโดเมนที่แตกต่างกัน กล่าวคือ ชุดของรายการข้อมูลอะตอมิกที่สามารถสร้างทูเปิลได้ แบบสอบถามนี้จะให้ผลลัพธ์ที่แตกต่างกัน ดังนั้นจึงเห็นได้ชัดว่าไม่ใช่แบบสอบถามที่ไม่ขึ้นกับโดเมน
ทฤษฎีบทของค็อดด์มีความสำคัญเนื่องจากพิสูจน์ความเท่าเทียมกันของภาษาที่มีโครงสร้างทางไวยากรณ์แตกต่างกันอย่างมากสองภาษา ได้แก่พีชคณิตเชิงสัมพันธ์เป็นภาษาที่ไม่มีตัวแปร ในขณะที่แคลคูลัสเชิงสัมพันธ์เป็นภาษาตรรกะที่มีตัวแปรและการกำหนดปริมาณ
แคลคูลัสเชิงสัมพันธ์นั้นเทียบเท่ากับตรรกะลำดับที่หนึ่งโดยพื้นฐาน[ 1 ]และที่จริงแล้ว ทฤษฎีบทของ Codd เป็นที่รู้จักในหมู่นักตรรกศาสตร์มาตั้งแต่ปลายทศวรรษ 1940 [ 2 ] [ 3 ]
ภาษาการสอบถามที่มีพลังการแสดงออกเทียบเท่ากับพีชคณิตเชิงสัมพันธ์เรียกว่า ภาษา ที่มีความสมบูรณ์เชิงสัมพันธ์โดย Codd ตามทฤษฎีบทของ Codd สิ่งนี้รวมถึงแคลคูลัสเชิงสัมพันธ์ ความสมบูรณ์เชิงสัมพันธ์ไม่ได้หมายความว่าการสอบถามฐานข้อมูลที่น่าสนใจใดๆ จะสามารถแสดงออกมาในภาษาที่มีความสมบูรณ์เชิงสัมพันธ์ได้ ตัวอย่างที่รู้จักกันดีของการสอบถามที่ไม่สามารถแสดงออกมาได้ ได้แก่การรวมกลุ่ม อย่างง่าย (การนับทูเปิล หรือการรวมค่าที่เกิดขึ้นในทูเปิล ซึ่งเป็นการดำเนินการที่สามารถแสดงออกมาได้ใน SQL แต่ไม่ใช่ในพีชคณิตเชิงสัมพันธ์) และการคำนวณการปิดแบบส่งผ่านของกราฟที่กำหนดโดยความสัมพันธ์ขอบแบบไบนารี (ดูพลังการแสดงออก ด้วย ) ทฤษฎีบทของ Codd ยังไม่ได้พิจารณาค่าว่างใน SQLและตรรกะสามค่าที่เกี่ยวข้อง การจัดการเชิงตรรกะของค่าว่างยังคงติดอยู่ในข้อโต้แย้ง[ 4 ]นอกจากนี้ SQL ยังมี อรรถศาสตร์ แบบมัลติเซ็ตที่อนุญาตให้มีแถวซ้ำกันได้ อย่างไรก็ตาม ความสมบูรณ์เชิงสัมพันธ์ถือเป็นมาตรวัดที่สำคัญที่สามารถใช้เปรียบเทียบพลังการแสดงออกของภาษาการสอบถามได้
หมายเหตุ
- ↑ Abiteboul, Serge ; Hull, Richard B. ; Vianu, Victor (1995). พื้นฐานของฐานข้อมูล . Addison-Wesley. ISBN 0-201-53771-0.
- ↑ Chin, LH; Tarski, A. (1948). "ข้อสังเกตเกี่ยวกับพีชคณิตเชิงโปรเจกทีฟ" . Bulletin of the American Mathematical Society . 54 (1): 80– 81. doi : 10.1090/S0002-9904-1948-08948-0 .
- ↑ Tarski, A.; Thompson, FB (1952). "คุณสมบัติทั่วไปบางประการของพีชคณิตทรงกระบอก" . Bulletin of the American Mathematical Society . 58 (1): 65. doi : 10.1090/S0002-9904-1952-09549-5 .
- ↑สำหรับงานวิจัยล่าสุดที่ขยายทฤษฎีบทของ Codd ในทิศทางนี้ โปรดดู Franconi, Enrico; Tessaris, Sergio (2012). "On the Logic of SQL Nulls" (PDF) . Proceedings of the 6th Alberto Mendelzon International Workshop on Foundations of Data Management, Ouro Preto, Brazil, June 27–30, 2012 : 114– 128.
ลิงก์ภายนอก
- Pichler, Reinhard (20 มีนาคม 2018). "ทฤษฎีฐานข้อมูล: 3. ทฤษฎีบทของ Codd" (PDF) . สถาบันตรรกศาสตร์และการคำนวณ, กลุ่ม DBAI, มหาวิทยาลัยเทคนิคเวียนนา. เก็บถาวรจากต้นฉบับ(PDF)เมื่อวันที่ 22 สิงหาคม 2020. สืบค้นเมื่อ8 สิงหาคม 2019 .