Formal RQL

Relational Algebra

關系代數 是一種 過程化查詢語言，它以 關系 作為輸入，同時輸出 關系 。

關系 是定義在一組域 上的 笛卡爾積

Basic Relational-Algebra

Select Operation

選擇 (Select) $\sigma$ 選出 滿足給定謂詞的元組。

Project Operation

投影 (Project) $\Pi$ 選出 指定的屬性

由於 關系 不允許 重復元組，所以 投影 運算之後需要再次 對元組進行去重

Set-Union Operation

參與 集合運算 的 兩個關系 必須是 相容的 (Compatible)：

• $r$ 和 $s$ 是 同元的，即 屬性數量 相同
• 對所有的 i，r的第i個屬性的域 與 s的第i個屬性的域 要相同。

Set-Difference Operation

Cartesian Product Operation

笛卡爾積 用於 組合/串接 兩個 關系。

參與 笛卡爾積 的兩個 關系 的 屬性名 必須 不同，當存在 同名屬性 (Common Attribute) 時，需要添加 關系名前綴 用於 區分。

n.b. $|r \times s| = |r| * |s|$，即 笛卡爾積 保留了 關系r的元組 和 關系s元組 的 所有可能的串接方式。

所得的 結果關系 可能有 某些元組 是 不符合 關系r 和 關系s 所提供的 信息 的。

可以使用下列的 選擇運算 來 過濾掉 這些不符合事實的元組

Renaming Operation

更名 (Rename) $\rho$ 用於為 關系代數表達式 提供 可供後續進行引用的標識符。

考慮 查詢最高工資 的例子。

任何 更名運算 都是 可替代的。可以使用 位置標記 來 隱含地 引用 關系的屬性。如 $1 = 第1個屬性

前面的例子可以 改寫 為

Additional Relational-Algebra

所有的 附加關系代數運算 都可以用 基本關系運算 來 描述。

Set-Intersection Operation

Natural-Join Operation

自然連接 $\Join$ 是 笛卡爾積 和 選擇 的一種 合並。

當 兩個關系 不存在 相同屬性 時， $r \Join s = r \times s$

自然連接 只不過是 Theta連接 的一個 特例

我們經常需要 笛卡爾積 和 選擇 一起使用，那麽可以轉而使用 Theta連接 來 簡化書寫

自然連接 滿足 結合律。

Assignment Operation

賦值運算 $\gets$ 用於將 關系代數表達式 存儲為 常量，以便後續的 引用 。

這非常類似於 PL的賦值

n.b. 賦值運算 必須 賦值 給 臨時變量，而不能直接 賦值 給 永久關系，否則將造成對 數據庫的修改。

Outer-Join Operation

外連接運算 可以處理 缺失的信息。

共有3種類型：

• 左外連接 $\sqsupset \Join$
• 右外連接 $\Join \sqsubset$
• 全外連接 $\sqsupset \Join \sqsubset$

Extended Relational-Algebra

不同於 附加關系代數，拓展關系代數 不能用 基本關系代數 來 描述。

Generalized-Project

廣義投影 (Generalized Project)：可以對 投影的屬性 進行 常量運算

Aggregate

聚集運算 (Aggregate Operation) 的輸入是 值的集合，輸出 單個值。

上面例子給出 查詢所有系的教師的平局工資 和 查詢每個系的教師的平均工資 的例子。

當 省略左側分組 時，默認為：將 輸入關系的所有元組 分組 為 唯一的一組

Tuple Relational Calculus

Definition

元組關系演算 的 形式 如下：$\s{t | P(t)}$

其中 $P$ 為 公式。公式 中出現的 變量 分為 自由變量 和 受限變量。

公式 由 如下的 原子 構成：

• $t \in r$

  $\notin$ 運算符未定義

• $t_1[x] \Theta t_2[y]$

  $\Theta$ 為 5個比較運算符

• $t[x] \Theta c$

公式 可以由 如下的 規則 來 構造：

• 原子 是 公式
• 如果 $P_1$ 是 公式，則 $\neg P_1$ 和 $(P_1)$ 也是 公式
• 如果 $P_1$ 和 $P_2$ 是 公式，則 $P_1 \or P_2$ ，$P_1 \and P_2$ 以及 $P_1 \implies P_2$ 均是 公式
• 如果 $P_1(t)$ 是包含 自由元組變量 $t$ 的 公式，且 $r$ 是 關系，則 $\exists t \in r(P_1(t))$ 和 $\forall t \in r (P_1(t))$ 也是 公式

Example

• 查詢 2009年秋季學期 或 2010年春季學期 這兩個學期 都開設 的 所有課程的集合

• 查詢 所有選修了生物系的全部課程的學生

n.b. 紅色部分 可以正確處理 當生物系沒有開設任何課程 的情況

Expression Security

考慮如下的 元組關系表達式

我們稱 該表達式 是 不安全的表達式。原因在於：neg 會產生 無限的結果。

進一步地，這是因為我們並沒有事先定義 $instructor$ 的 取值範圍。

為了解決上述問題，我們引入 域 (Domain) 的概念：

公式 $P$ 的 域 $dom(P)$ 用於描述 $P$ 所引用的所有值的集合：

• $P$ 自身所用到的值
• $P$ 中涉及的關系的元組中所出現的值

即：P的域 = P中顯式出現的值 +名稱出現在P中的那些關系的所有值

如果 元組關系表達式 $\s{t | P(t)}$ 結果中的所有值 均來自 $dom(P)$，則稱該表達式是 安全的。

安全的表達式 必定包含 有限個結果

Domain Relational Calculus

Definition

域關系演算 的 形式 如下：$\s{<x_1,x_2,\cdots,x_n> | P(x_1,x_2,\cdots,x_n)}$

域關系演算 由 如下的 原子 構成：

• $<x_1,x_2,\cdots,x_n> \in r$
• $x \Theta y$
• $x \Theta c$

公式 的 構造規則 類比 元組關系演算。

Example

• 找出 工資在80000美元以上 的教師的信息

• 查詢 2009年秋季學期 或 2010年春季學期 這兩個學期 都開設 的 所有課程的集合

• 查詢 所有選修了生物系的全部課程的學生

Expression Security

我們使用與 元組關系演算 同樣的策略來解決 表達式安全性問題：引入 域 的概念

下面幾種 語言 在 表達能力 上是 等價的：

• 基本關系代數
• 安全的元組關系演算
• 安全的域關系演算