杨剑锋12335247第12周书面作业

数据库

---

一、证明“多值依赖”性质1，3，5，6

(1) 多值依赖具有对称性。即若$X \to\to Y$，则$X \to\to Z$，其中$Z=U-X-Y$。

证明
$X \to\to Y$
即在$R(U)$的任一关系$r$中，
若元组$t,s\in r,t[X]=s[X]$，
必然存在$w',v' \in r$，
使得

$$w'[X]=v'[X]=t[X]=s[X]\\ w'[Y]=t[Y], w'[Z]=s[Z]\\ v'[Y]=s[Y], v'[Z]=t[Z]$$
令$w=v',v=w'$，则$w,v \in r$且
$$w[X]=v[X]=t[X]=s[X]\\ w[Z]=t[Z],w[Y]=s[Y]\\ v[Z]=s[Z],v[Y]=t[Y]$$
$\therefore X\to\to Z$

---

(3)函数依赖可以看作是多值依赖的特殊情况，即若$X \to Y$，则$X \to\to Y$。

证明
设$X\to Y$，取任意元组$t,s$，
使$t[X]=s[X]$，则$t[Y]=s[Y]$
取$w=s,v=t$，则

$$w[X]=v[X]=t[X]=s[X]\\ w[Y]=s[Y]=t[Y]=v[Y]\\ w[Z]=s[Z],v[Z]=t[Z]$$
由等价定义，有$X\to\to Y$。

---

(5)若$X\to\to Y,X\to\to Z$，则 $X\to\to Y\cap Z$

证明

$$\because X\to\to Y,X\to\to Z$$
由性质(1)，有 $$X\to\to U-X-Y, X\to\to U-X-Z$$
由性质(4)，有
$$\therefore X\to\to (U-X-Y)\cup (U-X-Z)$$
即
$$X\to\to U-X-(Y \cap Z)$$
$\therefore X\to\to Y\cap Z$

---

(6)若$X\to\to Y,X\to\to Z$，则$X\to\to Y-Z,X\to\to Z-Y$。

证明
$\because X\to\to Y$
$\therefore X\to\to U-X-Y$
$\therefore X\to\to (U-X-Y)\cup Z$
$\therefore X\to\to U-X-(Y - Z)$
$\therefore X\to\to Y-Z$
同理，$X \to\to Z-Y$

---

二、证明“伪传递规则”和“分解规则”（书P191）

伪传递规则（pseudo transitivity rule）：由$X\to Y,WY\to Z,$ 有 $XW\to Z$。

证明

$$\because X\to Y \\ \therefore WX \to WY \\ \because WY\to Z \\ \therefore WX \to Z$$
即$XW\to Z$

---

分解规则（decomposition rule）：由$X\to Y$及$Z\subseteq Y$，有$X\to Z$。

证明

$$\because Z\subseteq Y \\ \therefore Y\to Z （自反律）\\ \because X\to Y \\ \therefore X\to Z （传递律）$$