周鵬程，施歡歡，錢 鋼

（南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院，江蘇 南京210046）

基于MapReduce的關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢技術(shù)

周鵬程，施歡歡，錢 鋼*

（南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院，江蘇 南京210046）

為了解決關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢算法存在的問(wèn)題，根據(jù)圖搜索算法，將關(guān)系數(shù)據(jù)轉(zhuǎn)換成數(shù)據(jù)圖，再將數(shù)據(jù)圖物化成key/value形式存于分布式文件系統(tǒng)中。Map函數(shù)對(duì)數(shù)據(jù)圖中每個(gè)節(jié)點(diǎn)計(jì)算其可達(dá)關(guān)鍵詞，Reduce函數(shù)判斷一個(gè)節(jié)點(diǎn)是否可達(dá)所有查詢關(guān)鍵詞，若滿足條件則輸出以該節(jié)點(diǎn)為根的結(jié)果樹(shù)。在深入研究傳統(tǒng)的查詢算法基礎(chǔ)上，提出了基于MapReduce的分布式并行數(shù)據(jù)圖搜索算法。在用普通PC搭建的Hadoop集群上的實(shí)驗(yàn)表明：該方法明顯提升了查詢結(jié)果樹(shù)生成速度，并且具有較好的可擴(kuò)展性。

數(shù)據(jù)圖；關(guān)鍵詞查詢；MapReduce；云計(jì)算；分布式計(jì)算

關(guān)系數(shù)據(jù)庫(kù)是目前主流的信息存儲(chǔ)機(jī)制，如何從海量數(shù)據(jù)庫(kù)中以一種高效的方式獲取有用的信息是人們亟需解決的問(wèn)題。如果要利用結(jié)構(gòu)化查詢語(yǔ)言從目標(biāo)數(shù)據(jù)庫(kù)中獲得精確的結(jié)果，就需要用戶熟悉數(shù)據(jù)庫(kù)專業(yè)知識(shí)。然而普通用戶通常不具備復(fù)雜的查詢語(yǔ)言（如SQL、SPARQL、XQuery）和底層數(shù)據(jù)庫(kù)模式等知識(shí)。另一方面，發(fā)展得如火如荼的互聯(lián)網(wǎng)搜索引擎（如Google、百度）為廣大用戶提供了一種簡(jiǎn)單易用的信息獲取方式，即關(guān)鍵詞查詢。在搜索引擎中用戶只要提交一個(gè)關(guān)鍵詞集合，就能獲取到相關(guān)的查詢結(jié)果。比常規(guī)的信息檢索更具挑戰(zhàn)性的是，由于關(guān)系數(shù)據(jù)庫(kù)的規(guī)范化，原本一條完整的信息可能存儲(chǔ)在不同的表中，那么基于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢，目標(biāo)就不只是找到包含所給關(guān)鍵詞的相關(guān)文檔或文檔片段，更重要的是發(fā)現(xiàn)關(guān)鍵詞之間的語(yǔ)義關(guān)系[1]。

目前絕大多數(shù)對(duì)于關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢的研究按照對(duì)數(shù)據(jù)庫(kù)建模的方法來(lái)分可以分為兩大類：一類是基于數(shù)據(jù)圖的方法[2－4]；一類是基于模式圖的方法[5－6]。因?yàn)?，圖中的節(jié)點(diǎn)和邊都可以關(guān)聯(lián)文本內(nèi)容，所以，圖就成了關(guān)系數(shù)據(jù)（節(jié)點(diǎn)代表元組，邊表示主外鍵約束關(guān)系）、半結(jié)構(gòu)化數(shù)據(jù)（如XML，節(jié)點(diǎn)表示元素，邊表示XML元素間的包含關(guān)系或引用關(guān)系）、Web數(shù)據(jù)（節(jié)點(diǎn)表示網(wǎng)頁(yè)或者DOM元素，邊表示網(wǎng)頁(yè)間的鏈接關(guān)系或者DOM元素間的包含關(guān)系）的一種較好的公共表達(dá)形式[3]。因此，關(guān)鍵詞查詢的問(wèn)題自然地被轉(zhuǎn)化為圖搜索問(wèn)題，核心就是要從圖中高效地搜索到少量的與用戶查詢高度相關(guān)的結(jié)果樹(shù)。作為對(duì)傳統(tǒng)數(shù)據(jù)庫(kù)查詢的一種補(bǔ)充方式，關(guān)鍵詞查詢和應(yīng)用受到了數(shù)據(jù)庫(kù)研究領(lǐng)域越來(lái)越多的關(guān)注[7-10]，但由于其巨大的搜索空間，使得其查詢效率難以滿足實(shí)際應(yīng)用需求，尤其面對(duì)大規(guī)模海量數(shù)據(jù)時(shí)更是如此。例如，國(guó)家電網(wǎng)數(shù)據(jù)采集系統(tǒng)實(shí)時(shí)收集網(wǎng)點(diǎn)中的時(shí)序數(shù)據(jù)，由于其數(shù)據(jù)規(guī)模按時(shí)間呈遞增趨勢(shì)，傳統(tǒng)的存儲(chǔ)、查詢技術(shù)效率低下，擴(kuò)展性差，無(wú)法支撐調(diào)度自動(dòng)化、配電自動(dòng)化、海量歷史/實(shí)時(shí)數(shù)據(jù)管理平臺(tái)、發(fā)電等涉及多個(gè)智能電網(wǎng)環(huán)節(jié)的應(yīng)用系統(tǒng)。另一方面，大數(shù)據(jù)與云計(jì)算技術(shù)帶來(lái)的信息風(fēng)暴正在變革人們的生活、工作和思維，大量傳統(tǒng)的數(shù)據(jù)處理技術(shù)和數(shù)據(jù)挖掘技術(shù)正被移植到云計(jì)算平臺(tái)。盡管國(guó)內(nèi)外對(duì)云計(jì)算技術(shù)已經(jīng)開(kāi)展了很多相關(guān)研究，但是如何將它應(yīng)用于數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢的研究并不多。文獻(xiàn)[11]研究了基于MapReduce[12]的分布式索引構(gòu)建以實(shí)現(xiàn)對(duì)大規(guī)模圖數(shù)據(jù)的搜索優(yōu)化，但是其只是用MapReduce并行構(gòu)建索引，而沒(méi)有把搜索算法MapReduce化。筆者在傳統(tǒng)數(shù)據(jù)圖搜索算法的基礎(chǔ)上，研究提出基于MapReduce的分布式數(shù)據(jù)圖搜索算法。MapReduce模型處理的是key-value型數(shù)據(jù)，而關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)的是表數(shù)據(jù)，針對(duì)MR模型的特征研究了合適的數(shù)據(jù)分布策略以及相應(yīng)的搜索方法。實(shí)驗(yàn)表明，在大規(guī)模數(shù)據(jù)集中筆者提出的并行算法能夠提高數(shù)據(jù)圖搜索效率。

