基于庫(kù)所系統(tǒng)的增加類型變化傳播分析

彭珂

摘要：變化傳播在許多軟件領(lǐng)域都起著必不可少的重要作用，分析基于某種變化類型的傳播范圍更是一個(gè)難以忽視的問(wèn)題。文中提出一種基于Petri網(wǎng)的庫(kù)所系統(tǒng)，依據(jù)單向影響關(guān)系，分析添加增加類型變遷的變化傳播范圍的方法。首先，以某打車軟件為例，建立打車軟件客戶端的庫(kù)所系統(tǒng)，并插入一個(gè)增加類型的變化變遷。其次，利用單向影響關(guān)系，衡量庫(kù)所系統(tǒng)原變遷集與所添加的增加類型變遷之間的影響關(guān)系。最后，根據(jù)增加類型變化傳播影響范圍公式，得出基于打車軟件的庫(kù)所系統(tǒng)，添加一個(gè)增加類型變化的傳播影響范圍。

關(guān)鍵詞：Petri網(wǎng)；庫(kù)所系統(tǒng)；增加類型；單向影響關(guān)系；變化傳播

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1009-3044（2018）02-0211-02

Change Propagation Analysis of the Add Type Based on the Place System

PENG Ke

（College of Mathematics and Big Data， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： Change propagation plays an important role in many software fields. It is a difficult problem to analyze the change propagation range of some type of change. This paper presents a method of analyzing the change propagation influence range， which inserting a transition of add type into a place system Based on Petri net on a basis of unidirectional influence relationship. Firstly， take a taxi software as an example， build a place system for car-hailing software， and then insert a change transition of add type into the system. Secondly， the influence relationship between the original change set of the system and the inserted transition of add type， which is measured by the unidirectional influence relationship method. Finally， according to the formula of change propagation influence range of a transition of the above inserted add type， it is concluded that the change propagation influence range of an inserted transition of add type Based on the place system of a car-hailing software.

Key words： Petri net； place system； add type； unidirectional influence relationship； change propagation

1 背景

現(xiàn)今，變化傳播分析是業(yè)務(wù)流程管理中的一個(gè)重要方面。而在不斷變化的業(yè)務(wù)環(huán)境下，依據(jù)變化類型，量化變化傳播范圍則一直屬于比較繁瑣又很困難的一類問(wèn)題。因?yàn)樽兓愋头譃楹脦追N，每種不同的變化在流程中生成或添加后，都會(huì)由于漣漪效應(yīng)的多樣性而形成各種截然不同的新流程。故從變化傳播范圍角度分析變化傳播是一項(xiàng)刻不容緩的重任。

目前，關(guān)于變化類型和變化傳播已有許多研究。文獻(xiàn)[1]闡述了變化區(qū)域和變化傳播的概念，并對(duì)它們之間的關(guān)系進(jìn)行了簡(jiǎn)單的介紹。文獻(xiàn)[2]從變化分類角度來(lái)動(dòng)態(tài)評(píng)估變化區(qū)域?qū)φ麄€(gè)流程系統(tǒng)的影響。文獻(xiàn)[3]提出了一種基于流程結(jié)構(gòu)樹通用的分散式變化傳播方法，它同樣也是根據(jù)變化種類促使變化傳播持續(xù)使能發(fā)生。文獻(xiàn)[4]解決了利益相關(guān)者在業(yè)務(wù)流程中因通過(guò)不同視角執(zhí)行變化而導(dǎo)致的不一致現(xiàn)象。文獻(xiàn)[5]則是在Petri網(wǎng)的庫(kù)所系統(tǒng)中，基于置信度要求變量來(lái)分析并鞏固變化傳播并給出由內(nèi)部可信賴屬性生成的影響范圍。

本文的整體結(jié)構(gòu)如下：第一部分介紹文中所涉及的相關(guān)基本概念；第二部分為基于庫(kù)所系統(tǒng)的增加變化類型變化傳播范圍分析；第三部分則是總結(jié)本文的貢獻(xiàn)以及未來(lái)工作的結(jié)束語(yǔ)。

2 基本概念

這一部分主要介紹了與本文密切相關(guān)的概念，其他相關(guān)定義可參見文獻(xiàn)[6]。

