贯通与综合：数据库实践课程教学建设的思考

孔令波

（北京交通大学 软件学院，北京 100044）

1 数据库管理系统教学存在的问题

作为经典的软件，关系数据库管理系统（relational database management system: RDBMS）可以说支撑起现代信息社会：大量业务都需要它的支持，传统上与编译原理和操作系统一起，成为计算机和软件专业学生必须学习的课程[1-5]。了解数据库管理系统的设计与实现，对于学生编程能力的提升以及对软件工程的理解，都是极其重要的。

现有课程往往专注于概念和原理的介绍，疏于设计与实现的展示。因为按照课程分解的思路，已经“假定”学生在学习完先修课程（如C/Java语言、面向对象、操作系统、数据结构、算法等课程）后，就已掌握将概念和理论转换为程序的能力。

从北京交通大学软件学院的教学情况看，编程课程只能解决基本的编程能力问题，学生虽然已学完相关的先修课程，但是要理解如何设计与实现编译器或数据库管理系统等这样复杂的软件也是不太可能的。

让学生了解和掌握课程相关的设计与实现，挑战显然也很大：教师需要对众多的概念和技术有深入的理解，而且还要能够将数据库管理系统的设计与实现深入浅出地展示出来。

2 数据库管理系统结构示意和技术汇总

图1所示为关系数据库管理系统的示意图，对应数据库核心系统的是大圆角方框的部分。数据库管理系统的设计与实现要面对的主要问题就是在多用户并发访问情况下，如何保证数据访问的高效以及数据的一致性。

图1中①表示网络连接，②是数据库管理系统的多线程模块，两者共同支持多用户的并发访问，即多个用户可以通过它们将数据管理指令，主要是SQL语句（structured query language，结构化查询语言）交由数据库管理系统内部的模块进行处理。

图1 现代意义上的（关系）数据库管理系统的功能结构示意图

图1中③对应数据库管理系统的数据处理模块，除了要实现对输入的SQL指令进行解析和执行，并最终将满足SQL指令的结果（主要由查询处理器（query processor）和缓冲管理（buffer management）两个模块体现）返回给用户之外，还需要保证对数据的并发访问不会导致数据不一致的风险——尤其是涉及修改同一数据的操作。数据一致由日志管理（log management）和事务管理（transaction management）保证。

基于数据库管理系统的功能模块，可以概括出需要了解的主要技术。

1）索引文件的设计与实现。

数据结构课程中实现的只是内存版本，而数据库中的索引是需要保存到文件中的。索引文件中的数据是动态更新的，如何设计索引文件的格式以保证更新效率，是一个有趣的智力挑战。需要说明的是，此处不予考虑直接操作磁盘块的编程。

2）网络编程。

之前的程序语言课程都会讲授网络编程，此处需要将网络功能嵌入线程中。

3）线程和线程池（thread pool）。

早期的数据库管理系统往往只支持进程的实现，而现代意义上的数据库管理系统一般都借助线程来实现。其中，线程池的技术更是被普遍采用以支持多用户并发访问。

4）SQL 的解析与执行。

设计与实现数据库管理系统的核心之一就是SQL语句的解析与执行。真正理解编程实现SQL的解析与执行，是一个非常有挑战的任务。

5）锁机制的实现以及对数据进行监控的锁表（lock table）结构的设计与实现。

虽然操作系统中也讲解锁的概念，甚至列举4种解决方案（软件方案，硬件方案，操作系统的方案——P、V操作和信号量以及编程语言中的方案——管程），但是那些方案只是基本的技术，不能妥善解决数据库管理系统所需面对的数据访问的动态性挑战：不同用户要访问哪些数据是不能预先知道的，只有当SQL语句执行时才能确定。因此，数据库管理系统中解决此问题的基础方案是锁表，并发访问涉及的数据在锁表中要求能够被动态管控。

上述5种技术，基本就是数据库管理系统理论课程的主要内容，但理论课更多的是介绍概念与理论，而非设计与实现[1-5]。以SQL为例，一般主要介绍SQL的语法，并且通过大量的SQL语句训练促使学生掌握这种语言，至于SQL语句到底是怎样解析和执行的，往往是语焉不详的。

