k匿名數(shù)據(jù)上的聚集查詢及其性質＊－

張君寶，劉國華，王碧穎，王 梅，王羽婷，石丹妮，翟紅敏

（東華大學計算機科學與技術學院，上海201620）

1 引言

自Sweeney L提出k－匿名［1，2］以來，k－匿名隱私保護技術在國內(nèi)外引起了廣泛的關注。k－匿名有效預防了公開發(fā)布數(shù)據(jù)中隱私泄漏的問題，對包含隱私信息的數(shù)據(jù)共享做出了重大貢獻。但是到目前為止，很少有人對k－匿名數(shù)據(jù)的知識發(fā)現(xiàn)進行研究，從k－匿名數(shù)據(jù)中獲取有用的知識是目前亟待解決的問題。例如，在給定k－匿名病人信息表中，包含準標識符 Gender、Age、Zip－code、Area和敏感屬性Disease、Expense。若能分別查出［10，20］、［20，30］等10個年齡段患癌癥的人數(shù)，通過分析就可以得出年齡和患癌癥之間的關系，通過統(tǒng)計不同地區(qū)患某種疾病的人數(shù)，可以判斷“地區(qū)病”是否存在。k－匿名數(shù)據(jù)中大量地存在類似信息，對k－匿名數(shù)據(jù)的知識發(fā)現(xiàn)研究有重要的意義。

現(xiàn)有的不確定數(shù)據(jù) OLAP［3～6］主要使用可能世界概率模型［7］對不確定數(shù)據(jù)聚集查詢進行研究，時間效率很低。因為k－匿名數(shù)據(jù)的泛化程度很高，可能世界也要大得多，求解擴展數(shù)據(jù)庫時間消耗限制了將不確定數(shù)據(jù)的聚集查詢方法應用到k－匿名數(shù)據(jù)上的可能性。不確定數(shù)據(jù)OLAP最早由Burdick D等人于2005年在文獻［3］中提出，在2007年，他們在文獻［4］中對文獻［3］的方法進行了補充；在同一年，文獻［6］對元組間有約束的不確定數(shù)據(jù)OLAP進行了研究，基于元組間約束，構造約束超圖，提出了新的擴展數(shù)據(jù)庫分配策略。文獻［5］給出了計算擴展數(shù)據(jù)庫更加有效的分配策略。針對不確定數(shù)據(jù)的OLAP查詢，研究者的技術路線是將不確定數(shù)據(jù)庫展開成可能世界，然后為可能世界中的元組進行概率分配，將已經(jīng)分配的可能世界合并得到擴展數(shù)據(jù)庫，在擴展數(shù)據(jù)庫上執(zhí)行OLAP查詢。其中概率分配算法是指數(shù)級時間復雜度，雖然文獻［6］對算法進行了優(yōu)化，但仍然是指數(shù)級的時間復雜度，查詢的時間效率低。

文獻［8～13］對不確定數(shù)據(jù)的聚集查詢進行了研究，但仍是基于不確定數(shù)據(jù)概率模型，沒有避免指數(shù)級的不確定可能世界展開。Jayram T S在文獻［8］中將不確定數(shù)據(jù)轉換為概率數(shù)據(jù)流，在此基礎上研究了聚集查詢的IO效率，給出了聚集查詢的算法，并討論了算法的時間效率和空間效率。Cormode G等人在文獻［9］中給出了具有基數(shù)限制的不確定數(shù)據(jù)的關系操作實現(xiàn)算法，在此基礎上給出聚集查詢的實現(xiàn)，并對查詢結果提供了兩種處理方法，一種是求期望，另一種是求最大、最小值。Roy A在文獻［10］中將不確定數(shù)據(jù)之間的相關性用層次超圖來表示，基于層次超圖給出了擴展數(shù)據(jù)庫指數(shù)時間獲取算法，并給出了聚集查詢的實現(xiàn)。文獻［13］給出了基于過濾策略的分布式聚集查詢算法，將最不可能成為查詢結果的數(shù)據(jù)刪除，雖然該算法減少了分布式節(jié)點上的數(shù)據(jù)傳輸，但會導致信息損失。

文獻［14～18］對隱私保護進行研究，但是沒有人對k－匿名數(shù)據(jù)聚集查詢進行研究。雖然文獻［15］給出基于置換的匿名數(shù)據(jù)聚集查詢方法，但該方法有很大的局限性，不能應用到k－匿名數(shù)據(jù)上。

總結上面的文獻我們可以發(fā)現(xiàn)目前還沒有有效的解決k－匿名數(shù)據(jù)知識發(fā)現(xiàn)的方法。為了解決k－匿名數(shù)據(jù)的知識發(fā)現(xiàn)問題，本文將研究重點放到k－匿名數(shù)據(jù)的聚集查詢，并做出了以下貢獻：

（1）給出k－匿名關系模式的定義：關系數(shù)據(jù)庫在數(shù)據(jù)庫領域占據(jù)著重要的位置，而關系模式是關系查詢的基礎。結合確定數(shù)據(jù)關系模式的定義，給出了k－匿名關系模式的定義。這對k－匿名數(shù)據(jù)使用關系數(shù)據(jù)庫技術具有重要的意義。

