Download Introducción a las bases de datos deductivas

Introducción a las bases
de datos deductivas (I)
Rafael Caballero Roldán
D t d E
Doctorado:
Extensiones
t
i
d
de P
Programación
ió Ló
Lógica
i
Índice
 Sintaxis
 Semántica
 Modelo
de un programa Datalog
Objetivos

Aprender
A
d lla importancia
i
t
i de
d dar
d una semántica
á ti –
un significado
significado-- claro a los programas, estén en
el lenguaje en el que estén

L vamos a ver a través
Lo
t é de
d ejemplos
j
l basados
b
d
en extensiones de la programación lógica

Interés en sí mismos
mismos:: bases de datos
d d ti
deductivas,
answer sett programming
i … campos
de investigación activos
activos..
Idea
 Definir
un marco de programación lógica
q
en el que:




Se permita recursividad sin limitaciones
Se permita el uso de negación
negación, aunque sea
de forma limitada
Fá il d
Fácil
de iimplementar
l
t como llenguaje
j
Semántica clara y que corresponda con la
implementación
¿No vale Prolog?

E ell lenguaje
Es
l
j de
d programación
ió lógica
ló i
más
á
extendido.. Sin embargo
extendido

Tratamiento demasiado operacional de la recursión
camino(X,Y)  arco(X,Y)
camino(X,Y)  camino(X,Z), camino(Z,Y)


D
Dependencia
d
i del
d l orden
d
d llas reglas,
de
l
d l orden
del
d
d
de
los átomos en las reglas
reglas…
…
El tratamiento
inconsistencias
de
la
negación
da
lugar
a
Alternativas
 Datalog:
D t l



Simple, admite todo tipo de recursión
Semántica clara
Limitado a p
programas
g
sin funciones y
estratificados
 Answer


Set Programming
Extiende Datalog a programas no
estratíficados
Semántica más compleja
Datalog
 Sistema
de referencia: Datalog
y
, disponible
p
en
Educational System,
http://www.fdi.ucm.es/profesor/fernan/des/
 Artículo
de referencia:
Towards a Theory of Declarative Knowledge
Krzysztof
y
R. Apt,
p Howard A. Blair, Adrian Walker
Foundations of deductive databases and
programming, pp
pp.. 8989-148
logic
Sintaxis Datalog

Variables:: X,Y,Z,…
Variables

Constantes:: a,b,c,d,…
Constantes

Átomos: predicados con argumentos variables o
Átomos:
constantes: p(a
p(a,X),
X) q(Y
q(Y,Z,U),r,…
Z U) r

Literales: átomos o átomos negados,
Literales:
representados por L1, L2, …
Sintaxis (II)
Cláusulas.. De la forma:
Cláusulas
A  L1, …, Lm
A un átomo, la cabeza de la cláusula
cláusula,,
L1, …, Lm literales,
literales el cuerpo
cuerpo..


Si no hay literales (m=0) se dice que la cláusula
es un hecho.

Programa:: conjunto finito de cláusulas
Programa
Sintaxis (III)

Objetivos::  L1, …, Lm donde L1, …, Lm son literales
Objetivos

Sustitución θ = {{xx1 t1,…, xn  tn} es una aplicación que
reemplaza simultáneamente las variables x1, …, xn por
los términos t1,…,tn cuando es aplicada

tθ representa la aplicación de θ a t

Se dice que tθ es una instancia de t

El conjunto de instancias básicas o cerradas (sin
variables) de cláusulas de un programa se denota por
ground(P)
g
( )
Ejemplo
 edge(a,b).
 edge(a,c).
edge(a c)
 edge(b,a).
 edge(b,d).
 path(X,Y)
::-- path(X,Z), path(Z,Y).
 path(X,Y) ::-- edge(X,Y).
Semántica

L
Lenguaje
j de
d un programa D
Datalog
t l P
P: llenguaje
j
de primer orden formado por lo símbolos de P y
sólo por éstos

Base de Herbrand Up: Conjunto de todos los
átomos sin variables (básicos) que se pueden
formar con los símbolos del programa P


I
Importante:
En
E Datalog
D l Up es finito,
fi i en P
Prolog
l es
infinito
Interpretación I de un programa P: cualquier
conjunto I  Up
Semántica (II)

Una fórmula S es cierta en una interpretación I sii cada una de sus
instancias básicas (cerradas)
(
) es cierta en I

Un átomo básico A es cierto en I sii A  I

Una fórmula básica ¬S es cierta en I sii S no es cierta en I

Una fórmula cerrada x.S es cierta en I sii existe algún término sin variables
t tal
t l que S{x
S{ t} es cierta
S{x
i t en I

Una fórmula cerrada x.S es cierta en I sii S es cierta en I (por (1))

Una fórmula cerrada S1  S2 es cierta en I sii S2 no es cierto en I o bien
S1 es cierto en I

Una fórmula S1,….,Sn es cierta en I sii cada Si es cierta en I

Una fórmula S1 V … V Sn es cierta si algún
g Si es cierta en I
Modelos
 Una
interpretación M es un modelo de
programa
g
P si cada
Herbrand de un p
cláusula C  P es cierta en M. Se escribe
entonces M |=
| P
 Ejercicio
Ejercicio:: encuentra los modelos del
programa
q(a)
p(X)  p(X)
Modelos (II)

U modelo
Un
d l se di
dice mínimo
í i
sii está
tá iincluido
l id en
cualquier otro modelo

Un modelo se dice minimal si no contiene
ningún modelo

Ejercicio: ¿todo modelo mínimo es minimal? ¿y
Ejercicio:
viceversa?

Ejercicio: Di qué modelos del ejemplo de la
Ejercicio:
página anterior son mínimos o minimales
Modelos (III)
 Un
U
modelo
d l M se di
dice con soporte
t sii para
cada A  M existe una cláusula en
ground(P) con cabeza A y cuerpo válido
en M
 Ejercicio: Encuentra un modelo con
soporte
sopo
te pa
para
ae
el p
programa:
og a a
 p(a)
 p(x)
p( )  q(x)
q( )
 q(x)  q(x)