1 相關(guān)工作

對(duì)于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢，國(guó)內(nèi)外已經(jīng)出現(xiàn)了一批具有重要意義的研究成果。其中比較有影響的系統(tǒng)有Agrawal等人研發(fā)的DBXplorer[5]，Hristidis等人提出的DISCOVER[6]，Bhalotia等人實(shí)現(xiàn)的BANKS[2]。這些研究以及后續(xù)一些研究工作[13－14]雖然各有側(cè)重點(diǎn)，但是它們的核心思想是一致的，即將存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中的結(jié)構(gòu)化數(shù)據(jù)看成圖，其中數(shù)據(jù)庫(kù)中的元組構(gòu)成圖的頂點(diǎn)，元組間的主外鍵關(guān)系構(gòu)成圖中的邊。當(dāng)用戶提出一個(gè)關(guān)鍵詞查詢時(shí),則從圖中搜索出含全部或部分關(guān)鍵詞的最小子圖作為查詢結(jié)果。對(duì)于給定的數(shù)據(jù)庫(kù)和查詢，DBXplorer、DISCOVER都會(huì)生成所有的可能包含關(guān)鍵詞的連接樹(shù)。如果數(shù)據(jù)庫(kù)模式結(jié)構(gòu)復(fù)雜，那么生成所有的連接樹(shù)將會(huì)十分低效。BANKS首次提出一種叫做逆向搜索（backward search）的圖搜索算法。該算法利用了Dijkstra單源點(diǎn)最短路徑算法，逆向搜索的路徑是由樹(shù)中的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的最短路徑構(gòu)成。如果數(shù)據(jù)圖規(guī)模很大，包含某個(gè)關(guān)鍵詞的節(jié)點(diǎn)很多，或者當(dāng)算法遭遇一個(gè)入度非常大的節(jié)點(diǎn)時(shí)，逆向搜索算法的性能就顯得比較差。文獻(xiàn)[14]研究提出了一種融合了超節(jié)點(diǎn)圖和緩存細(xì)節(jié)圖的表示技術(shù)以減少查詢時(shí)的I/O開(kāi)銷，但其應(yīng)用場(chǎng)景局限于單機(jī)系統(tǒng)，不具備可擴(kuò)展性。

在云計(jì)算方面，Google提出的并行計(jì)算框架MapReduce[12]給超大規(guī)模數(shù)據(jù)集的處理開(kāi)辟了思路。不少研究者將MapReduce思想運(yùn)用到自己的研究領(lǐng)域中，改進(jìn)傳統(tǒng)算法，以提高執(zhí)行效率。文獻(xiàn)[15]提出了一種基于MapReduce的并行混合混沌加密方案，有效解決了云環(huán)境中大數(shù)據(jù)量加密速度慢的問(wèn)題。文獻(xiàn)[16]設(shè)計(jì)了一個(gè)高效的基于MapReduce的大規(guī)模圖挖掘框架，并在十億級(jí)的數(shù)據(jù)上驗(yàn)證了其性能。但是把MapReduce應(yīng)用到數(shù)據(jù)庫(kù)關(guān)鍵詞查詢算法上的研究工作還相對(duì)較少。

2 背景知識(shí)和問(wèn)題描述

文中對(duì)數(shù)據(jù)庫(kù)建模的方式采用數(shù)據(jù)圖，即直接將數(shù)據(jù)庫(kù)的實(shí)例數(shù)據(jù)構(gòu)建成數(shù)據(jù)圖，并轉(zhuǎn)換為key-value對(duì)的形式交給MapReduce進(jìn)行處理，從中枚舉簡(jiǎn)化子圖，最終以key-value的形式輸出結(jié)果。下面給出MapReduce計(jì)算模型以及數(shù)據(jù)圖、關(guān)鍵詞查詢等相關(guān)定義。

2.1 MapReduce計(jì)算模型

