基于事件平衡的工作流模型

基于事件平衡的工作流模型

自2008年以來，工作流技術(shù)在各個方面都取得了很大進(jìn)步和發(fā)展。它包括相對完整的工作流管理系統(tǒng)結(jié)構(gòu)、工作流模型和定義語言、工作流實現(xiàn)技術(shù)、工作流模擬分析、工作流特征、工作流整合和相執(zhí)行技術(shù)等。目前，這些工作流管理系統(tǒng)的普遍布局之一是缺乏有效的方法和工具來確保工作流的合理性。許多工作流管理系統(tǒng)允許建立錯誤控制邏輯的工作流模型，而執(zhí)行流模型是否存在任何異常情況。造成這種缺陷的原因有兩個主要原因。(1)工作流本身缺乏堅實的理論基礎(chǔ),許多模型的建立是基于直觀理解,沒有嚴(yán)格的形式化定義與約束,因而在驗證問題上也就沒有成熟的理論可以依據(jù);而且,由于不同的工作流系統(tǒng)之間可能存在很大差別,所以,很難有一種統(tǒng)一的驗證方法可以適用于所有類型的工作流模型.(2)工作流本身的復(fù)雜性使得對于它的驗證問題變得難以解決.在有關(guān)工作流性質(zhì)驗證的可計算性與復(fù)雜性的研究中[2~4],人們得出的一個普遍認(rèn)同的結(jié)論是:如果不對模型結(jié)構(gòu)加以限制,則對于任意工作流的性質(zhì)驗證問題將會是NP完全甚至是不可判定的.文獻(xiàn)指出,在工作流模型的表達(dá)能力與該工作流模型合理性驗證問題的復(fù)雜性之間存在著一種平衡(trade-off),模型的表達(dá)能力越強,相應(yīng)的合理性驗證問題就越復(fù)雜,一些驗證問題是難解的,甚至是不可確定的.對于已有的一些模型,研究人員給出了相應(yīng)的驗證方法,如文獻(xiàn)分別提出了基于Petri網(wǎng)與CTR(concurrenttransactionlogic)的分析方法,文獻(xiàn)則通過一些限制提出了一種可在多項式時間內(nèi)進(jìn)行終止驗證的模型結(jié)構(gòu).這些方法都是基于具體的工作流模型,而且這些模型都不同程度地帶有表達(dá)上的局限性,通常是對實際流程的一種簡化,因而適用的場合很有限.本文將提出一種與模型無關(guān)的工作流合理性的分析方法——事件平衡分析方法,這種方法從工作流執(zhí)行歷史的角度出發(fā),基于工作流對象發(fā)生的前因與后果,提出工作流合理性的必要條件——事件平衡定理,并給出證明.進(jìn)一步地,將事件平衡分析方法引入工作流模型,用于對模型結(jié)構(gòu)進(jìn)行判斷與分析.1工作流模型的結(jié)構(gòu)工作流執(zhí)行歷史是指一個工作流實例從開始到結(jié)束所經(jīng)歷的軌跡.無論工作流是采用怎樣的模型來進(jìn)行描述,工作流執(zhí)行歷史都具有相同的結(jié)構(gòu),即一系列對等工作流對象的偏序集合.“對等”是指集合中的元素在概念上屬于同一類型;“偏序”是指集合中的不同元素按照一定的順序進(jìn)行排列,在這里是基于時間的先后;“工作流對象”則取決于具體的工作流模型,它們可能是事件、任務(wù)、操作等,但無論是何種對象,都不影響我們在下文中分析所得的結(jié)果,因此,我們以“事件”為代表來進(jìn)行討論.我們稱一個工作流是合理的,當(dāng)且僅當(dāng)它所有可能的執(zhí)行歷史H都滿足:(1)在H中僅有一個工作流的初始事件和一個工作流的結(jié)束事件;(2)工作流的初始事件最先發(fā)生,即e∈IEwf,e?H(t)??t′≤t,h(t′)=?;(3)工作流的結(jié)束事件最后發(fā)生,即e∈TEwf,e∈H(t)??t′>t,H(t′)=H(t).直觀地理解,合理的工作流要求它的每一次執(zhí)行都是以整個工作流的一個初始事件為開始,以整個工作流的一個結(jié)束事件為終止.在這個初始事件發(fā)生前,任何其他事件都不允許發(fā)生,即所有的活動、任務(wù)或者操作都處于未執(zhí)行狀態(tài);在這個結(jié)束事件發(fā)生后,任何事件都不可能發(fā)生,即不存在正處于進(jìn)行中的活動、任務(wù)或者操作.與其他文獻(xiàn)中提出的有關(guān)工作流合理性方面的要求有所不同,我們所提出的工作流的合理性是從執(zhí)行歷史的角度來考慮的,而并未對模型本身的結(jié)構(gòu)及組成有任何明確的限制.只要一個工作流模型的所有可能的執(zhí)行歷史都滿足上述的要求,那么我們并不在意它具有怎樣的模型結(jié)構(gòu),這給了模型結(jié)構(gòu)以最大的自由度.從執(zhí)行歷史的角度來定義工作流的合理性要比從模型本身的角度來定義更為寬松一些.比如,工作流模型中可能存在有不可能發(fā)生的事件或任務(wù),但只要它不影響工作流的正常開始與結(jié)束,我們?nèi)苑Q它是合理的,只不過該模型在結(jié)構(gòu)上有些冗余,可以進(jìn)行一些優(yōu)化.基于執(zhí)行歷史來定義工作流合理性的另一個優(yōu)點就在于,工作流執(zhí)行歷史中工作流對象之間的關(guān)系具有簡單、直接的特點,這種關(guān)系是一種按時間偏序的“因果”關(guān)系,即某一對象出現(xiàn)在執(zhí)行歷史中的原因就在于執(zhí)行歷史中其他對象在此之前的發(fā)生;而且偏序集合中的所有元素都是惟一的、不重復(fù)的,即使是在模型中被表示為反復(fù)執(zhí)行的相同元素,在執(zhí)行歷史中也被認(rèn)為是不同元素而區(qū)別對待;出現(xiàn)在執(zhí)行歷史中的元素表示它已經(jīng)發(fā)生,這與模型中定義了某些可能因不滿足條件而不一定總發(fā)生的元素的情形相比要更為簡單,只要是出現(xiàn)在執(zhí)行歷史中的元素,則一定是滿足條件而發(fā)生的.執(zhí)行歷史所具備的這些特點為我們在下文中推導(dǎo)事件平衡定理奠定了基礎(chǔ).2工作流執(zhí)行歷史與事件平衡定理定義1.工作流執(zhí)行歷史中事件的關(guān)系是一種按時間偏序的“因果”關(guān)系,我們定義這種關(guān)系如下:→:EV×EV,EV為工作流執(zhí)行歷史H中的事件集合.e1→e2表示如果e1不出現(xiàn)在H中,則e2也必然不會發(fā)生;換言之,e1是e2發(fā)生的前提.容易證明,→關(guān)系本身是一個傳遞閉包.如果e1→e2,且不存在e′∈EV有e1→e′,e′→e2同時成立,我們則稱e1與e2構(gòu)成“直接因果”關(guān)系,e1為e2的“前因事件”,e2為e1的“后果事件”.在工作流的執(zhí)行歷史中,一個事件可能會有多個前因事件,即該事件需要在這些前因事件都發(fā)生之后才可以發(fā)生,比如模型中定義的事件同步;同樣,一個事件也可以有多個后果事件,即該事件的發(fā)生將導(dǎo)致多個后果事件的發(fā)生,比如模型定義中的事件并發(fā).對于一個合理的工作流,由前面的定義可知:工作流的初始事件沒有前因事件,而工作流的結(jié)束事件也沒有后果事件.除初始事件外,其他任意事件至少具有一個前因事件;除結(jié)束事件外,其他任意事件都可能具有后果事件;當(dāng)結(jié)束事件發(fā)生后,則所有事件都不可能存在后果事件.對于執(zhí)行歷史中的一個事件而言,它的前因事件數(shù)與后果事件數(shù)之間沒有確定的規(guī)律可循,前因事件數(shù)小于、等于或者大于后果事件數(shù)的情況都可能會發(fā)生,但對于執(zhí)行歷史中所有事件而言,這兩個數(shù)字之間則存在著一定的規(guī)律,這就是“事件平衡定理”.定理1(事件平衡定理).對于一個合理的工作流,在它的執(zhí)行歷史中,所有事件的前因事件數(shù)之和必然等于所有事件的后果事件數(shù)之和.也就是說,對于合理的工作流執(zhí)行歷史中的每個事件ei,i=1,2,…,n,如果它的前因事件數(shù)為Ni,后果事件數(shù)為Mi,則稱(-Ni+Mi)為ei的“事件平衡數(shù)”,記為Bi,則有證明:我們由工作流執(zhí)行歷史構(gòu)造一個有向圖G(V,E),其中V為所有節(jié)點的集合,E為連接于節(jié)點間的有向弧.構(gòu)造方法如下:(1)把工作流執(zhí)行歷史中的事件按照發(fā)生的先后順序由左向右依次排列,如果是同時發(fā)生,則在同一位置上下排列,使任意左側(cè)的事件都早于右側(cè)事件發(fā)生.排列完畢后,把每個事件映射成有向圖G中的節(jié)點v,從而構(gòu)成節(jié)點集合V.(2)在有“直接因果”關(guān)系的兩個節(jié)點(事件)之間,連接一個有向弧,方向是由左至右,也就是由前因事件到后果事件.這條連接弧直觀地表示出左側(cè)先發(fā)生的事件是右側(cè)后發(fā)生事件的“前因”,而右側(cè)后發(fā)生的事件是左側(cè)先發(fā)生事件的“后果”.如果某一事件有多個后果事件,則會有多條有向弧從這一節(jié)點出發(fā)(即輸出弧),分別指向各個后果事件;如果某一事件有多個前因事件,則會有多條有向弧指向這個節(jié)點(即輸入弧),這些有向弧分別來自那些需要先發(fā)生的前因事件.(3)由于存在著工作流執(zhí)行歷史中事件的惟一性、有序性,則按照前面兩個步驟構(gòu)造的有向圖G是一個無自環(huán)、無平行邊的簡單圖,而且無回路.所有的有向弧都是連接于G的不同節(jié)點間,我們用|E|表示圖G中有向弧的數(shù)量.因為Ni對應(yīng)于有向圖G是圖中每一節(jié)點的輸入弧的數(shù)量,所以N就是所有節(jié)點的輸入弧的總和,由上面的構(gòu)造過程,有N=|E|.同理,因為Mi對應(yīng)于有向圖G是圖中每一節(jié)點的輸出弧的數(shù)量,M就是所有節(jié)點的輸出弧的總和,由上面的構(gòu)造過程,有M=|E|;亦即N=M.￡圖1給出了一個有向圖G的示例,由圖1可知,e1為工作流的初始事件,e7為工作流的結(jié)束事件.3事件數(shù)的計算事件平衡定理可以看成是工作流合理性的一個必要條件,對于一個合理的工作流而言,它所有可能的執(zhí)行歷史必然滿足事件平衡定理;如果一個工作流的執(zhí)行歷史不滿足事件平衡定理,則該工作流必然為不合理的.從本質(zhì)上講,工作流的執(zhí)行歷史是由工作流模型中的控制流所決定的,一個工作流模型的控制流部分就是所有可能發(fā)生的該工作流執(zhí)行歷史的集合,因此,我們把相應(yīng)的事件平衡數(shù)的計算與分析引入到工作流模型中,從而在執(zhí)行前得出該工作流在事件平衡方面的有關(guān)結(jié)論,從模型層上保證合理工作流的事件平衡特性.但是,模型畢竟不能等同于執(zhí)行歷史.由于條件的設(shè)置,使得模型中引入了不確定性因素,條件是否滿足完全取決于執(zhí)行時的具體情況.也正是因為有這種不確定性因素的存在,才使模型集合了所有可能發(fā)生的執(zhí)行歷史.因此,在模型層對事件的“前因”、“后果”的計算分析要比已經(jīng)處于執(zhí)行歷史中的事件的分析困難得多.本節(jié)將給出一種基于條件發(fā)生概率來計算事件平衡數(shù)的方法.首先我們假設(shè)模型中不存在任何條件,即在完全確定的情況下分析事件平衡數(shù);然后再引入條件,分析不確定狀態(tài)下事件平衡數(shù)的計算.(1)模型中不出現(xiàn)任何條件在這種情況下,一個事件的后果事件數(shù)即為模型中它的后繼事件的總和,后繼事件包括由它直接產(chǎn)生的事件以及在與其他事件同步后而產(chǎn)生的事件.一個事件的前因事件數(shù)的計算要根據(jù)它與前趨事件的關(guān)系而定:如果任何一個前趨事件的發(fā)生都將直接產(chǎn)生該事件,我們稱這種關(guān)系為“異步激活”,則前因事件數(shù)只計為1;如果需要所有前趨事件同步后該事件才可發(fā)生,我們稱這種關(guān)系為“同步激活”,則前因事件數(shù)為所有需要同步的前趨事件數(shù)之和n.如果一個事件的前趨事件中既有異步關(guān)系又有同步關(guān)系,我們則可以通過引入中間的輔助事件來把這種復(fù)雜關(guān)系等價轉(zhuǎn)化為所有事件僅包含一種關(guān)系的情形,進(jìn)而再計算事件平衡數(shù).(2)模型中出現(xiàn)條件在這種情況下,一個事件的后果事件數(shù)即為模型中它可能產(chǎn)生的所有后繼事件之和,不論后繼事件的發(fā)生是否有條件,我們都把這些后繼事件計入該事件的后果事件數(shù)之中,這與在模型中不出現(xiàn)任何條件的情況下計算后果事件數(shù)的方法是完全相同的.對于前因事件數(shù)的計算,也需要按照與前趨事件的“同步”與“異步”關(guān)系而有所區(qū)別,我們先假設(shè)該事件有n個前趨事件{e1,e2,…,en},每個前趨事件與該事件之間的條件為Ci,i=1,2,…,n;Ci發(fā)生的概率為P(Ci).如果某一前趨事件ei與該事件間沒有條件設(shè)置,則可以認(rèn)為Ci=TRUE,P(Ci)=1.我們可以這樣理解上文的兩個計算公式:對于“異步”關(guān)系來說,如果一個前趨事件的條件不滿足時,則P(?Ci)=1,表示這個前趨事件的發(fā)生不會產(chǎn)生該事件,對于整個工作流的執(zhí)行而言,相當(dāng)于多消耗了一個事件,因此前因事件數(shù)應(yīng)該在原有基礎(chǔ)上加上P(?Ci);而對于“同步”關(guān)系來說,只要有一個前趨事件的條件不滿足,P(∪?Ci)=1,則該事件必然不能發(fā)生,對于整個工作流的執(zhí)行而言,也相當(dāng)于多消耗了一個事件,因此前因事件數(shù)應(yīng)該在原有基礎(chǔ)上加上P(∪?Ci).當(dāng)條件全部滿足時,則不論是“異步”關(guān)系還是“同步”關(guān)系,P(?Ci)=0,P(∪?Ci)=0,所得的前因事件數(shù)與無條件情況下的結(jié)果完全相同.實際上,孤立地計算一個事件的事件平衡數(shù)并沒有太大的意義,事件平衡定理是在多個事件的事件平衡數(shù)之間建立起一種相對的平衡關(guān)系,只要滿足這種關(guān)系,我們并不需要關(guān)心每一個具體的事件平衡數(shù)的含義.正如在模型中有條件設(shè)置的情況下,前因事件數(shù)的計算結(jié)果可能由于概率的出現(xiàn)而不是整數(shù),但這并不影響事件平衡關(guān)系的建立.下面我們將給出兩個例子,分別計算在互斥條件與非互斥條件的設(shè)置下所得到的事件平衡結(jié)果,從而說明條件設(shè)置得是否合理將對工作流的合理性產(chǎn)生影響.例1:條件選擇,如圖2(a)所示.e0發(fā)生后,如果滿足條件C1,則產(chǎn)生e1;如果滿足條件C2,則產(chǎn)生e2.e1,e2同后繼事件e3之間是異步關(guān)系,即只要e1,e2有一個發(fā)生,則e3發(fā)生.這是一個工作流的局部片段,e0到e3的事件平衡數(shù)分別計算如下:如果C1,C2是互斥條件,則P(?C1)+P(?C2)=1,所以有B=0,事件平衡.如果C1,C2是非互斥條件,則P(?C1)+P(?C2)不確定,所以有B不一定為0,事件平衡有可能被破壞,從而導(dǎo)致工作流不合理.直觀地理解,非互斥條件下,C1,C2有可能都不滿足,則e0無法產(chǎn)生后繼事件;反之,若C1,C2都得到滿足,則e1,e2將分別產(chǎn)生兩個e3的實例,這也可能導(dǎo)致工作流運行出錯.圖2條件選擇與反復(fù)的工作流示例例2:反復(fù)(即自環(huán)),如圖2(b)所示.當(dāng)e2發(fā)生后,如果條件C1滿足,則e1被再次激活、反復(fù)執(zhí)行;如果條件C2滿足,則e3被激活,自環(huán)結(jié)束.e1到e3的事件平衡數(shù)計算如下:與例1類似,如果C1,C2是互斥條件,則滿足事件平衡;否則,事件平衡可能被破壞.正常情況下,對于反復(fù)(自環(huán))的模型結(jié)構(gòu)都是設(shè)置互斥條件的,以保證自環(huán)能夠順利結(jié)束并激活后繼事件.4事件平衡分析方法的優(yōu)缺點工作流性質(zhì)的驗證問題至今還沒有很有效的解決方法.本文從一個比較獨特的角度推導(dǎo)了合理工作流的必要條件,提出工作流執(zhí)行歷史的事件平衡定理,并把事件平衡的計算引入工作流模型,用以分析模型中是否存在可能破壞工作流合理性的結(jié)構(gòu).事件平衡分析的方法具有如下優(yōu)點:(1)適用范圍