（2）給出求解滿足查詢約束的值、概率序偶集合的算法，并將該集合作為第二階段的輸入：通過k－匿名數(shù)據(jù)不確定屬性值的等概率特性，證明了k－匿名元組的可能世界實例的概率與其他元組無關。通過求解查詢約束的析取范式，給出相對于析取范式中合取子式的獨立屬性集的概念。結合獨立屬性集，給出求解滿足查詢約束的值、概率序偶集合的算法。

（3）給出WITH子句約束定義及語義：針對不確定數(shù)據(jù)庫，用戶可能會提出不同的查詢要求，例如查詢年齡一定在［20，40］之間患癌癥的人數(shù)，則年齡屬性值為［30，50］的不確定元組不在查詢結果中。為了滿足用戶這類需求，給出WITH子句約束的定義及其語義，并給出不同WITH子句約束對應查詢重要性的概念。

（4）給出k－匿名聚集查詢的性質：查詢的性質對查詢優(yōu)化、用戶選擇合適的查詢等具有重要意義。結合k－匿名聚集查詢，給出不同 WITH子句約束聚集查詢的單調(diào)性和一致性。

2 k－匿名模型

關系模式是關系數(shù)據(jù)庫的基礎，關系模式是對關系的準確描述。通過給出k－匿名的關系模式，為k－匿名數(shù)據(jù)應用可兼容的關系數(shù)據(jù)庫理論打下基礎。在給出k－匿名關系模式定義之前，先回顧一下確定數(shù)據(jù)關系模式中的經(jīng)典定義。

（1）關系模式。

定義1 （基礎域）基礎域是一個無限常量的集合DOM。所有屬性的屬性值均屬于DOM。

定義2 （關系模式）關系模式［19］R由以下兩部分組成：

①有限字符串的集合U，稱為屬性集，用R［U］表示。R［U］中元素的個數(shù)稱為元數(shù)，用arity（R）表示，即arity（R）＝｜R［U］｜。存在一個從R［U］到DOM的映射函數(shù)f，得到對應屬性的屬性域。

②R［U］上斷言的集合Σ，Σ中的元素稱為完整性約束。所有的關系實例都必須滿足Σ。

（2）k－匿名關系模式。

k－匿名數(shù)據(jù)是滿足k－匿名約束的特殊不確定數(shù)據(jù)，參考定義2并結合k－匿名的性質給出k－匿名關系模式相關定義。

定義3 （泛化域）基礎域DOM 的冪集P（DOM）構成一個無限對象的集合GDOM，稱為泛化域。GDOM中的元素稱為泛化值。

泛化域是基礎域的冪集，即泛化域中同時包含精確值和泛化值。例如，表1中Zip－code屬性既包含泛化值“9021＊”，也包含精確值“07620”和“33109”。

Table 1 2－anonymous table（DISEASE）表1 2－匿名表（DISEASE）

定義4 （k－匿名約束）給定R的任意實例I，I在準標識符［1］QI上的投影πQI（I），得到一個多重集MS。以MS中元素“相等”為一個等價關系，可將 MS劃分為I1，I2，…，In共n 個等價類，其中，｜Ij｜≥k，1≤j≤n。

定義5 （k－匿名關系模式）k－匿名關系模式R是一個六元組R（U，GDOM，f′，QI，SA，Σ′），其中，

①U是一個有窮字符串集合，稱為屬性集。

②GDOM為泛化域。

③f′是一個從U到GDOM 的映射函數(shù)，稱為域映射函數(shù)，值域對應各屬性的屬性域。

④QI為U的子集，稱為準標識符。

⑤SA為U的子集，稱為敏感屬性集。QI∩SA＝?。

⑥Σ′是包含傳統(tǒng)的完整性約束以及k－匿名約束的集合。

3 聚集查詢

傳統(tǒng)的關系數(shù)據(jù)庫聚集查詢將常量數(shù)值集合作為輸入，通過聚集計算得到一個單一值作為輸出。常用的聚集函數(shù)有SUM、COUNT、AVERAGE、MIN、MAX等。k－匿名數(shù)據(jù)的屬性值為泛化值，泛化值中的每一個可能取值對應一個概率，不能簡單地將滿足查詢條件的泛化值直接作為聚集函數(shù)的輸入。一方面，k－匿名數(shù)據(jù)泛化值中只有一個是“正確”的；另一方面，泛化值的每一個可能取值均有可能是“正確的”，將滿足查詢約束的可能取值的期望作為返回值在一定程度上反映了真實查詢結果。下面給出k－匿名聚集查詢定義及其語義：

定義6 （聚集查詢）給定k－匿名表T，T上的聚集查詢形式化定義為AGGexp（δQC（T）），其中AGG為聚集函數(shù)名，exp為常量、屬性或屬性表達式。QC為查詢條件，稱為查詢約束，δQC選擇滿足查詢約束的元組實例。

