关系数据库中事件日志的紧邻关系高效挖掘方法

高俊涛,刘 聪, 刘云峰

(1.东北石油大学 计算机与信息技术学院，黑龙江 大庆 163318；2.山东理工大学 计算机科学与技术学院，山东 淄博 255000)

1 问题的提出

随着信息技术的普及和发展，信息系统在为企业运营带来高效和快捷的同时，也留存下大量宝贵的日志数据。流程挖掘技术通过分析隐含在事件日志中的流程信息来发现、监控和改进实际业务流程[1]。目前，大多数信息系统采用成熟的关系数据库存储事务数据，关系型数据成为事件日志的主要来源。传统的流程挖掘工具采用MXML(mining extensible markup language)或XES(extensible event stream)格式的日志文件作为输入数据。在每次执行挖掘任务之前，需要根据具体问题从数据库提取所需数据[2]，手工构建事件日志文件。例如，在某采油工厂业务过程改进项目中，需要根据“去年超出预算的地面改造项目的规划设计流程分析”、“某个矿区产出井大修流程优化”、“两个部门间的协作流程的性能评价”等流程挖掘相关任务，分析底层数据库相关的数据模型，定义数据挖掘、转换规则，构建XES日志文件。表1所示为从某采油厂生产数据库十余张数据表抽取的事件日志片断。

表1 简化的事件日志片断

如图1a所示，传统日志挖掘策略每次需要编写SQL语句查询事务数据库，将得到的日志数据以某种文件格式保存到磁盘上。流程挖掘工具再将日志文件读入内存执行挖掘算法，挖掘蕴含其中的流程模型。分析涉及的全部日志数据在整个挖掘过程中需要反复读写磁盘3次，显然挖掘工具本身不需要这么多次低效的磁盘访问操作。而且这种挖掘策略不能与业务数据库的变化保持同步，即使重复执行以前执行过的流程挖掘任务也必须重新执行数据导出操作，以确保分析结果不会遗漏新产生的事件。因此，研究直接作用于关系型日志的挖掘方法，可以显著提高流程挖掘的灵活性与效率。

2 研究现状

早期流程挖掘工具处理的事件日志都是按标准格式存储的，如XES格式文件和MXML格式文件。实际工程环境下的事件日志往往分散存储在各种信息系统中，关系型作为存储数据的主要载体也蕴藏着大量事件日志。随着流程挖掘技术的应用越来越广泛，针对关系数据库的流程挖掘研究成为该领域的一个研究热点。表2从数据库侵入性、算法时间复杂度和空间复杂度3个维度对已有方法进行了对比。

表2 关系型日志紧邻关系挖掘方法比较

传统挖掘方法采用手工方式将存储在关系数据库中的事件数据导出成标准格式的日志文件，然后利用已有挖掘算法进行流程挖掘。该方法不需要对业务数据库进行修改，只需获得读取权限即可，对数据库不具有侵入性。面向日志文件的方法在流程挖掘前需要将整个日志调入内存，对系统内存要求较高。因为面向日志文件的方法不能直接抽取关系数据库中事件日志，所以每次挖掘任务都需要重新导出日志文件以保证挖掘结果的实时性，操作过程比较繁琐。

RXES(relational XES)[13]在关系数据库上实现了OpenXES的全部接口函数，支持挖掘工具随时获取事件日志并挖掘紧邻关系。由于不需要在内存中加载日志数据，RXES的内存使用量得到了有效控制，但其挖掘时间却因频繁的硬盘访问而明显变长。

为了减少挖掘工具访问数据库的次数，DB-XES方法[14]将紧邻关系挖掘工作转移到数据库内部，定义存储流程数据的数据仓库模型。DB-XES方法支持挖掘工具直接对数据库中的紧邻关系进行分析，降低了内存使用量和挖掘时间。但是为了保证紧邻关系随着事件数据的变化实时更新，DB-XES方法需要在事件相关字段上建立触发器实现数据同步。