MapReduce[12]是Google提出的一個(gè)用于處理大規(guī)模數(shù)據(jù)集的可擴(kuò)展的分布式編程模型，它既是一個(gè)并行計(jì)算模型，也是一種并行計(jì)算框架。MapReduce框架簡(jiǎn)化了用戶設(shè)計(jì)并行程序的難度，使得用戶只需要考慮算法本身的實(shí)現(xiàn)邏輯，而無(wú)須關(guān)心不同計(jì)算機(jī)之間的通信、容錯(cuò)等問(wèn)題。利用該模型，用戶可以自定義兩個(gè)函數(shù)Map和Reduce來(lái)實(shí)現(xiàn)分布式算法。輸入數(shù)據(jù)文件首先被計(jì)算框架切分成一個(gè)個(gè)數(shù)據(jù)分片，并解析成＜keyin，valuein＞的形式傳入Map函數(shù)。Map函數(shù)返回一個(gè)基于這個(gè)處理的中間結(jié)果集，即一系列新的＜keyout，valueintermediate＞，如式（1）；MapReduce框架會(huì)把從一個(gè)或多個(gè) Map任務(wù)處理得到的結(jié)果集按 keyout值進(jìn)行分類、匯聚，并分配給相應(yīng)的Reduce函數(shù)進(jìn)行匯總處理生成最終的valueout值，如式（2）。

Map和Reduce函數(shù)會(huì)并行運(yùn)行，即計(jì)算框架會(huì)在不同的機(jī)器上同時(shí)運(yùn)行多個(gè)Map和Reduce任務(wù)。許多現(xiàn)實(shí)世界中的數(shù)據(jù)處理任務(wù)可以表達(dá)成該模型，便于實(shí)現(xiàn)并行化的計(jì)算。Apache的Hadoop是Google MapReduce的一個(gè)開(kāi)源實(shí)現(xiàn)，它提供了與Google GFS類似的分布式數(shù)據(jù)存儲(chǔ)系統(tǒng)HDFS。Hadoop以其簡(jiǎn)單易用的特性推動(dòng)了MapReduce的廣泛應(yīng)用，方便了研究人員部署分布式算法。目前，Hadoop已經(jīng)成為大數(shù)據(jù)存儲(chǔ)與處理的新范式。

2.2 數(shù)據(jù)圖和查詢模型定義

定義1 數(shù)據(jù)圖[13]。一個(gè)數(shù)據(jù)圖G由一個(gè)節(jié)點(diǎn)集合V（G）和一個(gè)邊集E（G）構(gòu)成。數(shù)據(jù)圖中有兩類節(jié)點(diǎn)，即結(jié)構(gòu)化數(shù)據(jù)實(shí)例節(jié)點(diǎn)S（G）和關(guān)鍵詞節(jié)點(diǎn)K（G）。關(guān)鍵詞節(jié)點(diǎn)只有入射邊，而實(shí)例節(jié)點(diǎn)既有入射邊也有出射邊，因此，一條邊不能同時(shí)連接兩個(gè)關(guān)鍵詞。數(shù)據(jù)圖的邊可以有權(quán)重，權(quán)重函數(shù)wG給每一條邊e∈E（G）分配一個(gè)正的權(quán)重wG（e）。數(shù)據(jù)圖G的權(quán)重w（G）是圖G中所有邊的權(quán)重之和，即w（G）=Σe∈E（G）wG（e）。一個(gè)數(shù)據(jù)圖是有根的，如果它包含某個(gè)節(jié)點(diǎn)r，并且對(duì)于圖中任意節(jié)點(diǎn)都可以從節(jié)點(diǎn)r通過(guò)一條有向路徑到達(dá)，這個(gè)節(jié)點(diǎn)r就被稱作圖G的根。

定義2 關(guān)鍵詞查詢[1，13]。一個(gè)關(guān)鍵詞查詢就是給定一個(gè)有限的關(guān)鍵詞集合K。一個(gè)關(guān)鍵詞查詢的結(jié)果就是目標(biāo)數(shù)據(jù)圖G的一棵子樹(shù)T，T是關(guān)于給定的關(guān)鍵詞集合K的簡(jiǎn)化，即T包含了K，并且不再會(huì)有T的子樹(shù)包含K。

定義3 top-k關(guān)鍵詞查詢[1]。一個(gè)top-k關(guān)鍵詞查詢Q是一個(gè)關(guān)鍵詞集合K。而相應(yīng)的查詢結(jié)果則是一個(gè)由k個(gè)元組連接樹(shù)組成的列表T，并且對(duì)于查詢Q而言，這k個(gè)元組連接樹(shù)的最終評(píng)分Score（T，Q）是最高的。當(dāng)存在評(píng)分平局時(shí)，可以采用任意的方式打破平局。T中的元組連接樹(shù)按照評(píng)分降序排列。

總的來(lái)說(shuō)，對(duì)于給定的關(guān)鍵詞集合，基于數(shù)據(jù)圖的查詢過(guò)程主要包含兩個(gè)步驟：首先，查找倒排表形式的關(guān)鍵詞索引，獲得節(jié)點(diǎn)ID，這些節(jié)點(diǎn)都包含了至少一個(gè)查詢關(guān)鍵詞；然后，運(yùn)行圖搜索算法尋找連接了上述關(guān)鍵詞節(jié)點(diǎn)的有根樹(shù)，并且對(duì)結(jié)果進(jìn)行排序。

3 基于MapReduce的數(shù)據(jù)圖搜索算法

