Chap 5 關聯式代數與計算

5-1 關聯式代數的基礎 對於關聯式資料庫模型的資料操作或運算來說，E. F. Codd提出兩種存取關聯式資料庫的基礎查詢語言，如下所示： 關聯式代數（Relational Algebra）：一種低階的運算子導向語言（Operator-oriented Language），用來描述如何得到結果的步驟，使用關聯式運算子和關聯表建立的運算式進行資料操作或運算。 關聯式計算（Relational Calculus）：一種高階的宣告式語言（Declarative Language），其建立的查詢運算式主要是在描述所需的結果。

5-1-1 關聯式代數的運算子 關聯式代數運算子中有些是源於傳統集合論的運算子和數學符號，如下所示： 交集（Intersection）：∩ 聯集（Union）：∪ 差集（Difference）：－ 卡笛生乘積（Cartesian Product）：ｘ

5-1-1 關聯式代數的運算子 在關聯式代數運算子中屬於特殊關聯式運算子和其數學符號，如下所示： 選取（Selection）：δ 投影（Projection）：π 合併（Join）： 除法（Division）：÷

5-1-2 SQL語言與關聯式代數 資料庫管理系統的查詢處理模組（Query Processor）是將SQL指令敘述轉換成關聯式代數運算式，如右圖所示：

5-2 關聯式代數的基本運算 選取（Selection）：在指定條件後，可以從關聯表選出指定條件的值組。 投影（Projection）：在關聯表只取出所需屬性的集合。 聯集（Union）：將2個關聯表的所有值組合併成一個關聯表， 差集（Difference）：在2個關聯表中，值組只在第一個運算元的關聯表，而不在第二個運算元的關聯表。 卡笛生乘積（Cartesian Product）：在2個關聯表中，第一個運算元的關聯表值組將結合第二個關聯表的所有值組，可以產生一個新的關聯表。

5-2-1 選取運算 選取（Selection）也稱為「限制」運算子，這是一種單運算元（Unary）運算子，可以在關聯表選取指定條件的值組，預設包含所有屬性。例如：Students關聯表，如下圖所示： 選取

5-2-1 選取運算-語法與定義 選取運算子是使用希臘語’δ’符號（Sigma）代表，在δ下標的「謂詞」（Predicate）P是值組特性的描述，相當於是一個選取條件，選取運算的基本語法與定義，如下所示： δp(R) = { t | t∈R∧P(t) } 上述語法使用謂詞P選取關聯表R中符合條件的值組，也就是說，值組t不只屬於關聯表R，而且值組t需要滿足P(t)特性的條件。

5-2-1 選取運算-範例1 以Students關聯表為例的選取運算式範例，例如：選取GPA小於3.2的學生值組示： Result = δGPA < 3.2 (Students) SELECT * FROM Students WHERE GPA < 3.2

5-2-1 選取運算-範例2 選取GPA小於3.2且學號小於S003的值組，如下所示： Result1 = δGPA < 3.2 ∧ sid < ‘S003’ (Students) SELECT * FROM Students WHERE GPA < 3.2 AND sid < ‘S003’

5-2-2 投影運算 投影（Projection）運算子是一種單運算元（Unary）運算子，它是關聯表屬性的投影，只取出部分關聯表的屬性，而且在運算式結果的關聯表會刪除重複值組。例如：Instructors關聯表，如下圖所示：

5-2-2 投影運算-語法與定義 投影運算子是使用希臘語’π’符號（Pi）代表，其下標是取出的屬性清單，投影運算的基本語法與定義，如下所示： πattr1, attr2, …, attrn (R) ={ t[attr1, attr2, …, attrn] | t∈R } 上述語法取出關聯表R中下標屬性清單的定義域集合t[attr1, attr2, …, attrn]。

5-2-2 投影運算-範例1 以Instructors關聯表為例的投影運算式範例，例如：只選取關聯表的eid、name和rank三個屬性，如下所示： Result = πeid, name, rank (Instructors) SELECT eid, name, rank FROM Instructors

5-2-2 投影運算-範例2 找出各老師所屬的科系一共有那些科系，如下所示： Result1 = πdepartment(Instructors) SELECT DISTINCT department FROM Instructors