定義1[6]（Petri網(wǎng)）滿足下列三個(gè)條件的三元組[N=（P，T；F）]稱作Petri網(wǎng)：

1） [P]是一個(gè)有限非空庫(kù)所集，[T]是一個(gè)有限非空變遷集；

2） [P?T≠?]，[P?T=?]；

3） [F=（P×T）?（T×P）]表示流關(guān)系。

Petri網(wǎng)三元組包括庫(kù)所[P]、變遷[T]、流關(guān)系[F]。用圖形表示Petri網(wǎng)時(shí)，以圓圈表示庫(kù)所，矩形表示變遷。對(duì)于任意[x，y∈P×T]，若[x，y∈F]即[x]到[y]有一個(gè)流關(guān)系，則活動(dòng)對(duì)之間用一個(gè)有向線段表示。為計(jì)算變化傳播范圍，下面介紹庫(kù)所系統(tǒng)。endprint

定義2[7]（庫(kù)所系統(tǒng)）六元組[Σ=S，T；F，K，W，M]是一個(gè)庫(kù)所系統(tǒng)（Place System），其中

1） [（S，T；F）]是一個(gè)網(wǎng)；

2） [W：F→{1，2，3，...}]成為權(quán)函數(shù)；

3） [K：S→{1，2，3，...}]成為容量函數(shù)；

4） [M：S→{1，2，3，...}]是[Σ]的一個(gè)標(biāo)識(shí)，滿足條件[?s∈S：M（s）≤K（s）]

用一個(gè)庫(kù)所系統(tǒng)[PS]對(duì)一個(gè)系統(tǒng)建模時(shí)，五元組[S，T；F，K，W]描述系統(tǒng)的結(jié)構(gòu)，標(biāo)識(shí)[M]反應(yīng)系統(tǒng)的狀態(tài)，此五元組也成為庫(kù)所系統(tǒng)的基網(wǎng)。

定義3[3]（增加類型變化）

[AddChangePattern：]= [Add（Fragment，pred，succ）]

變化類型共有大概四種，本文分散式計(jì)算中將會(huì)用到的就是定義3增加類型變化，它是通過(guò)在流程前承結(jié)點(diǎn)[pred]與后繼結(jié)點(diǎn)[succ]之間插入一個(gè)新的變遷實(shí)現(xiàn)的。

3 基于庫(kù)所系統(tǒng)的增加變化類型變化傳播范圍分析

當(dāng)前，越來(lái)越多的市民和私家車踏入了某打車軟件這一領(lǐng)域，這些打車軟件使得閑置的私家車有了一番用武之地，司機(jī)也能掙得不少的外快。市民則因其便捷性和快捷性而更青睞于這一與出租車不同的打車方式。本文就以某打車軟件和乘客的交互行為為例子，建立庫(kù)所系統(tǒng)，以庫(kù)所系統(tǒng)為基礎(chǔ)，插入一個(gè)增加類型的變化變遷，并通過(guò)分析前驅(qū)后繼變遷集影響關(guān)系來(lái)計(jì)算影響范圍。圖1即為定義3所描述的增加類型變化，是圖2中變遷[t′]的變化類型。

[T={t2：使用此軟件；t7：新用戶驗(yàn)證；t8：老用戶默認(rèn)登錄；t15：所定位位置為初始位置；t16：自選位置；t17：到達(dá)位置為目的地；t18：現(xiàn)在叫車；t19：預(yù)約叫車；t22：搶單；t23：收到車輛信息；t28：車主電話聯(lián)系；t31：上車；t34：發(fā)送行車路線；t35：發(fā)送乘車金額；t38：無(wú)優(yōu)惠券；t39：有優(yōu)惠券；t40：付款}] 圖2中所增加的變化[t′={ 決定不坐車}]

為計(jì)算庫(kù)所系統(tǒng)的變化傳播范圍，本文將以衡量庫(kù)所系統(tǒng)原變遷集與所插入的增加類型變遷之間的影響關(guān)系為基礎(chǔ)。下面將介紹單向影響關(guān)系[5][M=（mt（i，j））]，

[mt（i，j）=1，ti與tj之間存在單向影響關(guān)系0，ti與tj之間不存在單向影響關(guān)系，1≤i，j≤n]

