计算机科学 ›› 2016, Vol. 43 ›› Issue (5): 169-173.doi: 10.11896/j.issn.1002-137X.2016.05.031

• 软件与数据库技术 • 上一篇    下一篇

基于条件冲突分析的主动规则集汇流性判定方法

熊中敏,朱吉光,李长绩,袁红春   

  1. 上海海洋大学信息学院 上海201306,上海海洋大学信息学院 上海201306,上海海洋大学信息学院 上海201306,上海海洋大学信息学院 上海201306
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受上海市科委科技支撑项目(14391901400),国家自然科学基金(61272098),国家973重大基础研究基金(2012CB316200),2015年度上海海洋大学大学生创新计划项目资助

Confluence Decision Method for Active Rule Set Based on Condition Conflict Analysis

XIONG Zhong-min, ZHU Ji-guang, LI Chang-ji and YUAN Hong-chun   

  • Online:2018-12-01 Published:2018-12-01

摘要: 主动规则使数据库具备自反应能力,在数据库、知识库和无线传感器网络等领域得到了广泛应用。汇流性分析是保持数据一致性的重要手段,但有效判定汇流性仍是一个难题。现有的方法基于规则可交换性进行判定,没有考虑规则之间是否存在条件冲突而导致它们不可能同时出现在同一个执行序列中;同时基于触发关系的集合分析没有考虑在规则触发序列中的先后时序性。为此,提出了规则的触发序列概念,分析了单个触发序列上的条件冲突和一对无序规则所在的两条触发序列之间的条件冲突,从而提出了更有效的汇流性先决条件及其判定定理,同时给出了新的判定算法的完整描述及其可终止性、正确性证明和复杂度分析。

关键词: 主动数据库,规则分析,汇流性,条件冲突,数据一致性

Abstract: With active rules,many databases have automatic reaction function.Many areas including databases,know-ledge database and wireless sensor network have employed active rules.Confluence analysis can maintain data consistency of database,but it is a very hard task.Based on rule commutativity,the existing methods do not consider whether there exists a condition conflict between rules and then these rules cannot be executed at the same executive sequence.And the existing analysis is based on the rules set and does not consider the time order between triggering rules.To add-ress these problems,the concepts of triggering sequence was provided and the condition conflicts in a triggering sequence were analyzed.Finally,a new algorithm of confluence detection was provided and its correctness and termination were proved.

Key words: Active database,Rule analysis,Confluence,Condition conflict,Data consistency

[1] Bonifati A,Ceri S,Paraboschi S.Active rules for XML:A new paradigm for e-services[J].VLDB Journal,2001,10(1):39-47
[2] Mansour E,Dube K,Wu Bing.AIM:An XML-Based ECA Rule Language for Supporting a Framework for Managing Complex Information[C]∥Proceedings of International Symposium.RuleML 2007.2007:232-241
[3] Bae H,Yu Y W.Auto-Triggering of RFID-based Logistic Pro-cess in Inter-workflow Using Complex Event[M]∥Dynamics in Logistics.Springer,2011:329-339
[4] Behrends E,Fritzen O,May W,et al.Embedding Event Algebras and Process for ECA Rules for the Semantic Web[J].Fundamenta Informaticae,2008,82(3):237-263
[5] ztarak H,Akkaya K,Yazici A.Providing Automated Actions in Wireless Multimedia Sensor Networks via Active Rules[M]∥Computer and Information Sciences II.Springer,2012:185-190
[6] Aiken A,Hellerstein J,Widom J.Static Analysis Techniques for Predicting the Behavior of Database Production Rules[J].ACM Transactions on Database Systems,1995,20(1):3-41
[7] Shu Jie.Analyzing Rules of Active Database based on Propagation Algorithm[D].Harbin:Harbin University of Science and Technology,2006(in Chinese) 舒杰.基于传播算法的主动数据库规则特性分析[D].哈尔滨:哈尔滨理工大学,2006
[8] Yang Ze-xue.Termination Analysis of Active Rules[D].Harbin:Harbin University of Science and Technology,2006(in Chinese) 杨泽雪.主动规则的终止性分析[D].哈尔滨:哈尔滨理工大学,2006
[9] Comai S,Tanca L.Termination and Confluence by Rule Prioritization[J].IEEE Transactions on Knowledge and Data Enginee-ring,2003,15(2):257-270
[10] Papamarkos G,Poulovassilis A,Wood P T.Event-Condition-Action Rules on RDF Metadata in P2P Environments[J].Compu-ter Networks,Elsevier,2006,50(10):1513-1532
[11] Bostan-Korpeoglu B,Yazici A.A fuzzy Petri net model for intelligent databases[J].Data & Knowledge Engineering,2007,62(2):219-247
[12] Xiong Zhong-min,Zhao Meng-lu,Zhou Xue-nan,et al.A Conflu-ence Decison Method for an Active Rule Set with Exclusive Rules [J].Journal of Computer Research and Development,2013,50(Suppl.):109-116(in Chinese) 熊中敏,赵梦露,周雪楠,等.含排他性选择规则的主动规则集的汇流性判定方法[J].计算机研究与发展,2013,50(增刊):109-116
[13] Baralis E,Ceri S,et al.Compile-Time and Runtime Analysis of Active Behaviors[J].IEEE Transactions on Knowledge and Data Engineering,1998,10(3):353-370
[14] Xiong Zhong-min,Zhao Meng-lu, Huang Dong-mei,et al.Active rules termination analysis based on activation path and enhanced formula [J].International Journal of Intelligent Information and Database Systems,2013,7(1):53-78
[15] Xiong Wei,Wu Ye,Zhang Zhen,et al.Termination Analysis for Active Rule Set Based on Triggering Path [J].Chinese Journal of Computers,2012,35(1):65-75(in Chinese) 熊伟,吴烨,张震,等.基于触发路径的主动规则集终止性分析[J].计算机学报,2012,35(1):65-75
[16] Xiong Zhong-min,Hao Zhong-xiao.An Approach to Termination Decision for a Rule Set Based on Activation Path and Conditional Formula [J].Journal of Computer Research and Deve-lopment,2006,43(5):901-907(in Chinese) 熊中敏,郝忠孝.基于活化路径和条件公式的主动规则集可终止性判定方法[J].计算机研究与发展,2006,3(5):901-907
[17] Hao Zhong-xiao,Xiong Zhong-min.An Efficient Algorithm for Computing an Irreducible Rule Set in Active Database [J].Journal of Computer Research and Development,2006,43(2):281-287(in Chinese) 郝忠孝,熊中敏.计算主动数据库中不可归约规则集的有效算法[J].计算机研究与发展,2006,43(2):281-287
[18] Lee S Y,Ling T W.Refined Termination Decision in Active Databases[C]∥Proceedings of Int’l Conf.On Database and Expert Systems Applications(DEXA).Toulouse,France,1997
[19] Lee S Y,Ling T W.A path Removing Technique for Detecting Trigger Termination[C]∥Proceedings of Int’l Conf.on Extended Database Technology(EDBT).Valencia,Spain,1998
[20] Urban S D,Tschudi M K,Dietrich S W,et al.Active Rule Termination Analysis:An Implementation and Evaluation of the Refined Triggering Graph Method[J].Journal of Intelligent Information Systems,1999,12(1):27-60

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!