单个运算符的组合

关系代数允许在算符运算后的结果上继续使用算符运算
例如，从表1中选出studioName为Fox，length至少为100的titles和years：

表1 Movies

可以表示为：

π t i t l e ,   y e a r ( σ l e n g t h ≥ 100   A N D   s t u d i o N a m e = ′ F o x ′ ( M o v i e s ) ) \pi_{title,\ year}\left(\sigma_{length\ge 100\ AND\ studioName='Fox'}(Movies)\right) πtitle, year​(σlength≥100 AND studioName=′Fox′​(Movies))

命名与重命名

表达形式： ρ S ( A 1 , A 2 , … , A n ) ( R ) \rho_{S(A_1,A_2,\dots,A_n)}(R) ρS(A1​,A2​,…,An​)​(R)
相当于对关系R进行复制并对属性重新命名，命名为 ( A 1 , A 2 , … , A n ) (A_1,A_2,\dots,A_n) (A1​,A2​,…,An​)
图1展示了关系R与关系S进行 R × ρ S ( X , C , D ) ( S ) R\times\rho_{S(X,C,D)}(S) R×ρS(X,C,D)​(S)运算的结果

图1

运算符的等价关系

对于关系代数而言，许多运算是相互等价的，例如：

1、 R ∩ S = R − ( R − S ) R\cap S=R-(R-S) R∩S=R−(R−S)

2、 R ⋈ C S = σ C ( R × S ) R\Join_C S=\sigma_C(R\times S) R⋈C​S=σC​(R×S)
其中， C : E . A 1 = S . A 1   A N D   R . A 2 = S . A 2   A N D   . . . C:E.A_1=S.A_1\ AND\ R.A_2=S.A_2\ AND\, ... C:E.A1​=S.A1​ AND R.A2​=S.A2​ AND...

3、 R ⋈ S = π L ( σ C ( R × S ) ) R\Join S=\pi_L(\sigma_C(R\times S)) R⋈S=πL​(σC​(R×S))
其中， C : E . A 1 = S . A 1   A N D   R . A 2 = S . A 2   A N D   . . . C:E.A_1=S.A_1\ AND\ R.A_2=S.A_2\ AND\, ... C:E.A1​=S.A1​ AND R.A2​=S.A2​ AND...， L L L表示R与S的属性的并

线性关系代数表达

在线性关系代数表达中，赋值符号写作 : = := :=
遇到复杂查询时，需要逐步写出关系运算
例如：
π t i t l e ,   y e a r ( σ l e n g t h ≥ 100   A N D   s t u d i o N a m e = ′ F o x ′ ( M o v i e s ) ) \pi_{title,\ year}\left(\sigma_{length\ge 100\ AND\ studioName='Fox'}(Movies)\right) πtitle, year​(σlength≥100 AND studioName=′Fox′​(Movies))
可以拆分为：
R ( t , y , l , i , s , p ) : = σ l e n g t h ≥ 100 ( M o v i e s ) R(t,y,l,i,s,p):=\sigma_{length\ge 100}(Movies) R(t,y,l,i,s,p):=σlength≥100​(Movies)
S ( t , y , l , i , s , p ) : = σ s t u d i o N a m e = ′ F o x ′ ( M o v i e s ) S(t,y,l,i,s,p):=\sigma_{studioName='Fox'}(Movies) S(t,y,l,i,s,p):=σstudioName=′Fox′​(Movies)
T ( t , y , l , i , s , p ) : = R ∩ S T(t,y,l,i,s,p):=R\cap S T(t,y,l,i,s,p):=R∩S
A n s w e r ( t , y , l , i , s , p ) : = π t , y ( T ) Answer(t,y,l,i,s,p):=\pi_{t,y}(T) Answer(t,y,l,i,s,p):=πt,y​(T)

除法运算