与DB-XES方法类似，SAP Celonis工具需要在SAP HANA[15]中构建数据仓库[16]，以方便高效地进行流程挖掘。DB-XES方法和Celonis工具对业务数据库都具有较大的侵入性，这在很多应用场景中是不允许的。很多企业从安全角度考虑，不允许第三方应用修改自已的数据库或创建触发器。

本文提出一种采用组合SQL实现的紧邻关系挖掘算子[12]。首先将日志L与自身做连接操作，选择在同一过程实例中执行时间存在先后关系的事件记录作为弱跟随关系集(WFR)。弱跟随关系代表在执行时间上存在先后次序，但并不一定紧邻执行的两个事件。然后将WFR与日志L再次做连接操作，选择在弱跟随关系间存在其他事件发生的非直接跟随关系集(NDFR)。将WFR与NDFR做差就得到日志L上的紧邻关系集合。

该方法采用关系代数作为紧邻关系挖掘的基础，编写简单且具有较好的通用性，适用于所有关系型数据库系统。但是该方法受到关系代数计算能力的限制，需要对整个日志数据连续做两次连接操作，算子的时间复杂度较高。为避免不必要的计算量，本文提出并证明了该算子与选择操作在执行次序上满足交换律以及该算子与投影操作联合执行的等价公式。虽然采用这两种等价变换可以极大缩短紧邻关系挖掘的时间，但无法从根本上解决大规模日志数据分析的难题。

注：*代表低、**代表高、***、代表极高、-代表无。

3 基于双排序的紧邻关系挖掘

为叙述方便，用E表示事件全集，A表示事件属性名称全集，则事件属性可定义如下。

定义1事件属性。事件e∈E通常由多个属性值描述。给定属性的名称a∈A，事件e的属性值用#a(e)表示。

{case,act,time}∈A是事件的标准属性集，其中：#case(e)表示事件e所属的流程实例，#act(e)表示产生事件e的活动，#time(e)表示发生事件e的时间。

σ表示活动轨迹。活动轨迹的集合L表示日志。

定义2紧邻关系[17]。活动a和活动b间存在紧邻关系，当日志L中存在业务活动轨迹σ=〈t1,t2,t3,…,tn〉,i∈{1,…,n-1},使得σ∈L,ti=a,ti+1=b。a>Lb表示活动a和活动b在日志L中存在紧邻关系。

关系数据库通常提供排序功能，利用关系数据库在索引上高效排序的能力，对日志数据表执行“selectt.activity,t.case,t.completetimefromTABLENAMEtorderbyt.caseidasc,t.completetimeasc”查询操作，得到一个在实例和时间戳上双升序排列的事件序列Lc↑,t↑，其中TABLENAME是存放日志数据的表或视图。