QC是一個析取范式，若不滿足，則使用現(xiàn)有的算法得到對應的析取范式。元組中的可能世界實例只要滿足析取范式中任意合取子式，則這個實例在查詢結果中，在后面只討論QC為合取表達式的情況。雖然求解析取范式會花費一些時間，后面利用析取范式進行優(yōu)化，彌補求解析取范式的時間消耗。

給定一個查詢Q，滿足Q中QC的所有元組構成一個區(qū)域，稱為查詢區(qū)域，表示為Region（Q），并且Regionatt（Q）?DOM。att為任意屬性，Regionatt（Q）為Region（Q）在att上的投影。元組t的所有可能世界的集合構成一個區(qū)域，稱為元組區(qū)域，表示為Region（t）。例如：元組〈［1，2］，3〉的元組區(qū)域為｛〈1，3〉，〈2，3〉｝。Region（t）在屬性集 A上的投影稱為A 屬性區(qū)域，表示為RegionA（t），Region（Q）在A上的投影RegionA（Q）稱為A屬性查詢區(qū)域。

在k－匿名表T上的聚集查詢將滿足QC的所有元組實例對應exp中屬性值和對應的概率作為聚集函數(shù)的輸入，然后通過線性運算得到查詢結果。為了方便敘述，將查詢過程分為兩個階段：（1）獲得滿足查詢約束的元組實例對應exp中屬性的屬性值及其概率的集合。（2）在階段（1）的結果集上進行線性計算得到最終查詢結果。

3.1 聚集查詢的第一階段

性質1 （k－匿名數(shù)據(jù)元組實例概率分配的元組無關性）在k－匿名數(shù)據(jù)元組進行可能世界概率展開時，元組可能世界實例的概率與其他元組無關。

證明 k－匿名數(shù)據(jù)中不確定屬性值的所有可能取值的概率相等，并且屬性之間獨立，元組之間獨立。表2是一個任意的k－匿名表。根據(jù)k－匿名的不確定可能取值的等概率特性，元組1中的任意可能世界實例的概率為1／（｜Val11｜＊｜Val12｜＊…＊｜Val1m｜）＝Pr1，可能世界實例的個數(shù)為｜Val11｜＊｜Val12｜＊…＊｜Val1m｜＝Num1，Pr1＊Num1＝1。同樣得到其它元組的可能世界實例的概率和個數(shù)分別為Pr2，Num2，…，Prn，Numn。將表2進行可能世界展開，則表2的所有可能世界中，任意可能世界實例的概率為Pr1＊Pr2＊…＊Prn，所有可能世界實例的個數(shù)為Num1＊Num2＊…＊Numn。元組1中的任意可能世界實例在表2的所有可能世界實例中的個數(shù)為Num2＊…＊Numn，所以元組1的一個可能世界實例的概率為：（Pr1＊Pr2＊…＊Prn）＊（Num2＊…＊Numn）＝Pr1，即元組1的可能世界實例概率只與元組1有關。同理可證其他元組可能世界實例的概率也只與元組本身有關。 □

Table 2 Arbitrarily k－anonymous table表2 任意k－匿名表

例：給定表3的1－匿名表，對應展開的可能世界為｛〈1，3〉，〈3，3〉｝，｛〈1，3〉，〈3，4〉｝，｛〈1，3〉，〈3，5〉｝，｛〈2，3〉，〈3，3〉｝，｛〈2，3〉，〈3，4〉｝，｛〈2，3〉，〈3，5〉｝，表3的可能世界實例概率為（1／2＊1）＊（1＊1／3）＝1／6，進行可能世界合并后〈1，3〉的概率為1／6＊3＝1／2，與直接在元組1中進行分配的概率一致。

Table 3 1－anonymous table表3 1－匿名表

根據(jù)性質1，得到k－匿名數(shù)據(jù)中任意元組t的x）。通過該公式，在求解聚集查詢的第一階段，只需枚舉元組獨立屬性集的可能世界。不在QC和exp中出現(xiàn)的獨立屬性集ATTy對應的QC（ATTy）＝ ?，ATTy所有取值序列均在S 中，RegionATTy（t）滿足QC（ATTy）的概率為1，只枚可能世界實例的概率為：1／｜Region（t）｜。遍歷所有元組的全部可能世界實例，將滿足QC的可能世界實例在exp中對應的屬性上投影并結合該可能世界實例的概率得到聚集查詢第一階段的結果。遍歷次數(shù)為｜Region（t1）｜＋｜Region（t2）｜＋…＋｜Region（tn）｜。k－匿名數(shù)據(jù)元組的可能世界較不確定數(shù)據(jù)要大得多，并且k－匿名數(shù)據(jù)存在大量的泛化數(shù)據(jù)。若將k－匿名數(shù)據(jù)的擴展數(shù)據(jù)庫物化，需要的存儲空間是｜Region（t1）｜＋｜Region（t2）｜＋…＋｜Region（tn）｜。否則，每次查詢都枚舉元組的可能世界實例，元組可能世界是相對于不確定屬性個數(shù)的指數(shù)級。

