不確定數(shù)據(jù)的有效查詢處理評估技術(shù)研究

金宗安，張志剛

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

1.引言

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

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

在表 1 Productp、表 2 Order、表 3 Buyerp三個關(guān)系中，其中右上角的p表示表1、表3為不確定關(guān)系，表1 Productp中name屬性為確定屬性，memory和color兩個屬性為不確定屬性，第1個元組表示產(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是一個不確性的關(guān)系模式，其中的每一個屬性用 Ai表示，i∈{1,2,3,…n,…}，A是所有屬性的集合，A={A1,A2,…An}，每一個屬性Ai都有一個域，記為Di，每一個元組x都是不確定性的，x(Ai)表示元組x在屬性Ai上的值，不確定關(guān)系R上的每一個元組x可以描述為<屬性，值>的模式，其中值為 ps，即，這樣的關(guān)系稱為不確定關(guān)系。

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

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

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

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

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

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)

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

表4 Q1查詢結(jié)果

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

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

表5 Q2查詢結(jié)果

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

表6 Q3查詢結(jié)果

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

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

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

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

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

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

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

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

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

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

算法1：

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

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

在查詢評估算法中，如果一個查詢只是針對一個不確定關(guān)系，只需要按照查詢的要求，查詢滿足條件的數(shù)據(jù)進行不相容元組投影再相互獨立元組投影即可；如果查詢的結(jié)果中存在不相容的相等元組或相互獨立相等的元組，則要分別按照（1）（2）中的方法進行合并操作；如果查詢Q可以分解為Q1、Q2兩個查詢，并且分解的復(fù)雜度比原來的小，則可以把原查詢分解為Q1、Q2的連接查詢。如果查詢在上面的方法中都不能得到解決，則這個查詢不能正確計算概率。

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

5.實驗分析

不確定數(shù)據(jù)查詢的實驗環(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編程語言實現(xiàn)，實驗結(jié)果取3次實驗平均值。

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

表6 TPC-H 查詢時間

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

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

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

6.結(jié)束語

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