• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2020-08-12 02:17:50李征宇曹科研
      計(jì)算機(jī)與生活 2020年8期
      關(guān)鍵詞:元組支配定義

      李征宇,李 貴,曹科研

      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)容。

      猜你喜歡
      元組支配定義
      Python核心語(yǔ)法
      被貧窮生活支配的恐懼
      意林(2021年9期)2021-05-28 20:26:14
      海量數(shù)據(jù)上有效的top-kSkyline查詢算法*
      跟蹤導(dǎo)練(四)4
      基于減少檢索的負(fù)表約束優(yōu)化算法
      基于決策空間變換最近鄰方法的Pareto支配性預(yù)測(cè)
      隨心支配的清邁美食探店記
      Coco薇(2016年8期)2016-10-09 00:02:56
      成功的定義
      山東青年(2016年1期)2016-02-28 14:25:25
      修辭學(xué)的重大定義
      面向數(shù)據(jù)流處理的元組跟蹤方法
      揭阳市| 沁源县| 尼勒克县| 平远县| 天峻县| 望城县| 广昌县| 库尔勒市| 稷山县| 淮安市| 弥勒县| 社旗县| 思茅市| 上林县| 育儿| 苏尼特右旗| 永春县| 沽源县| 桂林市| 剑河县| 沙湾县| 诸暨市| 保康县| 治多县| 黄陵县| 信宜市| 高州市| 亚东县| 临泉县| 郴州市| 彩票| 本溪市| 丹江口市| 乐业县| 衡阳市| 逊克县| 祁连县| 广宁县| 浑源县| 舒城县| 乐昌市|