概率數(shù)據(jù)庫研究問題綜述

王雅瑜，熊　婧，林　軍（工業(yè)和信息化部電子第五研究所軟件質(zhì)量工程研究中心，廣州510610）

概率數(shù)據(jù)庫研究問題綜述

王雅瑜，熊婧，林軍
（工業(yè)和信息化部電子第五研究所軟件質(zhì)量工程研究中心，廣州510610）

概率數(shù)據(jù)庫的管理，在不確定數(shù)據(jù)處理需求與日俱增的今天變得極為重要。一個概率數(shù)據(jù)庫管理系統(tǒng)，是一個能夠存儲大量概率數(shù)據(jù)并提供復(fù)雜查詢方法的數(shù)據(jù)庫管理系統(tǒng)，而且要能對概率計算進(jìn)行處理。在PRM模型的基礎(chǔ)上，根據(jù)現(xiàn)階段研究概況，給出由對象屬性、靜態(tài)屬性、動態(tài)屬性、概率屬性組合而成的概率數(shù)據(jù)庫模型；針對概率數(shù)據(jù)處理的應(yīng)用需求，論述查詢計算及查詢排序的方法及其特點，以及概率數(shù)據(jù)庫中安全問題的處理方法。

概率數(shù)據(jù)庫；概率數(shù)據(jù)庫管理；不確定數(shù)據(jù)；查詢計算；查詢排序

2012“核高基”科技專項（No.2012ZX01045-006-003）

0　引言

最近幾年，在很多新興的數(shù)據(jù)應(yīng)用中，對不確定數(shù)據(jù)的處理需求與日俱增。不確定數(shù)據(jù)來源很廣：傳感數(shù)據(jù)處理、科學(xué)計算、數(shù)據(jù)綜合與清理[1]、信息提取[2]、自然語言分析、圖像識別、數(shù)據(jù)錄入偏差等。傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)操作的數(shù)據(jù)對象都是確定的，完整的，對這一類不確定數(shù)據(jù)缺乏處理方法。而用戶們需要對它們分析、整理，從而找到自己需要的結(jié)果。近年來，研究者們對相關(guān)的問題做了許多工作，提出了概率數(shù)據(jù)庫的概念，以解決對不確定數(shù)據(jù)的處理。本文對這些工作進(jìn)行了分析和總結(jié)，闡述了概率數(shù)據(jù)庫中的幾個關(guān)鍵問題及研究方法。

1　概率數(shù)據(jù)庫的基本概念

1.1概率數(shù)據(jù)庫的概念與應(yīng)用

概率數(shù)據(jù)庫是根據(jù)不確定數(shù)據(jù)處理的需要而提出的。然而，對不確定或不完整數(shù)據(jù)的處理在上世紀(jì)八、九十年代就已有研究。Immelinski等在文獻(xiàn)[3]中提出了c-table這一形式來表示一個不完整的數(shù)據(jù)庫；Barbara等在文獻(xiàn)[4]中用概率理論提出了關(guān)系模式的擴(kuò)展，重新定義了投影、選擇、等操作，對概率數(shù)據(jù)提出了一個描述模型；Shashi K.Gadia等在文獻(xiàn)[5]中給出了一個包含完整信息的臨時數(shù)據(jù)庫模型，在此基礎(chǔ)上又給出了包含不完整信息的臨時數(shù)據(jù)庫模型，并研究了相關(guān)的查詢代數(shù)；等等。其中一些對不確定數(shù)據(jù)的處理方法、理論仍舊是現(xiàn)今研究的基礎(chǔ)。

N.Dalvi等在文獻(xiàn)[6]中對概率數(shù)據(jù)庫管理系統(tǒng)做了以下定義：一個概率數(shù)據(jù)庫管理系統(tǒng)，是一個能夠存儲大量概率數(shù)據(jù)并提供復(fù)雜查詢方法的數(shù)據(jù)庫管理系統(tǒng)，而且要能對概率計算處理。文章還指出，概率數(shù)據(jù)庫管理系統(tǒng)也可包含更新、恢復(fù)等功能，不過這些功能與傳統(tǒng)數(shù)據(jù)庫并無不同，主要的難點在查詢上。許多在概率數(shù)據(jù)庫方面的研究也著力于top-k查詢的處理[7]，出現(xiàn)了多種不確定性top-k查詢的語義和處理方法。

