非完整數據庫Skyline-join查詢*

鮑斌國，秦小麟，李星羅，張 彤

南京航空航天大學 計算機科學與技術學院，南京 211106

1 引言

隨著數據庫的發(fā)展，如何有效精準地從大數據集中獲取有價值的信息作為用戶決策的參考已經成為一個研究熱點。給定一組數據項，Skyline查詢[1]旨在得到不被其他數據支配的數據項集合。其中，一個數據項p支配數據項q，當且僅當p在所有維度上優(yōu)于或等于q，且至少存在一個維度p優(yōu)于q。比如，一個旅客想要在某個區(qū)域尋找一個離沙灘近且價格低的旅館，這種情況下Skyline 查詢只會返回那些不被支配的旅館。在不失一般性的情況下，假設較低的值對于所有維度上的所有用戶都是較優(yōu)的。Skyline查詢的主要目標是為用戶提供有價值的參考，由于其重要性，近些年來已經得到了廣泛的研究[2-4]。這些算法主要是基于完整數據庫的，但這并不能覆蓋所有真實的應用場景。

考慮一個來自電影評分應用的真實數據集Movie-Lens。該數據集中每個數據項中包含多個觀眾對于電影評分的維度。但事實上，一個用戶僅評價那些他看過或了解的電影，因此數據項可能會在多個維度上存在數據缺失的情況。傳統(tǒng)的Skyline查詢無法處理這種數據缺失的數據集，因此Khalefa 等[5]提出了一種非完整數據庫中Skyline 查詢的定義，各個數據項僅在它們都不缺失數據的維度上進行比較。如表1所示，O1和O2只能在第一個維度上進行比較，因此O1支配O2。之后的許多非完整數據庫研究[6-9]是基于該工作的。

但是傳統(tǒng)的非完整數據庫Skyline查詢明顯有以下兩個缺點：（1）支配傳遞性的丟失。這不僅大大增加計算量，因為不得不對所有數據進行兩兩比較，而且會使Skyline查詢結果過少甚至是空集。（2）一些非正常的數據項出現在結果集中。比如僅有極少維度數據完整的數據項，它們難以為用戶提供有效的選擇。這些缺點都會嚴重誤導用戶的選擇。

對于傳統(tǒng)非完整數據Skyline查詢的缺點，Zhang等[10]提出了非完整數據庫概率Skyline。他將數據項之間的支配關系用概率值表示，最后的Skyline 結果集取最不可能被支配的前K個數據項。但是傳統(tǒng)Skyline查詢大多假設數據項所有屬性均存儲在單個關系中，然而實際應用場景經常會涉及到多表連接操作。若盲目地先對所有關系進行連接操作，那么可能會產生海量的數據項，從而導致Skyline 查詢效率低下的問題。

因此提出了PSkyline-join算法，該算法主要有四個步驟：對于單個關系中的數據項進行多層次分組；確定每組的局部Skyline 結果集；采用剪枝策略連接局部Skyline結果集；確定全局Skyline集合。本文的主要貢獻如下：

（1）對概率Skyline 的定義進行補充使其適用于多表連接Skyline查詢。

（2）提出了PSkyline-join 算法，通過多層次分組高效計算局部Skyline候選集。

（3）利用局部Skyline 概率上界與全局Skyline 概率下界剪枝策略去除了無用的Skyline 概率計算，大幅提升了算法效率。

本文的組織結構如下：第2章介紹了非完整數據庫Skyline 查詢的相關工作；第3 章給出了非完整數據庫及概率Skyline 的基礎定義；第4 章詳細介紹了Skyline-join 的算法流程，包括多層次分組及兩種剪枝策略；第5 章通過實驗評估了該算法性能；第6 章總結全文。

2 相關工作

關于非完整數據庫中的Skyline 查詢最早由Khalefa 等[5]提出，文獻給出了一種非完整數據庫中Skyline 查詢的定義，即兩個數據項僅在它們都不缺失數據的維度上進行比較來得出支配關系。同時也提出了Bucket 和ISkyline 算法以計算非完整數據庫中的Skyline查詢結果集。

