支持近似圖查詢的Why-Not問題解釋方法*

賀 丹，宗傳玉，王 斌，李金旭，楊曉春

東北大學 計算機科學與工程學院，沈陽 110819

支持近似圖查詢的Why-Not問題解釋方法*

賀 丹，宗傳玉，王 斌，李金旭，楊曉春+

東北大學 計算機科學與工程學院，沈陽 110819

why-not問題是為查詢結(jié)果中的缺失元組找到合理的解釋。解決數(shù)據(jù)庫查詢中的why-not問題不僅能夠幫助用戶更好地理解查詢，而且能夠提高數(shù)據(jù)庫的質(zhì)量和可用性。為了提高圖數(shù)據(jù)庫的可用性，提出了支持近似圖查詢的why-not問題解釋方法。該解釋方法不僅闡明了為什么why-not問題沒有出現(xiàn)在查詢結(jié)果中，而且給出了一些修改初始查詢圖的建議，使得why-not問題能夠出現(xiàn)在修改后的查詢圖的查詢結(jié)果中。該算法分兩部分完成：第一部分為候選修改操作生成階段，首先利用邊頻率信息提出候選操作集生成基本算法，接著利用圖分解操作提出候選操作集生成改進算法，得到修改初始查詢圖的候選操作集；第二部分基于對查詢圖修改操作數(shù)最少的代價模型，分別采用貪心算法和回溯法選取候選操作，貪心算法設(shè)計了合理的貪心函數(shù)，回溯法構(gòu)建了回溯剪枝樹，并提出三種剪枝策略執(zhí)行剪枝操作，最終選取的候選操作集即為支持近似圖查詢的why-not問題的合理解釋。實驗表明，該方法可以快速有效地為近似圖查詢中的why-not問題提供合理解釋。

近似圖查詢；why-not問題；回溯法；剪枝策略

1 引言

目前，數(shù)據(jù)庫系統(tǒng)在資源存儲和查詢處理方面都十分高效。然而，隨著用戶需求的不斷提升，一方面，用戶對最終的查詢結(jié)果不夠滿意；另一方面，他們也想知道為什么現(xiàn)有的數(shù)據(jù)庫系統(tǒng)沒有返回他們想要的結(jié)果，這類問題被稱為why-not問題[1]。因此，回答數(shù)據(jù)庫系統(tǒng)中的why-not問題不僅能夠滿足數(shù)據(jù)庫系統(tǒng)用戶的應(yīng)用需求，同時也是提高數(shù)據(jù)庫系統(tǒng)質(zhì)量和可用性的重要途徑。近期，why-not問題已經(jīng)引起了數(shù)據(jù)庫研究者們的廣泛關(guān)注[1-4]，雖然已經(jīng)取得了一些初步的研究成果，但是研究體系尚未成熟，仍有許多問題值得研究。

在現(xiàn)實世界的許多領(lǐng)域可以用圖來表示各種復(fù)雜數(shù)據(jù)實體以及實體之間的關(guān)系。例如，在圖像處理領(lǐng)域[5-6]，用關(guān)系圖來表示圖像內(nèi)容，用頂點標號來表示圖像中某一區(qū)域的特征；在email通信網(wǎng)絡(luò)，用頂點表示具體的email地址，邊表示兩個email地址之間的通信往來。盡管在圖數(shù)據(jù)查詢領(lǐng)域已經(jīng)有不少研究，但是大部分研究都集中于圖的精確匹配查詢[7]。雖然精確圖查詢能夠準確無誤地找到與查詢圖匹配的圖，但是在實際應(yīng)用中，數(shù)據(jù)庫中存儲的圖數(shù)據(jù)結(jié)構(gòu)復(fù)雜，導致精確圖匹配方法查詢效率較低。因此，近年來近似圖查詢受到越來越多研究者的關(guān)注。

一般來說，圖數(shù)據(jù)庫可以分成兩種：第一種是事務(wù)型圖數(shù)據(jù)庫，該種類型的數(shù)據(jù)庫中存儲了大量的圖結(jié)構(gòu)，邊與節(jié)點信息相對簡單；第二種是社交網(wǎng)絡(luò)型圖數(shù)據(jù)庫，該類數(shù)據(jù)庫中只存儲了一張圖，邊與節(jié)點信息復(fù)雜。本文的研究重點為第一種類型，將在第一種類型的數(shù)據(jù)庫上進行近似圖查詢，并為whynot問題提供合理解釋。

近似圖查詢是圖數(shù)據(jù)庫管理系統(tǒng)實現(xiàn)的重要功能，然而在實際應(yīng)用中，用戶常常對數(shù)據(jù)庫管理系統(tǒng)返回的圖查詢結(jié)果不夠滿意。為提高圖數(shù)據(jù)庫系統(tǒng)的質(zhì)量和可用性，解決近似圖查詢過程中的why-not問題就顯得尤為重要。

為了更好地說明解釋近似圖查詢過程中的whynot問題的實際應(yīng)用價值，舉例如下應(yīng)用場景：當化學分子研究者在研究分子結(jié)構(gòu)與化學性質(zhì)的關(guān)系時，化學系統(tǒng)中包含的化學物質(zhì)為CH4、C2H6、C2H2、C2H6O，當他查詢與C2H6分子結(jié)構(gòu)相似的化學物質(zhì)時，系統(tǒng)返回的查詢結(jié)果為C2H6和C2H6O，這時他可能想知道為什么C2H2沒有出現(xiàn)在查詢結(jié)果中，是否有更合理的查詢讓查詢結(jié)果中包含C2H2。在這種場景下，合理地解釋用戶提出的why-not問題對其研究工作有重要意義?，F(xiàn)將該問題形式化舉例如下。

例1如圖1所示，給定圖數(shù)據(jù)集G={g1,g2,g3}和查詢圖q。當圖差異閾值設(shè)定為δ=3時，求得λ(g1,q)=4+5-2×3=3，λ(g2,q)=4+5-2×4=1，λ(g3,q)=5+5-2×3=4，從而近似圖查詢結(jié)果為R={g1,g2}。文中近似圖查詢返回圖數(shù)據(jù)集中與查詢圖的差異小于等于給定閾值的圖的集合，圖差異求解方法參照文獻[8]。

Fig.1 Aset of undirected graphG={g1,g2,g3}and query graphq圖1 無向圖集合G={g1,g2,g3}及查詢圖q

此時，數(shù)據(jù)庫查詢用戶可能會提出這樣的問題：為什么圖g3沒有出現(xiàn)在近似圖查詢結(jié)果R中？這就是近似圖查詢過程中的why-not問題。

通過分析發(fā)現(xiàn)，例1中進行近似圖查詢時，查詢圖q與圖g3的差異為4，大于閾值δ=3，因而查詢結(jié)果中不包含圖g3。為使得查詢結(jié)果R中包含g3，可以通過對查詢圖執(zhí)行增加邊(b,d)的操作，使查詢圖q與圖g3之間的差異小于等于δ，從而讓圖g3出現(xiàn)在查詢結(jié)果中。

依據(jù)上述分析，為了滿足用戶提出的查詢需求，本文為支持近似圖查詢的why-not問題提出了高效的解釋方法。本文的主要貢獻如下：

