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

于素華，張 俊，高 燕

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

0 引 言

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

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

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

1 模型構(gòu)建

1.1 建模信息缺失

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

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

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

圖2 DBLP對(duì)象

1.2 描述域分塊

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

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

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

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

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

2 ObjectMatch檢索方法

2.1 系統(tǒng)框架

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

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

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

2.2 對(duì)象級(jí)別檢索

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

表1 DBLP檢索屬性

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)描述

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

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

表2 DBLP對(duì)象描述域的塊閾值

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

圖9 對(duì)象圖抽取時(shí)間對(duì)比

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

圖10 Top－10檢索時(shí)間對(duì)比

4 結(jié)束語(yǔ)

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

[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）.[張俊，邵仁俊，曾一鳴.對(duì)象級(jí)別的關(guān)系數(shù)據(jù)庫(kù)信息檢索技術(shù)研究[J].計(jì)算機(jī)科學(xué)，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.