基于增强条件公式的主动规则集可终止性判定

J4 ›› 2014, Vol. 36 ›› Issue (01): 163-168.

基于增强条件公式的主动规则集可终止性判定

熊中敏，赵梦露，黄冬梅

（上海海洋大学信息学院，上海 201306）

收稿日期:2013-06-28 修回日期:2012-11-12 出版日期:2014-01-25 发布日期:2014-01-25
基金资助:
上海市科委研究基金资助项目（10510502800）；国家973重大基础研究基金资助项目（2012CB316200）

Active rules termination determination
based on enhanced conditional formula

XIONG Zhongmin,ZHAO Menglu,HUANG Dongmei

(College of Information Technology,Shanghai Ocean University,Shanghai 201306,China)

Received:2013-06-28 Revised:2012-11-12 Online:2014-01-25 Published:2014-01-25

摘要/Abstract

摘要：

主动规则集的可终止性判定是一个研究热点问题，现有的基于触发图和活化图的方法没有考虑触发环所有所属规则能否在同一次执行中执行；现有的条件公式判定方法只能包含不可更新或有限次更新变量，当主动规则集只包含可有限次循环执行的触发环时，现有方法不能准确判定它是可终止的。为此，提出了触发环的执行序列的概念和建立包含可更新变量的增强条件公式的方法，新的判定方法将触发环和执行语义有机地结合在一起，较现有方法可以发现更多的可终止性情形，同时给出了新算法的可终止性和正确性证明。

关键词: 主动数据库, 规则分析, 活化路径, 增强条件公式, 可终止性

Abstract:

Termination decision in active database becomes a focus for many researchers. Existing methods based on triggering and activation graphs do not consider whether all rules in a triggering cycle can be executed at the same execution sequence. Existing methods based on logical formula, where only those nonupdatable or finitely updatable variables can be represented, cannot conclude termination if a rule set contains only those cycles that can be executed in a finite number of times. To solve this problem, the concept of the execution sequence of a triggering cycle and the method to construct an enhanced formula including updatable variables are proposed. Many termination cases that cannot be determined by previous methods can be detected by the proposed solution, whose correctness and termination are proved.

Key words: active database;rule analysis;activation path;enhanced conditional formula;termination

熊中敏，赵梦露，黄冬梅. 基于增强条件公式的主动规则集可终止性判定[J]. J4, 2014, 36(01): 163-168.

XIONG Zhongmin,ZHAO Menglu,HUANG Dongmei. Active rules termination determination
based on enhanced conditional formula [J]. J4, 2014, 36(01): 163-168.

参考文献［15］

［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］	Bailey J, Poulovassilis A, Wood P T. An eventconditionaction language for XML［C］∥Proc of WWW’02, 2002:486495.
［3］	Papamarkos G, Poulovassilis A, Wood P T. RDFTL: An eventconditionaction language for RDF［C］∥Proc of the 3rd Web Dynamics Workshop at WWW’04,2004:223248.
［4］	Papamarkos G,Poulovassilis A,Wood P T.Eventconditionaction rule language for the semantic web［C］∥Proc of Workshop on Semantic Web and Databases,2003:855864.［5］Zoumboulakis M, Roussos G, Poulovassilis A. Active rules for sensor databases［C］∥Proc of the 30th VLDB Conference, 2004:98103.
［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］	Baralis E, Ceri S, Paraboschi S. Compiletime and runtime analysis of active behaviors［J］. IEEE Transactions on Knowledge and Data Engineering, 1998, 10(3):353370.
［8］	Bailey J, Dong Guozhu, Ramamohanarao K. On the decidability of the termination problem of active database system［J］. Theoretical Computer Science, 2004, 311 (13):389437.
［9］	Paton N W, Diaz O. Active database system［J］. ACM Computing Surveys, 1999, 31(1):63103.
［10］	Karadimce A P, Urban S D. Refined triggering graph:A logicbased approach to termination analysis in an active objectoriented database［C］∥Proc of International Conference on Data Engineering (ICDE), 1996:1.
［11］	Baralis E, Widom J. An algebraic approach to static analysis of active database rules［J］. ACM Transactions on Database Systems, 2000, 25(3):269332.
［12］	Hao Zhongxiao, Xiong Zhongmin. An efficient algorithm about computing an irreducible rule set in active database［J］. Journal of Computer Research and Development, 2006, 43(2):281287.(in Chinese)
［13］	Lee S Y, Ling T W. Refined termination decision in active databases［C］∥Proc of International Conference on Database and Expert Systems Applications, 1997:182191.
［14］	Lee S Y, Ling T W. A path removing technique for detecting trigger termination［C］∥Proc of International Conference on Extended Database Technology, 1998:1.
［15］	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 Development, 2006, 43(5):901907.(in Chinese)
	附中文参考文献：
［11］	郝忠孝, 熊中敏. 计算主动数据库中不可归约规则集的有效算法［J］. 计算机研究与发展, 2006, 43(2):281287.
［15］	熊中敏，郝忠孝. 基于活化路径和条件公式的主动规则集可终止性判定方法［J］. 计算机研究与发展, 2006, 43(5):901907.