對(duì)于MapReduce來(lái)說(shuō)輸入數(shù)據(jù)就是一系列的＜key，value＞對(duì)，處理邏輯是Map和Reduce函數(shù)，因此，并行的數(shù)據(jù)圖搜索算法的關(guān)鍵是定義合適的＜key，value＞存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)的Map、Reduce函數(shù)來(lái)表達(dá)對(duì)數(shù)據(jù)圖的搜索。筆者先介紹傳統(tǒng)的單機(jī)串行方式數(shù)據(jù)圖搜索算法，然后介紹基于MapReduce的方法。

3.1 傳統(tǒng)的數(shù)據(jù)圖搜索算法

逆向搜索（backward search）算法是尋找數(shù)據(jù)圖中最小連接子圖的一個(gè)經(jīng)典算法，它在BANKS系統(tǒng)中首先被提出，之后很多研究（如BANKS-II[4]和BLINKS[10]等）都是基于該算法的改進(jìn)。逆向搜索從每個(gè)與關(guān)鍵詞匹配的葉節(jié)點(diǎn)開(kāi)始，朝著匯合的根節(jié)點(diǎn)向上搜索，每當(dāng)標(biāo)記到一個(gè)被每個(gè)關(guān)鍵詞所到達(dá)的節(jié)點(diǎn)v時(shí)，就輸出一棵以v為根節(jié)點(diǎn)的結(jié)果樹(shù)。逆向搜索算法的具體步驟如下[4]：

（1）在逆向搜索的任意時(shí)刻，令Ei表示當(dāng)前已知的可以到達(dá)關(guān)鍵詞節(jié)點(diǎn)ki的節(jié)點(diǎn)集，Ei稱作關(guān)于ki的簇。（2）在最初始階段，Ei被定義為直接包含ki的節(jié)點(diǎn)集。稱這個(gè)集合為“原始簇”，它的成員節(jié)點(diǎn)即為關(guān)鍵詞節(jié)點(diǎn)。（3）在搜索過(guò)程的每一步，都從先前訪問(wèn)過(guò)的節(jié)點(diǎn)（比如節(jié)點(diǎn)v）開(kāi)始，選擇一條入射邊，沿著這條邊反向訪問(wèn)它的父節(jié)點(diǎn)（比如節(jié)點(diǎn)u）。此時(shí)任何包含節(jié)點(diǎn)v的Ei都被擴(kuò)展到節(jié)點(diǎn)u。一旦一個(gè)節(jié)點(diǎn)已經(jīng)被訪問(wèn)，那么搜索算法就可以獲得它的所有入射邊信息，并且在下一個(gè)搜索過(guò)程中訪問(wèn)這些邊。（4）如果對(duì)于每一個(gè)簇Ei，都有或者節(jié)點(diǎn)x∈Ei，或者存在一條從x到Ei中某個(gè)節(jié)點(diǎn)的邊，則意味著已經(jīng)發(fā)現(xiàn)了一個(gè)答案的根節(jié)點(diǎn)x。

假設(shè)有如圖1所示的數(shù)據(jù)圖片段（為描述簡(jiǎn)便，假設(shè)圖中每個(gè)節(jié)點(diǎn)內(nèi)的數(shù)字代表數(shù)據(jù)庫(kù)元組的ID，節(jié)點(diǎn)旁邊的小寫字母a，b，c，…表示該元組包含的關(guān)鍵詞集合）。以該圖為例，來(lái)分析逆向搜索算法的執(zhí)行過(guò)程。

假設(shè)用戶輸入的關(guān)鍵詞是 b、c，不難發(fā)現(xiàn)節(jié)點(diǎn) 3、4、5、10、12 都直接包含關(guān)鍵詞項(xiàng)，算法會(huì)對(duì)這5個(gè)節(jié)點(diǎn)進(jìn)行反向搜索。節(jié)點(diǎn)3可以反向到達(dá)節(jié)點(diǎn)1，所以標(biāo)記節(jié)點(diǎn)1、3可達(dá)關(guān)鍵詞c。同理，對(duì)節(jié)點(diǎn)4進(jìn)行逆向搜索，可以訪問(wèn)到節(jié)點(diǎn)1，所以標(biāo)記1、4可達(dá)關(guān)鍵詞b。所以當(dāng)搜索到節(jié)點(diǎn)1時(shí)，發(fā)現(xiàn)它已經(jīng)可達(dá)關(guān)鍵詞b，c，即包含了所有關(guān)鍵詞，因此，以節(jié)點(diǎn)1為根節(jié)點(diǎn)的一棵結(jié)果樹(shù)就生成了，如圖2中的結(jié)果樹(shù)I所示。同樣的，對(duì)節(jié)點(diǎn)5、10、12進(jìn)行逆向搜索將會(huì)得到如圖2所示的結(jié)果樹(shù) II、III。

圖1 一個(gè)數(shù)據(jù)圖片段

從逆向搜索算法模型中可以看到該算法的核心是從原始簇開(kāi)始進(jìn)行多次迭代搜索以擴(kuò)充每個(gè)關(guān)鍵詞的簇，直到每條搜索路徑都已到達(dá)圖的根節(jié)點(diǎn)截止。在迭代搜索的過(guò)程中一旦發(fā)現(xiàn)某個(gè)節(jié)點(diǎn)符合要求（對(duì)所有關(guān)鍵詞可達(dá)）就輸出以該節(jié)點(diǎn)為根的一棵結(jié)果樹(shù)。整個(gè)查詢過(guò)程中圖搜索的過(guò)程是最耗時(shí)的，尤其是當(dāng)數(shù)據(jù)圖的規(guī)模非常大，節(jié)點(diǎn)間的聯(lián)系比較復(fù)雜時(shí)更是如此。因此，文中考慮基于MapReduce的思想研究并行化的算法把搜索元組連接樹(shù)的過(guò)程MapReduce化。

