用于關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢的基于劃分的候選網(wǎng)絡(luò)生成算法

周 翔 金遠(yuǎn)平

(東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京211189)

隨著越來(lái)越多的文本數(shù)據(jù)存儲(chǔ)到關(guān)系數(shù)據(jù)庫(kù)中，關(guān)系數(shù)據(jù)庫(kù)關(guān)鍵詞查詢逐漸成為新的研究熱點(diǎn).一個(gè)關(guān)鍵詞的查詢分為相關(guān)元組獲取、候選網(wǎng)絡(luò)(candidate network，CN)［1］生成和候選網(wǎng)絡(luò)執(zhí)行3個(gè)階段.由于候選網(wǎng)絡(luò)執(zhí)行階段是整個(gè)系統(tǒng)的性能瓶頸，所以一直是重點(diǎn)關(guān)注的對(duì)象［1-6］，而對(duì)前2個(gè)階段算法的改進(jìn)很少.文獻(xiàn)［7-8］最先提出通過(guò)廣度優(yōu)先查詢方法生成所有組合關(guān)鍵詞的候選網(wǎng)絡(luò).但是組合關(guān)鍵詞的候選網(wǎng)絡(luò)數(shù)量會(huì)隨著網(wǎng)絡(luò)大小成指數(shù)增長(zhǎng)，執(zhí)行時(shí)間急劇上升［1，9］.Markowetz等［10］提出了減少中間結(jié)果和避免同構(gòu)檢查的算法.文獻(xiàn)［11］利用半連接和連接操作減少候選網(wǎng)絡(luò)連接計(jì)算，但是實(shí)驗(yàn)表明候選網(wǎng)絡(luò)的數(shù)量依然很龐大，消耗了大量的查詢結(jié)果生成時(shí)間［2］.文獻(xiàn)［1］在文獻(xiàn)［7］的基礎(chǔ)上，對(duì)候選網(wǎng)絡(luò)生成算法進(jìn)行了改進(jìn)，使之生成完備的基于查詢的候選網(wǎng)絡(luò).之后查詢結(jié)果的生成效果和效率受到廣泛研究，而對(duì)候選網(wǎng)絡(luò)生成算法的改進(jìn)越來(lái)越少，多數(shù)都采用文獻(xiàn)［1，7，10］的算法.

然而對(duì)候選網(wǎng)絡(luò)生成階段算法的改進(jìn)同樣也可以很大程度地提高關(guān)鍵詞查詢系統(tǒng)的性能.因此，本文通過(guò)對(duì)候選網(wǎng)絡(luò)生成過(guò)程［1］的分析，提出了基于劃分的候選網(wǎng)絡(luò)生成策略，并設(shè)計(jì)了高效的候選網(wǎng)絡(luò)生成算法.同時(shí)通過(guò)改寫(xiě)圖的同構(gòu)方法生成無(wú)冗余的候選網(wǎng)絡(luò)集合.最后，在DBLP［12］數(shù)據(jù)集上進(jìn)行了大量的算法對(duì)比實(shí)驗(yàn)，結(jié)果表明，本文提出的高效候選網(wǎng)絡(luò)生成算法的性能較基于廣度優(yōu)先擴(kuò)展算法有大幅度的提升.

1 候選網(wǎng)絡(luò)生成算法［1］

1.1 基于廣度優(yōu)先擴(kuò)展的候選網(wǎng)絡(luò)生成算法

文獻(xiàn)［1］提出的基于查詢的候選網(wǎng)絡(luò)數(shù)比文獻(xiàn)［7，10］基于關(guān)鍵詞的少得多，因此本文將文獻(xiàn)［1］中的算法作為對(duì)比算法.將數(shù)據(jù)庫(kù)模式(database schema)、最大候選網(wǎng)絡(luò)尺寸M和非自由元組集集合(the set of non-free tuple set，STS)作為輸入，輸出候選網(wǎng)絡(luò)集合(candidate network set，SCN).算法首先由數(shù)據(jù)庫(kù)模式圖GS和非自由元組集集合STS構(gòu)造元組集無(wú)向圖GTS，非自由元組集RQ和自由元組集Rφ構(gòu)成點(diǎn)的集合，即元組集所屬關(guān)系間的主外鍵聯(lián)系構(gòu)成邊的集合，即Ri和 Rj存在主外鍵聯(lián)系}.根據(jù) DBLP［11］數(shù)據(jù)集構(gòu)造的數(shù)據(jù)庫(kù)模式圖如圖1所示.圖中，表Person存儲(chǔ)編輯和作者信息;表Publication存儲(chǔ)出版物信息;表Publisher存儲(chǔ)出版社信息;表Series存儲(chǔ)出版物的類別;表Article存儲(chǔ)文章信息;表Cite存儲(chǔ)文章之間引用的信息;表Write存儲(chǔ)文章和作者之間關(guān)系;表Edit存儲(chǔ)出版物和編輯之間關(guān)系.假設(shè)STS由非自由元組集PersonQ和ArticleQ構(gòu)成，則對(duì)應(yīng)的元組集無(wú)向圖GTS如圖2所示.

