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

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

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