針對隱藏Web數(shù)據(jù)庫的Skyline查詢方法研究*

李征宇，李 貴，曹科研

1.東北大學 計算機科學與工程學院，沈陽 110004

2.沈陽建筑大學 信息與控制工程學院，沈陽 110168

1 引言

近年來，數(shù)據(jù)庫Skyline 查詢方法[1-4]得到了廣泛的研究。Skyline 查詢結(jié)果也被應用到多目標決策、top-k查詢[5-6]、近鄰搜索（nearest neighbor search）、凸包問題，以及基于用戶偏好查詢等眾多的領(lǐng)域中。例如，利用事先計算的Skyline 可以有效解決基于屬性排序的top-1查詢問題，文獻[5]利用基于Skyline擴展的K-skyband可以有效解決top-k（k≤K）查詢問題。

隨著Web 應用和Web 數(shù)據(jù)源的迅速增長，通過Web查詢接口來獲取服務端“隱藏”的數(shù)據(jù)庫Skyline已成為Web數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點。通過獲取隱藏Web數(shù)據(jù)庫的Skyline元組可以支持眾多基于Web的第三方應用，比如在Web信息集成中，通過獲取多個隱藏Web 數(shù)據(jù)庫的Skyline 元組，可以有效地解決滿足用戶偏好的top-k查詢和推薦問題。通過top-k查詢接口來獲取服務器端“隱藏”數(shù)據(jù)庫的Skyline 面臨著諸多挑戰(zhàn)，其中主要包括：（1）受top-k查詢限制，每次查詢結(jié)果最多返回滿足條件的k個元組；（2）用戶選擇的查詢條件受到Web接口類型和屬性類型的限制；（3）用戶端查詢次數(shù)受到Web服務器的限制等。基于這些挑戰(zhàn)，如何通過最少的查詢次數(shù)獲取服務端隱藏Web數(shù)據(jù)庫的Skyline的元組成為解決問題的關(guān)鍵，目前實現(xiàn)方法有兩種：一是通過Web 查詢接口獲取服務端隱藏Web 數(shù)據(jù)庫的所有元組，然后在本地生成數(shù)據(jù)庫的Skyline，這種方式的查詢代價往往很高，同時受到Web 服務端查詢次數(shù)的限制；二是通過設計合理的查詢分解算法和對應的查詢條件，通過Web 查詢接口以較少的查詢次數(shù)來獲取服務端隱藏Web數(shù)據(jù)庫的Skyline。文中針對第二種實現(xiàn)方法進行研究，主要貢獻如下：

利用平行坐標系分析Skyline元組折線的相交性質(zhì)；在定義相交元組查詢分解樹和證明查全性的基礎上提出了Web隱藏數(shù)據(jù)庫的Skyline元組的啟發(fā)式求解方法；并依據(jù)Web 接口類型提出了基于混合屬性條件范圍的隱藏Web 數(shù)據(jù)庫Skyline 元組求解算法；采用離線和在線數(shù)據(jù)集進行了算法的實驗驗證，通過理論分析和實驗結(jié)果表明文中提出的算法在查詢代價和查詢效率方面都優(yōu)于目前現(xiàn)有的方法。

2 相關(guān)研究

