PDF de programación - La Diagnosis basada en modelos: Un caso de estudio

Labelled Object−Oriented Relational

Constraint Databases

La Diagnosis basada en modelos: Un caso de

estudio

Ma Teresa Gómez López

[email protected]

Supervisado por los doctores Rafael Martínez Gasca y Carmelo del Valle Sevillano

Memoria del Periodo de Investigación en Lenguajes y Sistemas Informáticos.

Prefacio

Este trabajo es presentado como memoria del Periodo de Investigación en Lenguajes

y Sistemas Informáticos de la Universidad de Sevilla. La misma contiene los resultados

obtenidos en investigaciones llevadas a cabo en el Departamento de Lenguajes y Sistemas

Informáticos, durante el período comprendido entre febrero de 2003 y junio de 2005, bajo la

dirección de los doctores Rafael Martínez Gasca y Carmelo Del Valle Sevillano, Profesores

Titulares del Departamento de Lenguajes y Sistemas Informáticos de la Universidad de

Sevilla.

[email protected]
Departamento de Lenguajes y Sistemas Informáticos

Ma Teresa Gómez López

Universidad de Sevilla

España, Junio de 2005.

Índice general

1. Introducción

1.1. Contexto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1. Un ejemplo motivador

. . . . . . . . . . . . . . . . . . . . . . . . .

1.2. Problemas detectados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3. Aportaciones

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4. Publicaciones Relacionadas con el Período de Investigación . . . . . . . . .

5

6

7

7

8

9

1.5. Proyectos de Investigación . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.6. Organización del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2. Estado del Arte

15

2.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2. Formalizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.1. Lógica y Modelos de primer orden . . . . . . . . . . . . . . . . . . . 19

2.2.2. Formalización de las Bases de Datos con Restricciones

. . . . . . . 20

2.2.3. Modelado de Relaciones Restrictivas

. . . . . . . . . . . . . . . . . 22

2.2.4. Consultas sobre restricciones . . . . . . . . . . . . . . . . . . . . . . 23

2.2.5. Evaluación de consultas en sistemas en bases de datos con restricciones 24

2.2.6. Bases de Datos con Restricciones orientadas a objetos . . . . . . . . 24

2.3. Prototipos de bases de datos con restricciones

. . . . . . . . . . . . . . . . 26

2.3.1. Sistema DISCO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.2. MLPQ/PReSTO: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.3. DEDALE:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.4. CCUBE: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.5. CQA/CDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.3.6. DeCoR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2.3.7. Comparativas e inconvenientes de las Herramientas . . . . . . . . . 35

3. Técnicas utilizadas

37

3.1. Bases de Gr¨obner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.2. Descomposición Algebraica Cilíndrica . . . . . . . . . . . . . . . . . . . . . 38

3.3. Problemas de Satisfacción de Restricciones . . . . . . . . . . . . . . . . . . 40

3.3.1. Problemas de Consistencia de Restricciones

. . . . . . . . . . . . . 41

3.3.2. Problemas de Optimización con Restricciones

. . . . . . . . . . . . 42

3.3.3. Herramientas: OPL Studio y JSolver

. . . . . . . . . . . . . . . . . 42

4. Diagnosis: Un caso de estudio

45

4.1. Definiciones y Notación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2. Ejemplo de Diagnosis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5. Arquitectura para una LORCDB

6. Creación de una LORCDB

51

57

6.1. Creación de una LORCDB . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.2. Creación de tablas con restricciones en una LORCDB . . . . . . . . . . . . 58

6.3. Añadir información a tabla . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

7. Consultas a una LORCDB

61

7.1. Encontrar las restricciones relacionadas con la consulta . . . . . . . . . . . 62

7.2. Decidir qué parte de la arquitectura se debe usar

. . . . . . . . . . . . . . 67

7.3. Ejemplos de Consultas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

7.3.1. Técnicas de sustitución Simbólica . . . . . . . . . . . . . . . . . . . 70

7.3.2. Técnica Cuasi Simbólica . . . . . . . . . . . . . . . . . . . . . . . . 76

7.3.3. Consultas para Restricciones Lineales . . . . . . . . . . . . . . . . . 77

7.3.4. Consultas para Restricciones Polinómicas . . . . . . . . . . . . . . . 79

8. Conclusiones y Trabajos Futuros

81

Índice de figuras

1.1. Ejemplo Motivador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1. Figura representada por la fórmula ϕt