定义3Lc↑,t↑=〈e1,e2,…,em〉，在实例上升序排列决定相同过程实例的事件在序列Lc↑,t↑上排列位置具有区域性，即∀i,j∈[1,m]((i

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

(#timeei≤#timeei+1))。

定理1对于序列Lc↑,t↑上相邻的任意两个事件，它们的执行任务要么具有紧邻关系，要么是同时刻发生事件。

证明因为∀i∈[1,m]((#caseei=#caseei+1)→(#timeei≤#timeei+1))，所以要么#timeei=#timeei+1，要么#timeei<#timeei+1。若#timeei=#timeei+1，则ei与ei+1发生于同一时刻。若#timeei<#timeei+1，则#actei与#actei+1具有紧邻关系，因为日志L中至少存在一个过程实例#caseei，使#actei

具有相同时间戳的事件在日志中经常出现。如果#timeei=#timeei-1且#timeei<#timeei+1，则#actei

由于同时刻事件的存在，使得具有紧邻关系的活动执行产生的事件在序列Lc↑,t↑上不一定紧邻。

定理2对于任意具有紧邻关系的任务a

证明使用反证法。假设存在事件ek,k∈(i,j)，#caseek≠#caseei，则违背Lc↑,t↑的过程实例区域性。若(#timeek≠#timeei)∧(#timeek≠#timeej)，则#timeei<#timeek<#timeej，则与任务a

输入：SQL查询语句sql;

输出：紧邻关系DFR。

1.Function DFRGen(sql)

2. 在事务数据库中执行查询sql,c←null

3. 逐行读取日志记录e∈L，将结果#activitye、#casee和#timee存放于临时变量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紧邻关系枚举函数。

输入：前一个时间点发生的事件集合aes，前两个时间点发生的事件集合bes;

输出：紧邻关系。

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所示，该算法处理事件日志的过程中，最多只需要保存两个时间点发生的事件记录。读取案例的第1个时间点发生的事件序列时，算法处于状态S1，当读到第2个时间点以及晚于第2个时间点的事件序列时算法处于状态S2。当算法开始处理新案例时处于状态S1，负责搜集当前案例第1个时间点发生的事件集合。S2是算法的核心状态，处于该状态的算法不断地搜集当前时间点的事件集，并在进入新时间点之前将当前时间点的事件集与上一时间点的事件集进行笛卡尔乘积(调用Enumerate子过程)以生成一组紧邻关系的集合。

因此无论在时间复杂度上还是空间复杂度上，该算法都消除了事件日志规模对紧邻关系挖掘的限制。

4 实验设计与分析

本章通过实验比对了以上3种紧邻关系抽取方法的运行效率。如图1a所示，面向日志文件的方法需要将关系数据库中的日志导出为本地日志文件，然后利用ProM上的LogAbstractionImpl类挖掘紧邻关系。因此，面向日志文件的方法包括由手工操作衔接起来的导出日志文件、加载日志文件、紧邻关系挖掘3个步骤。本次实验分析紧邻关系挖掘的完整过程，因此需要在LogAbstractionImpl类的getFollowerInfo()方法添加时钟记录。

采用SQL92编写的组合SQL语句如下：

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

实验采用Oracle11g作为数据库管理系统，数据库服务器为8 G内存，2核CPU@1.6 GHz惠普服务器。挖掘算法运行在4 G内存，i54核心@2.3 GHz的个人台式机上。

实验数据包括真实数据和模拟数据。真实数据集选择导入Oracle11g数据库的CoSeLoG项目的WABO数据集[19]。WABO的原始数据集是XES的日志文件，事件数据是以过程实例为模块集中存储的。为了贴近实际数据库存储情况，在导入数据库时进行了乱序处理，打乱记录在数据库中的存储顺序。通过复制事件记录构造规模不同的数据表来分析算法在不同规模数据集下的性能表现。为单独分析活动数量、紧邻关系数量和实例长度对运行时间的影响，开发了日志数据模拟器，生成给定活动数量、紧邻关系数量和实例长度的合成日志。

本节实验分3组进行，分别比较每种因素对运行时间的影响，具体如表3所示。

表3 实验分组情况表

4.1 第1组实验分析

G1实验采用两组数据集，一组是基于真实事件日志构造的数据集，因为数据集较大，无法获得组合SQL运行结果，所以构造了一组模拟数据，比较算法在事件数量增长过程的性能变化情况，如图3所示。

4.2 第2组实验分析

4.3 第3组实验分析

4.4 内存使用情况分析

下面给出3种算法的内存使用量分析。

(2)组合SQL 在数据库服务器端要求是V×(E/V)×(E/V)，其中：V是过程实例个数，E是事件数量。也就是说，组合SQL所需的内存空间是过程实例平均长度与事件数量的乘积。

(3)面向日志文件的方法 因为需要将日志全部调入内存，然后挖掘紧邻关系，所以面向日志文件的方法在客户端需要的内存为日志文件的大小。

5 结束语

因为该算法在挖掘紧邻关系的过程中需要将整个日志传送至客户端，所以在服务器与客户端之间网速不够快的网络环境下，挖掘时间明显变长。该问题在面向日志文件的方法中同样存在。笔者已经在开源平台ProM上实现了该算法，并在此基础上重构了经典的α算法。该算法及其实现对提高关系数据库中事件日志的流程挖掘具有一定的理论意义和实践价值，未来将在多源关系数据库上研究直接挖掘策略的理论问题和实现方法，进一步拓宽该算法的应用范围。