2022 的 15-445 开始了，利用周末的时间学习一下，本专栏应该是 lecture、project、homework 都会记录，希望一年内能把整个课程做完，lecture 部分并不全面，只挑了些我认为的重点记录。

课程资料

课件、笔记、项目

数据模型

关系型数据库用的最多，使用的是关系模型。除了关系型数据库外，还有 NoSQL 数据库，使用键值模型、图模型、文档模型、列簇模型；机器学习数据库，使用数组/矩阵模型。

关系模型

定义 RelationRelationRelation 为: R(id,name,year)R(id, name, year)R(id,name,year)，TuplesTuplesTuples 为: {T(1,Alice,1992),T(2,Bob,1996)}\{T(1, Alice, 1992), T(2, Bob, 1996)\}{T(1,Alice,1992),T(2,Bob,1996)}

定义 SchemaSchemaSchema 为 {Relation,Tuples}\{Relation, Tuples\}{Relation,Tuples}，如此 SchemaSchemaSchema 可以用一张表来描述。

id	name	year
1	Alice	1992
2	Bob	1996

DML

DML，数据操作语句，用于数据库中存储和检索数据，分为命令式和声明式。

命令式

命令式 DML 基于关系代数运算，每种运算有一或多个关系模型作为输入，输出新的关系模型。运算类型和符号语言如下。

并

交

差

积

链接

选择

投影

不同的关系运算可能得到相同的结果，例如 R⋈σid=0(S)R \bowtie \sigma_{id=0}(S)R⋈σid=0​(S) 和 σid=0(R⋈S)\sigma_{id=0}(R \bowtie S)σid=0​(R⋈S)，但是前者的计算速度更快。

声明式

使用命令式 DML，可能需要开发者思考写出性能搞好的语句，这比较麻烦。可以使用更高级的语句，只声明最后需要的结果，而不去关心如何计算。SQL 就是声明式，与命令式可以互相转换。

声明式	命令式
SELCT * FROM R UNION ALL SELCT * FROM S;	R∪SR \cup SR∪S
SELCT * FROM R INTERSECT SELCT * FROM S;	R∩SR \cap SR∩S
SELCT * FROM R EXCEPT SELCT * FROM S;	R−SR - SR−S
SELCT * FROM R CROSS JOIN S;	R×SR \times SR×S
SELCT * FROM R NATURAL JOIN S;	R⋈SR \bowtie SR⋈S
SELECT * FROM R WHERE id=0;	σid=0R\sigma_{id=0}Rσid=0​R
SELECT id+1, FROM R WHERE id=0;	πid+1R\pi_{id+1}Rπid+1​R

课程实验

完成 Project0，实现一个并发安全的字典树，主要是通过这个 Project 学习一下 C++ 使用。