3 课程建设指导思路

帮助学生学习和掌握数据库管理系统的设计与实现，就需要至少覆盖上面所列举的技术，而且必须是从设计与实现的角度，这对授课教师是很大的挑战。教师不仅要自己深入学习和理解相关技术，而且还需要慎重地筛选和编纂适当的材料以便能够向学生深入浅出地展示。在实践的基础上，总结3个有助于达成本课程目标的建议。

1） 以贯通和综合作为实践课程建设的指导思想。

以贯通和综合作为实践课程建设的指导思想即凡是有益于学生理解数据库设计与实现的内容，都应该串接起来。以展示SQL的解析与执行为例，涉及的知识分散在编译原理、SQL语法、数据结构等课程中。一方面，国内的编译原理课程往往专注于概念和理论，学生学完后一般不会编程实现；另一方面学生的学习水平不同，这都需要将相关知识按照设计与实现的思路重新整合在一起。

应对此挑战的基本思路：首先将学生已经学习过的编程技术（数学表达式的直接计算）进行扩展，介绍基于语法构建数学表达式的AST（abstract syntax tree，抽象语法树）结构的编程技巧；之后借助这一扩展的技巧讲解SQL的解析与执行。

2）有效利用开源项目，直观展示和剖析代码。

在比较许多开源的数据库管理系统[6-9]后，建议选择HyperSQL作为本课程代码阅读和调试的样例。因为HyperSQL是“纯”Java，代码量相对较小，而且它能够支持现代数据库管理系统的主要特征，如对并发访问的支持（H2不支持多线程）、MVCC（Derby不支持MVCC），甚至是嵌入式运行方式等。

3）激励学生互助学习。

在介绍背景知识后，将相关的知识点进行分解，鼓励学生组团调研和编程实践并在班上作报告。能否调动学生的学习兴趣，是决定课程建设好坏的根本。在课程建设中，尝试激励学生利用互助学习的方式，即教师在负责介绍相关的背景知识以及所设定项目需要的必要编程技巧后，鼓励学生上讲台向其他同学作报告展示其所完成的项目。这样不仅有助于锻炼学生的自学能力，而且有助于提升学生组织内容和报告的能力。此外，学生间的交流有时更容易抓住学生的理解盲点：学生彼此之间的知识水平相近，某学生不明白的，极有可能也是其他同学所不了解的。

4 课程建设

在初步确定课程的指导思路后，还需要确定课程的专题内容。在梳理专题的过程中，也要尽量做到两点：一方面要对收集到的资料进行汇总和提炼，将有价值的内容组织到讲义中；另一方面要反复思考和设计项目的内容，希望项目既有助于理解数据库管理系统核心功能，又不要超出学生的能力太远。

4.1 相关的专题概述

深入浅出地展示SQL的解析与执行，是本课程的重点和难点。我们以SQL的解析与执行为例，展示如何做到内容的“按需拿来”和提炼。

一般数据库课程可能会介绍图2所示的SQL的处理流程，即SQL语句一般经过3个环节：解析（parser）、重写（re-writing）和物理计划（physical query plan）的构建，完成从SQL语句到最终的可运行的执行序列的转换，即SQL样例→Parse Tree（解析树）→Logical Plan （逻辑计划）→Physical Query Plan（物理查询计划），但对应的代码到底是怎样的，往往语焉不详。针对此问题，采取间接理解的技巧，并在给学生提供必要的工具后，让学生较为轻松地理解SQL的解析与执行。

（1）间接理解。以数学表达式的解析与执行代码为例，帮助学生了解如何编程实现从给定的语法构建对应的数据结构（编译原理中往往将此数据结构成为AST，SQL对应的是解析树）。之后，SQL的解析与执行就可以借助数学表达式的处理来展示，因为从SQL到其实际执行是通过两次类似的转换步骤得到，也就是图2中右侧4层所表达的：第1层SQL转换为第2层的解析树；解析树又通过遍历生成第3层的关系表达式（之所以有两种关系表达式，是为了体现等价表达式的意思）；优化后的关系表达式再转换为第4层的物理计划；最后，遍历物理计划过程中执行相应的文件和数据操作即可完成SQL的实际执行。

