2.5　*關系演算

關系演算是以數理邏輯中的謂詞演算為基礎的。按謂詞變元的不同，關系演算可分為元組關系演算和域關系演算。本小節先介紹元組關系演算，然后簡單介紹域關系演算。

一、元組關系演算語言ALPHA

元組關系演算以元組變量作為謂詞變元的基本對象。一種典型的元組關系演算語言是E. F. Codd提出的ALPHA語言。這一語言雖然沒有實際實現，但關系數據庫管理系統INGRES最初所用的QUEL語言是參照ALPHA語言研制的，與ALPHA十分類似。

ALPHA語言主要有GET，PUT，HOLD，UPDATE，DELETE，DROP 6條語句，語句的基本格式是：

操作語句 工作空間名（表達式）：操作條件

其中表達式用于說明要查詢的結果，它可以是關系名或（和）屬性名，一條語句可以同時操作多個關系或多個屬性。操作條件是一個邏輯表達式，說明查詢結果要滿足的條件，用于將操作結果限定在滿足條件的元組中，操作條件可以為空。除此之外，還可以在基本格式的基礎上加上排序要求、定額要求等。

1檢索操作

檢索操作用GET語句實現。

（1）簡單檢索（即不帶條件的檢索）

【例1】查詢所有被選修的課程號碼。

Get W（SC.Cno），W為工作空間名。這里條件為空，表示沒有限定條件。

【例2】查詢所有學生的數據。

GET W（Student）

（2）限定的檢索（即帶條件的檢索）

【例3】查詢信息系（IS）中年齡小于20歲的學生的學號和年齡。

GET W（Student.Sno，Student.Sage）：Student.Sdept＝‘IS’∧Student.Sage＜20

（3）帶排序的檢索

【例4】查詢計算機科學系（CS）學生的學號、年齡，結果按年齡降序排序。

GET W（Student.Sno，Student.Sage）：Student.Sdept＝‘CS’DOWN Student.Sage

DOWN表示降序排序。

（4）帶定額的檢索

【例5】取出一個信息系學生的學號。

GET W（1）（Student.Sno）：Student.Sdept＝‘IS’

排序和定額可以一起使用。所謂帶定額的檢索是指規定了檢索出元組的個數，方法是在W后括號中加上定額數量。

【例6】查詢信息系年齡最大的三個學生的學號及其年齡，結果按年齡降序排序。

GET W（3）（Student.Sno，Student.Sage）：Student.Sdept＝‘IS’DOWN Student.Sage

（5）用元組變量的檢索

前面已講到，元組關系演算是以元組變量作為謂詞變元的基本對象。元組變量是在某一關系范圍內變化（所以也稱為范圍變量Range Variable），一個關系可以設多個元組變量。元組變量主要有兩方面的用途：

①簡化關系名。如果關系的名字很長，使用起來就會感到不方便，這時可以設一個較短名字的元組變量來代替關系名。

②操作條件中使用量詞時必須用元組變量。

【例7】查詢信息系學生的名字。

RANGE Student X GET W（X.Sname）：X.Sdept＝‘IS’

ALPHA語言用RANGE來說明元組變量。本例中X是關系Student上的元組變量，用是簡化關系名，即用X代表Student。

（6）用存在量詞（existential quantifier）的檢索操作條件中使用量詞時必須用元組變量。

【例8】查詢選修2號課程的學生名字。

RANGE SC X GET W（Student Sname）：? X（X.Sno＝Student.Sno∧X.Cno＝‘2’）

【例9】查詢選修了這樣課程的學生學號，其直接先行課是6號課程。

RANGE Course CX GET W（SC Sno）：? CX（CX.Cno＝SC.Cno∧CX.Pcno＝‘6’）

【例10】查詢至少選修一門其先行課為6號課程的學生名字。

在【例10】中的元組關系演算公式可以變換為前束范式（Prenex normal form）的形式：

GET W（Student Sname）：? SCX ? CX（SCX.Sno＝Student.Sno∧CX.Cno＝SCX.Sno∧CX.Pcno＝‘6’）

【例8】、【例9】、【例10】中的元組變量都是為存在量詞而設的。其中【例10】需要對兩個關系作用存在量詞，所以設了兩個元組變量。

（7）帶有多個關系的表達式的檢索

