Post

CMU-15445 Leture 1&2

数据库主要架构，以及关系模型和关系代数

Posted Updated
By Payne
20 min read

15-445/645笔记。也参考李国良老师的《数据库管理系统》。

课程资料和背景

Leture 0: 关系模型和关系代数

要求阅读《数据库系统概念》第1-2，27(在线章节)章. 课后实验为Project0.

Leture 1：SQL

要求阅读《数据库系统概念》第3-5章.

数据库/数据库管理系统背景和框架

可以参考以前写的文章: 数据库概览。

数据库（Database）和数据库管理系统（Database Management System，DBMS）这两个概念经常被混淆。数据库管理系统是管理数据库的软件。

普通文件实现的数据库

讨论了一种用逗号分隔符分割值的文件（comma-separated value，CSV）来保存数据库的情况，每次读写都需要把文件整个读到内存里。 需要考虑这样的数据库管理系统：

  • 效率；
  • 灵活性；
  • 数据完整性；
  • 持久性；
  • 并发；
  • 抽象，该实现下每个表和逻辑存储强耦合。

数据库管理系统

数据库管理系统是存储和分析数据库中数据的应用。通用的DBMS被设计为允许根据某些数据模型来定义、创建、查询、更新和管理数据库。

数据模型（data model）是用于描述数据库中的数据的概念的集合，比如：

  • 关系型（relational），也是最常见的；
  • NoSQL，包括key/value，文档模型（document），图模型（graph）；
  • 数组/矩阵/向量（array/matrix/vectors），主要用于机器学习。

模式（schema）是对基于数据模型的特定数据集合的描述。

早期的数据库管理系统和逻辑层和物理层耦合度很高，以至于更换硬件之后需要重写编写代码。

关系模型和关系代数

参考以前写的《数据库管理系统》笔记: 关系模型。

理解数据之间的关系模型之后可以了解怎么设计数据库，可以参考《数据库管理系统》笔记：文章。

这里面包括以前面试八股里面很喜欢问的，在设计关系数据库的数据表时需要考虑四个范式(用来减少依赖和数据冗余)。

关系模型

在早期的数据库管理系统基础上，诞生了关系模型。关系模型抽象了数据库中的概念，用以避免额外的维护开销。

关系模型定义了三个概念：

  • 结构（Structure）：关系的定义及其内容，即关系所具有的属性和这些属性可以持有的值。
  • 完整性（Integrity）；

  • 操作（Manipulation）。

  • 关系（relation）是一个无序的集，它包含表示实体的属性之间的关系；
  • 元组（tuple）是一组属性值（也成为域，domain）；

  • 有n个属性的关系称为n元关系，n元关系等同于一个包含n列的表。

  • 主键（Primary key）：用于唯一标识数据库表中每一行记录的一个或多个字段。每个表只能有一个主键，且主键的值必须是唯一的，不能包含空值（NULL）。
  • 外键（Foreign Key）：一个或多个字段，这些字段在一个表中引用另一个表的主键；
  • 约束（Constraints）：限制和规范数据表中数据的规则和条件。

Data Manipulation Languages（DML）

在数据库中存储和检索数据的方法，分为两类：

  • 过程式（Procedural）：要求用户明确指定数据库管理系统（DBMS）应该使用的策略和步骤，以找到所需的结果。换句话说，用户不仅要告诉系统他们想要什么数据，还要告诉系统如何获取这些数据。
  • 非过程式（声明式，Non-Procedural）：这种类型的查询语言只要求用户指定他们想要的数据，而不需要指定如何找到这些数据。用户只需描述所需数据的条件，DBMS 会自动决定最优的执行策略。例如，使用 SQL 语句 SELECT COUNT(*) FROM artist 来计算表中有多少记录。用户只需关心查询的结果，而不需要关心查询的执行过程。

关系代数

选择（Select）

选择操作用于从关系中选择满足特定条件的元组。

\[\sigma_{\text{condition}}(R)\]

投影（Projection）

投影操作用于从关系中选择特定的属性列。

\[\pi_{\text{attribute1, attribute2, ...}}(R)\]

并（Union）

并操作用于合并两个关系中的所有元组。

\[R \cup S\]

交（Intersection）

交操作用于获取两个关系中共同存在的元组。

\[R \cap S\]

差（Difference）

差操作用于获取在一个关系中存在但不在另一个关系中存在的元组。

\[R - S\]

积（Product）

积操作用于生成两个关系的所有可能的元组组合。

\[R \times S\]

连接（Join）

连接操作用于合并两个关系中的元组，满足特定的连接条件。

\[R \bowtie_{\text{condition}} S\]

数据模型

  • 文档模型（Document Model）：文档模型是一种以文档为单位存储和管理数据的模型。在这种模型中，数据被组织成一系列记录文档，每个文档包含一个命名字段/值对的层次结构；
  • 向量模型（Vector Model）: 向量模型使用一维数组来表示数据，主要用于最近邻搜索（无论是精确的还是近似的）。

