ในทฤษฎีฐานข้อมูลพีชคณิตเชิงสัมพันธ์เป็นทฤษฎีที่ใช้โครงสร้างพีชคณิตในการสร้างแบบจำลองข้อมูลและกำหนดคำถามเกี่ยวกับข้อมูลด้วยความหมายที่ มีพื้นฐานที่ดี ทฤษฎีนี้ได้รับการแนะนำโดยEdgar F. Codd ^{[ 1 ]}

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

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

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

พีชคณิตเชิงสัมพันธ์ได้รับความสนใจเพียงเล็กน้อยนอกเหนือจากคณิตศาสตร์บริสุทธิ์จนกระทั่งมีการตีพิมพ์แบบจำลองข้อมูลเชิงสัมพันธ์ของEF Coddในปี 1970 ^{[ 2 ]} Codd เสนอพีชคณิตดังกล่าวเป็นพื้นฐานสำหรับภาษาการสอบถามฐานข้อมูล

ความสัมพันธ์ที่มีจำนวน สมาชิก n ตัว คือเซตของทูเปิล n ตัว พีชคณิตเชิงสัมพันธ์ทำงานกับเซตของทูเปิลที่เป็นเอกพันธุ์โดยที่ ทูเปิล n ตัวคือทูเปิล (แถว; ดัชนีj ) [ ^{a ] ที่}มีแอตทริบิวต์n ประเภท (หรือโดเมนข้อมูล ) ดังนั้นmคือจำนวนแถวของทูเปิลในตาราง และnคือจำนวนคอลัมน์ (และรายการทั้งหมดในแต่ละคอลัมน์มี' ประเภท' เดียวกัน ) ${\displaystyle S=\{(s_{j1},s_{j2},...s_{jn})\mid j\in 1...m\},}$

ความสัมพันธ์ยังมีทูเปิลที่ไม่ซ้ำกันเรียกว่าส่วนหัวซึ่งกำหนดชื่อหรือคุณลักษณะ ที่ไม่ซ้ำกันให้กับแต่ละคอลัมน์ ภายในความสัมพันธ์ คุณลักษณะเหล่านี้ใช้ในการฉายภาพและการเลือกข้อมูล

พีชคณิตเชิงสัมพันธ์ใช้การรวมเซตความแตกต่างของเซตและผลคูณคาร์ทีเซียนจากทฤษฎีเซต และเพิ่มข้อจำกัดเพิ่มเติมให้กับตัวดำเนินการเหล่านี้เพื่อสร้างตัวดำเนินการใหม่^{[ 3 ]}

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

เพื่อให้สามารถนิยามผลคูณคาร์ทีเซียนได้ ความสัมพันธ์ทั้งสองจะต้องมีส่วนหัวที่ไม่ซ้ำกัน (กล่าวคือ จะต้องไม่มีชื่อแอตทริบิวต์ร่วมกัน)

นอกจากนี้ ผลคูณคาร์ทีเซียนยังถูกนิยามแตกต่างจากในทฤษฎีเซตในแง่ที่ว่าทูเพิลถือว่า "ตื้น" สำหรับวัตถุประสงค์ของการดำเนินการ นั่นหมายความว่า ผลคูณคาร์ทีเซียนของเซตของ ทูเพิล nตัวกับเซตของทู เพิล mตัว จะได้เซตของทูเพิลที่ "แบนราบ" (ในขณะที่ทฤษฎีเซตพื้นฐานจะกำหนดเซตของทูเพิล 2 ตัว โดยแต่ละเซตประกอบด้วย ทูเพิล nตัวและทู เพิล mตัว) ในพีชคณิตเชิงสัมพันธ์ ผลคูณคาร์ทีเซียนถูกนิยามอย่างเป็นทางการดังนี้ ${\displaystyle (n+m)}$${\displaystyle R\times S}$

จำนวนสมาชิกของผลคูณคาร์ทีเซียนคือผลคูณของจำนวนสมาชิกของตัวประกอบของมัน นั่นคือ| R × S | = | R | × | S |