上面所舉的各個例子中，雖然查詢時可能會涉及多個關系，即公式中可能涉及多個關系，但查詢結果表達式中只有一個關系。實際上表達式中是可以有多個關系的。

【例11】查詢成績為90分以上的學生名字與課程名字。

本查詢所要求的結果是學生名字和課程名字，分別在Student和Course兩個關系中。

RANGE SC SCX GET W（Student.Sname，Course.Cname）：? SCX（SCX.Grade≥90∧SCX.Sno＝Student.Sno∧Course.Cno＝SCX.Cno）

（8）用全稱量詞（generality quantifier）的檢索

【例12】查詢不選1號課程的學生名字。

RANGE SC SCX GET W（Student.Sname）：? SCX（SCX.Sno≠Student.Sno∨SCX.Cno≠‘1’）

本例也可以用存在量詞來表示：

RANGE SC SCX GET W（Student.Sname）：￢? SCX（SCX.Sno＝Student.Sno∧SCX.Cno＝‘1’）

（9）用兩種量詞的檢索

【例13】查詢選修了全部課程的學生姓名。

（10）用蘊涵（Implication）的檢索

【例14】查詢最少選修了95002學生所選課程的學生學號。

本例題的求解思路是，對Course中的所有課程，依次檢查每一門課程，看95002是否選修了該課程，如果選修了，則再看某一個學生是否也選修了該門課。如果對于95002所選的每門課程該學生都選修了，則該學生為滿足要求的學生。把所有這樣的學生全都找出來即完成了本題。

（11）聚集函數

用戶在使用查詢語言時，經常要作一些簡單的計算，例如要求符合某一查詢要求的元組數，求某個關系中所有元組在某屬性上的值的總和或平均值等。為了方便用戶，關系數據語言中建立了有關這類運算的標準函數庫供用戶選用。這類函數通常稱為聚集函數或內置函數（Built.in Function）。關系演算中提供了COUNT，TOTAL，MAX，MIN，AVG等聚集函數，其含義如表2-3所示。

【例15】查詢學生所在系的數目。

GET W（COUNT（Student.Sdept）），COUNT函數在計數時會自動排除重復值。

表2-3　關系演算中的聚集函數

【例16】查詢信息系學生的平均年齡。

GET W（AVG（Student.Sage）：Student.Sdept＝‘IS’）

2更新操作

（1）修改操作

修改操作用UPDATE語句實現。其步驟是：

①首先用HOLD語句將要修改的元組從數據庫中讀到工作空間中；

②然后用宿主語言修改工作空間中元組的屬性值；

③最后用UPDATE語句將修改后的元組送回數據庫中。

需要注意的是，單純檢索數據使用GET語句即可，但為修改數據而讀元組時必須使用 HOLD語句，HOLD語句是帶上并發控制的GET語句。有關并發控制的概念將在第11章中詳細介紹。

【例17】把95007學生從計算機科學系轉到信息系。

在該例中用HOLD語句來讀95007的數據，而不是用GET語句。

如果修改操作涉及到兩個關系的話，就要執行兩次HOLD-MOVE-UPDATE操作序列。在ALPHA語言中，修改關系主碼的操作是不允許的，例如不能用UPDATE語句將學號95001改為95102。如果需要修改主碼值，只能先用刪除操作刪除該元組，然后再把具有新主碼值的元組插入到關系中。

（2）插入操作

插入操作用PUT語句實現。其步驟是：

①首先用宿主語言在工作空間中建立新元組；

②然后用PUT語句把該元組存入指定的關系中。

【例18】學校新開設了一門2學分的課程“計算機組織與結構”，其課程號為8，直接先行課為6號課程。插入該課程元組。

PUT語句只對一個關系操作，也就是說表達式必須為單個關系名。

（3）刪除

刪除操作用DELETE語句實現。其步驟為：

①用HOLD語句把要刪除的元組從數據庫中讀到工作空間中；

②用DELETE語句刪除該元組。

【例19】95110學生因故退學，刪除該學生元組。

【例20】將學號95001改為95102。

【例21】刪除全部學生。

HOLD W（Student） DELETE W

由于SC關系與Student關系之間的具有參照關系，為保證參照完整性，刪除Student中元組時相應地要刪除SC中的元組（手工刪除或由DBMS自動執行）：

HOLD W（SC） DELETE W

二、元組關系演算

上一節講解了一種具體的元組關系演算語言，這一節講解抽象的元組關系演算。

