金宗安，張志剛

（六安職業(yè)技術(shù)學(xué)院，安徽 六安 237158）

1.引言

許多現(xiàn)實(shí)生活中的應(yīng)用程序產(chǎn)生大量的不確定數(shù)據(jù)，需要存儲(chǔ)、檢索和查詢這些數(shù)據(jù)的系統(tǒng)。傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)面向存儲(chǔ)精確的數(shù)據(jù)，不適合存儲(chǔ)不確定的數(shù)據(jù)。另一方面，設(shè)計(jì)不確定數(shù)據(jù)庫來處理概率表示的不確定性，并設(shè)置特別的選項(xiàng)來存儲(chǔ)具有不確定性的數(shù)據(jù)。不確定數(shù)據(jù)庫的應(yīng)用包括信息檢索[1]，推薦系統(tǒng)[2]，移動(dòng)對(duì)象數(shù)據(jù)管理[3]，信息提取[4]，數(shù)據(jù)集成[5]和傳感器網(wǎng)絡(luò)的數(shù)據(jù)管理[6]等。

由于不確定數(shù)據(jù)的處理是基于可能世界的，有些針對(duì)不確定數(shù)據(jù)的查詢?cè)诰€性時(shí)間內(nèi)是不可完成的，例如：自連接查詢、存在環(huán)的連接查詢等，而目前并沒有有效的方法來判定一個(gè)不確定數(shù)據(jù)的查詢是否線性時(shí)間內(nèi)可計(jì)算。本文設(shè)計(jì)算法，把不確定關(guān)系中元組分為不相容元組和相互獨(dú)立元組，有效的評(píng)估哪線查詢是線性時(shí)間內(nèi)可計(jì)算，哪些是不可計(jì)算的。

在表 1 Productp、表 2 Order、表 3 Buyerp三個(gè)關(guān)系中，其中右上角的p表示表1、表3為不確定關(guān)系，表1 Productp中name屬性為確定屬性，memory和color兩個(gè)屬性為不確定屬性，第1個(gè)元組表示產(chǎn)品iphone 6s plus在上取值為<32G,golden>的概率為p1=0.21，取值為<32G,silvery>的概率為 p2=0.19，p1+p2=0.4。 iphone 6s plus在 上取值為<128G,silvery>的概率為p3=0.20。而p1+p2+p3=0.6<1，表示在屬性上的取值還有其它可能。

表1 Productp

表2 Order

表3 Buyerp

2.基本定義

定義1 不確定關(guān)系：R是一個(gè)不確性的關(guān)系模式，其中的每一個(gè)屬性用 Ai表示，i∈{1,2,3,…n,…}，A是所有屬性的集合，A={A1,A2,…An}，每一個(gè)屬性Ai都有一個(gè)域，記為Di，每一個(gè)元組x都是不確定性的，x(Ai)表示元組x在屬性Ai上的值，不確定關(guān)系R上的每一個(gè)元組x可以描述為<屬性，值>的模式，其中值為 ps，即，這樣的關(guān)系稱為不確定關(guān)系。

定義2 不確定屬性：不確定關(guān)系中的元組發(fā)生具有不確定性，因此每一個(gè)元組都有一個(gè)不確定屬性記錄它們發(fā)生的概率值，記為ps，ps∈(0,1]，元組x概率屬性ps表示對(duì)象x(R-{pS})發(fā)生的概率：

定義3 投影運(yùn)算π：在不確定關(guān)系R中，有k個(gè)元組在不確定屬性A上具有相同的值，概率分別為p1,p2,…,pk，若它們的關(guān)鍵字屬性相同，則此時(shí)投影稱為不相容事件的投影πPDA，在A屬性上投影的概率記為p1+p2+…+pk；若它們的關(guān)鍵字屬性不相同，則此時(shí)投影稱為相互獨(dú)立事件投影πPIA，在A屬性上投影的概率記為 1-(1-p1)(1-p2)…(1-pk)。

定義4 不確定數(shù)據(jù)連接查詢∞p：A、B兩個(gè)關(guān)系的連接查詢可以定義為其中c為兩個(gè)連接查詢的條件。由于已經(jīng)定義了選擇和笛卡爾乘積，連接查詢可以根據(jù)定義來獲得，選擇查詢可能會(huì)引入屬性之間的依賴關(guān)系。兩個(gè)元組t1和t2分別屬于兩個(gè)不確定關(guān)系A(chǔ)、B，它們的概率分別是p1和p2，則兩個(gè)元組連接查詢的概率為p1*p2。

3.不確定數(shù)據(jù)查詢