（1）提出了支持近似圖查詢的why-not問題解釋框架。

（2）針對用戶提出的why-not問題，結(jié)合近似圖查詢原始結(jié)果集，通過統(tǒng)計每條邊出現(xiàn)的頻率，提出了候選操作集生成基本算法，并得到why-not問題解釋候選操作集。

（3）針對候選操作集生成基本算法中的不足，通過對圖結(jié)構(gòu)進行分解操作，提出了候選操作集生成改進算法，從而得到why-not問題的解釋候選操作集。該改進算法減小了操作代價，提高了why-not問題的解釋效率。

（4）在候選操作集的基礎(chǔ)上，結(jié)合對查詢圖修改操作數(shù)要求最少的代價模型，分別利用貪心策略和回溯剪枝策略，從候選操作集中選取部分候選操作，并對最初的查詢圖做出相應(yīng)修改，從而合理解釋why-not問題。

（5）在真實數(shù)據(jù)集和合成數(shù)據(jù)集上進行了大量的實驗測試和分析，驗證了本文方法的可行性和高效性。

2 相關(guān)工作

2.1 why-not問題

目前，存在多種why-not問題解釋模型，文獻[1-4]闡述了不同數(shù)據(jù)和查詢集中存在的why-not問題。文獻[1]中Chapman等人提出了識別出使why-not元組過濾掉的操作的方法。Tran和Chan以Chapman的工作為基礎(chǔ)，提出了通過從用戶的反饋中收集whynot元組，執(zhí)行查詢重寫操作，從而解釋SPJA（select project join aggregate）查詢中的why-not問題[2]。文獻[3]中，He等人依據(jù)用戶的偏好來修改k值和權(quán)值來解釋top-k查詢上的why-not問題。文獻[4]解決了反向skyline查詢中的why-not問題。文獻[9-10]提出的算法可以快速有效地為why-not問題返回最小化解釋。文獻[11]中Islam等人提出了一種叫作FlexIQ（flexible interactive querying）的 SPJ（select project join）查詢重寫架構(gòu)，它充分考慮了用戶反饋的why和why-not問題。文獻[12]實現(xiàn)了一個基于因果關(guān)系分析查詢處理的框架模型。文獻[13]提出了基于查詢修改的解釋模型，通過分析why-not問題和查詢語句，得到一個新的查詢語句，使得新的查詢語句的查詢結(jié)果包括原來的查詢結(jié)果和why-not數(shù)據(jù)。文獻[14-15]提到的數(shù)據(jù)世系對缺失結(jié)果的解釋提供了依據(jù)。文獻[16]利用初始查詢中的關(guān)鍵字來解決Web文本查詢中的why-not問題。近期，針對近似圖匹配過程中的why-not問題，文獻[8]利用圖的星型結(jié)構(gòu)表示方式，提出了兩階段解釋算法，但是該文用星型結(jié)構(gòu)存儲圖信息，存儲空間較大，因而解釋效率有待提高。

上述文獻為本文的why-not問題解釋提供了參考依據(jù)，但是與前人的研究工作不同，本文從修改原始查詢圖的角度出發(fā)，將研究重點放在如何解釋用戶所提出的why-not問題。

2.2 近似圖查詢

根據(jù)圖查詢匹配的精確程度，可以將圖查詢分為精確圖查詢和近似圖查詢。本文主要研究近似圖查詢。

針對近似圖查詢問題，Yan等人在2005年提出了一種基于特征的結(jié)構(gòu)化過濾算法Grafil[17]。該方法結(jié)合基于結(jié)構(gòu)查詢模式的特點，采用NP難問題的最大集合覆蓋方法，提高了時間效率問題。Yan等人在Grafil的基礎(chǔ)上于2006年提出了PIS（partition-based graph index and search）算法[18]，在圖數(shù)據(jù)庫中建立了基于片段的索引。2006年He等人提出了一種基于樹結(jié)構(gòu)建立索引的查詢算法C-Tree[13]，它采用閉包樹建立索引，用閉包的思想來衡量近似，但是該方法在近似查詢中結(jié)果的正確性得不到保證。

通過上述分析發(fā)現(xiàn)，絕大部分現(xiàn)有方法是在原始圖數(shù)據(jù)庫上執(zhí)行相關(guān)操作，并未考慮用戶所提出的查詢圖對查詢結(jié)果的影響，同時這些方法不能合理地解釋近似圖查詢過程中的why-not問題。鑒于此，基于對用戶查詢圖作出合理修改的思想，本文提出支持近似圖查詢的why-not問題解釋方法。

3 相關(guān)定義

定義1（圖相似性度量方法）當給定兩個圖結(jié)構(gòu)g1和g2，文獻[15]利用公式λ(g1,g2)=|E(g1)|+|E(g2)|-2×|E(mcs(g1,g2))|來描述兩個圖之間的差異，其中|E(g1)|表示圖g1的邊數(shù)，mcs(g1,g2)表示圖結(jié)構(gòu)g1和g2的最大公共子圖，|E(mcs(g1,g2))|表示圖g1和g2的最大公共子圖的邊數(shù)。圖相似性度量方法定義為：當圖g1和g2之間的差異λ(g1,g2)小于等于閾值δ時，圖g1和g2定義為相似，否則不相似。

例2圖1中g(shù)1和g2之間的差異計算為：λ(g1,g2)=4+4-2×3=2。當給定圖差異閾值為3時，圖g1和g2為相似圖結(jié)構(gòu)。

定義2（候選修改操作集）候選操作包括增邊和刪邊兩種，增邊操作是在查詢圖中增加部分邊，記為add(add operations)，且用add(vi,vj)表示在查詢圖q中增加邊(vi,vj)；刪邊操作是在查詢圖中刪除部分邊，記為del(delete operations)，且用del(vi,vj)表示刪除查詢圖q中的邊(vi,vj)。

基于增邊和刪邊操作，將候選修改操作集表示為MOP(modification operations)，MOP中包括所有增邊候選操作和刪邊候選操作。

例3為使查詢圖q與圖g3之間的差異小于等于3，將查詢圖q修改成q*，如圖2所示，需要一個修改操作，即del(b,e)，于是得到why-not問題解釋候選操作集為MOP={del(b,e)}。

Fig.2 Converting query graph fromqtoq*圖2 查詢圖q修改成q*

定義3（最小修改代價）通過增邊、刪邊操作將圖q修改成圖q*所需的最少操作次數(shù)。假設(shè)每一次增邊操作或者刪邊操作的代價均為1，將查詢圖q修改為q*的代價函數(shù)定義為：cost(q,q*)=∑op，其中op表示對查詢圖執(zhí)行的修改操作。

例4接例3，根據(jù)定義2，可知將查詢圖q修改為q*需要一次刪邊操作，從而可得將查詢圖q修改為q*所需的最小修改代價為1。

綜合上述內(nèi)容，現(xiàn)給出問題1的描述。

問題1給定查詢圖q和圖數(shù)據(jù)集G={g1,g2,…,gk,gk+1,…,gn}，根據(jù)用戶的查詢圖q，以及圖差異閾值δ，得到近似圖查詢結(jié)果集為R={ga,gb,…,gk}，針對用戶提出的why-not問題W={gi,gj,…,gn}，要解決近似圖查詢過程中的why-not問題，就是要在滿足圖差異閾值δ的條件下，用最小的修改代價cost(q,q*)，將查詢圖q修改為q*，使近似圖查詢結(jié)果包含R和W。