為了討論方便，先允許關系（的基數）是無限的。然后再對這種情況下定義的演算作適當的修改，保證關系演算中的每一個公式表示的是有限關系。

在元組關系演算系統中，稱{t|φ（t）}為元組演算表達式。其中t是元組變量，φ（t）為元組關系演算公式簡稱公式。它由原子公式和運算符組成。

原子公式有三類：

a．R（t）

R是關系名，t是元組變量。R（t）表示t是R中的元組。于是，關系R可表示為{t|R（t）}

b．t[i]θu[j]

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

表示元組t的第2個分量小于元組u的第3個分量。

c．t[i]θc或cθt[i]

這里c是常量，該公式表示“t的第i個分量與常量C滿足比較關系0”。

例如，t[4]＝3表示元組t的第4個分量等于3。

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

公式可以遞歸定義如下：

（1）每個原子公式是公式。

（2）如果φ₁，和φ₂是公式，則φ₁∧φ₂，φ₁∨φ₂，￢φ₁也是公式。分別表示：

·如果φ₁和φ₂同時為真，則φ₁∧φ₂才為真，否則為假；

·如果φ₁和φ₂中一個或同時為真，則φ₁∨φ₂為真，僅當φ₁和φ₂同時為假時，φ₁∨φ₂才為假；

·若φ₁為真，則￢φ₁為假。

（3）若φ是公式，則?t（φ）也是公式。其中符號?是存在量詞符號，?t（φ）表示：若有一個t使φ為真，則it（φ）為真，否則it（φ）為假。

（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）投影

（5）選擇

σ_F（R）＝{t|R（t）∧F′}

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

下面用關系演算來對2.4.2小節中學生-課程數據庫進行查詢。

【例1】查詢信息系（IS系）全體學生。

S_IS＝{t|Student（t）∧t[5]＝‘IS’}

【例2】查詢年齡小于20歲的學生。

