數(shù)據(jù)庫(kù)模式匹配：一種查詢逆向工程方法

劉履宏 何震瀛 荊一楠

1(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) 2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)

0 引 言

在大數(shù)據(jù)時(shí)代，用戶對(duì)數(shù)據(jù)公開(kāi)、數(shù)據(jù)共享與數(shù)據(jù)融合等的需求越來(lái)越迫切。數(shù)據(jù)庫(kù)模式匹配(Database schema mapping)作為解決這些問(wèn)題的一個(gè)有效手段，成為數(shù)據(jù)庫(kù)領(lǐng)域一個(gè)重要的研究問(wèn)題[1]。

數(shù)據(jù)庫(kù)模式匹配通過(guò)在數(shù)據(jù)庫(kù)模式之間建立映射關(guān)系，幫助用戶實(shí)現(xiàn)從源數(shù)據(jù)模式到目標(biāo)數(shù)據(jù)模式的轉(zhuǎn)換。傳統(tǒng)的模式匹配技術(shù)[2-7]將兩個(gè)異構(gòu)數(shù)據(jù)源作為輸入，根據(jù)數(shù)據(jù)源的元信息或是數(shù)據(jù)實(shí)例對(duì)數(shù)據(jù)源的模式進(jìn)行匹配。在對(duì)數(shù)據(jù)源進(jìn)行匹配的過(guò)程中，使用的是基于屬性相似度的方法[4-7]。在得到可能的匹配后，用戶需要人為指定哪些匹配是用戶真正想要的。

圖1為一個(gè)整合圖書(shū)數(shù)據(jù)源的例子，給定需要做模式匹配的數(shù)據(jù)源SBook和TBook(假定SBook是源數(shù)據(jù)模式，TBook是目標(biāo)數(shù)據(jù)模式)，用戶需要將源數(shù)據(jù)模式SBook映射到目標(biāo)數(shù)據(jù)模式TBook。傳統(tǒng)的模式匹配方法通過(guò)語(yǔ)義學(xué)或者是統(tǒng)計(jì)學(xué)等方法計(jì)算SBook和TBook不同屬性之間的相似度從而得到SBook和TBook之間的可能匹配，但是這些匹配仍然需要用戶再次檢查以確保匹配的準(zhǔn)確性。這不僅要求用戶對(duì)兩個(gè)數(shù)據(jù)源都很了解，而且費(fèi)時(shí)費(fèi)力(真實(shí)場(chǎng)景可能要比給出的示例復(fù)雜得多)。

圖1 示例源數(shù)據(jù)模式和目標(biāo)數(shù)據(jù)模式

查詢逆向工程技術(shù)為數(shù)據(jù)庫(kù)模式匹配提供了新的思路。給出如圖2所示的源數(shù)據(jù)庫(kù)SBook，有兩張表Book和Author。在Book中，a_id是其主鍵，其余四列依次為書(shū)籍名稱name、出版社publisher、連接Author的外鍵f_id、評(píng)論comment；在Author中，a_id是主鍵，其余兩列依次是作者名稱author和作者國(guó)籍from。用戶可根據(jù)TBook的數(shù)據(jù)模式，提供來(lái)自源數(shù)據(jù)庫(kù)SBook的實(shí)例，構(gòu)成實(shí)例表，如表1所示。然后通過(guò)查詢逆向工程的方式得到生成這些實(shí)例的SPJ查詢。在這些查詢的投影(projection)列和其對(duì)應(yīng)的實(shí)例表列之間構(gòu)建映射關(guān)系，即可獲得實(shí)例表列和SBook列之間的匹配，也就是TBook和SBook之間的模式匹配。通過(guò)查詢逆向工程的方法獲得的模式匹配，可以確保用戶提供的每一行實(shí)例數(shù)據(jù)的內(nèi)部具有邏輯一致性，即實(shí)例表中的每一行數(shù)據(jù)要么來(lái)自SBook的某一張表的同一個(gè)元組，要么來(lái)自SBook不同表的元組，而且這些元組根據(jù)SBook的主外鍵關(guān)系可以連接(join)。

