17
En la definición del lenguaje L, hemos convertido cada relación n-aria del esquema S en un predicado n-ario, definiendo un orden en el conjunto de atributos del esquema de la relación. De esta forma el concepto de relación coincide con el concepto de relación matemática (subconjunto del producto cartesiano de los dominios): se pierde el concepto de atributo de una relación.
1. Lógica y Bases de Datos: introducción
Predicados P
Nombres de relación del esquema:
P = { Rn: R (A1: D1, A2 : D2 , …, An : Dn) ? S } ? {=}
18
En la definición de la interpretación I de L, hemos definido el dominio como la unión de los dominios de definición de las relaciones del esquema. De esta forma se pierde el concepto de dominio de un atributo (lógica homogénea). Esta simplificación no quita generalidad a la formalización, ya que podría trabajarse en una lógica con tipos (lógica heterogénea).
1. Lógica y Bases de Datos: introducción
Asignación
(K, E)
E : P ? ?i:1..n ( 2Di ) / E(pk) ? (2Dk), E(pk) = Ext(p)
(pk es un predicado de aridad k)
E(=) = { (d, d): d ? D }
Dominio D
Unión de los dominios de definición de las relaciones del esquema:
D = {di : di ? ?i (Di), Di es un dominio de S}
19
Esquema S: (L, RI) :
Constantes: dom_P È dom_A È dom_C
= {A, B, C, a, b, c, d, CS100, CS200, P100, P200}
Predicados: { Profesor(.), Alumno(.), Curso(.), Enseña(.,.), Matriculado(.,.)} ? {=}
Variables: { X, Y, Z, …}
Cuantificadores: { " , $ }
Conectivas lógicas: { Ù, Ú , ® }
Símbolos de puntuación: { (, ),’, … }
Restricciones de Integridad:
"x ( curso (x) ® ? y enseña (y,x) )
Fórmula bien formada de L
Lenguaje L
RI
1. Lógica y Bases de Datos: introducción
20
BD: interpretación de L que es modelo de RI
D = {A, B, C, a, b, c, d, CS100, CS200, P100, P200}
K(A)=A, K(B)=B, …, K(P200)=P200
(Gp:) E (Profesor)
(Gp:) E (Alumno)
(Gp:) E (Curso)
(Gp:) E (Matriculado)
(Gp:) E (Enseña)
1. Lógica y Bases de Datos: introducción
E(=) = {(d, d): d ?D}
21
BD: interpretación de L que es modelo de RI
D = {A, B, C, a, b, c, d, CS100, CS200, P100, P200}
K(A)=A, K(B)=B, …, K(P200)=P200
1. Lógica y Bases de Datos: introducción
En esta formalización, L es un lenguaje de definición de datos y de consulta:
f.b.f cerrada de L: restricción de integridad (?x ( curso (x) ? ? y enseña (y,x) )
f.b.f abierta de L: consulta a la BD (profesor (x) ? ¬ enseña (x, CS100) )
E(=) = {(d,d): d ?D}
22
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional:
Interpretación de un lenguaje de 1er orden
Teoría de un lenguaje de 1er orden
23
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional: teoría de un lenguaje de 1er orden.
Esquema S: (L, RI)
BD: Interpretación I de L
Esquema S: (L, RI)
BD: Teoría T de L
|=I F sii T |= F
24
1. Lógica y Bases de Datos: introducción
Formalización lógica de una base de datos relacional: teoría de un lenguaje de 1er orden.
Axiomas de información básica en T
Por cada predicado n-ario p de L y por cada tupla en la extensión de p en la base de datos, se incluye en T el átomo p(d1, …, dn).
T = { profesor(A), profesor(B), …, matriculado(d, P200)} ? {?x =(x, x)}
25
1. Lógica y Bases de Datos: introducción
Axiomas de compleción en T (información negativa)
Existen fórmulas F que no son consecuencia lógica de la teoría T y sin embargo son ciertas en la interpretación I, es decir T |?F y |=I F, por ejemplo la fórmula ¬Prof(P100).
Para resolverlo se añade a T un axioma que defina explícitamente quienes son los únicos individuos para cada predicado:
?x1, …, xn (p(x1, …, xn) ? ((=(x1, d11) ? … ? =(xn, d1n)) ?
. . . ( es una tupla de p)
(=(x1, dm1) ? … ? =(xn, dmn))))
T = { profesor(A), profesor(B), …, matriculado(d, P200), ?x =(x, x),
?x (profesor(x) ? (=(x, A) ? =(x, B) ? =(x,C))),
?x (alumno(x) ? (=(x, a) ? =(x, b) ? =(x,c) ? =(x,d))),
… }
26
1. Lógica y Bases de Datos: introducción
Axiomas de nombre único en T
Existen fórmulas F que no son consecuencia lógica de la teoría T y sin embargo son ciertas en la interpretación I, es decir T |?F y |=I F, por ejemplo la fórmula ¬ =(A, B). Para resolverlo se añade a T un axioma que defina explícitamente qué pares de constantes no son iguales:
¬ =(c, c’): c, c’ son dos constantes distintas de C
T = { profesor(A), profesor(B), …, matriculado(d, P200), ?x =(x, x),
?x (profesor(x) ? ( =(x, A) ? =(x, B) ? =(x,C))),
?x (alumno(x) ? ( =(x, a) ? =(x, b) ? =(x,c) ? =(x,d))),
…,
¬ =(A, B), ¬ =(A, C), ¬ =(A, a), …, ¬ =(P100, P200) }
27
1. Lógica y Bases de Datos: introducción
Axioma de cierre de dominio en T
Existen fórmulas F que no son consecuencia lógica de la teoría T y sin embargo son ciertas en la interpretación I, es decir T |?F y |=I F, por ejemplo la fórmula dependiente del dominio, F = ?x (Prof(x) ? Curso(x) ? Alumno(x)).
Para resolverlo se añade a T un axioma que defina explícitamente el domino:
?x (=(x, c1) ? … ? =(x, cm)): {c1, c2,…cm} son las constantes de C.
T = { profesor(A), profesor(B), …, matriculado(d, P200), ?x =(x, x),
?x (profesor(x) ? ( =(x, A) ? =(x, B) ? =(x,C))),
?x (alumno(x) ? ( =(x, a) ? =(x, b) ? =(x,c) ? =(x,d))),
…,
¬ =(A, B), ¬ =(A, C), ¬ =(A, a), …, ¬ =(P100, P200),
?x (=(x, A) ? =(x, B) ? … ? =(x, P200)) }
28
1. Lógica y Bases de Datos: introducción
Teoría T
T = { p(d1, …, dn): pn ? P, y ? Ext(p),
?x =(x, x),
?x1, …, xn (p(x1, …, xn)
?
((=(x1, d11) ? … ? =(xn, d1n)) ?
. . .
(=(x1, dm1) ? … ? =(xn, dmn)))): pn ? P y ? Ext(p),
?x1, …, xn ¬ p(x1, …, xn ): pn ? P y Ext(p) = ?,
¬ =(c, c’): c y c’ son constantes distintas de C,
?x (=(x, c1) ? =(x, c2) ? … ? =(x, cm)): (c1, c2, …, cm) son las constantes de C }
Axiomas de información básica
Axiomas de compleción
Axiomas de nombre único
Axioma de cierre de dominio
Axioma de la igualdad
29
Esquema S de la BD
Lenguaje de 1er orden L
Extensión D de la BD
Axiomas de información básica:
D = { p(d1, …, dn): pn ? P, y ? Ext(p)}
(átomos base)
Teoría de primer orden en L
1. Lógica y Bases de Datos: introducción
T = comp(D)
?
{axioma de cierre de dominio}
30
Esquema S de la BD
Lenguaje de 1er orden L
Extensión D de la BD
Programa lógico:
D = {A: A es un átomo base}
Semántica de D
1. Lógica y Bases de Datos: introducción
{L: L es un literal base, T |= L }
T = comp(D) ? {axioma de cierre de dominio}
31
La teoría de la compleción formaliza hipótesis implícitas
en la evaluación de consultas en bases de datos relacionales:
– hipótesis del mundo cerrado
– hipótesis del cierre del dominio
– hipótesis de nombre único
Hipótesis del mundo cerrado
Hipótesis del cierre de dominio
Hipótesis de nombre único
axiomas de compleción
axioma de nombre único
axioma de cierre de dominio
1. Lógica y Bases de Datos: introducción
32
Axiomas de compleción para
las relaciones del esquema
Hipótesis del mundo cerrado
A? D
D
Ø A
HMC
1. Lógica y Bases de Datos: introducción
33
Base de datos
deductiva
+
Base de datos
relacional
Conocimiento explícito
Reglas
deductivas
Conocimiento implícito
Las Bases de Datos Deductivas extienden la capacidad expresiva de las bases de datos relacionales incluyendo un conjunto de reglas que permiten definir conocimiento implícito
2. Bases de datos deductivas: definición y formalización
Reglas
deductivas
Base de datos
relacional
34
Base de datos deductiva
Padre
Antecesor (x, y) ¬ Padre (x, y)
Antecesor (x, y) ¬ ?z (Padre (x, z) Ù Antecesor (z, y) )
Reglas Deductivas:
Juan es antecesor de Luis
Juan es antecesor de María
Juan es antecesor de Pedro
Luis es antecesor de José
2. Bases de datos deductivas: definición y formalización
35
Hechos
Reglas
Información
derivada
Sistema de Gestión
de Bases de Datos
Relacionales
Sistema de Inferencia
Hechos = {tuplas de relaciones}
(información básica)
Reglas = {reglas deductivas}
(conocimiento implícito)
Sistema de gestión de bases de
datos deductivas
Usuario
+
Sistema
de inferencia
Base de datos
deductiva
+
Reglas
deductivas
Base de datos
relacional
2. Bases de datos deductivas: definición y formalización
36
Base de datos deductiva
Padre
Antecesor (x, y) ¬ Padre (x, y)
Antecesor (x, y) ¬ ?z (Padre (x, z) Ù Antecesor (z, y))
Reglas Deductivas:
Antecesor
Relación derivada
2. Bases de datos deductivas: definición y formalización
37
Bases de Datos Deductivas
ESQUEMA
Relaciones
Ri (Ai1: Di1, Ai2: Di2 , …, Aini: Dini)
(1 £ i £ m) (m relaciones)
Restricciones de Integridad
Wi: Wi es una expresión lógica
(1 = i = k) (k restricciones de integridad)
ESQUEMA
Relaciones básicas:
Ri (Ai1: Di1, Ai2: Di2 , …, Aini: Dini)
(1 £ i £ m) (m relaciones básicas)
Relaciones derivadas:
Si (Ai1: Di1 , Ai2: Di2 , …, Aini: Dini)
(1 £ i £ s) (s relaciones derivadas)
Restricciones de Integridad
Wi: Wi es una expresión lógica
(1 = i = k) (k restricciones de integridad)
Bases de Datos Relacionales
2. Bases de datos deductivas: definición y formalización
38
Bases de Datos Deductivas
Bases de Datos Relacionales
Ri Í (Di1 x Di2 x … x Dini)
(1 £ i £ m) (m relaciones)
Ri Í (Di1 x Di2 x … x Dini )
(1 £ i £ m) (m relaciones básicas)
Base de datos
Base de datos
Sij (x1, x2,…, xni ) ¬ Wij
(1 £ i £ s) (s relaciones derivadas)
(1 £ j £ Ki) (Ki reglas para la relación Si)
Ri
2. Bases de datos deductivas: definición y formalización
39
Bases de Datos Deductivas
Bases de Datos Relacionales
Ri Í (Di1 x Di2 x … x Dini)
(1 £ i £ m) (m relaciones)
Ri Í (Di1 x Di2 x … x Dini )
(1 £ i £ m) (m relaciones básicas)
Base de datos
Base de datos
Sij (x1, x2,…, xni ) ¬ Wij
(1 £ i £ s) (s relaciones derivadas)
(1 £ j £ Ki) (Ki reglas para la relación Si)
Si definimos un orden en el conjunto de atributos del esquema de la relación, el concepto de relación coincide con el concepto de relación matemática (subconjunto del producto cartesiano de los dominios): se pierde el concepto de atributo de una relación.
En la definición de una regla deductiva, S ? W: W es una fórmula cuyas únicas variables libres son las variables de S.
2. Bases de datos deductivas: definición y formalización
40
Relaciones básicas:
PIEZA (codpieza: D1, desc: D2, peso: D3)
CP = {codpieza}
PROV (codprov: D4, nombre: D5, zona: D6)
CP = {codprov}
PRECIOS (codprov: D4, codpieza: D1, precio: D7)
CP = {codprov, codpieza}
CAj = {codprov} ® PROV
CAj = {codpieza} ® PIEZA
COMP (pieza1: D1, pieza2: D1)
CP = {pieza1, pieza2}
CAj = {pieza1} ® PIEZA
CAj = {pieza2} ® PIEZA
Esquema
2. Bases de datos deductivas: definición y formalización
 Página anterior | Volver al principio del trabajo | Página siguiente  |