林 杰，覃 飆，覃雄派

(中國(guó)人民大學(xué) 信息學(xué)院，北京 100872)(*通信作者電子郵箱qinbiao@ruc.edu.cn)

0 引言

近幾十年來(lái)，科技得到飛速發(fā)展，數(shù)據(jù)呈爆炸式增長(zhǎng)，信息革命推動(dòng)了各個(gè)學(xué)科的共同發(fā)展，許多方向的發(fā)展由單一化到多元化。數(shù)據(jù)庫(kù)也隨著整體信息化的推進(jìn)不斷吸收和融合新的理念與技術(shù)而發(fā)展，用戶(hù)可以更加便捷地在數(shù)據(jù)庫(kù)中查詢(xún)所需信息。因果關(guān)系研究也是計(jì)算機(jī)科學(xué)領(lǐng)域的研究熱點(diǎn)之一，因果關(guān)系是對(duì)問(wèn)題更加本質(zhì)的認(rèn)識(shí)，比如在物理學(xué)、心理學(xué)或行為學(xué)中許多研究的核心問(wèn)題是對(duì)因果關(guān)系的闡述，即對(duì)變量或事件之間直接作用關(guān)系的闡述[1-2]。

結(jié)構(gòu)化查詢(xún)語(yǔ)言(Structured Query Language, SQL)是用于訪問(wèn)和處理數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)查詢(xún)語(yǔ)言，在關(guān)系型數(shù)據(jù)庫(kù)的查詢(xún)中為用戶(hù)提供方便高效的接口，且允許嵌套查詢(xún)，有極強(qiáng)的可擴(kuò)展性。常用的SQL查詢(xún)有等值連接查詢(xún)、不等式連接查詢(xún)等，其中帶有不等式查詢(xún)條件的SQL連接查詢(xún)(Queries with Inequalities, IQ)是應(yīng)用較為廣泛的一類(lèi)查詢(xún)，Dan等定義了一類(lèi)不等式查詢(xún)語(yǔ)句，并根據(jù)不等式查詢(xún)條件的結(jié)構(gòu)特性將其分為三類(lèi)：路徑類(lèi)型、樹(shù)類(lèi)型和圖類(lèi)型[3-4]查詢(xún)。因樹(shù)類(lèi)型、圖類(lèi)型的查詢(xún)可拆分為若干路徑類(lèi)型查詢(xún)，因此本文所提出的問(wèn)題及方法均只針對(duì)帶有不等式連接條件的路徑類(lèi)型查詢(xún)(以下簡(jiǎn)稱(chēng)路徑類(lèi)型IQ查詢(xún))。

近年來(lái)，有學(xué)者創(chuàng)造性地將因果關(guān)系研究與數(shù)據(jù)庫(kù)SQL查詢(xún)結(jié)合研究，基于干預(yù)的思想，分析表中的元組對(duì)某個(gè)查詢(xún)結(jié)果的因果關(guān)系。在查詢(xún)中，如果某些數(shù)據(jù)庫(kù)元組被刪除，將會(huì)對(duì)查詢(xún)結(jié)果產(chǎn)生較大影響。resilience[5]是一個(gè)將因果關(guān)系與數(shù)據(jù)庫(kù)SQL查詢(xún)結(jié)合研究的典型應(yīng)用，根據(jù)resilience的定義，在查詢(xún)中若刪除最小個(gè)數(shù)的元組，查詢(xún)將不成立時(shí)，此最小元組集合即為resilience解。通過(guò)resilience的量化描述，人們可以更充分地理解查詢(xún)語(yǔ)句的因果性質(zhì)，以及更好地知道在查詢(xún)中哪些元組是對(duì)查詢(xún)成立起決定性作用的元組，透過(guò)表象的數(shù)據(jù)，深層次地理解輸入元組與結(jié)果之間的因果關(guān)聯(lián)，以便更準(zhǔn)確和高效地預(yù)測(cè)和干預(yù)查詢(xún)。

