17 Método de Nicolas: Restricciones de integridad relevantes para T: Si W es una restricción de integridad de rango restringido [Nic82] (independiente del dominio), podemos afirmar que: "W es relevante respecto a la inserción (resp. borrado) de la tupla en R si y sólo si R(e1,e2,…,en) es unificable con un átomo que ocurre negativamente (resp. positivamente) en W". Un átomo A ocurre negativamente (resp. positivamente) en una fórmula W sii ¬A (resp. A) aparece en la forma prenexa normal de W. Ejemplo: W1 y W2 son relevantes respecto a las dos operaciones de la transacción.
18 Método de Nicolas: Instancias de las restricciones de integridad: Sea: • W una restricción de integridad relevante respecto a la inserción (resp. borrado) de en R. • ? el unificador más general que unifica R(e1,e2,…,en) con un átomo que ocurre negativamente (resp. positivamente) en W. • ? la restricción de ? a aquellas variables cuantificadas universalmente no precedidas de un cuantificador existencial. Entonces, definimos una instancia de W generada por la inserción (resp. borrado) de en R como la fórmula W?.
19 Método de Nicolas: Ejemplo: a) La sustitución ? no debe aplicarse a las variables cuantificadas existencialmente. La operación borrar(q(2,1,1)) genera una instancia de W1: ? = {z/2, x/1, y/1} W1? = p(1,1) ? q(2,1,1). D' no satisface W1?. y sin embargo D' satisface W1. b) La sustitución ? no debe aplicarse a las variables cuantificadas universalmente precedidas de un cuantificador existencial. La operación borrar(q(2,1,1)) genera una instancia de W2: ? = {z/2, x/1, y/1} W2? = p(1,1) ? q(2,1,1). D' no satisface W2? y sin embargo D' satisface W2. En nuestro ejemplo las instancias de las restricciones generadas por la transacción son: Para W1: insertar(p(3,3)): ?1= {x/3, y/3}, W1?1= p(3,3) ??z q(z,3,3) borrar(q(2,1,1)): ?2 = {x/1, y/1}, W1?2 = p(1,1) ??z q(z,1,1). Para W2: W2 es relevante para la transacción pero no se generan instancias de ella.
20 Método de Nicolas: Simplificación de las instancias: Las instancias de W pueden simplificarse reemplazando las ocurrencias de R(e1,e2,…,en) por el valor cierto (resp. falso) si la transacción ha insertado (resp. borrado) la tupla en R y aplicando reglas de absorción. Ejemplo: (W1 ?1)s = ?z q(z,3,3) (W1 ?2)s = p(1,1) ??z q(z,1,1).
21 Método de Nicolas: Comprobación de la integridad (método de Nicolas): RI = { W1 = ?x ? y (p(x,y) ? ?z q(z,x,y)) W2 = ?z ? x ? y (p(x,y) ? q(z,x,y)) }.
W1s=(W1 ?1)s ? (W1 ?2)s = ?z q(z,3,3) ? (p(1,1) ? ?z q(z,1,1))
D' satisface W1s, entonces D' satisface W1. D' satisface W2.
22 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
23 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
24 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
25 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 Paso1: Cálculo de conjuntos de literales que “representen” 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.
26 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).
27 Estudio de un método de simplificación: Semántica asumida. Concepto de satisfacción. 3. Requisitos sintácticos: forma sintáctica de las reglas y de las restricciones de integridad. 4. Corrección y completitud del método. 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
28 Métodos: Método de Lloyd, Sonnenberg y Topor Método de Sadri y Kowalski
29 Método de Lloyd, Sonnenberg y Topor Concepto de satisfacción Este método utiliza el punto de vista de la demostración con Tr = comp(D) ? {ACD}:
D satisface W sii Tr |= W.
30 Actualizaciones potenciales: Sea T una transacción y D y D' los estados consecutivos relacionados con T tales que D?D'; entonces, se definen posD,D' (conjunto de inserciones potenciales) y negD,D' (conjunto de borrados potenciales) inductivamente de la forma siguiente: Po D,D‘ 0 = {A: A? W ? D' D} (inserciones potenciales explícitas) PosD,D‘ n+1 = {A? : A ? W ? D, B ocurre positivamente en W, C ? posD,D‘n y ? = mgu(B,C)} ? {A? : A ? W ? D, B ocurre negativamente en W, C ? negD,D‘n y ? = mgu(B,C)} (inserciones potenciales inducidas) NegD,D‘0 = ? (borrados potenciales explícitos) NegD,D‘n+1 = {A? : A ? W ? D, B ocurre positivamente en W, C ? negD,D‘n y ? = mgu(B,C)} ? {A ? : A ? W ? D, B ocurre negativamente en W, C ? posD,D‘n y ? = mgu(B,C)} (borrados potenciales inducidos) posD,D‘ = ?n?0 posD,D‘n negD,D‘ = ?n?0 negD,D‘n
31 Actualizaciones potenciales: Según la anterior definición, la obtención de los conjuntos posD,D‘ y negD,D‘ podría significar el cálculo de infinitos conjuntos posD,D‘n y negD,D'n . En la práctica, el cálculo puede realizarse en un número finito de pasos si se utiliza alguna regla de parada del tipo siguiente: en lugar de calcular los conjuntos posD,D‘n y negD,D‘n calcular los conjuntos Pn y Nn definidos de la siguiente forma: Pn (resp. Nn) = {A: A ? posD,D‘n (resp. NegD,D‘n) y ? A' ? posD,D‘k (resp. NegD,D‘k) (0 ? k ? n) tal que A es una instancia de A'}. La computación finaliza cuando, para un valor de n, los conjuntos Pn y Nn son vacíos. El conjunto posD,D‘ (resp. negD,D‘) se caracteriza porque cualquier inserción (resp. borrado) real es una instancia de alguno de sus elementos.
32 Teorema de Simplificación Sea: • (L,RI) el esquema de una base de datos deductiva, donde: – L es un lenguaje de primer orden heterogéneo. Los conjuntos de símbolos de constante, función y predicado de L son finitos. – RI = {W: W=?x1 ?x2… ?xn W'} es el conjunto de restricciones de integridad, fórmulas cerradas de L en forma prenexa normal. • D un estado de la base de datos: D = {A? B: A es un átomo, B es una fbf }. • La semántica asumida es la de la compleción más el axioma de cierre de dominio. La teoría que representa el estado D es Tr = comp(D) ? {ACD}. Es importante destacar que comp(D) y ACD son las versiones con tipos de la compleción de D y del axioma de cierre de dominio [Llo87]. • T una transacción formada por dos conjuntos de cláusulas: Tdel: borrados de T Tins: inserciones de T. La transacción no es contradictoria (no inserta y borra la misma cláusula) y además no modifica el lenguaje L.
33 Teorema de Simplificación Sea: • D'' y D' estados tales que: D'' = D Tdel y D' = D'' ? Tins. • D y D' son estratificadas. • W una restricción de integridad tal que D satisface W. • ? = { ?: ? es la restricción a x1,x2,…,xn del unificador más general entre un átomo que ocurre negativamente en W y un átomo de posD'',D‘ o de un átomo que ocurre positivamente en W y un átomo de negD'',D‘ }. • ? = {?: ? es la restricción a x1,x2,…,xn del unificador más general entre un átomo que ocurre positivamente en W y un átomo de posD'',D o de un átomo que ocurre negativamente en W y un átomo de negD'',D }. Se cumple: a) D' satisface W sii D' satisface ? (W‘?) para todo ? ? ? ? ?. b) Si D' ? {? ?(W‘?)} tiene una refutación SLDNF para todo ? ? ? ? ?, entonces D' satisface W. c) Si D' ? {? ?(W‘?)} tiene un árbol SLDNF fallado finitamente para algún ? ? ? ? ?, entonces D' viola W. Si ? ? ? es el conjunto vacío, W no se ve afectada por la transacción. Si ? ? ? ? ? , W no admite simplificación.
34 Resumen. Semántica asumida: semántica de la compleción. Concepto de satisfacción: punto de vista de la demostración. Tipo de base de datos: las reglas deductivas son cláusulas generales de la forma A? W. Restricciones sintácticas: la base de datos debe ser estratificada. Las restricciones de integridad son fórmulas cerradas en forma prenexa normal. Estrategia: Fase de Generación potencial (sin acceso a la BDE). Método de Lloyd, Sonnenberg y Topor
35 Método de Sadri y Kowalski Concepto de satisfacción Este método utiliza el punto de vista de la consistencia, con Tr=comp(D) (semántica de la compleción): D satisface W sii Tr ? {W} es consistente
36 Método de Sadri y Kowalski Actualizaciones de la transacción Sea T= Tins ?Tdel una transacción formada por dos conjuntos de cláusulas. El conjunto ACT de actualizaciones de la transacción se define: ACT= { A: A?L1 ? L2 ? … ? Ln ? Tins} ? {¬A: A? ? Tdel y existe un árbol SLDNF fallado finitamente para D' ? {?A}} ? { ¬A?: A? L1 ? L2 ? … ? Ln ?Tdel, ? es una respuesta computada para D ? {? L1 ?L2 ?… ?Ln} y existe un árbol SLDNF fallado finitamente para D' ? {? A?} }.
37 Método de Sadri y Kowalski Procedimiento SLDNF* (SLDNF extendido) Sea: • S = D ? RI donde: – D es un conjunto de cláusulas de la forma: A ? L1 ? L2 ? … ? Ln (n ? 0) – RI un conjunto de cláusulas de la forma: ? L1 ? L2 ? … ? Ln (n>0) (Li es un literal; si Li es positivo (resp. negativo) le denominaremos condición positiva (resp. condición negativa)). • C0 una cláusula de S o un átomo negado (¬A) tal que existe un árbol SLDNF* fallado finitamente para S ? {?A}. • R una regla de computación segura.
38 Método de Sadri y Kowalski Procedimiento SLDNF* (SLDNF extendido) Una derivación vía R para S ? {C0} es una secuencia posiblemente infinita C0, C1, C2… tal que, Ci (i>0) es una cláusula, y para todo i?0, Ci+1 se obtiene a partir de Ci de la siguiente forma: a) Si R selecciona de Ci un literal L que no es una condición negativa de Ci, entonces Ci+1 es el resolvente sobre L de Ci y alguna cláusula de S. b) Si R selecciona una condición negativa ¬A de Ci, entonces Ci+1 es Ci eliminando el literal seleccionado, ¬A, si existe un árbol SLDNF* fallado finitamente para S ? {?A}. c) Si Ci es ¬A y en S hay una cláusula B?¬A‘ ? C de forma que A y A' unifican a través del unificador más general ?, entonces Ci+1 es (B?C) ?. El SLDNF* es correcto para consistencia: "Si existe una refutación SLDNF* para S ? {C0} entonces comp(D) ? RI es inconsistente"
39 Método de Sadri y Kowalski Teorema de simplificación Sea: • (L,RI) el esquema de una base de datos deductiva, donde: – L es un lenguaje de primer orden y – RI es el conjunto de restricciones de integridad, fórmulas cerradas de L. • {?incw: incw?¬W, W?RI} el conjunto de restricciones de integridad en forma negada (las cláusulas resultantes de aplicar el algoritmo Lloyd y Topor [LT84] a {incw ? ¬W: W?RI} deben ser de rango restringido y formar parte de cualquier estado de la base de datos). • D un estado de la base de datos: D= {A?L1? L2 ? … ? Ln: A es un átomo, Li es un literal y n ? 0}. • La semántica asumida es la de la compleción.
40 Método de Sadri y Kowalski Teorema de simplificación Sea: • T una transacción formada por dos conjuntos de cláusulas, el conjunto Tins de inserciones y un conjunto Tdel de borrados. • D' el estado resultante de aplicar a D la transacción T: D‘ = (D?Tins)Tdel. • D y D' son estratificados y de rango restringido. • W una restricción de integridad tal que D satisface W. Se cumple: "Si existe una refutación SLDNF* para D' ? RI ? {C0} para alguna actualización C0 de la transacción entonces D' viola RI".
| Página siguiente |