La Lógica en el desarrollo
de las Bases de Datos
Matilde Celma Giménez
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
La Lógica en el desarrollo de las Bases de Datos
1. Lógica y Bases de Datos.
2. Bases de datos deductivas.
3. Actualización de bases de datos deductivas.
3.1 Actualización
3.2 Comprobación de la integridad
3.3 Restauración de la consistencia
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
2
1. Lógica y Bases de Datos
La idea básica que subyace al uso de la lógica para el estudio de los
sistemas de bases de datos es una idea común a todos los campos de
la computación lógica: “la semántica por teoría de modelos de la lógica
proporciona una base para la representación del conocimiento, y la
semántica por teoría de la demostración proporciona una base para la
computación” [J.W. Lloyd, en Computational Logic, 1990].
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
3
1. Lógica y Bases de Datos.
La lógica de primer orden ha sido utilizada en el desarrollo del
modelo relacional de datos desde su aparición en 1970.
Problemas:
- formalización
- definición de lenguajes de consulta
- estudio del concepto de independencia del dominio
- actualización de vistas
- comprobación y restauración de la integridad.
- optimización de consultas
- diseño de bases de datos
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
4
2. Bases de datos deductivas.
Base de datos
relacional
Base de datos
relacional
Conocimiento explícito
Reglas
deductivas
Conocimiento implícito
+
Reglas
deductivas
Base de datos
deductiva
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
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
5
2. Bases de datos deductivas.
Hechos = {tuplas de relaciones}
Hechos
(conocimiento explícito)
Sistema
de inferencia
Información
derivada
Reglas = {reglas deductivas}
(conocimiento implícito)
Reglas
Sistema de Gestión
de Bases de Datos
Relacionales
Hechos
+
+
Reglas
Usuario
Sistema de Inferencia
Base de datos
deductiva
Sistema de gestión
de bases de
datos deductivas
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
6
2. Bases de datos deductivas
ESQUEMA
BASE DE DATOS
Ri
Relaciones básicas:
Relaciones básicas:
Ri (Ai1: Di1, Ai2: Di2 , ..., Aini: Dini)
Ri  (Di1 x Di2 x ... x Din )
(1 i m) (m relaciones básicas)
(1 i m)
Relaciones derivadas:
Si (Ai1: Di1 , Ai2: Di2 , ..., Aini: Dini)
Ai1
Ai2
......
i
(m relaciones básicas)
Relaciones derivadas:
(1 i s) (s relaciones derivadas)
Sij (x1, x2,..., xn )  Wij
Restricciones de Integridad
(1 i s)
(s relaciones derivadas)
(1 j Ki)
(Ki reglas para la relación Si)
Wi: Wi es una expresión lógica
Aini
i
(1 ≤ i ≤ k) (k restricciones de integridad)
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
7
2. Bases de datos deductivas
Relaciones básicas:
Relaciones derivadas:
PIEZA (codpieza: D1, desc: D2, peso: D3)
CP = {codpieza}
PRECIOS3 (codprov: D4, codpieza: D1, precio: D7)
CP = {codprov, codpieza}
CAj = {codprov}  PROV
CAj = {codpieza}  PIEZA
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
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
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
8
2. Bases de datos deductivas
BDD
:
PIEZA
PROV
codpieza
desc
peso
codprov
nombre
zona
pz1
tornillo
10
pv1
Juan.....
1
pz3
tuerca
11
pv5
Carlos ....
3
pz8
arandela
8
pv3
Luis ......
3
PRECIOS
COMP
codprov
codpieza
precio
pieza1
pieza2
pv1
pz3
10
pz1
pz3
pv1
pz8
20
pz3
pz8
pv3
pz8
30
pv5
pz1
50
Reglas deductivas:
1 precios3 (x, y,z) z (precios (x, y, z)  prov (x, w, 3) )
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 z ( prov (x, n,z)pieza (y, d,w)precios (x, y, p) )
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
9
2. Bases de datos deductivas
PRECIOS3
PRECIOS
PRECIOS_EXT
COMP
COMPONENTE
BASE DE DATOS
PIEZA
PROV
El usuario desea manipular (consultar y
actualizar) las relaciones de la BD
independientemente de que sean
relaciones básicas o derivadas.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
10
2. Bases de datos deductivas
Mecanismo de vistas
del modelo relacional
Definición de información
implícita
Relación derivada
VISTA
Base de datos deductiva
Base de datos relacional
con vistas
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
11
2. Bases de datos deductivas
Limitaciones del modelo relacional
(SQL92):
Definición de vistas
Limitaciones en la definición
de vistas recursivas
Actualización
Limitaciones en la
actualización de las vistas
SGBD relacionales
Ausencia de procedimientos
para la evaluación de consultas
recursivas
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
12
2. Bases de datos deductivas.
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
LÓGICA
 Construcción de SGBD deductivos
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
13
2. Bases de datos deductivas.
Formalización: Si intentamos representar la información explícita y la información
Hechos
Reglas deductivas
Base de datos deductiva
implícita en un mismo lenguaje (lenguaje de 1er orden) obtenemos
un programa lógico:
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) )
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
14
2. Bases de datos deductivas
MARCO FORMAL: Lógica de 1er 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)
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
15
2. Bases de datos deductivas
Semántica de una BDD
Semántica de una BDD: definir el conocimiento
existente en la base de datos.
¿qué es cierto en la BDD?
:
Semántica declarativa: conocimiento en la BDD
Semántica operacional: procedimiento para obtener el
conocimiento
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
16
2. Bases de datos deductivas
Semántica de una BDD
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
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
17
¿ De qué piezas se compone la pieza pz1?
componente (pz1,w)
2
3
comp (pz1,z)  componente (z,w)
hecho
Procedimiento
SLDNF
comp (pz1,w)
z/pz3
hecho
w/pz3
componente (pz3,w)
3
2
comp (pz3,z ‘)  componente (z ‘,w)
hecho
z’/pz8
comp (pz3,w)
hecho
w = pz3
w = pz8
w/pz8
componente ( pz8,w)
2
3
comp (pz8,z ‘‘)  componente (z ‘‘,w)
comp (pz8,w)
comp(D) |= componente (pz1, pz3)
2 componente (x, y) comp (x, z)  componente (z, y)
3 componente (x, y) comp (x, y)
comp(D) |= componente (pz1, pz8)
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
18
La Lógica en el desarrollo de las Bases de Datos
1. Lógica y Bases de Datos.
2. Bases de datos deductivas.
3. Actualización de bases de datos deductivas.
3.1 Actualización
3.2 Comprobación de la integridad
3.3 Restauración de la consistencia
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
19
3. Actualización de base de datos deductivas
Actualización sobre
relación derivada
Actualización(es) sobre
relación(es) básicas(s)
“Dada una base de datos D (D=BDI BDE) y un requisito
de actualización insertar (A) (resp. borrar (A)) donde A es una
tupla de una relación derivada, encontrar una transacción T
sobre EDB tal que T(D) satisfaga el requisito de actualización”
Ejemplo: DELETE FROM PRECIOS3 WHERE codprov=pv1
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
20
PIEZA
codpieza
desc
peso
pz1
tornillo
10
pz3
tuerca
11
pz8
arandela
8
PRECIOS_EXT
PRECIOS
codprov
codprov codpieza
pz3
10
pv1
pz8
20
pv3
pz8
30
pv5
pz1
50
PROV
nombre
desc
precio
precio
pv1
codprov
nombre codpieza
zona
pv1
Juan.....
1
pv5
Carlos ....
3
pv3
Luis ......
3
pv1
Juan...
pz3
tuerca
10
pv1
Juan...
pz8
arandela
20
pv3
Luis...
pz8
arandela
30
pv5
Carlos..
.
pz1
tornillo
50
T1={borrar (PROV (pv1,Juan,1))}
T2={borrar (PIEZA (pz3,tuerca,11),
borrar (PIEZA (pz8,arandela,8))}
T3={borrar (PRECIOS (pv1,pz3,10),
borrar (PRECIOS (pv1,pz8,20))}
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
21
3. Actualización de bases de datos deductivas
Métodos para la actualización
de bases de datos deductivas
Utilización de los procedimientos de evaluación
de consultas para determinar los posibles caminos
de derivación del conocimiento que se desea a
actualizar
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
22
SLDNF:
precios_ext (pv1, x1, x2, x3, x4)
4
prov (pv1, x1, x5)  pieza (x2,x3,x6) precios (pv1,x2,x4)
prov(pv1,Juan,1)
T1
x1 / Juan
pieza (x2,x3,x6)  precios (pv1,x2,x4)
pieza(pz3,tuerca,11)
x2 / pz3, x3 / tuerca
T2
precios (pv1,pz3,x4)
precios(pv1,pz3.10)
T3
x4/ 10
pieza(pz8,arandela,8)
T2
x2 / pz8, x3 / arandela
precios (pv1,pz8,x4)
precios(pv1,pz8,20)
T3
x4/ 20
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
23
3.1 Actualización
Enunciado general del problema:
Dados el esquema (L,RI) de una base de datos deductiva, un
estado de base de datos D de ese esquema tal que "WRI se
cumple que D satisface W, y dado un requisito de actualización U tal
que U no es cierto en D entonces encontrar una transacción T tal
que "WRI, D’ = T(D) satisface W y U es cierto en D’.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
24
3.1 Actualización
Ejemplo 1
1. p(x)  q(x)  t(x)
2. p(x)  w(x)  v(x)
3. t(x)  s(x)  ¬r(x)
p (1 )
w (1 )  v (1 )
q (1 )  t(1 )
Actualización: U = p(1)
1) {w(1), v(1)}  BDE
2) {q(1), s(1)}  BDE y {r(1)}  BDE
3) {p(1)}  BDE
4) {q(1), t(1)}  BDE
q (1 )  s(1 )   r(1 )
Obtener transacciones que aseguren
una de estas cuatro situaciones
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
25
3.1 Actualización
Caracterización del problema:
1) Tiempo de generación de la solución.
2) Variables cuantificadas existencialmente
3) Recursividad
4) Información asumida
5) Tratamiento de restricciones de integridad
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
26
3.1 Actualización
1) Tiempo de generación de la solución.
Tiempo de ejecución: el árbol de derivación para el requisito de
actualización se genera cuando la actualización es solicitada.
Tiempo de definición: el árbol de derivación para un requisito de
actualización se estudia cuando se define el esquema de la base de
datos, lo que supone una mejora ya que determinadas tareas sólo
se realizan una vez.
Mixto: en este caso una parte de la solución se genera en tiempo
de definición del esquema y se completa en tiempo de ejecución.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
27
3.1 Actualización
En el Ejemplo 1:
 un método que obtuviese la solución en tiempo de