Skyline 的概念最初是由Borzsony、Kossmann 等人在文獻[7]提出，隨后研究者基于不同的背景進行了大量的研究工作，其中文獻[8-10]利用索引和預排序技術(shù)提出了在線和漸進式的Skyline計算方法。文獻[1]研究以支配分數(shù)作為度量，設計了基于表掃描的RSTS（ranked Skyline with table scan）算法來獲取海量數(shù)據(jù)上有效top-kSkyline 的查詢結(jié)果。文獻[2]在交互式多用戶的場景下，研究通過用戶交互動態(tài)調(diào)節(jié)用戶權(quán)重，設定滿意度度量，以確定滿意度最大的Skyline 候選集。文獻[3]利用Voronoi 圖解決靜態(tài)和動態(tài)障礙環(huán)境中Skyline查詢的問題。文獻[4]在數(shù)據(jù)更新頻繁時,研究基于時序支配的數(shù)據(jù)過濾方法，并提出了基于滑動窗口的ρ-支配輪廓查詢算法。文獻[5]研究了基于K-skyband的top-k查詢算法，文獻[6]研究了top-krepresentative Skylines 問題。文獻[7-9]分別研究了基于流數(shù)據(jù)、偏序關(guān)系、不確定數(shù)據(jù)和成組技術(shù)的Skyline 計算方法。文獻[11]研究了P2P 網(wǎng)絡下不確定數(shù)據(jù)top-k的近似解法，通過引入Quad-tree 索引，分別根據(jù)局部和全局top-k間的關(guān)系，以及Skyline和top-k的關(guān)系，確定上下界實現(xiàn)空間剪枝，最后通過采樣驗證候選集。上述文獻與Web 數(shù)據(jù)庫Skyline有關(guān)的研究主要體現(xiàn)在top-k查詢方面。文獻[12]關(guān)注的是數(shù)據(jù)流上動態(tài)輪廓查詢處理，動態(tài)輪廓查詢是Skyline 查詢的一個重要變種，目標對于一個給定的查詢點q，返回在維度上最接近q的所有點。文獻[13]針對Deep Web查詢失效問題，提出了基于top-k和Skyline 的查詢結(jié)果過濾方法和基于屬性重要程度和數(shù)據(jù)源關(guān)系圖的漸進式查詢策略。文獻[14]針對Deep Web集成查詢中進行的數(shù)據(jù)抽樣必須具備先驗知識的問題，提出了ANS（adaptive neighborhood sampling）和TPS（two phase adaptive sampling）兩種免先驗知識的采樣方法，以適用Web 隱藏數(shù)據(jù)庫的集成查詢。文獻[15]研究了Deep Web數(shù)據(jù)集成的查詢松弛策略，利用全局數(shù)據(jù)源關(guān)系圖DRG（global database relationship graph）進行松弛查詢，分別用Skyline、top-k方法篩選和排序結(jié)果集。文獻[16]針對目標屬性分屬不同站點的情況，研究了漸進式分布Skyline 方法PDS（progressive distributed Skylining），以支持不同類型的Skyline查詢和允許用戶監(jiān)督指導查詢。文獻[17-18]分別定義了優(yōu)先和頻繁Skyline點，并分別運用Skyline優(yōu)先級和Skyline頻繁度這兩個新的度量來降低Skyline 候選集的規(guī)模，達到提升k-regret算法的目的。

然而，目前針對隱藏Web 數(shù)據(jù)庫Skyline 的研究較少，文獻[19]在預知Web數(shù)據(jù)庫查詢排名函數(shù)和獲取所有排序元組的條件下，研究了從多個Web 數(shù)據(jù)庫獲取Skyline 計算方法。文獻[20]提出了一種基于Web查詢接口類型和屬性類別的混合查詢Skyline算法，但查詢代價高，有些情況會超出爬取整個Web數(shù)據(jù)庫的代價。

3 Skyline相關(guān)概念及性質(zhì)

3.1 相關(guān)概念

隱藏Web 數(shù)據(jù)庫是指Web 服務器端的數(shù)據(jù)庫，用戶對其查詢只能通過Web查詢接口（top-k查詢）獲得滿足條件的部分元組記錄。

假設隱藏Web數(shù)據(jù)庫D具有n個元組，每個元組t有m個屬性，分別記為A1,A2,…,Am。屬性Ai的值域表示為Dom(Ai)，屬性值表示為t[Ai]∈Dom(Ai)∪{NULL}(1 ≤i≤m)[15]。

