嵌入圖數(shù)據(jù)庫的檢索算法研究

于素華，張 俊，高 燕

（大連海事大學 信息科學技術(shù)學院，遼寧 大連116026）

0 引 言

為了提高關(guān)系數(shù)據(jù)庫信息檢索的效率或效果，大量國內(nèi)外專家對檢索策略進行了諸多的嘗試和改進。Spark[1，2]采用一種非單調(diào)聚合函數(shù)對結(jié)果進行排序，DBPF[3]使用動態(tài)編程方式，在單位時間內(nèi)搜索字詞數(shù)量呈指數(shù)增長的情況下識別最小Steiner樹組，Blinks[4]使用雙向索引來優(yōu)化檢索表現(xiàn)，EASE[5]提出一種圖索引來支持非結(jié)構(gòu)化、半結(jié)構(gòu)化和關(guān)系數(shù)據(jù)的有效查詢，前提是查詢結(jié)果為半徑不超過最大規(guī)模的子圖。文獻[6]確保了枚舉結(jié)果時僅產(chǎn)生多項式延遲，但枚舉的方式是通過高度而不是權(quán)重。文獻[7]集成了外存圖上的關(guān)鍵詞檢索方法，該外存圖使用多粒度圖表示來降低I／O開銷，與虛擬內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)進行對比。STAR[8]在非多項式時間內(nèi)運用啟發(fā)式的方法輸出近似最佳的結(jié)果樹。這些檢索算法大都基于內(nèi)存數(shù)據(jù)圖，就必然會面臨大規(guī)模數(shù)據(jù)下內(nèi)存溢出的問題。為了解決內(nèi)存不足，BANKS－III[9]將檢索的數(shù)據(jù)圖存于外存，不僅增加了算法的復雜度，而且缺乏對海量數(shù)據(jù)的統(tǒng)一管理。

對象級別的信息檢索 （object－level information retrieval over relational databases，DBOIR）方法[10]，從對象的觀點和方法構(gòu)建關(guān)系數(shù)據(jù)的對象模型。雖然解決了元組級別的信 息 檢 索 （tuple－level information retrieval over relational databases，DBTIR）語義難以理解和結(jié)果重復的現(xiàn)象，但對于高度相關(guān)結(jié)果仍然存在部分缺失。在數(shù)據(jù)復雜性日益增高的今天，對象級別建模思想[11]盡管能夠在一定程度上降低數(shù)據(jù)圖的復雜性，但由于對象圖包含信息量的增加，數(shù)據(jù)圖的大小并不一定能夠真正減小。

Mississippi大學的Chad Vicknair等在2010年的一項研究表明[12]:圖數(shù)據(jù)庫在結(jié)構(gòu)化查詢方面優(yōu)于關(guān)系數(shù)據(jù)庫。圖數(shù)據(jù)庫數(shù)據(jù)管理已經(jīng)引起越來越多國內(nèi)外學者的關(guān)注和研究，特別是在子圖查詢 （subgraph search）、最短路徑查詢 （shortest－path query）、可達性確認 （reachability verifi－cation）和部分匹配 （pattern match）等方面成果頗豐，如GString[13]和 Distance－Join[14]等。而沒有將圖數(shù)據(jù)庫應用到關(guān)系數(shù)據(jù)庫信息檢索上，對圖數(shù)據(jù)庫存儲的對象圖進行檢索和統(tǒng)一管理的方法?；趫D數(shù)據(jù)庫可嵌入和多語言訪問支持的特點，本文提出了引入圖數(shù)據(jù)庫實現(xiàn)關(guān)系數(shù)據(jù)庫信息檢索的方法，通過該方法可以避免內(nèi)外存的管理問題。

1 模型構(gòu)建

1.1 建模信息缺失

現(xiàn)有的對象級別建模思想，僅將包含主－外鍵聯(lián)系的部分相關(guān)元組作為對象單元加入到對象描述域中，而忽略了含實體內(nèi)部聯(lián)系的關(guān)系數(shù)據(jù)庫中對象間聯(lián)系的相互作用。例如，在DBLP中查詢Q＝“ObjectRank”，其返回結(jié)果如圖1所示。查詢結(jié)果中僅包含論文的題目、作者和參考文獻的信息，缺失了該論文曾被哪些論文引用過的信息。

圖1 DBOIR在DBLP上檢索結(jié)果示例

在圖2中，pi代表論文主鍵，ai代表作者主鍵?？梢钥闯?作者對象a1寫了論文p1，故對象a1的描述域中包含p1；論文對象p1的作者為a1，故對象p1的描述域中包含a1。論文對象p2引用了論文p3，故對象p2的描述域中包含p3；論文對象p3被p2引用了，對象p3的描述域中卻沒有p2的任何信息。