Bucket算法基于數據項的位圖，即數據在某個維度上未缺失數據記為1，若缺失數據則記為0，將所有數據項根據位圖進行桶劃分；然后確定每個桶的局部Skyline 候選集；最后根據所有桶的局部候選集得到全局Skyline 結果集。ISkyline 在Bucket 算法的基礎上添加了更多剪枝策略，從而優(yōu)化了原算法效率。后來幾乎所有的非完整數據Skyline查詢研究都基于該工作。Bharuka 等[6]提出了一種基于排序的Bucket 算法（sorted bucket algorithm，SOBA），該算法在桶層次及點層次對數據項進行排序，從而減少了桶之間的數據項比較。

但是基于傳統(tǒng)非完整數據庫Skyline的算法面臨著循環(huán)支配的問題，丟失了完整數據庫下的支配傳遞性。對于表1 的數據集，O1支配O2，O2支配O3，按照在完整數據庫下的傳遞性O1支配O3，但此處O3支配O1，因此這三個數據項形成了循環(huán)支配。這會導致Skyline查詢結果過少甚至是空集。對于上述定義存在的缺陷，Zhang等[10]提出了非完整數據庫概率Skyline的概念。概率Skyline將數據項之間的支配關系用概率值表示，最后的Skyline 結果集取最不可能被支配的前K位數據項。同時提出了PISkyline 算法，采用兩種剪枝策略和排序技術來加速Skyline 概率的計算。但該研究僅局限在單關系，還不能很好地支持多關系Skyline 查詢，因此本文擴展了概率Skyline使其適用于多關系Skyline查詢。

近些年來Skyline-join方面的主要研究有：Jin等[11]提出了一種基于排序的多關系Skyline 查詢算法，但該算法是非平凡的，需要多次遍歷每個關系才能得出正確的Skyline 結果集。Sun 等[12]提出了一種基于SaLSa[13]的分布式環(huán)境下Skyline-join查詢算法，但該算法并不支持提前終止并依賴于每個關系的多個索引。而后Vlachou 等[14]提出了提前終止條件概念，該條件用于確定算法是否已經遍歷了足夠多的數據項用來生成完整的Skyline 結果集。Awasthi 等[15]提出了KSJQ（K-dominant Skyline join queries）算法以解決多關系完整庫中的K支配Skyline查詢問題。針對多數據流的Skyline 查詢問題，Zhang 等[16]提出了NPSWJ（naive parallel sliding window join）和IP-SWJ（incremental parallel sliding window join）算法。但是這些工作均未涉及非完整數據庫。Alwan 等[17]提出了一種非完整數據庫下的Skyline-join 算法JincoSkyline算法，但該算法是基于傳統(tǒng)的非完整數據庫Skyline，返回的Skyline 結果集不符合用戶需求，本文基于概率Skyline 的PSkyline-join 算法能夠返回具有高參考價值的Skyline查詢結果。

3 問題定義

本章主要介紹非完整數據庫和Skyline查詢的相關定義與概念。

定義1（單關系概率支配[10]）對于兩個擁有d維屬性的數據項p和q∈D，q支配p的概率定義為：

其中，E(p)表示與p完全相等的數據項集合。

為了便于分析，該定義做了如下假設：

（1）所有的數據項之間都是獨立的；

（2）數據項各個維度的屬性都是獨立的；

（3）缺失值是隨機出現在各個維度上的。

有了以上假設，當p(i)和q(i)都是缺失值時：

定義1僅考慮了單個關系情形下的概率支配，但當Skyline 查詢涉及到多關系時，定義1 假設所有的數據項之間都是獨立的，該條件明顯不成立，因為連接操作后兩個數據項中的部分維度有可能來自同一個關系的同一數據項。因此定義2 對定義1 進行了拓展，使其可以應用于多關系Skyline查詢。

定義2（多關系概率支配）對于由多個關系連接而來的數據項p和q，q支配p的定義為：

其中，βi表示數據項中來自關系Ri的屬性:

