Abstract
Especially during the design and tuning of active rules, it is possible that rule execution enters an endless loop, where rules “cascade” by triggering each other indefinitely, so that their processing does not terminate. Commercial systems detect this situation in a simple way, by keeping counters on the number or depth of cascading rules, and suspending an execution when the counters exceed given thresholds. However, the setting of these counters is quite critical: too low thresholds may cause the halting of rule processing in absence of loops, too high thresholds may reveal a loop only after an expensive processing.
In this paper, we propose a technique for revealing loops, which is based on recognizing that a given situation has already occurred in the past and therefore will occur an infinite number of times in the future. This technique is potentially very expensive, therefore we explain how it can be implemented in practice with limited computational effort. A particular use of this technique allows to develop cycle monitors, which check at run time that critical rule sequences, detected at compile time, do not repeat forever.
Research presented in this paper is supported by Esprit project P6333 IDEA, and by ENEL contract “VDS 1/94: Integrity Constraint Management”
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Agrawal, R. J. Cochrane, and B. Lindsay. On maintaining priorities in a production rule system. In G. M. Lohman, A. Sernadas, and R. Camps, editors, Proc. Seventeenth Int'l Conf. on Very Large Data Bases, pages 479–487, Barcelona, Spain, Sept. 1991.
A. Aiken, J. Widom, and J. M. Hellerstein. Behavior of database production rules: Termination, confluence, and observable determinism. In M. Stonebraker, editor, Proc. ACM SIGMOD Int'l Conf. on Management of Data, pages 59–68, San Diego, California, May 1992.
E. Baralis, S. Ceri, and S. Paraboschi. Improved rule analysis by means of triggering and activation graphs. In T. Sellis, editor, Proc. of the Second Workshop on Rules in Databases Systems, LNCS, Athens, Greece, Sept. 1995. To appear.
E. Baralis and J. Widom. An algebraic approach to rule analysis in expert database systems. In Proc. Twentieth Int'l Conf. on Very Large Data Bases, pages 475–486, Santiago, Chile, Sept. 1994.
L. Brownston, R. Farrell, E. Kant, and N. Martin. Programming Expert Systems in OPS5: An Introduction to Rule-Based Programming. Addison-Wesley, 1985.
S. Ceri, P. Fraternali, S. Paraboschi, and L. Tanca. Automatic generation of production rules for integrity maintenance. ACM Transactions on Database Systems, 19(3):367–422, Sept. 1994.
S. Ceri, P. Fraternali, S. Paraboschi, and L. Tanca. Active rule management in Chimera. In J. Widom and S. Ceri, editors, Active Database Systems. Morgan-Kaufmann, San Mateo, California, 1995.
S. Ceri and J. Widom. Deriving production rules for constraint maintenance. In D. McLeod, R. Sacks-Davis, and H. Schek, editors, Proc. Sixteenth Int'l Conf. on Very Large Data Bases, pages 566–577, Brisbane, Australia, Aug. 1990.
S. Ceri and J. Widom. Managing semantic heterogeneity with production rules and persistent queues. In R. Agrawal, S. Baker, and D. Bell, editors, Proc. Nineteenth Int'l Conf. on Very Large Data Bases, pages 108–119, Dublin, Ireland, Aug. 1993.
S. Ceri and J. Widom. Deriving incremental production rules for deductive data. Information Systems, 19(6):467–490, Nov. 1994.
U. Dayal, M. Hsu, and R. Ladin. Organizing long-running activities with triggers and transactions. In H. Garcia Molina and H. V. Jagadish, editors, Proc. ACM SIGMOD Int'l Conf. on Management of Data, pages 204–214, Atlantic City, New Jersey, May 1990.
O. Diaz, A. Jaime, and N. Paton. DEAR: A DEbugger for Active Rules in an object-oriented context. In N. W. Paton and M. H. Williams, editors, Proc. of First Workshop on Rules in Database Systems, WICS, pages 180–193, Edinburgh, Scotland, Aug. 1993. Springer-Verlag, Berlin.
Digital Equipment Corporation. Rdb/VMS — SQL Reference Manual. Nov. 1991.
J. Gray and A. Reuter. Transaction Processing Concepts and Techniques. Morgan Kaufmann Publishers, 1993.
E. Hanson. Rule condition testing and action execution in Ariel. In M. Stonebraker, editor, Proc. ACM SIGMOD Int'l Conf. on Management of Data, pages 49–58, San Diego, California, May 1992.
A. P. Karadimce and S. D. Urban. Conditional term rewriting as a formal basis for analysis of active database rules. In Proc. Fourth International Workshop on Research Issues in Data Engineering RIDE-ADS '94, Houston, Texas, Feb. 1994.
P. Loucopoulos. Requirements engineering: Conceptual modelling and CASE perspectives. Technical report, COMETT/FORMITT Course on Conceptual Modelling, Databases and CASE, Lausanne, Switzerland, Oct. 1994.
S. Paraboschi. Automatic Rule Generation for Constraint and View Maintenance in Active Databases. PhD thesis, Politecnico di Milano — Dipartimento di Elettronica e Informazione, Jan. 1994. In Italian.
W. W. Peterson and D. T. Brown. Cyclic codes for error detection. Proceedings IRE, 49:228–235, Jan. 1961.
L. van der Voort and A. Siebes. Termination and confluence of rule execution. In Proc. of the Second International Conference on Information and Knowledge Management, Washington DC, Nov. 1993.
J. Widom and S. Ceri. Active Database Systems. Morgan-Kaufmann, San Mateo, California, Aug. 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Baralis, E., Ceri, S., Paraboschi, S. (1995). Run-Time detection of non-terminating active rule systems. In: Ling, T.W., Mendelzon, A.O., Vieille, L. (eds) Deductive and Object-Oriented Databases. DOOD 1995. Lecture Notes in Computer Science, vol 1013. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60608-4_33
Download citation
DOI: https://doi.org/10.1007/3-540-60608-4_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60608-6
Online ISBN: 978-3-540-48460-8
eBook Packages: Springer Book Archive