Resumen

Los sistemas basados en reglas activas (sistemas activos) ejecutan acciones de manera automática ante la ocurrencia de ciertos eventos, los cuales pueden ser generados dentro o fuera del sistema. La parte medular de tales sistemas la constituye la base de reglas activas, la cual representa el conocimiento que se tiene acerca de un dominio particular. Una regla activa tiene la forma: ON evento IF condición THEN acción, la cual indica la tarea que se debe llevar a cabo cuando ha ocurrido un evento y ciertas condiciones se han cumplido. Este tipo de reglas también se denominan reglas ECA (Evento - Condición - Acción).
Desarrollar sistemas activos no es una tarea sencilla debido a factores como los siguientes: primero, no es fácil decidir las partes del sistema que pueden implementarse mediante reglas activas; segundo, se tiene que analizar el costo que se debe pagar por la introducción de las reglas en la aplicación; tercero, la falta de herramientas de verificación y análisis que ayuden a identificar errores en la base de reglas y examinar si esta realiza adecuadamente las tareas para las que fue diseñada. En la literatura se ha reportado un vasto trabajo relacionado con la verificación de errores en sistemas basados en reglas de producción, las cuales son un caso particular de las reglas activas ya que sólo contienen la parte de la condición y la acción, no así para sistemas activos. Asimismo, se han desarrollado métodos de análisis para las propiedades de terminación y confluencia, algunos de los cuales no determinan con exactitud su cumplimiento. La propiedad de terminación garantiza que el proceso de ejecución de una base de reglas se realiza en un número finito de pasos. La propiedad de confluencia determina si el orden de ejecución de reglas disparadas simultáneamente en un mismo estado del sistema influye en el resultado final que se obtenga.
En este trabajo de tesis se aborda la verificación de errores y el análisis de las propiedades de terminación y confluencia de reglas activas. Las principales aportaciones obtenidas se describen a continuación:

    1. Definiciones de errores de redundancia, inconsistencia, incompletitud y circularidad en el contexto de reglas activas. Hasta el momento, no se han reportado en la literatura relacionada con reglas activas definiciones para los errores mencionados, los conceptos originales sólo consideran reglas de producción. Dado que las reglas activas están formadas por un evento, una condición y una acción, es importante contar con definiciones de errores que consideren todas estas partes ya que el evento hace que estos puedan aparecer en formas más complicadas. Tomando en cuenta esta situación, se analizaron los tipos de errores que aparecen en bases de reglas de producción y, posteriormente, se redefinieron para adaptarlos al contexto de reglas activas. Como resultado se propusieron definiciones para los errores de redundancia, inconsistencia, incompletitud y circularidad que consideran todos las partes componentes de las reglas activas.

    2. Definiciones de errores potenciales. En algunas ocasiones, los errores ocurren sólo hasta que se satisfacen ciertas condiciones. En ese momento, pueden llegar a causar un mal funcionamiento de la base de reglas y, por lo tanto, deben prevenirse. Este tipo de errores los denominamos errores potenciales. Entre ellos están las reglas en conflicto potencial, las cuales pueden generar inconsistencia sólo cuando el resultado de la evaluación de sus condiciones es verdadero. Al conocer los errores potenciales que existen en la base de reglas se pueden tomar medidas para manejarlos cuando sucedan o, incluso, rediseñar el conjunto de reglas para eliminarlos.

    3. Método de verificación de errores basado en la CCPN. A partir del conjunto de definiciones se desarrolló un método de detección de errores basado en una extensión de las redes de Petri llamada Red de Petri Coloreada Condicional (CCPN, por sus siglas en inglés Conditional Colored Petri Net). El modelo de CCPN representa con claridad cada elemento de la regla así como su interacción. El método consta de dos etapas: primero, usando la CCPN se identificaron patrones que caracterizan a las reglas que pueden contener errores y se aprovechó la matriz de conexión de la CCPN para detectarlos automáticamente. Segundo, se extrajeron las reglas identificadas por los patrones y se analizó su interacción para determinar con exactitud la ocurrencia de algún tipo de error.

    4. Método de análisis de las propiedades de confluencia y terminación basado en la CCPN. El método de análisis de las propiedades de confluencia y terminación desarrollado está basado en la CCPN y consta de dos partes. En la primera de ellas, usando la CCPN, se identificaron los patrones que caracterizan reglas que pueden no terminar y reglas que pueden no ser confluentes. En la segunda parte, se desarrollaron algoritmos para analizar la interacción de las reglas identificadas a través de los patrones y así concluir acerca del cumplimiento de las propiedades. La ventaja que tienen estos enfoques de verificación de errores y análisis de propiedades de terminación y confluencia es que no necesitan examinar todas las reglas para formular conclusiones. El identificar patrones en la CCPN permite centrarse sólo en aquellas reglas que puedan ser incorrectas.

    5. Desarollo de la herramienta ECAPNVerifier. ECAPNVerifier es un sistema que permite verificar una base de reglas de forma automática. Esta herramienta se integró a ECAPNSim, el cual es un sistema que genera la CCPN de una base de reglas así como su correspondiente matriz de conexión.