由定義2可知，當p和q的部分屬性來自同一關系的同一數據項時，這部分屬性將不會對支配概率產生任何影響。

定義3（非完整數據下概率Skyline查詢）對于一個非完整數據集S，用戶指定一個參數K(K>0),概率Skyline查詢結果集表示為：

其中：

直觀上來看，概率Skyline 查詢的結果就是Skyline概率排名前K位的數據項，即最不可能被支配的前K個數據項。

考慮表2 中的數據集，用戶設置K=2。首先計算每一維度上的概率分布函數

Table 2 Incomplete data set S2表2 非完整數據集S2

4 PSkyline-join算法

如圖1 所示PSkyline-join 算法主要有四個步驟：數據項多層次分組；確定局部Skyline概率；連接數據項；確定全局Skyline結果集。

Fig.1 Steps of PSkyline-join algorithm圖1 PSkyline-join算法步驟

4.1 數據項分組

第一層分組：對于某個關系將連接鍵值相同的數據項劃分到一組中。第二層分組：在進行上述第一層分組后，再根據數據項的缺失位圖對數據項進行二次劃分，即桶劃分[5]。

考慮例子：對于表3 中的關系R1假設連接鍵為id，首先將id 值相同的屬性項劃分到同一組中，表4展示了上述劃分結果。然后對于每一組中的數據項根據缺失位圖進行桶劃分，劃分結果如表5所示。

數據項多層次分組主要是為了輔助計算局部Skyline概率上界。

4.2 計算局部Skyline概率上界

對于每個桶中的數據項，僅比較兩個數據項都未缺失數據項的維度，從而得到它們之間的支配關系。按照上述支配定義，兩兩比較桶中的數據項求得每個桶的局部Skyline候選集。表5灰色背景填充的數據項即為局部Skyline候選集。

Table 3 R1data set表3 R1數據集示例

Table 4 R1group dividing表4 R1組劃分

Table 5 R1bucket dividing表5 R1桶劃分

定理1?τ1p∈bucket，若?τ1q∈bucket且τ1q?τ1p，則?p≡τ1p?τ2p，其Skyline概率上界為，記為：

其中，w表示該桶缺失的維度數量。

證明S={τ|τ≡τ1?τ2,τ1∈R1,τ2∈R2},?p∈S，不妨假設p≡τ1p?τ2p，若?τ1q?τ1p，則?q≡τ1q?τ2p在各個非缺失維度上支配p,由此：

定理1 主要闡明了桶內數據項在與其他數據項連接后所能達到的Skyline概率上限值。同時由定理1可知局部Skyline候選集的概率上界為1。

根據定理1可以設計高效的局部Skyline 概率上界更新算法。算法1 的第1 行對數據項的局部Skyline 概率上界進行了初始化。初始化時假設各個數據項不會被其他數據項支配，因此對各個數據項的局部Skyline概率上界賦值為1。算法第2行至第4行根據連接鍵值對數據項進行組劃分，再根據數據項的位圖進行桶劃分。為了提高分組效率，可以將數據項的連接鍵值及缺失位圖作為數據項的分組鍵，再將所有具有相同鍵的數據項映射到同一集合中?？紤]到映射操作的時間復雜度為O(1)，可知采用這種分組算法的時間復雜度為O(n)，其中n為數據項總數。對于每一個桶中的數據項，將它與桶中的其他數據項進行比較，若桶內沒有數據項在非缺失維度上支配該數據項，則將其加入局部Skyline 候選集。由于要兩兩比較數據項，因此計算局部Skyline 候選集的算法時間復雜度為O(dm2)，其中d為數據項維數，m為桶內數據項的數量。算法第8 行，若數據項不為局部Skyline 點，則根據定理1 更新其局部Skyline概率上界。

算法1局部Skyline概率上界算法LocalSkyline-UpBound

輸入：非完整數據集S。

輸出：各個數據項的局部Skyline概率上界。

4.3 連接數據項

在連接數據項時，除了正常的連接操作外，還需要計算數據項的全局Skyline概率上界。

定理2?p∈R1?R2,p≡τ1p?τ2p，其中τ1p∈R1,τ2p∈R2，p的概率上界為：