圖1 DBLP數(shù)據(jù)庫(kù)模式圖

圖2 元組集無(wú)向圖GTS

構(gòu)造好GTS之后，首先選取非自由元組集(尺寸為1的連接元組集圖)作為算法的起始節(jié)點(diǎn)集，然后利用圖的廣度優(yōu)先遍歷思想不斷地?cái)U(kuò)展已生成的連接元組集圖，最后返回符合候選網(wǎng)絡(luò)條件的連接元組集圖［1］.為了敘述方便，稱連接元組集圖中度(出、入度之和)為1的元組集為葉子節(jié)點(diǎn).候選網(wǎng)絡(luò)的生成過(guò)程見(jiàn)表1.

表1 候選網(wǎng)絡(luò)生成過(guò)程

由于表1中“/”后的編號(hào)相同的連接元組集圖是重復(fù)的，因此，該算法會(huì)產(chǎn)生大量、重復(fù)的候選網(wǎng)絡(luò).

1.2 基于劃分策略的候選網(wǎng)絡(luò)生成算法

分析基于廣度優(yōu)先擴(kuò)展的候選網(wǎng)絡(luò)生成算法，可以發(fā)現(xiàn)，中間結(jié)果中同一個(gè)連接元組集圖可能會(huì)被生成多次.例如圖2中，由2個(gè)元組集構(gòu)成(尺寸為2)的ArticleQ←PublicationQ就可分別由尺寸為1的ArticleQ和PublicationQ擴(kuò)展生成.這樣SCN中就包含2個(gè)ArticleQ←PublicationQ，形成了冗余.當(dāng)元組集圖的尺寸增大時(shí)，SCN將出現(xiàn)很大的冗余，不僅消耗了大量?jī)?nèi)存資源，也嚴(yán)重降低了算法的效率.可見(jiàn)，在候選網(wǎng)絡(luò)生成算法中消除候選網(wǎng)絡(luò)冗余具有重要意義.

正因?yàn)槌叽鐬閕－1的、不同的連接元組集圖可以產(chǎn)生相同的尺寸為i的連接元組集圖，才導(dǎo)致冗余的出現(xiàn)，所以若能夠使尺寸為i的連接元組集圖只被生成一次，冗余就得到了解決.本文通過(guò)特定的劃分策略，將生成尺寸為i的連接元組集圖的職責(zé)指定給某個(gè)i－1的連接元組集圖.這樣就從源頭上解決了冗余的產(chǎn)生.

首先給元組集無(wú)向圖GTS中每一個(gè)元組集指定一個(gè)唯一的數(shù)值編號(hào)0，1，2，….非自由元組集最后編號(hào).圖2括號(hào)中的值為元組集的編號(hào).然后將尺寸為i的連接元組集圖的生成職責(zé)指定為刪除了最小編號(hào)的葉子節(jié)點(diǎn)所剩下的尺寸為i－1的連接元組集圖.按照以上策略，生成的候選網(wǎng)絡(luò)能夠保證其完備性.

定理1基于劃分策略的候選網(wǎng)絡(luò)生成算法可以保證生成候選網(wǎng)絡(luò)的完備性.

證明 ① 算法覆蓋了所有非自由元組集，所以，可以生成所有尺寸為1的連接元組集圖.② 設(shè)算法可以生成所有尺寸為i－1(i＞1)的連接元組集圖.因?yàn)槌叽鏸的連接元組集圖必定是由其去除一個(gè)葉子節(jié)點(diǎn)后所剩的尺寸為i－1的連接元組集圖擴(kuò)展生成.而基于劃分策略的算法保證尺寸i的連接元組集圖是由尺寸為i－1的連接元組集圖擴(kuò)展最小編號(hào)的葉子節(jié)點(diǎn)構(gòu)成的，從而保證了尺寸i的連接元組集圖可由算法生成.證畢.

