17 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. BDD: 1. p(x) ? q(x,y) ? t(x,y) …. t(1,2) Actualización: U = p(1). Ejemplo 2: ¬ p(1) ¬ q(1,y) ? t(1,y) 1 resolución $y (q(1,y) Ù t(1,y)) {y/–}
18 BDD: 1. p(x) ? q(x,y) ? t(x,y) …. t(1,2) Actualización: U = p(1). Ejemplo 2: ¬ p(1) ¬ q(1,y) ? t(1,y) 1 resolución $y (q(1,y) Ù t(1,y)) T1 = { insertar(q(1,nulo)), insertar(t(1,nulo))} T2 = { insertar(q(1, c)), insertar(t(1, c))} T3 = { insertar(q(1,2))} {y/ nulo} {y/ c} {y/ 2}
19 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.
20 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))} …
BDD: 1. p(x,y) ? q(x,y) 2. p(x,y) ? q(x,z) ? p(z,y) Actualización: U = p(1,1). Ejemplo 3:
21 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.
22 BDD: 1. p(x) ? r(x,y) Ù Ø s(x,y) Ù q(x,y) 2. s(1,2) ? q(1,2) r(1,2) Ejemplo 4: Actualización: U = p(1). $y (r(1,y) Ù Ø s(1,y) Ù q(1,y)) ¬ p(1) ¬ r(1,y) ? ¬ s(1,y) ? q(1,y) 1 resolución {y/2} ¬ r(1,2) ? ¬ s(1,2) ? q(1,2) T1 = { insertar( q(1,2)) } r(1,2) ? BDE s(1,2) fallo finito q(1,2) ? BDE ¬q(1,2) q(1,2) resolución ¬ s(1,2) 2 resolución 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. ¬q(1,2) ¬ s(1,2) 2 resolución
23 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.
24 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))}. BDD: 1. p(x) ? q(x) Ù r(x) … W = ?x (r(x) ? t(x)) Actualización: U = p(1). ¬ p(1) 1 resolución T1= { insertar(q(1)), insertar(r(1)) } ¬ q(x) ? r(x) T1 no es una solución correcta porque el estado T1(BDD) viola la restricción de integridad W Ejemplo 5:
25 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.
26 Métodos: Método de Kakas y Mancarella Método de Guessoum y Lloyd
27 Método de Kakas y Mancarella Este método se basa en el procedimiento de abducción de Eshghi y Kowalski definido en [EK89]. Semántica asumida. semántica declarativa: modelo estable [GL88]. semántica operacional: procedimiento de abducción de Eshghi y Kowalski. Bases de datos. bases de datos localmente estratificadas sin restricciones de integridad específicas. [KM90] Kakas, A. C.; Mancarella, P. Database updates through abduction. Proc. 16th International Conference on Very Large Databases, 1990, págs. 650-661. [EK89] Eshghi, K.; Kowalski, R.A. Abduction compared with negation by failure. Proc. 6th International Conference on Logic Programming, MIT Press, 1989.
28 Marco Abductivo: Debido a la semántica operacional asumida, la base de datos se traduce a un marco abductivo. Dado un estado de base de datos D = BDE È BDI, el marco abductivo asociado con D es < BDI*, Ab, RI* > donde: BDI* es el conjunto de reglas deductivas obtenido a partir de BDI, reemplazando cada literal negativo Øq( ) por un nuevo literal positivo q*( ). Ab está formado por el conjunto de símbolos de predicados básicos junto con un nuevo predicado p* por cada predicado básico o derivado p. Ab es el conjunto de predicados abducibles. Un átomo es abducible si su predicado lo es. RI* es un conjunto de restricciones de integridad tal que para todo conjunto ? de hipótesis abducidas sobre predicados de Ab representadas por átomo abducibles, BDI* È D debe satisfacer: RI* = {? p() Ù p*() } È { p() Ú p*()} : p es un predicado de la base de datos. (Estas restricciones de integridad definen la equivalencia entre p*() y ? p()).
29 Ejemplo 6: BDI: 1. p(x) ? q(x) ? ¬ r(x) 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) }
30 Requisitos de actualización. insertar(A) o borrar(A) (A es un átomo derivado base)
Transacción generada. conjunto de operaciones de inserción y borrado de hechos.
Método de Kakas y Mancarella
31 Descripción del método. Dado un requisito de actualización insertar(p()) (resp. borrar(p())) el método distingue dos etapas: Paso A: Búsqueda de una derivación abductiva para ? p() (resp. ? p*()). Este paso devuelve un conjunto de hipótesis ? tal que: BDI* ? ? implica p() (resp. p*()) y tal que BDI* ? ? es consistente y no viola RI*. Paso B: Obtención de una transacción T sobre BDE tal que el estado T(D) implique cualquier hipótesis en ?.
Dado un átomo L = p() (resp. L = p*()) con la expresión L* se representará al átomo p*() (resp. p()). Una regla de selección R es segura si es una función parcial tal que dado un objetivo ? L1 ? … ? Lk (k ? 1) devuelve un átomo Lj (1 ? j ? k) tal que Lj no es abducible o Lj es abducible y base. Método de Kakas y Mancarella
32 Paso A: Procedimiento de demostración abductivo. El procedimiento abductivo se basa en las definiciones de derivación abductiva y derivación de consistencia. Método de Kakas y Mancarella
33 Derivación abductiva. Una derivación abductiva desde (G1 ?1) hasta (Gn ? n) vía una regla segura R es una secuencia (G1 ? 1), (G2 ? 2), …, (Gn ? n) tal que ?i (1 ? i ? n) Gi tiene la forma ? L1 ? … ? Lk, ? i es un conjunto de hipótesis abducibles, la regla R selecciona el literal Lj (1 ? j ? k) y (Gi+1 ? i+1) se obtiene de acuerdo con una de las siguientes reglas: Regla A1: Si Lj no es abducible entonces Gi+1 := C y ?i+1 := ? i donde C es el resolvente de alguna cláusula de BDI* con Gi sobre el literal Lj. Regla A2: Si Lj es abducible y Lj ? ? i entonces Gi+1 := ? L1 ? … ? Lj-1 ? Lj+1 ? … ? Lk y ? i+1 := ? i. Regla A3: Si Lj es abducible, es básico, Lj ? ? i y Lj* ? ? i entonces Gi+1 := ? L1 ? … ? Lj-1 ? Lj+1 ? … ? Lk y ? i+1 := ? i ? {Lj}. Regla A4: Si Lj es abducible, es derivado y Lj ? ? i y hay una derivación de consistencia desde ({? Lj*} ? i ? Lj) hasta ({ } ?’) entonces Gi+1 := ? L1 ? … ? Lj-1 ? Lj+1 ? … ? Lk y ? i+1 := ?’.
34 Derivación de consistencia. Una derivación de consistencia desde (F1 ?1) hasta (Fn ? n) vía una regla segura R es una secuencia (F1 ? 1), (F2 ?2), … , (Fn ? n) tal que ?i (1 ? i ? n) Fi tiene la forma { ? L1 ? … ? Lk} ? Fi’ siendo Fi’ un conjunto de objetivos, ? i es un conjunto de hipótesis abducibles, la regla R selecciona el literal Lj (1 ? j ? k) y (Fi+1 ? i+1) se obtiene de acuerdo con una de las siguientes reglas: Regla C1: Si Lj no es abducible entonces Fi+1 := C ? Fi’ donde C es el conjunto de todos los resolventes de cláusulas de BDI* con ? L1 ? … ? Lk sobre el literal Lj, [ ] ? C y ? i+1 := ? i. Regla C2: Si Lj es abducible, Lj ? ? i y k > 1 entonces Fi+1 := { ? L1 ? … ? Lj-1 ? Lj+1 ? … ? Lk} ? Fi’ y ? i+1 := ? i. Regla C3: Si Lj es abducible y Lj* ? ? i entonces Fi+1 := Fi’ y ? i+1 := ? i. Regla C4: Si Lj es abducible, es básico, Lj ? ? i y Lj* ? ? i entonces Fi+1 := Fi’ y ?i+1 := ? i ? {Lj*}. Regla C5: Si Lj es abducible, no es básico y existe una derivación abductiva desde (? Lj* ? i) hasta ([ ] ?’) entonces Fi+1 := Fi’ y ? i+1 := ?’.
35 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) }
36
37
38 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) }
39
40
| Página siguiente |