域關係演算

域關係演算是關係演算中的另一種形式，是一元組變數的分量即域變數作為謂詞變元的基本對象。

基本介紹

• 中文名：域關係演算
• 含義：一元組變數的分量
• 代表：QBE語言
• 特點：關係演算中的另一種形式

典型代表

域關係演算語言的典型代表是1975年有IBM公司約克城搞基研究實驗室的M.M.Zloof提出的QBE語言，該語言於1978年在IBM 370上實現。

演算表達式

在元組關係演算系統中，稱{t|Φ(t)}為元組演算表達式。其中t是元組變數，Φ(t)為元組關係演算公式，簡稱公式。
它由原子公式和運算符組成。

原子公式有三類：

(1)R(t)

R是關係名，t是元組變數。R(t)表示t是R中的元組。於是，關係R可表示為：{t|R(t)}

(2)t[i]θu[j]

t和u是元組變數，θ是算術比較運算符。t[i]θu[j]表示斷言“元組t的第i個分量與元組u的第j個分量滿足比較關係θ”。例如，t[2]u[3]表示元組t的第2個分量小於元組u的第3個分量。

(3)t[i]θc或cθt[i]
這裡c是常量，該公式表示“t的第i個分量與常量C滿足比較關係θ”。例如：t[4]=3表示元組t的第4個分量等於3。

在關係演算中定義了“自由元組變數”和“約束元組變數”的概念。這些概念和謂詞演算中的概念完全一樣。若公式中的一個元組變數前有“全稱量詞”或“存在量詞”，則稱該變數為約束元組變數，否則稱自由元組變數。

公式可以遞歸定義如下：

(l)每個原子公式是公式。
(2)如果Φ1和Φ2是公式，則Φ1∧Φ2、Φ1∨Φ2、﹁Φ1也是公式。分別表示：
①如果Φ1和Φ2同時為真。則Φ1∧Φ2才為真，否則為假；
②如果Φ1和Φ2中一個或同時為真，則Φ1∨Φ2為真，僅Φ1和Φ2同時為假時，Φ1∨Φ2才為假；
③如果Φ1真，則﹁Φ1為假。
(3)若Φ是公式，則?t(Φ)也是公式。其中符號?是存在量詞符號，?t(Φ)表示：
若有一個t使Φ為真，則?t(Φ)為真，否則?t(Φ)為假。
(4)若Φ是公式，則?t(Φ)也是公式。其中符號?是全稱量詞符號，?t(Φ)表示：
如果對所有t，都使Φ為真，則?t(Φ)必為真，否則?t(Φ)為假。
(5)在元組演算公式中，各種運算符的優先次序為：
①算術比較運算符最高；
②量詞次之，且?的優先權高於?的優先權；
③邏輯運算符最低，且﹁的優先權高於∧的優先權，∧的優先權高於∨的優先權；
④加括弧時，括弧中運算符優先，同一括弧內的運算符之優先權遵循①②③各項。
(6)有限次地使用上述五條規則得到的公式是元組關係演算公式，其他公式不是元組關係演算公式。

一個元組演算表達式{t|Φ(t)}表示了使Φ(t)為真的元組集合。

基本運算

關係代數的運算均可以用關係演算表達式來表示(反之亦然)。下面用關係演算表達式來表示五種基本運算：

(1)並

R∪S={t|R(t)∨S(t)}

(2)差

R－S={t|R(t)∧﹁S(t)}

(3)笛卡爾積

R×S={t(n+m)|(?u(n))(?v(m))(R(u)∧S(v)∧t[1]=u[1]∧...∧t[n]=u[n]∧t[n+1]=v[1]∧...∧t[n+m]=v[m])}

註：t(n+m)表示t有目數(n+m)

(4)投影

πt1,t2,...,tk(R)={t(k)|(?u)(R(u)∧t[1]=u[i1]∧...t[k]=u[ik])}

(5)選擇

σF(R)={t|R(t)∧F}

註：F是公式。F用t[i]代替運算對象i得到的等價公式。

套用示例

例1查詢信息系(IS系)全體學生：
SIS={Student(t)∧t[5]='IS'}
例2查詢年齡小於20歲的學生。
S20={Student(t)∧t[4]20}

例3查詢學生的姓名和所在系。
S={t(2)|(?u)(Student(u)∧t[1]=u[2]∧t[2]=u[5])}

上面定義的關係演算允許出現無限關係。例如{t|﹁R(t)}表示所有不屬於R的元組(元組的目數等於R的目數)。要求出這些可能的元組是做不到的，所以必須排除這類無意義的表達式。把不產生無限關係的表達式稱為安全表達式，所採取的措施稱為安全限制。安全限制通常是定義一個有限的符號集dom(Φ)，dom(Φ)一定包括出現在Φ以及中間結果和最後結果的關係中的所有符號(實際上是各列中值的匯集)。dom(Φ)不必是最小集。

當滿足下列條件時，元組演算表達式{t|Φ(t)}是安全的：

（1）如果t使Φ(t)為真，則t的每個分量是dom(Φ)中的元素。
（2）對於Φ中每一個形如(?t)(W(u))的子表達式，若u使W(u)為真，則u的每個分量是dom(Φ)中的元素。
（3）對於Φ中每一個形如(?t)(W(u))的子表達式，若u使W(u)為假，則u的每個分量必屬於dom(Φ)。換言之，若u某一分量不屬於dom(Φ)，則W(u)為真。

例4設有關係R如圖2.8(a)，S={t|﹁R(t)}，若不進行安全限制，則可能是一個無限關係。所以定義

dom(Φ)=πA(R)∪πB(R)∪πC(R)

={{a1,a2},{b1,b2},{c1,c2}}

則S是dom(Φ)中各域值中元素的笛卡兒積與R的差集。結果如圖2.8(b)。注意，在做笛卡兒積時各個域中的元素不能搞混。