CMU15-445 学习笔记 (一)

1. 介绍

博主对大数据相关的技术很感兴趣，大概了解了一下这个领域所需要的技能和当前的发展状态，深感个人基础薄弱。架不住兴趣的驱使，决定好好补一补这一方面的知识体系。

博主很早就对 CMU15-445/645 这门数据库入门神课有所耳闻； 尤其是课程附带的项目， 刷过的人都赞不绝口。 正好博主前段时间恶补了一番三四年没碰过的 C/C++，遂决心闯一闯这门课。

2. Lecture #1-#2: 关系型数据库概述和SQL

博主选择了2022Fall 由 Andy Pavlo 主讲的版本。不得不说，课程片头、结尾和音乐很带感，总让我联想到绝命毒师或者切尔诺贝利，恍惚间仿佛在刷剧。

第一个晚上博主听完了两节视频课。第一节课是绪论课，主要讲了几个关于数据库的一些基本概念，尤其突出了使用 DBMS (Database Management System)管理、分析数据的优势和必要性，以及关系模型的一些东西。 第二节课围绕SQL展开。教授直接在黑框中演示不同数据库下SQL指令的执行效果，效果个人认为比PPT干讲好很多。这节课程在基础的联接查询、聚合查询、嵌套查询等SQL常用查询技术的基础上，额外增加了一些相对高级的特性，主要是窗口函数和循环查询。博主此前有过一些 SQL 积累，加上 SQL 本身作为声明式的语言，语法简单，所以对大部分内容的理解都没有障碍。但是不得不说，最后扩展的循环查询大大超出了我对 SQL 以往的认知。后面关于作业部分再细讲。

这门课程有要求先修 CMU15-213，因为课程会涉及一些操作系统方面的内容。博主本科阶段的背景其实更偏电气，操作系统、编译原理等计算机专业硬课学得并不多，颇为担心后期的学习是否乏力。另一方面，Andy老师的讲话语速是真的很快，本菜鸡表示没有字幕很难跟上… 就当练耳吧。

3. 第一次课程作业

前两节课布置了一个 SQL 作业和 Project0。 SQL 作业是利用 SQLite3 从提供的 IMDB 数据中检索信息。 不得不赞叹一下这门课的配套设施。课程网站提供了非常详细的说明和课程资料，作业是在Gradescope自动评分系统中进行提交和检查；课程同时还提供了专门的论坛，且活跃度相当不错。总之，不愧神课之名。

SQL 作业包含10个具体的查询问题，作业评分需要提供对应的查询语句文件。 总的来看，前面 9 个问题在能完全理解清除题意的前提下，都没有太大难度。博主也好几个月没碰 SQL 了，依然可以比较快速的完成查询目标。稍微有坑的地方就是不同的 DBMS 在一些 SQL 语法上有差异，比如，SQLite 对字符串连接采用 ||， 而 MySQL 提供了 STRCAT 函数；在一些时间处理函数上也存在一些差异。

第 10 个问题要求排序且按照指定格式串联查询到的字符串。老师给了提示，使用循环查询。说实话，博主在刚看到这个问题时是懵逼的，理解题意都花了老半天， 而这种查询需求也是相当怪异。 Andy 老师在课堂上提供了一段循环查询的例子：

WITH RECURSIVE cteSource (counter) AS (
  (SELECT 1)
  UNION
  (SELECT counter + 1 FROM cteSource
  WHERE counter < 10) 
)

该查询语句的输出是 1 到 10 的整数序列。但是这段查询语句具体的执行逻辑，博主并不清楚。于时点进了课程文档中提供的更详细的解释，瞬间刷新了对 SQL 的认知。 不得不说，还是自己太菜。

WITH RECURSIVE 的执行规则

WITH RECURSIVE 语句的构成如上图所示，需要提供一个结果表名，初始选择子句和递归选择子句，其中初始选择语句和迭代选择语句用 UNION 进行连接。可以看到，课堂中老师展示的例子和图中的表示也是非常一致的。

该语句执行的规则如下：

• 1. 运行初始选择子句，讲查询结果放入队列；
• 2. 检查队列，若队列不为空：
  • a. 从队列中弹出一条记录；
  • b. 将该条记录插入结果表中；
  • c. 将该条记录视作表格中的唯一记录，运行递归选择子句，并将查询结果放入队列；

值得注意的是，该语句可以有不同的变化：

• 1. UNION 和 UNION ALL： 使用 UNION 时，只加入不重复的记录到队列中；而 UNION ALL 则可以加入重复的记录；
• 2. LIMIT： 若提供了 LIMIT 子句 (提供大于等于 0 的整数)，迭代过程会在结果表到达 LIMIT 限制的记录条数时终止；若为 0， 则没有数被插入结果表；
• 3. OFFSET: 若提供了 OFFSET 子句 (正数 N)，迭代过程产生的前 N 条记录会被跳过；
• 4. ORDER BY： 指明出队的顺序。 可以利用其实现深度优先和广度优先的遍历；

在理清了该语句的具体执行规则后，博主结合窗口函数，成功解答了第 10 问题。 踩了一个小坑， 题目要求连接不同的电影名，因此必须要在某个地方加 DISTINCT ：

WITH RECURSIVE tb1(concat_title,counter) AS (
    VALUES('', 0)
    UNION ALL
    SELECT concat_title||', '||title, n
    FROM
        (
	SELECT title, 
	       ROW_NUMBER() OVER(ORDER BY title) AS n
       	FROM(
            SELECT DISTINCT title 
            FROM akas JOIN titles USING(title_id)
            WHERE primary_title == 'House of the Dragon' 
                  AND type == 'tvSeries'
            ) 
        )
	JOIN tb1 ON n == counter + 1
)
SELECT SUBSTR(concat_title,3)
FROM tb1
ORDER BY counter DESC
LIMIT 1;

课程文档中老师估计大家会花 6-8个小时完成这个作业，不得不说还是挺精准的。本以为自己能很快完成，结果最后一题直接卡了 2+ 小时。

4. Project 0: C++实现字典树

此项目单开一篇细讲。踩了很多坑，也有很多收获。

总结

希望自己能存活到最后吧。从成功闯关的大佬们的经历来看， 扎实刷完这门课的所有项目大概需要 1 个月。加油 ！