การฉายภาพ ( Π ) เป็นการดำเนินการเอกภาคที่เขียนได้เป็น โดยที่เป็นเซตของชื่อแอตทริบิวต์ ผลลัพธ์ของการฉายภาพดังกล่าวถูกกำหนดให้เป็นเซตที่ได้เมื่อทูเปิลทั้งหมด ในRถูกจำกัดให้อยู่ในเซต${\displaystyle \Pi _{a_{1},\ldots ,a_{n}}(R)}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle \{a_{1},\ldots ,a_{n}\}}$

หมายเหตุ: เมื่อนำไปใช้ใน มาตรฐาน SQL "การฉายภาพเริ่มต้น" จะส่งคืนมัลติเซ็ตแทนที่จะเป็นเซ็ต และ การฉายภาพ Πเพื่อกำจัดข้อมูลที่ซ้ำกันจะได้รับโดยการเพิ่มDISTINCTคำหลัก .

การเลือกแบบทั่วไป (σ) คือการดำเนินการเอกภาคที่เขียนได้เป็น โดยที่φคือสูตรเชิงประพจน์ที่ประกอบด้วยอะตอมตามที่อนุญาตในการเลือกแบบปกติและตัวดำเนินการตรรกะ( และ ), ( หรือ ) และ( การปฏิเสธ ) การเลือกนี้จะเลือกทูเปิล ทั้งหมด ในRที่φเป็นจริง ${\displaystyle \sigma _{\varphi }(R)}$${\displaystyle \wedge }$${\displaystyle \lor }$${\displaystyle \neg }$

เพื่อให้ได้รายชื่อเพื่อนหรือผู้ร่วมธุรกิจทั้งหมดในสมุดที่อยู่ อาจเขียนตัวเลือกได้ดังนี้ ผลลัพธ์ที่ได้จะเป็นความสัมพันธ์ที่มีคุณลักษณะทั้งหมดของทุกระเบียนที่ไม่ซ้ำกัน โดยที่isFriendเป็นจริง หรือisBusinessContactเป็นจริง $${\displaystyle \sigma _{{\text{isFriend = true}}\,\lor \,{\text{isBusinessContact = true}}}({\text{addressBook}}).}$$

การเปลี่ยนชื่อ ( ρ ) เป็นการดำเนินการแบบเอกภาคที่เขียนได้ดังนี้ โดยผลลัพธ์จะเหมือนกับRยกเว้นว่า แอตทริบิวต์ bในทูเปิลทั้งหมดจะถูกเปลี่ยนชื่อเป็นแอตทริบิวต์ a การดำเนินการนี้มักใช้ในการเปลี่ยนชื่อแอตทริบิวต์ของความสัมพันธ์เพื่อวัตถุประสงค์ในการเชื่อมต่อ (join) ${\displaystyle \rho _{a/b}(R)}$

อาจใช้ การเปลี่ยนชื่อแอตทริบิวต์ "isFriend" เป็น "isBusinessContact" ในความสัมพันธ์ได้${\displaystyle \rho _{\text{isBusinessContact / isFriend}}({\text{addressBook}})}$

นอกจากนี้ยังมีสัญลักษณ์ที่Rถูกเปลี่ยนชื่อเป็นxและแอตทริบิวต์ถูกเปลี่ยนชื่อเป็น. ^{[ 4 ]}${\displaystyle \rho _{x(A_{1},\ldots ,A_{n})}(R)}$${\displaystyle \{a_{1},\ldots ,a_{n}\}}$${\displaystyle \{A_{1},\ldots ,A_{n}\}}$

ในทางปฏิบัติ พีชคณิตเชิงสัมพันธ์แบบคลาสสิกที่อธิบายไว้ข้างต้นได้รับการขยายด้วยการดำเนินการต่างๆ เช่น การเชื่อมต่อภายนอก ฟังก์ชันการรวม และแม้กระทั่งการปิดแบบส่งผ่าน^{[ 5 ]}