SQL

可以参考以前写的《数据库管理系统》笔记：SQL

SQL历史

SQL意为”Structure Query Language”.其中包括了：

  1. Data Manipulation Language (DML)： SELECT，INSERT等语句；
  2. Data Definition Language (DDL): 用于定义表，索引，视图和其他对象；
  3. Data Control Language (DCL): 安全和访问规则。

连接

连接的指定方式：

  • 使用select，从两个表中选择字段并用where限制条件；
  • 使用JOIN语句（CMU讲义上都不提这种用法，可读性比较差）；

如：

SELECT *
FROM table1, table2
WHERE table1.common_field = table2.common_field;

SELECT *
FROM table1
JOIN table2
ON table1.common_field = table2.common_field;

JOIN提供了更多连接类型，如LEFT JOIN、RIGHT JOIN、FULL OUTER JOIN等,JOIN默认是内连接。

其实两种性能差别不大，毕竟有查询优化。建议使用前者。

聚集

常用聚集函数有：

  • AVG(col): 平均值
  • MIN(col): 最小值
  • MAX(col): 最大值
  • COUNT(col): 计数

获取login后缀为@cs的学生，以下三个查询效果相同：

1
2
3

SELECT COUNT(*) FROM student WHERE login LIKE '%@cs';
SELECT COUNT(login) FROM student WHERE login LIKE '%@cs';
SELECT COUNT(1) FROM student WHERE login LIKE '%@cs';

一个查询语句可以有多个聚集函数：

1
2

SELECT AVG(gpa), COUNT(sid)
FROM student WHERE login LIKE '%@cs';

获取每个login后缀为@cs的唯一学生数量，使用DISTINCT：

1
2

SELECT COUNT(DISTINCT login)
FROM student WHERE login LIKE '%@cs';

select包含聚集时，在聚集函数外查询其他行的行为无定义，比如

1
2
3
4

-- error!
SELECT AVG(s.gpa), e.cid
FROM enrolled AS e, student AS s
WHERE e.sid = s.sid;

select中包含的不参与聚集的列需要使用GROUP BY，比如上面这个例子应该改为：

1
2
3
4

SELECT AVG(s.gpa), e.cid
FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY e.cid;

HAVING子句过滤聚集计算输出结果，类似于GROUP BY的WHERE子句(相当于聚集前过滤一次，聚集后过滤一次)。示例：获取学生平均 GPA 大于 3.9 的课程集:

1
2
3
4
5
6
7

SELECT AVG(s.gpa) AS avg_gpa, e.cid
FROM enrolled AS e, student AS s
WHERE e.sid = s.sid
GROUP BY e.cid
HAVING avg_gpa > 3.9;
-- 这样写很多DBMS支持，但是符合SQL标准的需要这么写：
-- HAVING AVG(s.gpa) > 3.9;

字符串操作

SQL标准规定字符串区分大小写，并且只能使用单引号。有一些函数可以操作可用于查询任何部分的字符串。

  • 模式匹配: like关键词可以匹配字符串，其中”%”可以匹配任何不定长字串，”_“可以匹配任何单个字符；
  • 字符串函数：包括SUBSTRING(S, B, E); UPPER(S)等；
  • 连接：两个竖线（” “）将两个或多个字符串连接在一起成为单个字符串。

日期&时间

用于操作日期和时间属性，用在输出和谓词上。不同操作系统间区别很大。

输出重定向

可以将查询结果输出到表中而不是输出到客户端(e.g., 终端)，后续可以在数据库中查询这张表。

输出到新表中：

1

SELECT DISTINCT cid INTO CourseIds FROM enrolled;

输出到现有表中。目标表必须具有与目标表相同数量且相同类型的列，但输出查询中的列名称不必完全匹配。

1

INSERT INTO CourseIds (SELECT DISTINCT cid FROM enrolled);

输出控制

ORDER BY子句可以对SQL结果进行排序，默认排序方式是升序(ascending, ASC)。

1
2

SELECT sid, grade FROM enrolled WHERE cid = '15-721'
ORDER BY grade;

可以手动指定升序或者降序(decreasing, DESC)

1
2

SELECT sid, grade FROM enrolled WHERE cid = '15-721'
ORDER BY grade DESC;

也可以指定多个排序规则，会先按照前一个排序后，再按照后一个排序(即排序的优先级)。

1
2

SELECT sid, grade FROM enrolled WHERE cid = '15-721'
ORDER BY grade DESC, sid ASC;

还可以在ORDER BY子句中使用任意表达式：

1
2

SELECT sid FROM enrolled WHERE cid = '15-721'
ORDER BY UPPER(grade) DESC, sid + 1 ASC;