4 近似圖查詢why-not問題解釋

本章針對why-not問題的難點，提出了支持近似圖查詢的why-not問題解釋框架。并在此框架的基礎(chǔ)上，提出了why-not問題解釋方法。

4.1 解釋框架

本文提出的why-not問題解釋框架如圖3所示，已知圖數(shù)據(jù)集G，查詢圖q，近似圖查詢結(jié)果R和why-not問題集W。根據(jù)查詢圖q和why-not問題集W，得到候選修改操作集MOP。選取候選修改操作集中滿足代價模型的部分操作對初始查詢圖q進行修改，將q修改為q*。再利用修改后的查詢圖q*對圖數(shù)據(jù)集進行近似圖查詢，使得最終查詢結(jié)果中包含原始查詢結(jié)果R和why-not問題集W。

Fig.3 Framework of explanation圖3 解釋框架

4.2 候選操作集生成基本算法

從問題1的描述可知，圖的相似性最直觀地表現(xiàn)在邊結(jié)構(gòu)的相似上，因此，為了得到對查詢圖的候選修改操作，需要綜合考慮原始查詢結(jié)果集R和whynot問題集W。為了滿足用戶的查詢需求，通過統(tǒng)計出集合R和W中所有邊的頻率，得到一個邊頻率表，記為Fre-table，如圖4（a）所示。該表包括兩列，第一列為邊的信息，第二列為相應(yīng)邊出現(xiàn)的頻率，該頻率值由相應(yīng)邊出現(xiàn)的頻數(shù)值除以總邊數(shù)求得。該頻率表的統(tǒng)計過程是按照每條邊所涉及的節(jié)點的字典序進行，每條邊在表中出現(xiàn)且僅出現(xiàn)一次。為了對比每條邊在集合R和W中的出現(xiàn)情況，將邊頻率表Fretable按頻率值降序排序，得到結(jié)果如圖4（b）所示。

接著，利用排序后的邊頻率表Fre-table，在原始查詢圖q中標出所有邊的頻率值，如圖4（c）所示。對于出現(xiàn)在Fre-table中，卻沒有出現(xiàn)在查詢圖q中的邊，用紅色虛線標出，同時標出其頻率值。

Fig.4 Basic algorithm to generate candidate operations圖4 候選操作集生成基本算法

通過上述分析可知，要使why-not集合出現(xiàn)在查詢結(jié)果中，那些在集合R和W中出現(xiàn)頻率較高的邊應(yīng)該出現(xiàn)在查詢圖q中，那些出現(xiàn)頻率較低的邊則不應(yīng)該出現(xiàn)在查詢圖q中。于是，通過對比原始查詢圖q和Fre-table可以得到候選修改操作，對于在Fre-table中有較高頻率值卻在查詢圖q中未出現(xiàn)的邊，可以得到相應(yīng)的增邊候選操作，對于在Fre-table中有較低頻率值卻在查詢圖q中出現(xiàn)的邊，可以得到相應(yīng)的刪邊候選操作。

例5如圖1，當給定圖數(shù)據(jù)集G={g1,g2,g3}，查詢圖q，查詢結(jié)果集R={g1,g2}，why-not問題集W={g3}時，用候選操作集生成基本算法生成候選修改操作的過程為：首先依據(jù)集合R和W統(tǒng)計得到邊頻率表Fre-table，如圖4（a）所示；接著將頻率表按照頻率值降序排序，如圖4（b）所示；最后將相應(yīng)邊的頻率值在原始查詢圖q中標出，由于邊(b,e)在集合G中未出現(xiàn)，故其頻率值為0。從圖4（c）發(fā)現(xiàn)邊(b,d)有較高的頻率值，且邊(b,c)的頻率大于邊(b,e)的頻率值，同時查詢圖q中原始存在的邊的頻率值均大于等于未出現(xiàn)邊的最大頻率值，于是得到候選修改操作為MOP={add(b,d),add(b,c),del(b,e)}。

現(xiàn)將邊頻率表的生成算法表述為算法1。

算法1邊頻率表生成算法

輸入：近似圖查詢結(jié)果集R，why-not問題集W

輸出：按頻率值降序排列的Fre-table

2.For集合R和W中的每一個圖結(jié)構(gòu)gkdo

3.For圖結(jié)構(gòu)gk中的每一條邊(vi,vj)do

4.If Fre-table中不包括邊(vi,vj)，則將邊(vi,vj)加入Fre-table，并將該邊對應(yīng)頻率值設(shè)為1；

5.Else將邊(vi,vj)在Fre-table對應(yīng)的頻率值加1；

6.End if

7.End for

8.End for

9.按邊頻率值對Fre-table進行降序排序；

人員素質(zhì)是保障工作人員自身安全和提升工程質(zhì)量的最直接和最基本的因素，所以在公路工程的施工過程中，需要全面提升工作人員的素質(zhì)。在具體的工作開展中，對一線施工人員的素質(zhì)提升方式為讓其了解安全事故引發(fā)的后果，并講解如何對這些事故進行規(guī)避，經(jīng)過長時間的培訓后施工人員的安全意識自然會獲得提升。對于現(xiàn)場監(jiān)管人員，培訓內(nèi)容為讓其了解各類安保設(shè)施的佩戴方式和方法，同時也要讓其了解各類機械設(shè)備的故障表現(xiàn)形式，通過及時發(fā)現(xiàn)安全隱患的方式降低安全事故的發(fā)生幾率。而對于技術(shù)人員，施工單位可以建設(shè)全面追責制度，并要求這類人員主動研究專業(yè)知識以規(guī)避工程安全事故，防止在公路的運行中發(fā)生問題。

10.Return排序后的Fre-table。

根據(jù)算法1，假設(shè)圖集合R和W中每個圖的平均邊數(shù)為|E|，則行2～3兩重for循環(huán)的時間復(fù)雜度為|E|(|R|+|W|)。假設(shè)Fre-table中包含的邊數(shù)為m，則行9排序操作的時間復(fù)雜度為mlbm。因此算法1的時間復(fù)雜度為O(|E|(|R|+|W|)+mlbm)。

4.3 候選操作集生成改進算法

從4.2節(jié)中候選操作集生成基本算法的描述可知，通過統(tǒng)計集合R和W中各邊的頻率，對比原始查詢圖q，能得到候選修改操作集，但是該方法不夠直觀，并未考慮集合R和W中每個圖的結(jié)構(gòu)特性。鑒于此，本節(jié)將綜合考慮每個圖的結(jié)構(gòu)特性，并提出候選操作集生成改進算法。

圖的結(jié)構(gòu)特性可以從以下幾方面考慮：節(jié)點信息、邊信息、節(jié)點的度。文獻[19]中，Anthony等人提出了圖的星型結(jié)構(gòu)表示方式，將圖結(jié)構(gòu)按照節(jié)點信息分解成不同的星型結(jié)構(gòu)，但是該方法在分解時，每條邊的信息被存儲了兩次，導致空間占用較大。在該文獻的啟發(fā)下，本節(jié)將圖結(jié)構(gòu)進行分解，為了減小空間占用，每條邊僅存儲一次，具體分解過程由算法2描述。

