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