算法1基于劃分策略的候選網(wǎng)絡(luò)生成算法

算法1首先以非自由元組集開(kāi)始擴(kuò)展，即擴(kuò)展前的連接元組集圖集合為{8，9}.擴(kuò)展后的連接元組集圖集合為{8→0，8←2，8→7，9→5，9→7}.按照劃分策略，剛添加的葉子節(jié)點(diǎn)的編號(hào)應(yīng)該最小，如:2←8→0是由8→0擴(kuò)展的，但是剛添加的編號(hào)為2的葉子節(jié)點(diǎn)不是最小的葉編號(hào)(存在編號(hào)為0的葉子節(jié)點(diǎn))，所以不滿足基于劃分策略的擴(kuò)展過(guò)程，可以刪除.表1中帶有“×”標(biāo)記的連接元組集圖為算法執(zhí)行中的刪除結(jié)果.

連接元組集圖中編號(hào)并不唯一，會(huì)出現(xiàn)多個(gè)最小的葉子節(jié)點(diǎn)，所以算法1并不能完全消除冗余.盡管如此，定理1的證明表明，含j(1＜j＜i)個(gè)葉子的連接元組集圖存在j種由尺寸i－1生成尺寸i的方案，因而至少產(chǎn)生j－1倍冗余.所以可以說(shuō)明基于劃分的候選網(wǎng)絡(luò)生成算法較文獻(xiàn)［1］算法有較大改進(jìn).實(shí)驗(yàn)結(jié)果表明，算法1可以很大程度地減少了冗余，避免了指數(shù)量級(jí)的中間結(jié)果的檢查和擴(kuò)展.

1.3 冗余候選網(wǎng)絡(luò)的消除

由于算法1生成的候選網(wǎng)絡(luò)集合存在冗余，而候選網(wǎng)絡(luò)執(zhí)行階段需要無(wú)冗余的候選網(wǎng)絡(luò)集合，所以需要消除冗余.本節(jié)的冗余候選網(wǎng)絡(luò)消除算法是在文獻(xiàn)［13］中圖同構(gòu)算法的基礎(chǔ)上，利用候選網(wǎng)絡(luò)的同一性消除重復(fù)的網(wǎng)絡(luò).因?yàn)楹蜻x網(wǎng)絡(luò)的生成采用廣度優(yōu)先方式，且元組集的編號(hào)是允許重復(fù)的，所以2個(gè)候選網(wǎng)絡(luò)的同一性判斷需要在圖同構(gòu)的判別過(guò)程中檢測(cè)元組集編號(hào)是否相同.

定義1(候選網(wǎng)絡(luò)的同一性)對(duì)于尺寸相同的候選網(wǎng)絡(luò)，如果CN1中每個(gè)節(jié)點(diǎn)都可以找到元組集編號(hào)相同的CN2中的唯一對(duì)應(yīng)節(jié)點(diǎn)，且所有對(duì)應(yīng)節(jié)點(diǎn)間的連接關(guān)系完全一致，就稱CN1和CN2是相同的候選網(wǎng)絡(luò).

算法2給出了冗余候選網(wǎng)絡(luò)消除算法.算法以尺寸相同的一組候選網(wǎng)絡(luò)作為輸入.兩兩比較，刪除重復(fù)的候選網(wǎng)絡(luò).考慮2個(gè)尺寸為s的候選網(wǎng)絡(luò)CN1和 CN2，算法首先構(gòu)造檢測(cè)矩陣 Ms×s=(mi，j)s×s，其中

然后，對(duì)CN1中的節(jié)點(diǎn)按照其度數(shù)降序排列，并利用矩陣Ms×s依次檢查其與CN2中節(jié)點(diǎn)是否存在一一對(duì)應(yīng)關(guān)系，若所有節(jié)點(diǎn)都一一對(duì)應(yīng)，則2個(gè)候選網(wǎng)絡(luò)是相同的，刪除其中任意一個(gè)即可.

算法2冗余候選網(wǎng)絡(luò)消除算法

定理2已知CN1中的節(jié)點(diǎn)i與CN2中的節(jié)點(diǎn)j對(duì)應(yīng)，則CN1中節(jié)點(diǎn)p與CN2中節(jié)點(diǎn)k對(duì)應(yīng)的必要條件是:節(jié)點(diǎn)p和節(jié)點(diǎn)i間的關(guān)系與節(jié)點(diǎn)k與節(jié)點(diǎn)j間的關(guān)系一致，這里的關(guān)系包括邊的存在和方向.