文獻(xiàn)[5-6]中研究了等值且無(wú)環(huán)連接查詢(xún)的resilience計(jì)算，將其轉(zhuǎn)化為最大流最小割問(wèn)題，并理論證明其可以在多項(xiàng)式時(shí)間內(nèi)完成，時(shí)間復(fù)雜度為O(VE2)(其中：V表示圖中頂點(diǎn)的個(gè)數(shù)，E表示圖中邊的個(gè)數(shù))，但未給出具體實(shí)現(xiàn)方式。在本文的研究中發(fā)現(xiàn)，最大流最小割方法不僅可處理無(wú)環(huán)等值連接查詢(xún)，也可求解本文研究的路徑類(lèi)型IQ查詢(xún)；但在大數(shù)據(jù)集合中，該算法復(fù)雜度較高，時(shí)間開(kāi)銷(xiāo)巨大，尤其是在不等式連接查詢(xún)中，最壞情況下連接邊E的數(shù)量接近O(V2)，算法時(shí)間復(fù)雜度約為O(V5)，巨大的時(shí)間開(kāi)銷(xiāo)無(wú)法滿(mǎn)足用戶(hù)的實(shí)時(shí)查詢(xún)需求。

為了有效地計(jì)算路徑類(lèi)型IQ查詢(xún)語(yǔ)句的resilience，本文首先實(shí)現(xiàn)了基于最大流最小割的算法(以下簡(jiǎn)稱(chēng)Min-Cut算法)；接著基于路徑類(lèi)型IQ查詢(xún)連接圖的特點(diǎn)，采用溯源表達(dá)式并將其編輯為溯源圖，提出一種能夠在線性時(shí)間復(fù)雜度內(nèi)求解resilience的動(dòng)態(tài)規(guī)劃(Dynamic Programming for Resilience, DPResi)算法。相比最大流最小割算法，在路徑類(lèi)型IQ查詢(xún)中計(jì)算resilience的時(shí)間復(fù)雜度由O(VE2)減小到O(V)，說(shuō)明DPResi是一種高效可擴(kuò)展的算法。

1 相關(guān)研究工作

1.1 不等式查詢(xún)

本文主要研究的是數(shù)據(jù)庫(kù)中帶有不等式連接且每個(gè)表中僅有一個(gè)屬性參與連接的路徑類(lèi)型查詢(xún)語(yǔ)句，借鑒概率數(shù)據(jù)庫(kù)研究中常用的查詢(xún)語(yǔ)句的溯源表達(dá)方式[7-9]，將查詢(xún)結(jié)果采用溯源表達(dá)式的方式來(lái)表示。

圖1描述了示例數(shù)據(jù)庫(kù)，其中共包含5張表，下文中所用算法示例都基于此示例數(shù)據(jù)庫(kù)。

圖1 示例數(shù)據(jù)庫(kù)

表1描述了基于圖1示例數(shù)據(jù)庫(kù)的IQ查詢(xún)及其對(duì)應(yīng)的查詢(xún)結(jié)果溯源表達(dá)式。乘號(hào)代表一條連接邊，加號(hào)代表整個(gè)查詢(xún)的多條邊，通過(guò)交換律和結(jié)合律，即可化簡(jiǎn)溯源表達(dá)式。例如Q3查詢(xún)對(duì)應(yīng)的溯源表達(dá)式為x4e1(f1+f2)，包含了兩個(gè)合取子句x4e1f1和x4e1f2，這兩個(gè)合取子句反映了查詢(xún)中表之間元組的連接關(guān)系。圖2(a)是Q2的查詢(xún)結(jié)果，圖3(a)是其對(duì)應(yīng)的溯源圖。以<為例，如果存在查詢(xún)條件A

表1 查詢(xún)語(yǔ)句及其溯源表達(dá)式

1.2 因果關(guān)系及resilience研究