ในขณะที่ผลลัพธ์ของการรวม (หรือการรวมภายใน) ประกอบด้วยทูเปิลที่สร้างขึ้นโดยการรวมทูเปิลที่ตรงกันในตัวดำเนินการทั้งสอง การรวมภายนอกจะมีทูเปิลเหล่านั้นและทูเปิลเพิ่มเติมที่สร้างขึ้นโดยการขยายทูเปิลที่ไม่ตรงกันในตัวดำเนินการหนึ่งด้วยค่า "เติม" สำหรับแต่ละแอตทริบิวต์ของตัวดำเนินการอื่น การรวมภายนอกไม่ถือเป็นส่วนหนึ่งของพีชคณิตเชิงสัมพันธ์แบบคลาสสิกที่กล่าวถึงไปแล้ว^{[ 6 ]}

ตัวดำเนินการที่กำหนดไว้ในส่วนนี้ถือว่ามีค่าว่างωซึ่งเราไม่ได้กำหนดไว้ เพื่อใช้เป็นค่าเติม ในทางปฏิบัติ ค่านี้จะตรงกับNULLใน SQL เพื่อให้การดำเนินการเลือกข้อมูลในตารางที่ได้มีความหมาย จำเป็นต้องกำหนดความหมายเชิงความหมายให้กับค่าว่าง ในแนวทางของ Codd ตรรกะเชิงประพจน์ที่ใช้ในการเลือกจะถูกขยายไปเป็นตรรกะสามค่าแม้ว่าเราจะละเว้นรายละเอียดเหล่านั้นในบทความนี้ก็ตาม

มีการกำหนดตัวดำเนินการเชื่อมต่อภายนอก (outer join) ไว้สามแบบ ได้แก่ การเชื่อมต่อภายนอกด้านซ้าย (left outer join), การเชื่อมต่อภายนอกด้านขวา (right outer join) และการเชื่อมต่อภายนอกแบบเต็ม (full outer join) (บางครั้งอาจละคำว่า "outer")

การเชื่อมแบบ Left Outer Join (⟕) เขียนเป็นR ⟕ Sโดยที่RและSเป็นความสัมพันธ์^{[ b ]}ผลลัพธ์ของการเชื่อมแบบ Left Outer Join คือเซตของการรวมกันทั้งหมดของทูเปิลในRและSที่เท่ากันในชื่อแอตทริบิวต์ร่วมกัน นอกเหนือจาก (โดยคร่าวๆ) ทูเปิลในRที่ไม่มีทูเปิลที่ตรงกันใน S

ตัวอย่างเช่น ลองพิจารณาตารางEmployeeและDeptและการเชื่อมตารางทั้งสองเข้าด้วยกันโดยใช้ Left Outer Join:

ในความสัมพันธ์ที่ได้นั้น ทูเปิลในSที่ไม่มีค่าร่วมกันในชื่อแอตทริบิวต์ทั่วไปกับทูเปิลในRจะมีค่าเป็น nullคือ ω

เนื่องจากไม่มีทูเปิลในตาราง Deptที่มีDeptNameเป็นFinanceหรือExecutiveดังนั้น ค่า ωจึงเกิดขึ้นในความสัมพันธ์ที่ได้ผลลัพธ์ซึ่งทูเปิลในตาราง EmployeeมีDeptNameเป็นFinanceหรือExecutive

ให้r ₁ , r ₂ , ..., r _nเป็นแอตทริบิวต์ของความสัมพันธ์Rและให้ {( ω , ..., ω )} เป็นความสัมพันธ์แบบซิงเกิลตันบนแอตทริบิวต์ที่ไม่ซ้ำกันในความสัมพันธ์S (แอตทริบิวต์ที่ไม่ใช่แอตทริบิวต์ของR ) จากนั้นการเชื่อมแบบ Left Outer Join สามารถอธิบายได้ในแง่ของการเชื่อมแบบ Natural Join (และด้วยเหตุนี้จึงใช้ตัวดำเนินการพื้นฐาน) ดังนี้:

$${\displaystyle (R\bowtie S)\cup ((R-\pi _{r_{1},r_{2},\dots ,r_{n}}(R\bowtie S))\times \{(\omega ,\dots ,\omega )\})}$$

