Forma Clausal y Clausula de Horn

Cláusula de Horn

En lógica proposicional, una fórmula lógica es una cláusula de Horn si es una cláusula (disyunción de literales) con, como máximo, un literal positivo. Se llaman así por el lógico Alfred Horn, el primero en señalar la importancia de estas cláusulas en 1951.Esto es un ejemplo de una cláusula de Horn:

Una fórmula como esta tambien puede reescribirse de forma equivalente como una implicacion:

Una cláusula de Horn con exactamente un literal positivo es una cláusula "definite"; en álgebra universal las cláusulas "definites" resultan (aparecen) como cuasi-identidades. Una cláusula de Horn sin ningún literal positivo es a veces llamada cláusula objetivo (goal) o consulta (query), especialmente en programación lógica.Una fórmula de Horn es una cadena textual (string) de cuantificadores existentiales o universales seguidos por una conjunción nde cláusulas de Horn.

Lenguaje Lógico de Datos LDL y un Sistema de Gestión de Bases de Datos Relacional SGBDR

Sistema LDL:

El proyecto Logic Data Languaje (Lenguaje Lógico de Dato: LDL) de Microelectronics and Computer Corporation (MCC) se inició en 1984 con dos objetivos primarios:

Crear un sistema que extendiera el modelo relacional y a la vez aprovechara algunas de las características positivas de un SGBDR(Sistema de Gestión de Base de Datos Relacionales).

Mejorar la funcionalidad de un SGBD de modo que operara como un SGBD deductivo y además permitiera la creación de aplicaciones de propósito general.

Ahora el sistema resultante es un SGBD deductivo que se encuentra en el mercado.

SGBDR

El modelo relacional fue presentado en la década del 70, y a partir de ese momento comenzaron a desarrollarse múltiples sistemas para gestionar las bases de datos relacionales. IBM fue una de las pioneras en el desarrollo de productos comerciales sobre SGBD relacionales; algunos de sus productos fueron el SQL/DS para los entornos DOS/VSE y VM/CMS, y el DB2 para el sistema operativo MVS en 1983.

En tanto, INGRES fue otro SGBDR desarrollado por la Universidad de Berkeley a principios de los setenta. Luego se convirtió en comercial y comenzó a ser distribuido por Ingres Inc. y luego por Computer Associates.

Otras marcas comerciales de SGBDR son Oracle de Oracle Inc., Sybase de Sybase Inc., RDB de Digital Equipment Corp. de Compaq, INFORMIX de Informix Inc. y UNIFY de Unify Inc.

Además de los SGBDR mencionados, en los ochenta aparecen múltiples aplicaciones para PCs como ser RIM, RBASE 5000, PARADOX, OS/2 Database Manager, DBase IV, XDB, WAT-COM SQL, SQL Server (de Sybase Inc.), SQL Server (de Microsoft), Access, etc.

Notación Prolog / Datalog

Prolog

El Prolog (o PROLOG), proveniente del francés PROgrammation en LOGique, es un lenguaje de programación lógico e interpretado, bastante conocido en el medio de investigación en Inteligencia Artificial.

1. Historia

Se trata de un lenguaje de programación ideado a principios de los años 70 en la Universidad de Aix-Marseille (Marsella, Francia) por los profesores Alain Colmerauer y Philippe Roussel. Nació de un proyecto que no tenía como objetivo la implementación de un lenguaje de programación, sino el procesamiento de lenguajes naturales. Alain Colmerauer y Robert Pasero trabajaban en la parte del procesado del lenguaje natural y Jean Trudel y Philippe Roussel en la parte de deducción e inferencia del sistema. Interesado por el método de resolución SL, Trudel persuadió a Robert Kowalski para que se uniera al proyecto, dando lugar a una versión preliminar del lenguaje Prolog a finales de 1971 y apareciendo la versión definitiva en 1972. Esta primera versión de Prolog fue programada en ALGOL W.

Inicialmente se trataba de un lenguaje totalmente interpretado hasta que, en 1983, David H.D. Warren desarrolló un compilador capaz de traducir Prolog en un conjunto de instrucciones de una máquina abstracta denominada Warren Abstract Machine, o abreviadamente, WAM. Desde entonces Prolog es un lenguaje semi-interpretado.

Si bien en un principio se trataba de un lenguaje de uso reducido, la aparición de intérpretes del mismo para microordenadores de 8 bits (ej: micro-PROLOG) y para ordenadores domésticos de 16 bits (ej: Turbo Prolog de Borland, entre otros muchos) a lo largo de la década de 1980 contribuyó notablemente a su popularización. Otro importante factor en su difusión fue la adopción del mismo para el desarrollo del proyecto de la quinta generación de computadoras a principios de la década de los 80, en cuyo contexto se desarrolló la implementación paralelizada del lenguaje llamada KL1 y del que deriva parte del desarrollo moderno de Prolog.

Las primeras versiones del lenguaje diferían, en sus diferentes implementaciones, en muchos aspectos de sus sintaxis, empleándose mayormente como forma normalizada el dialecto propuesto por la Universidad de Edimburgo, hasta que en 1995 se estableció un estándar ISO (ISO/IEC 13211-1), llamado ISO-Prolog.

Prolog se enmarca en el paradigma de los lenguajes lógicos y declarativos, lo que lo diferencia enormemente de otros lenguajes más populares tales como Fortran, Pascal, C o Java.

2. Backtracking

En los lenguajes de programación antes mencionados, las instrucciones se ejecutan normalmente en orden secuencial, es decir, una a continuación de otra, en el mismo orden en que están escritas, que sólo varía cuando se alcanza una instrucción de control (un bucle, una instrucción condicional o una transferencia).