概率數(shù)據(jù)的應(yīng)用來源主要分為兩大類。一類是本身不可避免的模糊的、不確定的數(shù)據(jù)的應(yīng)用。例如傳感器傳送的數(shù)據(jù)、測量誤差、移動設(shè)備的數(shù)據(jù)噪聲、網(wǎng)絡(luò)延時造成的影響、圖像的識別、文本的信息提取、數(shù)據(jù)更新不一致帶來的數(shù)據(jù)沖突、歧義等。另一類不確定數(shù)據(jù)應(yīng)用的產(chǎn)生是人為的、出于特定需要的考慮。例如牽涉?zhèn)€人隱私保護(hù)的應(yīng)用中，可以通過不確定數(shù)據(jù)隱藏一些敏感信息[8]；一些數(shù)據(jù)清理應(yīng)用中，可以通過保留不確定數(shù)據(jù)來提高效率；對不確定數(shù)據(jù)的計算結(jié)果也會成為不確定數(shù)據(jù)的來源，等等。

1.2概率數(shù)據(jù)庫的主要研究問題

N.Dalvi等在文獻(xiàn)[6]中指出了概率數(shù)據(jù)庫研究的三個重要方面：怎樣存儲或表達(dá)一個概率數(shù)據(jù)庫；怎樣用這樣的表示去響應(yīng)查詢；怎樣將查詢結(jié)果返回給用戶。后兩個主要是對查詢的處理方法的研究，是近年來研究的重點。另外，Christoph Koch等在文獻(xiàn)[9]中研究了有效計算可信度并對概率數(shù)據(jù)進(jìn)行條件過濾的方法。Vibhor Rastogi等在文獻(xiàn)[10]中研究了對不確定數(shù)據(jù)實施訪問控制的方法。Qin Zhang等在文獻(xiàn)[11]中分別對靜態(tài)的和動態(tài)的不確定數(shù)據(jù)給出了計算高頻記錄的算法。Saket Sathe等在文獻(xiàn)[12]中研究了為不確定的時間序列創(chuàng)建概率數(shù)據(jù)庫的方法。Jianwen Chen等在文獻(xiàn)[13]研究概率數(shù)據(jù)庫的集合運(yùn)算結(jié)果概率計算的精確方法和近似方法。Christopher R'e在文獻(xiàn)[14]總結(jié)了通過Top-k查詢以及聚集計算、物化視圖等方法對大規(guī)模不確定數(shù)據(jù)的處理方法。

本文將目前對概率數(shù)據(jù)庫的研究大致概括為三方面：①概率數(shù)據(jù)庫的表示；②概率數(shù)據(jù)庫中查詢的處理；③概率數(shù)據(jù)庫的安全問題。下面將對這三方面問題分別闡述。

1.3一個具體實例

為了方便問題的說明，本文給出一個學(xué)生管理的實例。如表1，是一個學(xué)生-班級表。表中，學(xué)生Li Lei、Han Meimei所在班級不唯一，這在實際情況中是不可能的。造成這種結(jié)果的原因可能是數(shù)據(jù)錄入時的輸入模糊，或者數(shù)據(jù)更新不一致導(dǎo)致的數(shù)據(jù)沖突等。表中第三列概率p，是對數(shù)據(jù)不確定度的一種表示，來源于得到數(shù)據(jù)的工具。為了簡化問題，本文假定表中兩個人的記錄之間是相互獨立的。

表1　概率數(shù)據(jù)庫學(xué)生-班級表a

2　概率數(shù)據(jù)庫的表示