การเชื่อมตารางแบบ Right Outer Join (⟖) ทำงานเกือบเหมือนกับการเชื่อมตารางแบบ Left Outer Join แต่บทบาทของตารางจะสลับกัน

การเชื่อมแบบ right outer join ระหว่างความสัมพันธ์RและSเขียนได้เป็นR ⟖ S [ ^{c ] ผลลัพธ์}ของการเชื่อมแบบ right outer join คือเซตของการรวมกันทั้งหมดของทูเปิลในRและSที่เท่ากันในชื่อแอตทริบิวต์ร่วมกัน นอกเหนือจากทูเปิลในSที่ไม่มีทูเปิลที่ตรงกันใน R

ตัวอย่างเช่น พิจารณาตารางEmployeeและDeptและการเชื่อมต่อแบบ right outer join ระหว่างตารางทั้งสอง:

ในความสัมพันธ์ที่ได้นั้น ทูเปิลในRที่ไม่มีค่าร่วมกันในชื่อแอตทริบิวต์ทั่วไปกับทูเปิลในSจะมีค่าเป็น nullคือ ω

เนื่องจากไม่มีทูเปิลในตารางEmployeeที่มีDeptNameเป็นProductionดังนั้น ค่า ωจึงปรากฏในแอตทริบิวต์ Name และ EmpId ของความสัมพันธ์ที่ได้ โดยที่ทูเปิลในตาราง DeptมีDeptNameเป็นProduction

ให้s ₁ , s ₂ , ..., s _nเป็นแอตทริบิวต์ของความสัมพันธ์Sและให้ {( ω , ..., ω )} เป็นความสัมพันธ์แบบซิงเกิลตันบนแอตทริบิวต์ที่ไม่ซ้ำกันในความสัมพันธ์R (แอตทริบิวต์ที่ไม่ใช่แอตทริบิวต์ของS ) จากนั้น เช่นเดียวกับการเชื่อมภายนอกด้านซ้าย การเชื่อมภายนอกด้านขวาสามารถจำลองได้โดยใช้การเชื่อมแบบธรรมชาติ ดังนี้:

$${\displaystyle (R\bowtie S)\cup (\{(\omega ,\dots ,\omega )\}\times (S-\pi _{s_{1},s_{2},\dots ,s_{n}}(R\bowtie S)))}$$

การเชื่อมแบบ Outer Join (⟗) หรือFull Outer Join นั้น โดยพื้นฐานแล้วเป็นการรวมผลลัพธ์ของการเชื่อมแบบ Left Outer Join และ Right Outer Join เข้าด้วยกัน

การเชื่อมแบบเต็มออกด้านนอก (Full Outer Join) เขียนได้เป็นR ⟗ Sโดยที่RและSเป็นความสัมพันธ์ [ ^{d ] ผลลัพธ์}ของการเชื่อมแบบเต็มออกด้านนอกคือเซตของการรวมกันทั้งหมดของทูเปิลในRและSที่เท่ากันในชื่อแอตทริบิวต์ร่วมกัน นอกเหนือจากทูเปิลในSที่ไม่มีทูเปิลที่ตรงกันในRและทูเปิลในRที่ไม่มีทูเปิลที่ตรงกันในSในชื่อแอตทริบิวต์ร่วมกัน

ตัวอย่างเช่น ลองพิจารณาตารางEmployeeและDeptและการเชื่อมต่อแบบเต็ม (full outer join) ของทั้งสองตาราง:

ในความสัมพันธ์ที่ได้นั้น ทูเปิลในRที่ไม่มีค่าร่วมกันในชื่อแอตทริบิวต์ทั่วไปกับทูเปิลในSจะมีค่าเป็น null คือ ωส่วนทูเปิลในSที่ไม่มีค่าร่วมกันในชื่อแอตทริบิวต์ทั่วไปกับทูเปิลในRก็จะมีค่าเป็น nullคือ ω เช่นกัน

