41 Relaciones derivadas: PRECIOS3 (codprov: D4, codpieza: D1, precio: D7) CP = {codprov, codpieza} CAj = {codprov} ® PROV CAj = {codpieza} ® PIEZA
PRECIOS_EXT (codprov: D4, nombre: D5, codpieza: D1, desc: D2, precio: D7) CP = {codprov, codpieza} CAj = {codprov} ® PROV CAj = {codpieza} ® PIEZA
COMPONENTE (pieza1: D1, pieza2: D1) CP = {pieza1, pieza2} CAj = {pieza1} ® PIEZA CAj = {pieza2} ® PIEZA
Restricciones de integridad: "x "y ( COMPONENTE (x,y) ® Ø COMPONENTE (y,x) ) Esquema 2. Bases de datos deductivas: definición y formalización
42 PIEZA PROV PRECIOS COMP Base de Datos 2. Bases de datos deductivas: definición y formalización
43 Reglas deductivas:
1 PRECIOS3 (x, y, z) ¬ ?w (PROV (x, w, 3) ? PRECIOS (x, y, z) )
2 COMPONENTE (x, y) ¬ ?z (COMP (x, z) Ù COMPONENTE (z, y) ) 3 COMPONENTE (x, y) ¬ COMP (x, y)
4 PRECIOS_EXT (x, n, y, d, p) ¬ ?z ?w (PROV (x, n, z) Ù PIEZA (y, d, w) ? PRECIOS (x, y, p) ) Base de Datos Se asume la notación de la Programación Lógica: todas las variables libres en la regla se suponen cuantificadas universalmente. 2. Bases de datos deductivas: definición y formalización
44 PROV PIEZA PRECIOS COMP PRECIOS3 PRECIOS_EXT COMPONENTE BASE DE DATOS El usuario desea manipular las relaciones de la BD independientemente de que sean relaciones básicas o derivadas.
45 Mecanismo de vistas del modelo relacional Definición de información implícita Relación derivada PRECIOS3 VISTA SQL92: CREATE VIEW PRECIOS3 AS SELECT codprov, codpieza, precio FROM PRECIOS, PROV WHERE (PRECIOS.codprov = PROV.codprov AND (PROV.zona=3) 2. Bases de datos deductivas: definición y formalización
46 Relación derivada COMPONENTE VISTA SQL: CREATE VIEW COMPONENTE AS SELECT pieza1, pieza2 FROM COMP UNION SELECT pieza1, pieza2 FROM COMP, COMPONENTE ………………. ¡ En SQL92 no se pueden definir vistas recursivas! Limitaciones del modelo relacional (SQL92) en la definición de vistas: 2. Bases de datos deductivas: definición y formalización
47 INSERT INTO PRECIOS3 VALUES (pv12, pz23, 20) INSERT INTO PRECIOS VALUES (pv12,pz23,20) INSERT INTO PROV VALUES (pv12,NULL,3) INSERT INTO PIEZA VALUES (pz23,NULL,NULL) ¿el proveedor existe? ¿la pieza existe? ¿el proveedor es de la zona 3? error NO SI SI NO NO SI c opción 1 Limitaciones del modelo relacional (SQL92) en la actualización de vistas: 2. Bases de datos deductivas: definición y formalización
48 INSERT INTO PRECIOS3 VALUES (pv12, pz23, 20) INSERT INTO PRECIOS VALUES (pv12, pz23, 20) ¿el proveedor pv12 existe y es de la zona 3 y la pieza pz23 existe? opción 2 NO SI Limitaciones del modelo relacional (SQL92) en la actualización de vistas: error 2. Bases de datos deductivas: definición y formalización
49 INSERT INTO PRECIOS3 VALUES (pv12, pz23, 20) ¡Debido a la ambigüedad existente, el SQL92 no permite actualizar vistas definidas a partir de una concatenación de tablas! opción 1 opción 2 Limitaciones del modelo relacional (SQL92) en la actualización de vistas: 2. Bases de datos deductivas: definición y formalización
50 Los sistemas de gestión de bases de datos deductivas deben superar las limitaciones de los sistemas relacionales PROBLEMAS:
Formalización
Actualización de la base de datos
Construcción de SGBD deductivos
2. Bases de datos deductivas: definición y formalización
51 Bases de Datos Deductivas
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)
Ri Í (Di1 x Di2 x … x Dini )
(1 £ i £ m) BASE DE DATOS Sij (x1, x2,…, xni ) ¬ Wij
(1 £ i £ s) (1 £ j £ Ki) notación algebraica notación lógica 2. Bases de datos deductivas: definición y formalización
52 pieza (pz1, tornillo, 10) …
prov (pv1, Juan, 1) …
comp (pz1, pz3) …
precios3 (x, y, z) ¬ ?w (prov (x, w, 3) Ù precios (x, y, z) )
componente (x, y) ¬ ?z ( comp (x, z) Ù componente (z, y) ) componente (x, y) ¬ comp (x, y)
precios_ext (x,n,y,d,p)¬ ?z?w (prov (x, n, z) Ù pieza (y, d, w) Ù precios (x, y, p) ) Reglas deductivas Hechos Base de datos deductiva Formalización: Si intentamos representar la información explícita y la información implícita en un mismo lenguaje (lenguaje de 1er orden) obtenemos un programa lógico: 2. Bases de datos deductivas: definición y formalización
53 Lenguaje de definición de reglas
Lenguaje de 1er orden
Base de datos deductiva Programa lógico Sistema de programación lógica Sistema de gestión de bases de datos deductivas 2. Bases de datos deductivas: definición y formalización
54 MARCO FORMAL: Lógica de primer orden (Programación Lógica)
Esquema de BDD:
(L, RI): – L es un lenguaje de 1er orden – RI es un conjunto de f.b.f de L (restricciones de integridad)
BDD: (programa lógico)
{A: A es un átomo base} (hechos) È { A ¬ L1 Ù L2 Ù … Ù Ln : A es un átomo y Li es un literal} (reglas)
2. Bases de datos deductivas: definición y formalización
55 BDD (programa lógico)
{A: A es un átomo base}
È
{ A ¬ L1 Ù L2 Ù … Ù Ln: A es un átomo y Li es un literal} Ri Í (Di1 x Di2 x … x Dini )
(1 £ i £ m) BASE DE DATOS Sij (x1, x2,…, xni ) ¬ Wij
(1 £ i £ s) (1 £ j £ Ki) En la formalización como un programa lógico, las reglas se definen como cláusulas (disyunción de literales). Esta simplificación no quita generalidad ya que el algoritmo de Lloyd [LT84] permite transformar una regla general, S? W, en un conjunto de cláusulas equivalentes en la semántica de la compleción. 2. Bases de datos deductivas: definición y formalización
56 BDD definida: sin negación en el cuerpo de las reglas BDD normal: con negación en el cuerpo de las reglas BDD jerárquica: sin recursión BDD estratificada: con recursión (no en términos de negación)
BDD: (programa lógico)
{A : A es un átomo base} (hechos) È { A ¬ L1 Ù L2 Ù … Ù Ln : A es un átomo y Li es un literal} (reglas)
2. Bases de datos deductivas: definición y formalización
57 Esquema: (L, RI) : Constantes Unión de los dominios de definición de las relaciones del esquema Predicados Nombres de relación del esquema Lenguaje L Restricciones de Integridad (RI) Fórmulas bien formadas (f.b.f) de L RI 2. Bases de datos deductivas: definición y formalización
58 Esquema: (L, RI) : Constantes: D1 È D2 È D3 È D4 È D5 È D6 È D7 = {pz1, pz3, …, tornillo, tuerca, …, pv1, pv5, …, Juan,…} Predicados: { PIEZA, PROVEEDOR, PRECIOS, PRECIOS_EXT, PRECIOS3, COMP, COMPONENTE} Variables: { X, Y, Z, …} Cuantificadores: { " , $ } Conectivas lógicas: { Ù, Ú , ® } Símbolos de puntuación: { (, ),’, … } Restricciones de Integridad: "x "y ( componente (x,y) ® Ø componente (y,x) ) Fórmulas bien formadas de L Lenguaje L RI 2. Bases de datos deductivas: definición y formalización
59 { pieza (pz1, tornillo, 10), …, proveedor (pv1, Juan, 1), …, precios (pv1, pz3, 100), …, comp (pz1, pz3), … } 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) Reglas deductivas BDD: È Fórmulas bien formadas de L 2. Bases de datos deductivas: definición y formalización
60 Esquema de la BDD Lenguaje de 1er orden L Extensión de la BDD Programa lógico (D) 2. Bases de datos deductivas: definición y formalización
| Página siguiente |