傳統(tǒng)的關(guān)系數(shù)據(jù)庫處理不了包含概率的數(shù)據(jù)，因此要對數(shù)據(jù)庫模型加以擴(kuò)展。許多科研工作者都提出了自己對概率關(guān)系數(shù)據(jù)模型的描述。目前，普遍被認(rèn)可的概率關(guān)系模型有兩種——BGP框架和DS框架，金宗安在文獻(xiàn)[15]中大致總結(jié)了這兩個模型的優(yōu)缺點。Debabrata Dey和Sumit Sarkar提出了PRM[16]模型（Probabilistic Relational Model），該模型在數(shù)據(jù)庫的每個元組中引入概率標(biāo)記屬性表示元組的不確定性。本文在該模型基礎(chǔ)上，總結(jié)現(xiàn)階段研究概況，給出以下概率數(shù)據(jù)庫模型。

一個概率關(guān)系模式R{A1，A2，…，An}由對象屬性K、靜態(tài)屬性S、動態(tài)屬性T、概率屬性P組合而成。對象屬性是一個對象或事件的標(biāo)識，靜態(tài)屬性是伴隨該對象存在的相對穩(wěn)定的特性，動態(tài)屬性是在該對象存在的情況下，具有多種可能性的屬性，概率屬性則描述了這種可能性，取值范圍（0,1]。概率關(guān)系模式R{A1，A2，…，An}上每一屬性的取值范圍稱為屬性域，記為dom（Ai），模式上屬性域中值的笛卡爾積稱為關(guān)系模式R上的值域，記為dom（R）=dom（A1）×dom（A2）×…×dom（An）。關(guān)系模式R上的一個元組t就是從模式R到值域上的一個映射t:R→dom（R）。

如表1，對象屬性是Name，靜態(tài)屬性是Gender，動態(tài)屬性是Class，概率屬性是p。這種概率關(guān)系模式是對傳統(tǒng)關(guān)系模式的屬性進(jìn)行了區(qū)分，并增加了概率屬性的概念。形式上它類似傳統(tǒng)關(guān)系模式，一個元組也是二維表中的一行，本質(zhì)上它描述某事件發(fā)生的概率。傳統(tǒng)數(shù)據(jù)庫模型中，一條元組即可代表現(xiàn)實世界的一個對象（記錄）；而在概率數(shù)據(jù)庫模型中，一條元組也許只是一個對象的一種可能表示，一個對象可能需要幾個元組來表示其各種取值的聯(lián)合概率分布。

表1中，Li Lei和Han Meimei的記錄是相互獨立的，而Li Lei記錄包含的三條元組是互斥關(guān)系。N.Dalvi等在文獻(xiàn)[6]中把包含這樣的表的概率數(shù)據(jù)庫稱為BID (Block Independent-Disjoint)。即所有的元組可以劃分成幾塊，每塊里的元組互斥，不同塊的元組相互獨立。

比起傳統(tǒng)數(shù)據(jù)庫模型中的關(guān)系運(yùn)算，概率數(shù)據(jù)庫模型中的關(guān)系運(yùn)算也有所改動。例如當(dāng)對元組進(jìn)行合并或投影操作時，根據(jù)元組之間關(guān)系的不同，需采取不同的規(guī)則。對于互斥的多個元組，進(jìn)行投影操作時，使用的是互斥事件的概率計算公式p=p1+p2+…+pn；對于相互獨立的多個元組，進(jìn)行投影操作時，使用的是相互獨立事件的概率計算公式p=1-（1-p1）（1-p2）…（1-pn）。當(dāng)在投影操作過程中，既有互斥元組，也有相互獨立元組，則要先對互斥元組進(jìn)行合并，再對相互獨立的元組合并。例如表1，如果Class定為7，要對Class屬性投影，則相應(yīng)的概率p=1-（1-0.3）（1-0.8）=0.86。

表1的學(xué)生-班級表中還有一個屬性，形如Xi=j，這樣的表示叫做lineage，是指對一個元組所加的注釋。Immelinski等在文獻(xiàn)[3]中提出了c-table這一形式來表示一個不確定數(shù)據(jù)庫。在c-table中，一個元組由這樣的屬性經(jīng)過布爾運(yùn)算表示。例如表1，若要對Class屬性投影，采用c-table的表示如表2。

表2　采用c-table表示C lass上的投影

使用lineage既可以表示概率數(shù)據(jù)，也可以表示查詢結(jié)果[6]。對c-table的一個查詢結(jié)果仍舊可以用ctable和相應(yīng)的屬性表示，易于理解和處理。而且，通過它可以將用戶對查詢結(jié)果的反饋跟蹤到原數(shù)據(jù)。因此，在概率數(shù)據(jù)庫中，lineage有很重要的作用。

3　概率數(shù)據(jù)庫的查詢

概率數(shù)據(jù)庫管理系統(tǒng)需要提供復(fù)雜的、強(qiáng)大的概率數(shù)據(jù)處理能力以滿足應(yīng)用需求。其中的研究重點在查詢的處理上。因為傳統(tǒng)的數(shù)據(jù)庫運(yùn)算，如選擇、投影、連接等無法處理包含概率的數(shù)據(jù)；而在更新、刪除等操作上，概率數(shù)據(jù)庫與傳統(tǒng)數(shù)據(jù)庫并無很大差別。

由于自身特點，概率數(shù)據(jù)庫的查詢主要包含兩個問題：①查詢計算的處理；②查詢結(jié)果的處理。

3.1查詢計算

一般，對概率數(shù)據(jù)的查詢計算有兩個邏輯步驟：首先獲得數(shù)據(jù)并做相應(yīng)轉(zhuǎn)換，其次采用概率算法對數(shù)據(jù)做概率推演。簡單的方法是使用數(shù)據(jù)庫引擎做第一步，使用概率推演技術(shù)做第二步。研究工作者們提出了許多算法做這樣的處理。還有一種方法是將這兩個步驟合起來放在數(shù)據(jù)庫中處理。這樣的優(yōu)點在于可以使用數(shù)據(jù)庫本身的機(jī)制和技術(shù)處理數(shù)據(jù)，簡化了概率推演的復(fù)雜度，尤其在需要對數(shù)據(jù)進(jìn)行聚集處理時。但后者需要查詢語句本身是“安全”的才能完成[6]。

安全查詢是指能夠?qū)⑷扛怕释蒲莘诺讲樵冇媱澲刑幚淼牟樵儯幌鄳?yīng)的，安全計劃是指能夠使用擴(kuò)展的概率關(guān)系代數(shù)處理概率計算，進(jìn)而處理查詢的計劃。表3所示為與表1對應(yīng)的學(xué)生-成績表。對于一個查詢“SELECT a.Class,Confidence（）FROM a,b WHERE a. Name=b.Name and b.Subject='English'and a.Class=7”，如果執(zhí)行計劃的關(guān)系代數(shù)是πClass（σClass='7'（a??πName（σSubject='English'（b）））），則計算的概率結(jié)果是1-（1-p2q1）（1-p2q2）；如果執(zhí)行計劃的關(guān)系代數(shù)是，則計算的概率結(jié)果是p2（1-（1-q1）（1-q2））。在傳統(tǒng)數(shù)據(jù)庫中，兩種執(zhí)行計劃的結(jié)果應(yīng)該是等效的，差別只在于是否先對b表做Name上的投影。而如果采用上文提到的c-table表示這樣的查詢，則相應(yīng)的lineage應(yīng)當(dāng)是（X1=2/Y1=1）/（X1=2/Y1=2），因此正確的執(zhí)行計劃是后一種，即概率結(jié)果應(yīng)當(dāng)是p2（1-（1-q1）（1-q2））。造成這種差別的原因是表3中的前兩個元組并非相互獨立，而連接操作對這樣的情況無法正確計算?？梢?，對同一查詢語句的不同執(zhí)行計劃在計算概率上有可能不同。N.Dalvi等在文獻(xiàn)[6]中對這個問題有更詳盡的描述。

表3　概率數(shù)據(jù)庫學(xué)生-成績表b

聚集查詢在數(shù)據(jù)統(tǒng)計中有很廣泛的應(yīng)用。在概率數(shù)據(jù)庫中，聚集查詢需要考慮對象的每一種可能性。如果查詢元組有N個，那么聚集查詢的結(jié)果有可能到2N個，尤其在非安全查詢中，計算十分困難。研究工作者們提出了各種方法處理概率數(shù)據(jù)庫中類似的大計算量的問題。有的工作對聚集函數(shù)進(jìn)行改造；有的工作在查詢中設(shè)置了相關(guān)參數(shù)；有的工作采用實體化視圖將非安全查詢轉(zhuǎn)化為對安全查詢的處理，等等。

概率數(shù)據(jù)的查詢中，經(jīng)過大量復(fù)雜計算產(chǎn)生的結(jié)果有時并非對所有用戶都很有意義，這樣既耗費(fèi)資源，又無法讓用戶滿意。因此需要對查詢結(jié)果排序、過濾。

3.2查詢排序

由于概率數(shù)據(jù)庫處理對象的模糊特性，不同用戶對查詢結(jié)果的需求也不同。怎樣和用戶交互，返回最合適的查詢結(jié)果，是一個難題，也是目前研究的熱點。

常用的一種方法是將查詢結(jié)果按照一定的標(biāo)準(zhǔn)排序，只返回k個排序靠前的元組給用戶，這一般被稱作Top-k查詢問題。這一方法降低了查詢計算的復(fù)雜度，提高了查詢性能。在傳統(tǒng)數(shù)據(jù)庫中也有廣泛應(yīng)用。然而在概率數(shù)據(jù)庫中，數(shù)據(jù)的不確定性、用戶的不同要求，使得使用什么樣的排序標(biāo)準(zhǔn)成了一個問題。例如，可以返回k個具有最高分值的元組，或者k個概率最大的元組，或者k個最小期望排序的元組，等等。具體使用哪種排序方法要根據(jù)實際需求決定?，F(xiàn)今的許多工作針對不同情況提出了各種排序算法。Christopher等在計算Top-k時，主要使用的方法是同時并列使用多個Monte-Carlo模擬算法[17]；Ming Hua等提出了一個基于泊松估計的算法，通過設(shè)定概率的閾值返回不確定數(shù)據(jù)的Top-k查詢結(jié)果[18]；Dylla M等提供了一種通過計算條件概率的邊界值來獲得top-k查詢結(jié)果的算法[19]。

Jian Li等在文獻(xiàn)[20]中提出了一個統(tǒng)一的Top-k查詢排序方法。它將該問題看作一個多標(biāo)準(zhǔn)的最優(yōu)化問題，認(rèn)為一個單獨的排序函數(shù)無法滿足概率數(shù)據(jù)庫的需要，提出了兩個帶參數(shù)的函數(shù)PRFW和PRFE來模擬已有的排序函數(shù)。文中首先根據(jù)概率數(shù)據(jù)庫的模型，對數(shù)據(jù)庫定義了一系列能夠指示排序結(jié)果的關(guān)鍵屬性（即元組排列在某位的概率）；然后在已有的一些概率數(shù)據(jù)排序函數(shù)的基礎(chǔ)上，根據(jù)關(guān)鍵屬性定義了兩個帶參數(shù)的排序函數(shù)PRFW和PRFE；函數(shù)的參數(shù)可以通過在小數(shù)據(jù)集上對用戶需求的排序而學(xué)習(xí)得到；這兩個函數(shù)包含了現(xiàn)有的一些排序函數(shù)，也可以模擬一些其他排序函數(shù)；文章還設(shè)計了一個根據(jù)這些排序函數(shù)找到Top-k查詢結(jié)果的有效算法。與其他類似工作相比，該方法有一定的普適性，并且能夠與用戶交互。

4　概率數(shù)據(jù)庫的安全

數(shù)據(jù)庫安全是指數(shù)據(jù)庫的信息不受惡意侵害或未經(jīng)授權(quán)的訪問和修改。其內(nèi)涵包括三方面：保密性、完整性、可用性。對傳統(tǒng)數(shù)據(jù)庫管理系統(tǒng)的安全性研究已經(jīng)比較成熟，身份鑒別、訪問控制、數(shù)據(jù)加密、審計等機(jī)制都可以保障數(shù)據(jù)庫安全。而對概率數(shù)據(jù)庫的安全性研究則剛開始。下面以自主訪問控制為例說明概率數(shù)據(jù)庫中的安全問題。

傳統(tǒng)數(shù)據(jù)庫中，用戶的自主訪問權(quán)限一般通過訪問控制矩陣表示。假設(shè)數(shù)據(jù)庫中的訪問只有“讀”，矩陣元素M[si，oj]=1，表示用戶si對對象oj有讀權(quán)限；M[si，oj] =0，表示用戶si沒有oj的讀權(quán)限。但是，在概率數(shù)據(jù)庫中，數(shù)據(jù)對象本身就是不確定的、以概率的形式表示的，因此對其權(quán)限的控制也無法輕易地用0或1決策，而要用概率代替。例如對本文的學(xué)生管理例子，加入教師元素，同時有這樣的訪問控制策略：教師只能查看自己班級學(xué)生的成績，那么7班的教師能不能查詢Li Lei的成績？下面假設(shè)教師能查詢Li Lei成績的概率為p，最終查詢的結(jié)果為r。

一種方法是設(shè)置一個閾值b（0≤b≤1），如果p≥b，則r=pt（pt為查詢對象t的概率，這里理解對對象的查詢即是對其概率的查詢），如果p＜b，則r=deny。該方法實施簡單，缺點在于閾值b的選取很關(guān)鍵，對于不同應(yīng)用可能有不同要求，很難制定統(tǒng)一標(biāo)準(zhǔn)。

還有一種方法是抽樣。該方法類似于隨機(jī)擲骰子，骰子為p的概率為1，（1-p）的概率為0。若結(jié)果為1，r= pt，反之r=deny。擲骰子的時機(jī)是用戶做一系列的查詢前，而并非對每一個查詢，這是為了防止攻擊者通過多次重復(fù)查詢推算出概率值。該方法有可能導(dǎo)致系統(tǒng)漏洞。即使用戶能夠訪問某數(shù)據(jù)的概率很低，在此方法下仍有可能執(zhí)行訪問。

Vibhor Rastogi等通過對結(jié)果加入隨機(jī)噪聲的方法來實現(xiàn)概率數(shù)據(jù)的訪問控制[21]。用戶對對象t的訪問結(jié)果r=pt+n，其中n是噪聲，其選擇由關(guān)于p的函數(shù)決定。當(dāng)p=1時，n為0；當(dāng)p=0時，n是一個使得r成為與pt無關(guān)的隨機(jī)噪聲的值，即表示deny。該方法稍復(fù)雜，但是不論p為多少，都能給用戶一個返回值，較平滑地實現(xiàn)了對概率數(shù)據(jù)的訪問控制。

概率數(shù)據(jù)庫安全性的研究還包括數(shù)據(jù)加密、推理控制、隱通道判斷等，但相關(guān)文獻(xiàn)很少，研究工作也不成熟。

5　結(jié)語

隨著概率數(shù)據(jù)的應(yīng)用日益廣泛，對概率數(shù)據(jù)庫的研究也步步深入。本文大致介紹了概率數(shù)據(jù)庫的概念與應(yīng)用，對概率數(shù)據(jù)庫的表示、查詢、安全三方面內(nèi)容及現(xiàn)階段的研究方法做了較細(xì)致的闡述。

作為近年來新興的研究，概率數(shù)據(jù)庫中的許多問題還沒有得到很好的解決。例如對概率數(shù)據(jù)庫的關(guān)系運(yùn)算的擴(kuò)展還不夠完備、概率數(shù)據(jù)庫的安全問題還沒有得到足夠的重視、目前尚沒有一個完備的形式化的模型來描述概率數(shù)據(jù)庫，等等。這些都有待學(xué)者們更深一步的研究。

[1]Cuzzocrea A.Approximate OLAP Query Processing Over Uncertain and Imprecise Multidimensional Data Streams[C].Database and Expert Systems Applications.Springer Berlin Heidelberg,2013:156～173

[2]Dylla M,Theobald M.Learning Tuple Probabilities in Probabilistic Databases[J]，2014

[3]T.Im ielinskiand W.Lipski.Incomplete Information in Relational Databases.Journal of the ACM,31:761～791,October 1984

[4]D.Barbara,H.Garcia-Molina,D.Porter.The Managementof Probabilistic Data.IEEE Transaction of Knowledge and Data Engineering.4（5）:487～502,1992