圖2 DBLP對象

1.2 描述域分塊

為了有效的利用對象描述域，使對象分數(shù)組成更加合理化。需要對原有的對象構(gòu)建方式進行拓展，將與目標對象相連的所有元組全部放入對象描述域中。根據(jù)對象與元組間聯(lián)系的類型與出入度關(guān)系，把對象描述域進行結(jié)構(gòu)化分塊，分塊后的對象結(jié)構(gòu)如圖3所示。

圖3 分塊后的對象結(jié)構(gòu)

圖3 中，Topic表示對象的主題域，Description表示對象的描述域，typei表示對象描述域中包含的元組與該對象的聯(lián)系類型，inDeg與outDeg分別表示相應的聯(lián)系類型與該對象的入度／出度關(guān)系。將對象描述域分塊，有這樣幾個好處:①能夠使復雜的對象描述域變得有序，便于對象圖的檢索和結(jié)果呈現(xiàn)；②能夠更容易的發(fā)現(xiàn)數(shù)據(jù)內(nèi)部的聯(lián)系；③可以根據(jù)各個塊對對象的貢獻度大小進行自主調(diào)節(jié)，增加了對象權(quán)重的可伸縮性。

在對象結(jié)構(gòu)圖中，對象內(nèi)部或?qū)ο箝g相同類型的出度塊與入度塊是互補的。即若存在一個類型的出度塊／入度塊，則必然存在相應類型的入度塊／出度塊。圖4為DBLP中各對象分塊后的結(jié)構(gòu)圖，TP為對象主題。由此可以清楚的看出:采用當前對象級別建模思想構(gòu)建的對象圖，缺失了cited＿by類型的出度塊。

圖4 DBLP對象分塊后的結(jié)構(gòu)

2 ObjectMatch檢索方法

2.1 系統(tǒng)框架

圖5 ObjectMatch系統(tǒng)框架

系統(tǒng)框架主要分為預處理階段和查詢階段，如圖5所示。在預處理階段，關(guān)系數(shù)據(jù)庫中的元組按照主－外鍵聯(lián)系被組建為對象存入圖數(shù)據(jù)庫中，同時采用圖數(shù)據(jù)庫全文索引對檢索屬性 （search property，SP）進行索引。描述域在對象生成過程中被分塊為BD1，BD2，…，BDm，并按照各塊對對象的貢獻度設(shè)置相應的閾值α（BD）。存入圖數(shù)據(jù)庫的對象圖，是僅包含元組主鍵和對象SP的概要圖。

在查詢階段，檢索算法采用圖數(shù)據(jù)庫全文索引和用戶提交的查詢關(guān)鍵詞，對每個對象的SP進行評分，在描述域塊閾值的參與下對每個符合檢索條件的對象進行分數(shù)調(diào)節(jié)，從而得到每個對象的具體得分。利用倒排列表對每個對象進行排序，得到符合檢索條件的Top－K個對象。這Top－K個對象中的信息在關(guān)系數(shù)據(jù)庫交互模塊中被重新輸入到關(guān)系數(shù)據(jù)庫中，將從關(guān)系數(shù)據(jù)庫中返回的詳細信息進行整理，再輸出給用戶。

2.2 對象級別檢索

與關(guān)系數(shù)據(jù)庫類似，圖數(shù)據(jù)庫全文索引也需要設(shè)置所要索引的屬性名稱。在對象數(shù)據(jù)圖生成階段，除了將對象的主鍵存入對象主題域中之外，還要將需要查詢的對象對應的元組屬性中的內(nèi)容放入對象的SP中。例如，在DBLP數(shù)據(jù)集中對象的SP設(shè)置如表1所示。

表1 DBLP檢索屬性

對象的權(quán)重由兩部分組成:對象主題域分數(shù)和對象描述域分數(shù)。主題域分數(shù)由圖數(shù)據(jù)庫的全文索引fG來產(chǎn)生，這樣可以確保檢索結(jié)果必然包含查詢關(guān)鍵詞，保證查準率。其計算式如式 （1）所示

其中:Ti為對象Oi的對象主題域，k為輸入的查詢關(guān)鍵詞。

對象描述域分數(shù)由各塊對應的度數(shù)與相應的閾值來確定，采用啟發(fā)式的方式對匹配后的對象進行分數(shù)調(diào)節(jié)。定義一個比率γ表示各塊對于整個對象分數(shù)的作用關(guān)系。如下式所示

將該比率與1相加再取倒數(shù)，這樣可以保證該塊返回的分數(shù)在 （0，1）區(qū)間內(nèi)。將每塊返回的分數(shù)與對應塊的閾值相乘，再對各塊求和，就可以得到該對象描述域的分數(shù)，見式 （3）

