CMU15-445 Lecture #01: Relational Model & Relational Algebra[译]
数据库（Databases）
数据库是一个对现实世界的某个方面进行建模的有组织的、相互关联的数据集合（例如，对一个班级中的学生或数字音乐商店的建模）。人们经常将“数据库”与“数据库管理系统”（例如 MySQL、Oracle、MongoDB、Snowflake）混淆。数据库管理系统（DBMS）是管理数据库的软件。
考虑一个模拟数字音乐商店（例如 Spotify）的数据库。让数据库保存有关艺术家以及这些艺术家发布过哪些专辑的信息。
扁平文件雏形（Flat File Strawman）
数据库由数据库管理系统（DBMS）管理的逗号分隔值（CSV）文件形式存储。每个实体将被存储在自己的文件中。应用程序在每次想要读取或更新记录时都需要解析这些文件。
延续数字音乐商店的例子，我们将会有两个文件：一个用于艺术家，另一个用于专辑。
每个实体都有其自己的属性集，因此在每个文件中，不同的记录由换行符分隔，而记录内对应的属性则由逗号分隔。
例如：一个艺术家可能具有姓名、年份和国家属性，而一个专辑具有名称、艺术家和年份属性。
以下是关于艺术家信息的示例 CSV 文件，具有架构（姓名、年份、国家）：
“Wu-Tang Clan”，1992，”美国”
“Notorious BIG”，1992，”美国”
“GZE”，1990，”美国”
扁平文件存在的问题
- 效率：需要扫描整个文件并将其存储在内存中才能找到特定的记录。
- 灵活性：很难进行模式更改，即添加新字段。需要重新编写整个文件。
- 数据完整性：难以强制执行约束，例如，年份必须是一个数字。同时，在专辑文件中可能引用一个不存在的艺术家。
- 持久性：如果在我们的程序更新记录时机器崩溃了怎么办？
- 并发性：如果两个线程尝试同时更新同一条记录会怎么样？
- 抽象性：程序与物理存储（CSV 文件）紧密耦合。
数据库管理系统（DBMS）
DBMS 是一种允许应用程序对数据库进行存储和分析信息的软件。 通用的 DBMS 旨在根据某种数据模型对数据库定义、创建、查询、更新和管理。 数据模型*是描述数据库中数据的一组概念。
Examples:：关系型（最常见）、NoSQL（键/值、文档、图形）、数组/矩阵/向量（用于机器学习）。
模式是基于数据模型对特定数据集合的描述。
早期 DBMS
早期的数据库应用程序很难构建和维护，因为逻辑层和物理层之间存在紧密耦合。
逻辑层描述了数据库具有哪些实体和属性，而物理层则是这些实体和属性的存储方式。在早期，物理层是在应用程序代码中定义的，因此如果我们想要更改应用程序使用的物理层，就必须更改所有代码以适应新的物理层。
关系模型（Relational Model）
Ted Codd 注意到每次想要更改物理层时，人们都会重新编写 DBMS，因此在 1969 年，他提出了关系模型以避免这种情况。
关系模型基于关系定义了一个数据库抽象，以避免维护开销。它具有三个关键点：
- 使用简单的数据结构（关系）存储数据库。
- 通过高级语言访问数据，DBMS 找出最佳执行策略。
- 物理存储由 DBMS 实现决定。
关系数据模型定义了三个概念：
- 结构：关系及其内容的定义。这是关系具有的属性以及这些属性可以保存的值。
- 完整性：确保数据库的内容满足约束。一个示例约束是年份属性的任何值都必须是一个数字。
- 操作：如何访问和修改数据库的内容。
一个关系是一个无序集合，包含表示实体的属性之间的关系。由于关系是无序的，DBMS 可以以任何希望的方式存储它们，从而实现优化。关系中可以有重复的元素。
元组是关系中属性值的集合（也称为其域）。最初，值必须是原子或标量的，但现在值也可以是列表或嵌套的数据结构。每个属性都可以是特殊值 NULL，这意味着对于给定的元组，该属性未定义。
具有 n 个属性的关系称为 n 元关系。在本课程中，我们将互换使用关系和表。n 元关系相当于具有 n 列的表。
键（Keys）
关系的主键唯一标识单个元组。如果您未定义主键，一些 DBMS 会自动创建内部主键。许多 DBMS 支持自动生成的键，因此应用程序不必手动递增键，但某些 DBMS 仍然需要主键。 外键指定一个来自一个关系的属性必须映射到另一个关系中的元组。例如，我们可以在专辑表中包含艺术家 ID（引用艺术家表的外键）。
数据操作语言（DML）
从数据库中存储和检索信息的方法。有两类语言用于此目的：
- 过程性：查询指定了（高层次的）策略，DBMS 应该根据集合/包来查找所需的结果。例如，使用 for 循环扫描所有记录并计算有多少记录，以检索表中的记录数。
- 非过程性（声明性）：查询仅指定所需的数据，而不是如何找到它。例如，使用 SQL select count(*) from artist 来计算表中有多少条记录。
关系代数（Relational Algebra）
关系代数是一组用于检索和操作关系中的元组的基本操作。每个操作符都以一个或多个关系作为输入，并输出一个新的关系。为了编写查询，我们可以将这些操作符“链接”在一起，创建更复杂的操作。
选择（Select）
选择操作接收一个关系，并输出该关系中满足选择谓词的元组子集。谓词充当过滤器，我们可以使用合取和析取组合多个谓词。
语法：$σ_{predicate}(R)$。
Example：$σ_{aid}=’a2’(R)$
SELECT \* FROM R WHERE a_id = 'a2'
投影（Projection）
投影操作接收一个关系，并输出仅包含指定属性的元组的关系。您可以重新排列输入关系中的属性顺序，以及操纵值。
语法：πA1,A2,…,An(R)。
Example：$π_{bid}-100, aid(σ_{aid}=’a2’(R))$
SQL：SELECT b_id-100, a_id FROM R WHERE a_id = 'a2'
并（Union）
并操作接收两个关系，并输出一个包含出现在至少一个输入关系中的所有元组的关系。注意：两个输入关系必须具有完全相同的属性。 语法：(R ∪ S)。
SQL：(SELECT _ FROM R) UNION ALL (SELECT _ FROM S)
交集（Intersection）
交集操作接收两个关系，并输出一个包含出现在两个输入关系中的所有元组的关系。注意：两个输入关系必须具有完全相同的属性。
语法：(R ∩ S)。
SQL：(SELECT _ FROM R) INTERSECT (SELECT _ FROM S)
差集（Difference）
差集操作接收两个关系，并输出一个包含出现在第一个关系中但不在第二个关系中的所有元组的关系。注意：两个输入关系必须具有完全相同的属性。
语法：(R - S)。
SQL：(SELECT _ FROM R) EXCEPT (SELECT _ FROM S)
积（Product）
积操作接收两个关系，并输出一个包含来自输入关系的元组的所有可能组合的关系。
语法：(R × S)。
SQL：(SELECT _ FROM R) CROSS JOIN (SELECT _ FROM S)，或者直接 SELECT \* FROM R, S
连接（Join）
连接操作接收两个关系，并输出一个包含两个元组的组合的关系，其中对于两个关系共享的每个属性，这两个元组的该属性值是相同的。
语法：(R ▷◁ S)。
SQL：SELECT \* FROM R JOIN S USING (属性 1，属性 2...)
关系代数是一种过程性语言，因为它定义了如何计算查询的高级步骤。例如，$σ_{bid=102}$(R ▷◁ S) 表示首先执行 R 和 S 的连接，然后执行选择操作，而(R ▷◁ ($σ_{bid=102}$(S))) 将首先在 S 上执行选择，然后执行连接。这两个语句实际上会产生相同的答案，但如果在十亿个元组中只有一个具有 b id=102 的元组，那么(R ▷◁ ($σ_{bid=102}$(S))) 的速度将明显快于 $σ_{bid=102}$(R ▷◁ S)。
更好的方法是指定您想要的结果（从 R 和 S 检索联接的元组，其中 bid 等于 102），并让 DBMS 决定计算查询所需的步骤。SQL 正是这样做的，它是在关系模型数据库上编写查询的事实上的标准。