1
Introducción al problema.
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 requerimiento de actualización”
Ejemplo: DELETE FROM PRECIOS_EXT WHERE codprov=pv1
2
PIEZA
PRECIOS_EXT
PRECIOS
PROV
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))}
3
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
4
¬ precios_ext (pv1, x1, x2, x3, x4)
¬ prov (pv1, x1, x5) Ù pieza (x2,x3,x6) Ù precios (pv1,x2,x4)
¬ pieza (x2,x3,x6) Ù precios (pv1,x2,x4)
¬ precios (pv1,pz3,x4)
¬ precios (pv1,pz8,x4)
prov(pv1,Juan,1)
pieza(pz3,tuerca,11)
x2 / pz8, x3 / arandela
precios(pv1,pz3.10)
x4/ 10
x4/ 20
4
T1
T2
T2
T3
T3
SLDNF:
pieza(pz8,arandela,8)
x2 / pz3, x3 / tuerca
x1 / Juan
precios(pv1,pz8,20)
5
BDD: 1. q(x) ? ¬r(x) ? p(x)
2. q(x) ? s(x)
p(a)
¬ q(a)
¬ ¬ r(a) ? p(a)
¬ s(a)
¬ p(a)
T1 = { insertar (r(a)) }
T2 = { borrar (p(a)) }
Act: borrar(q(a))
¬ r(a)
p(a)
NF
resolución
1
resolución
2
6
BDD: 1. p(x) ¬ ¬q(x) Ù f(x)
2. p(x) ¬ s(x) Ù n(x)
3. s(x) ¬ r(x)
4. s(x) ¬ t(x) Ù ¬m(x)
r(a), q(a), m(a)
? p(a)
? ¬q(a) ? f(a)
? s(a) ? n(a)
? r(a) ? n(a)
? t(a) ? ¬m(a) ? n(a)
? n(a)
T1= {insertar (f(a)), borrar (q(a))}
T2 = {insertar (t(a)), borrar (m(a)), insertar (n(a))}
T3 = {insertar (n(a))}
Act: insertar(p(a))
1
resolución
2
3
4
resolución
r(a)
resolución
7
Procedimientos de borrado e inserción de una tupla de una relación derivada:
– reglas deductivas sin recursión (BDD jerárquicas)
– procedimiento de evaluación: SLDNF
– regla de selección de literales en un paso de derivación: seleccionar primero los literales derivados positivos y sólo seleccionar un literal negativo cuando es base.
Hipótesis:
Características:
– sólo actualizan la base de datos explícita
– procedimientos recursivos (se llaman mutuamente)
8
Procedimiento de borrado: Borrado (D, A, ?)
Entrada: una base de datos D y un requisito de borrado borrar(A) donde A es una tupla de una relación derivada
Salida: un conjunto de transacciones ?
Inicio
t:= un árbol SLDNF para D ? { ? A}
? := { [T1, …, Tn ]: (debe existir un Ti por cada rama de éxito del árbol t)
Ti = borrar(C) donde C es un hecho de D utilizado como cláusula de entrada en una rama de éxito de t
o
Ti = insertar(B) tal que B es básico y ¬B tiene éxito en una rama no fallada de t
o
Ti ? ? tal que ¬B tiene éxito en una rama no fallada de t, B es derivado y ? es la salida de la llamada al procedimiento de inserción con argumentos de entrada D y B }
Fin
9
Procedimiento de inserción: Inserción (D, A, ?)
Entrada: una base de datos D y un requisito de inserción insertar(A) donde A es una tupla de una relación derivada
Salida: un conjunto de transacciones ?
Inicio
? := { [T1, …, Tn ]: r:= una rama (derivación*) SLDNF fallada para D ? { ? A}
? L1 ? … ? Ln es el objetivo que falla en r, Li (i=1.. n) es base**
Ti = insertar (B) si Li = B y B es básico (hecho) y B ? D
o
Ti = borrar(B) si Li = ¬ B y B es básico (hecho) y B ? D
o
Ti ? ? si Li = ¬ B y B es derivado y ? es la salida de la llamada al procedimiento de borrado con argumentos de entrada D y B }
Fin
* seleccionar primero los literales derivados positivos y sólo seleccionar un literal negativo cuando es base (los literales se pueden seleccionar en cualquier orden)
** se deben buscar las derivaciones que cumplan esta propiedad porque a partir de ellas se pueden encontrar transacciones
10
BDD: 1. p(x) ¬ ¬q(x) Ù f(x)
2. p(x) ¬ ¬m(x) Ù n(x)
3. q(x) ¬ r(x) Ù ¬t(x)
r(a), m(a)
¬ p(a)
¬¬q(a) Ù f(a)
¬r(a) Ù ¬t(a)
¬¬m(a) Ù n(a)
¬ ¬t(a)
g1= {insertar(t(a))}
g2= {borrar(r(a))}
Act: insertar (p(a))
1
resolución
2
r(a)
resolución
¬ q(a)
NF
T1={borrar(m(a)), insertar(n(a))}
3
resolución
borrar(q(a))
T1 = {borrar (r(a)), insertar (f(a))}
T2 = {insertar (t(a)), insertar (f(a))}
11
Estudio avanzado del problema.
Enunciado 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’.
12
1. p(x) ? q(x) ? t(x)
2. p(x) ? w(x) ? v(x)
3. t(x) ? s(x) ? ¬r(x)
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
Ejemplo 1
Actualización: U = p(1)
Obtener transacciones que aseguren una de estas cuatro situaciones
13
Tiempo de generación de la solución.
Variables cuantificadas existencialmente
Recursividad
Información asumida
Tratamiento de restricciones de integridad
Caracterización del problema:
14
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.
15
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.
16
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.
Página siguiente  |