孔令波

（北京交通大學(xué) 軟件學(xué)院，北京 100044）

1 數(shù)據(jù)庫(kù)管理系統(tǒng)教學(xué)存在的問(wèn)題

作為經(jīng)典的軟件，關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)（relational database management system: RDBMS）可以說(shuō)支撐起現(xiàn)代信息社會(huì)：大量業(yè)務(wù)都需要它的支持，傳統(tǒng)上與編譯原理和操作系統(tǒng)一起，成為計(jì)算機(jī)和軟件專業(yè)學(xué)生必須學(xué)習(xí)的課程[1-5]。了解數(shù)據(jù)庫(kù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，對(duì)于學(xué)生編程能力的提升以及對(duì)軟件工程的理解，都是極其重要的。

現(xiàn)有課程往往專注于概念和原理的介紹，疏于設(shè)計(jì)與實(shí)現(xiàn)的展示。因?yàn)榘凑照n程分解的思路，已經(jīng)“假定”學(xué)生在學(xué)習(xí)完先修課程（如C/Java語(yǔ)言、面向?qū)ο蟆⒉僮飨到y(tǒng)、數(shù)據(jù)結(jié)構(gòu)、算法等課程）后，就已掌握將概念和理論轉(zhuǎn)換為程序的能力。

從北京交通大學(xué)軟件學(xué)院的教學(xué)情況看，編程課程只能解決基本的編程能力問(wèn)題，學(xué)生雖然已學(xué)完相關(guān)的先修課程，但是要理解如何設(shè)計(jì)與實(shí)現(xiàn)編譯器或數(shù)據(jù)庫(kù)管理系統(tǒng)等這樣復(fù)雜的軟件也是不太可能的。

讓學(xué)生了解和掌握課程相關(guān)的設(shè)計(jì)與實(shí)現(xiàn)，挑戰(zhàn)顯然也很大：教師需要對(duì)眾多的概念和技術(shù)有深入的理解，而且還要能夠?qū)?shù)據(jù)庫(kù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)深入淺出地展示出來(lái)。

2 數(shù)據(jù)庫(kù)管理系統(tǒng)結(jié)構(gòu)示意和技術(shù)匯總

圖1所示為關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)的示意圖，對(duì)應(yīng)數(shù)據(jù)庫(kù)核心系統(tǒng)的是大圓角方框的部分。數(shù)據(jù)庫(kù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)要面對(duì)的主要問(wèn)題就是在多用戶并發(fā)訪問(wèn)情況下，如何保證數(shù)據(jù)訪問(wèn)的高效以及數(shù)據(jù)的一致性。

圖1中①表示網(wǎng)絡(luò)連接，②是數(shù)據(jù)庫(kù)管理系統(tǒng)的多線程模塊，兩者共同支持多用戶的并發(fā)訪問(wèn)，即多個(gè)用戶可以通過(guò)它們將數(shù)據(jù)管理指令，主要是SQL語(yǔ)句（structured query language，結(jié)構(gòu)化查詢語(yǔ)言）交由數(shù)據(jù)庫(kù)管理系統(tǒng)內(nèi)部的模塊進(jìn)行處理。

圖1 現(xiàn)代意義上的（關(guān)系）數(shù)據(jù)庫(kù)管理系統(tǒng)的功能結(jié)構(gòu)示意圖

圖1中③對(duì)應(yīng)數(shù)據(jù)庫(kù)管理系統(tǒng)的數(shù)據(jù)處理模塊，除了要實(shí)現(xiàn)對(duì)輸入的SQL指令進(jìn)行解析和執(zhí)行，并最終將滿足SQL指令的結(jié)果（主要由查詢處理器（query processor）和緩沖管理（buffer management）兩個(gè)模塊體現(xiàn)）返回給用戶之外，還需要保證對(duì)數(shù)據(jù)的并發(fā)訪問(wèn)不會(huì)導(dǎo)致數(shù)據(jù)不一致的風(fēng)險(xiǎn)——尤其是涉及修改同一數(shù)據(jù)的操作。數(shù)據(jù)一致由日志管理（log management）和事務(wù)管理（transaction management）保證。

基于數(shù)據(jù)庫(kù)管理系統(tǒng)的功能模塊，可以概括出需要了解的主要技術(shù)。

1）索引文件的設(shè)計(jì)與實(shí)現(xiàn)。