一般来说查询会输出所有查询结果，可以使用limit来限制输出结果数量：

1
2

SELECT sid, name FROM student WHERE login LIKE '%@cs'
LIMIT 10;

还可以使用偏移量来选择输出的结果的范围：

1
2

SELECT sid, name FROM student WHERE login LIKE '%@cs'
LIMIT 20 OFFSET 10; -- 返回第11-30条

嵌套查询

嵌套查询可以出现在SELECT，FROM和WHERE子句中，比如：

1
2
3
4
5
6
7
8

SELECT (SELECT 1) AS one FROM student;

SELECT name
    FROM student AS s, (SELECT sid FROM enrolled) AS e
    WHERE s.sid = e.sid;

SELECT name FROM student
    WHERE sid IN ( SELECT sid FROM enrolled );

嵌套查询结果表达式（Nested Query Results Expressions）在SQL中用于在主查询中包含子查询的结果。以下是几种常见的嵌套查询结果表达式及其作用：

  • ALL: 全部满足子查询条件的结果;
  • ANY: 任意满足子查询条件的结果;
  • EXISTS: 子查询返回结果集非空;
  • IN: 值在子查询返回结果集中，等价于=ANY();
  • NOT IN: 值不在子查询返回结果集中。

举🌰:

1
2
3
4
5

SELECT * FROM course
    WHERE NOT EXISTS(
        SELECT * FROM enrolled
            WHERE course.cid = enrolled.cid
    );

窗口函数

窗口函数（Window Function）在SQL中用于在一组相关的元组上执行滑动计算。与聚合函数不同的是，窗口函数不会将元组分组成单个输出元组，而是保留每个元组的独立性，并在其上执行计算。

常见的滑动窗口函数包括任意的聚合函数，但也包括其他特殊的窗口函数：

  • ROW_NUMBER：返回当前行的行号，在窗口函数排序之前计算；
  • RANK：返回当前行的排名位置，相同排名的则并列，在窗口函数排序之后计算。

其中OVER子句用于指定计算窗口函数时如何将元组组合到一起。

1
2

SELECT cid, sid, ROW_NUMBER() OVER (PARTITION BY cid)
    FROM enrolled ORDER BY cid;

也可以在OVER内部排序来保证确定的排序结果，即使数据库内部会因此改变。

1
2

SELECT *, ROW_NUMBER() OVER (ORDER BY cid)
FROM enrolled ORDER BY cid;

CTE

公共表表达式(Common Table Expressions, CTE)是SQL中的一种用于简化复杂查询的功能。

WITH子句将SQL查询输出绑定到一个命名的临时查询结果上。

将常数值定义到cteName上：

1
2
3
4

WITH cteName AS (
    SELECT 1
)
SELECT * FROM cteName;

将输出定义到cte的列上：

1
2
3
4

WITH cteName (col1, col2) AS (
    SELECT 1, 2
)
SELECT col1 + col2 FROM cteName;

一个查询也可以包括多个CTE：

1
2

WITH cte1 (col1) AS (SELECT 1), cte2 (col2) AS (SELECT 2)
SELECT * FROM cte1, cte2;

在SQL查询中，添加RECURSIVE关键字到WITH子句之后，可以使公共表表达式（CTE）引用自身，从而实现递归操作。递归CTE允许SQL查询执行类似于编程语言中的递归函数的操作，这使得SQL具备了图灵完备性（Turing-complete）。图灵完备性意味着SQL具有与通用编程语言相同的计算表达能力，尽管在某些情况下可能会显得更为繁琐。

Example: 递归CTE打印1-10：

1
2
3
4
5
6
7
8

-- 相当于每次都把所有元素递增1，然后插入1
WITH RECURSIVE cteSource (counter) AS (
    ( SELECT 1 )
    UNION ALL
    ( SELECT counter + 1 FROM cteSource
        WHERE counter < 10 )
)
SELECT * FROM cteSource;

写在后面

链接分享失效欢迎评论/提issue/发邮件提醒。

说实话，我觉得关系模型-关系代数-SQL这部分有点掉书袋了。实际数据库的用法/SQL语言似乎也没必要完全记住(实际这里也没办法介绍完SQL的语法，但还是需要把基础语法了解一下)，除非本身每天就是在做直接写SQL的工作。如果是面向业务的工作，只需要将主要的SQL封装起来就可以了；如果是数据库内核的工作，一般来说每个功能模块也只跟一部分SQL语言有关…而且数据库当下类型也很多，包括关系型/非关系型，向量数据库等，每种数据库查询姿势也不尽相同。

就像C++一样，几乎从来也没有人精通过…总之，尽量窥其全貌，但是精细的研究每个工具确实没什么必要。

Tech, CMU-15/445
database distributed cmu 15-445
This post is licensed under CC BY 4.0 by the author.