[發(fā)明專(zhuān)利]云計(jì)算環(huán)境下面向不確定數(shù)據(jù)源的工作流視圖構(gòu)造方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210337694.9
• 申請(qǐng)日: 2012-09-13
• 公開(kāi)（公告）號(hào): CN102902739A
• 公開(kāi)（公告）日: 2013-01-30
• 發(fā)明（設(shè)計(jì)）人: 胡海洋;劉占晨
• 申請(qǐng)（專(zhuān)利權(quán)）人: 杭州電子科技大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 杭州求是專(zhuān)利事務(wù)所有限公司 33200
• 代理人: 杜軍

技術(shù)領(lǐng)域

本發(fā)明屬于科學(xué)工作流技術(shù)領(lǐng)域，涉及一種面向科學(xué)工作流不確定數(shù)據(jù)源的視圖構(gòu)造方法。

背景技術(shù)

近年來(lái)，隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)飛速發(fā)展，作為新型互聯(lián)網(wǎng)的后端支撐基礎(chǔ)云計(jì)算技術(shù)已開(kāi)始逐步走向人類(lèi)社會(huì)生活?？茖W(xué)工作流是一類(lèi)典型的面向海量密集型數(shù)據(jù)流、以減少計(jì)算成本為目標(biāo)的應(yīng)用系統(tǒng)，它的出現(xiàn)為跨多類(lèi)學(xué)科和跨不同地域的科研合作提供了方便。在科學(xué)工作流系統(tǒng)中，海量數(shù)據(jù)密集型計(jì)算與分布式資源共享彼此間協(xié)作、無(wú)隙地進(jìn)行，使得具有不同領(lǐng)域?qū)I(yè)知識(shí)、地理位置分布的科研工作者可跨組織合作完成相關(guān)的科學(xué)實(shí)驗(yàn)。科學(xué)工作流系統(tǒng)現(xiàn)已在各國(guó)的科研院所展開(kāi)應(yīng)用，并在生物信息學(xué)、社會(huì)關(guān)系分析、氣象學(xué)、物理學(xué)等多個(gè)領(lǐng)域都發(fā)揮了應(yīng)有的作用。在云計(jì)算環(huán)境下進(jìn)行科學(xué)工作流運(yùn)行時(shí)，將產(chǎn)生大量的中間數(shù)據(jù)和結(jié)果，對(duì)這些數(shù)據(jù)進(jìn)行管理與分析有助于科研工作者對(duì)復(fù)雜、多步驟的科學(xué)實(shí)驗(yàn)進(jìn)行描述和分析。為了保證實(shí)驗(yàn)結(jié)果的可重復(fù)性與可驗(yàn)證性，許多科學(xué)工作流系統(tǒng)都提供了對(duì)數(shù)據(jù)源的支持。由于復(fù)雜、大規(guī)模的科學(xué)工作流系統(tǒng)在運(yùn)行過(guò)程中將產(chǎn)生大量的數(shù)據(jù)源。如何對(duì)這些海量的數(shù)據(jù)源進(jìn)行有效地查詢(xún)與管理現(xiàn)已成為科研工作者研究的重要問(wèn)題之一，目前許多研究工作針對(duì)此方面展開(kāi)，它們通過(guò)構(gòu)造數(shù)據(jù)源視圖的方式來(lái)分析數(shù)據(jù)源，從而達(dá)到縮減數(shù)據(jù)源圖的規(guī)模和計(jì)算復(fù)雜度的目的。在數(shù)據(jù)源視圖中，科學(xué)工作流中的任務(wù)依據(jù)數(shù)據(jù)流關(guān)系，被抽象成高階的復(fù)合任務(wù)，從而達(dá)到隱藏不相關(guān)的源數(shù)據(jù)細(xì)節(jié)、降低數(shù)據(jù)源圖規(guī)模的目的，同時(shí)在視圖級(jí)進(jìn)行數(shù)據(jù)查詢(xún)將有效地提高查詢(xún)效率。然而由于受數(shù)據(jù)采集的準(zhǔn)確度和服務(wù)器的可靠性影響，當(dāng)對(duì)數(shù)據(jù)源進(jìn)行數(shù)據(jù)集成時(shí)，工作流數(shù)據(jù)的不確定性現(xiàn)象將會(huì)產(chǎn)生。一般說(shuō)來(lái)，這樣的數(shù)據(jù)不確定性現(xiàn)象可用概率的形式加以量化；在此基礎(chǔ)上，不確定科學(xué)工作流中的數(shù)據(jù)源可被定義成活動(dòng)執(zhí)行的概率圖形式。

