关系模型与关系代数
1.简介¶
无论是主流的关系数据库或者其他非关系数据库，它们的本质都是由无序的数据集构成模型，且能够提供高效的查询、修改等操作的系统。
同时，数据库往往能支持许多特性，如事务、并发控制、原子操作等，甚至支持分布式等能力。
15-445主要讨论的是关系模型下的关系数据库。关系模型的数据结构常常以关系，也称之为表（relation、table）呈现，其中relations是由无序的元组（tuple）组成的。tuple在table中表现为行，由各个属性（attributes）组成，表现为table中的列。
2.关系模型¶
如有一张名为instructor的表，如下所示
| ID | Name | dept_name | Salary |
|---|---|---|---|
| 10101 | Srinivasan | Comp.Sci. | 65000 |
| 12121 | Wu | Finance | 90000 |
其中定义了tuple结构的 |ID|name|dept_name|salary| 称之为模式（schema），按照schema定义存储的行就是上述的tuple，其属性为attribute。
schema不仅定义了tuple的组成，还需要定义主码（primary key），利用primary key去区分关系中不同的tuple。
关系模型有三类完整性约束（Integrity）
- 实体完整性：指的是一个tuple的primary key不能为空。事实上，若开发者在定义schema时没有制定primary key，数据库会自行利用唯一的方式去构建primary key。在MySQL中，如果没有主动设置主键，MySQL就会选一个不包含NULL的第一个唯一索引列作为主键列，并利用它生产聚集索引。如果没有这样的索引就会利用行号作为主键，大小为6bytes，并且自增。可以用select _rowid from table来查询。
- 参照完整性：是指参照关系中每个元素的外码（foreign key）要么为空(NULL)，要么等于被参照关系中某个元素的主码。这也是foreign key的定义：对于参照关系的每一个tuple来说，foreign key的取值肯定等于被参照关系中某个tuple中primary key的取值。
- 用户定义的完整性：比如primary key常用的自增约束，非空（NOT NULL）约束等
实体完整性很好理解，用于识别唯一的tuple；参照完整性主要用于在多表进行合并（JOIN）时，将tuple进行一一对应；用户定义的完整性则是去除部分不合理的数据。
因此，除了还没有提到的操作（Manipulation），关系模型主要关注三方面
- Structure：关系的定义。
- Integrity：保证数据的合理。
- Manipulation：如何去对数据进行操作。
3.SQL & 关系代数¶
SQL是数据库操作语言，通过上层的关系逻辑运算对已有的一个或多个table进行操作，从而生成新的table的工具。
常见的关系代数有
- 投影Projection（π）：选择table中特定的attribute，生成新的表table。
- 选择Select（σ）：类似Filter，将table作为输入，输出为经过筛选的subset table。
- 并运算Union（∪）：取两个table的交集作为输出，拥有自动去重的能力。
- 交运算Intersection（∩）：取两个table的交集作为输出。
- 差运算Difference（-）：取两个table的差集作为输出。
- 笛卡尔积Product（×）：生成两个table所有可能的tuple作为新的table。
- 连接Join：用于把来自两个或多个表作为输入，基于这些表之间的共同字段将tuple结合起来，可以看成是Product的扩展。