PDF de programación - Desarrollo de reglas ECA en Bases de Datos, un enfoque de Red de Petri

CENTRO de INVESTIGACIÓN
y de ESTUDIOS AVANZADOS

del IPN



DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION



Desarrollo de reglas ECA en Bases de Datos,

un enfoque de Red de Petri

Tesis que Presenta el:

M. en C. Joselito Medina Marín1



para obtener el grado de Doctor en Ciencias en
la especialidad de Ingeniería Eléctrica Opción



Computación

Director de la tesis

Dra. Xiaoou Li



17 de octubre de 2005



México, D.F.



1Becario de CONACYT no. 158604



Desarrollo de reglas ECA en Base de Datos Activas,

Un enfoque de Red de Petri

Joselito Medina Marín

17 de octubre de 2005

2

Índice general

. Agradecimientos

. Resumen

. Abstract

1

3

5

1. Introducción

1.1. Estado del Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .

7
9
9
1.1.1. Sistemas Manejadores de BD comerciales
1.1.2. Sistemas Manejadores de BD no comerciales . . . . . . . . . . . . . . . . . . . 11
1.2. Motivación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3. Planteamiento del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Objetivos
1.4.1. Objetivo general
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.2. Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.5. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6. Descripción del trabajo
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6.1. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.6.2. Organización de la tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2. Sistema de Base de Datos Activa

21
2.1. Sistema de Base de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.1.1. Modelos de Datos

ii

ÍNDICE GENERAL

2.2. Comportamiento activo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2.1. Modelo de conocimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2.2. Modelo de ejecución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2.3. Análisis de reglas ECA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3. Sintaxis de reglas en BDA existentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3.1. Postgres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.2. SAMOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.3.3. Ariel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.3.4. Starburst
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.5. A-RDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.6. Chimera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3.7. HiPAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3.8. Ode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.9. Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3.10. Informix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3. Conceptos básicos de Redes de Petri

49
3.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2. Representación de la estructura de la Red de Petri
. . . . . . . . . . . . . . . . . . . 52
3.3. Disparo de transiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4. Poder de representación de las PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.5. Propiedades de PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.6. Métodos de análisis de PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.6.1. Simulación de una PN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.7. Red de Petri Coloreada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.8. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4. Red de Petri Coloreada Condicional

71
4.1. Definición de Red de Petri Coloreada Condicional . . . . . . . . . . . . . . . . . . . . 72
4.2. Elementos de la CCPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

ÍNDICE GENERAL

iii

4.3. Modelación de reglas ECA con CCPN . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3.1. Algoritmo de conversión de reglas ECA a CCPN . . . . . . . . . . . . . . . . 82
4.4. Ejecución de la CCPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.5. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.6. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5. Modelación de Eventos Compuestos

103
5.1. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.1. SAMOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.1.2. ODE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.3. Snoop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.4. EPL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.1.5. CEDAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.1.6. Sistemas comerciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2. Eventos Compuestos en CCPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2.1. Conjunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2.2. Disyunción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2.3. Negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
5.2.4. Secuencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2.5. Simultáneo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.2.6. Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
5.2.7. Primero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.2.8. Último . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.2.9. Alguno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
5.3. Algoritmo de conversión de un evento compuesto a una CCPN . . . . . . . . . . . . 122
5.4. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.5. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

6. Análisis de Terminación y Confluencia

141
6.1. Problemas de análisis estático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.1.1. No terminación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

iv

ÍNDICE GENERAL

6.1.2. Confluencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.2. Estado del arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.3. Matriz de Incidencia de CCPN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.4. Analisis de Terminación y Confluencia con CCPN . . . . . . . . . . . . . . . . . . . . 148
6.4.1. Rutas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.4.2. Análisis de Terminación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
6.4.3. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
6.4.4. Análisis de Confluencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.5. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

7. ECAPNSIM

161
7.1. Ambiente de desarrollo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.2. Arquitectura de ECAPNSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
7.2.1. Kernel de ECAPNSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.2.2. Herramientas de ECAPNSim . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
7.3. Diagrama de clases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
7.4. Diseño e Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
7.5. Plataforma independiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.5.1. Base de reglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
7.5.2. MS Access
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.5.3. FoxPro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
7.5.4. Postgresql . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
7.6. Comentarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

8. Caso de estudio

9. Conclusiones y trabajo futuro

. Publicaciones

. Bibliografía

195

207

213

215

Agradecimientos

A Dios, por darme la oportunidad de existir y fuerzas para salir adelante.
En especial a mi esposa, quien me motivó y me