因果關(guān)系是人工智能領(lǐng)域的研究熱點(diǎn)之一，對(duì)于理解事件本質(zhì)、起因有著重要作用。Galles等[10]提出了因果關(guān)系模型；Halpern[11]基于結(jié)構(gòu)化的方程語(yǔ)言給出了因果關(guān)系的定義。類(lèi)似于大多數(shù)因果定義一樣，因果關(guān)系定義都是基于反事實(shí)定律的，當(dāng)事件A是B的原因時(shí)，如果事件A沒(méi)有發(fā)生的話(huà)，事件B也不會(huì)發(fā)生(然而事件A已經(jīng)發(fā)生)。在文獻(xiàn)[10-11]的描述中，世界是由隨機(jī)變量所描述的，其中一部分變量可能會(huì)受到另外一部分變量的影響，這種影響可以通過(guò)結(jié)構(gòu)方程式的方式所描述，每個(gè)方程式可能代表一種規(guī)定或條款等。這些變量通常可分為兩類(lèi)：外在型變量和內(nèi)在型變量。外在型變量通常只由因果關(guān)系模型以外的變量所影響；而內(nèi)在型變量通常是由因果關(guān)系結(jié)構(gòu)方程所描述的?；贖alpern定義的因果關(guān)系模型，Chockler等[12]提出了responsibility的概念，當(dāng)事件A是事件B的原因時(shí)，定義當(dāng)改變A中最少個(gè)數(shù)的變量(n個(gè))時(shí)，事件B會(huì)有明顯的影響，responsibility的值為1/(1+n)。Chockler等[12]研究了responsibility時(shí)間復(fù)雜度，并證明在通常情況下，responsibility的計(jì)算是NP難問(wèn)題；Meliou等[6]將responsibility與SQL查詢(xún)相結(jié)合，研究了數(shù)據(jù)庫(kù)中無(wú)環(huán)等值連接查詢(xún)的responsibility計(jì)算，并證明了非線性查詢(xún)語(yǔ)句的responsibility計(jì)算是NP完全問(wèn)題，但線性查詢(xún)的responsibility計(jì)算可以在多項(xiàng)式時(shí)間內(nèi)完成。

resilience[5]是與responsibility意義相近的另一個(gè)因果關(guān)系的概念，定義為：當(dāng)事件A是事件B的原因時(shí)，若刪除A中最小個(gè)數(shù)的變量時(shí)，事件B將不成立。應(yīng)用于數(shù)據(jù)庫(kù)連接查詢(xún)時(shí)表述為：在連接查詢(xún)中，當(dāng)刪除表中最小個(gè)數(shù)的元組時(shí)，連接查詢(xún)將不成立。Freire等[5]將resilience與responsibility作類(lèi)比，提出了等值無(wú)環(huán)連接查詢(xún)中求解resilience的方法，通過(guò)在連接結(jié)果圖中增加起點(diǎn)和終點(diǎn)，將問(wèn)題轉(zhuǎn)化為在有向無(wú)環(huán)連接圖中，割斷最少個(gè)數(shù)的邊使起點(diǎn)與終點(diǎn)間不連通。運(yùn)用最大流最小割理論，提出使用Ford-Fulkerson算法求解，并理論證明了可以在多項(xiàng)式時(shí)間內(nèi)完成，但沒(méi)有給出具體實(shí)現(xiàn)，且沒(méi)有擴(kuò)展到其他類(lèi)型查詢(xún)。然而在本文的研究中發(fā)現(xiàn)，F(xiàn)ord-Fulkerson算法可計(jì)算路徑類(lèi)型IQ查詢(xún)的resilience，但其具有多項(xiàng)式時(shí)間復(fù)雜度，時(shí)間開(kāi)銷(xiāo)較大，不適合處理大規(guī)模數(shù)據(jù)集。

1.3 最大流最小割算法

Ford-Fulkerson方法是Ford等[13]于1958年提出的增廣鏈算法，是計(jì)算網(wǎng)絡(luò)流的最大流最小割的貪心算法。Edmonds-Karp算法[14]是一種Ford-Fulkerson的實(shí)現(xiàn)，該算法的主要思想是只要有一條由起點(diǎn)到終點(diǎn)的連通路徑，且在所有邊上都有可用容量，就沿著這條路徑發(fā)送一個(gè)流；然后再找到另一條路徑，直到網(wǎng)絡(luò)中不存在這種路徑為止。該算法時(shí)間復(fù)雜度為O(VE2)。

2 resilience求解算法