Psup(p)=Psup(τ1p)×Psup(τ2p)

證明若Psup(τ1p)與Psup(τ2p)均為1，則上式明顯成立。若Psup(τ1p)<1 或Psup(τ2p)<1，不失一般性假設Psup(τ1p)<1，Psup(τ2p)=1，由定理1 可知τ1p在與其他數據項連接后的Skyline 概率上限值為Psup(τ1p)，故P(p)≤Psup(τ1p)，Psup(p)=Psup(τ1p)上式成立。若Psup(τ1p)<1且Psup(τ2p)<1，由定理1證明過程可知?m≡τ1q?τ2p及n≡τ1p?τ2q在非缺失維度上支配p,由此得:

定理2 主要闡明了局部Skyline概率上界與全局Skyline 概率上界的關系，從而可以高效地計算數據項的全局Skyline 概率上界，故可以建立高效的剪枝策略。

4.4 計算全局概率Skyline集合

在連接各個關系的數據項后，需要為用戶返回全局的Skyline 集合。為了去除不必要的Skyline 概率計算，采用了兩種剪枝策略。

剪枝策略1若數據項p在與數據項q比較后，其Skyline概率已經小于全局的Skyline概率下界，則可以中斷計算p的Skyline概率。

算法2Skyline概率算法SkylinePro

輸入：非完整數據集Q，數據項p,globalLowBound。

輸出：數據項Skyline概率。

剪枝策略2若數據項p的全局Skyline概率上界小于全局Skyline 概率下界，則無需計算數據項p的Skyline概率。

算法3PSkyline-join算法PSkyline-join

輸入：非完整數據集{R1,R2,…,Rn},Skyline 結果集大小K。

輸出：Skyline結果集。

算法3 的第1 行對全局Skyline 概率下界和全局Skyline 結果集進行初始化，由于開始時全局Skyline結果集為空，因此對Skyline概率下界賦值0。算法第2 到3 行對各個數據集的局部Skyline 概率上界進行計算。第4 行將各個數據集進行連接，并根據定理2計算每個數據項的全局Skyline概率上界。第5行根據數據項的全局Skyline 概率上界對數據項進行分類，Q1中的數據項Skyline 概率上界均為1，Q2中的數據項Skyline 概率上界小于1。第6 到8 行對Q1中的數據項進行Skyline概率計算，并更新Skyline結果集和全局Skyline 概率下界。全局Skyline 概率下界更新為Skyline 結果集數據項中最小的Skyline 概率。第9到13行結合剪枝策略2對Q2中的數據項進行Skyline 概率計算。將連接后的數據分類為Q1和Q2的出發(fā)點：由于Q1中數據項的Skyline概率上界都為1，因此這部分數據項最有可能進入全局Skyline結果集，并且能夠大幅提升全局Skyline概率下界，使得在兩種剪枝策略能夠發(fā)揮更大的作用。盡管存在兩種剪枝策略，但最壞情況下所有數據項依然需要進行兩兩比較，因此算法3的時間復雜度為O(dn2)，其中d為數據項連接后的維數，n為數據項連接后的數量。

5 實驗及分析

所有的對比算法都使用Python 實現，運行環(huán)境為Ubuntu16.04,Intel Core i5-7500 3.4 GHz 處理器，8 GB內存。

由于目前沒有符合實驗需求的公開數據集，因此實驗主要在人造數據集上進行，主要關注兩個數據集R1和R2在進行多對多連接操作后的Skyline 查詢問題。實驗主要有5 個參數：數據集基數、分組基數、數據集維數、缺失率、自定義Skyline 候選集大小K。數據集基數指一個數據集中的數據項的數量。分組大小指每個數據集按照連接鍵值分組后每組包含的數據項數量。數據集維度指一個數據集的屬性維數。缺失率指發(fā)生數據缺失的數據單元與所有數據單元的比例。人造數據集的每一維數據均為0,1之間的實數且服從隨機分布。

