[發(fā)明專利]基于垂直劃分模式的分布并行Skyline查詢方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110327359.6
• 申請(qǐng)日: 2011-10-26
• 公開(kāi)（公告）號(hào): CN102323957A
• 公開(kāi)（公告）日: 2012-01-18
• 發(fā)明（設(shè)計(jì)）人: 王意潔;王媛;鄧瑞鵬;裴曉強(qiáng);李小勇;孫偉東;馬行空
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 國(guó)防科技大學(xué)專利服務(wù)中心 43202
• 代理人: 郭敏

1.一種基于垂直劃分模式的分布并行Skyline查詢方法，其特征在于包括以下步驟：

第一步，構(gòu)建一個(gè)分布并行計(jì)算環(huán)境，它由多個(gè)節(jié)點(diǎn)構(gòu)成，每個(gè)節(jié)點(diǎn)都是一臺(tái)可獨(dú)立運(yùn)行的計(jì)算機(jī)，各節(jié)點(diǎn)通過(guò)網(wǎng)絡(luò)設(shè)備互連；節(jié)點(diǎn)包括一個(gè)協(xié)調(diào)節(jié)點(diǎn)和N個(gè)計(jì)算節(jié)點(diǎn)，N是原始數(shù)據(jù)集中數(shù)據(jù)對(duì)象的維度數(shù)目，N為正整數(shù)；協(xié)調(diào)節(jié)點(diǎn)負(fù)責(zé)存儲(chǔ)原始數(shù)據(jù)集中的所有數(shù)據(jù)對(duì)象的編號(hào)，負(fù)責(zé)與用戶交互，接收用戶提交的查詢請(qǐng)求，向各計(jì)算節(jié)點(diǎn)分發(fā)查詢處理任務(wù)和收集查詢處理結(jié)果，并向用戶返回查詢結(jié)果；每個(gè)計(jì)算節(jié)點(diǎn)存儲(chǔ)原始數(shù)據(jù)集的一個(gè)維度上的所有數(shù)據(jù)，計(jì)算節(jié)點(diǎn)執(zhí)行查詢處理任務(wù)，并向協(xié)調(diào)節(jié)點(diǎn)返回查詢處理結(jié)果；協(xié)調(diào)節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)上均安裝有操作系統(tǒng)、TCP/IP協(xié)議軟件，配置了網(wǎng)絡(luò)環(huán)境；協(xié)調(diào)節(jié)點(diǎn)上安裝有任務(wù)調(diào)度程序和結(jié)果分析處理程序，任務(wù)調(diào)度程序接收用戶提交的Skyline查詢請(qǐng)求，向各計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢處理任務(wù)，結(jié)果分析處理程序負(fù)責(zé)收集計(jì)算節(jié)點(diǎn)的Skyline查詢處理結(jié)果，并對(duì)收集到的所有計(jì)算節(jié)點(diǎn)的Skyline查詢處理結(jié)果再進(jìn)行Skyline查詢處理以得到最終的Skyline查詢結(jié)果；計(jì)算節(jié)點(diǎn)上安裝有查詢處理程序，查詢處理程序負(fù)責(zé)接收來(lái)自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢請(qǐng)求，并對(duì)計(jì)算節(jié)點(diǎn)上存儲(chǔ)的原始數(shù)據(jù)集進(jìn)行Skyline查詢處理；

第二步，協(xié)調(diào)節(jié)點(diǎn)執(zhí)行任務(wù)調(diào)度程序，向各計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢處理任務(wù)；各計(jì)算節(jié)點(diǎn)執(zhí)行查詢處理程序，接收來(lái)自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢處理任務(wù)，并行進(jìn)行Skyline查詢處理：

2.1協(xié)調(diào)節(jié)點(diǎn)的任務(wù)調(diào)度程序接收用戶提交的Skyline查詢請(qǐng)求；

2.2協(xié)調(diào)節(jié)點(diǎn)的任務(wù)調(diào)度程序向所有計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢處理任務(wù)，具體步驟如下：