證明 若節(jié)點(diǎn)p，k和節(jié)點(diǎn)i，j是2個(gè)候選網(wǎng)絡(luò)間的2對(duì)對(duì)應(yīng)點(diǎn)，則根據(jù)相同候選網(wǎng)絡(luò)的定義，顯然有節(jié)點(diǎn)p和i間的關(guān)系與節(jié)點(diǎn)k與j間的關(guān)系一致的結(jié)論.所以必要性成立.

但是，節(jié)點(diǎn)p和i間的關(guān)系與節(jié)點(diǎn)k和j間的關(guān)系一致卻不能推導(dǎo)出節(jié)點(diǎn)p和k是對(duì)應(yīng)點(diǎn).因?yàn)楹蜻x網(wǎng)絡(luò)中會(huì)存在元組集編號(hào)相同的節(jié)點(diǎn)，只有CN1中所有點(diǎn)都找到一一對(duì)應(yīng)的點(diǎn)之后才能確定對(duì)應(yīng)關(guān)系.所以充分性不成立.證畢.

定理2的非對(duì)應(yīng)點(diǎn)的判定條件為:在確定CN1中節(jié)點(diǎn)i的對(duì)應(yīng)點(diǎn)是CN2中節(jié)點(diǎn)j的情況下，若節(jié)點(diǎn)p和i間的關(guān)系與節(jié)點(diǎn)k和j間的關(guān)系不一致，則節(jié)點(diǎn)p和k必定不是對(duì)應(yīng)點(diǎn).

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

本實(shí)驗(yàn)從DBLP［12］數(shù)據(jù)集中抽取數(shù)據(jù)，構(gòu)造了如圖1的數(shù)據(jù)庫(kù)模式圖.其中5個(gè)含文本屬性的關(guān)系分別為:Person，Publisher，Series，Publication 和Article.實(shí)驗(yàn)假設(shè)這5個(gè)關(guān)系的非自由元組集都非空，從而可以廣泛地測(cè)試候選網(wǎng)絡(luò)生成算法的性能.算法使用 C#語(yǔ)言，在.NET 4.0平臺(tái)上實(shí)現(xiàn)，采用Windows XP操作系統(tǒng)，Intel Pentium雙核，主頻1.6 GHz，1G內(nèi)存.本實(shí)驗(yàn)分別固定候選網(wǎng)絡(luò)最大尺寸和關(guān)鍵詞個(gè)數(shù)，對(duì)候選網(wǎng)絡(luò)生成算法［1］(簡(jiǎn)稱GCN)、算法1和算法2的性能進(jìn)行了測(cè)試.表2分別展示了關(guān)鍵詞個(gè)數(shù)為3和4時(shí)，GCN和算法1隨著最大候選網(wǎng)絡(luò)尺寸M的變化而生成的候選網(wǎng)絡(luò)數(shù)量，以及算法2所計(jì)算的無(wú)冗余的候選網(wǎng)絡(luò)數(shù).表3為固定候選網(wǎng)絡(luò)最大尺寸為7時(shí)，各個(gè)算法生成的候選網(wǎng)絡(luò)數(shù)量.

此外，實(shí)驗(yàn)還對(duì)比了候選網(wǎng)絡(luò)生成階段執(zhí)行時(shí)間.圖3和圖4分別為關(guān)鍵詞個(gè)數(shù)為4和最大候選網(wǎng)絡(luò)尺寸為7時(shí)，候選網(wǎng)絡(luò)生成階段執(zhí)行時(shí)間與參數(shù)的關(guān)系.其中執(zhí)行時(shí)間為候選網(wǎng)絡(luò)生成時(shí)間與冗余候選網(wǎng)絡(luò)消除時(shí)間之和.

表2 不同關(guān)鍵詞個(gè)數(shù)生成的候選網(wǎng)絡(luò)的數(shù)目

表3 CN尺寸為7時(shí)生成的候選網(wǎng)絡(luò)數(shù)

圖3 關(guān)鍵詞個(gè)數(shù)為4時(shí)的執(zhí)行時(shí)間

圖4 最大候選網(wǎng)絡(luò)尺寸為7時(shí)的執(zhí)行時(shí)間