5-2-2 投影運算-範例3 投影運算式還可以配合選取運算子來篩選值組，例如：在Instructors關聯表選取salary大於55000的值組，而且只顯示eid、name和salary一共3個屬性，如下所示： Result2 = πeid, name, salary (δsalary > 55000 (Instructors)) SELECT DISTINCT eid, name, salary FROM Instructors WHERE salary > 55000

5-2-3 聯集運算 聯集（Union）運算源於傳統集合論，聯集是一種二元運算子，可以將2個關聯表的所有值組合併成一個關聯表，而且會將重複值組刪除掉。

5-2-3 聯集運算-語法與定義 若關聯表R與S為聯集運算的2個運算元，且都滿足「聯集相容」，聯集運算的基本語法與定義，如下所示： R∪S = S∪R = { t | t∈R∨t∈S } 上述語法的聯集運算滿足交換律，也滿足結合律，運算取出屬於關聯表R或屬於關聯表S的值組t。

5-2-3 聯集運算-聯集相容 在聯集運算的2個關聯表都需滿足聯集相容的2個條件，如下所示： 運算式2個關聯表運算元必須擁有相同的屬性數，即相同維度。 對應屬性必須擁有相同的定義域。

5-2-3 聯集運算-範例1 以Inventory1和Inventory2關聯表為例的聯集運算式範例，如下所示： Result = Inventory1∪Inventory2 運算式相當於SQL語言的SELECT和UNION指令，如下所示： SELECT * FROM Inventory1 UNION SELECT * FROM Inventory2

5-2-3 聯集運算-範例2 在聯集運算式的2個關聯表一定擁有相同的關聯表綱要。 如果是2個不同的關聯表綱要，只需部分屬性相同，一樣可以配合投影運算，取出2個關聯表中相同部分的屬性和定義域進行聯集運算。

5-2-3 聯集運算-範例2 Students和Instructors關聯表擁有相同屬性city，可以執行聯集運算，如下所示： Result1 = πcity(Students)∪πcity(Instructors) SELECT city FROM Students UNION SELECT city FROM Instuctors

5-2-4 差集運算 差集(Difference)是二元運算子，運算結果的值組只在第一個運算元的關聯表，而不在第二個運算元的關聯表。

5-2-4 差集運算-語法與定義 若關聯表R與S滿足聯集相容，差集運算的基本語法與定義，如下所示： R－S = { t | t∈R∧¬(t∈S) }≠S－R 上述語法的差集運算並不滿足交換律，也不滿足結合律，運算取出屬於關聯表R的值組t，但是不屬於關聯表S。

5-2-4 差集運算-範例1 以Inventory1和Inventory2關聯表為例的差集運算式範例，如下所示： Result1= Inventory1－Inventory2 Result2 = Inventory2－Inventory1 運算式相當於SQL語言的SELECT和EXCEPT指令： SELECT * FROM Inventory1 EXCEPT SELECT * FROM Inventory2 和

5-2-4 差集運算-範例2 如果有2個不同的關聯表綱要，只需配合投影運算，取出2個關聯表中相同部分的屬性和定義域，就可以滿足聯集相容條件進行差集運算，例如：Students和Instructors關聯表，如下圖所示：

5-2-4 差集運算-範例2 Students和Instructors關聯表擁有相同屬性city，可以執行差集運算，如下所示： Result2 = πcity(Students)－ πcity(Instructors) SELECT city FROM Students EXCEPT SELECT city FROM Instructors

5-2-5 卡笛生乘積運算 卡笛生乘積運算（Cartesian Product）是多個關聯表的關聯查詢基礎，在關聯查詢時，需要結合2個關聯表的值組，以便從一個關聯表找出另一個關聯表中相關聯的值組。 卡笛生乘積運算也稱為交叉合併（CROSS JOIN）。 卡笛生乘積是一種二元運算子，這是指在2個關聯表中，第一個運算元的關聯表值組將結合第二個關聯表的所有值組，以便產生一個新關聯表。

5-2-5 卡笛生乘積運算

5-2-5 卡笛生乘積運算-語法與定義 若存在關聯表R與S，卡笛生乘積運算的基本語法與定義，如下所示： R x S = { t | t = (r, s), r=(r1, r2, …, rm)∈R, s=(s1, s2, … sn)∈S } = S x R 上述語法的卡笛生乘積運算滿足交換律和結合律，因為是關聯表R與S所有可能值組的組合，值組t結合關聯表R和S的值組(r, s)，相當於：(r1, r2, …, rm, s1, s2, … sn)。 對於同名的屬性，請加上關聯表名稱字頭以供區別，例如：Students.name和Departments.name。