每一組實驗主要對比基準算法、PISkyline算法、PSkyline-join 算法處理Skyline-join 查詢的性能。其中基準算法為未經任何優(yōu)化的概率Skyline[10]查詢算法，與該算法進行比較可以很好地觀察兩種剪枝策略對于多關系概率Skyline查詢效率的影響。

5.1 數據基數對算法性能的影響

該組實驗的具體設置為：R1和R2的缺失率和數據集維度固定為20%和3，Skyline候選集大小K固定為10，R2的數據集基數和分組基數固定為100和10，R1的數據集基數分別為1×103、2×103、3×103、4×103、5×103，R1的分組基數分別設置為100、200、300、400、500。由上述設置可知R1與R2連接后的數據集基數分別為1×104、2×104、3×104、4×104、5×104。圖2展示了3 種算法在各個數據基數上的性能。由圖2（a）可知PSkyline-join的算法效率最高，其耗時隨數據基數線性增長，基線算法耗時隨數據基數平方增長。圖2（b）展示了概率Skyline 計算涉及到的兩兩數據項比較次數，由于PSkyline-join 算法的剪枝策略2 是在多層次分組后進行，而非像PISkyline 算法在單層次地進行桶劃分后進行剪枝，故而剪枝率不如PISkyline高。圖2（c）展示了兩種剪枝策略的剪枝率，可以看出隨基數增長PSkyline-join 算法總的剪枝率基本不變，但剪枝策略2隨數據基數的增長發(fā)揮的作用線性增長。

5.2 數據維度對算法性能的影響

該組實驗設置為：R1和R2的缺失率固定為20%，Skyline候選集大小K固定為10，R1的數據基數和分組基數固定為1 000和100，R2的數據基數和分組基數固定為100和10，R1和R2的數據集維數分別為2、3、4、5、6。由上述設置可知R1和R2連接后的數據集基數為4、6、8、10、12。從圖3（a）可知PSkyline-join算法在各個維度的效率都為最優(yōu)，由圖3（c）可知當維數為8 時PSkyline-join 算法的總體剪枝效率最低，從而造成該維度下的算法效率低下。同時隨著維數的上升剪枝策略2 的作用越來越小。因為隨著維數的上升單個桶中的數據項數量下降，從而造成其中的數據項被支配的概率變小，局部Skyline 候選集變小。

5.3 數據缺失率對算法性能的影響

圖4展示了各個缺失率下各個算法的性能表現。該組實驗設置為R1數據集基數固定1 000，R1分組基數固定100，R2數據集基數固定100，R2分組基數固定10，缺失率分別為10%、20%、30%、40%、50%。如圖4（a）所示，注意該圖y軸刻度為對數型而非線性的，PSkyline-join算法始終表現最優(yōu)。從圖4（b）可以看出PSkyline算法在計算Skyline概率時的兩兩比較次數略少于PSkyline-join算法，但由于其桶劃分是針對連接后的所有數據項，因此在劃分并計算概率上界時消耗了大量時間，導致消耗的總時間多于PSkyline-join 算法。圖4（c）主要展示了兩種剪枝策略的剪枝率，可以看出隨著缺失率的增長，PSkylinejoin 算法的總體剪枝率緩慢下降，但剪枝策略2 的作用隨著缺失率增長有所提升。

Fig.3 Effect of dimensionality on performance圖3 數據維度對算法性能的影響

Fig.4 Effect of missing ratio on performance圖4 缺失率對算法性能的影響

6 結束語

本文針對非完整數據庫下的Skyline-join查詢問題進行了深入的分析和研究，提出了一種基于多層次分組的概率Skyline 查詢算法PSkyline-join。對單關系下的概率Skyline 進行了補充，使其適用于多關系。PSkyline-join 算法通過多層次分組計算數據項的Skyline概率上界，結合全局Skyline概率下界有效地對Skyline概率計算進行剪枝。當算法結束時為用戶返回最不可能被支配的K個數據項，從而滿足用戶的真實需求。實驗證明了PSkyline-join 算法能有效地解決非完整數據庫下的Skyline-join 查詢，其效率相較未優(yōu)化算法有著最多百倍的提升。