為了將每個圖分解成多個圖結(jié)構(gòu)，算法2首先將gi分解后的結(jié)果集gi′初始化為空，并將圖gi每條邊賦權(quán)值0，這是為了使每條邊在分解之后的結(jié)構(gòu)中出現(xiàn)且僅出現(xiàn)一次，見行1。接著以圖gi中的每個節(jié)點為根節(jié)點，與之相連的節(jié)點為葉子節(jié)點，構(gòu)建樹型結(jié)構(gòu)，并使每條邊在分解之后的所有樹結(jié)構(gòu)中出現(xiàn)且僅出現(xiàn)一次，見行2～6。對于分解之后的樹結(jié)構(gòu)，如果其葉子節(jié)點為空，則將ε加入結(jié)果集，否則將節(jié)點vs對應(yīng)的樹結(jié)構(gòu)gis′加入結(jié)果集，見行7～8。最后返回結(jié)果集gi′，見行10。

算法2圖結(jié)構(gòu)分解算法

輸入：圖結(jié)構(gòu)gi

輸出：圖gi分解之后的集合gi′

1.將集合gi′初始化為空，并將圖gi每條邊權(quán)值均賦為0；

2.For圖gi中的每一個節(jié)點vs按字典序do

3.For圖gi中與節(jié)點vs相連的節(jié)點vtdo

4.If邊(vs,vt)的權(quán)值為0，則將邊(vs,vt)加入以節(jié)點vs為根節(jié)點的樹中，并將邊(vs,vt)的權(quán)值設(shè)為1；

5.End if

6.End for

7.If節(jié)點vs的葉子節(jié)點為空，則將節(jié)點vs設(shè)為空ε，并加入結(jié)果集gi′；

8.Else將以節(jié)點vs為根節(jié)點的樹gis′加入結(jié)果集gi′；

9.End for

10.Return結(jié)果集gi′。

根據(jù)算法2，假設(shè)圖gi邊數(shù)為|Ei|，則行1對圖gi每條邊賦值的時間復(fù)雜度為|Ei|。圖gi節(jié)點數(shù)為|Vi|，節(jié)點的平均度為|Di|，行2～3兩重for循環(huán)的時間復(fù)雜度為|Vi||Di|。因此算法2的時間復(fù)雜度為O(|Ei|+|Vi||Di|)。

例6給定例1中的結(jié)果集R、why-not集W和查詢圖q，利用算法2進行分解，得到的結(jié)果如圖5所示。其中第一行表示圖g1利用算法2分解之后的結(jié)果集，有g(shù)1′={g11′,g12′,g13′,g14′}，同理可得g2′={g21′,g22′,g23′,g24′}，g3′={g31′,g32′,g33′,g34′}，q′={q11′,q12′,q13′,q14′,q15′}。將結(jié)果集R和why-not集W分解之后的結(jié)果集記為R′，在本例中有R={g1′,g2′,g3′}。值得注意的是，原圖中的每條邊在分解之后的結(jié)構(gòu)中僅出現(xiàn)一次，因此分解后的圖結(jié)構(gòu)g13′、g14′、g22′、g24′、g34′、q14′、q15′為空，用ε表示。

Fig.5 Improved algorithm to generate candidate operations圖5 候選操作集生成改進算法

利用算法2將圖結(jié)構(gòu)分解之后，為了得到候選修改操作集，需要對比查詢圖q與圖集合R和W中根節(jié)點相同的結(jié)構(gòu)之間的差異。候選操作集生成改進算法由算法3描述。

算法3候選操作集生成改進算法

輸入：分解之后的圖集合R′={g1′,g2′,…,gk′}和q′

輸出：候選修改操作集MOP

1.初始化候選操作集MOP為空；

2.For集合q′中的每一個分解結(jié)構(gòu)q1i′do

3.For集合R′中每一個集合gj′中與結(jié)構(gòu)q1i′相對應(yīng)的結(jié)構(gòu)gji′do

4.If結(jié)構(gòu)gji′中存在邊 (u,v)且q1i′中不存在邊 (u,v)，則生成候選操作op=add(u,v)，并將該操作加入候選集MOP；

5.Else if結(jié)構(gòu)q1i′中存在邊 (u,v)且gji′中不存在邊(u,v)，則生成候選操作op=del(u,v)，并將該操作加入候選集MOP；

6.End for

7.End for

8.ReturnMOP

算法3首先將候選修改操作集MOP初始化為空，見行1。接著，對于分解之后的查詢圖集合q′中的每一個結(jié)構(gòu)q1i′，與所有g(shù)j′中與結(jié)構(gòu)q1i′有相同根節(jié)點的結(jié)構(gòu)gji′進行對比。對于那些在gji′中出現(xiàn)的且在q1i′中不出現(xiàn)的邊(u,v)，說明如果該邊出現(xiàn)在查詢圖中，則能減小查詢圖和why-not圖之間的差異，因此生成增邊候選操作op=add(u,v)，并將該操作加入候選集MOP；對于那些在q1i′中出現(xiàn)的且在gji′中不出現(xiàn)的邊(u,v)，說明該邊的出現(xiàn)，會加大查詢圖和why-not圖之間的差異，因此生成刪邊候選操作op=del(u,v)，并將該操作加入候選集MOP，見行2～7。最后返回候選修改操作集MOP，見行8。

根據(jù)算法3，當查詢圖q中節(jié)點數(shù)為|Vq|，圖節(jié)點的平均度為|Di|，集合R′中包含圖個數(shù)為k時，則行2～7兩重for循環(huán)的時間復(fù)雜度為O(k|Vq||Di|)。

例7接例6，給定用算法2分解之后的圖結(jié)構(gòu)集R′={g1′,g2′,g3′}和q′，利用算法 3 求解候選修改操作集。首先將q11′分別與g11′、g21′和g31′進行比較，發(fā)現(xiàn)q11′中的邊在g11′、g21′和g31′中均出現(xiàn)，且g11′、g21′和g31′中出現(xiàn)的邊在q11′中也出現(xiàn)，于是該列不產(chǎn)生候選操作。接著將q12′分別與g12′、g22′和g32′進行比較，邊(b,d)出現(xiàn)在g12′中，卻不出現(xiàn)在q12′中，于是產(chǎn)生增邊候選操作op1=add(b,d)；邊(b,c)和(b,d)出現(xiàn)在g32′中，卻不出現(xiàn)在q12′中，得到增邊候選操作add(b,c)和add(b,d)，由于add(b,d)操作與op1重復(fù)，故只產(chǎn)生候選操作op2=add(b,c)；邊(b,e)出現(xiàn)在q12′中，卻在g12′、g22′和g32′中未出現(xiàn)，于是產(chǎn)生刪邊候選操作op3=del(b,e)。接著將q13′分別與g13′、g23′和g33′進行比較，不產(chǎn)生候選操作，將q14′分別與g14′、g24′和g34′進行比較，也不產(chǎn)生候選操作。于是，最終用候選操作集生成改進算法得到的候選修改操作集為MOP={add(b,d),add(b,c),del(b,e)}，如圖5中最后一行所示。

4.4 貪心算法