給定k－匿名表T 和T 上的聚集查詢AGGexp（δQC（T）），t為T 中的任意一條元組，Region（t）中滿足QC的所有實例集合為S。若QC中的二元表達式包含兩個屬性A和B，則在S中A、B屬性取值相關，用A relate B表示。將屬性按relate求閉包，可以得到屬性集U 的一個劃分ATT1，…，ATTm，QC對應ATTi的約束為QC（ATTi），i∈［1，m］（若沒有給出析取范式不存在對應關系）。t在ATTi上滿足QC（ATTi）的可能取值序列集合為SATTi，則SATT1×…×SATTm一定在S中。即相對于S，ATTi和ATTj相互獨立，i，j∈［1，m］，i≠j，ATTi為獨立屬性集。兩個獨立屬性集的并仍然是一個獨立屬性集，當存在一個k－匿名關系實例，使獨立屬性集不能拆分為兩個獨立屬性集時，稱該獨立屬性集為最小獨立屬性集。relate閉包得到的獨立屬性集的屬性之間相關，不相關的屬性不會加入到閉包中，因此relate閉包得到的獨立屬性集為最小獨立屬性集。使用一般閉包算法就可得到相對于QC的最小獨立屬性集集合。

給定QC，得到滿足QC的元組可能世界實例集合S的獨立屬性集為ATT1，…，ATTm。假設ATTx中包含exp 中的屬性，RegionATTi（t）滿足QC（ATTi）的個數(shù)為 Ni，i≠x，i∈［1，m］，那么RegionATTi（t）滿 足 QC（ATTi）的 概 率 為 Ni／｜RegionATTi（t）｜，S在ATTx上的投影得到一個值序列的集合，集合中元素的概率為1／舉在QC和exp中出現(xiàn)的獨立屬性集。

例：給定表T 中一條元組t為〈｛1，2，3｝，｛2，3，4｝，｛5｝〉，聚集查詢?yōu)镾UM2：（δ1：＞1and2：＞2（T）），對應QC1：＞1and 2：＞2的獨立屬性集集合為｛｛1：｝，｛2：｝｛3：｝｝。對應獨立屬性集｛1：｝滿足QC（｛1：｝）的可能取值序列數(shù)目為2，｛2：｝中包含exp中屬性，｛3：｝滿足QC（｛3：｝）可能取值個數(shù)為1，所以對應｛2：｝中可能取值2、3、4的概率均為（1／3）＊（2＊1／3）＊（1＊1／1）＝2／9，與元組滿足QC 可能世界實例在｛2：｝上的投影一致。其中｛2：｝滿足QC（｛2：｝）的值序列為3和4，即將｛〈3，2／9〉，〈4，2／9〉｝作為第一階段的結果。給定一條元組tuple、QC和exp，求元組滿足QC的可能世界實例在exp中屬性上投影及概率集合的算法，即求解聚集查詢第一階段結果的算法見算法1。

算法1 求解聚集查詢第一階段結果的算法

輸入：k－匿名元組tuple、QC和exp；

輸出：元組滿足QC在包含exp的屬性序列上的投影及對應的概率的集合。

Begin：

1.TmpPr＝1，Count＝0，resultSet＝?；

使用閉包算法，得到QC對應獨立屬性集的集合IS。

2.將IS中不包含QC和exp中屬性的獨立屬性集刪除，得到獨立屬性集集合IS′，IS′中元素個數(shù)為n，包含exp屬性的獨立屬性集下標為x。

3.For：IS′中的每一個元素Ei，i≠x

Count＝0；

For：tuple在Ei上的每一個可能取值序列

If t滿足QC（Ei）then

Count＋＋；

End if；

End for；

TmpPr＝TmpPr＊（Count／｜RegionEi（t）｜）；

4.End for；

5.For：tuple在Ex中每一個可能取值t

If t滿足QC（Ex）then

將t在exp中屬性上投影，其值為val，將〈val，TmpPr＊1／｜RegionEx（t）｜〉加入到resulSet中

（val值有重復）。

End if；

6.End for；

7.Return resultSet；

End

在聚集查詢的第一階段，用戶可能會要求元組獨立屬性集中的每一個可能取值序列都必須滿足QC中對應部分，或者屬性值序列必須為精確值。例如，一個實力不足的投資公司對一個k-匿名個人信用信息表統(tǒng)計信用狀況一定為“優(yōu)秀”的人的特征，對滿足統(tǒng)計特征的對象進行投資以減小投資風險。為了滿足用戶的這種需求，增加用戶的查詢能力，對k－匿名聚集查詢增加WITH子句約束，該約束限制了屬性查詢區(qū)域與屬性區(qū)域之間的關系。（詳見第4節(jié)）

3.2 聚集查詢的第二階段

在第一階段結束后，得到結果如表4所示。將表4的VAL代入exp中得到對應的值exp（VAL），exp 替換規(guī)則如下：（1）當 AGG 函數(shù)為SUM 或AVERAGE時，將exp中的屬性名替換為對應的確定值。（2）當AGG為COUNT 時將exp替換成1或計算時默認為1但不進行替換，結果如表5所示。

Table 4 Results table of aggregate query′s first stage表4 聚集查詢第一階段結果表