Active rule-based systems (active systems) respond automatically to events that are taking place inside or outside the system itself. The most important element of active systems is the rule base which represents knowledge about a particular area. An active rule of the rule base is written as follows: ON event IF condition THEN action. It specifies the task which has to be performed when an important event happens and some conditions are met. This kind of rules are also called ECA (Event - Condition - Action) rules. Developing a rule base is commonly perceived as a difficult task for a variety of reasons, first, it is not obvious which parts of an application should be supported using active mechanisms, second, what performance penalty is likely to result from the use of rules, and third, the verification and analysis tools which detect errors and determine if the rule base properly fulfills its goal may be minimal. Many works on error verification using production rules, which are a special case of active rules since they only have condition and action parts, have been reported in specialized literature. However, to the best of our knowledge, there is no enough work about error verification usign active rules. Also, many works about confluence and termination properties analysis have been published. But, some of them cannot draw conclusion accurately. Confluence property guarantees that the final result of rules triggered at the same time will be the same independently of their execution order. Termination property guarantees that rule processing will be done in a finite number of steps. This thesis tackles error verification and confluence and termination analysis properties in active rule base. In the following we describe our main contributions:

    1. Definitions for redundancy, inconsistency, incompleteness and circularity errors using active rules. Up to date, there isn't any report in literature about active rules related with definitions of mentioned errors, original conceptions only take into account production rules. Since active rules consist of an event, a condition and an action, it is important to have error definitions which consider all these parts because of event makes errors to appear in more complicated ways. Considering this situation, errors which appear in production rule base were analized and, later, they were redefined to adapt them to active rule context. As result we obtained definitions for redundancy, inconsistency, incompleteness and circularity errors which take into account all the rule's parts.

    2. Definitions of potential errors. Potential errors are those which can cause a bad performance of the rule base at a specific moment and, therefore, they have to be prevented. Among potential errors are potential conflicting rules which can cause inconsistency only when their conditions may be true at the same time. If potential errors are discovered it is possible to formulate ways to deal with them when they happen, or even the rule base can be designed again to take away potential errors.

    3. CCPN-based method to verify errors in an active rule base. From above definitions we developed an error verification method, which is based on a Petri net extension called Conditional Colored Petri Net (CCPN). CCPN model represents each rule element as well as their interaction. Our method consists of two parts: first, using CCPN we identified patterns which characterize rules with errors and took advantage of its incidence matrix representation to automatically detect them. Second, we extract the rules represented identified by patterns and we analyzed their interaction to draw conclusion about errors.

    4. CCPN-based method to analyze confluence and termination properties. We developed a method for analyzing above properties which is based on CCPN. Our method is performed in two stages: first, we identify those CCPN structures which depict nonconfluence and non-termination problems. Second, we analyzed rule interaction of rules represented by above structures and we conclude about confluence and termination.  The great advantage of our verification and analysis method is that we can draw conclusion about errors and fulfillment of confluence and termination properties with no need to test all the rules pairs in the rule base. Using CCPN we can focus our test on the rules which may be wrong.

    5. ECAPNVerifier development. ECAPNVerifier is a software system which verifies an active rule base automatically. It was integrated into a more robust tool called ECAPNSim which can generate a CCPN and its corresponding incidence matrix form an active rule base.