在4.2節(jié)和4.3節(jié)中分別用候選操作集生成基本算法和改進算法求得了對why-not問題解釋的候選修改操作集MOP。通過上文分析可知，對于候選操作集中的每一個候選操作，對查詢圖的修改代價都是1。如果對查詢圖q執(zhí)行候選操作集中的所有操作，能順利地為支持近似圖查詢的why-not問題提供合理解釋，但是從4.2節(jié)和4.3節(jié)的分析中會發(fā)現(xiàn)當執(zhí)行某一個候選操作之后，有可能會改變原始結(jié)果集R中某一個圖與查詢圖之間的差異，從而導致原始查詢結(jié)果在修改查詢圖之后的查詢結(jié)果中不出現(xiàn)，這不滿足問題1的定義。因此，在生成候選操作集之后，需要從中選取部分候選操作，在修改代價cost(q,q*)最小的條件下，滿足修改后的查詢圖q*的查詢結(jié)果為{R,W}。本文采用貪心算法和回溯法選取候選操作集，本節(jié)介紹貪心算法選取候選修改操作。

本文的貪心策略為：對于初始查詢結(jié)果集R和why-not問題集W中的每一個圖，求解其與查詢圖之間的差異值，得到距離向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))。如果選擇候選操作opi將查詢圖q修改為q*，這時重新計算查詢圖與集合R和W之間的差異值，得到新的距離向量d′=(λ′(q,g1),λ′(q,g2),…,λ′(q,gk))，將貪心函數(shù)定義如下：

式（1）中，ΔλW表示根據(jù)選擇的候選操作opi將查詢圖修改為q*之后，W集合中圖差異由不滿足閾值δ變?yōu)闈M足閾值δ的圖的個數(shù)；ΔλR表示R集合中圖差異由滿足閾值δ變?yōu)椴粷M足閾值δ的圖的個數(shù)；k表示集合R和W中包含的圖的個數(shù)。該函數(shù)表示對于候選操作opi，變化的滿足閾值要求的圖差異個數(shù)與變化的不滿足閾值要求的圖差異個數(shù)的差值占整個圖總量的比例，該比例越大，說明候選操作opi對why-not問題解釋越有效。因此，用貪心策略選取候選修改操作時，總是選擇當前條件下使f值最大的候選操作。該策略綜合考慮了候選操作對集合R和W的影響，總是選擇當前狀態(tài)下最合理的操作，將其描述為算法4。

算法4貪心算法選取候選操作

輸入：查詢圖q，候選操作集MOP，初始距離向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))，圖差異閾值δ

輸出：選取的候選操作集MOP′

1.初始化選取的操作集MOP′為空；

2.While向量d中存在不滿足閾值δ的分量且候選集MOP中存在未選取的操作do

3.For候選操作集MOP中的每一個候選修改操作opido

4.對查詢圖q執(zhí)行修改操作opi，得到q*，同時求得d′=(λ′(q,g1),λ′(q,g2),…,λ′(q,gk))為新的距離向量，根據(jù)向量d′分別求得ΔλW和ΔλR，利用式（1）求得候選操作opi對應(yīng)的貪心函數(shù)值fi；

5.End for

6.選取貪心函數(shù)值fi最大的候選操作加入操作集MOP′

7.End while

8.ReturnMOP′

根據(jù)算法4，當候選操作集MOP中候選操作個數(shù)為|MOP|，圖近似查詢結(jié)果集R中圖數(shù)量為|R|，why-not集合W中圖數(shù)量為|W|時，算法4中行2～7的時間復(fù)雜度為O(|MOP|(|R|+|W|))。

例8結(jié)合例7，在得到候選修改操作集MOP={add(b,d),add(b,c),del(b,e)}之后，利用算法4從中選取部分候選操作，如圖6所示。由算法4，首先計算得到初始距離向量d=(3,1,4)。圖6中第一行對應(yīng)候選操作op1，將查詢圖q根據(jù)操作op1修改為q*之后的結(jié)果在圖中顯示。接著分別計算修改之后的查詢圖q*與集合R和W中圖的差異，得到λ(q*,g1)=4，λ(q*,g2)=2 ，λ(q*,g3)=3，于是距離向量更新為d′=(4,2,3)。接著利用式（1），求得 ΔλW=1，ΔλR=0，從而有f1=0.33。同理，對于候選操作op2求得f2=0，對于候選操作op3求得f3=0.33。

Fig.6 Greedy algorithm based candidate selection圖6 貪心算法選取候選操作

根據(jù)本文選取的貪心策略，此時選取使f值最大的那個候選操作op1或者op3。如果選取的是op1，那么由更新后的距離向量d′=(2,2,3)可知，集合R和W中所有圖的差異小于等于閾值δ，于是最終選取的操作集為MOP′={add(b,d)}。同理，如果選取的是op3，由更新后的距離向量d′=(2,0,3)可知，集合R和W中所有圖也滿足圖差異小于等于閾值δ的條件，因此最終得到的操作集為MOP′={del(b,e)}。根據(jù)定義3中的代價函數(shù)，兩種選取方式的操作代價均為1，因此兩種操作集均可。

4.5 回溯法

在候選集選取階段，需要選取MOP集的一個子集，同時滿足操作代價最小。然而滿足要求的子集是不唯一的，這就需要設(shè)計相應(yīng)的策略來選取合適的操作子集。除了4.4節(jié)設(shè)計的貪心算法，本文還采用了回溯法來選取候選子集，并設(shè)計三種剪枝策略來剪枝不必要的操作，提高算法的運行效率。

對于本文中候選操作集的選取，首先需要對候選操作集MOP中的所有操作進行排序，排序依據(jù)是候選操作生成的先后。此外，為了滿足圖差異閾值δ的要求，需要求解初始狀態(tài)時，查詢圖q與集合R和W中每一個圖的差異，d=(λ(q,g1),λ(q,g2),…,λ(q,gk))，同時用λm表示當前距離向量d中的最大值。

根據(jù)排序后的候選操作構(gòu)建操作樹，每一層都代表一個候選操作，其中左孩子節(jié)點表示執(zhí)行該候選操作，其右孩子節(jié)點表示不執(zhí)行該候選操作。為了高效地選取操作代價最小的操作集，需要對構(gòu)建完的操作樹進行剪枝。

本文設(shè)計了三種剪枝策略：第一種是根據(jù)當前的λm值執(zhí)行剪枝，當λm小于等于設(shè)定的圖差異閾值δ時，執(zhí)行剪枝操作。第二種策略需要記錄下當前滿足閾值δ的最少操作次數(shù)，記作minop，如果某一次選取操作時，已選取的操作個數(shù)達到minop，但是當前的λm值仍大于閾值δ，則執(zhí)行剪枝操作。第三種是根據(jù)當前的λm值與剩余的候選操作個數(shù)的差值執(zhí)行剪枝，當λm值與剩余的候選操作個數(shù)的差值大于設(shè)定的圖差異閾值δ時，執(zhí)行剪枝操作。

通過上述三種剪枝策略，能保證選取到的候選操作數(shù)最少，滿足操作代價最小的要求；此外，通過回溯法選取候選操作能考慮操作的所有可能的組合情況，避免漏解或者解不全的情況。同時，通過剪枝操作能及時去除那些不滿足要求的解，避免不必要的比較和計算，提高了算法的效率。