本章首先分析路徑類(lèi)型IQ查詢(xún)的連接圖，給出了基于最大流最小割方法實(shí)現(xiàn)的Min-Cut算法，進(jìn)而提出了本文的核心算法——DPResi算法，該算法主要分為兩部分：溯源矩陣構(gòu)造和最短距離計(jì)算。最短距離計(jì)算是充分利用了IQ查詢(xún)溯源圖的最優(yōu)子結(jié)構(gòu)性質(zhì)而實(shí)現(xiàn)的動(dòng)態(tài)規(guī)劃算法，是一種O(V)時(shí)間復(fù)雜度的高效算法，具有很好的魯棒性和可擴(kuò)展性。

2.1 Min-Cut算法

通過(guò)最大流最小割算法描述，基于圖2(a)對(duì)查詢(xún)結(jié)果圖增加起始點(diǎn)和終點(diǎn)，并將每個(gè)節(jié)點(diǎn)值置為節(jié)點(diǎn)內(nèi)元組個(gè)數(shù)，表示該節(jié)點(diǎn)權(quán)重，得到圖2(b)網(wǎng)絡(luò)連接圖，將問(wèn)題轉(zhuǎn)化為在圖2(b)中求解起點(diǎn)s到終點(diǎn)e的最大流最小割問(wèn)題。

圖2 Q2的查詢(xún)結(jié)果圖及網(wǎng)絡(luò)連接圖

在路徑類(lèi)型IQ查詢(xún)中，不等關(guān)系可包含多個(gè)元組的連接關(guān)系，即：xi元組可能與多個(gè)yi元組連接，因此在流式網(wǎng)絡(luò)中，切割其中一條連接邊沒(méi)有意義，只有將xi刪除，xi連向y列的連接才會(huì)失效，對(duì)應(yīng)到網(wǎng)絡(luò)連接圖中，即置所有連接邊的容量為無(wú)窮，切割時(shí)刪除點(diǎn)xi。

標(biāo)準(zhǔn)的最大流最小割算法中網(wǎng)絡(luò)流的容量在圖的邊中迭代，路徑的距離為路徑中邊的權(quán)重相加，本文提出兩種對(duì)連接圖改造以適配Ford-Fulkerson的方法。

方法1 拆點(diǎn)成邊，將點(diǎn)拆分為一條邊，點(diǎn)的權(quán)重拆分成一條邊上的權(quán)重，拆分后可直接使用最大流最小割方法。

方法2 修改算法中計(jì)算流大小的方法，將計(jì)算邊權(quán)重改為計(jì)算點(diǎn)權(quán)重，即：f(xi→yi)=weight(xi)。

通過(guò)上面的描述，可簡(jiǎn)單地對(duì)標(biāo)準(zhǔn)Ford-Fulkerson算法進(jìn)行改造，即可實(shí)現(xiàn)路徑類(lèi)型IQ查詢(xún)的resilience計(jì)算的Min-Cut算法，具體算法如下所示。

輸入：圖G=(V,E)，源點(diǎn)s以及終點(diǎn)e。

輸出：網(wǎng)絡(luò)f中從s到e的最大流。

對(duì)于圖中每一條邊(u,v)，在開(kāi)始時(shí)流量f(u,v)=0

當(dāng)Gf中存在一條從s到e的路徑p使得對(duì)于每一條邊(u,v)都有cf(u,v)>0時(shí)

找出cfp=min{cf(u,v):(u,v)∈p}

對(duì)于p中每一條邊(u,v)

f(u,v)=f(u,v)+cfp

f(v,u)=f(v,u)-cfp

在圖2(b)的有向圖中，運(yùn)用Min-Cut算法可得出s到e的最小割為3，其中一個(gè)最小割集合為{x4,x3,y1}。當(dāng)刪除該最小割集合中的所有元組時(shí)，此查詢(xún)將不成立，因此此查詢(xún)的resilience解為3。

