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

李征宇，李 貴，曹科研

1.東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110004

2.沈陽(yáng)建筑大學(xué) 信息與控制工程學(xué)院，沈陽(yáng) 110168

1 引言

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

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

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

2 相關(guān)研究

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

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

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

3.1 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

Table 1 Tuples of D表1 D的元組

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

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

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

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

證明既然任一元組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]同時(shí)存在，自然無(wú)法滿足對(duì)于任一屬性Ak(1 ≤k≤m)，都存在ti[Ak]≤tj[Ak]，也即元組ti和tj是非支配關(guān)系。 □

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

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

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

證明因?yàn)閠和S1中的元組均相交，由引理2知，t和S1是非支配關(guān)系。此時(shí)，若t位于S2下面，由引理1 知，t支配S2，由定義4 可知Skyline 必由S1 和t構(gòu)成。相反地，若t并不位于S2 下面，假設(shè)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ù)庫(kù)Skyline查詢方法

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

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

q0：SELECT*FROMD；

依據(jù)查詢q0返回結(jié)果T，當(dāng)|T|≥K時(shí)，將T的首條元組t遞歸定義如下查詢分解q1,q2,…,qm-1；當(dāng)|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é)點(diǎn)t的分支查詢條件，由根節(jié)點(diǎn)到該父親節(jié)點(diǎn)的路徑條件的合取組成。如果父節(jié)點(diǎn)是根節(jié)點(diǎn)，則B_Const(t)=TRUE。

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

上述查詢可進(jìn)一步簡(jiǎn)化為：

q1：WHEREP_Const(q1)&A1

q2：WHEREP_Const(q2)&A2

……

qi：WHEREP_Const(qi)&Ai

……

qm：WHEREP_Const(qm-1)&Am

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2.1 基本查詢分解方法

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

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

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

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

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

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

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

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

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

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

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

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

4.3 查詢方法代價(jià)分析

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

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

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

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

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

當(dāng)Ti=?時(shí)執(zhí)行遠(yuǎn)程查詢；

當(dāng)遠(yuǎn)程查詢結(jié)果|Ti|

當(dāng)遠(yuǎn)程查詢結(jié)果|Ti|≥K時(shí)，再依據(jù)Ti的首條元組t1進(jìn)行m次的查詢分解。

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

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

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

又因?yàn)镈中至少有一條Skyline 元組，所以遠(yuǎn)程查詢代價(jià)C≥m+1。 □

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

Fig.6 Effect of top-k on query cost圖6 top-k對(duì)查詢代價(jià)的影響

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

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

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

盡管如此，啟發(fā)式算法的實(shí)驗(yàn)中，特別針對(duì)各類典型的模擬數(shù)據(jù)集的實(shí)驗(yàn)中，發(fā)現(xiàn)無(wú)效的查詢?cè)诓煌匦詳?shù)據(jù)集中差距巨大，因而在數(shù)據(jù)集采樣的基礎(chǔ)上分析其特性，進(jìn)而針對(duì)不同類型的數(shù)據(jù)集設(shè)定不同策略，達(dá)到進(jìn)一步減少遠(yuǎn)程查詢次數(shù)的目的。

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