常用于查找选修全部课程的人、参加全部活动的人等情形
π s n o ,   c n o ( S C ) ÷ π c n o ( C ) = π s n o ( S C ) − π s n o ( π s n o ( S C ) × π c n o ( C ) − π s n o ,   c n o ( S C ) ) \pi_{sno,\ cno}(SC)\div \pi_{cno}(C)=\pi_{sno}(SC)-\pi_{sno}(\pi_{sno}(SC)\times\pi_{cno}(C)-\pi_{sno,\ cno}(SC)) πsno, cno​(SC)÷πcno​(C)=πsno​(SC)−πsno​(πsno​(SC)×πcno​(C)−πsno, cno​(SC))
如图2所示，关系r和关系s进行运算r ÷ \div ÷s运算：

图2

泛化投影

与投影类似，但不仅可以投影到属性上，还可以代入到数学表达式上，例如： π c u s t o m e r _ n a m e ,   l i m i t − c r e d i t _ b a l a n c e ( c r e d i t _ i n f o ) \pi_{customer\_name,\ limit-credit\_balance}(credit\_info) πcustomer_name, limit−credit_balance​(credit_info)中，在投影的同时，还进行了limit-credit_balance的运算

聚集函数

由多个值得到一个值，例如：
1、 a v g avg avg：求平均值
2、 m i n min min：求最小值
3、 m a x max max：求最大值
4、 s u m sum sum：对值求和
5、 c o u n t count count：统计取值的个数

外连接

左外连接：保留自然连接的左边失配的元组
右外连接：同理
图3显示了两关系自然连接与左外连接的结果，注意到左外连接时，关系Loan中的L-260所在元组被保留，customer_name相应地为缺省

图3 外连接示例

关系的约束

在使用关系代数时，有两种表示约束的方式（此处假定R和S为两个关系代数表达式）：
1、 R = ∅ R=\empty R=∅，表示R值为空
2、 R ⊆ S R\subseteq S R⊆S，表示R中的所有元组必定会在S中出现

引用完整性

π A ( R ) ⊆ π B ( S ) \pi_A(R)\subseteq \pi_B(S) πA​(R)⊆πB​(S)
对于在关系R中的值为v的属性A，希望它能够在关系S的属性B中以值为v的形式出现（具有外键特性）

键约束

一个属性或属性集所构成的关键字
没有任何元组在键上具有完全相同的属性分量

自定义约束条件

类似地，可以进行自定义约束条件

数据库的修改

数据库的修改分为三类：删除、插入和修改

删除

关系代数表示形式： r ← r − E r\leftarrow r-E r←r−E，其中r为关系，E为一个元素（？）

插入

关系代数表示形式： r ← r ∪ E r\leftarrow r\cup E r←r∪E

修改

关系代数表示形式： r ← π F 1 , F 2 , . . . , F n ( σ p ( r ) ) ∪ ( r − σ p ( r ) ) r\leftarrow \pi_{F_1,F_2,...,F_n}(\sigma_p(r))\cup (r-\sigma_p(r)) r←πF1​,F2​,...,Fn​​(σp​(r))∪(r−σp​(r))

ch3.关系数据库的设计理论

函数依赖

函数依赖（Functional Dependency/FD）的定义

任意两条记录，如果在A上的记录一致时，在B上的也一致，则称A决定B，记做 A → B A\rightarrow B A→B
进一步地说，在关系R中，如果任意两个元组当属性 A 1 A 2 . . . A n A_1A_2...A_n A1​A2​...An​相等时， B 1 B 2 . . . B m B_1B_2...B_m B1​B2​...Bm​也相等，则称 A 1 A 2 . . . A n A_1A_2...A_n A1​A2​...An​决定 B 1 B 2 . . . B m B_1B_2...B_m B1​B2​...Bm​，记做： A 1 A 2 . . . A n → B 1 B 2 . . . B m A_1A_2...A_n\rightarrow B_1B_2...B_m A1​A2​...An​→B1​B2​...Bm​
实际上，上式等价于
A 1 A 2 . . . A n → B 1 A_1A_2...A_n\rightarrow B_1 A1​A2​...An​→B1​
A 1 A 2 . . . A n → B 2 A_1A_2...A_n\rightarrow B_2 A1​A2​...An​→B2​
. . . ... ...
A 1 A 2 . . . A n → B m A_1A_2...A_n\rightarrow B_m A1​A2​...An​→Bm​