用回溯法選取候選操作的過程由算法5描述。

算法5利用回溯法選取候選操作。首先根據(jù)查詢圖q，查詢結(jié)果R和why-not問題W求出初始狀態(tài)下的向量d和λm值，并將minop的值初始化為MOP中操作數(shù)的個數(shù)，見行1。接著對候選操作集MOP中的候選操作進行排序，見行2。定義一個集合dSet存儲構(gòu)建操作數(shù)的過程中每個節(jié)點的向量值、λm值及到該節(jié)點時執(zhí)行的操作。dSet中每個元素都是一個三元組，將初始(d,λm,null)存入dSet，見行3。遍歷候選操作集中的每一個操作opi構(gòu)建操作樹，如果dSet中某個元素的值小于等于閾值，則更新minop的值，并將該元素對應(yīng)的操作存入結(jié)果集MOP′。如果dSet中某個元素的值滿足任意一種剪枝策略，則刪除該元素，見行4～5。在遍歷完所有操作后，返回結(jié)果集MOP′，見行6。

算法5回溯法選取候選操作

輸入：查詢圖q，圖差異閾值δ，查詢結(jié)果集R，whynot問題集W，候選操作集MOP

輸出：選取的候選操作集MOP′

1.根據(jù)查詢圖q、查詢結(jié)果集R和why-not問題集W計算初始圖差異向量d=(λ(q,g1),λ(q,g2),…,λ(q,gk))和初始λm值，初始化minop值為|MOP|；

2.根據(jù)候選操作的生成順序?qū)OP中所有候選操作進行排序，得到MOP={op1,op2,…,opn}；

3.定義一個集合dSet存儲構(gòu)建操作樹的過程中每個節(jié)點的向量值、λm值及到該節(jié)點時執(zhí)行的操作，dSet中每個元素都是一個三元組，將初始(d,λm,null)存入dSet；

4.For每一個MOP中的元素opido

根據(jù)是否執(zhí)行操作opi更新當前的集合dSet，如果dSet中某個元素的λm值小于等于閾值δ，則更新minop的值，并將該元素的操作存入MOP′，如果dSet中某個元素的值滿足任意一種剪枝策略，則刪除該元素；

5.End for

6.ReturnMOP′

從算法5可知，當候選操作集MOP中候選操作個數(shù)為|MOP|時，在最壞情況下，剪枝策略的作用得不到發(fā)揮，需要構(gòu)建完整的搜索樹，從而算法5的時間復(fù)雜度為O(2|MOP|)。

例9結(jié)合例8，當圖差異閾值設(shè)為δ=3，查詢結(jié)果為R={g1,g2}，why-not問題集為W={g3}時，利用算法3得到的候選操作集為MOP={add(b,d),add(b,c),del(b,e)}，此時利用算法5來選取候選操作，如圖7所示。

Fig.7 Backtracking with pruning based candidate selection圖7 回溯法選取候選操作

圖7中每條邊上的1表示執(zhí)行該層候選操作，0表示不執(zhí)行該層候選操作。從圖7可知，當執(zhí)行候選操作op1之后，圖差異向量更新為d=(2,2,3)，λm=3，有λm≤δ，滿足圖差異閾值δ=3的要求，此時將minop更新為1，根據(jù)第一種剪枝策略，其后的操作樹被剪枝（如圖7中剪枝1）。當不執(zhí)行候選操作op1，圖差異向量和λm均不發(fā)生變化，于是向下擴展一層。當執(zhí)行候選操作op2之后，圖差異向量更新為d=(4,2,3)，λm=4，minop值不發(fā)生變化，此時不滿足λm值小于等于閾值δ的條件，但操作數(shù)已經(jīng)達到當前的minop值，根據(jù)第二種剪枝策略，其后的操作樹被剪枝（如圖7中剪枝2）。當不執(zhí)行候選操作op1和op2時，有d=(3,1,4)，λm=4，于是向下擴展一層。當執(zhí)行候選操作op3之后，圖差異向量更新為d=(2,0,3)，λm=3，有λm≤δ，滿足圖差異閾值δ=3的要求，minop值不變。

通過上述分析，可知本例一共有兩種why-not問題解釋方案，即MOP′={add(b,d)}或MOP′={del(b,e)}。

5 實驗結(jié)果與分析

本文將在不同數(shù)據(jù)集上進行大量的實驗，用實驗結(jié)果來證明本文方法是正確且高效的。

5.1 實驗環(huán)境及實驗數(shù)據(jù)集

本文實驗采用的操作系統(tǒng)為Windows7，系統(tǒng)內(nèi)存為8 GB，編程環(huán)境為Visual Studio 2012，實驗代碼用C++編程語言實現(xiàn)。

本文選取真實數(shù)據(jù)集StanfordSNAP（http://snap.stanford.edu/data/email-Enron.html）和合成數(shù)據(jù)集Synthetic來評估算法的性能。

（1）真實數(shù)據(jù)集StanfordSNAP。該數(shù)據(jù)集抽取于SNAP，其中的email-Enron通信網(wǎng)絡(luò)中包含了超過50萬件email的通信信息，該網(wǎng)絡(luò)中的節(jié)點表示email地址，如果email地址i至少給地址j發(fā)送了一封郵件，那么在圖中就存在一條從節(jié)點i到節(jié)點j的無向邊。該數(shù)據(jù)集一共包括36 692個節(jié)點，183 831條邊。從中抽取4個圖集合G1、G2、G3和G4，它們分別包括1 000、2 000、3 000和4 000個圖。每個圖都是以某一個email地址i為中心，將與其有郵件往來的地址抽取出來。同時為4個數(shù)據(jù)集設(shè)計了3個不同的查詢圖qr1、qr2和qr3，以及相應(yīng)的why-not問題。

（2）合成數(shù)據(jù)集Synthetic。該數(shù)據(jù)集是根據(jù)實驗需求，隨機生成4個圖集合G1′、G2′、G3′和G4′，分別包括1 000、2 000、3 000和4 000個圖。為4個數(shù)據(jù)集設(shè)計了3個不同的查詢圖qs1、qs2和qs3，并設(shè)計相應(yīng)的why-not問題。

每個實驗數(shù)據(jù)集中總節(jié)點數(shù)和總邊數(shù)如表1所示。

Table1 Information of vertices and edges表1 數(shù)據(jù)集節(jié)點和邊信息

查詢圖的設(shè)計主要是依據(jù)實驗數(shù)據(jù)集G1、G2、G3、G4和G1′、G2′、G3′、G4′，從數(shù)據(jù)集中選取出部分圖作為查詢圖。由于查詢圖選取自實驗數(shù)據(jù)集，其結(jié)構(gòu)和大小與數(shù)據(jù)集中圖的結(jié)構(gòu)和大小相同。此外，選取圖數(shù)據(jù)集中與查詢圖的差異接近閾值的圖作為why-not圖。

本實驗主要從兩方面對支持近似圖查詢的whynot問題解釋算法進行評估：（1）why-not問題解釋算法的有效性；（2）why-not問題解釋算法的時間性能。

5.2 why-not問題解釋算法的有效性