Table 5 Input table of aggregate function表5 聚集函數(shù)的輸入表

將表5作為聚集函數(shù)的輸入。給定聚集查詢的輸入，聚集函數(shù)的計算公式如下所示：

對于聚集函數(shù)MAX（MIN），可能出現(xiàn)滿足查詢條件的查詢結果值是最大（?。┑?，但是對應的概率非常小，即該結果值出現(xiàn)的可能性很小，是否將該值作為查詢結果返回給用戶？這類問題是多因素最值選取問題。如何選取這類最值問題是Topk中研究的內(nèi)容，在這里不進行討論。

4 WITH子句約束

定義7 （WITH子句約束）給定查詢約束QC，WITH子句約束原子 WCCA是一個謂詞PWCCA（1，ATT），PWCCA（1，ATT）＝true。參數(shù)1的可選項為“CONTAIN”、“OVERLAP”、“NONE”；ATT相對于QC為獨立屬性集。WITH子句約束WCC是約束原子的謂詞 PWCC（WCCA1θWCCA2θ…θWCCAn），θ∈｛∨，∧｝，PWCC＝true。

為方便描述，后面WCC默認只討論包含一個WCCA的情況。其它情況類似。

圖1中虛線矩形表示屬性查詢區(qū)域，實線矩形表示屬性區(qū)域，顯然無論什么情況第三類都不會在查詢結果中，相同屬性集上的不同OP約束互斥。結合圖1，不同WCCA的語義定義如下：

PWCCA（NONE，ATT）：iff ATT 屬性查詢區(qū)域和ATT 屬性區(qū)域對應的關系為類1，并且｜RegionATT（t）｜＝1，PWCCA為 true。PWCCA（CONTAIN，ATT）：iff ATT 屬性查詢區(qū)域和ATT 屬性區(qū)域的關系為類1，PWCCA為true。PWCCA（OVERLAP，ATT）：iff ATT 屬性查詢區(qū)域和ATT屬性區(qū)域的關系為類1或類2，PWCCA為true。

例：對表 1 查詢 COUNT1（δAge≥40andAge≤50andDisease＝‘Cancer′（DISEASE））。若 用戶給出WCC 為PWCCA（CONTAIN，Age），只有第3條元組WCC為true；若WCC為PWCCA（OVERLAP，Age），第3條和第5條的WCC 為true；若WCC 為PWCCA（NONE，Age），則沒有元組使得WCC為true。

Figure 1 Relationship between query region and attribute region圖1 屬性查詢區(qū)域與屬性區(qū)域之間的關系

下面討論WCCA滿足的性質，通過該性質可以將WCCA中的獨立屬性集的并分解為最小獨立屬性集。

性質2 （WCCA一致性）給定一個WCCA為PWCCA（OP，AB），A、B 為屬性集合。若A、B 相對于QC為獨立屬性集，則PWCCA（OP，AB）＝PWCCA（OP，A）∧PWCCA（OP，B）。即相對于QC，AB 的OP約束與A的OP約束和B的OP約束的合取保持一致。

證明 OP 選項可能為 “NONE”、“CONTAIN”、“OVERLAP”。當OP 為 NONE時，因為A和B獨立，所以AB值序列在A和B上的投影也一定滿足A 和B 的NONE選項；相反，A和B分別滿足NONE選項，則笛卡爾積也一定滿足NONE選項。同理可證其它OP也滿足，證畢。

□

利用性質2，將ATT分解為最小獨立屬性集，在查詢的第一階段求解元組在獨立屬性集上滿足QC對應部分的概率時，同時判斷元組在此獨立屬性集上是否滿足WCCA，若有一個獨立屬性集上的WCCA不滿足，則WCC為假，元組不在查詢結果中。

下面給出檢查一條元組是否滿足WCCA的算法。

算法2 給定查詢約束QC，元組t，WCCA，判斷t是否滿足WCCA

輸入：QC，t，WCCA；

輸出：true，false。

Begin：

for WCCA中ATT的每個最小獨立屬性集A

If WCCA：1＝NONE and｜A｜＞1

return false；

Else if WCCA：1＝CONTAIN and ?x∈Region

（A），QC（A）＝false

return false；

Else if WCCA：1＝OVERLAP and x∈Region

（A），QC（A）＝true

return false；

End if；

End for；

return true；

End

算法的每一次for循環(huán)只有一個if分支真正執(zhí)行，每一個if判斷的句子均可在O（n）時間內(nèi)完成，n＝｜RegionA（t）｜，算法的時間復雜度為O（n）×m，m為ATT中最小獨立屬性集的個數(shù)。

定義8 （WCCA對應查詢Q的重要性）任意給定表T和T上的聚集查詢Q以及WCCA，WCCA的參數(shù)1分別使用選項OP1和OP2，對應滿足QC和WCCA的元組數(shù)為Num1和Num2。若Num1≤ Num2（Num2≤ Num1）恒成立，則稱OP1對應的查詢Q的重要性比OP2弱（強）。

定理1 WCCA 分別使用 NONE、CONTAIN、OVERLAP選項時，對應WCCA的查詢Q重要性逐漸增強。