例如，关系Movies1(title, year, length, genre, studioName, starName)中， t i t l e ,   y e a r → l e n g t h   g e n r e   s t u d i o N a m e title,\ year\rightarrow length\ genre\ studioName title, year→length genre studioName，但不满足 t i t l e ,   y e a r → s t a r N a m e title,\ year\rightarrow starName title, year→starName

函数依赖分类

1、平凡的函数依赖

对于属性集X,Y，如果X是Y的子集，则一定有 Y → X Y\rightarrow X Y→X
假定属性集X为{A, B}，属性集Y为{A, B, C}，当两个元组的属性集Y一致时，显然属性集X也一致

2、部分/完全函数依赖

部分依赖：已知 X → Y X\rightarrow Y X→Y，若存在X的真子集X’，使得 X ′ → Y X'\rightarrow Y X′→Y，那么 X → Y X\rightarrow Y X→Y部分依赖
完全依赖：已知 X → Y X\rightarrow Y X→Y，若不存在X的真子集X’，使得 X ′ → Y X'\rightarrow Y X′→Y，那么 X → Y X\rightarrow Y X→Y完全依赖

3、传递依赖

X → Y X\rightarrow Y X→Y，但 Y ↛ X ,   Y → Z Y\not\rightarrow X,\ Y\rightarrow Z Y​→X, Y→Z，那么 X → Z X\rightarrow Z X→Z

函数依赖举例

分子运动：假定有N个分子在容器中运动，现使用关系R(ID, x, y, z, v x v_x vx​, v y v_y vy​, v z v_z vz​)来描述这些分子，则此关系R具有下述关系依赖（假定分子的坐标不会重合）：

I D → x ,   I D → y ,   I D → z ID\rightarrow x,\ ID\rightarrow y,\ ID\rightarrow z ID→x, ID→y, ID→z

I D → v x ,   I D → v y ,   I D → v z ID\rightarrow v_x,\ ID\rightarrow v_y,\ ID\rightarrow v_z ID→vx​, ID→vy​, ID→vz​

( x , y , z ) → I D ,   ( x , y , z ) → v x (x,y,z)\rightarrow ID,\ (x,y,z)\rightarrow v_x (x,y,z)→ID, (x,y,z)→vx​

( x , y , z ) → v y ,   ( x , y , z ) → v z (x,y,z)\rightarrow v_y,\ (x,y,z)\rightarrow v_z (x,y,z)→vy​, (x,y,z)→vz​

键

关系的键

候选关键字：对于X → \rightarrow →U，对于任意X的子集X’，都不满足 X ′ ↛ U X'\not\rightarrow U X′​→U，则X是候选关键字
候选关键字能够唯一地确定记录

关键字（键）：给定R，属性全集U，属性集X。若X → \rightarrow →U，且不存在X的真子集X’，使得X’ → \rightarrow →U成立，则X’是关键字
确定关键字时，元组也随之确定
有多个关键字时，选取主关键字（主键）

主属性：所有候选关键字中的属性
其他属性为非主属性

键可以是单个属性，也可以是属性集

超键

包含键的属性集称为超键

范式

第一范式：表格中不能套表格

第二范式：不存在非主属性对码（关键字）的部分依赖

第三范式：不存在非主属性对码的传递依赖

BCNF：对于一个关系R，每个函数左边都包含一个候选关键字

不满足范式时，需要想办法修改函数依赖关系

寻找函数依赖

F是一个函数依赖集， X → Y ,   X → Y ∈ F X\rightarrow Y,\ X\rightarrow Y\in F X→Y, X→Y∈F

推理规则：阿氏（Armstrong）公理