3.2 基于MapReduce的逆向搜索算法

3.2.1 基于MapReduce的逆向搜索算法的key-value結(jié)構(gòu)和流程

MapReduce計(jì)算框架下的輸入是key-value數(shù)據(jù)，其中value可以是簡(jiǎn)單類型，比如數(shù)值或字符串，也可以是復(fù)雜的結(jié)構(gòu)，比如列表、記錄等。對(duì)于數(shù)據(jù)圖來(lái)說(shuō)，其內(nèi)部表示方式以鄰接表為宜，文中設(shè)計(jì)了式（3）那樣的key-value結(jié)構(gòu)。輸入數(shù)據(jù)的key為圖中節(jié)點(diǎn)ID，對(duì)應(yīng)的value為復(fù)雜記錄，其中記載了key節(jié)點(diǎn)當(dāng)前可達(dá)關(guān)鍵詞、key節(jié)點(diǎn)的父節(jié)點(diǎn)ID等信息。MapReduce內(nèi)部計(jì)算過(guò)程中的Shuffle和Sort操作起到類似于通過(guò)圖中節(jié)點(diǎn)出邊進(jìn)行消息傳播的效果。

通過(guò)將數(shù)據(jù)圖表達(dá)成式（3）這樣的鍵值對(duì)作為算法輸入（即作為Map函數(shù)的初始輸入），并行執(zhí)行一系列Map函數(shù)和Reduce函數(shù)對(duì)原始鍵值對(duì)處理，得到包含所有關(guān)鍵詞的連接樹(shù)鍵值對(duì)＜key，valueout＞，每一個(gè)輸出鍵值對(duì)代表一棵結(jié)果樹(shù)，其中key表示結(jié)果樹(shù)的根節(jié)點(diǎn)ID，valueout表示連接樹(shù)的路徑信息?；贛apReduce的逆向搜索算法的流程如圖3。

在圖 1 的例子當(dāng)中，根據(jù)數(shù)據(jù)圖生成的初始鍵值對(duì)是：＜1，＜＜a＞，＜null＞＞＞、＜2，＜＜f＞，＜1＞＞＞、＜3，＜＜c，d＞，＜1＞＞＞、＜4，＜＜b＞，＜1＞＞＞、＜5，＜＜b＞，＜2＞＞＞、＜6，＜＜e＞，＜2，3＞＞＞、＜7，＜＜g＞，＜3＞＞＞、＜8，＜＜f＞，＜3＞＞＞、＜9，＜＜g＞，＜5＞＞＞、＜10，＜＜c＞，＜5＞＞＞、＜11，＜＜a＞，＜6＞＞＞、＜12，＜＜c＞，＜6＞＞＞。

3.2.2 逆向搜索算法的Map函數(shù)

Map函數(shù)根據(jù)每個(gè)節(jié)點(diǎn) （key-value形式）的父節(jié)點(diǎn)列表擴(kuò)充其可達(dá)關(guān)鍵詞列表。Map函數(shù)偽代碼如下：

輸入：數(shù)據(jù)圖對(duì)應(yīng)的初始鍵值對(duì)KVPair

輸出：新生成的鍵值對(duì)集newKVPair

圖2 一個(gè)查詢的結(jié)果樹(shù)

圖3 基于MapReduce的搜索算法流程

以圖1所示的數(shù)據(jù)圖（查詢關(guān)鍵詞為b，c）為例分析Map函數(shù)的執(zhí)行過(guò)程。

輸入數(shù)據(jù)文件首先會(huì)被分布式文件系統(tǒng) （HDFS）切分成若干個(gè)數(shù)據(jù)塊存儲(chǔ)于計(jì)算機(jī)集群的不同節(jié)點(diǎn)。MapReduce計(jì)算框架從分布式文件系統(tǒng)中獲得輸入數(shù)據(jù)分片并解析出初始鍵值對(duì)交給Map任務(wù)處理，Map函數(shù)對(duì)該鍵值對(duì)進(jìn)行重組、擴(kuò)展。例如對(duì)于鍵值對(duì)＜3，＜＜c，d＞，＜1＞＞＞，因?yàn)椋?jié)點(diǎn) 3 可達(dá)關(guān)鍵詞 c、d，那么認(rèn)為節(jié)點(diǎn) 3 的父節(jié)點(diǎn) 1 也可達(dá)該關(guān)鍵詞，算法生成若干新的鍵值對(duì)＜3，＜c，d＞＞、＜1，＜c（3）＞＞、＜1，＜d（3）＞＞，分別表示節(jié)點(diǎn)3可達(dá)關(guān)鍵詞c、d，節(jié)點(diǎn)1途經(jīng)節(jié)點(diǎn)3可達(dá)關(guān)鍵詞c，節(jié)點(diǎn)1途經(jīng)節(jié)點(diǎn)3可達(dá)關(guān)鍵詞d。同理，對(duì)于其余鍵值對(duì)進(jìn)行Map操作輸出結(jié)果如下：

