intro
课程介绍
这门课主要的内容是如何去构建和设计数据库管理系统。
- ⾯向
磁盘的数据库
大纲大概是这样：
- 关系型数据库
- 是什么，如何存储、如何在之上查询
- 事务管理，以及恢复
- ⾼级主题，例如分布式数据库，或者⼀些其他类型的数据库以及关系型数 据库的⼀些扩展
- 如何对它们的规模进⾏扩展以及如何在云环境运⾏它们
lab部分，你需要从头开始构建你⾃⼰的数据库存储管理器
- 但⽆法运⾏SQL语句，也没有查询解析器，但你能够通过提供给你的⼿写代码来执⾏查询
- 因此，这要远⽐简单的键值存储来的复杂得多，但它并不是⼀个功能完善的系统
- 完全⽤C++17，这并不意味着我们会去使⽤C++17的所有⾼级特性
- 今年所有的项⽬都会在我们所开发的新学术系统BusTub上进⾏实现，所有的源码都在会Github上进⾏开源
这是⼀个⾯向硬盘的数据管理系统，它⽀持Volcano式⻛格的查询处理。该系统中的部分内容还⽀持插拔式API，这样我们就可以替换系统中已经给出的算法，使⽤不同的索引数据结构或者不同的⽇志格式和控制⽅案
数据库概述
数据库无处不在，任何程序内部都有一个数据库。许多问题都能最后简化为数据库层⾯的问题。
它是以某种⽅式去进⾏关联的数据集合，这意味着可以对现实进行建模
比如一个电子音乐商店，它背后的数据库用来存储艺术家以及他们的专辑信息
e.g. 构建一个存储信息的应用
- 每个实体例如Artist和Album会分为存为单独的csv⽂件
- 假如查询 Ice Cube 单飞的年份，我们打开csv，对每一行用逗号分割，查看第一个元素是不是~，如果是把第二个属性转换为整数返回
问题
而这种方式会有一些问题：
- ？
- 如何保证每个属性的值是合法的？
- 如果⼀张专辑是由多个艺术家制作的，那我们该如何保存数据？我们只有一个artist字段
- 可以放在同一个引号内，然后用逗号分隔
- 查询效率如何保证？
- 语言变了，但是我们想使用同一个数据库该怎么办？我们不想重复造轮子
- 并发写入数据库如何保证一致？
- 如何保证数据是安全的、不会因机器、程序故障丢失？如何进行故障恢复？如何进行分布式存储？
以上都是我们想象要⽤⼀个数据库 管理系统来帮你对此进⾏管理的原因
DBMS概述
DBMS允许程序在⽆须关⼼底层实现的情况下，对数据库中的信息进⾏存储和分析；可以复用，不必造轮子
我们这学期要设计⼀个通⽤的DBMS，即设计⽤于可以允许应⽤程序来对数据库进⾏定义，创 建，查询，更新以及管理
它们不必是内存数据库或者GPU数据库以及其他类型数据库，我们假设我们的数据库是存在硬盘⾥的
关系模型
历史
在计算机早年发展期间，⼈们便很快意识到如果有专⻔的数据库管理系统来帮助我们管理数据， 那会⾮常nice
早期数据库的逻辑层和数据系统⽤来存储数据的物理层存在了⼀种紧密耦合，如果想要转存数据，就必须改代码
Ted Codd 在1970年提出了关系模型，即你如何在数据库系统中存储数据。
关系模型概述
将数据的关系用元组表示，表与表之间的关系即是数据库。然后通过高级语言去查询，但不告诉它怎么查询，由DBMS决定怎么查询
当时的⼈们表示，没有⼀种软件可以⽣成像⼈⼯那样⾼效的查询计划。这与⼈们在1970年提出的关于编译器的观点相同，“任何编译器都⽆法⽣成和⼿写汇编⼀样⾼效的机器码”
如今，我们有了⾮常复杂的查询计划，现在的优化器并不完美，但它们所能做的⼯作要⽐⼤部分⽤⼈⼯去做的要来得更好
具体怎么存储由DBMS决定，元组仅仅只是数据的关系模型，我们永远通过元组访问数据，即便背后的存储模式变了，我们也不需要改应用程序的代码。从而，分离了逻辑层和物理层
在某些应⽤程序领域中，其中⼀些数据模型⽐关系数据模型能更好地描述数据。
关系型数据模型已经采纳了其他数据模型的⼀些概念或者思路
- 例如将数组/矩阵认为是⼀种数据模型，用于保存数组/矩阵
- 在MultiValue数据模型中，还有层次数据模型和⽹络数据模 型
关系型数据库
relation structure，定义我们的数据integrity constraints：对数据值的约束manipulation：如何操作数据
我们的所有数据用关系结构来表示，具体的某条数据被称为实例，用元组表示
- 元组每个属性的值都必须保证原子性，不可嵌套
- 但在最近，你可以在关系型数据库⾥存⼊数组，JSON对象，这种约束已经没了
- 每个属性现在都支持⼀个特殊值NULL
- 实际上你该如何储存它们，这就取决于实现了
一些术语
- 我会使⽤
relation和table这两个术语，实际上它们是⼀回事。 n-ary关系其实就是⼀张表上有n列，也即每个元组由n个属性。- 每条记录即是一个
tuple - 每个记录的
主键唯一标识了这条记录，通常是一个整数id，它还可以自增。我们使用主键跟踪一条记录 外键，指定某个属性的值必须存在另一张表上，从而维护不同表的数据一致性
e.g. 电子音乐商店
对于我们的例子，每个专辑可能有多个作者，由于属性的原子性、主键的唯一性，我们需要额外的一张中间表存储作者和专辑的关系
两个id都作为外键，DBMS会跟踪这些值的合法性
查询数据
我们不写for，而使用DML操作数据，这是一种声明式的语言，具体查询的实现方式由DBMS实现
关系代数用于过程化语言，而关系演算用于非过程化语言。
对于这⻔课，我们只关注关系代数，高效的查询方案实现可能需要关系演算、微积分等知识
关系代数
这种代数是基于无序集合的，元素可以重复
七种基本运算符，每个运算符都实现了关系间的映射。我们将这些代数原语连接起来就可以得到我们想要的结果
SQL并不依赖于关系代数，即使它使⽤关系代数作为查询执⾏时底层的操作符来使⽤
select 根据条件筛选元组，在有多个条件时，他们的顺序并不指定实际的筛选顺序——这一切由DBMS决定
projection 投影掉原关系的某些属性，生成一个新的关系
Union 取两个关系的并集。这要求两个关系兼容，即有相同的属性和类型
Intersection 取两个关系的交集，也要求它们兼容
Difference 取1中有，2中没有的元组，要求兼容
- SQL中的 except
Product 即笛卡尔积，产生两个关系中所有sql可能的组合
- SQL中的Cross Join，这是默认的关系连接形式
Join 即自然连接，如果两个关系有相同的属性，它会对这个属性进行匹配，把有相同值的元组连接到一起，然后输出
- 它和Difference不同，会有一些额外的属性输出
- 允许这些公共属性的名字可以不同
这些运算符是Ted Codd所提出的七个最核⼼的关系操作符，人们在之后添加了一些额外的东西，比如 aggregations、sorting。论文也没有提出SQL，这些都是人们后来发明的，也并不是唯一一种查询数据的方式
关系代数优化
关系代数仍有执行顺序，不同的执行顺序也会带来不同的执行效率，尽管执行结果相同
这里第二种方案效率显然更高