Min-Cut算法的空間復(fù)雜度與圖存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)有關(guān)，當(dāng)采用鄰接矩陣存儲(chǔ)圖時(shí)，空間復(fù)雜度為O(V2)；當(dāng)采用鄰接表存儲(chǔ)圖時(shí)，空間復(fù)雜度為O(E)，時(shí)間復(fù)雜度為O(VE2)。隨著數(shù)據(jù)量增大或連接圖變得相對(duì)復(fù)雜時(shí)，時(shí)間復(fù)雜度呈多項(xiàng)式增加，尤其是在不等式連接查詢(xún)中，連接圖中邊數(shù)較多。給定N個(gè)表連接，平均每個(gè)表有M個(gè)元組，連接圖中頂點(diǎn)數(shù)V約為MN。最壞情況下，連接圖中的邊數(shù)接近O(NM2)，采用Min-Cut算法的時(shí)間復(fù)雜度約為O(N3M5)。

2.2 DPResi算法

2.2.1 溯源矩陣

觀察如圖3(a)所示路徑類(lèi)型IQ查詢(xún)的溯源圖，通過(guò)聚合連接點(diǎn)，使得圖中連接關(guān)系得以清楚地展示。數(shù)據(jù)結(jié)構(gòu)中圖的存儲(chǔ)方式通常為鄰接矩陣或鄰接表，然而在溯源圖中，每個(gè)節(jié)點(diǎn)均可連接至連接列的同行及以下的元素，例如圖3(a)中x3可連接至y列同行元素y3及以下所有元素{y3,y2,y1}。這種包含連接關(guān)系使得可以使用矩陣形式存儲(chǔ)該圖，對(duì)應(yīng)圖3(b)所示溯源矩陣圖，使用M×N的矩陣存儲(chǔ)，本文稱(chēng)之為溯源矩陣(Lineage Matrix, LM)。

圖3 Q2的溯源圖及溯源矩陣圖

定義1 孤立點(diǎn)與非孤立點(diǎn)。定義在溯源矩陣LM中，不存在的點(diǎn)稱(chēng)之為孤立點(diǎn)，并將其填充為0。其他所有點(diǎn)稱(chēng)為非孤立點(diǎn)，將其填充為對(duì)應(yīng)節(jié)點(diǎn)內(nèi)元組的個(gè)數(shù)。

在圖4(a)所示溯源矩陣中，LM[0][2]、LM[2][0]為孤立點(diǎn)，故其值等于0。任意一個(gè)元素LM[i][j]可連接LM[i][j+1]至LM[M-1][j+1]的所有非孤立點(diǎn)。

通過(guò)如上描述，將IQ查詢(xún)溯源圖存儲(chǔ)為一個(gè)結(jié)構(gòu)清晰的矩陣，在算法實(shí)現(xiàn)過(guò)程中，僅需存儲(chǔ)一個(gè)如圖4(a)所示M×N的二維數(shù)組矩陣即可。圖中邊的關(guān)系，均可通過(guò)溯源矩陣自動(dòng)獲取，減少了鄰接矩陣或鄰接表存儲(chǔ)邊的開(kāi)銷(xiāo)，降低了算法的空間復(fù)雜度。其中：SDM(Shortest Distance Matrix)為最短距離矩陣。

圖4 Q2的溯源矩陣及SDM

2.2.2 resilience求解

原SQL查詢(xún)是自左向右進(jìn)行連接，且由于IQ查詢(xún)時(shí)，連接列具有有序的包含關(guān)系，以小于為例，自上向下降序排列，因此得出如下定理。

定理1 如果查詢(xún)溯源矩陣圖中左上角元組LM[0][0]到右下角元素LM[M-1][N-1]不連通，則查詢(xún)不成立。

證明 反證法證明上述定理，假設(shè)查詢(xún)成立。

在SQL查詢(xún)中，查詢(xún)成立時(shí)至少存在一條從最左側(cè)連接列(x列)中元組LM[i][0]到最右側(cè)連接列(z列)中元組LM[j][N-1]的連通路徑。又因IQ查詢(xún)具有包含關(guān)系，在構(gòu)造的溯源矩陣圖中LM[0][0]到LM[i][0]間必然存在一條連通路徑。同理，LM[j][N-1]到LM[M-1][N-1]間也必然存在一條連通路徑，即存在LM[0][0]到LM[M-1][N-1]的一條連通路徑。而由定理1的條件所知，LM[0][0]到LM[M-1][N-1]不連通，所以假設(shè)不成立，定理1得證。

