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
| Página siguiente |