數(shù)據(jù)結(jié)構(gòu)課程中實(shí)現(xiàn)的只是內(nèi)存版本，而數(shù)據(jù)庫(kù)中的索引是需要保存到文件中的。索引文件中的數(shù)據(jù)是動(dòng)態(tài)更新的，如何設(shè)計(jì)索引文件的格式以保證更新效率，是一個(gè)有趣的智力挑戰(zhàn)。需要說(shuō)明的是，此處不予考慮直接操作磁盤塊的編程。

2）網(wǎng)絡(luò)編程。

之前的程序語(yǔ)言課程都會(huì)講授網(wǎng)絡(luò)編程，此處需要將網(wǎng)絡(luò)功能嵌入線程中。

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

早期的數(shù)據(jù)庫(kù)管理系統(tǒng)往往只支持進(jìn)程的實(shí)現(xiàn)，而現(xiàn)代意義上的數(shù)據(jù)庫(kù)管理系統(tǒng)一般都借助線程來(lái)實(shí)現(xiàn)。其中，線程池的技術(shù)更是被普遍采用以支持多用戶并發(fā)訪問(wèn)。

4）SQL 的解析與執(zhí)行。

設(shè)計(jì)與實(shí)現(xiàn)數(shù)據(jù)庫(kù)管理系統(tǒng)的核心之一就是SQL語(yǔ)句的解析與執(zhí)行。真正理解編程實(shí)現(xiàn)SQL的解析與執(zhí)行，是一個(gè)非常有挑戰(zhàn)的任務(wù)。

5）鎖機(jī)制的實(shí)現(xiàn)以及對(duì)數(shù)據(jù)進(jìn)行監(jiān)控的鎖表（lock table）結(jié)構(gòu)的設(shè)計(jì)與實(shí)現(xiàn)。

雖然操作系統(tǒng)中也講解鎖的概念，甚至列舉4種解決方案（軟件方案，硬件方案，操作系統(tǒng)的方案——P、V操作和信號(hào)量以及編程語(yǔ)言中的方案——管程），但是那些方案只是基本的技術(shù)，不能妥善解決數(shù)據(jù)庫(kù)管理系統(tǒng)所需面對(duì)的數(shù)據(jù)訪問(wèn)的動(dòng)態(tài)性挑戰(zhàn)：不同用戶要訪問(wèn)哪些數(shù)據(jù)是不能預(yù)先知道的，只有當(dāng)SQL語(yǔ)句執(zhí)行時(shí)才能確定。因此，數(shù)據(jù)庫(kù)管理系統(tǒng)中解決此問(wèn)題的基礎(chǔ)方案是鎖表，并發(fā)訪問(wèn)涉及的數(shù)據(jù)在鎖表中要求能夠被動(dòng)態(tài)管控。

上述5種技術(shù)，基本就是數(shù)據(jù)庫(kù)管理系統(tǒng)理論課程的主要內(nèi)容，但理論課更多的是介紹概念與理論，而非設(shè)計(jì)與實(shí)現(xiàn)[1-5]。以SQL為例，一般主要介紹SQL的語(yǔ)法，并且通過(guò)大量的SQL語(yǔ)句訓(xùn)練促使學(xué)生掌握這種語(yǔ)言，至于SQL語(yǔ)句到底是怎樣解析和執(zhí)行的，往往是語(yǔ)焉不詳?shù)摹?/p>

3 課程建設(shè)指導(dǎo)思路

幫助學(xué)生學(xué)習(xí)和掌握數(shù)據(jù)庫(kù)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，就需要至少覆蓋上面所列舉的技術(shù)，而且必須是從設(shè)計(jì)與實(shí)現(xiàn)的角度，這對(duì)授課教師是很大的挑戰(zhàn)。教師不僅要自己深入學(xué)習(xí)和理解相關(guān)技術(shù)，而且還需要慎重地篩選和編纂適當(dāng)?shù)牟牧弦员隳軌蛳驅(qū)W生深入淺出地展示。在實(shí)踐的基礎(chǔ)上，總結(jié)3個(gè)有助于達(dá)成本課程目標(biāo)的建議。

1） 以貫通和綜合作為實(shí)踐課程建設(shè)的指導(dǎo)思想。

