Bases de datos deductivas.



Introducción y definición


Un sistema de base de datos deductiva, es un sistema de base de datos pero con la característica de que a través información extensional de reglas y hechos se pueden deducir o inferir información adicional a la que tenemos almacenada en nuestra base de datos. El lenguaje más usado para este tipo de bases de datos es el Datalog.Deductivas.jpg
Fig. 1: Esquema base de datos deductiva


Este tipo de bases de datos surgieron en la década de los ochenta y ha permitido aportar al campo de las bases de datos resultados y desarrollos fundamentales en el campo de la lógica, la programación lógica y la inteligencia artificial, además de ser muy usadas en campos como la deducción automática.
Estas bases de datos tienen un gran nivel de lógica matemática, la cual guarda una estrecha relación con la computación, y debido a esto se les suele llamar en diferentes artículos y libros “bases de datos lógicas”.
La gran finalidad de este tipo de bases de datos es conseguir guardar el mayor número de datos a través de un programa lógico, un mapeo de relaciones hacia hechos y reglas que son usadas para definir nuevas y futuras relaciones. Así pues, se intenta minimizar los datos requeridos en la memoria principal para guardar una determinada información.
Las bases de datos deductivas utilizan de base dos tipos de especificaciones: hechos y reglas. Los hechos se especifican de manera similar a las relaciones y las reglas especifican relaciones virtuales que no están almacenadas en memoria pero que se pueden obtener a partir de los hechos aplicando una lógica de conocimiento.

Representación de la información



sistema.jpg
Fig.2: Derivación de la información


Hechos

Conocidos como la base de datos extensional (EDB):
Los hechos corresponden a las tuplas en una base de datos relacional. La única diferencia es que se indica el nombre del tupla pero no se indican los nombres de los atributos. Recordemos que una tupla en una relación intenta describir algún hecho del mundo real cuyo significado queda determinado en parte por los nombres de los atributos. En una Base de Datos Deductiva, el significado del valor del atributo en una tupla queda determinado exclusivamente por su posición dentro de la tupla.

Reglas

Referidos como la base de datos intensional (IDB):
Guardan un ligero parecido a las vistas relacionales, indican cómo deducir hechos nuevos a partir de los hechos almacenados y cómo deducir relaciones indirectas entre las entidades. Estas reglas se escriben, normalmente, usando un lenguaje declarativo y, por lo tanto, se indica lo que se desea pero no se indica el algoritmo para llegar a esa meta. El motor de inferencia es el que implementa el algoritmo para deducir nuevos hechos y relaciones a partir de las reglas y los hechos almacenados.

Por tanto, las bases de datos deductivas combinan el modelo relacional para representar los datos con el modelo de la programación lógica para la representación y manejo de las reglas.

Sistema de inferencia

Una máquina de inferencia (o mecanismo de deducción) dentro del sistema puede deducir hechos nuevos a partir de la base de datos interpretando las reglas. El modelo empleado en las BDDs está íntimamente relacionado con el modelo de datos relacional, y sobre todo con el formalismo del cálculo relacional. También está relacionado con el campo de la programación lógica y el lenguaje Prolog. Los trabajos sobre BDDs basados en lógica han utilizado Prolog como punto de partida.
Con Datalog, lenguaje similar al Prolog, se definen reglas declarativamente junto con un conjunto de relaciones existentes que se tratan como literales en el lenguaje. Aunque la estructura gramatical se parece a la de Prolog, su semántica operativa es diferente y nos da la oportunidad de trabajar con datos que no estén en memoria principal, es decir, la capacidad de manejar bases de datos más grandes.

Existen principalmente dos tipos de inferencia computacional basados en la interpretación de las reglas por la teoría de la demostración:
  • Mecanismo de inferencia ascendente: También llamado encadenamiento hacia delante o resolución ascendente. La máquina de inferencia parte de los hechos y aplica las reglas para generar hechos nuevos. Conviene usar una estrategia de búsqueda para generar sólo los hechos que sean pertinentes a una consulta.
  • Mecanismo de inferencia descendente: También llamado encadenamiento hacia atrás o resolución descendente. Parte del predicado que es el objetivo de la consulta e intenta encontrar coincidencias con las variables que conduzcan a hechos válidos de la base de datos. Retrocede desde el objetivo buscado para determinar hechos que lo satisfacen. Si no existieran los hechos que buscamos, el sistema entonces buscará la primera regla cuya cabeza (LHS) tenga el mismo nombre de predicado que la consulta.

Lenguaje de programación


Datalog