圖2 源數(shù)據(jù)庫(kù)SBook

表1 實(shí)例表

這種基于實(shí)例的模式匹配以實(shí)例表和源數(shù)據(jù)庫(kù)為輸入，可以幫助用戶提供確切的模式匹配結(jié)果。用戶只需要提供上述實(shí)例表和源數(shù)據(jù)庫(kù)，并不需要用戶對(duì)源數(shù)據(jù)庫(kù)有任何了解。

查詢逆向工程(Query Reverse Engineering，QRE)技術(shù)[8-10]和上文描述的基于實(shí)例的模式匹配技術(shù)相關(guān)。QRE技術(shù)根據(jù)實(shí)例表和對(duì)應(yīng)數(shù)據(jù)庫(kù)可以求解出從數(shù)據(jù)庫(kù)得到給定實(shí)例的查詢。盡管QRE技術(shù)不是直接用來(lái)解決模式匹配問(wèn)題的，但是從QRE求解到的查詢可以用來(lái)獲得給定實(shí)例表列和數(shù)據(jù)庫(kù)列之間的映射關(guān)系，從而確定源數(shù)據(jù)模式和目標(biāo)數(shù)據(jù)模式之間的匹配。但使用QRE技術(shù)來(lái)求解基于實(shí)例的模式匹配問(wèn)題也有不足之處。QRE中的一些過(guò)程在模式匹配問(wèn)題中是不必要的，這些不必要的計(jì)算過(guò)程給模式匹配問(wèn)題帶來(lái)了更大的優(yōu)化空間。

據(jù)此，本文提出了基于查詢逆向工程的模式匹配方法。本文的主要貢獻(xiàn)在于：(1)形式化定義了基于查詢逆向工程的模式匹配問(wèn)題。(2)以查詢逆向工程方法為基礎(chǔ)，提出基于行的模式匹配方法，繼而提出基于重用和基于列的優(yōu)化算法?；谥赜玫哪Ｊ狡ヅ渫ㄟ^(guò)對(duì)之前結(jié)果的重用實(shí)現(xiàn)效率的優(yōu)化；基于列的模式匹配以實(shí)例表中的列為基本單元做計(jì)算，即使處理多行實(shí)例數(shù)據(jù)也能保證運(yùn)行效率。(3)本文在IMDB數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn)對(duì)本文提出的三種方法做了對(duì)比。實(shí)驗(yàn)證明了基于重用和基于列的優(yōu)化方法的高效性。

1 相關(guān)研究

1.1 模式匹配

模式匹配技術(shù)[2-7]被用以匹配異構(gòu)數(shù)據(jù)源的模式，確定不同數(shù)據(jù)源的屬性之間的映射關(guān)系。模式匹配技術(shù)在數(shù)據(jù)整合、數(shù)據(jù)公開(kāi)、數(shù)據(jù)共享、數(shù)據(jù)起源等領(lǐng)域起著至關(guān)重要的作用[11]。傳統(tǒng)的模式匹配方法大體可以分為基于元數(shù)據(jù)的匹配[2,4]和基于實(shí)例的匹配[5-7]。在基于元數(shù)據(jù)的模式匹配中，算法利用數(shù)據(jù)源模式的元數(shù)據(jù)來(lái)構(gòu)建源數(shù)據(jù)屬性和目標(biāo)數(shù)據(jù)屬性之間的映射關(guān)系。基于實(shí)例的模式匹配使用統(tǒng)計(jì)學(xué)、文本分析或者機(jī)器學(xué)習(xí)方法計(jì)算數(shù)據(jù)源屬性之間的相似性。無(wú)論是基于數(shù)據(jù)源模式元數(shù)據(jù)的方法還是基于實(shí)例的方法，本質(zhì)上都是基于相似度的方法，在計(jì)算得到數(shù)據(jù)源之間的匹配之后仍需用戶確認(rèn)這些匹配的正確性，而且基于實(shí)例的方法忽略了用戶給定實(shí)例中在同一行的數(shù)據(jù)的內(nèi)部邏輯關(guān)聯(lián)。QuickMig[3]雖然使用用戶提供的樣例來(lái)輔助構(gòu)建數(shù)據(jù)源模式之間的映射，但是QuickMig和基于相似度的模式匹配方法在本質(zhì)上沒(méi)有區(qū)別，它并沒(méi)有考慮用戶構(gòu)建的實(shí)例中的數(shù)據(jù)內(nèi)部的邏輯關(guān)聯(lián)。