2.2.1任務(wù)調(diào)度程序根據(jù)計(jì)算節(jié)點(diǎn)的數(shù)目N將原始數(shù)據(jù)集的所有M個(gè)數(shù)據(jù)對(duì)象編號(hào)分成大小均等的N個(gè)數(shù)據(jù)對(duì)象編號(hào)集合，每個(gè)數(shù)據(jù)對(duì)象編號(hào)集合包括[M/N]個(gè)或者[M/N]+1個(gè)數(shù)據(jù)對(duì)象編號(hào)，M為數(shù)據(jù)對(duì)象編號(hào)總數(shù)，M為正整數(shù)，[M/N]表示不超過(guò)M/N的最大整數(shù)；

2.2.2任務(wù)調(diào)度程序向所有計(jì)算節(jié)點(diǎn)分發(fā)Skyline查詢請(qǐng)求，并向每個(gè)計(jì)算節(jié)點(diǎn)分發(fā)一個(gè)數(shù)據(jù)對(duì)象編號(hào)集合；

2.3每個(gè)計(jì)算節(jié)點(diǎn)的查詢處理程序接收來(lái)自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢處理任務(wù)，根據(jù)接收的Skyline查詢請(qǐng)求對(duì)收到的數(shù)據(jù)對(duì)象編號(hào)集合對(duì)應(yīng)的數(shù)據(jù)對(duì)象構(gòu)成的集合進(jìn)行Skyline查詢處理，具體步驟如下：

2.3.1查詢處理程序接收來(lái)自協(xié)調(diào)節(jié)點(diǎn)的Skyline查詢請(qǐng)求和數(shù)據(jù)對(duì)象編號(hào)集合；

2.3.2查詢處理程序初始化查詢處理結(jié)果集合簡(jiǎn)稱Skyline集合

2.3.3查詢處理程序從其他計(jì)算節(jié)點(diǎn)獲取計(jì)算節(jié)點(diǎn)負(fù)責(zé)的數(shù)據(jù)對(duì)象集合中所有數(shù)據(jù)對(duì)象的全部維度數(shù)據(jù)，組成本地原始數(shù)據(jù)集Set；

2.3.4查詢處理程序?qū)Ρ镜卦紨?shù)據(jù)集合Set中的所有數(shù)據(jù)對(duì)象逐一進(jìn)行數(shù)據(jù)對(duì)象之間的控制關(guān)系判斷，將不被Set中任意一個(gè)其他數(shù)據(jù)對(duì)象所控制的數(shù)據(jù)對(duì)象放到Skyline集合LS中，即，判斷本地原始數(shù)據(jù)集Set中的每個(gè)數(shù)據(jù)對(duì)象DO與Set中的所有其他數(shù)據(jù)對(duì)象之間的控制關(guān)系，如果DO不被Set中任意一個(gè)其他數(shù)據(jù)對(duì)象所控制，則將DO放入計(jì)算節(jié)點(diǎn)的Skyline集合LS中，即，LS＝LS+{DO}；

2.3.5查詢處理程序?qū)kyline集合LS返回給協(xié)調(diào)節(jié)點(diǎn)。

第三步，協(xié)調(diào)節(jié)點(diǎn)的結(jié)果分析處理程序收集所有計(jì)算節(jié)點(diǎn)的Skyline集合LS，并對(duì)其進(jìn)行Skyline查詢處理，得到最終的Skyline查詢結(jié)果：

3.1結(jié)果分析處理程序收集所有計(jì)算節(jié)點(diǎn)的Skyline集合LS；

3.2結(jié)果分析處理程序合并所有計(jì)算節(jié)點(diǎn)的Skyline集合LS，得到新數(shù)據(jù)集NS；

3.3初始化協(xié)調(diào)節(jié)點(diǎn)的Skyline集合

3.4結(jié)果分析處理程序?qū)S進(jìn)行Skyline查詢處理，即，判斷NS中的每個(gè)數(shù)據(jù)對(duì)象N_DO與NS中所有其他數(shù)據(jù)對(duì)象之間的控制關(guān)系，如果N_DO不被NS中任意一個(gè)其他數(shù)據(jù)對(duì)象所控制，那么將N_DO放入?yún)f(xié)調(diào)節(jié)點(diǎn)的Skyline集合GS中，即，GS＝GS+{N_DO}；

3.5結(jié)果分析處理程序?qū)kyline集合GS返回給用戶。