證明 將定理2分為以下兩部分：

（1）WCCA 分別使用NONE、CONTAIN選項時，對應WCC的查詢Q重要性增強。

（2）WCCA 分別使用 CONTAIN、OVERLAP選項時，對應WCC的查詢Q重要性增強。

證明（1）：由WCCA的不同選項對應的屬性查詢區(qū)域和屬性區(qū)域之間的關系可知，在T中滿足QC和WCCA的元組只可能存在兩種情況：①元組同時滿足兩個WCCA。②元組只滿足使用CONTAIN選項的WCCA。當只存在情況①時，Num1＝Num2；當只存在情況②時，Num1＜Num2；當兩種情況都存在時，Num1＜Num2。根據(jù)定義8可知（1）成立。同理可證（2）成立，定理證畢。 □

5 聚集查詢的性質

聚集查詢的性質對查詢優(yōu)化、用戶選擇合適的查詢等具有重要意義。例如，利用下面的單調(diào)性結合CONTAIN、OVERLAP的特點，我們可以得到真實數(shù)據(jù)統(tǒng)計結果的準確下限和近似上限。利用一致性，對數(shù)據(jù)進行劃分，并發(fā)地執(zhí)行查詢，可以加快查詢的響應速度。

5.1 單調(diào)性

定義9 （單調(diào)性）任意給定k－匿名表T 上的AGG聚集查詢，相對于WCCA兩個不同選項OP1和OP2，查詢結果分別為q1、q2，若q1≥q2（q2≥q1）恒成立，則稱AGG聚集查詢滿足單調(diào)性。

定理2 COUNT聚集查詢滿足單調(diào)性。

證明 假設T中滿足QC和WCCA元組數(shù)分別為 Num1和 Num2，由定理 1，num1≥num2（num2≥num1）恒成立。COUNT查詢結果與滿足QC和WCCA的元組數(shù)成正比，因此q1≥q2（q2≥q1）恒成立。定理證畢。 □

由定理2的證明可知，當SUM聚集查詢exp中屬性域為正數(shù)時滿足單調(diào)性，否則不滿足單調(diào)性。AVERAGE聚集查詢同時涉及到分子和分母，并不滿足單調(diào)性。

5.2 一致性

定義10 （一致性）任意給定k－匿名表T 和AGG 聚集查詢Q；T1，T2，T3，…，Tm是T 的一個劃分，在T，T1，T2，T3，…，Tm上的聚集查詢Q 的結果分別為q，q1，q2，q3，…，qm，若q＝AGG（q1，q2，…，qm），則稱AGG聚集查詢滿足一致性。

定理3 SUM、COUNT聚集查詢滿足一致性。

證明 按照劃分將k－匿名表中滿足QC和WCCA 的所有元組排列為t1，1，t1，2，…，tm，n，則 Q在T 上的聚集查詢結果為：Q（T）＝Q（t1，1，t1，2，…，tm，n）＝Q（t1，1，t1，2，…，t1，…）＋…＋Q（tm，1，…，tm，n）＝Q（T1）＋Q（T2）＋…＋Q（Tk），定理證畢。 □

對于AVERAGE聚集查詢，k－匿名表T 的劃分，滿足QC和WCCA元組數(shù)目不同，為了使AVERAGE聚集查詢滿足一致性，將查詢結果表示為〈Q（Ti），QNum（Ti）〉，QNum（Ti）為滿足 QC 和WCCA 的 COUNT 結 果。AGG′（Q′（T1），Q′Q′（Ti）為〈Q（Ti），QNum（Ti）〉。

定理4 AVERAGE聚集查詢AGG′操作下滿足一致性。

根據(jù)AVERAGE聚集查詢公式，定理4顯然成立。 □

6 實驗

實驗環(huán)境是 Windows7 32bit操作系統(tǒng)，Intel T6600雙核2.2GHz處理器，2GB內(nèi)存，320GB 5 400r／min硬盤。底層數(shù)據(jù)庫為 ORACLE11g?，F(xiàn)有的k－匿名數(shù)據(jù)量小，不能在本實驗中比較不同數(shù)據(jù)量及不同不確定數(shù)據(jù)百分比的時間及準確性。在實驗中使用人工生成的確定數(shù)據(jù)，確定數(shù)據(jù)包含四個屬性，將確定數(shù)據(jù)庫的第二個屬性當作準標識符。因為沒有實現(xiàn)原型系統(tǒng)，為了在關系數(shù)據(jù)庫上表示k－匿名屬性值的不確定性，將屬性值進行連續(xù)泛化，準標識符屬性對應k－匿名表中兩個屬性，分別表示連續(xù)泛化的上限和下限，即確定數(shù)據(jù)對應的k－匿名數(shù)據(jù)有五個屬性。k－匿名數(shù)據(jù)的k值和數(shù)據(jù)泛化的程度成正相關，在這里我們不討論不同k值下的時間及準確性。下面對k－匿名數(shù)據(jù)聚集查詢的時間效率和準確性進行實驗驗證。

6.1 查詢的時間效率

