非完整數(shù)據(jù)庫(kù)Skyline-join查詢(xún)*

鮑斌國(guó)，秦小麟，李星羅，張 彤

南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106

1 引言

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

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

但是傳統(tǒng)的非完整數(shù)據(jù)庫(kù)Skyline查詢(xún)明顯有以下兩個(gè)缺點(diǎn)：（1）支配傳遞性的丟失。這不僅大大增加計(jì)算量，因?yàn)椴坏貌粚?duì)所有數(shù)據(jù)進(jìn)行兩兩比較，而且會(huì)使Skyline查詢(xún)結(jié)果過(guò)少甚至是空集。（2）一些非正常的數(shù)據(jù)項(xiàng)出現(xiàn)在結(jié)果集中。比如僅有極少維度數(shù)據(jù)完整的數(shù)據(jù)項(xiàng)，它們難以為用戶(hù)提供有效的選擇。這些缺點(diǎn)都會(huì)嚴(yán)重誤導(dǎo)用戶(hù)的選擇。

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

因此提出了PSkyline-join算法，該算法主要有四個(gè)步驟：對(duì)于單個(gè)關(guān)系中的數(shù)據(jù)項(xiàng)進(jìn)行多層次分組；確定每組的局部Skyline 結(jié)果集；采用剪枝策略連接局部Skyline結(jié)果集；確定全局Skyline集合。本文的主要貢獻(xiàn)如下：

（1）對(duì)概率Skyline 的定義進(jìn)行補(bǔ)充使其適用于多表連接Skyline查詢(xún)。

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

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

本文的組織結(jié)構(gòu)如下：第2章介紹了非完整數(shù)據(jù)庫(kù)Skyline 查詢(xún)的相關(guān)工作；第3 章給出了非完整數(shù)據(jù)庫(kù)及概率Skyline 的基礎(chǔ)定義；第4 章詳細(xì)介紹了Skyline-join 的算法流程，包括多層次分組及兩種剪枝策略；第5 章通過(guò)實(shí)驗(yàn)評(píng)估了該算法性能；第6 章總結(jié)全文。

2 相關(guān)工作

關(guān)于非完整數(shù)據(jù)庫(kù)中的Skyline 查詢(xún)最早由Khalefa 等[5]提出，文獻(xiàn)給出了一種非完整數(shù)據(jù)庫(kù)中Skyline 查詢(xún)的定義，即兩個(gè)數(shù)據(jù)項(xiàng)僅在它們都不缺失數(shù)據(jù)的維度上進(jìn)行比較來(lái)得出支配關(guān)系。同時(shí)也提出了Bucket 和ISkyline 算法以計(jì)算非完整數(shù)據(jù)庫(kù)中的Skyline查詢(xún)結(jié)果集。

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

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

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

3 問(wèn)題定義

本章主要介紹非完整數(shù)據(jù)庫(kù)和Skyline查詢(xún)的相關(guān)定義與概念。

定義1（單關(guān)系概率支配[10]）對(duì)于兩個(gè)擁有d維屬性的數(shù)據(jù)項(xiàng)p和q∈D，q支配p的概率定義為：

其中，E(p)表示與p完全相等的數(shù)據(jù)項(xiàng)集合。

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

（1）所有的數(shù)據(jù)項(xiàng)之間都是獨(dú)立的；

（2）數(shù)據(jù)項(xiàng)各個(gè)維度的屬性都是獨(dú)立的；

（3）缺失值是隨機(jī)出現(xiàn)在各個(gè)維度上的。

有了以上假設(shè)，當(dāng)p(i)和q(i)都是缺失值時(shí)：

定義1僅考慮了單個(gè)關(guān)系情形下的概率支配，但當(dāng)Skyline 查詢(xún)涉及到多關(guān)系時(shí)，定義1 假設(shè)所有的數(shù)據(jù)項(xiàng)之間都是獨(dú)立的，該條件明顯不成立，因?yàn)檫B接操作后兩個(gè)數(shù)據(jù)項(xiàng)中的部分維度有可能來(lái)自同一個(gè)關(guān)系的同一數(shù)據(jù)項(xiàng)。因此定義2 對(duì)定義1 進(jìn)行了拓展，使其可以應(yīng)用于多關(guān)系Skyline查詢(xún)。

定義2（多關(guān)系概率支配）對(duì)于由多個(gè)關(guān)系連接而來(lái)的數(shù)據(jù)項(xiàng)p和q，q支配p的定義為：

其中，βi表示數(shù)據(jù)項(xiàng)中來(lái)自關(guān)系Ri的屬性:

由定義2可知，當(dāng)p和q的部分屬性來(lái)自同一關(guān)系的同一數(shù)據(jù)項(xiàng)時(shí)，這部分屬性將不會(huì)對(duì)支配概率產(chǎn)生任何影響。

定義3（非完整數(shù)據(jù)下概率Skyline查詢(xún)）對(duì)于一個(gè)非完整數(shù)據(jù)集S，用戶(hù)指定一個(gè)參數(shù)K(K>0),概率Skyline查詢(xún)結(jié)果集表示為：

其中：

直觀上來(lái)看，概率Skyline 查詢(xún)的結(jié)果就是Skyline概率排名前K位的數(shù)據(jù)項(xiàng)，即最不可能被支配的前K個(gè)數(shù)據(jù)項(xiàng)。