S₂₀＝{t|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）對于西中每一個形如（?u）（W（u））的子表達式，若u使W（u）為真，則U的每個分量是dora（西）中的元素。

（3）對于φ中每一個形如（?u）（W（u））的子表達式，若u使W（u）為假，則U的每個分量必屬于dom（φ）。換言之，若u某一分量不屬于dom（φ），則W（u）為真。

【例4】設有關系R如圖2-1（a），S＝{t|￢R（t）}，若不進行安全限制，則可能是一個無限關系。

R

圖2-1（a）

所以定義

dom（φ）＝π_A（R）∪π_B（R）∪π_C（R）＝{{a₁，a₂}，{b₁，b₂}，{c₁，c₂}}

則S是dom（φ）中各域值中元素的笛卡爾積與R的差集。結果如圖2-1（b）。

S

圖2-1（b）

注意，在做笛卡爾積時各個域中的元素不能搞混。

三、域關系演算語言QBE

關系演算的另一種形式是域關系演算。域關系演算以元組變量的分量即域變量作為謂詞變元的基本對象。1975年由M. M. Zloof提出的QBE就是一個很有特色的域關系演算語言，該語言于1978年在IBM370上得以實現。QBE也指此關系數據庫管理系統。

QBE是Query By Example（即通過例子進行查詢）的簡稱，其最突出的特點是它的操作方式。它是一種高度非過程化的基于屏幕表格的查詢語言，用戶通過終端屏幕編輯程序以填寫表格的方式構造查詢要求，而查詢結果也是以表格形式顯示，因此非常直觀，易學易用。QBE中用示例元素來表示查詢結果可能的情況，示例元素實質上就是域變量。

圖2-2　QBE操作框架

下面以學生-課程關系數據庫為例，說明QBE的用法。

1檢索操作

a．簡單查詢

【例1】求信息系全體學生的姓名。操作步驟為：

（1）用戶提出要求；

（2）屏幕顯示空白表格；

（3）用戶在最左邊一欄輸入關系名Student；

（4）系統顯示該關系的屬性名；

（5）用戶在上面構造查詢要求。

這里T是示例元素，即域變量。QBE要求示例元素下面一定要加下劃線。IS是查詢條件，不用加下劃線。P.是操作符，表示打印（Print），實際上是顯示。

查詢條件中可以使用比較運算符＞，≥，＜，≤，＝和≠。其中＝可以省略。

示例元素是這個域中可能的一個值，它不必是查詢結果中的元素。比如要求信息系的學生，只要給出任意的一個學生名即可，而不必真是信息系的某個學生名。

對于【例1】，可如下構造查詢要求：

這里的查詢條件是Sdept＝‘IS’，其中“＝”被省略。

（6）屏幕顯示查詢結果

根據用戶的查詢要求，求出了信息系的學生姓名。

【例2】查詢全體學生的全部數據。

顯示全部數據也可以簡單地把P.操作符作用在關系名上。因此本查詢也可以簡單地表示如下：

b．條件查詢

【例3】求年齡大于19歲的學生的學號。

【例4】求計算機科學系年齡大于19歲的學生的學號。

本查詢的條件是Sdept＝‘CS’和Sage＞19兩個條件的“與”。在QBE中，表示兩個條件的“與”有兩種方法：

（1）把兩個條件寫在同一行上；

（2）把兩個條件寫在不同行上，但使用相同的示例元素值。

【例5】查詢計算機科學系或者年齡大于19歲的學生的學號。

本查詢的條件是Sdept＝‘CS’和Sage＞19兩個條件的“或”。在QBE中把兩個條件寫在不同行上，并且使用不同的示例元素值，即表示條件的“或”。

對于多行條件的查詢，如【例4】（2）和【例5】，先輸入哪一行是任意的，不影響查詢結果。這就允許查詢者以不同的思考方式進行查詢，十分靈活、自由。

【例6】查詢既選修了1號課程又選修了2號課程的學生的學號。

本查詢條件是在一個屬性中的“與”關系，它只能用“與”條件的第（2）種方法表示，即寫兩行，但示例元素相同。

【例7】查詢選修1號課程的學生姓名。

本查詢涉及兩個關系：SC和Student。在QBE中實現這種查詢的方法是通過相同的連接屬性值把多個關系連接起來。

這里示例元素Sno是連接屬性，其值在兩個表中要相同。

【例8】查詢未選修1號課程的學生姓名

這里的查詢條件中用到邏輯非。在QBE中表示邏輯非的方法是將邏輯非寫在關系名下面。

這個查詢就是顯示學號為95001的學生名字，而該學生選修1號課程的情況為假。

【例9】查詢有兩個人以上選修的課程號。

本查詢是在一個表內連接。

這個查詢就是要顯示這樣的課程1，它不僅被95001選修，而且也被另一個學生（95001）選修了。

c．聚集函數

為了方便用戶，QBE提供了一些聚集函數，主要包括CNT，SUM，AVG，MAX，MIN等，其含義如表2-4所示。

表2-4　QBE中的聚集函數

【例10】查詢信息系學生的平均年齡。

d．對查詢結果排序

對查詢結果按某個屬性值的升序排序，只需在相應列中填入“AO.”，按降序排序則均“DO.”。如果按多列排序，用“AO（i）.”或“DO（i）.”表示，其中i為排序的優先級，i值越小，優先級越高。

【例11】查全體男生的姓名，要求查詢結果按所在系升序排序，對相同系的學生按年齡降序排序。

2更新操作

a．修改操作修改操作符為“U.”。在QBE中，關系的主碼不允許修改，如果需要修改某個元組的主碼，只能先刪除該元組，然后再插入新的主碼的元組。

【例12】把95001學生的年齡改為18歲。

這是一個簡單修改操作，不包含算術表達式，因此可以有兩種表示方法。

（1）將操作符“U.”放在值上；

（2）將操作符“U.”放在關系上。

這里，碼95001標明要修改的元組?！癠.”標明所在的行是修改后的新值。由于主碼是不能修改的，所以即使在第二種寫法中，系統也不會混淆要修改的屬性。

【例13】把95001學生的年齡增加1歲。

這個修改操作涉及表達式，所以只能將操作符“U.”放在關系上。

【例14】將計算機科學系所有學生的年齡都增加1歲。

b．插入操作

插入操作符為“I.”。新插入的元組必須具有碼值，其他屬性值可以為空。

【例15】把信息系女生95701，姓名張三，年齡17歲存入數據庫中。

c．刪除操作

刪除操作符為“D.”。

【例16】刪除學生95089。

由于SC關系與Student關系之間具有參照關系，為保證參照完整性，刪除95089學生后，通常還應刪除95089學生選修的全部課程。