5-2-5 卡笛生乘積運算-範例1 Students和Departments關聯表的卡笛生乘積運算式範例，如下所示： Result = Students × Departments 卡笛生乘積運算配合選擇運算可以看到2個關聯表的關聯查詢結果，如下所示： Result1 = δStudents.d_no = Departments.d_no (Students × Departments)

5-2-5 卡笛生乘積運算-範例2 卡笛生乘積運算結果還可以再加上投影運算，刪除不需要的屬性，如下所示： Result2 = δStudents.d_no = Departments.d_no( πsid, Students.name, Departments.name, room (Students x Departments))

5-3 關聯式代數的非基本運算 交集（Intersection）：將2個關聯表的相同值組取出成一個關聯表。 合併（Join）：在2個關聯表使用相同定義域的屬性為條件合併2個關聯表。 除法運算（Division）：在2個關聯表中，一個關聯表是除關聯表，一個是被除關聯表，可以找出除關聯表在被除關聯表中的「所有」資料。

5-3-1 交集運算 交集（Intersection）運算和聯集、差集運算一樣源於集合論，交集運算是將2個關聯表的相同值組取出成一個關聯表。

5-3-1 交集運算-語法與定義 若關聯表R與S都滿足聯集相容，交集運算的基本語法與定義，如下所示： R∩S = S∩R = { t | t∈R∧t∈S } 上述語法的聯集運算滿足交換律，也滿足結合律，運算取出屬於關聯表R且屬於關聯表S的值組t。 交集可以使用差集運算來導出，如下所示： R∩S = R – (R－S) = S－(S－R)

5-3-1 交集運算-範例 以Inventory1和Inventory2關聯表為例的交集運算式範例，如下所示： Result = Inventory1∩Inventory2 運算式相當於SQL語言的SELECT和INTERSECT指令，如下所示： SELECT * FROM Inventory1 INTERSECT SELECT * FROM Inventory2

5-3-1 交集運算-使用差集運算導出1 Inventory1∩Inventory2可以寫成差集運算式，如下所示： Result = Inventory1－(Inventory1－Inventory2) 首先是Inventory1－Inventory2差集運算式的結果，如下圖所示：

5-3-1 交集運算-使用差集運算導出2 接著，Inventory1－(Inventory1－Inventory2)差集運算式的結果。

5-3-2 合併運算 合併運算是在兩個關聯表中，使用具有相同定義域的屬性為條件合併兩個關聯表，相當於先執行基本運算的卡笛生乘積運算，再配合選擇運算取出所需值組的關聯表。 合併運算滿足交換律和結合律，合併運算可以分為數種： θ合併 Equijoin合併 自然合併 外部合併

5-3-2 合併運算-資料表範例

5-3-2 合併運算-θ合併(語法) θ合併是使用謂詞（Predicate）來合併2個關聯表，其基本語法和定義如下所示： R pS = σp(R x S) 上述語法的謂詞P使用 的比較運算子，θ ∈{ =, >, <, ≥, ≤ , ≠ }。

5-3-2 合併運算-θ合併(範例) 例如：Transcripts關聯表與自己本身的θ合併運算式，如下所示： Result = ρA(Transcripts) A.c_no = B.c_no ∧A.score > B.score ρB(Transcripts) SELECT A.*, B.* FROM Transcripts A, Transcripts B WHERE A.c_no = B.c_no AND A.score > B.score

5-3-2 合併運算- Equijoin合併 Equijoin合併是一種特殊情況的θ合併，其合併條件只能使用’＝’等號，其基本語法和定義如下所示： R r = s S = σr = s (R x S) 上述語法的條件是r=s，只能使用等號。

5-3-2 合併運算- Equijoin合併 (範例) 例如：Students和Departments關聯表的等位合併運算式，如下所示： Result = Students Student.d_no = Departments.d_no Departments SELECT * FROM Students, Departments WHERE Students.d_no = Departments.d_no