基于上述分析，依據(jù)resilience的定義，在IQ查詢(xún)中，當(dāng)最小個(gè)數(shù)的元組被刪除時(shí)，查詢(xún)不成立。將其轉(zhuǎn)化為溯源圖中描述即為，當(dāng)刪除溯源圖中左上角元組至右下角元組最短連通路徑上的節(jié)點(diǎn)后，查詢(xún)將不再成立，即：路徑類(lèi)型IQ查詢(xún)的resilience解為其溯源圖中左上角元組LM[0][0]到右下角元組LM[M-1][N-1]的最短距離，最短距離結(jié)果存儲(chǔ)在最短距離矩陣(SDM)中。

定理2 記LM[i][j]到LM[m][n]的距離為cost(LM[i][j],LM[m][n])，對(duì)于同行相鄰元組之間有：cost(LM[i][j-1],LM[i][j])=0，對(duì)于同列相鄰元組之間有cost(LM[i-1][j],LM[i][j])=LM[i][j]。

證明 在溯源矩陣圖中，對(duì)于任一非孤立點(diǎn)LM[i][j]，最多有兩條通路可達(dá)。依據(jù)溯源圖的構(gòu)造規(guī)則，每一條自左向右的連接為溯源表達(dá)式中一條合取子句，代表連乘操作。當(dāng)左側(cè)節(jié)點(diǎn)LM[i][j-1]不連通時(shí)，當(dāng)前單條合取子句將不成立，此時(shí)自左向右連接的距離cost(LM[i][j-1],LM[i][j])=0。每一條自上向下的連接為溯源表達(dá)式的合取子句相加操作，需刪除LM[i][j]才能使該溯源表達(dá)式不成立，即溯源圖不連通，因此自上向下連接的代價(jià)cost(LM[i-1][j],LM[i][j])=LM[i][j]。

定理3 對(duì)于LM右上角存在的孤立點(diǎn)，在SDM中，將對(duì)應(yīng)的位置置0。

證明 當(dāng)LM右上角存在孤立點(diǎn)時(shí)，因其元組不存在，從LM[0][0]到這些孤立點(diǎn)的子連接查詢(xún)本身就不存在，故此時(shí)，LM[0][0]到這些點(diǎn)的距離為0。

Dijkstra算法是求解單源最短路徑較為經(jīng)典和高效的方法[15]，復(fù)雜度為O(V2)，然而觀察溯源矩陣圖，具有明顯最優(yōu)子結(jié)構(gòu)性質(zhì)，具備如下的遞歸特性。