庫(kù)所系統(tǒng)由此影響關(guān)系得到添加一個(gè)增加變化后，包含此變化及其前驅(qū)變遷的影響關(guān)系矩陣[M1]和包含此變化及其后繼變化的影響關(guān)系矩陣[M2]，矩陣中的元素均由單向影響關(guān)系[M=（mt（i，j））]所組成。

增加一個(gè)變化[t′]后，包含此變化及其前驅(qū)變遷的影響關(guān)系矩陣為

增加類型變化傳播影響范圍的公式[8]為：

[CPIRA=M11M10，1+M21M2（0，1）×100%]，

其中[M1]和[M0，1]分別表示矩陣中的元素1以及元素0、1，而[M]則表示矩陣所包含元素個(gè)數(shù)。這個(gè)公式的意義就是根據(jù)計(jì)算前驅(qū)矩陣[M1]和后繼矩陣[M2]中，含1即存在單向影響關(guān)系的數(shù)量占含0，1總數(shù)的比例之和的百分比，來(lái)展示增加類型變化在庫(kù)所網(wǎng)中傳播的影響范圍。

由上述公式可以得到，本文基于庫(kù)所系統(tǒng)插入一個(gè)增加類型變化的傳播影響范圍是：

[CPIRA=40961+22144×100%=19.4%]

4 結(jié)束語(yǔ)

盡管過(guò)去的研究在包括軟件領(lǐng)域等企業(yè)管理范圍內(nèi)各個(gè)方面的變化傳播分析都有所涉獵，卻很少考慮到從每個(gè)變化類型分散式的一一計(jì)算這些變化所傳播的范圍，本文則從增加類型變化彌補(bǔ)了一部分的短板。本文將乘客在使用某打車軟件時(shí)的交互行為來(lái)建立庫(kù)所系統(tǒng)，同時(shí)在其中添加一個(gè)增加類型的變化變遷。之后引入單向影響關(guān)系，用以衡量庫(kù)所系統(tǒng)原變遷集與所插入的增加類型變遷之間的影響關(guān)系。隨之得出由單向影響關(guān)系組成的，包含此增加類型變化的前驅(qū)矩陣和后繼矩陣。最后，再依據(jù)增加類型變化傳播影響范圍的公式計(jì)算得到本文基于庫(kù)所系統(tǒng)插入一個(gè)增加類型變化的傳播影響范圍。在此研究的基礎(chǔ)上，未來(lái)工作將從兩方面展開：試用本文中的方法計(jì)算基于其他變化類型的變化傳播范圍；以運(yùn)行時(shí)間，運(yùn)行良好程度等方面來(lái)檢驗(yàn)此法的優(yōu)劣之處，揚(yáng)長(zhǎng)避短，發(fā)揮優(yōu)勢(shì)并改正缺陷。

參考文獻(xiàn)：

[1] Demuth A， Riel-Ehrenleitner M. Co-evolution of Metamodels and Models through Consistent Change Propagation[J]. The Journal of Systems and Software， 2016， 111： 281-297.

[2] Gupta C， Singh Y， Singh D. A Dynamic Approach to Estimate Change Impact using Type of Change Propagation[J]. Journal of Information Processing Systems， 2010， 4（6）：597-608.

[3] Fdhila W， Indiono C， Rechert M. Dealing with Change in Process Choreographies： Design and Implementation of Propagation Algorithms[J]. Information Systems， 2015， 9（5）：55-106.

[4] Grossmann G， Mafazi S. Change Propagation and Conflict Resolution for the Co-Evolution of Business Processes[J]. International Journal of Cooperative Information Systems， 2015， 12（8）：102-140.

[5] Chen Y， Cheng P， Yin J. Change Propagation Analysis of Trustworthy Requirements Based on Dependency Relations[J]. 2010 IEEE International Conference on Information Management and Engineering， 246-251.

[6] Polyvyanyy A， Armas-Cervantes A， Marlon Dumas. On the expressive power of behavioral profiles[J]. Formal Aspects of Computing， 2016， 5（28）：597-599.

[7] 吳哲輝. Petri網(wǎng)導(dǎo)論[M]. 北京： 機(jī)械工業(yè)出版社， 2006： 9-15.

[8] Salay R， Gorzny J， Chechik M. Change Propagation due to Uncertainty Change[J]. Springer Verlag Berlin Heidelberg， 2013， 28（21）：21-36.endprint