＜1，＜a＞＞，＜2，＜f＞＞、＜1，＜f（2）＞＞，＜4，＜b＞＞、＜1，＜b（4）＞＞，＜5，＜b＞＞、＜2，＜b（5）＞＞，＜6，＜e＞＞、＜2，＜e（6）＞＞、＜3，＜e（6）＞＞，＜7，＜g＞＞、＜3，＜g（7）＞＞，＜8，＜f＞＞、＜3，＜f（8）＞＞，＜9，＜g＞＞、＜5，＜g（9）＞＞，＜10，＜c＞＞、＜5，＜c（10）＞＞，＜11，＜a＞＞、＜6，＜a（11）＞＞，＜12，＜c＞＞、＜6，＜c（12）＞＞。

所有的Map任務(wù)都是并行工作的，Map的輸出結(jié)果經(jīng)過(guò)shuffle階段處理后作為Reduce函數(shù)的輸入。

3.2.3 逆向搜索算法的Reduce函數(shù)

通過(guò)MapReduce框架的shuffle過(guò)程，具有相同key值的鍵值對(duì)合并，values為它們所有的value值疊加。算法的Reduce函數(shù)偽代碼如下：

輸入：經(jīng)過(guò)shuffle處理過(guò)的鍵值對(duì)KVPair

輸出：結(jié)果樹(shù)鍵值對(duì)resKVPair和進(jìn)入下一輪迭代的鍵值對(duì)newKVPair

同樣以上面的例子接著分析算法Reduce函數(shù)的執(zhí)行過(guò)程。經(jīng)過(guò)shuffle處理后，具有相同key值的鍵值對(duì)歸并到一起交給 Reduce 處理。 例如鍵值對(duì)＜1，＜a＞＞、＜1，＜f（2）＞＞、＜1，＜c（3）＞＞、＜1，＜d（3）＞＞、＜1，＜b（4）＞＞在 shuffle 階段歸并成＜1，＜a，f（2），c（3），d（3），b（4）＞＞，表示節(jié)點(diǎn) 1 直接可達(dá)關(guān)鍵詞 a，并且可以通過(guò)節(jié)點(diǎn) 2到達(dá)關(guān)鍵詞f，通過(guò)節(jié)點(diǎn)3到達(dá)關(guān)鍵詞c、d，通過(guò)節(jié)點(diǎn)4到達(dá)關(guān)鍵詞b。Reduce函數(shù)會(huì)對(duì)輸入鍵值對(duì)的values列表值進(jìn)行判斷，如果 values中包含所有的查詢關(guān)鍵詞，就輸出結(jié)果鍵值對(duì)。 例如鍵值對(duì)＜1，＜a，f（2），c（3），d（3），b（4）＞＞同時(shí)包含了查詢關(guān)鍵詞 b 和 c，就可以輸出結(jié)果樹(shù)對(duì)＜1，＜c（3），b（4）＞＞，表示一棵以節(jié)點(diǎn) 1 為根節(jié)點(diǎn)，節(jié)點(diǎn) 3、4 為葉節(jié)點(diǎn)的連接樹(shù)。 同理，鍵值對(duì)＜5，＜b＞＞、＜5，＜g（9）＞＞、＜5，＜c（10）＞＞歸并后得到＜5，＜b，g（9），c（10）＞＞也能得到一個(gè)滿足查詢要求的結(jié)果對(duì)＜5，＜b，c（10）＞＞，表示一棵以節(jié)點(diǎn) 5 為根節(jié)點(diǎn)，節(jié)點(diǎn)10為葉節(jié)點(diǎn)的連接樹(shù)。同時(shí)將節(jié)點(diǎn)1、5標(biāo)記為已輸出，即不再尋找以節(jié)點(diǎn)1、5為根節(jié)點(diǎn)的結(jié)果樹(shù)，降低搜索范圍。再把其余鍵值對(duì)重新組裝成式（3）那樣的形式進(jìn)入下一輪迭代，直到每個(gè)鍵值對(duì)的可達(dá)關(guān)鍵詞列表不再變化，說(shuō)明此時(shí)整個(gè)數(shù)據(jù)圖已經(jīng)搜索完畢，算法結(jié)束。 最終輸出的結(jié)果對(duì)如下：＜1，（c（3），b（4））＞，＜5，（b，c（10））＞，＜2，（b（5），c（12）（6））＞。其中＜2，（b（5），c（12）（6））＞表示根節(jié)點(diǎn) 2 通過(guò)節(jié)點(diǎn) 5 可達(dá)關(guān)鍵詞 b，通過(guò)節(jié)點(diǎn)6、節(jié)點(diǎn)12可達(dá)關(guān)鍵詞c。該結(jié)果恰好對(duì)應(yīng)圖2的結(jié)果樹(shù)，由此可知基于MapReduce的逆向搜索算法與傳統(tǒng)逆向搜索算法的輸出結(jié)果是一致的。

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

4.1 實(shí)驗(yàn)環(huán)境與設(shè)置

文中從執(zhí)行效率、可擴(kuò)展性兩個(gè)方面評(píng)估算法的性能。分別在單機(jī)上運(yùn)行串行的數(shù)據(jù)圖搜索算法和在集群上運(yùn)行基于MapReduce的搜索算法來(lái)輸出查詢結(jié)果樹(shù)。采用的實(shí)驗(yàn)集群由1個(gè)主控節(jié)點(diǎn)Master（同時(shí)運(yùn)行NameNode和ResourceManager進(jìn)程）、6個(gè)計(jì)算節(jié)點(diǎn)Slave（同時(shí)運(yùn)行DataNode和NodeManager進(jìn)程）組成，集群的節(jié)點(diǎn)配置為 CPU（4 核 Intel Core i5 3.30 GHz），Memory（4GB），Disk（500G STAT），Network Bandwidth（1Gbps），OS（CentOS6.4），JVM Version（JDK1.7），Hadoop Version（Hadoop2.4）。