1.2 查詢逆向工程

本文工作和查詢逆向工程(QRE)[8-10]相關(guān)。QRE在給定數(shù)據(jù)樣例和數(shù)據(jù)庫(kù)的情況下，找出可以生成給定數(shù)據(jù)樣例的查詢。然而模式匹配問(wèn)題的目標(biāo)是得到不同模式之間的匹配關(guān)系。盡管可以使用QRE技術(shù)逆向出生成給定數(shù)據(jù)樣例的查詢，再基于這些查詢抽取出給定樣例表列和數(shù)據(jù)庫(kù)列之間的匹配關(guān)系，從而得到數(shù)據(jù)庫(kù)模式匹配，但是從QRE逆向出來(lái)的不同查詢可能對(duì)應(yīng)著相同的模式匹配關(guān)系，不做改動(dòng)地使用QRE技術(shù)做模式匹配會(huì)造成不必要的計(jì)算，增加運(yùn)行成本。Shen等[9]的工作是QRE技術(shù)的一個(gè)代表，在給定樣例和數(shù)據(jù)庫(kù)的情況下，找出生成給定樣例的SPJ查詢。雖然他們已經(jīng)做了查詢逆向工程的執(zhí)行優(yōu)化，但用作模式匹配卻依然有很大的優(yōu)化空間。

2 問(wèn)題定義

記用戶給定的實(shí)例表為I，I的第j列為I·cj。對(duì)于實(shí)例表中的某一行數(shù)據(jù)ri∈I在列I·cj上的數(shù)據(jù)項(xiàng)，記為ri[I·cj]。

給定關(guān)系型數(shù)據(jù)庫(kù)G，在其對(duì)應(yīng)的模式圖(Schema Graph)中，關(guān)系表可以被視為一組節(jié)點(diǎn)V，表與表之間的主外鍵關(guān)系連接為一組邊E。關(guān)系表Rm中的第n列記為Rm·cn。實(shí)例表I中的實(shí)例數(shù)據(jù)由數(shù)據(jù)庫(kù)G經(jīng)SPJ查詢得到。如果在列Rm·cn中有任何值等于ri[I·cj]，則記為ri[I·cj]∈Rm·cn。例如表1中數(shù)據(jù)項(xiàng)r1[I·C1]Harry Potter出現(xiàn)在圖2所示源數(shù)據(jù)庫(kù)的列R1·c2(Book·name)中，即記r1[I·c1]∈R1·c2。

表2 實(shí)例表中的列匹配

記Rm的列集合為Col(Rm)，I的列集合為Col(I)。定義實(shí)例關(guān)系如下：

實(shí)例關(guān)系和中間關(guān)系的連接方式通過(guò)構(gòu)造查詢計(jì)劃樹(shù)來(lái)表示。實(shí)例關(guān)系和中間關(guān)系構(gòu)成查詢計(jì)劃樹(shù)中的節(jié)點(diǎn)。如果查詢計(jì)劃樹(shù)的節(jié)點(diǎn)之間存在一條邊，那么他們所對(duì)應(yīng)的關(guān)系表在數(shù)據(jù)庫(kù)G中一定有一條表示主外鍵關(guān)系的邊。為了避免無(wú)效和重復(fù)，查詢計(jì)劃樹(shù)應(yīng)滿足以下條件:

3)查詢計(jì)劃樹(shù)中的葉子節(jié)點(diǎn)不能為中間關(guān)系Rm〈?〉。