Datalog es el lenguaje utilizado para la manipulación de las bases de datos deductivasy es sintácticamente un subconjunto del lenguaje Prolog . Hay dos tipos de Datalog: con recursión y sin recursión.
Datalog sin recursión tiene el mismo poder expresivo que el álgebra relacional.
Datalog con recursión permite expresar consultas que no se pueden satisfacer en SQL2. Sin embargo, SQL:1999 ha usado la solución para la recursión en Datalog para el desarrollo de consultas recursivas.
Datalog es similar a Prolog en su sintaxis, pero en su semántica operacional es diferente. La interpretación de una colección de predicados asigna cierto o falso a cada posible instancia de los predicados, donde los argumentos se escogen de un conjunto infinito de constantes. La interpretación se representa habitualmente por el conjunto de instancias verdaderas.
Datalog evalúa las consultas mediante la evaluación de cada regla y cada regla es evaluada examinando todos los hechos, ya sean hechos almacenados o hechos derivados, que unifican cada predicado en el cuerpo de una regla. Si alguna colección de hechos unifica con cada predicado en el cuerpo de una regla, se produce un nuevo hecho que corresponderá al encabezado de la regla

Sintáxis


Este tipo de bases de datos se componen de cláusulas de Horn que constituyen reglas de tipo "modus ponendo pones", lo que quiere decir que si es verdad el antecendente será verdad el consecuente. En este caso se escribe al revés, primero el consecuente y después el antecedente.
El antecedente suele ser una secuencia de objetivos, que formarán un conjunto de condiciones que ha de cumplirse para poder llegar a la conclusión del consecuente. Cada objetivo se separa de una "," y se puede considerar una llamada similar a una instrucción o un procedimiento.
Si los argumentos son constantes se toma el predicado como verdadero, si son variables se considera consulta o parte de una regla o restricción.

%hechos
hombre(teraj).
hombre(abraham).
hombre(najor).
hombre(haran).
hombre(lot).
mujer(sarai).
mujer(melca).
mujer(jesca).
padre(teraj,sarai).
padre(teraj,abraham).
padre(teraj,najor).
padre(teraj,haran).
padre(abraham,ismael).
padre(abraham,isaac).
padre(najor,batuel).
padre(haran,melca).
padre(haran,jesca).
padre(haran,lot).
casado(abraham,sarai).
casado(najor,melca).

%reglas
hijo(X,Y) :-
hombre(X),(padre(Y,X);madre(Y,X)).

hija(X,Y) :-
mujer(X),(padre(Y,X);madre(Y,X)).

abuelo(X,Y) :-
padre(X,Z),(padre(Z,Y);madre(Z,Y)).

abuela(X,Y) :-
madre(X,Z),(padre(Z,Y);madre(Z,Y)).

hermano(X,Y) :-
(X\==Y),hombre(X),hijo(X,Z),(hijo(Y,Z);hija(Y,Z)).

hermana(X,Y) :-
(X\==Y),mujer(X),hija(X,Z),(hijo(Y,Z);hija(Y,Z)).

tio(X,Y) :-
hermano(X,Z),(padre(Z,Y);madre(Z,Y)).

tia(X,Y) :-
hermana(X,Z),(padre(Z,Y);madre(Z,Y)).


Para hacer una consulta utilizamos una cláusula de Horn con uno de los parámetros vacíos (poniendo una variable en lugar donde queremos recibir los datos)

Ejemplo de consultas:

?-padre(X,sarai)
X=teraj
YES

?-madre(X,isaac)
X=sarai
YES

?-padre(X,isaac)
X=abraham
YES


?-padre(X,abraham)
X=teraj
YES

?-abuelo(X,isaac)
X=teraj
X=teraj
YES.


Al final de la ejecución, la variable contendrá los valores de la consulta y devolverá un booleano con el resultado de la recorrida del árbol. Puede ser que si no se diseñan bien las reglas se caiga en un bucle infinito y nunca acabe la deducción.