（2）在有了（1）中的理解后，进一步通过两个环节加深学生的理解。一是在给学生介绍一些现成的工具（如Lex+Yacc[10-11]、CUP （Construction of Useful Parsers）+Flex[12-13]、ANTLR[14]等 ）后，要求学生尝试使用；二是设定项目要求学生阅读和调试HyperSQL中解析与执行SQL的代码。

从学生的反馈看，一是学生确实对这部分内容很感兴趣，二是学生很有兴致尝试和理解SQL的解析与执行。

4.2 课程项目的设计

为有效促进学生的实践，可设计如下有针对性的项目。

图2 SQL解析与执行的示意：处理流程和相关数据结构

（1）B+-树索引文件的设计与实现。虽然数据结构课程肯定介绍B+-树的概念和算法，但实现的是内存版本。此项目要求将索引结构保存在文件中，因此需要考虑很多内存版本不会涉及的挑战，如内外存存取的时间差可能导致索引的不一致性问题、如何保证数据和索引间保持高效的同步更新等。

（2）线程池对并发用户响应的仿真。在给出线程中嵌入网络技术的代码架构后，要求学生完成线程池的仿真，既帮助学生了解这种编程技巧，又有助于学生后续分析和调试HyperSQL的代码。

（3）锁表的仿真。锁表是数据库管理系统用于监管对数据进行并发访问的数据结构，基于锁表，再结合相应的访问控制协议/机制才能保证数据的一致性。在第二轮实践中，此项目选取的是数据库理论课都会讲到的二段锁（2 phased lock: 2PL）协议。

此外，课堂上也介绍了其他协议，如MVCC（multiple version concurrency control，多版本并发控制）、Snapshot等，但并没有要求学生去了解，欣喜的是第二轮中有部分学生自主地调研和了解了这些协议。

（4）数学表达式的解析和SQL解析树的构建（可借助已有的工具）。此项目要求学生实现数学表达式到AST数据结构的程序，从中体会如何基于给定的语法实现简版的解析器。在此基础上，介绍SQL解析与执行的内容，包括从解析树到关系表达式的转换以及基于关系代数变换规律构造等价的形式，并从中选择执行效率最高的PQP来执行实际的数据查询操作。

（5）HyperSQL的初步调试，通过引入HyperSQL源代码，让学生初步感受高水平Java编程的面貌，并初步了解理论部分的概念在HyperSQL中的实现，如HyperSQL中使用的是Java 的线程组（Java thread group）应对多用户的并发访问，锁表的实现是使用了对应读、写锁的哈希图（hashmap）等。

（6）使用JSP（Java server pages）和HyperSQL实现Web 项目开发。

此项目是教学大纲中强调的环节，帮助学生体会“数据库+Web”的开发方式，这是当前非常流行的软件开发技术，可以说是学生就业必备的开发技能。

（7）阅读和调试HyperSQL，以了解SQL的执行以及对事务概念的支持。此项目要求学生能够深入调试HyperSQL代码，了解其代码架构。实践证明，在前述专题的基础上，绝大多数学生可以尝试着走通一条SQL语句在HyperSQL内的解析和执行流程。

5 结语

北京交通大学软件学院自2015年便尝试开设数据库管理系统综合实践课程，在此过程中做了深入的思考和梳理，概括为如下3点建议：①从设计与实现的角度将分散在其他课程中的必要知识点融会贯通于此课程；②借助剖析源代码帮助学生体会将那些概念转化为程序的编程技巧；③尝试互助学习教学方式，让学生就所分派的项目作调研、编程实践，并在课上作专题报告，这既能促使他们自主调研相关资料和技术，又能锻炼他们整理和提炼资料甚至是表达的能力。

学校已完成两轮的授课实践，在第一轮的基础上，第二轮实践有更深入的修改，实践效果良好，不仅表现为学生对所讲授的知识点能够有所领悟，而且学生也很有兴趣亲手调试和完成相关的项目，普遍反映有将以前所学知识融会贯通的感觉。