一個(gè)查詢計(jì)劃樹(shù)T代表著一個(gè)查詢，T中的節(jié)點(diǎn)表示子查詢，邊表示連接。執(zhí)行T代表的查詢，可以得到一張結(jié)果表(T)。給定一個(gè)數(shù)據(jù)行ri∈I，記其對(duì)應(yīng)的一個(gè)列匹配組合所能產(chǎn)生的查詢計(jì)劃樹(shù)集合為定義查詢計(jì)劃如下:

定義4查詢計(jì)劃。給定一個(gè)查詢計(jì)劃樹(shù)T∈其對(duì)應(yīng)的數(shù)據(jù)行是ri∈I，列匹配組合是則查詢計(jì)劃

3 基于QRE方法的模式匹配及優(yōu)化方法

本文提出了基于QRE方法的模式匹配方法。首先基于問(wèn)題定義給出了基于行的模式匹配，對(duì)實(shí)例表的每個(gè)行求解出模式匹配集合，相交得到最終的結(jié)果集。然后在基于行的模式匹配方法的基礎(chǔ)上，提出了基于重用的模式匹配方法，在求解下一行的模式匹配時(shí)，利用前一個(gè)行的模式匹配的結(jié)果。最后提出了同時(shí)處理多行實(shí)例數(shù)據(jù)的基于列的模式匹配方法。

3.1 基于行的模式匹配

基于問(wèn)題定義，提出基于行的模式匹配方法，具體算法如算法1所示。

算法1基于行的模式匹配方法

輸入：實(shí)例表I和源數(shù)據(jù)庫(kù)G。

輸出：模式匹配Δ。

1. For eachri∈Ido

2.Δi←?

3. 在G中搜索ri，并且枚舉列匹配組合集合Φi

6. If ?T∈

8. End If

9. End For

10. End For

11.Δ=∩Δi

12. ReturnΔ

基于行的模式匹配方法包含4個(gè)步驟：1)在數(shù)據(jù)庫(kù)中搜索實(shí)例表中的每行數(shù)據(jù)得出相應(yīng)的列匹配組合；2)對(duì)每個(gè)列匹配組合，生成查詢計(jì)劃樹(shù)集合；3)由查詢計(jì)劃樹(shù)得到查詢計(jì)劃，執(zhí)行查詢計(jì)劃，驗(yàn)證列匹配組合的合法性，得到合法的模式匹配集合；4)將實(shí)例表中每行數(shù)據(jù)對(duì)應(yīng)的合法模式匹配集合相交得到最終結(jié)果。

在數(shù)據(jù)庫(kù)中搜索實(shí)例表中的數(shù)據(jù)項(xiàng)時(shí)，本文使用的是相等關(guān)系，用戶可以設(shè)定自己需要的關(guān)系，比如用戶若只能在實(shí)例表中提供書(shū)籍作者的姓氏，就可以使用數(shù)據(jù)庫(kù)中的CONTAINS方法來(lái)處理包含關(guān)系。

算法2查詢計(jì)劃樹(shù)生成

2. 將所有的實(shí)例關(guān)系節(jié)點(diǎn)初始化為候選查詢計(jì)劃樹(shù)隊(duì)列Q，初始化查詢計(jì)劃樹(shù)結(jié)果集合

3. WhileQ≠? do

4.CurTree←Q.pop()

7. End If

8. For eachnode∈nodeListdo CurTree

9. For eachnode′∈CurTreedo

10. Ifnode和node′可以連接then

11. 將node連接到CurTree的node′，并且生成新的候選查詢計(jì)劃樹(shù)CurTree′

13. 丟棄CurTree′

14. Else

15.Q.add(CurTree′)

16. End If

17. End If

18. End For

19. End For

20. End While

