概率數據庫研究問題綜述

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

概率數據庫研究問題綜述

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

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

概率數據庫；概率數據庫管理；不確定數據；查詢計算；查詢排序

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

0　引言

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

1　概率數據庫的基本概念

1.1概率數據庫的概念與應用

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

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

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

1.2概率數據庫的主要研究問題

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

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

1.3一個具體實例

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

表1　概率數據庫學生-班級表a

2　概率數據庫的表示

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

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

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

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

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

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

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

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

3　概率數據庫的查詢

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

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

3.1查詢計算

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

安全查詢是指能夠將全部概率推演放到查詢計劃中處理的查詢；相應的，安全計劃是指能夠使用擴展的概率關系代數處理概率計算，進而處理查詢的計劃。表3所示為與表1對應的學生-成績表。對于一個查詢“SELECT a.Class,Confidence（）FROM a,b WHERE a. Name=b.Name and b.Subject='English'and a.Class=7”，如果執行計劃的關系代數是πClass（σClass='7'（a??πName（σSubject='English'（b）））），則計算的概率結果是1-（1-p2q1）（1-p2q2）；如果執行計劃的關系代數是，則計算的概率結果是p2（1-（1-q1）（1-q2））。在傳統數據庫中，兩種執行計劃的結果應該是等效的，差別只在于是否先對b表做Name上的投影。而如果采用上文提到的c-table表示這樣的查詢，則相應的lineage應當是（X1=2/Y1=1）/（X1=2/Y1=2），因此正確的執行計劃是后一種，即概率結果應當是p2（1-（1-q1）（1-q2））。造成這種差別的原因是表3中的前兩個元組并非相互獨立，而連接操作對這樣的情況無法正確計算?？梢?，對同一查詢語句的不同執行計劃在計算概率上有可能不同。N.Dalvi等在文獻[6]中對這個問題有更詳盡的描述。

表3　概率數據庫學生-成績表b

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

概率數據的查詢中，經過大量復雜計算產生的結果有時并非對所有用戶都很有意義，這樣既耗費資源，又無法讓用戶滿意。因此需要對查詢結果排序、過濾。

3.2查詢排序

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

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

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

4　概率數據庫的安全

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

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

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

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

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

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

5　結語

隨著概率數據的應用日益廣泛，對概率數據庫的研究也步步深入。本文大致介紹了概率數據庫的概念與應用，對概率數據庫的表示、查詢、安全三方面內容及現階段的研究方法做了較細致的闡述。

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

[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].軟件學報，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]金宗安.概率數據庫及有效查詢技術的研究.碩士學位論文，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-），碩士研究生，助理工程師，研究方向為數據庫應用、軟件測試

熊婧（1985-），碩士研究生，工程師，研究方向為現代數據庫理論與實現、數據庫安全

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

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