下面3個(gè)標(biāo)準(zhǔn)SQL查詢語句及其相應(yīng)的標(biāo)識(shí)公式，查詢語句假設(shè)3個(gè)關(guān)系都是確定性的，不考慮元組的概率屬性，查詢得到的結(jié)果會(huì)有一個(gè)概率屬性值，代表了元組的可信度。

Q1：SELECT DISTINCT name,memory

FROM Productp

WHERE name=‘iphone 6s plus’

Q1(‘iphone 6s plus’,x):-Productp(‘iphone 6s plus’,x,y)

Q2:SELECT DISTINCT address

FROM Buyerp

Q2(v):-Buyerp(u,v)

Q3:SELECT DISTINCT*

FROM Productp,Order,Buyerp

WHERE Productp.name=Order.nameandOrder.orderer=Buyerp.orderer and Productp.color=Order.color

Q3(*):-Productp(x,y,z)

Order(u,x,y,z)

Buyerp(u,v)

在第一個(gè)查詢語句Q1中，查詢不確定關(guān)系Productp中name=‘iphone 6s plus’的信息，查詢的結(jié)果為：

表4 Q1查詢結(jié)果

對(duì)于查詢Q1，計(jì)算查詢結(jié)果的概率時(shí)，不用列舉所有的可能世界，可以從表中直接計(jì)算：（1）選擇name=‘iphone 6s plus’ 的行；（2） 在 name,memory 上投影；（3）由于第1個(gè)元組和第2個(gè)元組是不相容元組，投影后的值是一樣的，因此要合并元組，合并后的元組概率為之前兩個(gè)元組的概率之和。

對(duì)于查詢Q2，計(jì)算查詢結(jié)果概率時(shí)，采取與查詢Q1相似的方法，但在合并元組過程中，存在相互獨(dú)立投影，例如對(duì)于address=ShangHai條件第一個(gè)元組和第三個(gè)元組都滿足，采用合并的方法消除重復(fù)元組，這兩個(gè)元組進(jìn)行投影合并時(shí)要使用相互獨(dú)立投影方法計(jì)算它們的概率，查詢結(jié)果如下表所示：

表5 Q2查詢結(jié)果

第三個(gè)查詢是多關(guān)系連接查詢，連接查詢只限制了連接條件，查詢得到的結(jié)果共有4條記錄，表中沒有重復(fù)元組，不需要進(jìn)行其它操作，查詢結(jié)果如下表所示：

表6 Q3查詢結(jié)果

有的查詢結(jié)果中既有不相容的重復(fù)元組，又有相互獨(dú)立重復(fù)元組，此時(shí)先要消除不相容，再消除相互獨(dú)立元組。

4.不確定數(shù)據(jù)查詢算法

在不確定關(guān)系中，連接查詢要進(jìn)行有效的評(píng)估，因?yàn)橛行┎樵冊(cè)诰€性時(shí)間內(nèi)能夠得到解決，但有些查詢對(duì)象的多個(gè)關(guān)系中存在鍵的約束問題，使得查詢不能在線性時(shí)間內(nèi)完成的（#p完全），比如不確定關(guān)系的自連接查詢，因此要設(shè)計(jì)有效算法評(píng)估哪些查詢是線性時(shí)間內(nèi)可計(jì)算，哪些是#P完全的。

算法相關(guān)的定義如下：

Rels(Q)={R1,…,Rk}是指發(fā)生在查詢語句Q中的所有不確定關(guān)系的集合，假設(shè)每個(gè)不確定關(guān)系至多出現(xiàn)一次。

Attr(Q)表示查詢語句Q中所有不確定關(guān)系的所有屬性集合，Ri.A表示第i個(gè)不確定關(guān)系R的A屬性；

Head(Q)表示查詢語句Q中所要查詢的屬性集合，很顯然有

R.Key代表不確定關(guān)系R中的關(guān)鍵字屬性；

R.NKey代表不確定關(guān)系R中的非關(guān)鍵字屬性；

Qx表示一個(gè)帶有x屬性的查詢Q，則

算法1：

if q是一個(gè)單個(gè)關(guān)系查詢

如果不滿足以上情況，則返回Q是#P完全的；

在查詢?cè)u(píng)估算法中，如果一個(gè)查詢只是針對(duì)一個(gè)不確定關(guān)系，只需要按照查詢的要求，查詢滿足條件的數(shù)據(jù)進(jìn)行不相容元組投影再相互獨(dú)立元組投影即可；如果查詢的結(jié)果中存在不相容的相等元組或相互獨(dú)立相等的元組，則要分別按照（1）（2）中的方法進(jìn)行合并操作；如果查詢Q可以分解為Q1、Q2兩個(gè)查詢，并且分解的復(fù)雜度比原來的小，則可以把原查詢分解為Q1、Q2的連接查詢。如果查詢?cè)谏厦娴姆椒ㄖ卸疾荒艿玫浇鉀Q，則這個(gè)查詢不能正確計(jì)算概率。

