元組關係演算（從集合的角度深入淺出）
- 2020 年 7 月 5 日
- 筆記
元組關係演算（從集合的角度深入淺出）
一、定義
元組關係演算中，以元組為單位，通過公式約束所要查找元組的條件，可以表示為: \({t\ |\ \psi(t)}\)，使φ(t)為真的元組t的集合。其中: t為元組變數，即查詢目的，φ為元組演算的謂詞公式，即查詢的條件。
按照集合的思想來理解即為：個體詞t具有謂詞φ(t)的性質。
二、元組關係演算的謂詞公式
\(\psi(t)\) 可以通過原子公式、約束公式、自由變數、運算符構成。
（Ⅰ）原子公式分為三類
①、\(R(t)\)：\(R\)為關係名，表示\(t\)是\(R\)中的元組；
②、\(t[\ i\ ]\quad\theta\quad u[\ j\ ]\)：元組\(t\)的第\(i\)個分量與元組\(u\)的第\(j\)個分量進行比較運算，運算符號用\(\theta\)來表示。比如\(t[\ 2\ ]\quad\lt\quad u[\ 3\ ]\)。
③、\(t[\ i\ ]\quad\theta\quad C\)：元組的第\(i\)個分量與常量\(C\)進行比較運算，運算符號用\(\theta\)來表示。比如\(t[\ 2\ ]\quad\lt\quad 5\)。
（Ⅱ）約束元祖變數 \(\&\&\) 自由元組變數
若元組演算公式中的一個元組變數前有「
全稱量詞」和「存在量詞」，則稱該變數為約束元組變數; 否則稱為自由元組變數。
即: 在公式\(【(\exists\ t)\ \psi(t)】\)和\(【(\forall\ t)\ \psi(t)】\)中，\(\psi\)稱為量詞的轄域。\(t\)出現在\((\exists\ t)\)或\((\forall\ t)\)的轄域內，\(t\)為約束元組變數，被量詞所綁定。任何沒有以這種方法顯示綁定的變數都稱為自由變數。（Ⅲ）為此公式\(\psi(t)\)的遞歸定義
①、原子公式是公式；
②、通過吸取連接詞、合取連接詞所構成的複合公式也是公式。
設\(\psi_1(t_1)\)和\(\psi_2(t_2)\)是公式，則¬\(\psi_1(t_1)\)，\(\psi_1(t_1)\ \bigwedge\ \psi_2(t_2)\)和\(\psi_1(t_1)\ \bigvee\ \psi_2(t_2)\)也是公式；③、利用全稱量詞和存在量詞構成的公式也是\(\psi(t)\)的一種表現形式 。
\(【(\exists\ t)\ \psi(t)】\)和\(【(\forall\ t)\ \psi(t)】\)也是公式;④、有限次利用上述規則得到的式子都是公式；
三、公式運算符及其優先順序
（Ⅰ）算術比較符: <, >, ≥, ≤, ≠, =；
（Ⅱ）全稱量詞\(\forall\)和存在量詞\(\exists\)；
（Ⅲ）邏輯運算符: \(\bigwedge\), \(\bigvee\), ¬, \(\longrightarrow\)；
（Ⅳ）優先順序: 算術比較符 > 全稱量詞\(\forall\)和存在量詞\(\exists\) > 邏輯運算符；
四、元組關係演算與關係代數
在元組關係演算中，可以不用考慮為解決表的自然連接中產生數據冗餘而進行投影屬性列。
（注意：最好還是考慮，但是為了簡化步驟就沒有考慮）。（Ⅰ）
傳統關係代數到元組關係演算①、交操作：\(\{t | R(t)\ \bigwedge\ S(t)\}\);
②、並操作：\(\{t | R(t)\ \bigvee\ S(t)\}\);
③、差操作：\(\{t | R(t)\ \bigwedge\ ¬S(t)\}\);
④、廣義笛卡爾積操作：\(\{\ t(m+n)\ |\ (∃u)(∃v)\ （R(u) Λ S(v)）\ \bigwedge\ （t[\ i\ ]=u[\ j\ ]\ (i=1, 2, …, m）\ \bigwedge\ t[\ i\ ]=v[\ k\ ])\ \}\)，
其中\((i=m+1, m+2, …, m+n)\ (j=1, 2, …,m)\ (k=1, 2, …, n)\}\)；（Ⅱ）
專門關係代數到元組關係演算（1） 選擇操作：\(\{t\ |\ R(t)\ \bigwedge\ F\}\)，其中\(F\)是指查詢條件。選取操作只是在原有的表上，將滿足特定性質的元組提取出來，並沒有形成新的表。
（2）投影操作: \(\{t(n)\ |\ (∃u)\ (R(u)\ \bigwedge\ t[\ i\ ]\ =\ u[\ j\ ])\}\)，其中\((i=1, 2, …, n, j∈[1, count_A(R)])\)。
即為，\(\exists u\ \in\ R\)，滿足\(t[\ 1\ ]\ =\ u[\ 1\ ]\)。投影是建立了一個新的表，這個表中的列來自於原表中的屬性列(感興趣的、被選取出來的列)。補充：
投影用存在量詞∃的原因
補充：為什麼投影是要對所有的關係中元組進行操作(將所有的元組投影到屬性列上)，但卻用”存在量詞∃”而不是”全稱量詞∀”？
答：因為如果用了”全稱量詞∀”，那麼這句話將會被解釋為：”對於任意的u∈R，都滿足t[i] = u[j]” ===> “新關係中某一個元組上的第i個分量t[i]等於原關係的第j列上所有的分量”，這顯然是不正確的，這是因為一個t[i]有且僅有一個u[j]與之對應相等。所以說，我們只能表述為：”在關係R中，總是存在某一個u元組，滿足t[i] = u[j]”。
還有一種解釋(更確切地說是理解)將會在下面提到。
五、淺析打開全稱量詞∀和存在量詞∃的方式
（Ⅰ）存在量詞∃：當需求中含有「存在一個」、「至少一個」、「有一個」等詞的時候。就像上述的投影操作一樣：有且僅有一個\(R\)中的\(u\)元組，滿足\(t[\ i\ ]\ =\ u[\ j\ ]\)。
（Ⅱ）全稱量詞∀：當需求中含有「全部」、「所有」等詞，並且將「全部」一詞去掉有後改變原句句意的時候。eg：
①、「在進行操作的過程中選擇某一集合中全部元素」的元素集合時，即此時的「全部」並不是默認值，默認值為「至少一個 / 存在」，比如說某個要求為：「查詢選修了全部課程的學生」，此時將「全部」一詞去掉後變為「查詢選修了課程的學生」，不難發現，前一個是「選修了全部課程」，後一個是「只要是選修了課程，即至少選修了一門課程」，將兩者比較，兩句話的句意完全不同。
②、在經過一系列操作後所得到的集合中選擇全部元組時，即此時的「全部」為默認值：對於「查詢選修了『劉偉』老師的課程的全部學生」，將「全部」一詞去掉後變為「查詢選修了『劉偉』老師的課程的學生」，這並沒有\(len\)何差別，所以自然就「不配」使用「全稱量詞∀」了。
補充： 關於「投影中使用『存在量詞∃』的另一角度的理解」：「將所有的元組投影到屬性列上」，把「所有的」一詞去掉變為「將元組投影到屬性列上」，顯然這兩句話其實是一樣的意思。
六、命題的否定 VS 否命題
存在一個命題為：若\(p\)，則\(q\)。
（Ⅰ）命題的否定: 若\(p\)，則\(¬q\)。（√）
也就是說，命題的否定只會否定命題的結論，並不會否定命題的條件。簡單來說就是與原命題唱反調，所以他與原命題是完全對立的。所以我們研究問題的時候用的「正難則反」就是研究問題的否定形式\(¬q\)。
（Ⅱ）否命題: 若\(¬p\)，則\(¬q\)。（\(PASS\)）
也就是說，否命題會把命題的條件和結論一起否定掉。他與原命題的真假無關，與逆命題同真同假。
### （Ⅲ）全稱量詞∀和存在量詞∃的否定形式
（1）全稱量詞∀的否定形式
①、更換量詞: 將全稱量詞∀換成存在量詞∃；
②、將結論否定；也就是說: 全稱量詞∀的否定是一個存在命題。
（2）存在量詞∃的否定形式
①、更換量詞: 將存在量詞∃換成全稱量詞∀；
②、將結論否定；也就是說: 存在量詞∃的否定是一個全稱命題；
七、總結，深入全稱量詞∀和存在量詞∃的打開方式
研究「全稱量詞∀和存在量詞∃」本質上就是研究「集合」的有關問題，所以要先把握住集合與集合之間的關係。任何兩個集合的關係有且僅可能有3種：相交、包含、相離，並且這三種關係又有如下的關係：
（1）「相離」 與「相交」∪「包含」：互為對立事件，即「全部都沒」$ VS \(「至少有一」；
（2）「包含」 與「相交」∪「相離」：互為對立事件，即「全部都有」\)VS $「至少沒一」；了解了這個後，我們就可進一步的歸納出使用”全稱量詞∀和存在量詞∃”的情景：
（1）當某個事件被表述為兩個集合「相離」或者「包含」的時候 ：使用「全稱量詞∀」來表示「全部都沒」或者「全部都有」；
（2）當某個事件被表述為兩個集合「相交」的時候：使用「存在量詞∃」來表達「至少有一」或者「至少沒一」;舉個栗子 ：
（1）
相離：「沒有選修過『李力』老師教授的課程的同學」這個問題就可以被表述為：「\(A_i ∩ B = \phi\)」，其中\(A_i\) = {第\(i\)個學生的「學生-選課資訊」的課程編號集合}，\(B\) = {『李力』老師教授的課程的課程編號集合}；（2）
相交：「選修過『李力』老師教授的課程的同學」這個問題就可以被表述為：「\(A_i ∩ B ≠ \phi\)」，其中\(A_i\) = {第\(i\)個學生的「學生-選課資訊」的課程編號集合}，\(B\) = {『李力』老師教授的課程的課程編號集合}；（3）
包含：「選修了『李力』老師教授的全部課程的同學」這個問題就可以被表述為：「\(A_i\) ⊇ \(B\)」，其中\(A_i\) = {第\(i\)個學生的「學生-選課資訊」的課程編號集合}，B = {『李力』老師教授的課程的課程編號集合}；從「正」、「反」兩個方面考慮問題的角度來說：
（1）當考慮的問題是
「全部都有」時則可以從正面入手，在關係代數中利用除法，在元組演算中利用「全稱量詞∀」；（2）當考慮的問題是
「至少沒有一個」時則可以從反面入手，在關係代數中利用除法 + 減法，在元組演算則從正面入手，直接利用「存在量詞∃」，譯作「存在一個沒有滿足……」；（3）當考慮的問題是
「至少存在一個」時則可以從正面入手，在關係代數中利用自然連接，在元組演算中利用「存在量詞∃」，譯作「存在一個滿足……」；（4）當考慮的問題是
「全部都無」時則可以從反面入手，在關係代數中利用自然連接 + 減法，在元組演算中利用「全稱量詞∀」；
