貫通與綜合：數據庫實踐課程教學建設的思考

孔令波

（北京交通大學 軟件學院，北京 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點建議：①從設計與實現的角度將分散在其他課程中的必要知識點融會貫通于此課程；②借助剖析源代碼幫助學生體會將那些概念轉化為程序的編程技巧；③嘗試互助學習教學方式，讓學生就所分派的項目作調研、編程實踐，并在課上作專題報告，這既能促使他們自主調研相關資料和技術，又能鍛煉他們整理和提煉資料甚至是表達的能力。

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