Los programas en Prolog se componen de cláusulas de Horn que constituyen reglas del tipo "modus ponendo ponens", es decir, "Si es verdad el antecedente, entonces es verdad el consecuente". No obstante, la forma de escribir las cláusulas de Horn es al contrario de lo habitual. Primero se escribe el consecuente y luego el antecedente. El antecedente puede ser una conjunción de condiciones que se denomina secuencia de objetivos. Cada objetivo se separa con una coma y puede considerarse similar a una instrucción o llamada a procedimiento de los lenguajes imperativos. En Prolog no existen instrucciones de control. Su ejecución se basa en dos conceptos: la unificación y el backtracking.

Gracias a la unificación, cada objetivo determina un subconjunto de cláusulas susceptibles de ser ejecutadas. Cada una de ellas se denomina punto de elección. Prolog selecciona el primer punto de elección y sigue ejecutando el programa hasta determinar si el objetivo es verdadero o falso.

En caso de ser falso entra en juego el backtracking, que consiste en deshacer todo lo ejecutado situando el programa en el mismo estado en el que estaba justo antes de llegar al punto de elección. Entonces se toma el siguiente punto de elección que estaba pendiente y se repite de nuevo el proceso. Todos los objetivos terminan su ejecución bien en éxito ("verdadero"), bien en fracaso ("falso").

Datalog

Es un lenguaje de consultas, no procedimental, basado en el lenguaje de programación lógica de Prolog. Como se hace en el cálculo relacional, el usuario describe la información deseada sin especificar un procedimiento específico de obtención de dicha información. La sintaxis de Datalog se asemeja a la de Prolog. Sin embargo, el significado de los programas en Datalog se define de una manera puramente declarativa, a diferencia de la semántica más procedimental de Prolog. Datalog simplifica la escritura de consultas simples y hace más sencilla la optimización de consultas.

Técnicas de fragmentación, replicación y reparto de datos para el diseño de base de datos distribuidas

Fragmentación de datos

Consiste en subdividir las relaciones y distribuirlas entre los sitios de la red, tiene como objetivo buscar formas alternativas de dividir una las instancias (tablas) de relaciones en otras más pequeñas. La fragmentación se puede realizar por tuplas individuales (fragmentación horizontal), por atributos individuales fragmentación vertical) o una combinación de ambas (fragmentación híbrida). El principal problema de la fragmentación radica en encontrar la unidad apropiada de distribución. Una relación no es una buena unidad por muchas razones. Normalmente las vistas de una relación están formadas por subconjuntos de relaciones. Además, las aplicaciones acceden localmente a subconjuntos de relaciones. Por ello, es necesario considerar a los subconjuntos de relaciones como unidad de distribución. Al descomponer de una relación en fragmentos, tratados cada uno de ellos como una unidad de distribución, permite el proceso concurrente de las transacciones. El conjunto de estas relaciones, provocará la ejecución paralela de una consulta al ser dividida en una serie de subconsultas que operará sobre los fragmentos. Cuando las vistas definidas sobre una relación son consideradas como unidad de distribución que se ubican en diferentes sitios de la red, podemos optar por dos alternativas diferentes: La relación no estará replicada y se almacena en un único sitio, o existe réplica en todos o algunos de los sitios en los cuales reside la aplicación. Las consecuencias de esta estrategia son la generación de un volumen de accesos remotos que pueden ser innecesarios con un mal manejo de estas replicas. Además, las réplicas innecesarias pueden causar problemas en la ejecución de las actualizaciones y puede no ser deseable si el espacio de almacenamiento está limitado. Los inconvenientes de la fragmentación están dados en que si las pueden estar definidas por fragmentos mutuamente exclusivos y al recuperar los datos de dos fragmentos situados en sitios diferentes es necesario trasmitir los datos de un sitio a otro y realizar sobre ellos la operación de unión (Join), lo cual puede ser costoso. El control semántico cuando los atributos implicados en una dependencia una relación se descompone en diferentes fragmentos y estos se ubican en sitios diferentes puede ser muy costos porque es necesario hacer búsquedas en un gran número de sitios.

Replicadas

El esquema de BDD de replicación consiste en que cada nodo debe tener su copia completa de la base de datos. Es fácil ver que este esquema tiene un alto costo en el almacenamiento de la información. Debido a que la actualización de los datos debe ser realizada en todas las copias, también tiene un alto costo de escritura, pero todo esto vale la pena si tenemos un sistema en el que se va a escribir pocas veces y leer muchas, y dónde la disponibilidad y fiabilidad de los datos sea de máxima importancia.

Distribución de los datos

Una de las decisiones más importantes que el diseñador de bases de datos distribuidas debe tomar es el posicionamiento de la data en el sistema y el esquema bajo el cuál lo desea hacer. Para esto existen cuatro alternativas principales: centralizada, replicada, fragmentada, e híbrida. La forma centralizada es muy similar al modelo de Cliente/Servidor en el sentido que la BDD está centralizada en un lugar y los usuarios están distribuidos. Este modelo solo brinda la ventaja de tener el procesamiento distribuido ya que en sentido de disponibilidad y fiabilidad de los datos no se gana nada.

Relación entre fiabilidad y disponibilidad en una base de datos distribuida

Fiabilidad de la data: Almacenando varias copias de la data en lugares geográficamente apartados se logra maximizar la probabilidad de que la data va a ser recuperable en caso de que ocurra daño físico en cualquier sitio.

Disponibilidad de la data: como en la fiabilidad, almacenar varias copias asegura que los usuarios tengan a su disponibilidad los elementos de la data, aún si el nodo al que usualmente acceden no está disponible o falla.