CMU15-445笔记

本文最后更新于 2026年3月30日下午

Relational Model & Algebra

Basic Concepts

关系性数据库：

关系和内容分开，亦即表现形式相同，内部的物理存储结构封装
保证数据满足特定约束
提供修改的API

关系：一个无序的数据的集合，表示某个实体的一系列属性（理解为一个高度抽象的数据结构）

记录/tuple（元组）：关系的实例化

Foreign Key（外键）：存放在当前表中的一个字段，指向另一个表的 ID。

Foreign Table（外键表）：被指向的那张目标表（在图中就是 Artist 和 Album）。

约束 Constraints：比如主键的唯一性

Date Manipulation Languages (DML):

Procedural 过程性的，需要一步一步指出如何计算得到结果
Non-Procedural，指出想要得到的结果而不在乎过程

我们关注后者，后者与关系代数紧密相关。

Relational Algebra

七个基本运算操作：select, projection, union, intersection, difference, product, join

select：根据给定的谓词逻辑筛选出表

projection：表示想要如何呈现，选出想要的属性（列）

union：就是取公共的属性合并关系

intersection：交

product：笛卡尔积

join：找到主值相同的部分然后连在一起

...

总之，用关系代数可以描述如何操作数据库，有时候不同的代数表达式得到相同的结果，但是性能可能依数据库不同的存储方式而异。——SQL应运而生。

虽然在开始的论文设计中关系型数据库是基于集合的，但是如今的SQL是基于multi ordered set -> bag的。

Extra

文档数据模型：JSON XML

Modern SQL

Aggregates: Functions that return a single value from a bag of tuples: AVG(col), MIN(col), MAX(col), SUM(col), COUNT(col)

GROUP BY：把tuples分类

HAVING：首先从一个错误的例子出发

SELECT AVG(s.gpa) AS avg_gpa, e.cid
FROM enrolled as e, student AS s
WHERE e.sid = s.sid
AND avg_gpa > 3.9
GROUP BY e.cid

这里的AND avg_gpa > 3.9是错误的，因为聚合计算是在查询计算之后进行的（这里需要理解SQL语句的执行顺序），正确的做法：

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

数据库实际执行的逻辑顺序是：

FROM & JOIN：先把表连起来，形成一大片原始数据。

WHERE：就在这里！ 数据库逐行扫描原始数据。如果这一行不符合条件（比如 e.sid != s.sid），就直接扔掉。

报错原因：此时数据库还没开始“分堆”（Group），更没有计算“平均分”。你让它根据 avg_gpa > 3.9 过滤，它会一脸懵：“avg_gpa 是什么？我还没算呢！”

GROUP BY：把剩下的行按 cid 分成一堆一堆。

计算聚合：在每一堆里算出 AVG(gpa)。

HAVING：轮到它了！ 数据库看着算好的平均分，把不达标的“堆”扔掉。

SELECT：最后把剩下的结果显示出来。

字符串：SQL规范：不区分大小写(not case-sensitive)，用单引号包裹。

但是各家的数据库系统都各有不同，这里也不想详细记录了。

LIKE：used for string matching

'%' matches any substrings, '_' match any one character.

也有别的很多有的没的的字符串函数。

关于日期，这一块几乎所有主流数据库不存在一个统一的标准。

窗口函数 - Window Functions：

例子：

SELECT FUNC-NAME(...) OVER(...) FROM tableName

FUNC-NAME()里面可以是Aggregation Functions 也可以是 Special Functions；所谓的 Special Functions 就是 ROW_NUMBER()和RANK()。

OVER()里面填写PARTITION BY或者ORDER BY

有窗口函数的SELECT语句不能直接使用WHERE语句。

JOIN相比于嵌套查询的优势：后者通常时间复杂度很差，一般优化成JOIN会好。

引用我们用一个最经典、最常出现在面试和实际开发中的场景：“找出每个系中 GPA 最高的一名学生”。假设我们有两张表： student (sid,...

我们用一个最经典、最常出现在面试和实际开发中的场景：“找出每个系中 GPA 最高的一名学生”。

假设我们有两张表：

student (sid, name, dept_id)

enrolled (sid, gpa)

❌ 坏例子：相关子查询 (Correlated Subquery)

这种写法非常符合直觉：对于每一个学生，我都去查一下他所在系的最大 GPA 是多少，然后看看他是不是那个最高分。

SQL
SELECT s.name, s.dept_id, e.gpa
FROM student AS s
JOIN enrolled AS e ON s.sid = e.sid
WHERE e.gpa = (
    -- 子查询：每一行都要重新跑一遍
    SELECT MAX(e2.gpa)
    FROM student AS s2
    JOIN enrolled AS e2 ON s2.sid = e2.sid
    WHERE s2.dept_id = s.dept_id
);
为什么它很糟糕？

逐行扫描：如果学校有 10,000 名学生，数据库就要执行 10,000 次内部的 SELECT MAX。

重复计算：同一个系的平均分被反复计算了成百上千次。

复杂度：这在数据库里被称为 $O(N^2)$ 操作，数据量翻倍，耗时会翻四倍。

✅ 好例子：使用 JOIN（或者 CTE 临时表）

我们改变思路：先一次性算出“每个系最高分是多少”，得到一张小清单，然后直接拿学生表去和这张清单“对暗号”。

SQL
-- 先算出每个系的最高分清单
WITH DeptMaxGpa AS (
    SELECT s2.dept_id, MAX(e2.gpa) AS max_gpa
    FROM student AS s2
    JOIN enrolled AS e2 ON s2.sid = e2.sid
    GROUP BY s2.dept_id
)
-- 然后直接做一次高效的 JOIN
SELECT s.name, s.dept_id, e.gpa
FROM student AS s
JOIN enrolled AS e ON s.sid = e.sid
JOIN DeptMaxGpa AS dmg ON s.dept_id = dmg.dept_id AND e.gpa = dmg.max_gpa;
为什么它很快？

只算一次：不管你有多少学生，每个系的最高分只计算一次。

利用索引：最后的 JOIN 可以利用数据库的 Hash Join 算法，速度极快。

批量处理：数据库最擅长处理集合对集合的操作，而不是一行一行的判断。

🚀 终极进化：使用窗口函数 (Window Function)

如果你已经掌握了我们刚才聊的窗口函数，代码会变得更加简洁且性能极佳：

SQL
SELECT name, dept_id, gpa
FROM (
    SELECT s.name, s.dept_id, e.gpa,
           RANK() OVER (PARTITION BY s.dept_id ORDER BY e.gpa DESC) as rnk
    FROM student AS s
    JOIN enrolled AS e ON s.sid = e.sid
) AS ranked_students
WHERE rnk = 1;
它的威力：

一次扫描：数据库只需要把数据读一遍，并在内存里排个序。

语义清晰：一眼就能看出你在按系排名并取第一。

总结：优化的本质

减少扫描次数：能扫一遍表解决的，绝不扫两遍。

变“串行”为“并行”：避免让子查询依赖外层查询的变量（即避免“相关”）。

相信集合的力量：永远优先考虑如何把问题转化成“表与表的连接”。

嵌套查询还有 ALL ANY IN EXISTS，让LLM来解释一下：

引用这四个关键词是 SQL 嵌套查询中的“逻辑门卫”，它们专门负责处理主查询与子查询返回的一组值之间的关系。简单来说，当子查询返回的不止一个数字（...

这四个关键词是 SQL 嵌套查询中的“逻辑门卫”，它们专门负责处理主查询与子查询返回的一组值之间的关系。

简单来说，当子查询返回的不止一个数字（而是一个列表）时，你就需要这四个兄弟来帮忙做决定。

1. ALL (全部满足)

逻辑： 只有当主查询的值，满足子查询返回结果中的每一个值时，条件才成立。

例子： WHERE gpa > ALL (SELECT gpa FROM students WHERE dept_id = 'CS')

白话： 你的 GPA 必须比 CS 系所有人都高（也就是你比 CS 系的第一名还猛）。

2. ANY (满足其一)

逻辑： 只要主查询的值，满足子查询返回结果中的至少一个值，条件就成立。

例子： WHERE gpa > ANY (SELECT gpa FROM students WHERE dept_id = 'CS')

白话： 你的 GPA 只要比 CS 系任何一个人高就行（也就是你只要不是 CS 系的倒数第一，你就赢了）。

冷知识： ANY 和 SOME 在 SQL 里是完全等价的，由于 ANY 更常用，SOME 经常被遗忘。

3. IN (是否存在)

逻辑： 检查主查询的值，是否等于子查询结果列表中的某一个。

例子： WHERE sid IN (SELECT sid FROM enrolled WHERE cid = '15-445')

白话： 看看你的 ID 是不是在那张“15-445 选课名单”里。

等价关系： IN 其实就等于 = ANY。

4. EXISTS (是否有结果)

逻辑： 它是最特别的一个，它不关心子查询返回的具体值是什么，它只关心子查询有没有返回行（是不是空集）。

例子： WHERE EXISTS (SELECT * FROM enrolled WHERE sid = s.sid AND cid = '15-445')

白话： 数据库会问：“喂，那个名单里有没有这个学生？” 如果有，哪怕只有一行，也算成功。

威力： 就像我们之前聊到的，EXISTS 配合“相关子查询”非常强大，因为它只要找到第一行匹配的就会停止扫描（短路运算），性能有时比 IN 更好。

总结对比表

关键词 逻辑核心 类似的人类语言

ALL 必须击败所有人 "你比他们每一个都强吗？"

ANY 只要击败一个 "你比他们中任何一个强吗？"

IN 精确匹配 "你在名单里吗？"

EXISTS 存在性检查 "名单里有关于你的记录吗？"

关键词	逻辑核心	类似的人类语言
`ALL`	必须击败所有人	"你比他们每一个都强吗？"
`ANY`	只要击败一个	"你比他们中任何一个强吗？"
`IN`	精确匹配	"你在名单里吗？"
`EXISTS`	存在性检查	"名单里有关于你的记录吗？"

LATERAL JOIN：SQL里面的 for-loop

common table expression (CTE)：在执行主查询之前，先定义一个临时表，并给它起个名字。

举个例子：

SELECT name FROM student
WHERE gpa > (SELECT AVG(gpa) FROM student)

使用CTE让逻辑更清晰：

WITH SchoolAvg AS (
	SELECT Avg(gpa) AS avg_gpa FROM student
)
SELECT s.name
FROM student AS s, SchoolAvg as sa
WHERE s.gpa > sa.gpa

课程笔记 > 数据库

#数据库 #SQL #索引

UCB CS168笔记 Chapter 1 Introduction 上一篇

JavaSE Note 下一篇