考慮表2 中的數(shù)據(jù)集，用戶(hù)設(shè)置K=2。首先計(jì)算每一維度上的概率分布函數(shù)

Table 2 Incomplete data set S2表2 非完整數(shù)據(jù)集S2

4 PSkyline-join算法

如圖1 所示PSkyline-join 算法主要有四個(gè)步驟：數(shù)據(jù)項(xiàng)多層次分組；確定局部Skyline概率；連接數(shù)據(jù)項(xiàng)；確定全局Skyline結(jié)果集。

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

4.1 數(shù)據(jù)項(xiàng)分組

第一層分組：對(duì)于某個(gè)關(guān)系將連接鍵值相同的數(shù)據(jù)項(xiàng)劃分到一組中。第二層分組：在進(jìn)行上述第一層分組后，再根據(jù)數(shù)據(jù)項(xiàng)的缺失位圖對(duì)數(shù)據(jù)項(xiàng)進(jìn)行二次劃分，即桶劃分[5]。

考慮例子：對(duì)于表3 中的關(guān)系R1假設(shè)連接鍵為id，首先將id 值相同的屬性項(xiàng)劃分到同一組中，表4展示了上述劃分結(jié)果。然后對(duì)于每一組中的數(shù)據(jù)項(xiàng)根據(jù)缺失位圖進(jìn)行桶劃分，劃分結(jié)果如表5所示。

數(shù)據(jù)項(xiàng)多層次分組主要是為了輔助計(jì)算局部Skyline概率上界。

4.2 計(jì)算局部Skyline概率上界

對(duì)于每個(gè)桶中的數(shù)據(jù)項(xiàng)，僅比較兩個(gè)數(shù)據(jù)項(xiàng)都未缺失數(shù)據(jù)項(xiàng)的維度，從而得到它們之間的支配關(guān)系。按照上述支配定義，兩兩比較桶中的數(shù)據(jù)項(xiàng)求得每個(gè)桶的局部Skyline候選集。表5灰色背景填充的數(shù)據(jù)項(xiàng)即為局部Skyline候選集。

Table 3 R1data set表3 R1數(shù)據(jù)集示例

Table 4 R1group dividing表4 R1組劃分

Table 5 R1bucket dividing表5 R1桶劃分

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

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

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

定理1 主要闡明了桶內(nèi)數(shù)據(jù)項(xiàng)在與其他數(shù)據(jù)項(xiàng)連接后所能達(dá)到的Skyline概率上限值。同時(shí)由定理1可知局部Skyline候選集的概率上界為1。

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

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

輸入：非完整數(shù)據(jù)集S。

輸出：各個(gè)數(shù)據(jù)項(xiàng)的局部Skyline概率上界。

4.3 連接數(shù)據(jù)項(xiàng)

在連接數(shù)據(jù)項(xiàng)時(shí)，除了正常的連接操作外，還需要計(jì)算數(shù)據(jù)項(xiàng)的全局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，不失一般性假設(shè)Psup(τ1p)<1，Psup(τ2p)=1，由定理1 可知τ1p在與其他數(shù)據(jù)項(xiàng)連接后的Skyline 概率上限值為Psup(τ1p)，故P(p)≤Psup(τ1p)，Psup(p)=Psup(τ1p)上式成立。若Psup(τ1p)<1且Psup(τ2p)<1，由定理1證明過(guò)程可知?m≡τ1q?τ2p及n≡τ1p?τ2q在非缺失維度上支配p,由此得:

定理2 主要闡明了局部Skyline概率上界與全局Skyline 概率上界的關(guān)系，從而可以高效地計(jì)算數(shù)據(jù)項(xiàng)的全局Skyline 概率上界，故可以建立高效的剪枝策略。

4.4 計(jì)算全局概率Skyline集合

在連接各個(gè)關(guān)系的數(shù)據(jù)項(xiàng)后，需要為用戶(hù)返回全局的Skyline 集合。為了去除不必要的Skyline 概率計(jì)算，采用了兩種剪枝策略。

剪枝策略1若數(shù)據(jù)項(xiàng)p在與數(shù)據(jù)項(xiàng)q比較后，其Skyline概率已經(jīng)小于全局的Skyline概率下界，則可以中斷計(jì)算p的Skyline概率。

算法2Skyline概率算法SkylinePro

輸入：非完整數(shù)據(jù)集Q，數(shù)據(jù)項(xiàng)p,globalLowBound。

輸出：數(shù)據(jù)項(xiàng)Skyline概率。

剪枝策略2若數(shù)據(jù)項(xiàng)p的全局Skyline概率上界小于全局Skyline 概率下界，則無(wú)需計(jì)算數(shù)據(jù)項(xiàng)p的Skyline概率。

算法3PSkyline-join算法PSkyline-join

輸入：非完整數(shù)據(jù)集{R1,R2,…,Rn},Skyline 結(jié)果集大小K。

輸出：Skyline結(jié)果集。

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

5 實(shí)驗(yàn)及分析

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

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

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

5.1 數(shù)據(jù)基數(shù)對(duì)算法性能的影響

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

5.2 數(shù)據(jù)維度對(duì)算法性能的影響

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

5.3 數(shù)據(jù)缺失率對(duì)算法性能的影響

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

Fig.3 Effect of dimensionality on performance圖3 數(shù)據(jù)維度對(duì)算法性能的影響

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

6 結(jié)束語(yǔ)

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