Actualización de Vistas en Bases de Datos (página 3)

Partes: 1, 2, 3, 4

41
Paso B: Obtención de una transacción.
Sea ? un conjunto de hipótesis generadas por el procedimiento abductivo, T? es una transacción asociada a ? si dado un estado D, para cada átomo abducido básico L ? ? (resp. L* ? ? ), D’ |= L (resp. D’ |= ¬L) donde D’ es el estado de base de datos obtenido al aplicar T? a D.
Método de Kakas y Mancarella

42
Ejemplo 6:
BDI: 1. p(x) ? q(x) ? ¬ r(x) Actualización: U = insertar(p(1))
2. p(x) ? t(x)
3. r(x) ? s(x)
Marco abductivo:
BDI* = {p(x) ? q(x) ? r*(x), Ab = {q, s, t, p*, q*, r*, s*, t*}
p(x) ? t(x),
r(x) ? s(x)}
RI* = { ? p(x) ? p*(x), p(x) ? p*(x),
? q(x) ? q*(x), q(x) ? q*(x),
? r(x) ? r*(x), r(x) ? r*(x),
? s(x) ? s*(x), s(x) ? s*(x),
? t(x) ? t*(x), t(x) ? t*(x) }

43
? T?1 = { insertar(t(1)) }
? T?2= {insertar(q(1)), borrar(s(1))}
BDE: s(1)

44
Ejemplo 6:
BDI: 1. p(x) ? q(x) ? ¬ r(x) Actualización: U = borrar(p(1))
2. p(x) ? t(x)
3. r(x) ? s(x)
Marco abductivo:
BDI* = {p(x) ? q(x) ? r*(x), Ab = {q, s, t, p*, q*, r*, s*, t*}
p(x) ? t(x),
r(x) ? s(x)}

RI* = { ? p(x) ? p*(x), p(x) ? p*(x),
? q(x) ? q*(x), q(x) ? q*(x),
? r(x) ? r*(x), r(x) ? r*(x),
? s(x) ? s*(x), s(x) ? s*(x),
? t(x) ? t*(x), t(x) ? t*(x) }

45
BDE: q(1)
t(1)
? T?3= {borrar(q(1)), borrar(t(1))}
? T?4= {insertar(s(1)), borrar(t(1))}

46
Corrección y completitud.
Corrección: Sea D una base de datos localmente estratificada, U un requisito insertar(L) (resp. borrar(L)). Si hay una derivación abductiva desde (?L {}) (resp. (?L* {})) hasta ([] ?) entonces para cualquier base de datos extensional se cumple que |=MD’ L (resp. |=MD’ ¬L) donde D’ es el estado de base de datos obtenido al aplicar a D una transacción asociada a D y MD’ es el modelo estable de D’.

Completitud: Sea D = BDI ? BDE un estado de base de datos cuya parte intensional cumple las propiedades de ser acíclica y de no tener variables existencialmente cuantificadas, U un requisito insertar(L) (resp. borrar(L)). Si existe una parte extensional BDE’ tal que |=MD’L (resp. |=MD’¬L) donde D’ = BDI ? BDE’ y MD’ es el modelo estable de D’ entonces hay una derivación abductiva desde (? L {}) (resp. (? L* {})) hasta ([] ?) tal que L’ ? BDE’ (resp. L’ ? BDE’) para cada átomo abducible básico L’ ? ? (resp. L’* ? ?).
Método de Kakas y Mancarella

47
Resumen:
Los requisitos de actualización sólo pueden ser inserciones o borrados de tuplas base sobre predicados derivados no admitiendo requisitos más generales.
Obtiene las soluciones (conjunto ?) en tiempo de ejecución pero sin acceder al conjunto de hechos.
Debido a la regla de selección segura que utiliza el método, no se pueden elegir en las derivaciones las reglas deductivas con variables existencialmente cuantificadas por lo que no se aporta solución al problema de falta de valores.
Debido al problema anterior, el método no puede tratar con reglas recursivas. En el caso de predicados derivados definidos recursivamente sólo se consideraría las reglas que definen el caso base encontrándose soluciones sólo en el caso de requisitos de inserción.
En [KM90] se comenta que el método puede extenderse fácilmente para comprobar las restricciones de integridad durante el paso de obtención de las hipótesis
El problema de la información asumida es controlado por el método en la regla A3 de la derivación abductiva y en la regla C4 de la derivación de consistencia ya que en ellas la abducción de un literal se realiza tras comprobar que su complementario no pertenece ya al conjunto de hipótesis.

48
Método de Guessoum y Lloyd
Semántica asumida.
semántica declarativa: la compleción.
semántica operacional: procedimiento SLDNF
Base de Datos.
bases de datos localmente consistentes en llamada
el conjunto de predicados básicos y el conjunto de predicados derivados pueden no ser disjuntos.
las restricciones de integridad se representan por fórmulas cerradas bien formadas.
[GL90] Guessoum, A.; Lloyd, J. W. Updating knowledge bases. New Generation Computing, Vol. 8, 1990, págs. 71-89.
[GL91] Guessoum, A.; Lloyd, J. W. Updating knowledge bases II. New Generation Computing, Vol. 10, 1991, págs. 73-100.

49
Requisito de actualización.
insertar(A) (resp. borrar(A)) (A es un átomo).

Transacción generada.
inserción y borrado de hechos y reglas deductivas