實(shí)驗(yàn)所用數(shù)據(jù)集是計(jì)算機(jī)科學(xué)文獻(xiàn)庫(kù)DBLP數(shù)據(jù)集，它提供了計(jì)算機(jī)領(lǐng)域科學(xué)文獻(xiàn)的檢索服務(wù)，但只儲(chǔ)存這些文獻(xiàn)的相關(guān)元數(shù)據(jù)，如標(biāo)題、作者、發(fā)表日期等。將DBLP網(wǎng)站提供的XML數(shù)據(jù)分解成4個(gè)關(guān)系：Author（Aid，Name）、Write（Aid，Pid）、Paper（Pid，Title，Year，Type）、Cite（Pid1，Pid2）。每個(gè) Author和 Paper實(shí)例對(duì)應(yīng)于數(shù)據(jù)圖中的一個(gè)節(jié)點(diǎn)，若實(shí)例之間存在Write或者Cite關(guān)系則建立相應(yīng)的邊。由于MapReduce的輸入是鍵值對(duì)形式，所以預(yù)先將數(shù)據(jù)圖映射成key-value數(shù)據(jù)存儲(chǔ)在HDFS上作為MapReduce的輸入源，數(shù)據(jù)集的大小根據(jù)不同的實(shí)驗(yàn)需求確定。

4.2 執(zhí)行性能測(cè)試

對(duì)5組不同規(guī)模的數(shù)據(jù)用傳統(tǒng)的單機(jī)串行算法和基于MapReduce的并行算法分別進(jìn)行了5次測(cè)試，最后取算法從接收關(guān)鍵詞到輸出查詢結(jié)果樹(shù)的平均時(shí)間作為運(yùn)行耗時(shí)，實(shí)驗(yàn)所用關(guān)鍵詞數(shù)量為2，并且都是從DBLP數(shù)據(jù)中選出來(lái)的。實(shí)驗(yàn)結(jié)果見(jiàn)表1。

由實(shí)驗(yàn)結(jié)果可見(jiàn)，與傳統(tǒng)的方式相比，基于MapReduce的并行方式在處理速度上有明顯優(yōu)勢(shì)，特別是隨著數(shù)據(jù)集大小的增長(zhǎng)，分布式的算法就更能發(fā)揮優(yōu)勢(shì)。同時(shí)發(fā)現(xiàn)，基于MapReduce的算法耗時(shí)并未隨著數(shù)據(jù)集大小的線性增長(zhǎng)而線性上升，這一方面是由于MapReduce框架每次并行運(yùn)行的Map任務(wù)數(shù)是根據(jù)輸入數(shù)據(jù)大小自動(dòng)優(yōu)化的，每次任務(wù)運(yùn)行都有一定的通信開(kāi)銷。另一方面，數(shù)據(jù)圖中節(jié)點(diǎn)之間聯(lián)系的復(fù)雜度并不是隨著數(shù)據(jù)量的增長(zhǎng)而線性增長(zhǎng)的。

4.3 可擴(kuò)展性測(cè)試

為了觀察集群的規(guī)模增大時(shí)算法的性能變化情況，實(shí)驗(yàn)中還進(jìn)行了算法可擴(kuò)展性測(cè)試。實(shí)驗(yàn)中，將同一個(gè)數(shù)據(jù)集文件分別在從1個(gè)節(jié)點(diǎn)（local模式）增長(zhǎng)到7個(gè)節(jié)點(diǎn)（1個(gè)主節(jié)點(diǎn)+6個(gè)從節(jié)點(diǎn)）的集群上進(jìn)行實(shí)驗(yàn)，每組實(shí)驗(yàn)也進(jìn)行5次取平均值，實(shí)驗(yàn)結(jié)果如圖4所示。

圖4顯示了計(jì)算節(jié)點(diǎn)數(shù)目變化時(shí)算法的運(yùn)行時(shí)間變化曲線。其中橫坐標(biāo)為集群中在線節(jié)點(diǎn)數(shù)目，縱坐標(biāo)為算法執(zhí)行時(shí)間。從圖中曲線可見(jiàn)，剛開(kāi)始時(shí)算法的運(yùn)行時(shí)間隨著集群內(nèi)節(jié)點(diǎn)數(shù)目的增加呈接近于線性下降，之后曲線表現(xiàn)得比較平緩，這主要是由于并行算法的通信調(diào)度等開(kāi)銷造成的，特別是在數(shù)據(jù)規(guī)模遠(yuǎn)小于集群處理能力的情況下這種開(kāi)銷顯示出的代價(jià)越大。但總的來(lái)說(shuō)，從圖4中可以發(fā)現(xiàn)隨著計(jì)算節(jié)點(diǎn)的增加，并行執(zhí)行的耗時(shí)下降顯著，即算法有比較好的可擴(kuò)展性。

表1 查詢執(zhí)行時(shí)間

圖4 集群節(jié)點(diǎn)數(shù)變化時(shí)算法運(yùn)行時(shí)間對(duì)比

5 結(jié)語(yǔ)