對why-not問題解釋算法的有效性從兩方面進行評估：候選操作集生成基本算法和改進算法生成候選操作個數(shù)；貪心算法和回溯法生成why-not問題解釋個數(shù)。

候選操作集MOP中候選修改操作的個數(shù)受到數(shù)據(jù)集大小的影響。圖8（a）顯示了當why-not問題包含一個圖時，利用候選操作集生成基本算法，得到的候選修改操作個數(shù)隨數(shù)據(jù)集SNAP的增加而變化的情況，圖8（b）則顯示了同樣條件下，候選修改操作個數(shù)隨合成數(shù)據(jù)集Synthetic的增加而變化的情況。從圖中可知，隨著數(shù)據(jù)集的增加，候選修改操作個數(shù)也隨之增加。例如，當查詢?yōu)閝r1，SNAP數(shù)據(jù)集從1 000變化到4 000時，得到的候選修改操作個數(shù)分別為8、12、20和23。同理，當采用候選操作集生成改進算法時，也能得到相同的實驗結(jié)果，如圖9所示。

為了對比基本算法和改進算法在生成候選操作個數(shù)上的差異，將利用查詢qr1、qr2、qr3和qs1、qs2、qs3得到的候選操作個數(shù)分別取平均值，得到的結(jié)果如圖10所示。從圖10（a）可知，對于同一規(guī)模數(shù)據(jù)集，用改進算法得到的候選操作個數(shù)比用基本算法得到的多，這是因為改進算法綜合考慮了圖的結(jié)構(gòu)特性。從圖中還可知，隨著數(shù)據(jù)量的增加，得到的候選操作個數(shù)也會增加，因為當數(shù)據(jù)量增加時，近似圖數(shù)量也會增加，相應(yīng)圖中的邊數(shù)增加，從而候選操作數(shù)量增加，對于真實數(shù)據(jù)集SNAP和合成數(shù)據(jù)集Synthetic能得到相同的結(jié)論。

Fig.8 The number of candidate modified operations based on basic algorithm圖8 基本算法生成候選修改操作個數(shù)

Fig.9 The number of candidate modified operations based on improved algorithm圖9 改進算法生成候選操作個數(shù)

除了對比候選操作集生成基本算法和改進算法的差異，需要比較貪心算法和回溯法在生成why-not問題解釋個數(shù)上的差異，如圖11所示。

為了對比貪心算法（greedy algorithm，GA）和回溯法（back trace，BT）在生成why-not問題解釋個數(shù)上的差異，將利用查詢qr1、qr2、qr3和qs1、qs2、qs3得到的解釋個數(shù)分別取平均值，得到的結(jié)果如圖11所示。從圖11（a）可知，對于同一規(guī)模數(shù)據(jù)集，用回溯法得到的解釋個數(shù)比用貪心算法得到的多，這是因為回溯法比貪心算法考慮更全面，從而得到的解釋個數(shù)更多。此外，隨著數(shù)據(jù)量的增加，回溯法和貪心算法得到解釋個數(shù)的差異逐漸增大。

通過上述實驗結(jié)果及分析可知，候選操作集MOP中候選修改操作的個數(shù)隨數(shù)據(jù)集的增加而增加，因而why-not問題解釋的數(shù)量也隨之增加。此外，不同的候選操作選取算法會得到不同數(shù)量的why-not問題解釋個數(shù)。

綜上可知，本文提出的why-not問題解釋方法是有效且穩(wěn)定的。

5.3 why-not問題解釋算法的時間性能

本文why-not問題解釋算法的有效性在5.2節(jié)得到驗證，本節(jié)從時間性能方面對why-not問題解釋算法進行評估。評估從以下兩方面進行：基本算法和改進算法生成候選修改操作所需時間；貪心算法和回溯法選取候選操作所需時間。

首先考慮基本算法和改進算法生成候選操作所需時間，如圖12所示。

為了對比基本算法和改進算法生成候選操作集所需時間的差異，將查詢qr1、qr2、qr3和qs1、qs2、qs3生成候選操作所需時間分別求解平均值，得到的結(jié)果如圖12所示。從圖12（a）可知，對于同一規(guī)模數(shù)據(jù)集，用改進算法生成候選操作集的時間明顯小于用基本算法的時間。

Fig.10 Comparison between basic algorithm and improved algorithm圖10 基本算法和改進算法對比

Fig.11 Comparison between GAand BT圖11 貪心算法和回溯法對比

Fig.12 Comparison between basic algorithm and improved algorithm圖12 基本算法和改進算法對比

Fig.13 Comparison between GAand BT圖13 貪心算法和回溯法對比

接著考慮貪心算法和回溯法選取候選操作所需時間。

用回溯法選取候選操作所需時間的實驗結(jié)果如表2所示。從表中可知，真實數(shù)據(jù)集SNAP和合成數(shù)據(jù)集Synthetic候選操作選取時間差別不大。此外，對于同一個查詢，隨著數(shù)據(jù)集規(guī)模的增加，候選操作所需時間呈指數(shù)增長。例如，對于查詢qr1，當數(shù)據(jù)集大小從1 000變化到4 000時，候選操作選取所需時間分別為464、1 856、7 424、14 848 ms，這與之前分析的算法5的時間復(fù)雜度為O(2|MOP|)相符合。

Table 2 Running time of candidate selection表2 候選操作選取時間

為了比較貪心算法和回溯法選取候選操作所需時間，對查詢qr1、qr2、qr3和qs1、qs2、qs3生成解釋所需時間分別取平均值，從圖13可知，用貪心算法生成whynot問題解釋的時間明顯小于用回溯法的時間，這是由于用回溯法生成的解釋數(shù)量多于貪心算法，從而貪心算法的時間小于回溯法。

綜上，本節(jié)通過大量實驗對why-not解釋算法的有效性和時間性能進行評估，從實驗結(jié)果可知本文算法是正確且高效的。

6 結(jié)束語

本文提出了支持近似圖查詢的why-not問題解釋方法，通過統(tǒng)計邊頻率和圖分解的方法，得到候選修改操作集，并利用貪心算法和回溯法選取候選操作，最終得到why-not問題解釋。實驗結(jié)果表明，本文的方法能夠快速有效地為why-not問題返回合理的解釋。

[1]Chapman A,Jagadish H V.Why not?[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data,Providence,USA,Jun 29-Jul 2,2009.New York:ACM,2009:523-534.

[2]Tran Q T,Chan C Y.How to ConQueR why-not questions[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data,Indianapolis,USA,Jun 6-10,2010.New York:ACM,2010:15-26.

[3]He Z,Lo E.Answering why-not questions on top-kqueries[C]//Proceedings of the 28th International Conference on Data Engineering,Washington,Apr 1-5,2012.Washington:IEEE Computer Society,2012:750-761.

[4]Islam M S,Zhou Rui,Liu Chengfei.On answering why-not questions in reverse skyline queries[C]//Proceedings of the 29th International Conference on Data Engineering,Brisbane,Australia,Apr 8-12,2013.Washington:IEEE Computer Society,2013:973-984.

[5]Liu Jianzhuang,Lee Y T.A graph-based method for face identification from a single 2D line drawing[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,3(1):1106-1119.

[6]Lladós J,Martí E,Villanueva J J.Symbol recognition by errortolerant subgraph matching between region adjacency graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,3(1):1137-1143.

[7]Cheng J,Ke Yiping,Ng W,et al.Efficient query processing on graph databases[J].ACM Transactions on Database Systems,2009,34(1):1-48.

[8]Islam M S,Liu Chengfei,Li Jianxin.Efficient answering of why-not questions in similar graph matching[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(10):2672-2686.

[9]Zong Chuanyu,Yang Xiaochun,Wang Bin,et al.Minimizing explanations for missing answers to queries on databases[C]//LNCS 7825:Proceedings of the 18th International Conference on Database Systems for Advanced Applications,Wuhan,China,Apr 22-25,2013.Berlin,Heidelberg:Springer,2013:254-268.

[10]Zong Chuanyu,Wang Bin,Sun Jing,et al.Minimizing explanations of why-not questions[C]//LNCS 8505:Proceedings of the 19th International Conference on Database Systems for Advanced Applications,Bali,Indonesia,Apr 21-24,2014.Berlin,Heidelberg:Springer,2014:230-242.

[11]Islam M S,Liu Chengfei,Zhou Rui.User feedback based query refinement by exploiting skyline operator[C]//LNCS 7532:Proceedings of the 31st International Conference on Conceptual Modeling,Florence,Italy,Oct 15-18,2012.Berlin,Heidelberg:Springer,2012:423-438.

[12]Meliou A,Gatterbauer W,Moore K F,et al.Why so?or Why no?Functional causality for explaining query answers[R].Washington:University of Washington,2009.

[13]He Huahai,Singh A K.Closure-tree:an index structure for graph queries[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA,Apr 3-8,2006.Washington:IEEE Computer Society,2006:38.

[14]Cheney J,Chiticariu L,Tan W C.Provenance in databases:why,how,and where[J].Foundations and Trends in Databases,2009,1(4):379-474.

[15]Gao Ming,Jin Cheqing,Wang Xiaoling,et al.The research summarizes of data lineage management technology[J].Chinese Journal of Computers,2010,33(3):373-389.

[16]Chen Lei,Xu Jianliang,Lin Xin,et al.Answering why-not spatial keyword top-kqueries via keyword adaption[C]//Proceedings of the 32nd International Conference on Data Engineering,Helsinki,Finland,May 16-20,2016.Washington:IEEE Computer Society,2016:697-708.

[17]Yan Xifeng,Yu P S,Han Jiawei.Substructure similarity in graph databases[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data,Baltimore,USA,Jun 14-16,2005.New York:ACM,2005:766-777.

[18]Yan Xifeng,Zhu Feida,Han Jiawei,el al.Searching substructures with superimposed distance[C]//Proceedings of the 22nd International Conference on Data Engineering,Atlanta,USA,Apr 3-8,2006.Washington:IEEE Computer Society,2006:88.

[19]Zeng Zhiping,Tung A K H,Wang Jianyong,et al.Comparing stars:on approximating graph edit distance[C]//Proceedings of the 35th International Conference on Very Large Data Bases,Lyon,France,Aug 24-28,2009.New York:ACM,2009:25-36.

附中文參考文獻：

[15]高明,金澈清,王曉玲,等.數(shù)據(jù)世系管理技術(shù)研究綜述[J].計算機學報,2010,33(3):373-389.

Explaining Why-Not Questions onApproximate Graph Queries*

HE Dan,ZONG Chuanyu,WANG Bin,LI Jinxu,YANG Xiaochun+

School of Computer Science and Engineering,Northeastern University,Shenyang 110819,China

2016-08,Accepted 2016-10.

Why-not questions aim to seek clarifications on the missing tuples for query results.Answering why-not questions on database queries not only helps user better understand the query,but also improves data quality and the availability of database.To enhance the availability of graph database,this paper proposes an efficient explaining technique for why-not questions on approximate graph queries.This technique gives explanations for missing graphs,as well as some suggestions how to modify the initial query graph to let the missing graphs appear in the query result set.Algorithm for answering approximate graph queries includes two parts:the first part is a candidate generation phase,which proposes the basic algorithm according to frequency information of edges,and the improved algorithm by graph decomposition operation to acquire candidate operation set.And in the second part,in order to minimize the cost of modifying initial query graph,greedy algorithm and backtracking are proposed separately to select candidate operations.Reasonable greedy function is designed for greedy algorithm.The pruning trees based on candidate selection are built and three strategies for selecting candidate operations from the candidate set are proposed.The final candidate operation set includes the reasonable explanations for why-not questions on graph queries.According to experiments,the algorithm proposed in this paper can efficiently generate reasonable explanations for why-not questions on approximate graph queries.

approximate graph queries;why-not questions;backtracking;pruning strategy

+Corresponding author:E-mail:yangxc@mail.neu.edu.cn

10.3778/j.issn.1673-9418.1608050

*The National Natural Science Foundation of China under Grant Nos.61572122,61322208,61272178,61532021(國家自然科學基金);the National Basic Research Program of China under Grant No.2012CB316201(國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-31,http://www.cnki.net/kcms/detail/11.5602.TP.20161031.1650.014.html

HE Dan,ZONG Chuanyu,WANG Bin,et al.Explaining why-not questions on approximate graph queries.Journal of Frontiers of Computer Science and Technology,2017,11(12)：1871-1885.

A

TP311.1

HE Dan was born in 1992.She is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.Her research interests include approximate graph query and data provenance,etc.

賀丹（1992—），女，湖南湘潭人，東北大學計算機科學與工程學院碩士研究生，主要研究領(lǐng)域為近似圖查詢，數(shù)據(jù)世系等。

ZONG Chuanyu was born in 1985.He is a Ph.D.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include data quality management and data provenance,etc.

宗傳玉（1985—），男，山東濰坊人，東北大學計算機科學與工程學院博士研究生，主要研究領(lǐng)域為數(shù)據(jù)質(zhì)量管理，數(shù)據(jù)世系等。

WANG Bin was born in 1972.He received the Ph.D.degree in computer science from Northeastern University in 2008.Now he is an associate professor at Northeastern University,and the member of CCF.His research interests include design and analysis of algorithms,databases and data quality,etc.

王斌（1972—），男，遼寧沈陽人，2008年于東北大學獲得博士學位，現(xiàn)為東北大學副教授，CCF會員，主要研究領(lǐng)域為算法設(shè)計與分析，數(shù)據(jù)庫，數(shù)據(jù)質(zhì)量等。

LI Jinxu was born in 1992.He is an M.S.candidate at School of Computer Science and Engineering,Northeastern University.His research interests include database and data query,etc.

李金旭（1992—），男，河北承德人，東北大學計算機科學與工程學院碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)庫，數(shù)據(jù)查詢等。

YANG Xiaochun was born in 1973.She received the Ph.D.degree from Northeastern University in 2001.Now she is a professor and Ph.D.supervisor at Northeastern University,and the senior member of CCF.Her research interests include theory and technology of database and data quality analysis,etc.

楊曉春（1973—），女，遼寧沈陽人，2001年于東北大學獲得博士學位，現(xiàn)為東北大學教授、博士生導師，CCF高級會員，主要研究領(lǐng)域為數(shù)據(jù)庫理論與技術(shù)，數(shù)據(jù)質(zhì)量分析等。