查詢的響應時間是用戶體驗的重要因素之一。現(xiàn)有的不確定數(shù)據(jù)聚集查詢均是基于不確定數(shù)據(jù)庫的可能世界展開，求解擴展數(shù)據(jù)庫，然后在擴展數(shù)據(jù)庫上執(zhí)行查詢。從文獻［3］實驗結果分析中可以看到，當不確定達到25%時獲取擴展數(shù)據(jù)庫的時間最高已經(jīng)達到800秒以上，最少的也有200秒。擴展數(shù)據(jù)庫上查詢時間最高達到140秒以上，最少的也有10秒左右。k－匿名數(shù)據(jù)的不確定元組所占比例遠高于25%，將不確定數(shù)據(jù)聚集查詢的方法應用到k－匿名數(shù)據(jù)上，時間消耗會更高。本文研究的k－匿名數(shù)據(jù)聚集查詢的時間效率遠低于傳統(tǒng)的不確定數(shù)據(jù)聚集查詢方法。下面對查詢的時間效率進行驗證。從實驗結果看，查詢響應時間比較穩(wěn)定，為多項式時間增長，同時查詢的響應時間較不確定數(shù)據(jù)聚集查詢方法效率要快很多，時間效率高。

圖2～圖4的實驗中，WCC為作用在準標識符屬性上的WCCA，數(shù)據(jù)量為50萬條。從圖2中可以看出，隨著不確定數(shù)據(jù)量的增加，NONE選項的響應時間逐漸減小，因為NONE選項在遍歷不確定屬性的第二個可能取值時不滿足WCCA，直接跳到下一個元組執(zhí)行，大大減少了遍歷不確定獨立屬性值的次數(shù)。從圖3和圖4可以看出，隨著不確定元組所占比例的增加，查詢響應時間成多項式時間增長，并且不同的聚集函數(shù)的查詢響應時間相差不大。

Figure 2 Query time of NONE option，500thousands tuples圖2 NONE選項，50萬條數(shù)據(jù)的查詢時間

Figure 3 Query time of CONTAIN option，500thousands tuples圖3 CONTAIN選項，50萬條數(shù)據(jù)的查詢時間

Figure 4 Query time of OVERLAP option，500thousands tuples圖4 OVERLAP選項，50萬條數(shù)據(jù)的查詢時間

圖5 ～圖7的實驗為不同數(shù)據(jù)量的查詢響應時間。從圖中可以看出隨著數(shù)據(jù)量的增加，不同聚集函數(shù)的查詢響應時間近似地成多項式時間增長，響應時間隨著數(shù)據(jù)量的增長比較穩(wěn)定。

Figure 5 Query time of NONE option，80percent uncertainty圖5 NONE選項，80%不確定數(shù)據(jù)的查詢時間

Figure 6 Query time of CONTAIN option，80percent uncertainty圖6 CONTAIN選項，80%不確定數(shù)據(jù)的查詢時間

Figure 7 OVERLAP option，80percent uncertainty圖7 OVERLAP選項，80%不確定數(shù)據(jù)

從圖2～圖7中可以看出，利用k－匿名的不確定數(shù)據(jù)可能取值的等概率特性，給出的多項式時間聚集查詢的算法的時間效率非常高。在實驗中沒有加上求解析取范式以及兩個屬性之間相關的情況，但是在前文中提到當不確定屬性值的個數(shù)有限時，聚集查詢的算法仍為多項式時間的算法，時間同樣滿足多項式倍增長。

6.2 聚集查詢的準確性

k－匿名數(shù)據(jù)中存在大量不確定數(shù)據(jù)。k－匿名數(shù)據(jù)的聚集查詢結果與真實數(shù)據(jù)在大多數(shù)情況下不一致?，F(xiàn)有的k－匿名算法保證了k－匿名數(shù)據(jù)的統(tǒng)計特征，使k－匿名數(shù)據(jù)的聚集查詢在一定程度上反映原始數(shù)據(jù)的趨勢。下面的實驗對k－匿名數(shù)據(jù)聚集查詢的準確性進行驗證。

圖8中查詢?yōu)镹ONE選項，屬性值為不確定的數(shù)據(jù)均不在查詢結果中，所以不確定元組所占的比例越高，查詢結果與真實值相差越多。AVERAGE聚集查詢同時涉及分子和分母，隨著查詢結果中數(shù)據(jù)的減少，分子和分母同時減少，因此AVERAGE聚集查詢結果的準確性沒有隨著不確定元組的增加產(chǎn)生劇烈變化。從前文中可以知道，NONE選項并不是為了返回與真實結果相近的結果，而是為了滿足用戶的特殊需求。

Figure 8 Relative error of NONE option，500thousands tuples圖8 NONE選項，50萬條數(shù)據(jù)的查詢相對誤差

從圖9～圖10可以看出，查詢結果的準確性與不確定元組所占的比例不具有相關性，并且AVERAGE聚集查詢結果的相對誤差比較低。OVERLAP選項的查詢結果較CONTAIN選項查詢結果準確性要高。從整體上看，CONTAIN選項和OVERLAP選項的查詢結果與真實值比較接近，查詢結果的準確性較高。