由表2、表3和圖3、圖4可以清晰看出，當(dāng)關(guān)鍵詞個(gè)數(shù)與最大候選網(wǎng)絡(luò)尺寸較小時(shí)，連接元組集圖可擴(kuò)展的選擇較少，2種算法所生成的候選網(wǎng)絡(luò)數(shù)量相差不大，執(zhí)行時(shí)間相近.隨著關(guān)鍵詞個(gè)數(shù)與最大候選網(wǎng)絡(luò)尺寸的不斷增大，GCN算法生成龐大的冗余候選網(wǎng)絡(luò)，消耗了大量的空間和時(shí)間;而算法1生成的候選網(wǎng)絡(luò)的冗余較小，執(zhí)行時(shí)間增長(zhǎng)緩慢.可見(jiàn)，在數(shù)據(jù)量很大的情況下，算法1有著非常明顯的優(yōu)勢(shì).據(jù)保守估算，當(dāng)最大候選網(wǎng)絡(luò)平均尺寸為7，查詢關(guān)鍵詞平均個(gè)數(shù)為4時(shí)，采用算法1至少可以減少10倍的冗余.

3 結(jié)語(yǔ)

本文在對(duì)候選網(wǎng)絡(luò)的生成過(guò)程進(jìn)行觀察的基礎(chǔ)上，提出了一種基于劃分策略的候選網(wǎng)絡(luò)生成算法.實(shí)驗(yàn)結(jié)果表明，基于劃分策略的候選網(wǎng)絡(luò)生成算法較盲目的廣度優(yōu)先擴(kuò)展的生成算法能夠減少大幅度冗余，有效地提升了整個(gè)候選網(wǎng)絡(luò)生成階段的性能.

目前，本文基于劃分策略的候選網(wǎng)絡(luò)生成算法還不能完全消除冗余候選網(wǎng)絡(luò)的產(chǎn)生，需要借助候選網(wǎng)絡(luò)消除算法做進(jìn)一步的過(guò)濾，因此，一個(gè)能夠完全消除冗余候選網(wǎng)絡(luò)產(chǎn)生的高效算法是需要進(jìn)一步研究的方向.

References)

［1］Hristidis V，Gravano L，Papakonstantinou Y.Efficient IR-style keyword search over relational databases［C］//Proceedings of the 29th VLDB Conference.Berlin，Germany，2003:850-861.

［2］Qin Lu，Yu J X，Chang Liujun.Ten thousand SQLs:parallel keyword queries computing［C］//Proceedings of the VLDB Endowment.Singapore，2010:58-69.

［3］Luo Yi，Lin Xuemin，Wang Wei，et al.SPARK:top-k keyword query in relational databases［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Beijing，China，2007:115-126.

［4］Liu Fang，Yu C，Meng Weiyi，et al.Effective keyword search in relational databases［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Chicago，USA，2006:563-574.

［5］Qin Lu，Yu J X，Chang Liujun.Keyword search in databases:the power of rdbms［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Rhode Island，USA，2009:681-694.

［6］Ding B，Yu J X，Wang S，et al.Finding top-k mincost connected trees in databases［C］//Proceedings of the 23rd International Conference on Data Engineering.Istanbul，Turkey，2007:836-845.

［7］Hristidis V，Papakonstantinou Y.DISCOVER:keyword search in relational databases［C］//Proceedings of the 28th VLDB Conference.Hong Kong，China，2002:670-681.

［8］Agrawal S，Chaudhuri S，Das G.DBXplorer:a system for keyword-based search overrelationaldatabases［C］//Proceedings of the 18th International Conference on Data Engineering.California，USA，2002:5-16.

［9］Yu J X，Qin Lu，Chang Liujun.Keyword search in databases［M］.Washington，USA:Morgan and Claypool Publishers，2010:12-21.

［10］Markowetz A，YangYin，Papadias D.Keyword search on relational data streams［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Beijing，China，2007:605-616.

［11］Qin Lu，Yu J X，Chang Liujun，et al.Scalable keyword search on large data streams［C］//Proceedings of the 25th International Conference on Data Engineering.Shanghai，China，2009:1199-1202.

［12］Ley M，Herbstritt M，Hoffmann O，et al.The DBLP Computer Science Bibliography［EB/OL］.(2011-05-01)［2011-05-20］.http://www.informatik.uni-trier.de/～ ley/db/.

［13］Ullman J R.An algorithm for subgraph isomorphism［J］.Journal of the Association for Computing Machinary，1976，23(1):31-42.