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 siguiente |