雲計算環境下面向不確定數據源的工作流視圖構造方法
2023-09-17 14:10:10 1
專利名稱：雲計算環境下面向不確定數據源的工作流視圖構造方法
技術領域：
本發明屬於科學工作流技術領域，涉及一種面向科學工作流不確定數據源的視圖構造方法。
背景技術：
近年來，隨著計算機網絡技術飛速發展，作為新型網際網路的後端支撐基礎雲計算技術已開始逐步走向人類社會生活。科學工作流是一類典型的面向海量密集型數據流、以減少計算成本為目標的應用系統，它的出現為跨多類學科和跨不同地域的科研合作提供了方便。在科學工作流系統中，海量數據密集型計算與分布式資源共享彼此間協作、無隙地進行，使得具有不同領域專業知識、地理位置分布的科研工作者可跨組織合作完成相關的科學實驗。科學工作流系統現已在各國的科研院所展開應用，並在生物信息學、社會關係分析、氣象學、物理學等多個領域都發揮了應有的作用。在雲計算環境下進行科學工作流運行 時，將產生大量的中間數據和結果，對這些數據進行管理與分析有助於科研工作者對複雜、多步驟的科學實驗進行描述和分析。為了保證實驗結果的可重複性與可驗證性，許多科學工作流系統都提供了對數據源的支持。由於複雜、大規模的科學工作流系統在運行過程中將產生大量的數據源。如何對這些海量的數據源進行有效地查詢與管理現已成為科研工作者研究的重要問題之一，目前許多研究工作針對此方面展開，它們通過構造數據源視圖的方式來分析數據源，從而達到縮減數據源圖的規模和計算複雜度的目的。在數據源視圖中，科學工作流中的任務依據數據流關係，被抽象成高階的複合任務，從而達到隱藏不相關的源數據細節、降低數據源圖規模的目的，同時在視圖級進行數據查詢將有效地提高查詢效率。然而由於受數據採集的準確度和伺服器的可靠性影響，當對數據源進行數據集成時，工作流數據的不確定性現象將會產生。一般說來，這樣的數據不確定性現象可用概率的形式加以量化；在此基礎上，不確定科學工作流中的數據源可被定義成活動執行的概率圖形式。目前在科學工作流視圖構建技術方面的研究尚未深入，現有工作則主要集中在確定式數據源圖方面；而面向不確定式數據源視圖的合理性檢驗與構建技術方面的相關研究工作還有待進一步開展。因此本發明針對此方面進行研究，提出了在不確定數據源圖中檢測視圖合理性的方法，並進一步基於任務間的數據流和局部期望支持度給出了構建不確定式視圖的方法。本發明方法的具體步驟是
步驟(I)讀取科學工作流的數據源圖信息，包括數據源圖中任務節點集、任務節點間的數據流邊的集合和數據流邊的存在概率。步驟(2)將整個數據源圖視為一個完整的工作流視圖，檢測它的合理性，包括 ①根據數據源圖中的每條輸入數據流必須能夠到達該數據源圖的所有輸出任務節點
這一原則，來檢測數據源圖的合理性。②數據源圖中的相鄰任務節點在滿足條件①的情況下能否合併為一個新的複合任務、且新的複合任務存在概率是否小於未合併之前各任務節點的存在概率，如果合併後的新複合任務存在概率大於合併之前各任務節點的存在概率，則認為原來的數據源圖具有不合理性。若數據源圖具有合理性，則整個數據源圖被視為一個完整的工作流視圖。步驟(3)若步驟(2)中整個數據源圖將作為一個工作流視圖被檢測為不合理的，則按照以下兩種情況重新構造該數據源圖的合理性視圖
i)若數據源圖因為不符合步驟(2)中的條件①，則對該數據源圖按照步驟(4)進行拆分重構，從數據源圖裡面重新構造出合理性的視圖。ii)若數據源圖不符合步驟(2)中的條件②，則找出數據源圖中存在那些相鄰任務節點這些相鄰任務節點在滿足條件①的情況下能合併為一個新的複合任務、且新複合任務存在概率大於未合併之前各任務節點的存在概率，並將這些相鄰的任務節點進行合併。 步驟(4)對數據源圖進行拆分與重構時，按照如下情形處理
情形I、對某一任務節點，若它有且僅有一個相鄰的前序節點，且該任務節點與該前序節點合併後生成的複合任務的概率期望支持度大於該任務節點及前序節點的概率期望支持度，則該任務節點與其前序節點可以合併為合理的複合任務節點。情形2、若對於某一任務節點，若它僅有一個相鄰的後續節點，且該任務節點與其後續節點合併後生成的複合任務的概率期望支持度大於該任務節點及前序節點的概率期望支持度，則該任務節點可與其後續節點合併為合理的複合任務。情形3、若某一任務節點有多個相鄰前序節點，若這些前序節點中存在著某個任務節點，使得從其它前序節點出發的數據流邊都能到達該前序任務節點，並且從該前序任務節點出發的、所有沒有指向該任務節點的數據流邊的概率和小於用戶給定的經驗閾值，則可對從該前序任務節點出發的、所有沒有指向該任務節點的數據流邊進行嘗試性刪除，並將這些前序節點與該任務節點進行嘗試性合併，如果合併之後的複合任務的概率期望支持度大於合併前各任務節點的概率期望支持度，則這樣的合併是可行的，且合併生成的複合任務是合理的。情形4、若數據源圖中某幾個任務節點具有相同的相鄰前序任務集，且這些前序任務節點中的每一個節點同時所具有相同的相鄰後續任務集，此外若這些任務節點與它們的前序任務集合併後生成的複合任務的概率期望支持度大於合併前的這些任務節點各自的概率期望支持度，則這些任務節點與它們的相鄰前序任務節點可以合併為一個合理的複合任務。步驟(5)重複步驟(3)對數據源圖中的任務節點進行合併與重構，直到數據源圖中無法再進行任務節點之間的合併為止，則數據源圖中最終存在的任務節點和複合任務節點將構成該數據源圖的合理性視圖。本發明所提供的雲計算環境下面向不確定數據源的工作流視圖構造方法由一組功能模塊組成，它們包括數據源圖信息讀入模塊、視圖遍歷檢測模塊和不合理視圖拆分重構模塊。數據源圖信息讀入模塊讀入科學工作流不確定數據源圖視圖的詳細信息。包括數據源圖的節點數目，邊的數目，節點與節點、節點與邊之間的關係，邊的存在概率。視圖所包含的節點以及邊。
視圖遍歷檢測模塊將對輸入的數據源圖進行檢測，首先將整個數據源圖視為一個完整的視圖，依據數據源圖的輸入數據流必須到達數據源圖的所有輸出任務節點，並對數據源圖中的任務節點的概率期望支持度進行檢測。若檢測出是不合理的，則數據源圖作為下一個模塊的輸入。不合理數據源圖拆分重構模塊對輸入的數據源圖進行拆分重構。本模塊首先對輸入的數據源圖進行遍歷，統計該數據源圖的輸入節點和輸出接點，並分別存放於輸入節點集合和輸出節點集合中，從輸出節點中的某一任務節點開始，依次遍歷該節點的前序節點，如果符合合併規則就將該節點與其前序合併為一個複合任務，直至遍歷到輸入節點集合中的節點，按照此方法依次遍歷輸出節點集合中剩餘的複合任務。與傳統方法相比，本發明所提供的檢測方法不僅考慮到了確定數據源圖中視圖的合理性，更是結合了視圖存在的期望支持度來檢測是否可以將多個任務合併為期望支持度更大的複合任務。··在不合理視圖檢測環節對實際科學工作流數據源圖做出直接映射，考慮了實際情景中可能出現的各種情況。在對不合理視圖拆分重構過程中總結了四種不同的合併規則，對於減少合理視圖數目具有很重要的作用。
具體實施例方式 相關概念及符號說明
G ={VG, Eg, hg, Li):不確定數據源 Vg :不確定數據源圖中節點集合；
Eg :不確定數據源圖中邊的集合
G :不確定數據源圖中邊的概率集合；
Lq :不確定數據源圖中節點Vg、Eg的標籤；
K:不確定數據源圖中的視 複合任務；
Hpiyi, I):複合任務Z7中的節點Vj.的一階前序；
Qpiyi, I):複合任務/7中的節點~的一階後序；
V :普通節點；
Set (κ):節點的集合；
本發明可用於雲計算環境下處理不確定數據源圖視圖的檢測以及重構，主要可分為兩大功能視圖的檢測和不合理視圖的重構。(I)假設輸入的不確定數據源圖為G ={匕，&，\，&}，匕為圖中節點集合，&為圖中邊的集合，\為邊的概率集合，4則定義了圖中節點匕、私的標籤。圖G的視圖將
圖劃分為若干個互不相交的區域，每一個區域被稱為一個視圖或複合任務。圖G的子圖是圖G的部分邊和節點集合，我們可以通過邊的存在概率計算出子圖在圖^中的存在概率。(2)對於輸入的不確定數據源圖^視圖遍歷檢測模塊首先檢測整個數據源圖作為一個完整的視圖是否具有合理性，其檢測依據是視圖的所有的輸入數據流邊都能到達該視圖的所有輸出任務節點。如果數據源圖中的任務節點能滿足上述條件，則嘗試將數據源圖中某些任務節點與其相鄰的任務節點依照上述條件合併為一個複合任務，若合併後的複合任務的期望支持度大於合併前各任務節點的概率期望支持度，則由該數據源圖所構成視圖具有不合理性。(3)若數據源圖所構成視圖G被檢測出是不合理的，則查找出其輸入節點集合和輸出節點集。計算輸出節點集合中的每一個任務節點的前序，按照節點前序數目從多到少進行排序。從輸出節點集合中的某一個任務節點開始，依次尋找具有公共前序的任務節點，如果存在具有公共前序的節點集，則按照合併規則4 (見下文)進行合併，否則順次對輸出節點集合中的任務節點進行前序遍歷。對於輸出節點集合中的某一任務節點的前序節點，按照該任務節點與前序節點的輸入輸出邊的關係以及邊的概率，可分為三種情況進行處理，具體的情況以及處理方式可參考下文的規則1、2、3。若符合合併規則就將該任務節點與其前序合併為一個複合任務，直至遍歷到輸入節點集合中的所有節點為止。(4)重複步驟(3)按照此方法依次遍歷數據源圖中剩餘的任務與複合任務，直到無 法再進行任務節點間的合併為止；數據源圖中所有的任務與複合任務將構成該數據源圖的合理性視圖。合併規則的說明
規則I:若對於某一任務節點八其一階前序節點有且僅有一個節點K，且該任務節點Z7與其前序節點K合併後的期望支持度大於該任務節點的期望支持度，則該任務節點與其前序節點可以合併為合理的複合任務。規則2 :若對於某一任務節點八其一階後續節點r有且僅有一個節點，且該任務節點產與其一階後續節點r合併後的期望支持度大於該任務節點的期望支持度，則該複合任務與其一階後續節點可以合併為合理的複合任務。規則3 :假定某一任務節點/7的一階前序為節點的集合盡(匕，I)，對於集合中的任意一點K，如果集合中的其他節點都能到達K，且r的所有沒有指向任務節點/7的邊的概率和小於用戶給定的經驗閾值，則對這些邊進行嘗試性刪除，並將集合盡(^，D合併到任務節點/7中，如果合併之後的複合任務的期望支持度大於合併之前各任務節點的概率期望支持度，則/7與盡(^，I)可以合併為合理的複合任務。規則4:若某一任務節點集合(κ)中的每一個節點都具有相同的一階前序Ui, 1)，且這些一階前序中的每一個節點同時具有相同的一階後續，且節點集(κ)與其一階前序D合併之後的複合任務的期望支持度大於合併前各任務節點的概率期望支持度，則節點集(幻和其一階前序Iifr; (6，I)可以合併為合理的複合任務。
權利要求
1.雲計算環境下面向不確定數據源的工作流視圖構造方法，其特徵在於該方法的具體步驟 步驟(I)讀取科學工作流的數據源圖信息，包括數據源圖中任務節點集、任務節點間的數據流邊的集合和數據流邊的存在概率； 步驟(2)將整個數據源圖視為一個完整的工作流視圖，檢測它的合理性，包括 ①根據數據源圖中的每條輸入數據流必須能夠到達該數據源圖的所有輸出任務節點這一原則，來檢測數據源圖的合理性； ②數據源圖中的相鄰任務節點在滿足條件①的情況下能否合併為一個新的複合任務、且新的複合任務存在概率是否小於未合併之前各任務節點的存在概率，如果合併後的新複合任務存在概率大於合併之前各任務節點的存在概率，則認為原來的數據源圖具有不合理性； 若數據源圖具有合理性，則整個數據源圖被視為一個完整的工作流視圖； 步驟(3)若步驟(2)中整個數據源圖將作為一個工作流視圖被檢測為不合理的，則按照以下兩種情況重新構造該數據源圖的合理性視圖 i)若數據源圖因為不符合步驟(2)中的條件①，則對該數據源圖按照步驟(4)進行拆分重構，從數據源圖裡面重新構造出合理性的視圖； )若數據源圖不符合步驟(2)中的條件②，則找出數據源圖中存在那些相鄰任務節點這些相鄰任務節點在滿足條件①的情況下能合併為一個新的複合任務、且新複合任務存在概率大於未合併之前各任務節點的存在概率，並將這些相鄰的任務節點進行合併；步驟(4)對數據源圖進行拆分與重構時，按照如下情形處理 情形I、對某一任務節點，若它有且僅有一個相鄰的前序節點，且該任務節點與該前序節點合併後生成的複合任務的概率期望支持度大於該任務節點及前序節點的概率期望支持度，則該任務節點與其前序節點可以合併為合理的複合任務節點； 情形2、若對於某一任務節點，若它僅有一個相鄰的後續節點，且該任務節點與其後續節點合併後生成的複合任務的概率期望支持度大於該任務節點及前序節點的概率期望支持度，則該任務節點可與其後續節點合併為合理的複合任務； 情形3、若某一任務節點有多個相鄰前序節點，若這些前序節點中存在著某個任務節點，使得從其它前序節點出發的數據流邊都能到達該前序任務節點，並且從該前序任務節點出發的、所有沒有指向該任務節點的數據流邊的概率和小於用戶給定的經驗閾值，則可對從該前序任務節點出發的、所有沒有指向該任務節點的數據流邊進行嘗試性刪除，並將這些前序節點與該任務節點進行嘗試性合併，如果合併之後的複合任務的概率期望支持度大於合併前各任務節點的概率期望支持度，則這樣的合併是可行的，且合併生成的複合任務是合理的； 情形4、若數據源圖中某幾個任務節點具有相同的相鄰前序任務集，且這些前序任務節點中的每一個節點同時所具有相同的相鄰後續任務集，此外若這些任務節點與它們的前序任務集合併後生成的複合任務的概率期望支持度大於合併前的這些任務節點各自的概率期望支持度，則這些任務節點與它們的相鄰前序任務節點可以合併為一個合理的複合任務; 步驟(5)重複步驟(3)對數據源圖中的任務節點進行合併與重構，直到數據源圖中無法再進行任務節點之間的合併為止，則數據源圖中最終存在的任務節點和複合任務節點將構成該數據 源圖的合理性視圖。
全文摘要
本發明公開了雲計算環境下面向不確定數據源的工作流視圖構造方法。本發明首先讀取科學工作流的數據源圖信息，並將整個數據源圖視為一個完整的工作流視圖，檢測它的合理性。然後對數據源圖進行拆分與重構時，按照四種情形處理。最後對數據源圖中的任務節點進行再次合併與重構，直到數據源圖中無法再進行任務節點之間的合併為止，則數據源圖中最終存在的任務節點和複合任務節點將構成該數據源圖的合理性視圖。本發明所提供的檢測方法不僅考慮到了確定數據源圖中視圖的合理性，更是結合了視圖存在的期望支持度來檢測是否可以將多個任務合併為期望支持度更大的複合任務。
文檔編號G06F17/30GK102902739SQ20121033769
公開日2013年1月30日 申請日期2012年9月13日 優先權日2012年9月13日
發明者胡海洋, 劉佔晨 申請人:杭州電子科技大學