把對象主題域分數(shù)與對象描述域分數(shù)相加，就可以得到對象的分數(shù)。如式 （4）所示

帶有分數(shù)的對象依次進入優(yōu)先隊列，在隊列中根據(jù)對象分數(shù)進行倒排，就可以獲得查詢對象的倒排優(yōu)先隊列。對象級別關(guān)鍵詞檢索方法偽代碼如圖6所示。

為了能夠更加全面的發(fā)揮對象級別關(guān)鍵詞檢索的優(yōu)勢，將盡可能多的信息反饋給用戶。算法將檢索得到的Top－K個對象中，包含在對象主題域與對象描述域的主鍵與關(guān)系數(shù)據(jù)庫進行交互，交互得到的詳細信息將被整理后返回給用戶。其中，Top－K結(jié)果展現(xiàn)方法偽代碼如圖7所示。

圖6 關(guān)鍵詞檢索方法

圖7 Top－K結(jié)果展現(xiàn)

3 實驗及結(jié)果分析

3.1 實驗描述

所用測試數(shù)據(jù)集為DBLP數(shù)據(jù)庫的子集，共包含4個表。其中，author表294062條記錄，paper表446407條記錄，write表997145條記錄，cite表110547條記錄。將ObjectMatch與Retune（DB＋IR）作對比，關(guān)系數(shù)據(jù)庫為MySQL，圖數(shù)據(jù)庫為Neo4j。運行環(huán)境為:Intel Core i5 2410MCPU 2.3GHz，4GB內(nèi)存，Windows 7Ultimate SP1 32位操作系統(tǒng)。

對于作者來說，我們只考慮該作者寫作的論文的數(shù)量，將論文發(fā)表最多且最匹配查詢關(guān)鍵詞的作者作為最優(yōu)結(jié)果。而對于論文來說，往往將該論文的被引用量作為重要指標，論文作者數(shù)量與參考文獻數(shù)量為相對弱一點的指標。形式上，我們認為一篇論文如果作者很多，該論文必然經(jīng)過了多人的認同，要比相同情況下作者數(shù)量少的論文重要性略高；如果一篇論文引用了很多參考文獻，該論文必然汲取了多人的成果，要比相同條件下引用參考文獻少的論文重要性略高。因此，對象描述域的塊閾值設(shè)置如表2所示。

表2 DBLP對象描述域的塊閾值

3.2 實驗結(jié)果分析

為了降低計算機的影響，將測量的十組實驗數(shù)據(jù)分別去掉最大與最小的一組，再進行平均后得到。如圖8所示，由于ObjectMatch與Retune（DB＋IR）都采用了全文索引進行檢索，因此其Top－K相關(guān)性都相對較高。隨著關(guān)鍵詞個數(shù)的增多，領(lǐng)域數(shù)據(jù)庫內(nèi)最相關(guān)的文獻被引用次數(shù)逐漸增多，故其相關(guān)性比Retune（DB＋IR）略高。

圖8 Top－K相關(guān)性對比

值得注意的是:現(xiàn)在圖數(shù)據(jù)庫尚不成熟，在一定程度上增加了使用圖數(shù)據(jù)庫存放對象圖環(huán)節(jié)所帶來的時間開銷，如圖9所示。隨著圖數(shù)據(jù)庫技術(shù)的慢慢成熟，該方法所產(chǎn)生的時間開銷必然會越來越少。應用圖數(shù)據(jù)庫存儲對象數(shù)據(jù)圖的優(yōu)勢在于:一次性抽取后若關(guān)系數(shù)據(jù)庫中的數(shù)據(jù)沒有改變，則下一次檢索就不需要再進行對象數(shù)據(jù)圖抽取。這樣極大的提高了對象數(shù)據(jù)圖的利用率，使對象數(shù)據(jù)圖的使用不再具有 “一次性”，從而顯著的提高了檢索效率。

圖9 對象圖抽取時間對比