從實驗的時間效率和準確性兩個方面看，本文的k－匿名數(shù)據(jù)聚集查詢算法是有效的。

Figure 9 Relative error of CONTAIN option，500thousands tuples圖9 CONTAIN選項，50萬條數(shù)據(jù)的查詢相對誤差

Figure 10 Relative error of OVERLAP option，500thousands tuples圖10 OVERLAP選項，50萬條數(shù)據(jù)的查詢相對誤差

7 結束語

本文給出了有效的k－匿名數(shù)據(jù)聚集查詢方法，通過定義WITH子句約束，增加了查詢的表達能力。對k－匿名數(shù)據(jù)的知識發(fā)現(xiàn)研究具有重要意義。

［1］ Samarati P，Sweeney L.Protecting privacy when disclosing information：k－anonymity and its enforcement through generalization and suppression［R］.Technical Report，SRI International，1998.

［2］ Samarati P.Protecting respondents’identities in microdata release［J］.IEEE Transactions on Knowledge and Data Engineering，2001，13（6）：1010－1027.

［3］ Burdick D，Deshpande P M，Jayram T S，et al.OLAP over uncertain and imprecise data［C］∥Proc of the 31st International Conference on Very Large Data Bases，2005：970－981.

［4］ Burdick D，Doan A H，Ramakrishnam R，et al.OLAP over imprecise data with domain constraints［C］∥Proc of the 33rd International Conference on Very Large Data Bases，2007：39－50.

［5］ Burdick D，Deshpande P M，Jayram T S，et al.Efficient allocation algorithms for OLAP over imprecise data［C］∥Proc of the 32nd International Conference on Very Large Data Ba－

ses，2006：391－402.

［6］ Burdick D，AnHai Doan，Ramakrishnan R，et al.OLAP over Imprecise data with domain constraints［C］∥Proc of the 33rd International Conference on Very Large Data Bases，2007：39－50.

［7］ Zhou Ao－ying，Jin Che－qing，Wang Guo－ren，et al.A survey on the management of uncertain data［J］.Chinese Journal of Computers，2009，32（1）：1－16.（in Chinese）

［8］ Jayram T S，Kale S，Vee E.Efficient aggregation algorithms for probabilistic data［C］∥Proc of the 18th Annual ACM－SIAM Symposium on Discrete Algorithms，2007：346－355.

［9］ Cormode G，Srivastava D，Shen E，et al.Aggregate query answering on possibilistic data with cardinality constraints［C］∥Proc of the 28th IEEE International Conference on Data Engineering，2012：258－269.

［10］ Roy A，Sarkar C，Angryk R A.Using taxonomies to perform aggregated querying over imprecise data［C］∥Proc of the 10th IEEE International Conference on Data Mining，2010：989－996.

［11］ Procopiuc C M，Srivastava D.Efficient table anonymization

for aggregate query answering［C］∥Proc of the 25th Inter

national Conference on Data Engineering，2009：1291－1294.［12］ Arbee L，Chen P，Chiu Jui－shang，et al.Evaluating aggregate operations over imprecise data［J］.IEEE Transactions on Knowledge Data Engineering，1996，8（2）：273－284.

［13］ Zhou Xun，Li Jian－zhong，Shi Sheng－fei.Distributed algorithms for aggregation queries over uncertain data［C］∥Proc of the 26th Chinese Conference on Database，2009：126－134.（in Chinese）

［14］ Rebollo－Monedero D，F(xiàn)ornéJ，Pallarès E，et al.A modification of the Lloyd algorithm for k－anonymous quantization［J］.Information Sciences，2012，222：185－202.

［15］ Zhang Qing，Koudas N，Srivastava D，et al.Aggregate query answering on anonymized tables［C］∥Proc of the 23rd International Conference on Data Engineering，2007：116－125.

［16］ Jung E，Ahn S，Hwang S.k－ARQ：k－Anonymous ranking queries［C］∥Proc of the 15th International Conference，Database Systems for Advanced Applications，2010：414－428.

［17］ Martínez S，Sánchez D，Valls A.Towards k－anonymous nonnumerical data via semantic resampling［C］∥Proc of the 14th International Conference on Information Processing and Management of Uncertainty in Knowledge－Based Syst－em，2012：519－528.

［18］ Rebollo－Monedero D，F(xiàn)ornéJ，Soriano M.An algorithm for k－anonymous microaggregation and clustering inspired by the design of distortion－optimized quantizers［J］.Data and Knowledge Engineering，2011，70（10）：892－921.

［19］ CalìA，Calvanese D，De Giacomo G，et al.Data integration under integrity constraints［C］∥Proc of the 14th International Conference，2002：262－279.

附中文參考文獻：

［7］ 周傲英，金澈清，王國仁，等.不確定性數(shù)據(jù)管理技術研究綜述［J］.計算機學報，2009，32（1）：1－16.

［13］ 周遜，李建中，石勝飛.不確定數(shù)據(jù)上聚集查詢的分布式處理算法［C］∥第26屆中國數(shù)據(jù)庫學術會議論文集（A），2009：126－134.