目前在科學(xué)工作流視圖構(gòu)建技術(shù)方面的研究尚未深入，現(xiàn)有工作則主要集中在確定式數(shù)據(jù)源圖方面；而面向不確定式數(shù)據(jù)源視圖的合理性檢驗(yàn)與構(gòu)建技術(shù)方面的相關(guān)研究工作還有待進(jìn)一步開(kāi)展。因此本發(fā)明針對(duì)此方面進(jìn)行研究，提出了在不確定數(shù)據(jù)源圖中檢測(cè)視圖合理性的方法，并進(jìn)一步基于任務(wù)間的數(shù)據(jù)流和局部期望支持度給出了構(gòu)建不確定式視圖的方法。

本發(fā)明方法的具體步驟是：

步驟（1）讀取科學(xué)工作流的數(shù)據(jù)源圖信息，包括數(shù)據(jù)源圖中任務(wù)節(jié)點(diǎn)集、任務(wù)節(jié)點(diǎn)間的數(shù)據(jù)流邊的集合和數(shù)據(jù)流邊的存在概率。?

步驟（2）將整個(gè)數(shù)據(jù)源圖視為一個(gè)完整的工作流視圖，檢測(cè)它的合理性，包括：

①根據(jù)數(shù)據(jù)源圖中的每條輸入數(shù)據(jù)流必須能夠到達(dá)該數(shù)據(jù)源圖的所有輸出任務(wù)節(jié)點(diǎn)這一原則，來(lái)檢測(cè)數(shù)據(jù)源圖的合理性。

②數(shù)據(jù)源圖中的相鄰任務(wù)節(jié)點(diǎn)在滿(mǎn)足條件①的情況下能否合并為一個(gè)新的復(fù)合任務(wù)、且新的復(fù)合任務(wù)存在概率是否小于未合并之前各任務(wù)節(jié)點(diǎn)的存在概率，如果合并后的新復(fù)合任務(wù)存在概率大于合并之前各任務(wù)節(jié)點(diǎn)的存在概率，則認(rèn)為原來(lái)的數(shù)據(jù)源圖具有不合理性。

若數(shù)據(jù)源圖具有合理性，則整個(gè)數(shù)據(jù)源圖被視為一個(gè)完整的工作流視圖。

步驟（3）?若步驟(2)中整個(gè)數(shù)據(jù)源圖將作為一個(gè)工作流視圖被檢測(cè)為不合理的，則按照以下兩種情況重新構(gòu)造該數(shù)據(jù)源圖的合理性視圖：

i)若數(shù)據(jù)源圖因?yàn)椴环喜襟E（2）中的條件①，則對(duì)該數(shù)據(jù)源圖按照步驟(4)進(jìn)行拆分重構(gòu)，從數(shù)據(jù)源圖里面重新構(gòu)造出合理性的視圖。

ii)若數(shù)據(jù)源圖不符合步驟（2）中的條件②，則找出數(shù)據(jù)源圖中存在那些相鄰任務(wù)節(jié)點(diǎn)：這些相鄰任務(wù)節(jié)點(diǎn)在滿(mǎn)足條件①的情況下能合并為一個(gè)新的復(fù)合任務(wù)、且新復(fù)合任務(wù)存在概率大于未合并之前各任務(wù)節(jié)點(diǎn)的存在概率，并將這些相鄰的任務(wù)節(jié)點(diǎn)進(jìn)行合并。

步驟(4)對(duì)數(shù)據(jù)源圖進(jìn)行拆分與重構(gòu)時(shí)，按照如下情形處理：

情形1、對(duì)某一任務(wù)節(jié)點(diǎn)，若它有且僅有一個(gè)相鄰的前序節(jié)點(diǎn)，且該任務(wù)節(jié)點(diǎn)與該前序節(jié)點(diǎn)合并后生成的復(fù)合任務(wù)的概率期望支持度大于該任務(wù)節(jié)點(diǎn)及前序節(jié)點(diǎn)的概率期望支持度，則該任務(wù)節(jié)點(diǎn)與其前序節(jié)點(diǎn)可以合并為合理的復(fù)合任務(wù)節(jié)點(diǎn)。

情形2、若對(duì)于某一任務(wù)節(jié)點(diǎn)，若它僅有一個(gè)相鄰的后續(xù)節(jié)點(diǎn)，且該任務(wù)節(jié)點(diǎn)與其后續(xù)節(jié)點(diǎn)合并后生成的復(fù)合任務(wù)的概率期望支持度大于該任務(wù)節(jié)點(diǎn)及前序節(jié)點(diǎn)的概率期望支持度，則該任務(wù)節(jié)點(diǎn)可與其后續(xù)節(jié)點(diǎn)合并為合理的復(fù)合任務(wù)。