关系数据模型 Relational Model

一些基本概念

Relation

• Relation：一个关系就是一张二维表。

  用数学方法表示，假设我们有一个集合集合\(D_1, D_2, \dots, D_n (D_i = a_{ij} |_{j = 1\dots k})\)，一条relation就是\(D_1\times D_2\times\dots\times D_n\)（\(D_i\)的笛卡尔积）的子集；

  换句话说，一个relation是一个\(n\)元的元组，a relation is a set of \(n\)-tuples \((a_{ij}, a_{2j},\dots , a_{nj})\) where \(\forall a_{ij}\in D_i (i\in [1,n])\)

  1. Relation Schema：描述relation的结构
  2. Relation Instance：是某个时间节点下某个具体的relation的快照

  如果采用变量的类比方式，relation就相当于variable，而variable type就是relation schema，variable value就是relation instance

• Relation Database：关系型数据库是基于relation model的一个relation的集合

Attribute

• Attribute：属性，表的列名
  1. Attribute Type：属性的类型。要求是基本类型，不能是数组
  2. Attribute Value：属性值。要求属性值atomic（关系理论第一范式），即属性值不可分割（多取值的属性multivalued attribute和复合属性composite attribute就都不满足原子性）。
• Domain：属性的取值范围（null是所有属性的domain中都存在的元素）

Key

• Superkey：能够唯一标识元组的属性集

  Example

  在关系\(Student\)中，\(\{ID\}\)和\(\{ID, name\}\)都可以视为superkey，因为它们都足以定位到一个唯一的元组

• Candidate Key：最小的superkey

  Example

  在上面的例子中，\(\{ID\}\)就是Candidate Key

• Primary Key：is candidate key and is defined by user explicitly，是candidate key并且由用户明确指定（用下划线标出）

• Foreign Key：用来描述两个表之间的关系。

  如果表1中的某个key是表2的primary key，那么它就是referencing表2的一个foreign key。此时，表1称为referencing relation，表2称为referenced relation

Relational Algebra Operations

六个基本操作

1. Select：选择，筛选出所有满足条件的元素（选择出的是一行）

   Example

   \(\sigma_{A = \beta \wedge D > 5} (r)\)表示在关系\(r\)中筛选出\(A\)列为\(\beta\)、\(D\)列大于5的行

2. Project：投影，指定一些需要保留的属性，剩下的删去（自动去重，因为relation是集合，所以不能有重复的元素）

   Example

   \(\prod_{A,C}(r)\)表示保留属性\(A\)和\(C\)，并去重（结果不存在重复的行）

3. Union：并，将两个relation取并集（两个relation必须含有相同的arity（属性个数），并且属性的domain可兼容）

   Example

   \(\prod_{\mathrm{customer\_name}}(\mathrm{depositor})\cup\prod_{\mathrm{customer\_name}}(\mathrm{borrower})\)表示所有有存款或借款的人

4. Set Different：差，和union一样，必须有相同的属性个数，且domain可兼容

5. Cartesian Product：笛卡尔积，\(r\times s = \{tq|t\in r\wedge q\in s\}\)

   Example

   一个\(p\times q\)和一个\(m\times n\)的relation作笛卡尔积会得到一个\(p\cdot m\times (q + n)\)的关系

   

   因为笛卡尔积会导致relation的规模倍增，所以在实际应用中最好能有一定的优化意识。假设我们希望找到所有在Perryridge有贷款的用户名，有如下两种查找方式：

   Query 1Query 2

   \(\prod_{\mathrm{customer\_name}}(\sigma_{\mathrm{branch\_name = Perryridge}}(\sigma_{\mathrm{borrower.loan\_number = loan.loan\_number}}(\mathrm{borrower}\times\mathrm{loan})))\)

   \(\prod_{\mathrm{customer\_name}}(\sigma_{\mathrm{borrower.loan\_number = loan.loan\_number}}(\mathrm{borrower}\times(\sigma_{\mathrm{branch\_name = Perryridge}}(\mathrm{loan}))))\)

   Query 2先缩小了relation的规模，然后才计算笛卡尔积，效率更高