En el caso de la inserción de reglas deductivas, éstas sólo pueden ser de la forma A ?, donde A es un átomo que no es base (esto significa que se admite la inserción de reglas deductivas dependientes del dominio). Así pues la transacción obtenida es un conjunto de operaciones de la forma insertar(C) donde C es un átomo que, si es base es un hecho y si no lo es representa una regla deductiva sin cuerpo, o de la forma borrar(C) donde C es una sentencia de base de datos (hecho o regla deductiva).
Método de Guessoum y Lloyd

50
Descripción del método.
El método de actualización se basa en los procedimientos:
Borrado
Inserción
que utilizan a su vez los procedimientos básicos:
Borrado-Básico
Inserción-Básica
que se llaman recursivamente entre sí.

En estos procedimientos, que se presentan a continuación, se utiliza el concepto de árbol SLDNF trivial que es aquél que sólo consta del nodo raíz.
Método de Guessoum y Lloyd

51
ALGORITMO Borrado
ENTRADA
D: Estado de base de datos;
U = borrar(A) : Requisito de actualización de borrado;
RI: Conjunto de restricciones de integridad;
SALIDA:
? : Conjunto de transacciones;
INICIO
SI comp(D) |= A
ENTONCES
Borrado_Básico (D, A, t0);
t := {T : T ? t0, comp(T(D)) |¹ A y T(D) satisface RI}
FIN_SI
FIN.

52
ALGORITMO Borrado_Básico
ENTRADA
D: Estado de base de datos;
A: átomo;
SALIDA:
t0: Conjunto de transacciones;
INICIO
t := árbol SLDNF finito que no sea trivial para D È { ? A};
t0 := {[T1, ¼ , Tn] : existe un Ti (no necesariamente distinto) para cada rama que no sea fallada de t, tal que
Ti = borrar(Ci) donde Ci es una sentencia de D utilizada como cláusula de entrada en una rama no fallada de t
o
Ti ? ti tal que ØB tiene éxito en una rama no fallada de t y ti es la salida de la llamada al procedimiento de Inserción_Básica con argumentos de entrada D y B}
FIN.

53
ALGORITMO Inserción
ENTRADA
D: Estado de base de datos;
U = insertar(A) : Requisito de actualización de inserción;
RI: Conjunto de restricciones de integridad;
SALIDA
t : Conjunto de transacciones;
INICIO
SI comp(D) |¹ A
ENTONCES}
Inserción_Básica(D, A, t0);
t := {T|T? t0, comp(T(D)) |= A y T(D) satisface RI}
FIN.

54
ALGORITMO Inserción_Básica
ENTRADA
D: Estado de base de datos;
A: átomo;
SALIDA
t0: Conjunto de transacciones;
INICIO
t := un árbol SLDNF finito para D È { ? A};
t0 := {[T1, ¼ , Tn] : ? L1, ¼ , Ln es un objetivo en t tal que Li es base si es negativo y,
o
Ti = insertar(Ai) si Li = Ai (donde Ai es un átomo)
o
Ti ? ti si Li = ØBi (donde Bi es un átomo) y ti es la salida de la llamada al procedimiento Borrado_Básico con argumentos de entrada D y Bi}
FIN.

55
Ejemplo 7:
BDI: 1. p(x) ? q(x) ? ¬ r(x) Actualización: U = insertar(p(1))
2. p(x) ? t(x)
3. r(x) ? s(x)
s(1)
El procedimiento Inserción llama al procedimiento Inserción_Básica tras comprobar que p(1) no es consecuencia lógica de comp(D) ; supóngase que este procedimiento construye el árbol SLDNF que se muestra a continuación.

56

? p(1) ? T1 = {insertar(p(1))}
? t(1) ? T2 = {insertar(t(1))}
? q(1) ? ?r(1) ? T3 = {insertar(q(1)), borrar(r(x) ? s(x))}
? q(1) ? ? r(1) ? T4 = {insertar(q(1)), borrar(s(1))}

En las transacciones T3 y T4 la segunda operación se obtiene de la salida del procedimiento Borrado_Básico con el átomo de entrada r(1) que estudia el siguiente árbol SLDNF.
Inserción_Básica

57

T1’ = { borrar (r(x) ? s(x)) }
T2’ = { borrar (s(1)) }

Borrado-Básico

58
Ejemplo 8:
BDI: 1. p(x) ? q(x) ? ¬ r(x) Actualización: U = borrar(p(1))
2. p(x) ? t(x)
3. r(x) ? s(x)
q(1)
t(1)
El procedimiento Borrado llama al procedimiento Borrado_básico tras comprobar que comp(D) |= p(1); supóngase que este procedimiento construye el árbol SLDNF que se muestra a continuación.

59
T1 = {borrar(p(x) ? q(x) ? ¬r(x)), borrar(p(x) ? t(x)) } T5 = { insertar(r(1)), borrar(p(x) ? t(x)) }
T2 = {borrar(p(x) ? q(x) ? ¬ r(x)), borrar(t(1)) } T6 = { insertar(r(1)), borrar(t(1)) }
T3 = {borrar(q(1)), borrar(p(x) ? t(x)) } T7 = { insertar(s(1)), borrar(p(x) ? t(x)) }
T4 = {borrar(q(1)), borrar(t(1)) } T8 = { insertar(s(1)), borrar(t(1)) }
Borrado_Básico

60
T1’ = { insertar (r(1)) }
T2’ = { insertar (s(1)) }
Inserción_Básica