每一棵查詢計(jì)劃樹(shù)都可以被翻譯為一個(gè)具體查詢。查詢計(jì)劃樹(shù)中的邊代表連接(join)方式，實(shí)例關(guān)系節(jié)點(diǎn)可以被轉(zhuǎn)換為帶有WHERE條件的子查詢，中間關(guān)系節(jié)點(diǎn)可以被轉(zhuǎn)換為沒(méi)有WHERE條件的子查詢。每棵查詢計(jì)劃樹(shù)都可以進(jìn)一步轉(zhuǎn)換為查詢計(jì)劃。如果執(zhí)行查詢計(jì)劃得到的結(jié)果表不為空，就代表著這個(gè)查詢計(jì)劃對(duì)應(yīng)的列匹配組合是合法有效的，可以得到合法模式匹配。為了提升效率，在將查詢計(jì)劃轉(zhuǎn)換為具體查詢時(shí)，在查詢后面加上“LIMIT 1”。

在驗(yàn)證某個(gè)列匹配組合的合法性時(shí)，一旦發(fā)現(xiàn)某個(gè)查詢計(jì)劃執(zhí)行結(jié)果非空，就將該列匹配組合標(biāo)記為合法，并輸出模式匹配，同時(shí)停止對(duì)后續(xù)查詢計(jì)劃的驗(yàn)證。因?yàn)閿?shù)據(jù)IO，在數(shù)據(jù)庫(kù)上執(zhí)行查詢代價(jià)很大，避免執(zhí)行不必要的查詢可以顯著提升運(yùn)行效率。

3.2 基于重用的模式匹配

基于行的模式匹配方法的最后一步，是將根據(jù)實(shí)例表不同行得到的模式匹配集合相交得到最終的模式匹配結(jié)果。任何兩個(gè)集合相交的結(jié)果不會(huì)超出相交前的任何一個(gè)集合。因此，在處理完一行數(shù)據(jù)之后，得到的模式匹配結(jié)果可以用作處理下一行數(shù)據(jù)時(shí)的列匹配搜索范圍。假設(shè)處理完某行數(shù)據(jù)ri之后得到的模式匹配集合是Δi，對(duì)樣例表中下一行數(shù)據(jù)ri+1在列I·cj上的數(shù)據(jù)項(xiàng)ri+1[I·cj]進(jìn)行列匹配搜索時(shí)，不需要搜索整個(gè)數(shù)據(jù)庫(kù)，只需要搜索Δi中I·cj在數(shù)據(jù)庫(kù)中的映射列。然后依次進(jìn)行查詢計(jì)劃樹(shù)生成和查詢計(jì)劃驗(yàn)證，最終得到ri+1的模式匹配集合。處理完樣例表中的所有數(shù)據(jù)行之后，將所有的模式匹配集合相交得到最終結(jié)果。

3.3 基于列的模式匹配

在基于行的方法和基于重用的方法中，隨著需要處理的數(shù)據(jù)行的增加，模式匹配的整體時(shí)間成本會(huì)成倍增加。增加的時(shí)間成本主要來(lái)自查詢計(jì)劃樹(shù)的生成和執(zhí)行。為了減少查詢計(jì)劃樹(shù)生成帶來(lái)的時(shí)間成本，本文提出一種基于列的模式匹配方法，在處理不同數(shù)據(jù)行時(shí)共享查詢計(jì)劃樹(shù)的結(jié)構(gòu)而不需要針對(duì)每一行數(shù)據(jù)都進(jìn)行一次查詢計(jì)劃樹(shù)生成。

在生成共享查詢計(jì)劃樹(shù)之前，先獲得不同數(shù)據(jù)行的公共列匹配。公共列匹配定義如下：

定義5公共列匹配。給定列I·cj∈Col(I)，實(shí)例表列I·cj中不同數(shù)據(jù)項(xiàng)ri[I·cj](?ri∈I)在數(shù)據(jù)庫(kù)G上的公共列匹配是Cj={I·cj?Rm·cn|?ri∈I,ri[I,·cj]∈Rm·cn}。

以表1的實(shí)例表和圖2源數(shù)據(jù)庫(kù)為例，列I·c1的公共列匹配C1={I·c1?R1·c2}，因?yàn)閷?shí)例表列I·c1的數(shù)據(jù)都出現(xiàn)在源數(shù)據(jù)庫(kù)的列R1·c2中。

公共列匹配組合被定義如下：