การเชื่อมต่อภายนอกแบบเต็มรูปแบบสามารถจำลองได้โดยใช้การเชื่อมต่อภายนอกด้านซ้ายและด้านขวา (และด้วยเหตุนี้จึงรวมถึงการเชื่อมต่อแบบธรรมชาติและการรวมเซต) ดังต่อไปนี้:

R ⟗ S = ( R ⟕ S ) ∪ ( R ⟖ S )

ในพีชคณิตเชิงสัมพันธ์ที่นำเสนอมาจนถึงตอนนี้ ไม่มีอะไรที่จะอนุญาตให้คำนวณบนโดเมนข้อมูลได้ (นอกเหนือจากการประเมินนิพจน์เชิงประพจน์ที่เกี่ยวข้องกับความเท่าเทียมกัน) ตัวอย่างเช่น การใช้พีชคณิตที่นำเสนอมาจนถึงตอนนี้เพียงอย่างเดียว จะไม่สามารถเขียนนิพจน์ที่คูณตัวเลขจากสองคอลัมน์ได้ เช่น ราคาต่อหน่วยกับปริมาณเพื่อให้ได้ราคารวม ภาษาการสอบถามเชิงปฏิบัติมีสิ่งอำนวยความสะดวกดังกล่าว เช่น คำสั่ง SELECT ของ SQL อนุญาตให้ดำเนินการทางคณิตศาสตร์เพื่อกำหนดคอลัมน์ใหม่ในผลลัพธ์และสิ่งอำนวยความสะดวกที่คล้ายกันนี้มีให้ชัดเจนยิ่งขึ้นโดยคำหลัก ของ Tutorial D ^{[ 7 ]}ในทฤษฎีฐานข้อมูล สิ่งนี้เรียกว่า การฉาย ภาพแบบขยาย^{[ 8 ] : 213} SELECTunit_price*quantityAStotal_priceFROMtEXTEND

นอกจากนี้ การคำนวณฟังก์ชันต่างๆ บนคอลัมน์ เช่น การหาผลรวมขององค์ประกอบในคอลัมน์นั้น ก็ไม่สามารถทำได้โดยใช้พีชคณิตเชิงสัมพันธ์ที่ได้กล่าวมาแล้ว ระบบฐานข้อมูลเชิงสัมพันธ์ส่วนใหญ่มีฟังก์ชันการรวมข้อมูลอยู่ 5 ฟังก์ชัน_{ได้แก่ ผลรวม จำนวน ค่าเฉลี่ย ค่าสูงสุด และค่าต่ำสุด ในพีชคณิตเชิงสัมพันธ์ การดำเนินการรวมข้อมูลบนสคีมา (A1 ,} A2 , ... An ) เขียน_ได้ดังนี้:

