基于扩展Petri网的ECA规则集表示及终止性分析

doi:10.3969/j.issn.1000-436x.2013.03.020

摘要/Abstract

摘要：

为了提高ECA规则集可终止性分析的准确性，建立了一种可描述ECA规则集的扩展Petri网(EPN, ex-tended Petri net)模型，在此基础上研究并提出了一种ECA规则集终止性判定算法。该算法充分利用EPN所包含ECA规则特性的丰富信息，综合分析了ECA规则特性对规则集可终止性的影响。理论分析和实验结果表明，所提出的算法具有更高的准确性和更低的时间复杂度。

关键词: ECA规则, Petri网, 终止性分析, EPN, 模型表示

Abstract:

In order to improve the accuracy of the termination an lysis on ECA rules, a novel representation model (EPN, extended Petri net) of ECA rules was built. Based on the EPN, an effective termination decision algorithm was discussed and proposed. By using plenty of information about the rule characteristics in EPN, the proposed termination algorithm could comprehensively analyze the influence on the termination analysis. The theoretical analysis and experimental re-sults show that the proposed algorithm has higher accuracy and lower time complexity.

Key words: ECA rule, Petri net, termination analysis, extended Petri net, model representation

张立臣,王小明,窦文阳. 基于扩展Petri网的ECA规则集表示及终止性分析[J]. 通信学报, 2013, 34(3): 157-164.

Li-chen ZHANG,Xiao-ming WANG,Wen-yang DOU. Representation and termination analysis for ECA rules based on extended Petri net[J]. Journal on Communications, 2013, 34(3): 157-164.

图/表 17

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

表1

表2

表3

参考文献 17

[1]	PATONN , DIAZO . Active database systems[J]. ACM Computing Surveys, 1999,31(1): 63-103.
[2]	卢捍华, 闵丽娟, 王亚石 . 工作流主从实例处理方法及其 Petri网建模[J]. 通信学报, 2010,31(1): 92-99. LUT H , MINL J , WANGY S . Approach to master-slave workflow system and its Petri-net modeling[J]. Journal on Communications, 2010,31(1): 92-99.
[3]	郭迎九, 林闯, 尹浩等. 基于Petri网的数字媒体分发协议的安全性证明[J]. 电子学报, 2009,37(5): 1031-1036. GUOY J , LINC , YINH , et al. Proof of the security of digital media distributing protocol based on Petri net models[J]. Acta Electronica Sinica, 2009,37(5): 1031-1036.
[4]	AIKENA , WIDOMJ , HELLERSTEINJ M . Behavior of database production rules: termination, confluence, and observable determin-ism[J]. SIGMOD, 1992,21(2): 59-68.
[5]	BAILEYJ , DONGG , RAMAMOHANARAOK . Decidability and undecidability results for the termination problem of ive database rules[A]. PODS'98[C]. New York, USA, 1998. 264-273.
[6]	MURATAT . Petri nets: properties, analysis and applica ions[J]. Pro-ceedings of the IEEE, 1989,77(4): 541-580.
[7]	BARALISE , CERIS , WIDOMJ . Better termination analysi for active databases[A]. RIDS '93[C]. Edinburgh, Scotland, 1993. 163-179.
[8]	BARALISE , CERIS , PARABOSCHIS . Improved rule analysis by means of triggering and activation graphs[A]. RIDS'95[C]. Greece: Springer-Verlag, 1995. 165-181.
[9]	MONTESID , BAGNATOM , DALLERAC . Termination analysis in active databases[A]. IDEAS'99[C]. Montreal,Canada, 1999. 288-297.
[10]	郝忠孝, 任超, 赵龄强 . 含环触发图对应的主动规则集可终止性分析[J]. 计算机研究与发展, 2005,42(12): 2199-2205. HAOZ X , RENC , ZHAOL Q . Termination analysis of acti rule based on dependency set[J]. Journal of Computer Research and De-velopment, 2005,42(12): 2199-2205.
[11]	熊曾刚, 杨扬, 曾明 . 基于Petri网的两阶段网格任务调度模型与分析[J]. 通信学报, 2009,30(8): 69-77. XIONGC G , YANGY , ZENGM . Research on two-phase grid task scheduling based on Petri nets[J]. Journal on Communications, 2009,30(8): 69-77.
[12]	LATIFAB , HAFIDAB . The priority of rules and the term nation analysis using Petri nets[J]. The International Arab Journal of Informa-tion Technology, 2007,4(2): 177-183.
[13]	MEDINA-MARINJ , PEREZ-LECHUGAG , LIX . ECA rule analysis in a distributed active database[A]. ICCTD'09[C]. Kinabalu,Malaysia, 2009. 113-116.
[14]	BOSTAN-KORPEOGLUB , YAZICIA . A fuzzy Petri net model for intelligent databases[J]. Data ＆ Knowledge Engineering, 2007,62(2): 219-247.
[15]	张立臣 . 面向普适计算的主动访问控制模型研究[D]. 西安: 陕西师范大学， 2011. ZHANGL C . Research on Active Access Control Model for Pervasive Computing[D]. Xian: Shaanxi Normal University, 2011.
[16]	CHRISTENSENS , HANSENN . Coloured Petri nets extended ith place capacities, test arcs and inhibitor arcs[J]. Lecture Notes in Com-puter Science, 1993,691(1): 186-205.
[17]	FRATERNALIP , TANCAL . A structured approach for the definition of the semantics of active databases[J]. ACM Trans on Database Sys-tems, 1995,20(4): 414-471.

算法	规则条数
算法	100	150	200	250	500	1000
TG	13	67	234	649	＞10⁴	＞10⁵
BK	13	68	253	666	＞10⁴	＞10⁵
PN	＜10^{- 2}	＜10^{- 2}	＜10^{- 2}	＜10^{- 2}	0.04	0.1

算法				规则条数
算法	100	150	200	250	500	1000
TG	6	35	118	318	＞10⁴	＞10⁵
BK	13	71	259	672	＞10⁴	＞10⁵
PN	＜10^{- 2}	＜10^{- 2}	＜10^{- 2}	＜10^{- 2}	0.03	0.1

算法	规则条数
算法	100	150	200	250	500	1000
TG	13	82	250	708	＞10⁴	＞10⁵
BK	15	83	290	729	＞10⁴	＞10⁵
PN	0.04	0.05	0.08	0.1	0.2	0.3