domingo, 14 de octubre de 2012

La lógica predicativa en las bases de datos.

Como pudimos ver en clase de verificación de software, la lógica predicativa tiene una alta gama de significaciones que la lógica booleana que hemos visto anteriormente, por lo que este tipo de lógica predicativa tiene aplicaciones más diversas, para esta entrada voy a explicar como podemos utilizar la lógica predicativa en las bases de datos.

Primero que nada vamos a definir base de datos, la cual podemos decir que es una colección finita de datos relacionados, por ejemplo un diccionario inglés-español, un directorio de teléfonos, etc...

En una base de datos podemos encontrar los siguientes elementos los cuales podemos representarlos de manera lógica [1]:

  • Un átomo = numero, letra, etc...
    • Representado en lógica como un elemento en el universo.
  • Un registro = una tupla de elementos atómicos.
    • Representado en lógica como un hecho.
  • Una tabla = una colección de registros compatibles.
    • Representado en lógica como una relación.
  • Una base de datos relacionada = una colección de tablas
    • Representado en lógica como una colección de relaciones
  • Una base de datos deductiva = base de datos relacionada incluyendo mecanismos deductivos.
    • Representado en lógica como una base de datos extensional y bases de datos intencionales (esto quiere decir que se incluyen ciertas reglas)
  • Un query = es una herramienta linguistica para seleccionar información.
    • Representado en lógica como una fórmula.

Entonces podemos decir que el modelo de bases de datos deductivo es una restricción de primer orden de la lógica de predicativa en un modelo de datos relacional, este modelo deductivo se hacen relaciones bien definidos extensionalmente a través de hechos o intencionalmente a través de reglas, en donde las reglas pueden ser definidas, como podemos ver en la arquitectura de una base de datos deductiva.

Arquitectura de una base de datos deductiva
Podemos decir que las bases de datos extensionales, las restrucciones de integridad y las queries están presentes en los sistemas tradicionales de bases de datos, lo que se diferencia la base de datos deductivas es que ofrece almacenar reglas deductivas en bases de datos intensionales y proporcionar un mecanismo de deducción.

Se han desarrollado varios lenguajes formales para este tipo de modelo de datos deductiva, por ejemplo existe un lenguaje llamado Datalog [2], un sublenguaje en donde se le llena una base de datos y se ingresan algún query que cumple con lógica predicativa de primer ornen, también lenguajes como Prolog [3], extienden las estructuras de bases de datos complejas utilizando componentes en donde se combinan el lenguaje lógico declarativo con el almacenamiento de datos en base a sus datos y las reglas.

Los hechos en datalog son representados en forma de relaciones NOMBRE(argumento-1, ..... argument-n), donde NOMBRE es el nombre de la relación y argumento son las constantes.
Por ejemplo, DIRECCION(Roberto, 'Calle 13')

Los queries atómicas son representados de la siguiente forma: NOMBRE(argumento-1.... argumento-n), donde los argumentos son constantes o variables que incluyen la variable ''-" negación.

Las reglas en datalog son expresadas de la siguiente forma.
En donde las Z son vectores de variables o constantes en donde cualquier variable que aparece en la parte de la izquierda de ":-" aparece también del lado derecho.

La semántica en datalog es la forma:

En donde todas las variables que aparecen tanto de lado izquierdo como de lado derecho de la regla (llamados cabeza y cuerpo) son universalmente cuantificados, mientras que los que solamente aparecen de lado izquierdo (en el cuerpo) están existencialmente cuantificados.

Entonces en base a los conceptos anteriores voy a desarrollar un ejemplo en donde vamos a utilizar lo anterior, supongamos que necesitamos realizar una base de datos que contenga información acerca de autores de libros, vamos a guardar en una relación, llamada AUTOR y otra relación llamada TITULO de la siguiente manera:
  • AUTOR(Nombre_autor, Id) 
    • Esto significa que el autor cuyo nombre tiene una identificación ID
  • TITULO(Id, Nombre_libro)
    • Esto significa que el autor cuyo numero de ID es autor o coautor de un libro titulado Nombre_libro.
Ahora por ejemplo vamos a definir una nueva relación COAUTOR(Nombre_1, Nombre_2), el cual significa que dichos nombres fueron coautores del libro:

COAUTOR(Nombre_1, Nombre_2) :- AUTOR(Nombre_1, ID_1), TITULO(ID_1, Nombre_libro), AUTOR(Nombre_2, ID_2), TITULO(ID_2, Nombre_libro), Nombre_1 =/= Nombre_2.

Podemos ver que la regla que hemos realizado diciendo que tenemos un número de ID único en donde a esta variable le podemos decir que es una restricción de integridad que cumple con la siguiente semántica:

Entonces este sería una forma de modelar una base de datos por medio del lenguaje Datalog, se puede implementar este tipo de bases en nuestros programas incluyendo la lógica en base a algunas extensiones por ejemplo en python existe pyDatalog [4] en donde de manera sencilla podemos modelar una base de datos deductiva.

Esta sería mi tarea de verificación si tienen alguna duda espero me lo hagan saber.

Bibliografía.
[1] Lectura de la clase lógica de la Universidad de Linkoping liga.
[2] Lenguaje Datalog liga
[3] GNU Prolog website. liga
[4] pyDatalog liga

1 comentario: