關(guān)系數(shù)據(jù)庫(kù)中事件日志的緊鄰關(guān)系高效挖掘方法

高俊濤,劉 聰, 劉云峰

(1.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318；2.山東理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 淄博 255000)

1 問(wèn)題的提出

隨著信息技術(shù)的普及和發(fā)展，信息系統(tǒng)在為企業(yè)運(yùn)營(yíng)帶來(lái)高效和快捷的同時(shí)，也留存下大量寶貴的日志數(shù)據(jù)。流程挖掘技術(shù)通過(guò)分析隱含在事件日志中的流程信息來(lái)發(fā)現(xiàn)、監(jiān)控和改進(jìn)實(shí)際業(yè)務(wù)流程[1]。目前，大多數(shù)信息系統(tǒng)采用成熟的關(guān)系數(shù)據(jù)庫(kù)存儲(chǔ)事務(wù)數(shù)據(jù)，關(guān)系型數(shù)據(jù)成為事件日志的主要來(lái)源。傳統(tǒng)的流程挖掘工具采用MXML(mining extensible markup language)或XES(extensible event stream)格式的日志文件作為輸入數(shù)據(jù)。在每次執(zhí)行挖掘任務(wù)之前，需要根據(jù)具體問(wèn)題從數(shù)據(jù)庫(kù)提取所需數(shù)據(jù)[2]，手工構(gòu)建事件日志文件。例如，在某采油工廠業(yè)務(wù)過(guò)程改進(jìn)項(xiàng)目中，需要根據(jù)“去年超出預(yù)算的地面改造項(xiàng)目的規(guī)劃設(shè)計(jì)流程分析”、“某個(gè)礦區(qū)產(chǎn)出井大修流程優(yōu)化”、“兩個(gè)部門(mén)間的協(xié)作流程的性能評(píng)價(jià)”等流程挖掘相關(guān)任務(wù)，分析底層數(shù)據(jù)庫(kù)相關(guān)的數(shù)據(jù)模型，定義數(shù)據(jù)挖掘、轉(zhuǎn)換規(guī)則，構(gòu)建XES日志文件。表1所示為從某采油廠生產(chǎn)數(shù)據(jù)庫(kù)十余張數(shù)據(jù)表抽取的事件日志片斷。

表1 簡(jiǎn)化的事件日志片斷

如圖1a所示，傳統(tǒng)日志挖掘策略每次需要編寫(xiě)SQL語(yǔ)句查詢事務(wù)數(shù)據(jù)庫(kù)，將得到的日志數(shù)據(jù)以某種文件格式保存到磁盤(pán)上。流程挖掘工具再將日志文件讀入內(nèi)存執(zhí)行挖掘算法，挖掘蘊(yùn)含其中的流程模型。分析涉及的全部日志數(shù)據(jù)在整個(gè)挖掘過(guò)程中需要反復(fù)讀寫(xiě)磁盤(pán)3次，顯然挖掘工具本身不需要這么多次低效的磁盤(pán)訪問(wèn)操作。而且這種挖掘策略不能與業(yè)務(wù)數(shù)據(jù)庫(kù)的變化保持同步，即使重復(fù)執(zhí)行以前執(zhí)行過(guò)的流程挖掘任務(wù)也必須重新執(zhí)行數(shù)據(jù)導(dǎo)出操作，以確保分析結(jié)果不會(huì)遺漏新產(chǎn)生的事件。因此，研究直接作用于關(guān)系型日志的挖掘方法，可以顯著提高流程挖掘的靈活性與效率。

2 研究現(xiàn)狀

早期流程挖掘工具處理的事件日志都是按標(biāo)準(zhǔn)格式存儲(chǔ)的，如XES格式文件和MXML格式文件。實(shí)際工程環(huán)境下的事件日志往往分散存儲(chǔ)在各種信息系統(tǒng)中，關(guān)系型作為存儲(chǔ)數(shù)據(jù)的主要載體也蘊(yùn)藏著大量事件日志。隨著流程挖掘技術(shù)的應(yīng)用越來(lái)越廣泛，針對(duì)關(guān)系數(shù)據(jù)庫(kù)的流程挖掘研究成為該領(lǐng)域的一個(gè)研究熱點(diǎn)。表2從數(shù)據(jù)庫(kù)侵入性、算法時(shí)間復(fù)雜度和空間復(fù)雜度3個(gè)維度對(duì)已有方法進(jìn)行了對(duì)比。

表2 關(guān)系型日志緊鄰關(guān)系挖掘方法比較

傳統(tǒng)挖掘方法采用手工方式將存儲(chǔ)在關(guān)系數(shù)據(jù)庫(kù)中的事件數(shù)據(jù)導(dǎo)出成標(biāo)準(zhǔn)格式的日志文件，然后利用已有挖掘算法進(jìn)行流程挖掘。該方法不需要對(duì)業(yè)務(wù)數(shù)據(jù)庫(kù)進(jìn)行修改，只需獲得讀取權(quán)限即可，對(duì)數(shù)據(jù)庫(kù)不具有侵入性。面向日志文件的方法在流程挖掘前需要將整個(gè)日志調(diào)入內(nèi)存，對(duì)系統(tǒng)內(nèi)存要求較高。因?yàn)槊嫦蛉罩疚募姆椒ú荒苤苯映槿￡P(guān)系數(shù)據(jù)庫(kù)中事件日志，所以每次挖掘任務(wù)都需要重新導(dǎo)出日志文件以保證挖掘結(jié)果的實(shí)時(shí)性，操作過(guò)程比較繁瑣。

RXES(relational XES)[13]在關(guān)系數(shù)據(jù)庫(kù)上實(shí)現(xiàn)了OpenXES的全部接口函數(shù)，支持挖掘工具隨時(shí)獲取事件日志并挖掘緊鄰關(guān)系。由于不需要在內(nèi)存中加載日志數(shù)據(jù)，RXES的內(nèi)存使用量得到了有效控制，但其挖掘時(shí)間卻因頻繁的硬盤(pán)訪問(wèn)而明顯變長(zhǎng)。

為了減少挖掘工具訪問(wèn)數(shù)據(jù)庫(kù)的次數(shù)，DB-XES方法[14]將緊鄰關(guān)系挖掘工作轉(zhuǎn)移到數(shù)據(jù)庫(kù)內(nèi)部，定義存儲(chǔ)流程數(shù)據(jù)的數(shù)據(jù)倉(cāng)庫(kù)模型。DB-XES方法支持挖掘工具直接對(duì)數(shù)據(jù)庫(kù)中的緊鄰關(guān)系進(jìn)行分析，降低了內(nèi)存使用量和挖掘時(shí)間。但是為了保證緊鄰關(guān)系隨著事件數(shù)據(jù)的變化實(shí)時(shí)更新，DB-XES方法需要在事件相關(guān)字段上建立觸發(fā)器實(shí)現(xiàn)數(shù)據(jù)同步。

與DB-XES方法類似，SAP Celonis工具需要在SAP HANA[15]中構(gòu)建數(shù)據(jù)倉(cāng)庫(kù)[16]，以方便高效地進(jìn)行流程挖掘。DB-XES方法和Celonis工具對(duì)業(yè)務(wù)數(shù)據(jù)庫(kù)都具有較大的侵入性，這在很多應(yīng)用場(chǎng)景中是不允許的。很多企業(yè)從安全角度考慮，不允許第三方應(yīng)用修改自已的數(shù)據(jù)庫(kù)或創(chuàng)建觸發(fā)器。

本文提出一種采用組合SQL實(shí)現(xiàn)的緊鄰關(guān)系挖掘算子[12]。首先將日志L與自身做連接操作，選擇在同一過(guò)程實(shí)例中執(zhí)行時(shí)間存在先后關(guān)系的事件記錄作為弱跟隨關(guān)系集(WFR)。弱跟隨關(guān)系代表在執(zhí)行時(shí)間上存在先后次序，但并不一定緊鄰執(zhí)行的兩個(gè)事件。然后將WFR與日志L再次做連接操作，選擇在弱跟隨關(guān)系間存在其他事件發(fā)生的非直接跟隨關(guān)系集(NDFR)。將WFR與NDFR做差就得到日志L上的緊鄰關(guān)系集合。

該方法采用關(guān)系代數(shù)作為緊鄰關(guān)系挖掘的基礎(chǔ)，編寫(xiě)簡(jiǎn)單且具有較好的通用性，適用于所有關(guān)系型數(shù)據(jù)庫(kù)系統(tǒng)。但是該方法受到關(guān)系代數(shù)計(jì)算能力的限制，需要對(duì)整個(gè)日志數(shù)據(jù)連續(xù)做兩次連接操作，算子的時(shí)間復(fù)雜度較高。為避免不必要的計(jì)算量，本文提出并證明了該算子與選擇操作在執(zhí)行次序上滿足交換律以及該算子與投影操作聯(lián)合執(zhí)行的等價(jià)公式。雖然采用這兩種等價(jià)變換可以極大縮短緊鄰關(guān)系挖掘的時(shí)間，但無(wú)法從根本上解決大規(guī)模日志數(shù)據(jù)分析的難題。

注：*代表低、**代表高、***、代表極高、-代表無(wú)。

3 基于雙排序的緊鄰關(guān)系挖掘

為敘述方便，用E表示事件全集，A表示事件屬性名稱全集，則事件屬性可定義如下。

定義1事件屬性。事件e∈E通常由多個(gè)屬性值描述。給定屬性的名稱a∈A，事件e的屬性值用#a(e)表示。

{case,act,time}∈A是事件的標(biāo)準(zhǔn)屬性集，其中：#case(e)表示事件e所屬的流程實(shí)例，#act(e)表示產(chǎn)生事件e的活動(dòng)，#time(e)表示發(fā)生事件e的時(shí)間。

σ表示活動(dòng)軌跡?；顒?dòng)軌跡的集合L表示日志。

定義2緊鄰關(guān)系[17]?；顒?dòng)a和活動(dòng)b間存在緊鄰關(guān)系，當(dāng)日志L中存在業(yè)務(wù)活動(dòng)軌跡σ=〈t1,t2,t3,…,tn〉,i∈{1,…,n-1},使得σ∈L,ti=a,ti+1=b。a>Lb表示活動(dòng)a和活動(dòng)b在日志L中存在緊鄰關(guān)系。

關(guān)系數(shù)據(jù)庫(kù)通常提供排序功能，利用關(guān)系數(shù)據(jù)庫(kù)在索引上高效排序的能力，對(duì)日志數(shù)據(jù)表執(zhí)行“selectt.activity,t.case,t.completetimefromTABLENAMEtorderbyt.caseidasc,t.completetimeasc”查詢操作，得到一個(gè)在實(shí)例和時(shí)間戳上雙升序排列的事件序列Lc↑,t↑，其中TABLENAME是存放日志數(shù)據(jù)的表或視圖。