Web 查詢接口依據(jù)隱藏Web 數(shù)據(jù)庫的屬性類型（數(shù)值型和分類型）可分為：范圍查詢、分類查詢和混合查詢。其中，范圍查詢基于數(shù)值屬性指定范圍條件的查詢，包括單端范圍查詢（如價格<300）和雙端范圍查詢（200<價格<300）；分類查詢是指基于分類屬性取一個或多個具體值的條件查詢；混合查詢是指既包括數(shù)值屬性的范圍查詢又包括分類屬性的分類查詢。

定義1（屬性優(yōu)先關(guān)系）數(shù)據(jù)庫元組的屬性按其重要程度進行排序，原則是重要的屬性排在前面，次要的屬性排在后面，對于屬性序列{A1,A2,…,Ai-1,Ai,…,Am}來說，Ai-1優(yōu)先Ai，記為Ai-1

定義2（元組支配關(guān)系）兩個元組ti和tj，如果對于任一屬性Ak(1 ≤k≤m)，都存在ti[Ak]≤tj[Ak]，則元組ti支配tj，元組ti和tj具有支配關(guān)系。否則，元組ti和tj是非支配關(guān)系。

定義3（元組優(yōu)先關(guān)系）兩個元組tr和ts是非支配關(guān)系，如果存在屬性Ak(1 ≤k≤m)，使得tr[Ai]≤ts[Ai](1 ≤its[Ak]，則元組tr優(yōu)先ts，記為tr

定義4（隱藏Web數(shù)據(jù)庫Skyline）隱藏Web數(shù)據(jù)庫D中所有非支配關(guān)系的元組構(gòu)成數(shù)據(jù)庫D的Skyline，有時也稱為Web數(shù)據(jù)庫D的輪廓。

定義5（支配一致性約束（dominate consistence constraint））Top-k查詢結(jié)果中的k個元組{t1,t2,…,tk}是Web服務器端依據(jù)Web接口查詢條件獲得結(jié)果元組中受支配最少的k個元組，并依據(jù)指定排名函數(shù)的元組優(yōu)先關(guān)系“<”排序得到的結(jié)果，即ti(1 ≤i

3.2 基于平行坐標系的Skyline元組性質(zhì)

平行坐標系的基本思想是將n維數(shù)據(jù)屬性空間通過n條等距離的平行軸映射到二維平面上，每一條軸線代表一個屬性維，軸線上的取值范圍為從對應屬性的最小值到最大值，這樣數(shù)據(jù)庫的每一個元組（或記錄）可以依據(jù)其屬性取值而用一條跨越n條平行軸的折線表示（這里要求對空值屬性和分類屬性進行適當處理和映射）。如表1的元組在平行坐標系的表示如圖1所示。

Table 1 Tuples of D表1 D的元組

定義6（相交關(guān)系和非相交關(guān)系）兩個元組ti和tj(1 ≤i,j≤n)如果存在屬性Ak和Ar(1 ≤k,r≤m,k≠r)使得ti[Ak]tj[Ar]同時存在，則元組ti和tj是相交關(guān)系。否則元組ti和tj是非相交關(guān)系。

Fig.1 Tuple-line diagram of parallel coordinates圖1 平行坐標系的元組折線圖

定義7（完全相交關(guān)系）對于任一k個元組，如果其中任何一個元組ti(1 ≤i≤k)和其他k-1 個元組存在相交關(guān)系，則這k個元組是完全相交關(guān)系。

引理1平行坐標系中任何一個元組支配其上面所有與其非相交的元組。

證明既然任一元組t0和位于其上的元組ti(1 ≤i≤n)都是非相交關(guān)系，由定義6 知t0和ti(1 ≤i≤n)均滿足t0[Ak]≤ti[Ak](1 ≤k≤m)，再由定義2 可知，t0支配ti(1 ≤i≤n)。 □

引理2相交關(guān)系的元組是非支配關(guān)系。

證明若元組ti和tj是相交關(guān)系，由定義6 知存在屬 性Ak和Ar(1 ≤k,r≤m,k≠r) 使 得ti[Ak]tj[Ar]同時存在，自然無法滿足對于任一屬性Ak(1 ≤k≤m)，都存在ti[Ak]≤tj[Ak]，也即元組ti和tj是非支配關(guān)系。 □

定理1一個數(shù)據(jù)庫的Skyline中所有元組都是完全相交關(guān)系。

證明（反證法）假設在數(shù)據(jù)庫的Skyline中存在兩個元組ti和tj(1 ≤i

定理2在數(shù)據(jù)庫的Skyline中新增一個元組t，該元組將Skyline劃分成兩部分，和t相交的元組S1，和t不相交元組S2，那么，若t位于S2 下面，則Skyline 由S1和t構(gòu)成；否則，t必位于S2上面且Skyline保持不變。

證明因為t和S1中的元組均相交，由引理2知，t和S1是非支配關(guān)系。此時，若t位于S2下面，由引理1 知，t支配S2，由定義4 可知Skyline 必由S1 和t構(gòu)成。相反地，若t并不位于S2 下面，假設t出現(xiàn)在S2的中間，那么S2 將被t分成互不相交的兩部分，這和S2 是Skyline 的一部分，由定理1知S2內(nèi)的元組是完全相交的已知條件相矛盾，故t只可能出現(xiàn)在S2的上方，再由引理1知，S2的所有元組均支配t，最后由定義4知t不是Skyline的組成部分，故Skyline保持不變。□

4 隱藏Web數(shù)據(jù)庫Skyline查詢方法

4.1 相交元組查詢樹的構(gòu)造及性質(zhì)

假設：查詢qi的top-k結(jié)果集T滿足支配一致性約束，結(jié)果集T的首條元組為t。

q0：SELECT*FROMD；

依據(jù)查詢q0返回結(jié)果T，當|T|≥K時，將T的首條元組t遞歸定義如下查詢分解q1,q2,…,qm-1；當|T|

q1：WHEREA1

q2：WHEREA1≥t[A1]&A2

q3：WHEREA1≥t[A1]&A2≥t[A2]&A3

……

qi：WHEREA1≥t[A1]&A2≥t[A2]&…&Ai-1≥t[Ai-1]&Ai

……

qm：WHEREA1≥t[A1]&A2≥t[A2]&…&Am-1≥t[Am-1]&Am

B_Const(t)：表示父節(jié)點t的分支查詢條件，由根節(jié)點到該父親節(jié)點的路徑條件的合取組成。如果父節(jié)點是根節(jié)點，則B_Const(t)=TRUE。

P_Const(qi)=B_Const(t)&A1≥t[A1]&A2≥t[A2]&…&Ai-1≥t[Ai-1]：表示查詢qi查詢的前置條件；

上述查詢可進一步簡化為：

q1：WHEREP_Const(q1)&A1

q2：WHEREP_Const(q2)&A2

……

qi：WHEREP_Const(qi)&Ai

……

qm：WHEREP_Const(qm-1)&Am

例1假設數(shù)據(jù)庫D的屬性集和元組集如表1 所示，圖2所示為基于top-3的相交元組查詢分解樹，該查詢樹的所有中間節(jié)點都將返回top-3結(jié)果的首條元組，相交元組查詢分解的查詢結(jié)果是S={t2,t4,t1,t3,t6,t5,t7}，從圖2 中可以看出S中的所有元組在平行坐標系中的折線是完全相交關(guān)系。

Fig.2 Intersectant tuples query decomposition tree of example 1 based on top-3圖2 例1基于top-3的相交元組查詢分解樹

由上述相交元組查詢分解樹的構(gòu)造可知其具有如下性質(zhì)：

（1）相交元組查詢分解條件在屬性A1,A2,…,Ai-1,Ai,…,Am-1范圍上是互斥和全覆蓋的。

（2）（相交關(guān)系查全性）父節(jié)點的首條元組在條件范圍P_Const(qi)下，通過q1,q2,…,qm的m個查詢分解找到的在屬性A1,A2,…,Ai-1,Ai,…,Am上與其有相交關(guān)系的最優(yōu)先元組，分解到最后將找到所有與父節(jié)點具有相交關(guān)系的元組。

（3）（同一條枝條的完全相交關(guān)系）同一條分支上的所有節(jié)點元組都具有完全相交關(guān)系。

（4）（不同枝條的非完全相交關(guān)系）由于查詢條件P_Const(qi)的限制，不同分支上的節(jié)點元組可能存在支配關(guān)系，即非相交關(guān)系或非完全相交關(guān)系。

（5）（同層分解的非重復性）由于查詢條件的互斥性，任何節(jié)點的查詢分解都不會出現(xiàn)重復元組。

定理3（查全性）如果一個元組t∈D是數(shù)據(jù)庫D的Skyline 中的一個元組，即t∈Skyline，則在相交元組查詢分解樹中存在一個查詢節(jié)點qi，使得該節(jié)點的查詢結(jié)果T包含元組t(t∈T)。

證明由于t∈Skyline，由定理1 得知，至少存在屬性Ai,Aj(1

t[Ai]>t′[Ai]&t[Aj]

由定義8得知：在相交元組查詢分解過程中將存在一個查詢節(jié)點t″(t″∈Skyline) 和一個正整數(shù)k(1

t[A1]≥t″[A1]&t[A2]≥t″[A2]&…&t[Ak-1]≥t″[Ak-1]&t[Ak]

即，元組t被包含在節(jié)點t″的一個分支節(jié)點的查詢結(jié)果T中，|T|≥k時，作為首條元組出現(xiàn)。 □

4.2 Web數(shù)據(jù)庫Skyline查詢方法

4.2.1 基本查詢分解方法

依據(jù)相交元組查詢分解樹的定義和Skyline元組的完全相交性質(zhì)，提出如下基本查詢分解方法。

基本查詢分解方法的基本思路[19-20]：

（1）通過深度優(yōu)先或廣度優(yōu)先方式建立相交元組查詢分解樹，獲得隱藏Web數(shù)據(jù)庫D中所有具有相交關(guān)系的元組集S1和S2，其中S1是查詢分解樹的中間節(jié)點的首條元組集合，S2是查詢分解樹的葉子節(jié)點的元組集合。

（2）對于S1?S2中的元組，依據(jù)Skyline元組的完全相交性質(zhì)生成隱藏Web數(shù)據(jù)庫D的Skyline元組集。

4.2.2 啟發(fā)式查詢分解方法

為減少查詢代價（遠程查詢次數(shù)）提高查詢效率，提出如下啟發(fā)式查詢分解方法。

啟發(fā)式查詢分解方法的基本思路：

（1）在基本查詢分解中，每次查詢分解首先在父節(jié)點的返回結(jié)果集中進行本地查詢，如果查詢結(jié)果非空，則不發(fā)出遠程查詢請求；如果查詢結(jié)果為空，則發(fā)出遠程查詢請求。

（2）如果查詢結(jié)果的首條元組t被當前查詢樹的某一節(jié)點的查詢結(jié)果中的元組t′支配，則將t置換為t′繼續(xù)分解。

定理4啟發(fā)式分解方法具有查全性。

證明對于啟發(fā)式的情況（1），若子節(jié)點對父節(jié)點的分解結(jié)果的本地查詢非空，結(jié)果集的首記錄記為t1，那么容易知道該子節(jié)點若進行遠程訪問所獲查詢結(jié)果亦非空，結(jié)果集的首記錄記為t2，由隱藏Web數(shù)據(jù)庫的支配一致性約束知，t1=t2，故可用非空的本地查詢代替遠程查詢（為確保約束成立，只需保證父節(jié)點分解結(jié)果中元組出現(xiàn)的先后順序在本地查詢的結(jié)果中維持不變）。

對于啟發(fā)式的情況（2），將t置換為t′，由于t被t′支配，那么由t′產(chǎn)生的分解樹將更為簡短，因為根據(jù)分解樹的生成條件表達式，t′產(chǎn)生的條件表達式中必有一子項比t的上界更低，進而可以更多更快地過濾非Skyline元組，但所剩元組（包括中間節(jié)點和葉子節(jié)點）所構(gòu)成的分解樹中包含的Skyline 是不變的。由（1）、（2）知啟發(fā)式方法的查全性。 □

4.3 查詢方法代價分析

在求解服務端隱藏Web數(shù)據(jù)庫的Skyline元組時查詢代價的主要因素決定于遠程查詢次數(shù)，依據(jù)相交元組查詢分解樹的定義得知，遠程查詢次數(shù)等于相交元組查詢分解樹中的遠程查詢分支數(shù)。

定理5啟發(fā)式查詢分解方法的查詢代價C（遠程查詢次數(shù)）在K≤m條件下滿足如下不等式：

m+1 ≤C<(|S|+[n/k])×m(k≤n)

證明從查詢的分解過程得知：從最初通過Q0=SELECR*FROM D →T0查詢得到的T0的首條元組t1（t1∈Skyline 元組）開始，對t1的每一次分解查詢Qi，首先依據(jù)父節(jié)點的查詢結(jié)果T0執(zhí)行本地查詢，查詢的結(jié)果為Ti：

當Ti≠?時取T中的首條元組繼續(xù)m次分解；

當Ti=?時執(zhí)行遠程查詢；

當遠程查詢結(jié)果|Ti|

當遠程查詢結(jié)果|Ti|≥K時，再依據(jù)Ti的首條元組t1進行m次的查詢分解。

由于在查詢分解過程中，查詢Qi的首條元組有可能被當前S1?S2中的元組支配，因此在查詢分解樹中會存在Skyline 元組被重復分解的情況，但是由于查詢分解條件的屬性范圍是互斥的，因此Skyline元組重復分解的次數(shù)一定不會大于[n/k]次。

因此查詢分解樹的中間節(jié)點數(shù)不會超過|S|+[n/k]，查詢樹中總的分支數(shù)（每一條分支代表一次查詢）將不會超過(|S|+[n/k])×m。

查詢分解樹中，遠程查詢的次數(shù)必然小于查詢樹中總的分支數(shù)，即遠程查詢代價C<(|S|+[n/k])×m。

又因為D中至少有一條Skyline 元組，所以遠程查詢代價C≥m+1。 □

5 實驗分析

通過模擬實驗和在線真實實驗兩個步驟進行。在模擬實驗部分采用兩個數(shù)據(jù)庫：學生成績模擬數(shù)據(jù)庫和實際項目中真實的房地產(chǎn)戶型數(shù)據(jù)庫，并開發(fā)了基于top-k的查詢接口。由于數(shù)據(jù)庫已經(jīng)裝載在本地，數(shù)據(jù)庫的結(jié)構(gòu)特性（實體的屬性類型、數(shù)量和關(guān)系等）和數(shù)值特性（記錄元組個數(shù)等）都是已知的，因此可以通過對這些特性值的調(diào)節(jié)來檢驗算法的查全性，測試它們的查詢代價，以及觀測它們隨不同因素影響的變化趨勢等。在線實驗依據(jù)房譜網(wǎng)（http：//www.house-book.com.cn）真實網(wǎng)站對算法進行測試。

5.1 數(shù)據(jù)集

學生成績數(shù)據(jù)庫包括10 門課程（包括5 門數(shù)值屬性的考試課和5 門分類屬性的考查課）且存儲有100 000條記錄。考試課的成績?nèi)≈捣秶鸀閇0,100]，考查課的成績?nèi)≈捣秶鸀椋?-優(yōu)，4-良，3-中，2-及格，1-差）。房地產(chǎn)戶型數(shù)據(jù)庫中設置10個屬性，包含5 300余萬條記錄。實驗中選取5個數(shù)值屬性和5個分類屬性。

5.2 實驗結(jié)果分析

首先，需要驗證基本分解算法和啟發(fā)式分解算法的查全性。在對模擬數(shù)據(jù)驗證成功后，對實際的網(wǎng)絡數(shù)據(jù)集進行抓取并全部存儲在本地，然后運用本地Skyline求解算法獲取正確的Skyline集，并用此對基本分解算法和啟發(fā)式分解算法獲得的結(jié)果集進行驗證。結(jié)果表明，無論在模擬數(shù)據(jù)還是實際網(wǎng)絡數(shù)據(jù)集上，上述兩種算法均滿足查全性，查全性驗證完畢。此處出于完整性，進行必要的說明，不過鑒于查全性不是本文研究的重點，因此相關(guān)的實驗內(nèi)容就不再列出。

然后，比較基本分解算法和啟發(fā)式分解算法的查詢代價，也即遠程查詢的次數(shù)C。根據(jù)查詢代價的理論分析結(jié)果m+1 ≤C<(|S|+[n/k])×m(k≤n)，考察參數(shù)集{m,|S|,n,k}的變化對上述兩種算法的查詢代價C的影響。此處，為了便于比較兩種算法，當考察一個參數(shù)影響時，固定了其他3個參數(shù)；考慮到普遍性，其他3個參數(shù)設定應當令數(shù)據(jù)集具有代表性。為此，通過分析設定了相關(guān)影響因子，以此生成各典型的數(shù)據(jù)集。主要的因子包括：Skyline 集占全數(shù)據(jù)集的比例因子，通過它可以生成稠密集、普通集、稀疏集；范圍型字段和枚舉型字段的比例因子，通過它可以生成不同構(gòu)成的數(shù)據(jù)集；規(guī)模因子，通過它可生成規(guī)模不等的數(shù)據(jù)集。由于待比較的參數(shù)較多，相應組合的情形更多，鑒于篇幅，下面僅列出在各類典型設定中4個參數(shù)對兩算法影響的代表情形，即包括屬性的影響效果如圖3，Skyline元組數(shù)|S|的影響效果如圖4，數(shù)據(jù)集規(guī)模的影響效果如圖5 和top-k中k的影響效果如圖6。

Fig.3 Effect of number of attributes m on query cost圖3 屬性個數(shù)m對查詢代價的影響

Fig.4 Effect of number of Skyline tuples|S|on query cost圖4 Skyline元組數(shù)|S|對查詢代價的影響

Fig.5 Effect of data set size n on query cost圖5 數(shù)據(jù)集規(guī)模n對查詢代價的影響

Fig.6 Effect of top-k on query cost圖6 top-k對查詢代價的影響

最后，實驗結(jié)果表明無論在哪種情況下，啟發(fā)式分解算法的代價都要優(yōu)于傳統(tǒng)的基本分解算法。

6 結(jié)束語

通過Web 接口來獲取服務端“隱藏”的數(shù)據(jù)庫Skyline 已成為Web 數(shù)據(jù)挖掘領(lǐng)域的一個研究熱點，文中通過引入平行坐標系技術(shù)分析了數(shù)據(jù)庫多維數(shù)據(jù)的Skyline 元組相交性質(zhì)，在定義相交元組查詢分解樹和證明查全性的基礎上，提出了隱藏Web 數(shù)據(jù)庫的Skyline 元組的基本求解算法和啟發(fā)式求解方法，并通過理論分析和實驗驗證了方法的有效性。

盡管如此，啟發(fā)式算法的實驗中，特別針對各類典型的模擬數(shù)據(jù)集的實驗中，發(fā)現(xiàn)無效的查詢在不同特性數(shù)據(jù)集中差距巨大，因而在數(shù)據(jù)集采樣的基礎上分析其特性，進而針對不同類型的數(shù)據(jù)集設定不同策略，達到進一步減少遠程查詢次數(shù)的目的。

此外，在Web 信息集成中，如何通過上述方法來有效地解決基于用戶偏好的top-k查詢和推薦等問題是下一步要研究的內(nèi)容。