實(shí)現(xiàn)查詢計(jì)劃樹(shù)共享的核心思想是采用占位符的方式來(lái)保留查詢計(jì)劃樹(shù)結(jié)構(gòu)但是不具體指定數(shù)據(jù)行，為此提出占位符實(shí)例關(guān)系。

占位符實(shí)例關(guān)系代表一個(gè)參數(shù)化的查詢，需要在WHERE條件中填入具體的數(shù)據(jù)行才能實(shí)例化為具體的查詢。

占位符查詢計(jì)劃樹(shù)的生成過(guò)程只需將查詢計(jì)劃樹(shù)生成過(guò)程中的實(shí)例關(guān)系節(jié)點(diǎn)替換為占位符實(shí)例關(guān)系節(jié)點(diǎn)即可。把占位符查詢計(jì)劃樹(shù)轉(zhuǎn)換成具體的查詢計(jì)劃時(shí)，要將數(shù)據(jù)行ri∈I組裝到占位符查詢計(jì)劃樹(shù)中的占位符實(shí)例關(guān)系，填充上WHERE條件上的參數(shù)，實(shí)例化數(shù)據(jù)行參數(shù)。

基于列的模式匹配方法始終將實(shí)例表的數(shù)據(jù)列作為一個(gè)整體，從公共列匹配組合的獲取到占位符查詢計(jì)劃樹(shù)的生成都是以列為數(shù)據(jù)單元。只有在把占位符查詢計(jì)劃樹(shù)轉(zhuǎn)換成具體查詢計(jì)劃時(shí)才分開(kāi)處理每個(gè)數(shù)據(jù)行。這種方法避免了實(shí)例表中數(shù)據(jù)行增長(zhǎng)所帶來(lái)的數(shù)據(jù)搜索開(kāi)銷和查詢計(jì)劃樹(shù)生成開(kāi)銷。

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)環(huán)境

代碼基于Java 8實(shí)現(xiàn)。運(yùn)行過(guò)程中的內(nèi)存限制是8 GB。實(shí)驗(yàn)所用數(shù)據(jù)集為IMDB數(shù)據(jù)集，其包含大量的電影和評(píng)分?jǐn)?shù)據(jù)。IMDB數(shù)據(jù)集大小為3.7 GB，共有7張表。實(shí)驗(yàn)中使用MySQL5.7存儲(chǔ)數(shù)據(jù)。為了加速數(shù)據(jù)搜索的過(guò)程，本文給數(shù)據(jù)庫(kù)的列建立了索引。

4.2 實(shí)驗(yàn)參數(shù)

查詢計(jì)劃樹(shù)的最大大小(MaxSize)和用戶給定實(shí)例表的列數(shù)量影響著本文方法的性能。在實(shí)驗(yàn)中對(duì)這兩個(gè)參數(shù)設(shè)定不同的值。MaxSize取值3、4、5，默認(rèn)大小為4；實(shí)例表列數(shù)量取值3、4、5，默認(rèn)大小為4。為了研究各方法在實(shí)例表中有不同數(shù)量數(shù)據(jù)行時(shí)的表現(xiàn)，在不同行數(shù)量下進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)中實(shí)例表的數(shù)據(jù)行數(shù)量取為1、5、10，默認(rèn)數(shù)量為5。

實(shí)驗(yàn)中的實(shí)例表從IMDB數(shù)據(jù)集中隨機(jī)采樣生成。每一行實(shí)例數(shù)據(jù)都可以被某個(gè)查詢生成。每組參數(shù)下都隨機(jī)采樣出15個(gè)實(shí)例表，實(shí)驗(yàn)結(jié)果數(shù)據(jù)取15組實(shí)驗(yàn)的平均值。

4.3 性能分析

(1)不同MaxSize下的性能比較。為研究查詢計(jì)劃樹(shù)的最大大小MaxSize對(duì)本文三種方法的影響，實(shí)驗(yàn)比較了不同MaxSize值下不同方法的運(yùn)行時(shí)間，結(jié)果如圖3所示，“row”表示基于行的模式匹配，“reuse”表示基于重用的模式匹配，“column”表示基于列的模式匹配。