定義3Lc↑,t↑=〈e1,e2,…,em〉，在實(shí)例上升序排列決定相同過(guò)程實(shí)例的事件在序列Lc↑,t↑上排列位置具有區(qū)域性，即?i,j∈[1,m]((i

?i∈[1,m]((#caseei=#caseei+1)→

(#timeei≤#timeei+1))。

定理1對(duì)于序列Lc↑,t↑上相鄰的任意兩個(gè)事件，它們的執(zhí)行任務(wù)要么具有緊鄰關(guān)系，要么是同時(shí)刻發(fā)生事件。

證明因?yàn)?i∈[1,m]((#caseei=#caseei+1)→(#timeei≤#timeei+1))，所以要么#timeei=#timeei+1，要么#timeei<#timeei+1。若#timeei=#timeei+1，則ei與ei+1發(fā)生于同一時(shí)刻。若#timeei<#timeei+1，則#actei與#actei+1具有緊鄰關(guān)系，因?yàn)槿罩綥中至少存在一個(gè)過(guò)程實(shí)例#caseei，使#actei

具有相同時(shí)間戳的事件在日志中經(jīng)常出現(xiàn)。如果#timeei=#timeei-1且#timeei<#timeei+1，則#actei

由于同時(shí)刻事件的存在，使得具有緊鄰關(guān)系的活動(dòng)執(zhí)行產(chǎn)生的事件在序列Lc↑,t↑上不一定緊鄰。

定理2對(duì)于任意具有緊鄰關(guān)系的任務(wù)a

證明使用反證法。假設(shè)存在事件ek,k∈(i,j)，#caseek≠#caseei，則違背Lc↑,t↑的過(guò)程實(shí)例區(qū)域性。若(#timeek≠#timeei)∧(#timeek≠#timeej)，則#timeei<#timeek<#timeej，則與任務(wù)a

輸入：SQL查詢語(yǔ)句sql;

輸出：緊鄰關(guān)系DFR。

1.Function DFRGen(sql)

2. 在事務(wù)數(shù)據(jù)庫(kù)中執(zhí)行查詢sql,c←null

3. 逐行讀取日志記錄e∈L，將結(jié)果#activitye、#casee和#timee存放于臨時(shí)變量act、cid和time

4. While(e≠null)

5. If cid≠c

6. If(#timees1≠φ)and(#timees2≠φ) DFR←Enumerate(es1,es2)

7. c←cid

8. es1←φ,es2←φ,es3←φ,es1←es1∪{act},#timees1←time

9. Else If

10. If(#timees1=time)es1←es1∪{act}

11. Else If(es2=φ)es2←{act},#timees2←time

12. ElseIf(#timees2=time)es2←es2∪{act}

13. Else

14. DFR←Enumerate(es1,es2)

15. es1←es2,es2←{act},#timees2←time

16. EndIf

17. EndWhile

18. DFR←Enumerate(es1,es2)

19. return DFR

20.EndFunction

算法2緊鄰關(guān)系枚舉函數(shù)。

輸入：前一個(gè)時(shí)間點(diǎn)發(fā)生的事件集合aes，前兩個(gè)時(shí)間點(diǎn)發(fā)生的事件集合bes;

輸出：緊鄰關(guān)系。

1.Function Enumerate(aes, bes)

2. RT←?

3.Fori in aes

4. For j in bes

5. RT←RT∪{(i,j)}

6. EndFor

7. EndFor

8. return RT

9.EndFunction

如圖2所示，該算法處理事件日志的過(guò)程中，最多只需要保存兩個(gè)時(shí)間點(diǎn)發(fā)生的事件記錄。讀取案例的第1個(gè)時(shí)間點(diǎn)發(fā)生的事件序列時(shí)，算法處于狀態(tài)S1，當(dāng)讀到第2個(gè)時(shí)間點(diǎn)以及晚于第2個(gè)時(shí)間點(diǎn)的事件序列時(shí)算法處于狀態(tài)S2。當(dāng)算法開(kāi)始處理新案例時(shí)處于狀態(tài)S1，負(fù)責(zé)搜集當(dāng)前案例第1個(gè)時(shí)間點(diǎn)發(fā)生的事件集合。S2是算法的核心狀態(tài)，處于該狀態(tài)的算法不斷地搜集當(dāng)前時(shí)間點(diǎn)的事件集，并在進(jìn)入新時(shí)間點(diǎn)之前將當(dāng)前時(shí)間點(diǎn)的事件集與上一時(shí)間點(diǎn)的事件集進(jìn)行笛卡爾乘積(調(diào)用Enumerate子過(guò)程)以生成一組緊鄰關(guān)系的集合。

因此無(wú)論在時(shí)間復(fù)雜度上還是空間復(fù)雜度上，該算法都消除了事件日志規(guī)模對(duì)緊鄰關(guān)系挖掘的限制。

4 實(shí)驗(yàn)設(shè)計(jì)與分析

本章通過(guò)實(shí)驗(yàn)比對(duì)了以上3種緊鄰關(guān)系抽取方法的運(yùn)行效率。如圖1a所示，面向日志文件的方法需要將關(guān)系數(shù)據(jù)庫(kù)中的日志導(dǎo)出為本地日志文件，然后利用ProM上的LogAbstractionImpl類挖掘緊鄰關(guān)系。因此，面向日志文件的方法包括由手工操作銜接起來(lái)的導(dǎo)出日志文件、加載日志文件、緊鄰關(guān)系挖掘3個(gè)步驟。本次實(shí)驗(yàn)分析緊鄰關(guān)系挖掘的完整過(guò)程，因此需要在LogAbstractionImpl類的getFollowerInfo()方法添加時(shí)鐘記錄。

采用SQL92編寫(xiě)的組合SQL語(yǔ)句如下：

SELECT DISTINCT a.activity, b.activity

FROM R a, R b WHERE a.case=b.case AND a.time

NOT EXIST SELECT * FROM R c WHERE c.case=a.case AND a.time

實(shí)驗(yàn)采用Oracle11g作為數(shù)據(jù)庫(kù)管理系統(tǒng)，數(shù)據(jù)庫(kù)服務(wù)器為8 G內(nèi)存，2核CPU@1.6 GHz惠普服務(wù)器。挖掘算法運(yùn)行在4 G內(nèi)存，i54核心@2.3 GHz的個(gè)人臺(tái)式機(jī)上。

實(shí)驗(yàn)數(shù)據(jù)包括真實(shí)數(shù)據(jù)和模擬數(shù)據(jù)。真實(shí)數(shù)據(jù)集選擇導(dǎo)入Oracle11g數(shù)據(jù)庫(kù)的CoSeLoG項(xiàng)目的WABO數(shù)據(jù)集[19]。WABO的原始數(shù)據(jù)集是XES的日志文件，事件數(shù)據(jù)是以過(guò)程實(shí)例為模塊集中存儲(chǔ)的。為了貼近實(shí)際數(shù)據(jù)庫(kù)存儲(chǔ)情況，在導(dǎo)入數(shù)據(jù)庫(kù)時(shí)進(jìn)行了亂序處理，打亂記錄在數(shù)據(jù)庫(kù)中的存儲(chǔ)順序。通過(guò)復(fù)制事件記錄構(gòu)造規(guī)模不同的數(shù)據(jù)表來(lái)分析算法在不同規(guī)模數(shù)據(jù)集下的性能表現(xiàn)。為單獨(dú)分析活動(dòng)數(shù)量、緊鄰關(guān)系數(shù)量和實(shí)例長(zhǎng)度對(duì)運(yùn)行時(shí)間的影響，開(kāi)發(fā)了日志數(shù)據(jù)模擬器，生成給定活動(dòng)數(shù)量、緊鄰關(guān)系數(shù)量和實(shí)例長(zhǎng)度的合成日志。

本節(jié)實(shí)驗(yàn)分3組進(jìn)行，分別比較每種因素對(duì)運(yùn)行時(shí)間的影響，具體如表3所示。

表3 實(shí)驗(yàn)分組情況表

4.1 第1組實(shí)驗(yàn)分析

G1實(shí)驗(yàn)采用兩組數(shù)據(jù)集，一組是基于真實(shí)事件日志構(gòu)造的數(shù)據(jù)集，因?yàn)閿?shù)據(jù)集較大，無(wú)法獲得組合SQL運(yùn)行結(jié)果，所以構(gòu)造了一組模擬數(shù)據(jù)，比較算法在事件數(shù)量增長(zhǎng)過(guò)程的性能變化情況，如圖3所示。

4.2 第2組實(shí)驗(yàn)分析

4.3 第3組實(shí)驗(yàn)分析

4.4 內(nèi)存使用情況分析

下面給出3種算法的內(nèi)存使用量分析。

(2)組合SQL 在數(shù)據(jù)庫(kù)服務(wù)器端要求是V×(E/V)×(E/V)，其中：V是過(guò)程實(shí)例個(gè)數(shù)，E是事件數(shù)量。也就是說(shuō)，組合SQL所需的內(nèi)存空間是過(guò)程實(shí)例平均長(zhǎng)度與事件數(shù)量的乘積。

(3)面向日志文件的方法 因?yàn)樾枰獙⑷罩救空{(diào)入內(nèi)存，然后挖掘緊鄰關(guān)系，所以面向日志文件的方法在客戶端需要的內(nèi)存為日志文件的大小。

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

因?yàn)樵撍惴ㄔ谕诰蚓o鄰關(guān)系的過(guò)程中需要將整個(gè)日志傳送至客戶端，所以在服務(wù)器與客戶端之間網(wǎng)速不夠快的網(wǎng)絡(luò)環(huán)境下，挖掘時(shí)間明顯變長(zhǎng)。該問(wèn)題在面向日志文件的方法中同樣存在。筆者已經(jīng)在開(kāi)源平臺(tái)ProM上實(shí)現(xiàn)了該算法，并在此基礎(chǔ)上重構(gòu)了經(jīng)典的α算法。該算法及其實(shí)現(xiàn)對(duì)提高關(guān)系數(shù)據(jù)庫(kù)中事件日志的流程挖掘具有一定的理論意義和實(shí)踐價(jià)值，未來(lái)將在多源關(guān)系數(shù)據(jù)庫(kù)上研究直接挖掘策略的理論問(wèn)題和實(shí)現(xiàn)方法，進(jìn)一步拓寬該算法的應(yīng)用范圍。