. . . . . . . . . . . . . . . . . . . . 23

3.1. Ejemplo de Descomposición algebraica cilíndrica

. . . . . . . . . . . . . . 39

4.1. Ejemplo introductorio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.2. Red de Contextos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.1. Ejemplo de Diagnosis

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.2. Arquitectura del sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.1. Tablas para indexar restricciones y variables . . . . . . . . . . . . . . . . . 58

6.2. Tablas ejemplo con restricciones almacenadas

. . . . . . . . . . . . . . . . 60

7.1. Sistema con las restricciones analizadas en la consulta

. . . . . . . . . . . 63

7.2. ConstraintList del ejemplo (I) . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3. ConstraintList para el ejemplo (II)

. . . . . . . . . . . . . . . . . . . . . . 66

7.4. Contenido de la lista ConstraintList

. . . . . . . . . . . . . . . . . . . . . 72

7.5. Búsqueda de más grupos de restricciones relacionadas

. . . . . . . . . . . 73

7.6. Una parte del ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.7. Ejemplo de CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

7.8. Ejemplo de COP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

Mis padres me enseñaron a luchar todos los días para conseguir lo que quería y mi

marido me da fuerzas para poderlo hacer.

Capítulo 1

Introducción

Las bases de datos relacionales han avanzado para dar soluciones cada vez más versáti-

les y potentes al tratamiento de datos discretos. Sin embargo, el almacenamiento y pro-

cesado de datos continuos es aún un área por desarrollar. Para almacenar y tratar in-

formación continua en una base de datos relaciona, como en los sistemas geográficos, es

necesaria la discretización de los datos. Es obvia la pérdida de información y la saturación

que eso conllevaría en la base de datos. Sin embargo, si se tuviera la capacidad de almace-

nar la ecuación en sí, la información sería completa y el espacio necesario para almacenarla

muy pequeño. De forma que es necesario buscar alternativas para no tener que discretizar

la información. No sólo encontramos este problema en los sistemas geográficos, sino en

todos los sistemas cuyo comportamiento depende de parámetros cuyos valores concretos

son desconocidos, variables o venga definido por una función matemática.

La idea que originó el desarrollo de este trabajo fue la necesidad de obtener una

nueva forma de almacenar la información, como la espacio-temporal, científica, médica

o datos de ingeniería. Ante estos requisitos, las actuales bases de datos convencionales

tienen importantes limitaciones de almacenamiento y representación, ya que los soportes

físicos imponen un tamaño finito. Por ejemplo, para almacenar el comportamiento de una

función en una base de datos relacional, sería necesario discretizar la información, lo que

conllevaría un crecimiento de la base de datos. Además hay que tener en cuenta que tener

bases de datos de gran tamaño provoca grandes retrasos en la obtención y modificación

de la información almacenada. Este tipo de información hace necesario buscar otra forma

de representar y almacenar comportamientos en forma de restricciones sin necesidad de

discretizar la información.

6

Capítulo 1. Introducción

Los desarrollos en este campo vienen motivados ante la necesidad de nuevas formas de

almacenamiento, debido a la existencia de gran cantidad de datos de carácter continuo. De

esta manera, es necesario proveer de un lenguaje de consulta que permita a los usuarios

consultar la información restrictiva almacenada en una base de datos convencional de una

forma eficiente, compacta y transparente.

1.1. Contexto

Para abordar esta propuesta, se partió de un modelo de datos ya introducido en

[KLP98], fundamentado en considerar una tupla en una base de datos como un conjunto

de restricciones de igualdad o desigualdad en los atributos de dicha tupla, ya que las

restricciones son un mecanismo natural de especificar las consultas de similitud en series

de datos. Para mostrar esta idea se utiliza la representación mediante restricciones de un

área rectangular:

{1 ≤ y ≤ 5; 2 ≤ x ≤ 4}

Si se utiliza una bases de datos relacional para almacenar estas restricciones, una forma

sería almacenar la restricción mediante los puntos que la acotan: (2, 1), (2, 5), (4, 1), (4, 5).

De esta manera, se obtiene una manera válida de representar puntos, segmentos, líneas,

cubos o caminos. Sin embargo, Esta solución no es buena principalmente por dos razones:

no todos los tipos de restricciones pueden ser representadas de esta forma; y por la evidente

pérdida de simbología, haciendo mucho más difícil la inferencia de nueva información.

Ante estas necesidades aparecieron las bases de datos con restricciones (Constrain