以貫通和綜合作為實(shí)踐課程建設(shè)的指導(dǎo)思想即凡是有益于學(xué)生理解數(shù)據(jù)庫(kù)設(shè)計(jì)與實(shí)現(xiàn)的內(nèi)容，都應(yīng)該串接起來(lái)。以展示SQL的解析與執(zhí)行為例，涉及的知識(shí)分散在編譯原理、SQL語(yǔ)法、數(shù)據(jù)結(jié)構(gòu)等課程中。一方面，國(guó)內(nèi)的編譯原理課程往往專注于概念和理論，學(xué)生學(xué)完后一般不會(huì)編程實(shí)現(xiàn)；另一方面學(xué)生的學(xué)習(xí)水平不同，這都需要將相關(guān)知識(shí)按照設(shè)計(jì)與實(shí)現(xiàn)的思路重新整合在一起。

應(yīng)對(duì)此挑戰(zhàn)的基本思路：首先將學(xué)生已經(jīng)學(xué)習(xí)過(guò)的編程技術(shù)（數(shù)學(xué)表達(dá)式的直接計(jì)算）進(jìn)行擴(kuò)展，介紹基于語(yǔ)法構(gòu)建數(shù)學(xué)表達(dá)式的AST（abstract syntax tree，抽象語(yǔ)法樹）結(jié)構(gòu)的編程技巧；之后借助這一擴(kuò)展的技巧講解SQL的解析與執(zhí)行。

2）有效利用開源項(xiàng)目，直觀展示和剖析代碼。

在比較許多開源的數(shù)據(jù)庫(kù)管理系統(tǒng)[6-9]后，建議選擇HyperSQL作為本課程代碼閱讀和調(diào)試的樣例。因?yàn)镠yperSQL是“純”Java，代碼量相對(duì)較小，而且它能夠支持現(xiàn)代數(shù)據(jù)庫(kù)管理系統(tǒng)的主要特征，如對(duì)并發(fā)訪問(wèn)的支持（H2不支持多線程）、MVCC（Derby不支持MVCC），甚至是嵌入式運(yùn)行方式等。

3）激勵(lì)學(xué)生互助學(xué)習(xí)。

在介紹背景知識(shí)后，將相關(guān)的知識(shí)點(diǎn)進(jìn)行分解，鼓勵(lì)學(xué)生組團(tuán)調(diào)研和編程實(shí)踐并在班上作報(bào)告。能否調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，是決定課程建設(shè)好壞的根本。在課程建設(shè)中，嘗試激勵(lì)學(xué)生利用互助學(xué)習(xí)的方式，即教師在負(fù)責(zé)介紹相關(guān)的背景知識(shí)以及所設(shè)定項(xiàng)目需要的必要編程技巧后，鼓勵(lì)學(xué)生上講臺(tái)向其他同學(xué)作報(bào)告展示其所完成的項(xiàng)目。這樣不僅有助于鍛煉學(xué)生的自學(xué)能力，而且有助于提升學(xué)生組織內(nèi)容和報(bào)告的能力。此外，學(xué)生間的交流有時(shí)更容易抓住學(xué)生的理解盲點(diǎn)：學(xué)生彼此之間的知識(shí)水平相近，某學(xué)生不明白的，極有可能也是其他同學(xué)所不了解的。

4 課程建設(shè)

在初步確定課程的指導(dǎo)思路后，還需要確定課程的專題內(nèi)容。在梳理專題的過(guò)程中，也要盡量做到兩點(diǎn)：一方面要對(duì)收集到的資料進(jìn)行匯總和提煉，將有價(jià)值的內(nèi)容組織到講義中；另一方面要反復(fù)思考和設(shè)計(jì)項(xiàng)目的內(nèi)容，希望項(xiàng)目既有助于理解數(shù)據(jù)庫(kù)管理系統(tǒng)核心功能，又不要超出學(xué)生的能力太遠(yuǎn)。

4.1 相關(guān)的專題概述

深入淺出地展示SQL的解析與執(zhí)行，是本課程的重點(diǎn)和難點(diǎn)。我們以SQL的解析與執(zhí)行為例，展示如何做到內(nèi)容的“按需拿來(lái)”和提煉。