Ventajas e inconvenientes


  • Ventajas

    1. Almacenamiento de pocos datos. Esto se debe gracias a que utiliza un mapeo de relaciones entre datos y reglas, con lo que se minimiza la cantidad de datos almacenados.
    2. Ofrecen reglas que permiten crear combinaciones de datos. Lo que ayuda mucho a recoger una mejor semántica del problema.
    3. Soportan objetos y conjuntos complejos. Al igual que en el punto anterior ayuda a recoger mucho mejor la semántica del problema y además lo hace más modulable.
    4. Ofrecen la capacidad de expresar consultas por medio de reglas lógicas. De esta forma las consultas pueden obtener de una manera más optimizada los datos requeridos, sin tener que hacer otro paso posterior por un optimizador de consultas.
    5. Permiten consultas recursivas y algoritmos eficientes para su evaluación. Este tipo de bases de datos fue uno de los primeros en proporcionar las consultas recursivas. La eficiencia de los algoritmos nos lleva a obtener consultas más optimizadas.
    6. Cuentan con métodos de optimización que garantizan la traducción de especificaciones dentro de planes eficientes de acceso.
    7. Cuentan con negaciones estratificadas.

  • Inconvenientes

    1. Poder encontrar criterios de interpretación para las reglas deductivas. Es complicado poder encontrar buenos criterios de evaluación para las reglas lógicas por lo que es muy difícil sacar todo su potencial.
    2. Replantear correctamente, en un contexto deductivo, las convenciones habituales en una base de datos.
    3. Desarrollar procedimientos eficaces de deducción. Es una de las tareas más difíciles que implican trabajar con este tipo de base de datos. Cuanto más eficaces sean los procedimientos más productividad obtendremos de las bases de datos deductivas.


Posibles aplicaciones



- Modelado de empresas: este dominio implica modelar la estructura, los procesos y las restricciones dentro de una empresa. Los datos relacionados con ella pueden resultar en modelo ER extendido que contiene cientos de entidades y vínculos y miles de atributos. Es posible desarrollar varias aplicaciones útiles para los diseñadores de nuevas aplicaciones (así como para los gerentes) a partir de esta ”metabase de datos”, que contiene información tipo diccionario acerca de toda la empresa.

- Prueba de hipótesis o dragado de datos: este dominio implica formular una hipótesis, traducirla a un conjunto de reglas LDL y una consulta, y luego ejecutar la consulta contra los datos para probar la hipótesis. El proceso se repite reformulando las reglas y la consulta. Esto se ha aplicado al análisis de datos de genoma en el campo de la microbiología. El dragado de datos consiste en identificar las secuencias de DNA a partir de auto radiografías digitalizadas de bajo nivel obtenidas de experimentos con bacterias E. coli.

- Reutilización de software: el grueso del software para una aplicación se desarrolla en código estándar por procedimientos, y una pequeña fracción se basa en reglas y se codifica en LDL. Las reglas dan origen a una base de conocimientos que contienen los siguientes elementos:
    • Una definición de cada módulo C empleado en el programa.
    • Un conjunto de reglas que define las formas en que los módulos pueden exportar/importar funciones, restricciones, etc.

Ejemplos de uso


Un ejemplo de software construido apoyándose en una base de datos deductiva es el "Proyecto MYDDAS" una aplicación capaz de hacer un control en tiempo real de una red de sensores móviles.


PACADE sistema creado para el análisis de la estructura de las proteínas en 3 dimensiones.



Previsión de futuro


A pesar de ser un tipo de base de datos en desuso, se pueden encontrar algunas investigaciones en las que se plantean nuevas formas
para aprovechar el potencial de las mismas.
Algunos de estos artículos utilizan las deductivas[2] , en conjunción a las difusas, para poder extraer hechos aplicando las reglas.
Por otra parte en otros artículos[4] utilizan las características de este tipo de bases de datos para la captación de datos y eliminación de "ruidos" (en dichos datos) aplicando reglas escritas por ingenieros conocedores tanto de las características de los sensores como de la interpretación de los datos.
Otra rama[3] investiga acerca de la utilización de éstas junto con la minería de datos para poder extraer información a través de reglas/consultas poco elaboradas del estilo:
‘‘give an alarm to the regions when there is a strong possibility of flooding because of high level of rainfall’’.

Todos los estudios tienen algo en común, pretenden dotar de más "inteligencia" a las bases de datos, que sean capaces de llegar más allá con los datos que las proporcionamos sin sobre esfuerzo por nuestra parte.

Conclusión


Las bases de datos deductivas surgieron en la época de los ochenta y desde entonces no han sido muy usadas a nivel comercial, pero sí en entornos de investigación y campos de las ciencias aplicadas. Estudios recientes indican que este tipo de bases de datos son usadas un 4/4 en entornos científicos, 2/4 en entornos industriales y 1/4 en entornos comerciales.
Además, desde entonces las bases de datos deductivas no han sufrido una gran evolución dada la complejidad a la hora el uso de las mismas y falta de investigación y desarrollo en este campo.
Para poder manejar este tipo de bases de datos hace falta tener conocimiento en el manejo de reglas deductivas, campo que es bastante complejo y no ha sido muy estudiado a nivel de bases de datos. Además, este tipo de bases de datos no ofrece ningún atractivo al entorno empresarial o de uso individual.

Referencias


Cálculo relacional.

Logic Data Language(LDL)