1、自反律：若 Y ⊆ X Y\subseteq X Y⊆X，则 X → Y X\rightarrow Y X→Y
2、增广律：若 X → Y X\rightarrow Y X→Y， Z ⊆ U Z\subseteq U Z⊆U，则 X Z → Y Z XZ\rightarrow YZ XZ→YZ
3、传递律：若 X → Y X\rightarrow Y X→Y， Y → Z Y\rightarrow Z Y→Z，则 X → Z X\rightarrow Z X→Z

也能表示为：

1、X为Y的子集，则 Y → X Y\rightarrow X Y→X
2、 X → Y X\rightarrow Y X→Y，则 X Z → Y Z XZ\rightarrow YZ XZ→YZ
3、 X → Y X\rightarrow Y X→Y， Y → Z Y\rightarrow Z Y→Z，则 X → Z X\rightarrow Z X→Z

属性闭包

对于闭包 X F + X_F^+ XF+​，如果 Y Y Y是 X F + X_F^+ XF+​的子集，则有 X → Y ∈ F X\rightarrow Y\in F X→Y∈F

寻找属性X的闭包的方式：给定一个函数依赖F，给定一个属性集X
1、 X F + = X X_F^+=X XF+​=X
2、如果 A → B ∈ F A\rightarrow B\in F A→B∈F并且A是X的子集（而B不是）
那么 X F + = X F + ∪ B X_F^+=X_F^+\cup B XF+​=XF+​∪B，直到 X F + X_F^+ XF+​不发生变化或者 X F + = U X_F^+=U XF+​=U（U为属性全集）

举例：
F = { A → B , A → C , E → F , A → F } F=\{A\rightarrow B, A\rightarrow C, E\rightarrow F, A\rightarrow F\} F={A→B,A→C,E→F,A→F}
A + = A B C F ,   ( B C ) + = B C ,   ( E ) + = E F A^+=ABCF,\ (BC)^+=BC,\ (E)^+=EF A+=ABCF, (BC)+=BC, (E)+=EF
A + A^+ A+的计算过程：首先设定 A + = { A } A^+=\{A\} A+={A}，对于 A → B ∈ F A\rightarrow B\in F A→B∈F， A ∈ A + A\in A^+ A∈A+而 B ∉ A + B\not\in A^+ B​∈A+，因此 A + A^+ A+更新为 { A , B } \{A,B\} {A,B}。同理，从 A → C ∈ F A\rightarrow C\in F A→C∈F中更新为 A + = { A , B , C } A^+=\{A,B,C\} A+={A,B,C}，最后从 A → F ∈ F A\rightarrow F\in F A→F∈F中更新为 A + = { A , B , C , F } A^+=\{A,B,C,F\} A+={A,B,C,F}

最小函数依赖集

最小函数依赖集（最小化基本集）满足三个条件：
1、不存在多余的函数依赖
2、每个函数依赖的右边是单个属性
3、每个函数依赖的左边不包含多余的属性

获取最小化基本集，可以以上述三个条件为目标，对原有FD逐步进行修正。（此处参考：https://blog.****.net/TNTnine/article/details/82769796）
对于条件2，使用分解规则，例如 X → Y Z X\rightarrow YZ X→YZ拆分为 X → Y X\rightarrow Y X→Y和 X → Z X\rightarrow Z X→Z
对于条件1：判断 A → B A\rightarrow B A→B是不是多余的：尝试去掉 A → B A\rightarrow B A→B（即 F − { A → B } F-\{A\rightarrow B\} F−{A→B}），然后在剩下的FD中计算 A + A^+ A+，若这个 A + A^+ A+包含 B B B，则说明函数依赖 A → B A\rightarrow B A→B是多余的，可以删去
对于条件3：去除各依赖左边的多余的属性。例如 X Y → A XY\rightarrow A XY→A，判断 Y Y Y是否多余（即 X → A X\rightarrow A X→A是否能代替 X Y → A XY\rightarrow A XY→A）时，需要查看 X + X^+ X+是否包含 A A A，如果包含，则说明Y是多余属性，可以去掉