[5]Shashi K.Gadia,Sunil S.Nair，Yiu-Cheong Poon.Incomplete Information in Relational Temporal Databases.VLDB,1992

[6]N.Dalvi,C.Re and D.Suciu.Probabilistic Databases:Diamonds in the Dirt.CACM 52（7）:86～94,2009

[7]李文鳳，彭智勇，李德毅.不確定性Top-K查詢處理[J].軟件學(xué)報，2012，23（6）:1542～1560

[8]Hamm J.Preserving Privacy of Continuous High-Dimensional Data with Minimax Filters[J]，2015

[9]Christoph Koch，Dan Olteanu.Conditioning Probabilistic Database.VLDB,2008

[10]Vibhor Rastogi,Dan Suciu，EvanWelbourne.Access Control over Uncertain Data.VLDB,2008

[11]Qin Zhang,Feifei Li，Ke Yi.Finding Frequent Items in Probabilistic Data.SIGMOD,2008

[12]Sathe S,Jeung H,Aberer K.Creating Probabilistic Databases from Imprecise Time-Series Data[C].Data Engineering（ICDE）,2011 !IEEE 27th International Conference on.IEEE,2011:327～338

[13]Chen J,Feng L.Computing Event Probability in Probabilistic Databases[C].Intelligent Computing and Intelligent Systems（ICIS）, !2010 IEEE International Conference on.IEEE,2010,3:249～253

[14]RéC.Managing Large-Scale Probabilistic Databases[D].University ofWashington,2009

[15]金宗安.概率數(shù)據(jù)庫及有效查詢技術(shù)的研究.碩士學(xué)位論文，2009

[16]Dey D，Sarkar S.A Probabilistic RelationalModel and Algebra.ACM Transaction on Database System,22（3）:419～469,1997

[17]R'eC,N.Dalvi，D.Suciu.Efficient Top-k Query Evaluation on Probabilistic Data.ICDE,2007

[18]Ming Hua,Jian Pei,Wenjie Zhang，Xuem in Lin.Ranking Queries on Uncertain Data:A Probabilistic Threshold Approach.SIGMOD，!2008

[19]Dylla M,Miliaraki I,Theobald M.Top-k Query Processing in Probabilistic Databaseswith Non-Materialized Views[C].Data Engineering（ICDE）,2013 IEEE 29th International Conference on.IEEE,2013:122～133

[20]Jian Li,Barna Saha，Amol Deshpande.A Unified Approach to Ranking in Probabilistic Database.VLDB,2009

[21]Vibhor Rastogi,Dan Suciu and Evan Welbourne.Access Control over Uncertain Data.VLDB，2008

王雅瑜（1987-），碩士研究生，助理工程師，研究方向為數(shù)據(jù)庫應(yīng)用、軟件測試

熊婧（1985-），碩士研究生，工程師，研究方向為現(xiàn)代數(shù)據(jù)庫理論與實現(xiàn)、數(shù)據(jù)庫安全

林軍（1976-），碩士研究生，高級工程師，研究方向為移動通信、信息安全及基礎(chǔ)軟件質(zhì)量測評技術(shù)

Probabilistic Database;Probabilistic Database Management;Imprecise Data;Query Computing;Query Sorting

An Overview of Research on Probabilistic Databases

WANG Ya-yu，XIONG Jing，LIN Jun
（Software Quality Engineering Research Center,China Electronic Products Reliability and Environmental Testing Research Institute，Guangzhou 510610）

Probabilistic database management is very important while the need for processing over imprecise data is increasing.A probabilistic databasemanagement system is a databasemanagement system that can store large amountof probabilistic data,provides complex query theory and handles probability calculation.On the basis of PRM model and researches nowadays,probabilistic databasemodel which is composed of object attribute,static attribute,dynam ic attribute,proposes probabilistic attribute,for the need of probabilistic data handing,proposes themethods of query computing and query sorting and their features,and mentions the methods security of probabilistic database.

1007-1423（2015）15-0057-06

10.3969/j.issn.1007-1423.2015.15.015

2015-04-21

2015-05-05