圖3 不同MaxSize下的運(yùn)行時(shí)間

可以看出，隨著MaxSize的增大，三種方法的運(yùn)行時(shí)間都會(huì)增加。查詢計(jì)劃樹(shù)最大大小MaxSize決定了查詢計(jì)劃樹(shù)的生成數(shù)量，MaxSize越大，生成的查詢計(jì)劃樹(shù)越多，需要執(zhí)行的查詢計(jì)劃也就越多，運(yùn)行時(shí)間就會(huì)增加。在不同的MaxSize下，三種方法中始終是基于行的方法運(yùn)行時(shí)間最長(zhǎng)，其次是基于重用的方法，基于列的方法運(yùn)行時(shí)間最短?；谛械哪Ｊ狡ヅ浞绞降倪\(yùn)行時(shí)間是基于重用的模式匹配方法運(yùn)行時(shí)間的3～5倍，是基于列的模式匹配方法運(yùn)行時(shí)間的10倍左右。這是因?yàn)榛谛械哪Ｊ狡ヅ浞椒▽?duì)每個(gè)數(shù)據(jù)行都需要在整個(gè)數(shù)據(jù)庫(kù)搜索數(shù)據(jù)、生成查詢計(jì)劃樹(shù)并且執(zhí)行查詢計(jì)劃?；谥赜玫哪Ｊ狡ヅ浞椒ㄖ赜昧饲懊娴哪Ｊ狡ヅ浣Y(jié)果，縮小了數(shù)據(jù)搜索的范圍，但是在處理每個(gè)數(shù)據(jù)行的時(shí)候仍需要重新生成所有的查詢計(jì)劃樹(shù)?；诹械哪Ｊ狡ヅ浞椒▽⒄麄€(gè)實(shí)例表中的列視為一個(gè)整體，只生成一次查詢計(jì)劃樹(shù)，降低了查詢計(jì)劃樹(shù)生成成本。同時(shí)，公共列匹配組合的使用減少了查詢計(jì)劃樹(shù)的生成，降低了查詢計(jì)劃的數(shù)量，降低了運(yùn)行成本。

(2)不同列數(shù)量下的性能比較。實(shí)驗(yàn)通過(guò)改變實(shí)例表中的列數(shù)量來(lái)研究其對(duì)三個(gè)方法運(yùn)行時(shí)間的影響，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 不同列數(shù)量下的運(yùn)行時(shí)間

可以看出，實(shí)驗(yàn)運(yùn)行時(shí)間隨著列數(shù)量的增加而增長(zhǎng)。列數(shù)量增加之后，列匹配組合的數(shù)量會(huì)增加。此外，列匹配組合中的列增多了之后，生成查詢計(jì)劃樹(shù)輸入的實(shí)例關(guān)系節(jié)點(diǎn)會(huì)增加，每一個(gè)列匹配組合生成的查詢計(jì)劃樹(shù)數(shù)量隨之增長(zhǎng)。最終需要執(zhí)行的查詢計(jì)劃數(shù)量增多，執(zhí)行時(shí)間加長(zhǎng)。在不同的列數(shù)量下，基于行的方法、基于重用的方法和基于列的方法的執(zhí)行時(shí)間依次變短。基于行的方法用時(shí)是基于重用的方法用時(shí)的3～5倍，是基于列的方法用時(shí)的6～10倍。

(3)不同行數(shù)量下的性能比較。為了比較三種方法處理不同數(shù)量數(shù)據(jù)行時(shí)的效率，在不同行數(shù)量下進(jìn)行了實(shí)驗(yàn)，各方法運(yùn)行時(shí)間如圖5所示。

圖5 不同行數(shù)量下的運(yùn)行時(shí)間