6. Rename：\(\rho_X(E)\)表示将关系\(E\)重命名为\(X\)。而\(\rho_{X(A_1, A_2, \dots, A_n)}(E)\)表示将关系\(E\)重命名为\(X\)，并将原先的列名重命名为\(A_1, A_2,\dots, A_n\)

Additional Relation-Algebra Operations

因为一些基本操作的组合经常被用到，所以就有了下面4个basic operation（注意它们只是基本操作的常用组合，并不能让relational algebra实现原来无法实现的功能）

1. Set Intersection：交，\(r\cap s = \{ t|t\in r \wedge t\in s \} = r-(r-s)\)，和union对应，同样要attribute数量相同且可兼容

2. Natural Join：自然连接。根据相同的列名筛选出两张表中都存在的行，然后合并去重

   Example

   先笛卡尔积，然后选出两张表格对应列相同的行，最后投影去重

   假设\(R = (A, B, C, D), S = (B, D, E)\)，则\(R\Join S = \prod_{r.A, r.B, r.C, r.D, s.E}(\sigma_{r.B = s.B\wedge r.D = s.D}(R\times S))\)

   

3. Division：除，乘法的逆运算，找出所有同时满足条件的元组。如果\(q = r\div s\)，则\(q\)是最大的满足\(q\times s\subseteq r\)的关系

   Example

   先把\(r\)，\(s\)中同名属性，相同值情况下的元祖拿出来，再project，去掉同名属性

   假设\(R = (A_1, \dots, A_m, B_1, \dots, B_n)\)且\(S = (B_1, \dots, B_n)\)，那么\(r \div s = \{t|t\in \prod_{R-S}(r) \wedge \forall u \in s, tu\in r \}\)，最终结果的属性是\(R - S = (A_1, \dots, A_m)\)

   

   结合图表会直观的多。可以这样理解：比如说\(A,B,C\)分别代表了年级、班级和学生，则\(r\div s\)可以解释为找出所有既选了\(\{a,1\}\)课，又选了\(\{b,1\}\)课的学生。不难看出，除法常用作「查询全部」

4. Assignment：类似于重载，用\(\leftarrow\)将某个表达式取名

   Example

   当表达式比较复杂时，assignment可以让书写更加优雅。比如，我们可以将\(r\div s\)写为： $$ \begin{aligned} temp1 &\leftarrow \prod_{R-S}(r)\\ temp2 &\leftarrow \prod_{R-S}\left((temp1\times s) - \prod_{R-S, S}(r)\right)\\ result &= temp1 - temp2 \end{aligned} $$

Extended Relational-Algebra Operations

• Generalized Projection：允许在投影的下标中使用数学表达式

  Example

  如果我们想要知道每个用户信用卡中剩余的额度，可以写作\(\prod_{\mathrm{customer\_name}, \mathrm{limit - credit\_balance}}(credit\_info)\)

• Aggregate Functions：聚合操作，指的是多输入、单输出的系列操作

  基本形式为\(_{G_1,\dots, G_n} {\mathcal G}_{F_1(A_1), \dots, F_n (A_n)}\)。其中\(G\)是聚合的标准（可以理解为groupby(G)，将G相同的元素视为一个整体，进行聚合。可以省略），\(F\)是表达式，\(A\)是属性

  Example

  其实聚合操作就相当于是增加了一列统计量，常见的有均值、最值、求和、计数等。

  

数据库更改 Modification of Database

数据库的内容可能会因为下面3种操作发生改变，并且都是通过assignment操作来表示的：

1. Deletion：\(r\leftarrow r - E\)
2. Insertion：\(r\leftarrow r\cup E\)
3. Updating：To change a value in a tuple without charging all values in the tuple. 改变一个元组中的一些值，但不占用该元组中所有的元素，用广义投影表示。\(r\leftarrow\prod_{F_1, \dots, F_k}(r)\)