ejecución estudiaría el árbol de derivación de la
actualización p(1) para encontrar una solución.
 un método que trabajase en tiempo de definición del
esquema estudiaría el requisito genérico p(x) para
obtener soluciones que luego se instanciarían en tiempo
de ejecución.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
28
3.1 Actualización
2) Variables existencialmente cuantificadas.
Dada una regla deductiva de una base de datos normal, a las
variables que aparecen en el cuerpo de la regla y no aparecen en la
cabeza se les denomina variables existencialmente cuantificadas.
"x1 "xi "xm (A  L1    Ln)
 (xi no aparece en A)
"x1 "xi-1 "xi+1  "xm (A  xi (L1    Ln))
La presencia de variables existencialmente cuantificadas en las
reglas deductivas puede provocar la aparición del problema llamado
falta de valores durante la generación de las transacciones que
resuelven un requisito de actualización.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
29
3.1 Actualización
BDD: 1. p(x)  q(x,y)  t(x,y)
Ejemplo 2:
….
p(1)
1
t(1,2)
resolución
q(1,y)  t(1,y)
Actualización: U = p(1).
y (q(1,y)  t(1,y))
{y/--}
Una solución sencilla a este problema consiste en utilizar el valor nulo para la
variable de la que se desconoce el valor o bien un valor cualquiera proporcionado
por el usuario o extraído sin criterio de la base de datos. Aunque en ocasiones
esta solución es la única posible, en otras se puede elegir un valor tal que la
transacción obtenida sea más sencilla.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
30
3.1 Actualización
BDD: 1. p(x)  q(x,y)  t(x,y)
Ejemplo 2:
….
t(1,2)
p(1)
1
Actualización: U = p(1).
resolución
y (q(1,y)  t(1,y))
q(1,y)  t(1,y)
{y/ nulo}
T1 = { insertar(q(1,nulo)),
insertar(t(1,nulo))}
{y/ c}
{y/ 2}
T2 = { insertar(q(1, c)),
insertar(t(1, c))}
T3 = { insertar(q(1,2))}
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
31
3.1 Actualización
3) Recursividad.
La presencia de reglas recursivas en la base de datos puede
complicar la generación de la transacción, ya que el árbol de
derivación puede ser infinito para un determinado requisito de
actualización, lo que supone la existencia de infinitas
transacciones posibles para satisfacerlo.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
32
3.1 Actualización
Ejemplo 3:
BDD: 1. p(x,y)  q(x,y)
2. p(x,y)  q(x,z)  p(z,y)
Actualización: U = p(1,1).
Para satisfacer este requisito hay infinitas transacciones
posibles:
T1: {insertar(q(1,1))}
T2: {insertar(q(1,2)), insertar(q(2,1))}
T3: {insertar(q(1,2)), insertar(q(2,3)), insertar(q(3,1))}
…
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
33
3.1 Actualización
4) Problema de la información asumida.
En presencia de negación en las reglas deductivas, es posible
que algunas soluciones que podrían parecer correctas no lo
sean, ya que alguna información que se ha supuesto cierta (resp.
falsa), durante la construcción de la solución pase a ser falsa
(resp. cierta) debido a las actualizaciones propuestas más
adelante.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
34
3.1 Actualización
BDD: 1. p(x)  r(x,y)   s(x,y)  q(x,y)
Ejemplo 4:
2. s(1,2)  q(1,2)
r(1,2)
p(1)
1
Actualización: U = p(1).
resolución
r(1,y)  ¬ s(1,y)  q(1,y)
y (r(1,y)   s(1,y)  q(1,y))
{y/2}
r(1,2)  ¬ s(1,2)  q(1,2)
r(1,2)  BDE
s(1,2) fallo finito
T1 = { insertar( q(1,2)) }
q(1,2)  BDE
s(1,2)
s(1,2)
T1 no es una solución
correcta porque induce
la inserción de s(1,2)
que se había asumido
falsa en la construcción
de la solución.
2
resolución
q(1,2)
q(1,2)
2
resolución
q(1,2)
resolución
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
35
3.1 Actualización
5) Tratamiento de las restricciones de integridad.
La solución propuesta para un requisito de actualización
puede suponer la violación de alguna restricción de
integridad por lo que es interesante estudiar cómo integra
cada método, si lo hace, su estrategia con la comprobación
de las restricciones del esquema.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
36
3.1 Actualización
Ejemplo 5:
BDD: 1. p(x)  q(x)  r(x)
…
p(1)
1
W = "x (r(x)  t(x))
resolución
Actualización: U = p(1).
q(x)  r(x)
T1= { insertar(q(1)), insertar(r(1)) }
T1 no es una solución
correcta porque el estado
T1(BDD) viola la
restricción de integridad W
Un método que integre la generación de las soluciones con la restauración de la
integridad podría generar la transacción {insertar(q(1)), insertar(r(1)), insertar(t(1))}.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
37
3.1 Actualización
Estudio de un método de actualización:
1. Semántica asumida: la semántica declarativa determina el conjunto de
posibles soluciones al requisito de actualización y la semántica operacional
constituye la herramienta para computar esas soluciones.
2. Bases de datos: tipo de bases de datos y de restricciones de integridad
para los que está definido el método.
3. Requisitos de actualización: forma sintáctica de los requisitos de
actualización permitidos en el método.
4. Transacciones generadas: tipo de soluciones obtenidas y si sólo se
obtiene una o todas las soluciones posibles.
5. Descripción del método: estrategia seguida para generar las
transacciones.
6. Corrección y completitud del método.
7. Resumen: cómo el método resuelve los problemas antes mencionados.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
38
La Lógica en el desarrollo de las Bases de Datos
1. Lógica y Bases de Datos.
2. Bases de datos deductivas.
3. Actualización de bases de datos deductivas.
3.1 Actualización
3.2 Comprobación de la integridad
3.3 Restauración de la consistencia
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
39
3.2 Comprobación de la integridad
Restricción de integridad: propiedad del mundo real que una base de
datos debe satisfacer en cualquier instante para ser consistente con
cierto modelo del mundo real.
D0
T1
D1
Ti
Di
Tn
Dn
Evolución de una BD
Restricciones estáticas: hacen referencia a un único estado de la base de datos. Estas
restricciones restringen los estados válidos con independencia de la secuencia de los
mismos.
Restricciones dinámicas: hacen referencia a dos o más estados de la base de datos.
Estas restricciones restringen las secuencias de estados válidas. Un caso particular de
restricciones dinámicas son las restricciones de transición que restringen dos estados
consecutivos válidos.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
40
3.2 Comprobación de la integridad
Comprobación de la integridad: la comprobación de la integridad en
bases de datos consiste en comprobar si el par de estados (D,D')
implicados en una transacción T satisface las restricciones de
transición y si el estado final D' satisface las restricciones estáticas.
Método de comprobación de la integridad: es un procedimiento de
decisión tal que, dado un estado D y una restricción de integridad
estática W, decide con una respuesta binaria si/no si el estado D
satisface/viola la restricción estática W.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
41
3.2 Comprobación de la integridad
La forma más sencilla de comprobar las restricciones estáticas es evaluar
cada una de ellas después de la transacción; sin embargo esta
aproximación puede ser muy costosa en bases de datos voluminosas.
La comprobación de la integridad podría simplificarse si consideráramos
sólo los "cambios" que la transacción ha producido en la base de datos.
Todos los métodos propuestos para simplificar la comprobación de la
integridad suponen que la base de datos era íntegra antes de la
transacción. Apoyándose en esta hipótesis, los métodos comprueban sólo
instancias de las restricciones generadas a partir de las actualizaciones
(inserciones y borrados) de la transacción, evitando comprobar instancias
que ya se satisfacían antes de la transacción y que además no se ven
afectadas por ésta.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
42
3.2 Comprobación de la integridad
Comprobación simplificada de la integridad
en bases de datos relacionales:
PRECIOS (codprov: D4, codpieza: D1, precio: D7)
CP = {codprov, codpieza}
CAj = {codprov}  PROV
CAj = {codpieza}  PIEZA
W: "x "y "z ( (precios(x, y, z) w t (prov(x,w,t)) )
T = { insertar (PRECIOS (pv11,pz3,100)) }
D
T
D’
Si D es un estado íntegro
entonces
D’ satisface W si y sólo si D’ satisface w t (prov (pv11,w,t) )
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
43
3.2 Comprobación de la integridad
Comprobación simplificada de la integridad en
bases de datos deductivas:
En bases de datos deductivas las actualizaciones generadas
por una transacción no son sólo las explícitamente requeridas
por ésta (operaciones que la componen) sino también todas las
actualizaciones que se pueden inducir por la presencia de
reglas deductivas en la base de datos.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
44
COMP
D
COMPONENTE
pieza1
pieza2
pieza1
pieza2
pz1
pz3
pz1
pz3
pz3
pz8
pz3
pz8
pz1
pz8
Reglas deductivas:
COMPONENTE
COMPONENTE (x, y) COMP (x,z) COMPONENTE (z, y)
COMPONENTE (x, y) COMP (x, y)
Transacción: {insertar (COMP(pz8,pz1))}
D’
COMP
pieza1
pieza1
pieza2
pz1
pz3
pz3
pz8
pz1
pz8
pz8
pz1
pz8
pz3
pz8
pz8
pz1
pz1
pz3
pz1
pz3
pz3
pieza2
pz1
pz3
pz3
pz8
pz8
pz1
inserciones
inducidas
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
45
3.2 Comprobación de la integridad
Restricción de integridad:
W: "x "y ( COMPONENTE (x,y)   COMPONENTE (y,x) )
insertar ( COMPONENTE(pz8,pz1) )
 COMPONENTE (pz1, pz8)
Si D es un estado íntegro entonces
D’ satisface W si y sólo si D’ satisface  COMPONENTE (pz1, pz8)
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
D’ viola W
46
3.2 Comprobación de la integridad
Enunciado general del problema:
Dados, el esquema (L,RI) de una base de datos deductiva, un estado D de
ese esquema tal que D satisface W (para toda WRI), una transacción T
formada por dos conjuntos de sentencias de base de datos, T=TinsTdel,
(TinsTdel = , Tdel  D y TinsD =  ), el estado D’ resultante de aplicar a D la
transacción T, (D' = (DTins) \ Tdel), comprobar que D' satisface W (para toda
WRI).
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
47
3.2 Comprobación de la integridad
Caracterización del problema:
1) Concepto de satisfacción
2) Corrección y completitud de un método
2) Fases en la comprobación simplificada de la integridad
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
48
3.2 Comprobación de la integridad
1) Concepto de satisfacción:
a) Punto de vista de la demostración:
D satisface W sii Tr |= W.
b) Punto de vista de la consistencia:
D satisface W sii Tr  {W} es consistente.
El concepto de violación se define en términos del concepto de
satisfacción:
D viola W sii no (D satisface W).
Diremos que un estado D es íntegro si, para toda restricción W
perteneciente a RI, D satisface W.
Tr es la teoría de 1er orden que representa la base de datos en la semántica asumida
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
49
3.2 Comprobación de la integridad
Ejemplo 1:
D={
p(a)  q(x)  ¬r(x),
q(a),
r(x)  r(x) }.
Si asumimos la semántica de la compleción:
Tr=comp(D) = {"y(p(y)  y=a  x(q(x)  ¬r(x))),
" x(q(x)  x=a),
" x(r(x)  r(x)) }.
Desde el punto de vista de la consistencia D satisface: W1=q(a), W2=r(a),
W3=p(a), W4=¬r(a).
Desde el punto de vista de la demostración D satisface: W1=q(a).
Tr es la teoría de 1er orden que representa la base de datos en la semántica asumida
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
50
3.2 Comprobación de la integridad
Si asumimos la semántica del punto fijo iterado: MD={q(a), p(a)}
Tr(MD) = {"x (p(x)  x=a),
"x (q(x)  x=a),
"x (r(x) }.
D satisface W1=q(a) y W2=p(a) en los dos conceptos de satisfacción.
Tr es la teoría de 1er orden que representa la base de datos en la semántica asumida
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
51
3.2 Comprobación de la integridad
2) Corrección y completitud de un método:
Sean:
 M un método de comprobación de la integridad. D satisfaceM (resp. violaM) W significa
que el método M decide que el estado D satisface (resp. viola) la restricción W (WRI).
 CS el concepto de satisfacción asumido por el método M. D satisfaceCS (resp. violaCS) W
significa que el estado D satisface (resp. viola) la restricción W (WRI) en el concepto de
satisfacción CS.
Un método M es correcto cuando se cumple:
si D satisfaceM W entonces D satisfaceCS W (correcto para satisfacción)
si D violaM W entonces D violaCS W
(correcto para violación).
Un método M es completo cuando se cumple:
si D satisfaceCS W entonces D satisfaceM W (completo para satisfacción)
si D violaCS W entonces D violaM W
(completo para violación).
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
52
3.2 Comprobación de la integridad
3) Fases en la comprobación simplificada de la integridad
Hipótesis: D es íntegro.
Comprobación de la integridad:
FASE I: Fase de Generación
Paso 1:
Cálculo del conjuntos de literales que “representan” la diferencia
entre los estados consecutivos D y D'.
Paso 2:
Identificación de las restricciones relevantes.
Paso 3:
Instanciación de las restricciones relevantes.
Paso 4:
Simplificación de las instancias de las restricciones relevantes.
FASE II: Fase de Evaluación
Paso 5:
Comprobación en D' de las instancias simplificadas de las
restricciones relevantes.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
53
3.2 Comprobación de la integridad
3) Fases en la comprobación simplificada de la integridad
Ejemplo 2:
D={
p(x)  q(x,y)  ¬ t(y),
D’ = {
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  s(y),
q(a,b), q(b,a), s(c) }
t(y)  q(y,z)  t(z)
q(a,b), q(b,a), s(c), s(b) }
T= {ins(s(b), ins(t(y)  q(y,z)  t(z))}
W1 = "x "y ( q(x,y)  q(y,x) )
W2 = "x ( s(x)  p(x) )
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
54
Fase de Generación
Paso 1: Cálculo del conjuntos de literales que “representan” la diferencia
entre los estados consecutivos D y D'.
D’ = {
D={
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
T
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  q(y,z)  t(z)
q(a,b), q(b,a), s(c) }
q(a,b), q(b,a), s(c), s(b) }
T= {ins(s(b), ins(t(y)  q(y,z)  t(z))}
Actualizaciones inducidas por T:
Inserciones = {A: ABD, comp(D’) |= A y comp(D) |= A } = {s(b), t(a), t(b)}
Borrados = {A: ABD, comp(D) |= A y comp(D’) |= A } = {p(a), p(b)}
Se asume la semántica de la compleción y el punto de vista de la demostración.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
55
Fase de Generación
Paso 2: Identificación de restricciones relevantes
D’ = {
D={
p(x)  q(x,y)  ¬ t(y),
T
t(y)  s(y),
q(a,b), q(b,a), s(c) }
Inserciones = {s(b), t(a), t(b)}
T= {ins(s(b),
ins(t(y)  q(y,z)  t(z))}
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  q(y,z)  t(z)
q(a,b), q(b,a), s(c), s(b) }
W1 = "x "y ( q(x,y)  q(y,x) ) no es relevante para T
Paso 2
Borrados = {p(a), p(b)}
W2 = "x ( s(x)  p(x) ) es relevante para T
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
56
Fase de Generación
Paso 3: Instanciación de las restricciones relevantes
Paso 4: Simplificación de las instancias de las restricciones relevantes
D={
p(x)  q(x,y)  ¬ t(y),
D’ = {
T
t(y)  s(y),
q(a,b), q(b,a), s(c) }
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  q(y,z)  t(z)
Inserciones = {s(b), t(a), t(b)}
q(a,b), q(b,a), s(c), s(b) }
Borrados = {p(a), p(b)}
W2 = "x ( s(x)  p(x) )
W2 1= s(b)  p(b)
W2 1= p(b)
W2 2= s(a)  p(a)
W2 2= s(a)
W2 3= s(b)  p(b)
W2 3= s(b)
Paso 3
Paso 4
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
57
3.2 Comprobación de la integridad
3) Fases en la comprobación simplificada de la integridad
Hipótesis: D es íntegro.
Comprobación de la integridad:
FASE I: Fase de Generación
Paso 1:
Cálculo del conjuntos de literales que “representan” la diferencia
entre los estados consecutivos D y D'.
Paso 2:
Identificación de las restricciones relevantes.
Paso 3:
Instanciación de las restricciones relevantes.
Paso 4:
Simplificación de las instancias de las restricciones relevantes.
FASE II: Fase de Evaluación
Paso 5:
Comprobación en D' de las instancias simplificadas de las
restricciones relevantes.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
58
3.2 Comprobación de la integridad
3) Fases en la comprobación simplificada de la integridad
Hipótesis: D es íntegro.
Comprobación de la integridad:
Solución
FASE I: Fase de Generación Potencial
Paso 1:
Cálculo del conjuntos de literales que “capturen” la diferencia
entre los estados consecutivos D y D‘ sin acceder a la BDE.
Paso 2:
Identificación de las restricciones relevantes.
Paso 3:
Instanciación de las restricciones relevantes.
Paso 4:
Simplificación de las instancias de las restricciones relevantes.
FASE II: Fase de Evaluación
Paso 5:
Comprobación en D' de las instancias simplificadas de las
restricciones relevantes.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
59
Fase de Generación Potencial
Paso 1: Cálculo del conjuntos de literales que “capturen” la diferencia entre
los estados consecutivos D y D'.
D’ = {
D={
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
q(a,b), q(b,a), s(c) }
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
T
t(y)  q(y,z)  t(z)
q(a,b), q(b,a), s(c), s(b) }
T= {ins(s(b),
ins(t(y)  q(y,z)  t(z))}
Actualizaciones potenciales inducidas por T:
Inserciones
Borrados
Inserciones = {s(b), t(a), t(b)}
{s(b), t(y)}
{t(b)}
Actualizaciones reales
instancias inducidas por T:
{p(x)}
Borrados = {p(a), p(b)}
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
60
Fase de Generación Potencial
Paso 3: Instanciación de las restricciones relevantes
Paso 4: Simplificación de las instancias de las restricciones relevantes
D={
p(x)  q(x,y)  ¬ t(y),
D’ = {
T
t(y)  s(y),
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  q(y,z)  t(z)
q(a,b), q(b,a), s(c) } Inserciones = {s(b), t(y), t(b)}
Borrados = {p(x)}
q(a,b), q(b,a), s(c), s(b) }
W2 1= s(b)  p(b)
W2 = "x ( s(x)  p(x) )
W2 2= "x s(x)  p(x)
W2 = "x s(x)  p(x)
W2 3= "x s(x)  p(x)
Paso 3
Paso 4
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
61
Fase de Generación Potencial
Paso 3: Instanciación de las restricciones relevantes
Paso 4: Simplificación de las instancias de las restricciones relevantes
D={
p(x)  q(x,y)  ¬ t(y),
D’ = {
T
t(y)  s(y),
q(a,b), q(b,a), …, s(c) }
p(x)  q(x,y)  ¬ t(y),
t(y)  s(y),
t(y)  q(y,z)  t(z)
Inserciones = {s(b), t(y), t(b)}
Borrados = {p(x)}
q(a,b), q(b,a), …, s(c), s(b) }
Si la extensión de q es
grande los borrados
sobre p inducidos por T
pueden ser muchos.
W3 = "x ( p(x)  r(x) ) no es relevante para T.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
62
3.2 Comprobación de la integridad
Estudio de un método de simplificación:
1. Semántica asumida: referencia para interpretar el concepto de
satisfacción.
2. Concepto de satisfacción utilizado.
3. Requisitos sintácticos: forma sintáctica de las reglas y de las
restricciones de integridad.
4. Corrección y completitud del método.
5. Estrategia del método:
• Fase de Generación: potencial (sin acceso a la BDE), real (con
acceso a la BDE).
• Intercalación de las fases de Generación y Evaluación.
• Etapa de compilación independiente de la transacción.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
63
La Lógica en el desarrollo de las Bases de Datos
1. Lógica y Bases de Datos.
2. Bases de datos deductivas.
3. Actualización de bases de datos deductivas.
3.1 Actualización
3.2 Comprobación de la integridad
3.3 Restauración de la consistencia
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
64
3.2 Restauración de la consistencia
D
T = TinsTdel
U
D’
Actualización
Requisito de
actualización
D satisface W
Tr (D)
D’’
D' = (DTins) \ Tdel)
Tr (D’) |= U
|= U
Comprobación
RI
T’ = T’ins T’del
D‘’ = (D’T’ins) \ T’del)
Restauración
de la
consistencia
NO
SI
D’
Tr (D’’) |= U
D’’ satisface W ("W RI)
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
65
3.2 Restauración de la consistencia
Enunciado general del problema:
Dados, el esquema (L,RI) de una base de datos deductiva, un estado
D de ese esquema tal que D satisface W (para toda WRI), una
transacción T=TinsTdel, (TinsTdel = , Tdel  D y TinsD =  ), el estado
D’ resultante de aplicar a D la transacción T, (D' = (DTins) \ Tdel), y
una restricción WRI tal que D' viola W, encontrar una transacción
T*=T*insT*del (T*insT*del = , T*delTins = , T*insTdel = , ), tal que
el estado D’’ resultante de aplicar T* a D’, D‘’ = (D’T*ins) \ T*del),
satisface W.
Departamento de Sistemas Informáticos y Computación / Universidad Politécnica de Valencia
66
Descargar

BASES DE DATOS DEDUCTIVAS