文中針對(duì)關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢中大規(guī)模數(shù)據(jù)圖搜索效率低下的問(wèn)題，以經(jīng)典的連接樹(shù)生成算法作為基礎(chǔ)，提出了基于MapReduce的分布式并行搜索算法。分析和實(shí)驗(yàn)結(jié)果表明,并行算法充分利用計(jì)算資源減少了時(shí)間開(kāi)銷,并且具有較好的可擴(kuò)展性。進(jìn)一步的工作包括考慮有意義的結(jié)果評(píng)分和數(shù)據(jù)可視化機(jī)制，用以將查詢結(jié)果樹(shù)按照相關(guān)順序和良好的展現(xiàn)方式返回給用戶。

參考文獻(xiàn)：

[1]林子雨，楊冬青，王騰蛟，等.基于關(guān)系數(shù)據(jù)庫(kù)的關(guān)鍵詞查詢[J].軟件學(xué)報(bào)，2010，21（10）：2454-2476.

[2]BHALOTIA G，HULGERI A，NAKHE C，et al.Keyword Searching and Browsing in Databases using BANKS[C]//Data Engineering，2002.Proceedings.18th International Conference on Data Engineering.IEEE，2002：431-440.

[3]KACHOLIA V，PANDIT S，CHAKRABARTI S，et al.Bidirectional Expansion for Keyword Search on Graph Databases[C]//Proceedings of the 31st International Conference on Very Large Data Bases.VLDB Endowment，2005：505-516.

[4]HE H，WANG H，YANG J，et al.BLINKS：Ranked Keyword Searches on Graphs[C]//Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data.ACM，2007：305-316.

[5]AGRAWAL S，CHAUDHURI S，DAS G.DBXplorer：Enabling Keyword Search over Relational Databases[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data.ACM，2002：627-627.

[6]HRISTIDIS V，PAPAKONSTANTINOU Y.Discover：Keyword Search in Relational Databases[C]//Proceedings of the 28th international conference on Very Large Data Bases.VLDB Endowment，2002：670-681.

[7]MOTTIN D，LISSANDRINI M，VELEGRAKIS Y，et al.Exemplar queries：Give me an example of what you need[J].Proceedings of the VLDB Endowment，2014，7（5）：365-376.

[8]ZENG Z，BAO Z，LE T N，et al.ExpressQ：Identifying Keyword Context and Search Target in Relational Keyword Queries[C]//Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management.ACM，2014：31-40.

[9]楊書新，徐麗萍，夏小云，等.圖數(shù)據(jù)關(guān)鍵詞查詢研究進(jìn)展[J].電子學(xué)報(bào)，2014，42（11）：2260-2267.

[10]王新軍，閆實(shí)，彭朝暉，等.Extractor：支持查詢重構(gòu)的高效數(shù)據(jù)庫(kù)關(guān)鍵詞檢索系統(tǒng)[J].電子學(xué)報(bào)，2014，42（2）：209-216.

[11]桑雷，鐘鳴，陳柳，等.FindGrape：一個(gè)高效的圖數(shù)據(jù)庫(kù)關(guān)鍵詞搜索引擎[C]//第29屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集.合肥：中國(guó)計(jì)算機(jī)學(xué)會(huì)，2012.

[12]DEAN J，GHEMAWAT S.MapReduce：simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）：107-113.

[13]KIMELFELD B，SAGIV Y.Efficiently enumerating results of keyword search over data graphs[J].Information Systems，2008，33（4）：335-359.

[14]DALVI B B，KSHIRSAGAR M，SUDARSHAN S.Keyword search on external memory data graphs[J].Proceedings of the VLDB Endowment，2008，1（1）：1189-1204.

[15]王欣宇，楊庚，閔兆娥，等.基于 MapReduce的并行混合混沌加密方案[J].計(jì)算機(jī)應(yīng)用研究，2015，32（6）：1757-1760.

[16]LAI H C，LI C T，LO Y C，et al.Exploiting and Evaluating MapReduce for Large-Scale Graph Mining[C]//Advances in Social Networks Analysis and Mining（ASONAM），2012 IEEE/ACM International Conference on.IEEE，2012：434-441.

Keyword query over relational databases based on MapReduce

ZHOU Pengcheng， SHI Huanhuan， QIAN Gang*
（College of Information Engineering，Nanjing University of Finance and Economics，Nanjing 210046，China）

In order to solve the problems of memory capacity and CPU processing speed in the traditional search algorithm,we proposed a parallel search algorithm based on MapReduce.In this algorithm，relational data were transformed into graph data which were then stored into HDFS in the form of key-value pairs.Map function calculated all the keywords that one node could reach；Reduce function judged if a node was reachable for all the query keywords.If this condition was satisfied，an answer root was discovered.According to the experiments on Hadoop cluster set up by ordinary PCs，the algorithm speeds up the query process and takes high expansibility.

data graphs；keyword search；MapReduce；cloud computing；distributed computing

TP311

A

2096－3289（2017）03－0064－07

責(zé)任編輯：艾淑艷

2015－11－30

江蘇省產(chǎn)學(xué)研合作項(xiàng)目（BY2015010-05）；南京財(cái)經(jīng)大學(xué)研究生創(chuàng)新研究基金資助項(xiàng)目（YJS14102）

周鵬程（1990-），男，江蘇泰州人，碩士研究生，研究方向：數(shù)據(jù)庫(kù)與信息系統(tǒng)。

*通信作者：錢 鋼（1975-），男，博士，副教授，碩士生導(dǎo)師，E-mail：zpcandzhj@163.com。