一般數(shù)據(jù)庫(kù)課程可能會(huì)介紹圖2所示的SQL的處理流程，即SQL語(yǔ)句一般經(jīng)過(guò)3個(gè)環(huán)節(jié)：解析（parser）、重寫（re-writing）和物理計(jì)劃（physical query plan）的構(gòu)建，完成從SQL語(yǔ)句到最終的可運(yùn)行的執(zhí)行序列的轉(zhuǎn)換，即SQL樣例→Parse Tree（解析樹）→Logical Plan （邏輯計(jì)劃）→Physical Query Plan（物理查詢計(jì)劃），但對(duì)應(yīng)的代碼到底是怎樣的，往往語(yǔ)焉不詳。針對(duì)此問(wèn)題，采取間接理解的技巧，并在給學(xué)生提供必要的工具后，讓學(xué)生較為輕松地理解SQL的解析與執(zhí)行。

（1）間接理解。以數(shù)學(xué)表達(dá)式的解析與執(zhí)行代碼為例，幫助學(xué)生了解如何編程實(shí)現(xiàn)從給定的語(yǔ)法構(gòu)建對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)（編譯原理中往往將此數(shù)據(jù)結(jié)構(gòu)成為AST，SQL對(duì)應(yīng)的是解析樹）。之后，SQL的解析與執(zhí)行就可以借助數(shù)學(xué)表達(dá)式的處理來(lái)展示，因?yàn)閺腟QL到其實(shí)際執(zhí)行是通過(guò)兩次類似的轉(zhuǎn)換步驟得到，也就是圖2中右側(cè)4層所表達(dá)的：第1層SQL轉(zhuǎn)換為第2層的解析樹；解析樹又通過(guò)遍歷生成第3層的關(guān)系表達(dá)式（之所以有兩種關(guān)系表達(dá)式，是為了體現(xiàn)等價(jià)表達(dá)式的意思）；優(yōu)化后的關(guān)系表達(dá)式再轉(zhuǎn)換為第4層的物理計(jì)劃；最后，遍歷物理計(jì)劃過(guò)程中執(zhí)行相應(yīng)的文件和數(shù)據(jù)操作即可完成SQL的實(shí)際執(zhí)行。

（2）在有了（1）中的理解后，進(jìn)一步通過(guò)兩個(gè)環(huán)節(jié)加深學(xué)生的理解。一是在給學(xué)生介紹一些現(xiàn)成的工具（如Lex+Yacc[10-11]、CUP （Construction of Useful Parsers）+Flex[12-13]、ANTLR[14]等 ）后，要求學(xué)生嘗試使用；二是設(shè)定項(xiàng)目要求學(xué)生閱讀和調(diào)試HyperSQL中解析與執(zhí)行SQL的代碼。

從學(xué)生的反饋看，一是學(xué)生確實(shí)對(duì)這部分內(nèi)容很感興趣，二是學(xué)生很有興致嘗試和理解SQL的解析與執(zhí)行。

4.2 課程項(xiàng)目的設(shè)計(jì)

為有效促進(jìn)學(xué)生的實(shí)踐，可設(shè)計(jì)如下有針對(duì)性的項(xiàng)目。

圖2 SQL解析與執(zhí)行的示意：處理流程和相關(guān)數(shù)據(jù)結(jié)構(gòu)

（1）B+-樹索引文件的設(shè)計(jì)與實(shí)現(xiàn)。雖然數(shù)據(jù)結(jié)構(gòu)課程肯定介紹B+-樹的概念和算法，但實(shí)現(xiàn)的是內(nèi)存版本。此項(xiàng)目要求將索引結(jié)構(gòu)保存在文件中，因此需要考慮很多內(nèi)存版本不會(huì)涉及的挑戰(zhàn)，如內(nèi)外存存取的時(shí)間差可能導(dǎo)致索引的不一致性問(wèn)題、如何保證數(shù)據(jù)和索引間保持高效的同步更新等。

（2）線程池對(duì)并發(fā)用戶響應(yīng)的仿真。在給出線程中嵌入網(wǎng)絡(luò)技術(shù)的代碼架構(gòu)后，要求學(xué)生完成線程池的仿真，既幫助學(xué)生了解這種編程技巧，又有助于學(xué)生后續(xù)分析和調(diào)試HyperSQL的代碼。

（3）鎖表的仿真。鎖表是數(shù)據(jù)庫(kù)管理系統(tǒng)用于監(jiān)管對(duì)數(shù)據(jù)進(jìn)行并發(fā)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，基于鎖表，再結(jié)合相應(yīng)的訪問(wèn)控制協(xié)議/機(jī)制才能保證數(shù)據(jù)的一致性。在第二輪實(shí)踐中，此項(xiàng)目選取的是數(shù)據(jù)庫(kù)理論課都會(huì)講到的二段鎖（2 phased lock: 2PL）協(xié)議。

