孔令波
(北京交通大學(xué) 軟件學(xué)院,北京 100044)
作為經(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)深入淺出地展示出來。
圖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>
幫助學(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é)所不了解的。
在初步確定課程的指導(dǎo)思路后,還需要確定課程的專題內(nèi)容。在梳理專題的過程中,也要盡量做到兩點:一方面要對收集到的資料進(jìn)行匯總和提煉,將有價值的內(nèi)容組織到講義中;另一方面要反復(fù)思考和設(shè)計項目的內(nèi)容,希望項目既有助于理解數(shù)據(jù)庫管理系統(tǒng)核心功能,又不要超出學(xué)生的能力太遠(yuǎ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í)行。
為有效促進(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í)行流程。
北京交通大學(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é)知識融會貫通的感覺。