一種流程模型結構解析算法RPST

肖蓓 喻學軍

(福建師范大學數學與信息學院,福建福州 350007)

0 引言

實際應用中,公司廣泛使用業務流程建模來記錄其操作過程,業務分析師通過將業務場景分解為業務活動并定義其邏輯和時間依賴關系來開發流程模型。這些模型用于協調、分析、優化和支持單個業務案例在公司內部或跨公司的執行[1]。業務流程的控制流通常可以建模為工作流圖,工作流圖是一種有向圖,其中節點(nodes)表示活動或控制決策,邊(edges)指定時間依賴關系。工作流圖捕獲了業務流程語言的核心,如U M L 活動圖、B P M N 和E P C s。B P M N(Business Process Modelling Notation)是一種面向圖形的建模語言,在這種語言中,動作節點和控制節點幾乎可以進行任意連接,它被各種建模工具支持但目前還沒有系統能夠直接執行BPMN模型[2]。因此我們需要對其進行轉化,如將基于圖的語言(即BPMN)建模的流程轉換為以基于塊的語言(如BPEL)建模的流程。因此,需要對工作流圖的解析問題進行研究。

一個工作流圖可以被解析為一個具有單個入口和單個出口的子圖的層次結構。這樣的子圖是邏輯上獨立的子工作流或業務流程的子流程。解析過程的結果是一棵解析樹,具有多種應用,如流程語言之間的轉換、控制流和數據流分析、流程比較和合并、流程抽象、流程綜合、模型布局、流程建模中的模式應用[1]。

1 RPST介紹

精細過程結構樹(Refined Process Structure Tree)是一種工作流圖解析技術,它生成的解析樹是唯一的,并且是模塊化的,它比任何已知的替代方法都更細粒度,且可以在線性時間內計算[3]。如圖1所示:

圖1 (a)一個TTG 及其片段劃分 (b)相應的RPST

1.1 片段(fragment)

首先我們對圖論的概念進行一些回顧, 多重圖(multi-graph)即圖1中(a)任意兩個節點可以被多條邊所連接,可被形式化的定義為一個三元組G=(V,E,M),其中V是節點集,E是邊集,M表示一種映射,它為每條邊分配一對有序或無序的節點。TTG(two-terminal graph)是一個沒有自環(self-loop)的有向圖G,它有唯一的源節點s及匯聚節點t(s≠t),且任意節點v都被包含在從s到t的有向路徑上。對于邊的子集,VF表示與F中某條邊相關的節點集,GF表示包含節點FV和邊F的子圖。假設G為一個TTG,F是其邊的子集,使得GF是G的連通子圖。當節點v∈VF為G的源節點或匯聚節點時;或事件v連接了邊e及邊e’,G包含邊e∈F且e?F’時,v為F的邊界節點。當v所有出度的邊都包含于F且入度的邊都不包含于F時,v為F的入口邊界節點;當v所有入度的邊都包含于F且出度的邊都不包含與F時,v為F的出口邊界節點。如果F恰好有兩個邊界節點,一個入口和一個出口,則稱F為G的一個片段。

1.2 三連通組件(triconnedted component)

TTG的片段與其三連通組件密切相關,因此我們對三連通組件做一些簡單介紹。給定一個T T G,表示為C(G),忽略G中所有邊的方向并在源節點和匯聚節點之間額外連接一條邊,可得到一個無向圖,其中,附加邊稱為C(G)的返回邊。假定G為無向多重圖(undirected multigraph),如果每對節點都可通過一條路徑連接,則G是連通的;如果G沒有自環且對任意三個節點u、v、x,都存在由u到達v且不經過x的路徑,則稱G是重連通的;如果對任意四個節點u、v、x、y,都存在由u到達v且不經過x、y的路徑,則G為三連通的。

1.3 算法

接下來對RPST的算法進行展示:

表1 RPST 算法表

圖2 BPMN 流程圖

圖3 解析后圖形化的RPST

生成樹的過程中,我們需要刪除一些冗余片段來對其進行清理(如表1)。因此,冗余片段的唯一子片段成為其父片段的子片段,如果冗余片段沒有父片段,則成為樹的根。

2 實驗

2.1 RPST的改進

實際運行的流程在執行網關判斷時往往需要讀取數據,而當前的R P S T 樹無法將判斷條件進行展示;在由RPST提取相應的業務流程規則時(business rule),還應當保證同一層級的節點依照BPMN中的執行順序進行展示,因此我們對RPST進行改進。

2.2 實現

給定一個包含Loop及網關判定條件的BPMN流程圖(如圖2),通過解析生成相應的RPST(如圖3)。實驗環境為:eclipse IDE(2020-06)。運行環境為:64位Win7操作系統、8G內存、i5-6500的臺式機。

3 結語

在本文中,介紹了RPST的概念及算法,并通過實驗驗證了改進后的RPST算法在處理復雜流程圖方面具有較好的性能。