貫通與綜合：數(shù)據(jù)庫實踐課程教學(xué)建設(shè)的思考

孔令波

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 課程建設(shè)

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

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

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

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

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

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

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

4.2 課程項目的設(shè)計

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

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

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

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

（3）鎖表的仿真。鎖表是數(shù)據(jù)庫管理系統(tǒng)用于監(jiān)管對數(shù)據(jù)進(jìn)行并發(fā)訪問的數(shù)據(jù)結(jié)構(gòu)，基于鎖表，再結(jié)合相應(yīng)的訪問控制協(xié)議/機制才能保證數(shù)據(jù)的一致性。在第二輪實踐中，此項目選取的是數(shù)據(jù)庫理論課都會講到的二段鎖（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)建（可借助已有的工具）。此項目要求學(xué)生實現(xiàn)數(shù)學(xué)表達(dá)式到AST數(shù)據(jù)結(jié)構(gòu)的程序，從中體會如何基于給定的語法實現(xiàn)簡版的解析器。在此基礎(chǔ)上，介紹SQL解析與執(zhí)行的內(nèi)容，包括從解析樹到關(guān)系表達(dá)式的轉(zhuǎn)換以及基于關(guān)系代數(shù)變換規(guī)律構(gòu)造等價的形式，并從中選擇執(zhí)行效率最高的PQP來執(zhí)行實際的數(shù)據(jù)查詢操作。

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

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

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

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

5 結(jié)語

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

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