在概率數(shù)據(jù)庫中，大部分的連接查詢結(jié)果的計(jì)算都是很容易處理的，這些查詢都能夠在線性的時(shí)間內(nèi)解決，但是一部分連接查詢的結(jié)果可能會(huì)違反一些鍵約束，因此計(jì)算連接查詢可能是#P完全的，這部分所討論的查詢不包括自連接查詢。

5.實(shí)驗(yàn)分析

不確定數(shù)據(jù)查詢的實(shí)驗(yàn)環(huán)境為Windows 7操作系統(tǒng)，Intel(R)Core(TM)i5-4200M CPU,主頻 2.50Ghz，內(nèi)存4GB，用DataFactory生成不確定數(shù)據(jù)，數(shù)據(jù)尺寸s=0.03GB，約100萬元組，使用JAVA編程語言實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果取3次實(shí)驗(yàn)平均值。

實(shí)驗(yàn)首先測(cè)試了10個(gè)TPC-H查詢中有多少查詢不能正確的計(jì)算概率（不安全的）。實(shí)驗(yàn)對(duì)數(shù)據(jù)進(jìn)行了優(yōu)化，把概率為0的元組刪除。從表6中可以看出10個(gè)TPC-H查詢有8個(gè)是安全的，能夠正確計(jì)算概率。Q7和Q8是不安全的查詢，這主要是由于查詢謂詞的不確定性。對(duì)數(shù)據(jù)進(jìn)行了優(yōu)化，刪除了概率為0的元組，這樣處理并不會(huì)對(duì)查詢的結(jié)果造成影響，但節(jié)約了大量的查詢時(shí)間，從表6中可以看出優(yōu)化后的查詢時(shí)間一般來說較短。

表6 TPC-H 查詢時(shí)間

由于很多用戶只關(guān)心查詢結(jié)果Top-k個(gè)元素 （查詢結(jié)果有N個(gè)，k遠(yuǎn)小于N），而對(duì)查詢得到的概率很小或k+1到N個(gè)查詢結(jié)果并不是很感興趣，因此選擇TPC-H中Q3、Q9作為查詢實(shí)驗(yàn)對(duì)象，查詢?cè)M的返回率為k/N，也就是說當(dāng)要求返回元組數(shù)即為滿足查詢條件的元組數(shù)時(shí)，返回率為1。從圖中可以看出，當(dāng)k數(shù)量很小時(shí)，返回率很低，這樣很容易丟失大量的有關(guān)聯(lián)的數(shù)據(jù)。

表7 不同關(guān)聯(lián)度數(shù)據(jù)TPC-H查詢

表7顯示了對(duì)不同關(guān)聯(lián)度D＝0.3，0.6，0.9分別進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)選用了TPC-H中的Q2,Q3,Q5,Q6,Q9,Q10，從表中可以看出不同查詢?cè)谕粩?shù)據(jù)上的執(zhí)行時(shí)間不相同，同一查詢針對(duì)不同關(guān)聯(lián)度的數(shù)據(jù)處理的時(shí)間也是不相同的?？傮w上，關(guān)聯(lián)度越低，執(zhí)行的時(shí)間越短；相反，關(guān)聯(lián)度越高，執(zhí)行的時(shí)間就越長(zhǎng)。這主要是由于隨著關(guān)聯(lián)度的增高，可能世界的數(shù)量會(huì)呈指數(shù)級(jí)的增長(zhǎng)。

6.結(jié)束語

本文設(shè)計(jì)不確定數(shù)據(jù)查詢有效算法，對(duì)數(shù)據(jù)查詢進(jìn)行有效評(píng)估，采用不同關(guān)聯(lián)度數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果顯示，當(dāng)不確定數(shù)據(jù)的關(guān)聯(lián)度較低時(shí)，數(shù)據(jù)查詢時(shí)間較短，而當(dāng)數(shù)據(jù)之間關(guān)聯(lián)度比較高時(shí)，可能世界數(shù)量呈指數(shù)級(jí)增長(zhǎng)，查詢時(shí)間也會(huì)越來越長(zhǎng)。但對(duì)不確定數(shù)據(jù)的研究?jī)?nèi)容還有很多，例如不確定數(shù)據(jù)的聚集查詢、查詢優(yōu)化、自連接查詢、不確定數(shù)據(jù)空值的處理等，一些數(shù)據(jù)查詢的復(fù)雜性是#P完全的，這些查詢沒有有效的計(jì)算方法，尋求近似計(jì)算的方法來解決此類問題也是研究的一個(gè)方向。