若將對象圖生成階段省略，僅計算檢索時間，結(jié)果如圖10所示。當檢索關(guān)鍵詞個數(shù)為1時，ObjectMatch檢索時間略高于Retune（DB＋IR）。由于Retune（DB＋IR）僅計算一個關(guān)鍵詞的TF／IDF，時間會較短。當關(guān)鍵詞個數(shù)為2個以上時，ObjectMatch算法的檢索時間會明顯降低，因為圖數(shù)據(jù)庫中全文索引能夠匹配所有關(guān)鍵詞的對象個數(shù)會越來越少，而Retune（DB＋IR）雖然會因關(guān)系數(shù)據(jù)庫全文索引匹配的元組數(shù)目降低而在DB分數(shù)計算中節(jié)省時間，但計算多關(guān)鍵詞的TF／IDF（IR分數(shù)計算階段）會耗費算法大量的時間。按現(xiàn)在用戶的檢索習慣一般會輸入2－5個關(guān)鍵詞，這樣Retune（DB＋IR）就無法滿足用戶的檢索需求。由于Retune（DB＋IR）為元組級別關(guān)鍵詞檢索，返回的結(jié)果信息量少。而ObjectMatch采用對象級別關(guān)鍵詞檢索，考慮了對象圖的內(nèi)部結(jié)構(gòu)，返回結(jié)果的信息要比Retune（DB＋IR）全面得多。

圖10 Top－10檢索時間對比

4 結(jié)束語

本文提出了將圖數(shù)據(jù)庫嵌入到應用程序中，結(jié)合圖數(shù)據(jù)庫與關(guān)系數(shù)據(jù)庫解決關(guān)系數(shù)據(jù)庫信息檢索的思想。該方法利用圖數(shù)據(jù)庫靈活的圖模型，存儲和管理大規(guī)模對象圖，解決了大規(guī)模數(shù)據(jù)條件下關(guān)系數(shù)據(jù)庫信息檢索的內(nèi)外存管理問題。把該方法與使用關(guān)系數(shù)據(jù)庫全文索引且效果較好的Retune（DB＋IR）進行對比，驗證了該方法在關(guān)系數(shù)據(jù)庫信息檢索時具有較高的查準率，且在多關(guān)鍵詞檢索時效率明顯。雖然在對象圖抽取時的時間開銷較大，但隨著圖數(shù)據(jù)庫技術(shù)的日趨成熟，圖數(shù)據(jù)庫在關(guān)系數(shù)據(jù)庫信息檢索中的應用必將會越來越廣泛。

[1]Luo Yi，Lin Xuemin，Wang Wei，et al.Spark:top－k keyword query in relational databases[C]／／ACM Int Conf on Management of Data，2007:115－126.

[2]Luo Yi，Wang Wei，Lin Xuemin，et al.Spark2:Top－k keyword query in relational databases[C]／／IEEE Trans Knowl Data Eng，2011，23 （12）:1763－1780.

[3]Ding B，Yu J X，Wang S，et al.Finding top－k min－cost connected trees in databases[C]／／ICDE，2007:836－845.

[4]He Hao，Wang Haixun，Yang Jun，et al.BLINKS:Ranked keyword searches on graphs[C]／／ACM Int Conf on Management of Data，2007:305－316.

[5]Li G，Ooi B C，F(xiàn)eng J，et al.EASE:An effective 3－in－1keyword search method for unstructured，semi－structured and structured data[C]／／SIGMOD，2008:903－914.

[6]Golenberg K，Kimelfeld B，Sagiv Y.Keyword proximity search in complex data graphs[C]／／SIGMOD，2008:927－940.

[7]Dalvi B B，Kshirsagar M，Sudarshan S.Keyword search on external memory data graphs[C]／／PVLDB，2008 （1）:1189－1204.

[8]Kasneci G，Ramanth M，Sozio M，et al.STAR:Steiner tree approximation in relationship graphs[C]／／ICDE，2009:868－879.

[9]Dalvi B B，Kshirsagar M，Sudarshan S.Keyword search on external memory data graphs[C]／／Auckland，New Zealand:VLDB，2008:1189－1204.

[10]ZHANG Jun，SHAO Renjun，ZENG Yiming.Research on object－level information retrieval over relational databases[C]／／Computer Science，2012，39 （1）:142－147 （in Chinese）.[張俊，邵仁俊，曾一鳴.對象級別的關(guān)系數(shù)據(jù)庫信息檢索技術(shù)研究[J].計算機科學，2012，39 （1）:142－147.]

[11]Zhang Jun，Shao Renjun.Object－level data model for keyword search over relational databases[C]／／The 7th International Conference on Frontier of Computer Science and Technology，2011.

[12]Chad Vicknair，Michael Macias，Zhendong Zhao，et al.A comparison of a graph database and a relational database[C]／／ACMSE Proceedings of the 48th Annual Southeast Regional Conference.New York，NY，USA:ACM，2010.

[13]Jiang Haoliang，Wang Haixun，Philip S Yu，et al.GString:A novel approach for efficient search in graph databases[C]／／Proceedings of the 23rd Inter－national Conference on Data Engineering，2007.

[14]Zou Lei，Chen Lei，Tamer zsu M.DistanceJoin:Pattern match query in a large graph database[C]／／VLDB，2009.