此外，課堂上也介紹了其他協(xié)議，如MVCC（multiple version concurrency control，多版本并發(fā)控制）、Snapshot等，但并沒有要求學(xué)生去了解，欣喜的是第二輪中有部分學(xué)生自主地調(diào)研和了解了這些協(xié)議。

（4）數(shù)學(xué)表達(dá)式的解析和SQL解析樹的構(gòu)建（可借助已有的工具）。此項(xiàng)目要求學(xué)生實(shí)現(xiàn)數(shù)學(xué)表達(dá)式到AST數(shù)據(jù)結(jié)構(gòu)的程序，從中體會(huì)如何基于給定的語(yǔ)法實(shí)現(xiàn)簡(jiǎn)版的解析器。在此基礎(chǔ)上，介紹SQL解析與執(zhí)行的內(nèi)容，包括從解析樹到關(guān)系表達(dá)式的轉(zhuǎn)換以及基于關(guān)系代數(shù)變換規(guī)律構(gòu)造等價(jià)的形式，并從中選擇執(zhí)行效率最高的PQP來(lái)執(zhí)行實(shí)際的數(shù)據(jù)查詢操作。

（5）HyperSQL的初步調(diào)試，通過(guò)引入HyperSQL源代碼，讓學(xué)生初步感受高水平Java編程的面貌，并初步了解理論部分的概念在HyperSQL中的實(shí)現(xiàn)，如HyperSQL中使用的是Java 的線程組（Java thread group）應(yīng)對(duì)多用戶的并發(fā)訪問(wèn)，鎖表的實(shí)現(xiàn)是使用了對(duì)應(yīng)讀、寫鎖的哈希圖（hashmap）等。

（6）使用JSP（Java server pages）和HyperSQL實(shí)現(xiàn)Web 項(xiàng)目開發(fā)。

此項(xiàng)目是教學(xué)大綱中強(qiáng)調(diào)的環(huán)節(jié)，幫助學(xué)生體會(huì)“數(shù)據(jù)庫(kù)+Web”的開發(fā)方式，這是當(dāng)前非常流行的軟件開發(fā)技術(shù)，可以說(shuō)是學(xué)生就業(yè)必備的開發(fā)技能。

（7）閱讀和調(diào)試HyperSQL，以了解SQL的執(zhí)行以及對(duì)事務(wù)概念的支持。此項(xiàng)目要求學(xué)生能夠深入調(diào)試HyperSQL代碼，了解其代碼架構(gòu)。實(shí)踐證明，在前述專題的基礎(chǔ)上，絕大多數(shù)學(xué)生可以嘗試著走通一條SQL語(yǔ)句在HyperSQL內(nèi)的解析和執(zhí)行流程。

5 結(jié)語(yǔ)

北京交通大學(xué)軟件學(xué)院自2015年便嘗試開設(shè)數(shù)據(jù)庫(kù)管理系統(tǒng)綜合實(shí)踐課程，在此過(guò)程中做了深入的思考和梳理，概括為如下3點(diǎn)建議：①?gòu)脑O(shè)計(jì)與實(shí)現(xiàn)的角度將分散在其他課程中的必要知識(shí)點(diǎn)融會(huì)貫通于此課程；②借助剖析源代碼幫助學(xué)生體會(huì)將那些概念轉(zhuǎn)化為程序的編程技巧；③嘗試互助學(xué)習(xí)教學(xué)方式，讓學(xué)生就所分派的項(xiàng)目作調(diào)研、編程實(shí)踐，并在課上作專題報(bào)告，這既能促使他們自主調(diào)研相關(guān)資料和技術(shù)，又能鍛煉他們整理和提煉資料甚至是表達(dá)的能力。

學(xué)校已完成兩輪的授課實(shí)踐，在第一輪的基礎(chǔ)上，第二輪實(shí)踐有更深入的修改，實(shí)踐效果良好，不僅表現(xiàn)為學(xué)生對(duì)所講授的知識(shí)點(diǎn)能夠有所領(lǐng)悟，而且學(xué)生也很有興趣親手調(diào)試和完成相關(guān)的項(xiàng)目，普遍反映有將以前所學(xué)知識(shí)融會(huì)貫通的感覺。