CMU::15-445/645::Relational Model 笔记

关系模型和关系代数

0W1wSYn

数据库

数据库是一个有组织的相互关联的数据集合，它对现实世界的某些方面进行建模。数据库是很多计算机应用的核心部分。人们经常将数据库与数据库管理系统(比如 MyQSL，Oracle，MongoDB)相混淆，数据库管理系统是指管理数据库的软件。

文本文件稻草人

数据库被存储为 DBMS 管理的逗号分隔值（CSV）文件。每个实体将被存储在它自己的文件中。应用程序每次要读取或更新记录时，都必须解析文件。每个每个实体都有自己的属性集，所以在每个文件中，不同的记录都用新的行来分隔，而记录中的每个而记录中的每个相应的属性都用逗号隔开。继续沿用数字音乐商店的例子，会有两个文件：一个是艺术家文件，另一个是专辑。一个艺术家可以有一个名字、年份和国家属性，而一张专辑有名字、艺术家和年份属性

J7czXgM

查询 Ice Cube 解散的年份

ICFu6bL

无格式文件的问题

  • 数据完整性
    • 我们如何确保每个专辑条目中的艺术家是相同的？
    • 如果有人用一个无效的字符串覆盖了专辑年份怎么办？
    • 我们如何存储一张专辑中有多个艺术家的情况？
    • 如果我们删除了一个有专辑的艺术家会发生什么？
  • 实现
    • 你如何找到一个特定的记录？
    • 如果我们现在想创建一个使用相同数据库的新应用程序，该怎么办？
    • 如果两个线程试图同时写到同一个文件怎么办？
  • 持久性
    • 如果我们的程序在更新一条记录时机器崩溃了怎么办？
    • 如果我们想在多台机器上复制数据库以获得高可用性怎么办？

数据库管理系统

  • DBMS 是一种允许应用程序在数据库中存储和分析信息的软件
  • 通用的 DBMS 被能够定义、创建、查询、更新和管理数据库

早期数据库

数据库应用很难建立和维护，因为逻辑层和物理层之间存在着紧密的耦合。

逻辑层是指数据库有哪些实体和属性，而物理层是指这些实体和属性是如何被存储的。

早期，物理层是在应用程序代码中定义的，所以如果我们想改变应用程序正在使用的物理层，我们就必须改变所有的代码来匹配新的物理层。

随着人工成本超过物理成本，这种做法逐渐不可接受，Codd 发布了关于数据关系模型的论文。

N5XTGyo

关系模型

  • 关系模型三个关键点
    • 以简单的数据结构（关系）存储数据库
    • 通过高级语言访问数据
    • 物理存储由实现决定

数据模型是描述数据库中数据的概念的集合。关系模型是一个数据模型的例子

模式是对一个特定的数据集合的描述，使用一个给定的数据模型

img

关系型数据库定了三个概念

  • 结构。关系的定义和它们的内容。这就是关系所具有的属性和这些属性可以持有的值
  • 完整性。确保数据库的内容满足约束。一个约束的例子是年份属性的任何值都必须是一个数字
  • 操作性。如何访问和修改数据库的内容

关系是一个无序的集合，包含代表实体的属性关系。由于关系是无序的，DBMS 可以以任何方式存储它们，允许进行优化

Tuple是关系中的一组属性值（也被称为它的域）。最初，值必须是原子或标量，现在值也可以是列表或嵌套数据结构。每个属性都可以是一个特殊的值 NULL，即属性是未定义的

一个有 n 个属性的关系被称为 n-ary 关系

键值

一个关系的主键唯一地标识了一个单一的 Tuple 。如果你没有定义一个主键，一些 DBMS 会自动创建一个内部主键。很多 DBMS 都支持自动生成的键，所以应用程序不必手动增加键

img

外键指定了一个关系中的属性必须映射到另一个关系中的 Tuple

img

数据操作语言 DML

一种从数据库中存储和检索信息的语言。在这方面有两类语言可选择

  • 过程式。查询指定 DBMS 应该使用的策略来寻找所需的结果
  • 声明式。查询只指定想要什么数据，而不是如何找到它

关系代数

关系代数是一组基本操作，用于检索和操作关系中的 Tuple 。每个运算符接受一个或多个关系作为输入，并输出一个新的关系。为了编写查询，我们可以将这些运算符连接起来，以创建更复杂的运算

img

选择 \(\sigma\)

接收一个关系，并从该关系中输出一个满足选择谓词的 Tuple 的子集。谓词的作用就像一个过滤器，我们可以使用连接词和非连接词来组合多个谓词

语法: \(\sigma_{predicate}(R)\)

img

投影 \(\pi\)

接收一个关系并输出一个只包含指定属性的 Tuple 的关系。你可以在输入的关系中重新安排属性的顺序，也可以操作这些值

语法: \(\pi_{A1,A2,. . . ,An}(R)\)

img

并集 \(\cup\)

接收两个关系并输出一个关系，该关系包含至少出现在一个关系中的所有 Tuple 。这两个输入关系必须具有完全相同的属性

语法: (R \(\cup\) S)

img

交集 \(\cap\)

接收两个关系，并输出一个包含所有在输入关系中出现的 Tuple 的关系。这两个输入关系必须具有完全相同的属性

语法: (R \(\cap\) S)

img

差集 -

接收两个关系并输出一个关系，该关系包含出现在第一个关系中的所有 Tuple 但不在第二个关系中。注意：两个输入关系必须有完全相同的属性

语法: (R - S)

img

叉积 \(\times\)

接收两个关系，并输出一个关系，该关系包含了所有可能的 Tuple 组合，这些 Tuple 来自输入关系的所有可能组合

语法: (R \(\times\) S)

img

连接 \(\bowtie\)

接收两个关系，并输出一个关系，该关系包含两个 Tuple 的所有组合。其中对于两个关系共享的每个属性，两个 Tuple 的属性的值都是相同

语法: (R \(\bowtie\) S)

img

其他关系代数

img

观察

关系代数是一种过程式语言，因为它定义了如何计算一个查询的高级步骤。例如，\(\sigma_{b\_id=102}(R \bowtie S)\)是说先做 R 和 S 的连接，然后再做选择，而\((R \bowtie (\sigma_{b\id=102}(S))\)会先对 S 做选择，然后再做连接。这两个语句实际上会产生相同的答案，但是如果在 10 亿个 Tuple 中，S 中只有 1 个 b_id=102 的 Tuple 那么的连接，然后再做选择，而\((R \bowtie (\sigma{b\id=102}(S))\) 将明显快于 \(\sigma{b\_id=102}(R \bowtie S)\)。

一个更好的方法是说出你想要的结果，并让 DBMS 决定它要采取的步骤来计算这个查询。SQL 正是这样做的，它是在关系模型数据库上编写查询的事实上的标准。