${\displaystyle G_{1},G_{2},\ldots ,G_{m}\ g_{f_{1}({A_{1}}'),f_{2}({A_{2}}'),\ldots ,f_{k}({A_{k}}')}\ (r)}$

โดยที่ A j ′ แต่ละอัน, 1 _≤ j ≤ k ,เป็นหนึ่งในคุณลักษณะดั้งเดิมA _i , 1 ≤ i ≤ n

คุณลักษณะที่อยู่ก่อนหน้าgคือคุณลักษณะสำหรับการจัดกลุ่ม ซึ่งทำหน้าที่คล้ายกับคำสั่ง "group by" ใน SQL จากนั้นจะมีฟังก์ชันการรวมข้อมูลจำนวนมากที่ใช้กับคุณลักษณะแต่ละรายการ การดำเนินการนี้จะถูกนำไปใช้กับความสัมพันธ์r ใด ๆ คุณลักษณะสำหรับการจัดกลุ่มนั้นเป็นตัวเลือก และหากไม่ได้ระบุไว้ ฟังก์ชันการรวมข้อมูลจะถูกนำไปใช้กับความสัมพันธ์ทั้งหมดที่การดำเนินการนั้นถูกนำไปใช้

สมมติว่าเรามีตารางชื่อAccountที่มีสามคอลัมน์ ได้แก่Account_Number, Branch_NameและBalanceเราต้องการหาค่าสูงสุดของยอดคงเหลือในแต่ละสาขา ซึ่งทำได้โดยใช้_{สูตร Branch_Name} G _{Max( Balance )} ( Account ) หากต้องการหาค่าสูงสุดของยอดคงเหลือทั้งหมดของทุกบัญชีโดยไม่คำนึงถึงสาขา เราสามารถเขียนได้ง่ายๆ ว่าG _{Max( Balance )} ( Account )

การจัดกลุ่มมักจะเขียนเป็น_{Branch_Name} ɣ _{Max( Balance )} ( Account ) แทน^{[ 8 ]}

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

${\displaystyle \forall x\forall y\forall z\left((x,y)\in R^{+}\wedge (y,z)\in R^{+}\Rightarrow (x,z)\in R^{+}\right)}$

^{สามารถพิสูจน์ ได้}โดยใช้ข้อเท็จจริงที่ว่าไม่มีนิพจน์พีชคณิตเชิงสัมพันธ์E ( R ) ที่ใช้Rเป็นตัวแปรอาร์กิวเมนต์ที่สร้างR ⁺ [ ^{9 ]}

อย่างไรก็ตาม SQL รองรับการค้นหาแบบ fixpoint อย่างเป็นทางการ มาตั้งแต่ปี 1999 และมีส่วนขยายเฉพาะของผู้จำหน่ายในทิศทางนี้มานานก่อนหน้านั้นแล้ว

แผนการค้นหา ที่เป็น ไปได้สองแบบสำหรับการค้นหาแบบสามเหลี่ยมได้แก่${\displaystyle R(A,B)\bowtie S(B,C)\bowtie T(A,C)}$แบบแรกจะเชื่อมSและTก่อน แล้วจึงเชื่อมผลลัพธ์กับRและแบบที่สองจะเชื่อมRและSก่อน แล้วจึงเชื่อมผลลัพธ์กับT

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

สามารถแสดงคำถาม ในรูปแบบ โครงสร้างต้นไม้ ได้ โดยที่

• โหนดภายในคือตัวดำเนินการ
• ใบไม้มีความสัมพันธ์กัน
• ซับทรีคือซับเอ็กซ์เพรสชัน

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

ต่อไปนี้คือชุดกฎที่สามารถนำมาใช้ในการแปลงดังกล่าวได้

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

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

1. ${\displaystyle \sigma _{A}(R)=\sigma _{A}\sigma _{A}(R)\,\!}$
2. ${\displaystyle \sigma _{A}\sigma _{B}(R)=\sigma _{B}\sigma _{A}(R)\,\!}$

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

1. ${\displaystyle \sigma _{A\land B}(R)=\sigma _{A}(\sigma _{B}(R))=\sigma _{B}(\sigma _{A}(R))}$
2. ${\displaystyle \sigma _{A\lor B}(R)=\sigma _{A}(R)\cup \sigma _{B}(R)}$

ผลคูณไขว้เป็นตัวดำเนินการที่ใช้ต้นทุนในการประเมินสูงที่สุด หากความสัมพันธ์ ที่ป้อนเข้า มี แถว NและMแถว ผลลัพธ์ก็จะมีแถวเช่นกัน ดังนั้นจึงเป็นสิ่งสำคัญที่จะต้องลดขนาดของตัวถูกดำเนินการทั้งสองก่อนที่จะใช้ตัวดำเนินการผลคูณไขว้ ${\displaystyle NM}$

วิธีนี้สามารถทำได้อย่างมีประสิทธิภาพหากตามด้วยตัวดำเนินการเลือก เช่นเมื่อพิจารณาจากนิยามของการเชื่อมต่อ (join) แล้ว นี่คือกรณีที่น่าจะเป็นไปได้มากที่สุด หากไม่ตามด้วยตัวดำเนินการเลือก เราอาจลองผลักการเลือกจากระดับที่สูงกว่าของโครงสร้างต้นไม้ของนิพจน์โดยใช้กฎการเลือกอื่นๆ ${\displaystyle \sigma _{A}(R\times P)}$

ในกรณีข้างต้น เงื่อนไขAจะถูกแบ่งออกเป็นเงื่อนไขB , CและDโดยใช้กฎการแบ่งแยกเกี่ยวกับเงื่อนไขการเลือกที่ซับซ้อน ดังนั้นB จะมีแอตทริบิวต์เฉพาะจาก R, Cจะมีแอตทริบิวต์เฉพาะจาก P และ D จะมีส่วนของAที่มีแอตทริบิวต์จากทั้งRและPโปรดทราบว่าB , CหรือDอาจว่างเปล่า จากนั้นจะเป็นดังนี้: ${\displaystyle A=B\wedge C\wedge D}$

${\displaystyle \sigma _{A}(R\times P)=\sigma _{B\wedge C\wedge D}(R\times P)=\sigma _{D}(\sigma _{B}(R)\times \sigma _{C}(P))}$

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

1. ${\displaystyle \sigma _{A}(R\setminus P)=\sigma _{A}(R)\setminus \sigma _{A}(P)=\sigma _{A}(R)\setminus P}$
2. ${\displaystyle \sigma _{A}(R\cup P)=\sigma _{A}(R)\cup \sigma _{A}(P)}$
3. ${\displaystyle \sigma _{A}(R\cap P)=\sigma _{A}(R)\cap \sigma _{A}(P)=\sigma _{A}(R)\cap P=R\cap \sigma _{A}(P)}$

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

$${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(\sigma _{A}(R))=\sigma _{A}(\pi _{a_{1},\ldots ,a_{n}}(R))\,\,{\text{if}}\,A\subseteq \{a_{1},\ldots ,a_{n}\}}$$

การฉายภาพมีคุณสมบัติเอกลักษณ์ (idempotent) กล่าวคือ ชุดของการฉายภาพ (ที่ถูกต้อง) จะเทียบเท่ากับการฉายภาพภายนอกสุด

$${\displaystyle {\begin{aligned}&\pi _{a_{1},\ldots ,a_{n}}(\pi _{b_{1},\ldots ,b_{m}}(R))=\pi _{a_{1},\ldots ,a_{n}}(R)\\[4pt]&\,\,\,{\text{where}}\,\,\{a_{1},\ldots ,a_{n}\}\subseteq \{b_{1},\ldots ,b_{m}\}\end{aligned}}}$$

การฉายภาพเป็นคุณสมบัติการกระจายตัวเหนือการรวมกันของเซต

$${\displaystyle \pi _{a_{1},\ldots ,a_{n}}(R\cup P)=\pi _{a_{1},\ldots ,a_{n}}(R)\cup \pi _{a_{1},\ldots ,a_{n}}(P).\,}$$

การฉายภาพไม่กระจายผ่านส่วนที่ทับซ้อนกันและความแตกต่างของเซต ตัวอย่างค้านได้แก่:

$${\displaystyle {\begin{aligned}\pi _{A}(\{\langle A=a,B=b\rangle \}\cap \{\langle A=a,B=b'\rangle \})&=\emptyset \\\pi _{A}(\{\langle A=a,B=b\rangle \})\cap \pi _{A}(\{\langle A=a,B=b'\rangle \})&=\{\langle A=a\rangle \}\end{aligned}}}$$

และ

$${\displaystyle {\begin{aligned}\pi _{A}(\{\langle A=a,B=b\rangle \}\setminus \{\langle A=a,B=b'\rangle \})&=\{\langle A=a\rangle \}\\\pi _{A}(\{\langle A=a,B=b\rangle \})\setminus \pi _{A}(\{\langle A=a,B=b'\rangle \})&=\emptyset \end{aligned}}}$$

โดยที่bถือว่าแตกต่างจากb '

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

1. ${\displaystyle \rho _{a/b}(\rho _{b/c}(R))=\rho _{a/c}(R)\,\!}$
2. ${\displaystyle \rho _{a/b}(\rho _{c/d}(R))=\rho _{c/d}(\rho _{a/b}(R))\,\!}$

ฟังก์ชัน Rename มีคุณสมบัติการกระจายตัวเหนือผลต่างเซต ยูเนียน และอินเตอร์เซกชันของเซต

1. ${\displaystyle \rho _{a/b}(R\setminus P)=\rho _{a/b}(R)\setminus \rho _{a/b}(P)}$
2. ${\displaystyle \rho _{a/b}(R\cup P)=\rho _{a/b}(R)\cup \rho _{a/b}(P)}$
3. ${\displaystyle \rho _{a/b}(R\cap P)=\rho _{a/b}(R)\cap \rho _{a/b}(P)}$

ผลคูณคาร์ทีเซียนมีคุณสมบัติการกระจายตัวเหนือการรวมกัน

1. ${\displaystyle (A\times B)\cup (A\times C)=A\times (B\cup C)}$

ภาษาสอบถามแรกที่อิงตามพีชคณิตของ Codd คือ Alpha ซึ่งพัฒนาโดย Dr. Codd เอง ต่อมาISBLได้ถูกสร้างขึ้น และงานบุกเบิกนี้ได้รับการยกย่องจากผู้เชี่ยวชาญหลายท่าน^{[ 10 ]}ว่าได้แสดงให้เห็นถึงวิธีการนำแนวคิดของ Codd มาใช้เป็นภาษาที่มีประโยชน์Business System 12เป็น DBMS เชิงสัมพันธ์ที่มีความแข็งแกร่งในระดับอุตสาหกรรมซึ่งมีอายุสั้นและดำเนินตามแบบอย่างของ ISBL

ในปี พ.ศ. 2541 Chris DateและHugh Darwenได้เสนอภาษาที่เรียกว่าTutorial Dซึ่งมีจุดประสงค์เพื่อใช้ในการสอนทฤษฎีฐานข้อมูลเชิงสัมพันธ์ และภาษาการสอบถามของภาษานี้ยังดึงเอาแนวคิดของ ISBL มาใช้ด้วย^{[ 11 ]} Rel เป็นการนำTutorial D มาใช้ Bmg เป็นการนำพีชคณิตเชิงสัมพันธ์มาใช้ใน Ruby ซึ่งปฏิบัติตามหลักการของTutorial DและThe Third Manifestoอย่าง ใกล้ชิด ^{[ 12 ]}

แม้แต่ภาษาการสอบถามของSQL ก็ ยังอิงตามพีชคณิตเชิงสัมพันธ์อย่างหลวมๆ แม้ว่าตัวดำเนินการใน SQL ( ตาราง ) จะไม่ใช่ความสัมพันธ์ โดยตรง และทฤษฎีบทที่มีประโยชน์หลายอย่างเกี่ยวกับพีชคณิตเชิงสัมพันธ์ก็ไม่สามารถใช้ได้กับ SQL (ซึ่งอาจส่งผลเสียต่อตัวเพิ่มประสิทธิภาพและ/หรือผู้ใช้) โมเดลตารางของ SQL เป็นถุง ( มัลติเซต ) มากกว่าเซต ตัวอย่างเช่น นิพจน์นี้เป็นทฤษฎีบทสำหรับพีชคณิตเชิงสัมพันธ์บนเซต แต่ไม่ใช่สำหรับพีชคณิตเชิงสัมพันธ์บนถุง^{[ 8 ]}${\displaystyle (R\cup S)\setminus T=(R\setminus T)\cup (S\setminus T)}$

• Imieliński, T. ; Lipski, W. (1984). "แบบจำลองเชิงสัมพันธ์ของข้อมูลและพีชคณิตทรงกระบอก"วารสารวิทยาการคอมพิวเตอร์และระบบ 28 : 80– 102. doi : 10.1016 /0022-0000(84)90077-1 .(สำหรับความสัมพันธ์กับพีชคณิตทรงกระบอก )

• RAT Relational Algebra Translatorซอฟต์แวร์ฟรีสำหรับแปลงพีชคณิตเชิงสัมพันธ์เป็น SQL
• วิดีโอการบรรยาย: การประมวลผลพีชคณิตเชิงสัมพันธ์ - บทนำเกี่ยวกับวิธีการที่ระบบฐานข้อมูลประมวลผลพีชคณิตเชิงสัมพันธ์