5-3-2 合併運算- 自然合併 自然合併是一種使用主鍵和外來鍵為條件的合併方式，其隱含的條件是主鍵等於外來鍵條件的Equijoin合併 ，所以自然合併屬於一種特殊格式的Equijoin合併 ，其基本語法和定義如下所示： R S = πr∪s(R r = s S) 上述語法並沒有指明條件，這是因為預設使用主鍵和外來鍵對應的條件，即所有共通屬性值（All Common Attributes）都需要相等。 自然合併的執行結果關聯表綱要的共通屬性部分在運算結果中只會顯示一次。

5-3-2 合併運算- 自然合併(範例) 例如：Students和Departments關聯表的自然合併運算式，如下所示： Result = Students Departments SELECT * FROM Students INNER JOIN Departments ON Students.d_no = Departments.d_no

5-3-2 合併運算- 外部合併 外部合併是使用關聯表主鍵和其關聯性（Relationship）關聯表的外來鍵為條件執行合併，只不過這是一種完全的值組合併，運算元的關聯表需要供獻全部值組。 外部合併依供獻的運算元不同可以分為三種： 左外部合併（Left Outer Join） 右外部合併（Right Outer Join） 完全外部合併（Full Outer Join）

5-3-2 合併運算-左外部合併 左外部合併執行結果的關聯表是取回左邊關聯表的所有值組，例如：Students和Instructors關聯表的左外部合併運算式： Result = Studentsleft Instructors

5-3-2 合併運算-右外部合併 右外部合併執行結果的關聯表是取回右邊關聯表的所有值組，例如：Students和Instructors關聯表的右外部合併運算式，如下所示： Result = Students rightInstructors

5-3-2 合併運算-完全外部合併 完全外部合併執行結果的關聯表是取回兩邊關聯表的所有值組，例如：Students和Instructors關聯表的完全外部合併運算式，如下所示： Result = Studentsleft rightInstructors

5-3-3 除法運算-說明 除法運算（Division）類似數學除法，這是一種二運算元的運算子，其中一個運算元關聯表是除關聯表，一個是被除關聯表，可以找出除關聯表在被除關聯表中的「所有」資料。

5-3-3 除法運算-語法與定義(說明) 若關聯表R=(r1, r2, …, rm, s1, s2, …sn)，S=( s1, s2, …sn)，S的關聯表綱要是R的子集，除法運算的基本語法與定義，如下所示： R÷S = { t | (t x S)⊆R, t∈r1, r2, …, rm(R) } 上述語法的除法運算結果的關聯表綱要為：(r1, r2, …, rm)，其值組t屬於關聯表R，在與關聯表S執行卡笛生乘積運算後，其運算結果仍為R的子集。

5-3-3 除法運算-語法與定義(條件) 除法運算的2個運算元需要滿足一些條件，如下所示： 被除關聯表的屬性需要比除關聯表至少多一個，Books關聯表有3個屬性，Authors只有一個。 除關聯表的屬性集合是被除關聯表屬性集合的子集，例如：Books關聯表擁有Authors關聯表的author屬性，它是Books關聯表屬性集合的子集。

5-3-3 除法運算-語法與定義(導出) 除法運算不滿足交換律和結合律，而且並不是關聯式代數的基本運算子，因為它可以使用基本運算子來導出，若關聯表R=(r1, r2, …, rm, s1, s2, …sn)，S=( s1, s2, …sn)，如下所示： R÷S = πr1, r2, …, rm (R)－πr1, r2, …, rm((πr1, r2, …, rm (R) x S)－R)

5-3-3 除法運算-範例1 Books和Authors關聯表為例的除法運算式範例，如下所示： Result = Books÷Authors 除法運算式可以使用基本運算子導出，Books Authors運算式可以寫成： Result=πcode, title (Books)－πcode, title ((πcode, title (Books) x Authors)－Books)

5-3-3 除法運算-範例1(導出過程1) 首先執行πcode, title (Books) x Authors的卡笛生乘積運算：

5-3-3 除法運算-範例1(導出過程2) 與Books關聯表執行差集運算：(πcode, title (Books) x Authors)－Books，這是Books關聯表中不屬於Books÷Authors的值組，如下： 最後，再與Books關聯表執行差集運算：πcode, title (Books)－πcode, title ((π code, title (Books) x Authors)－Books)，就可以得到Books÷Authors的結果。

5-3-3 除法運算-範例2