Lógica y Bases de Datos (Powerpoint) (página 4)

Partes: 1, 2, 3, 4

61
Programación lógica: semántica operacional: SLDNF
semántica declarativa: comp(D)

Semántica operacional: procedimiento SLDNF

SLDNF: – procedimiento de refutación
– reglas de inferencia:
resolución
negación como fallo

Semántica declarativa asociada al SLDNF: compleción de D
Semántica de una BDD
2. Bases de datos deductivas: definición y formalización

62
¬ componente (pz1,w)
¬ comp (pz1,z) Ù componente (z,w)
componente (pz3,w)
¬ comp (pz3,z ‘) Ù componente (z ‘,w)
¬ componente ( pz8,w)
¬ comp (pz8,z ‘‘) Ù componente (z ‘‘,w)
¬ comp (pz8,w)
¬ comp (pz3,w)
¬ comp (pz1,w)
2
hecho
z/pz3
2
3
hecho
z’/pz8
2
3
hecho
w/pz3
hecho
w/pz8
3
w = pz3
w = pz8
¿ De qué piezas se compone la pieza pz1?
2 componente (x, y) ¬ comp (x, z) Ù componente (z, y)
3 componente (x, y) ¬ comp (x, y)
Procedimiento SLDNF

63
¬ componente (pz1,w)
¬ comp (pz1,z) Ù componente (z,w)
(Gp:) resolución

componente (x,y) ¬ comp (x,z) Ù componente (z,y)
x/pz1
y/w
¬ componente (pz3,w)
(Gp:) resolución

comp (pz1,pz3)
hecho
regla 2
z/pz3
comp (pz3,pz8)
hecho
w/pz8
(Gp:) resolución

éxito
w = pz8
respuesta
componente (x,y) ¬ comp (x,y)
regla 3
x/pz3
y/w
¬ comp (pz3,w)
(Gp:) resolución

¿ De qué piezas se compone la pieza pz1?
Procedimiento SLDNF

64
¬ proveedor (x, y, z) Ù Ø precios (x,pz1,30)
¬ Ø precios (pv1, pz1,30)
(Gp:) resolución

proveedor (pv1,Juan,1)
x/pv1, y/Juan, z/1
hecho
¬ precios (pv1,pz1,30)
fallo
negación como fallo
éxito
x/pv1
respuesta
¿Qué proveedores no suministran la pieza pz1 a 30€?
Procedimiento SLDNF

65
Semántica declarativa: teoría de la compleción de D (comp(D))
¬ precios (pv1, pz1, 30)
no
D
precios (pv1, pz1, 30)
D
Ø precios (pv1, pz1, 30)
SLDNF no infiere consecuencias lógicas de D

SLDNF infiere consecuencias lógicas de comp(D)
¿Suministra el proveedor pv1 la pieza pz1 a 30€?
2. Bases de datos deductivas: definición y formalización

66
{ precios (pv1, pz3,10),
precios (pv1, pz8,20),
precios (pv3, pz8, 30),
precios (pv5, pz1,50),
, … }
D:
D
precios (pv1, pz1, 30)
D
Ø precios (pv1, pz1, 30)
{ precios (pv1, pz3,10),
precios (pv1, pz8, 20),
precios (pv3, pz8, 30),
precios (pv5, pz1, 50),
"x "y "z ( precios (x, y, z) ®
(x=pv1 Ù y=pz3 Ù z=10) Ú (x= pv1 Ù y= pz8 Ù z= 20)
Ú (x= pv3 Ù y= pz8 Ù z= 30) Ú (x= pv5 Ù y= pz1 Ù z= 50) ), … }
Comp(D):
Ø precios (pv1, pz1, 30)
Comp(D):
2. Bases de datos deductivas: definición y formalización

67
"x "y "z ( precios (x, y, z) ®
(x=pv1 Ù y=pz3 Ù z=10) Ú (x= pv1 Ù y= pz8 Ù z= 20) Ú
(x= pv3 Ù y= pz8 Ù z= 30) Ú (x= pv5 Ù y= pz1 Ù z= 50) )
(precios (pv1, pz1,30) ®
(pv1=pv1 Ù pz1=pz3 Ù 30=10) Ú (pv1=pv1 Ù pz1=pz8 Ù 30=20) Ú
(pv1=pv3 Ù pz1=pz1 Ù 30=30) Ú (pv1=pv5 Ù pz1=pz1 Ù 30=50) )
Ø (pv1=pv1 Ù pz1=pz3 Ù 30=10)
Ø (pv1=pv1 Ù pz1=pz1 Ù 30=20)
Ø (pv1=pv3 Ù pz1=pz8 Ù 30=30)
Ø (pv1= pv5 Ù pz1=pz1 Ù 30=50)
Ø precios (pv1, pz1, 30)
2. Bases de datos deductivas: definición y formalización

68
comp (D) =
{pieza (pz1, tornillo, 10), …,
proveedor (pv1, Juan, 1), …,
precios (pv1, pz3, 100), …,
comp (pz1, pz3), … }
È
Axiomas de hechos
precios3 (x, y,z) ¬ precios (x, y, z) Ù prov (x, w, 3)

componente (x, y) ¬ comp (x,z) Ù componente (z, y)
componente (x, y) ¬ comp (x, y)

precios_ext (x,n,y,d,p) ¬ prov (x, n, z) Ù pieza (y, d, w) Ù precios (x, y, p)
Axiomas de
reglas
È
2. Bases de datos deductivas: definición y formalización

69
"x "y "z pieza (x, y, z) ® (x= pz1 Ù y= tornillo Ù z=10)
Ú
(x= pz3 Ù y= tuerca Ù z=11)
Ú
(x= pz8 Ù y= arandela Ù z=8)
…
"x "y "z precios3 (x, y, z) ® precios (x,y,z) Ù prov (x,w,3)
…

"x "y componente (x,y) ® comp(x,y)
Ú
$z (comp(x,z) Ù componente (z,y))
È
Axiomas de
compleción

70
Teoría de la compleción: comp(D)
p(t1,.., tn) ? L1 ? L2 ? … ? Lm ? p(x1,…, xn) ? ?y1… ?yd (x1=t1 ? … ? xn=tn ? L1 ? L2 ? … ? Lm)
Com(D) =
{ p(x1,…, xn) ? E1
. . . (Ei = ?y1… ?yd (x1=t1 ? … ? xn=tn ? L1 ? L2 ? … ? Lm) )
p(x1,…, xn) ? Ek ,

?x1, …, xn ( p(x1, …, xn) ? (E1 ? … ? Ek) ),
?x1, …, xn ¬ p(x1, …, xn): no existen sentencias de p en D

?x =(x, x),
¬ =(A, B), ¬ =(A, C), ¬ =(A, a), …, ¬ =(P100, P200)

?x (=(x, A) ? =(x, B) ? … ? =(x, P200)) }
Axiomas de la igualdad
Axiomas sobre p en D
Axiomas de compleción de p
Axioma de cierre de dominio
2. Bases de datos deductivas: definición y formalización

71
BDD
PL
hechos >>> reglas hechos
~
reglas
relaciones de D:
– básicas
– derivadas
predicados de P
lenguaje libre de funciones
no
hechos y reglas son
independientes del dominio
no
tiempo de acceso
a los datos
eficiencia º
tiempo del
sistema de inferencia
eficiencia º
2. Bases de datos deductivas: definición y formalización