遞歸1 置SDM[0][0]=LM[0][0]，對(duì)首行頂點(diǎn)，SDM[0][j]=min(SDM[0][j-1],LM[0][j])(0

遞歸2 對(duì)第一列中的頂點(diǎn)，SDM[i][0]=SDM[i-1][0]+LM[i][0](0

遞歸3 對(duì)其他頂點(diǎn)LM[i][j](0

通過(guò)上述遞歸分析，提出了本文的核心算法——DPResi，如下所示。

輸入：LM[M][N]。

輸出：SDM[M][N]。

for (i=0;i

if (LM[i][N-1]≠0) break

for (j=N-1;j>=0;j--)

if (LM[i][j]=0)SDM[i][j]=0

else break

SDM[0][0]=LM[0][0]

for (j=1;j

SDM[0][j]=min(SDM[0][j-1],LM[0][j])

for (i=1;i

SDM[i][0]=SDM[i-1][0]+LM[i][0]

for (i=1;i

for (j=1;j

SDM[i][j]=min{SDM[i][j-1],

SDM[i-1][j]+LM[i][j]}

在圖4(a)中運(yùn)用DPResi算法，可以計(jì)算出該示例查詢(xún)對(duì)應(yīng)的SDM結(jié)果矩陣，如圖4(b)所示。SDM[3][2]為該示例的resilience解，即至少刪除3個(gè)元組，此查詢(xún)將不成立。通過(guò)回溯SDM即可得到需要?jiǎng)h除的元組集合，如圖4(b)中的回溯路徑，對(duì)應(yīng)到LM中得到其中一條回溯路徑為L(zhǎng)M[3][2] →LM[3][1] →LM[2][1] →LM[2][0] →LM[1][0] →LM[0][0]，即每行僅需刪除最左側(cè)元組后，該行將不成立，且去除孤立點(diǎn)，結(jié)果集合為{LM[3][1],LM[1][0],LM[0][0]}對(duì)應(yīng)圖3(a)所示溯源圖中原始元組集合為{x4,x3,y1}。

2.2.3 DPResi算法復(fù)雜度分析

路徑類(lèi)型IQ查詢(xún)語(yǔ)句在計(jì)算resilience時(shí)，對(duì)于原始查詢(xún)圖，由于不等關(guān)系的存在會(huì)導(dǎo)致結(jié)果圖中存在較多的邊，在M×N的連接圖中，邊的個(gè)數(shù)約為O(NM2)。而通過(guò)溯源表達(dá)式及溯源圖的表示，將路徑類(lèi)型IQ查詢(xún)的包含關(guān)系表示為矩陣的形式，邏輯意義上的連接邊數(shù)為O(MN)。在現(xiàn)在的大數(shù)據(jù)時(shí)代，數(shù)據(jù)庫(kù)中行數(shù)通?？赡苁前偃f(wàn)級(jí)或者更多，連接查詢(xún)時(shí)，連接表個(gè)數(shù)通常是較少的，即M?N。溯源圖將圖復(fù)雜度降低了一個(gè)數(shù)量級(jí)，且通過(guò)溯源矩陣替代鄰接表或鄰接矩陣存儲(chǔ)圖，僅需O(MN)的空間復(fù)雜度。

DPResi算法時(shí)間復(fù)雜度也為O(MN)，一趟掃描LM即可得到SDM最短距離矩陣。矩陣中SDM[M-1][N-1]的值代表左上角元組LM[0][0]到右下角元組LM[M-1][N-1]的最短距離，即為此查詢(xún)的resilience解，通過(guò)回溯SDM，可求得需要?jiǎng)h除的元組集合?；谒菰磮D求解resilience的算法時(shí)間復(fù)雜度與溯源矩陣圖中頂點(diǎn)個(gè)數(shù)V呈線性關(guān)系，易于擴(kuò)展到大規(guī)模數(shù)據(jù)集上，是擴(kuò)展性非常好的算法。

3 實(shí)驗(yàn)對(duì)比

實(shí)驗(yàn)在Windows系統(tǒng)下進(jìn)行，系統(tǒng)配置：內(nèi)存為8 GB，CPU為Intel Core i7- 4790@ 3.60 GHz，數(shù)據(jù)庫(kù)為PostgreSQL 9.0。DPResi算法及Min-Cut算法由C++語(yǔ)言編程實(shí)現(xiàn)，數(shù)據(jù)集采用的是TPC-H。

查詢(xún)語(yǔ)句 實(shí)驗(yàn)主要對(duì)比帶有不等式關(guān)系的路徑類(lèi)型查詢(xún)語(yǔ)句的resilience計(jì)算時(shí)間開(kāi)銷(xiāo)，因此，隨機(jī)選擇了4組路徑類(lèi)型IQ查詢(xún)語(yǔ)句用于性能對(duì)比，且為了覆蓋不同類(lèi)型、不同量級(jí)的查詢(xún)，這4組不等式查詢(xún)語(yǔ)句所包含的節(jié)點(diǎn)個(gè)數(shù)及元組都不盡相同。其中每組查詢(xún)包含4條具有不同過(guò)濾條件的查詢(xún)語(yǔ)句，算法時(shí)間開(kāi)銷(xiāo)主要與連接元組總個(gè)數(shù)V有關(guān)，因此通過(guò)過(guò)濾條件的不同來(lái)控制查詢(xún)所產(chǎn)生結(jié)果的元組數(shù)量(1X代表基準(zhǔn)查詢(xún)語(yǔ)句，2X、5X、10X分別代表結(jié)果元組數(shù)為基準(zhǔn)的2倍、5倍、10倍)。表2列出了1X大小下的4組查詢(xún)語(yǔ)句，表3列出了實(shí)驗(yàn)用到的16條查詢(xún)語(yǔ)句的查詢(xún)結(jié)果元組量。

在本文前面描述中，理論分析了DPResi算法與Min-Cut算法的時(shí)間復(fù)雜度，可知Min-Cut算法O(VE2)的時(shí)間復(fù)雜度遠(yuǎn)遠(yuǎn)超過(guò)了DPResi算法O(MN)的時(shí)間復(fù)雜度。在實(shí)驗(yàn)中，本文首先實(shí)現(xiàn)并驗(yàn)證了Min-Cut算法的可行性，且為了驗(yàn)證DPResi算法的高效性及可擴(kuò)展性設(shè)計(jì)了對(duì)比實(shí)驗(yàn)進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果如圖5所示，其中：橫軸表示查詢(xún)結(jié)果元組的量級(jí)，縱軸表示resilience計(jì)算所需時(shí)間(單位μs)。

表2 實(shí)驗(yàn)查詢(xún)語(yǔ)句

表3 查詢(xún)的數(shù)據(jù)規(guī)模

對(duì)于路徑類(lèi)型IQ查詢(xún)語(yǔ)句，通過(guò)圖5可知，在不同查詢(xún)中，DPResi算法時(shí)間開(kāi)銷(xiāo)均遠(yuǎn)遠(yuǎn)低于Min-Cut，且DPResi算法時(shí)間開(kāi)銷(xiāo)隨數(shù)據(jù)規(guī)模增大而線性增加，而Min-Cut算法呈多項(xiàng)式增長(zhǎng)。如Q7在10X的數(shù)據(jù)量級(jí)下，查詢(xún)結(jié)果元組數(shù)約為2.50×107，DPResi算法時(shí)間開(kāi)銷(xiāo)僅779 μs，與Min-Cut算法72 s的時(shí)間開(kāi)銷(xiāo)相比，耗時(shí)僅為Min-Cut算法的1.07×10-5，降低了99.99%。時(shí)間開(kāi)銷(xiāo)差距較大，性能優(yōu)勢(shì)明顯，DPResi算法對(duì)于路徑類(lèi)型IQ查詢(xún)語(yǔ)句resilience計(jì)算具有較高的效率，尤其在當(dāng)前信息爆炸的時(shí)代，其線性時(shí)間復(fù)雜度的開(kāi)銷(xiāo)能夠處理大規(guī)模數(shù)據(jù)集，有極好的可擴(kuò)展性。

圖5 兩種算法的時(shí)間開(kāi)銷(xiāo)對(duì)比

4 結(jié)語(yǔ)

本文提出一種對(duì)帶有不等式連接的路徑類(lèi)型查詢(xún)語(yǔ)句進(jìn)行因果關(guān)系resilience計(jì)算的DPResi算法，通過(guò)將查詢(xún)的溯源表達(dá)式編輯為溯源圖，有效地完成了路徑類(lèi)型IQ查詢(xún)語(yǔ)句的resilience計(jì)算，進(jìn)而更深層次地對(duì)所看到的查詢(xún)結(jié)果作出解釋?zhuān)脖阌谌藗儗?duì)當(dāng)前SQL查詢(xún)進(jìn)行干預(yù)。本文通過(guò)與現(xiàn)有的Min-Cut算法對(duì)比，驗(yàn)證了DPResi算法能夠極大地降低計(jì)算的時(shí)間開(kāi)銷(xiāo)，提升resilience計(jì)算效率，且能夠較好地?cái)U(kuò)展到大規(guī)模數(shù)據(jù)集上。在接下來(lái)的研究中，可將resilience計(jì)算由路徑類(lèi)型擴(kuò)展到樹(shù)類(lèi)型及圖類(lèi)型的查詢(xún)中，并提出更高效的算法來(lái)解決帶有等值連接與不等關(guān)系連接的混合查詢(xún)語(yǔ)句resilience計(jì)算的問(wèn)題。