當(dāng)行數(shù)量為1時(shí)，三種方法所用時(shí)間基本相同，這符合文中方法設(shè)計(jì)原理。隨著行數(shù)量增加，基于行的方法運(yùn)行時(shí)間成倍增長(zhǎng)，因?yàn)樵诖朔椒ㄖ袑?duì)每一行數(shù)據(jù)的處理過(guò)程完全相同，所以數(shù)據(jù)行數(shù)量的成倍增加會(huì)造成運(yùn)行時(shí)間的成本增長(zhǎng)?；谥赜玫姆椒ㄋ脮r(shí)間隨著數(shù)據(jù)行數(shù)量的增長(zhǎng)緩慢增長(zhǎng)。每次數(shù)據(jù)行的數(shù)據(jù)搜索范圍來(lái)自上一個(gè)數(shù)據(jù)行的模式匹配結(jié)果，這不僅會(huì)減少數(shù)據(jù)搜索時(shí)間，也會(huì)減少列匹配組合的數(shù)目，從而減少需要執(zhí)行的查詢數(shù)量?；诹械姆椒ㄔ谛袛?shù)量為1的時(shí)候用時(shí)為3 214 ms，在行數(shù)量為5和10的時(shí)候用時(shí)為1 500 ms左右，是行數(shù)量為1時(shí)用時(shí)的一半。在生成查詢計(jì)劃樹(shù)之前，基于列的方法將各個(gè)數(shù)據(jù)行的列匹配相交得到公共列匹配，行數(shù)量增加時(shí)，公共列匹配會(huì)減少，則公共列匹配組合會(huì)減少，生成的查詢計(jì)劃樹(shù)數(shù)量也隨之降低。因此，隨著行數(shù)量的增加，基于列的方法所用時(shí)間反而降低。

通過(guò)以上實(shí)驗(yàn)可得，提出的基于重用和基于列的優(yōu)化方法在不同最大大小和不同列數(shù)量下都有很好的效率，基于列的模式匹配方法表現(xiàn)最好。相比于基于行的模式匹配方法和基于重用的模式匹配方法，基于列的模式匹配方法即使在行數(shù)量較多的情況下也有很好的表現(xiàn)，能夠處理多行數(shù)據(jù)的情況。

5 結(jié) 語(yǔ)

數(shù)據(jù)庫(kù)模式匹配在數(shù)據(jù)共享、數(shù)據(jù)公開(kāi)等領(lǐng)域起著至關(guān)重要的作用。本文通過(guò)查詢逆向工程的方法，根據(jù)用戶提供的符合目標(biāo)模式的實(shí)例數(shù)據(jù)以及源數(shù)據(jù)庫(kù)，計(jì)算出源數(shù)據(jù)庫(kù)生成給定實(shí)例的查詢，在實(shí)例數(shù)據(jù)列和源數(shù)據(jù)庫(kù)列之間建立映射關(guān)系，幫助用戶自動(dòng)完成數(shù)據(jù)庫(kù)模式匹配，此方法不要求用戶對(duì)源數(shù)據(jù)庫(kù)有任何了解。依照定義提出的基于行的模式匹配方法在分別處理實(shí)例表中各數(shù)據(jù)行后取各數(shù)據(jù)行模式匹配結(jié)果的交集。基于重用的優(yōu)化方法將上一行數(shù)據(jù)的模式匹配結(jié)果作為處理下一行數(shù)據(jù)的輸入，減小數(shù)據(jù)搜索范圍和生成的查詢計(jì)劃數(shù)量，提升執(zhí)行效率?；诹械膬?yōu)化方法將整個(gè)實(shí)例表作為一個(gè)整體，以列為單位進(jìn)行搜索和查詢計(jì)劃樹(shù)的生成，實(shí)現(xiàn)了效率的大幅提升，能夠很好地處理實(shí)例表中有多行數(shù)據(jù)的情況。實(shí)驗(yàn)驗(yàn)證了本文提出的優(yōu)化方法的高效性。未來(lái)研究仍有如下問(wèn)題值得思考：在很多情況下，用戶提供的樣例表不一定完全準(zhǔn)確無(wú)誤，如何處理這些錯(cuò)誤數(shù)據(jù)是一個(gè)巨大的挑戰(zhàn)。此外，在模式匹配中處理經(jīng)過(guò)加工或者格式轉(zhuǎn)換的數(shù)據(jù)也是一個(gè)非常值得研究的部分。