# Tuple Relational Calculus - Universal Quantifier

:::warning
對**所有**屬於整數$\mathbb{Z}$的$x$，$P(x)$皆成立。
:::
用一般的數學語言可表示為:
$$\forall x \in \mathbb{Z}, P(x)$$

但是值組導向關聯式計算的全稱量詞(universal quantifier, 寫作$\forall$)不能這樣使用，$(\forall x)$與$(x \in \mathbb{Z})$必須分開寫。

一個常見的**錯誤寫法**: $(\forall x)(x\in \mathbb{Z} \text{ and } P(x))$。
這樣代表的意思為: 對所有可能的任意數$x$，$x$皆屬於整數$\mathbb{Z}$且$P(x)$皆成立。這顯然不是我們想要的。

正確的改法如下:

$$(\forall x)( x\in \mathbb{Z} \Rightarrow P(x))$$

將$(x \in \mathbb{Z})$修改成關聯式計算range relation的寫法:
$$(\forall x)( \mathbb{Z}(x) \Rightarrow P(x))$$

其意義為: 對所有可能的$x$，若$x$屬於整數$\mathbb{Z}$，則$P(x)$成立。

又因為$p \Rightarrow q \equiv -p \vee q$，所以上面的寫法可再修改為:

$$(\forall x)( \text{ NOT}(\mathbb{Z}(x)) \text{ OR } P(x))$$

由上可知，為了縮小廣如宇宙[^universe]的$x$變數範圍，需在全稱量詞之後加上$(\text{ NOT}(...) \text{ OR }...)$結構。

Ramez Elmasri的例題答案[^bible-ex]也有這種結構。

#### 參考資料與內容:

[1] UC Berkeley, CS 186: Introduction to Database Systems, Fall 2005, Lecture Notes: Relational Calculus & SQL-I
https://www-inst.eecs.berkeley.edu//~cs186/fa05/lecs/10CalcSQLI-6up.pdf

以下節錄的內容簡單說明了universal quantifier的意思與常見用法。

> * $\forall x (P(x))$ - is only true if $P(x)$ is true for every $x$ in the universe
> * Usually: $\forall x((x\in \text{Boat})\Rightarrow(x.\text{color}=\text{"Red"}))$

如此，我們可知$(\forall x)( x\in \mathbb{Z} \Rightarrow Q(x))$與$(\forall x)( x\in \mathbb{Z} \textbf{ AND } Q(x))$的意義完全不同。

前者代表: 對所有任意一個數$x$，若$x$是整數，則$Q(x)$成立。換句話說: 對所有的整數$x$，$Q(x)$成立。

後者代表: 任意一個數$x$必是整數，且$Q(x)$成立。

[2] Ramez Elmasri, Fundamentals of Database Systems, 7th Edition

> Rule 4: If F is a formula, then so is (∀t)(F), where t is a tuple variable. The for mula (∀t)(F) is TRUE if the formula F valuates to TRUE for every tuple (in the universe) assigned to free occurrences of t in F; otherwise, (∀t)(F) is FALSE.

(∀t)的t是代表在宇宙中所有可能的tuple。

以下節錄了書中出現的universal quantifier的例題與解答。

> __Query 3.__ List the names of employees who work on all the projects controlled by department number 5.

列出參與所有由五號部門控制的專案的員工姓名。

>__Q3.__ $\{e.\text{Lname}, e.\text{Fname } | \text{ EMPLOYEE}(e) \textbf{ AND } F'\}$
$F' = ((\forall x)(\textbf{ NOT}(\text{PROJECT}(x)) \textbf{ OR } F_1))$
>$F_1 = (\textbf{ NOT}(x.\text{Dnum}=5) \textbf{ OR } F_2)$
>$F_2 = ((\exists w)(\text{WORKS_ON}(w) \textbf{ AND } w.\text{Essn}=e.\text{Ssn} \textbf{ AND } x.\text{Pnumber}=w.\text{Pno}))$

這個解答很難看懂，因此要做一些公式轉換以方便解讀。

因為$-p \vee q \equiv p \Rightarrow q$，所以可將解答中的$F'$與$F_1$重新表示成:

$F' = ((\forall x)(\text{PROJECT}(x) \Rightarrow F_1))$
$F_1 = ((x.\text{Dnum}=5) \Rightarrow F_2)$

又因為$p \Rightarrow (q \Rightarrow r) \equiv -p \vee -q \vee r \equiv (p \wedge q) \Rightarrow r$，所以可將$F'$重寫為:

$F'=((\forall x)((P \textbf{ AND } Q)\Rightarrow F_2))$,
where $P=\text{PROJECT}(x)$ and $Q=(x.\text{Dnum}=5)$

用文字說明:
- Q3: 選擇出的值組$e$的須符合: 每一個$e$都屬於EMPLOYEE 且 滿足$F'$。
- $F'$: 每一個$e$對所有可能的$x$須符合: 若$x$屬於PROJECT且$x$.Dnum=5，則須滿足$F_2$。換句話說，每一個$e$對所有屬於PROJECT的$x$須符合$F_2$。
- $F_2$: 在WORKS_ON中存在值組$w$，使得$w$.Essn=e.Ssn且$x$.Pnumber=$w$.Pno。

下面摘錄書中對解答的解說。

> In English, Q3 gives the following condition for selecting an EMPLOYEE tuple $e$: For every tuple $x$ in the PROJECT relation with $x$.Dnum=5, there must exist a tuple $w$ in WORKS_ON such that $w$.Essn=$e$.Ssn and $w$.Pno$=x$.Pnumber. This is equivalent to saying that EMPLOYEE $e$ works on every PROJECT $x$ in DEPARTMENT number 5.

[^universe]: 廣如宇宙的變數範圍
出自 Ramez Elmasri, Fundamentals of Database Systems, 7th Edition.
第8.6.3節 The Existential and Universal Quantifiers
> Rule 4: If F is a formula, then so is (∀t)(F), where t is a tuple variable. The for mula (∀t)(F) is TRUE if the formula F valuates to TRUE for every tuple (in the universe) assigned to free occurrences of t in F; otherwise, (∀t)(F) is FALSE.

(∀t)的t是代表在宇宙中所有可能的tuple。

[^bible-ex]: Ramez Elmasri的例題與答案
出自 Ramez Elmasri, Fundamentals of Database Systems, 7th Edition.
第8.6.7節 Using the Universal Quantifier in Queries
> __Query 3.__ List the names of employees who work on all the projects controlled by department number 5.

>__Q3.__ $\{e.\text{Lname}, e.\text{Fname } | \text{ EMPLOYEE}(e) \textbf{ AND } F'\}$
$F' = ((\forall x)(\textbf{ NOT}(\text{PROJECT}(x)) \textbf{ OR } F_1))$
>$F_1 = (\textbf{ NOT}(x.\text{Dnum}=5) \textbf{ OR } F_2)$
>$F_2 = ((\exists w)(\text{WORKS_ON}(w) \textbf{ AND } w.\text{Essn}=e.\text{Ssn} \textbf{ AND } x.\text{Pnumber}=w.\text{Pno}))$