Comprobación de restricciones de integridad
2 Restricción de integridad: propiedad del mundo real que una base de datos debe satisfacer en cualquier instante para ser consistente con cierto modelo del mundo real. Comprobación de restricciones de integridad Introducción al problema D0 T1 D1 Ti Di Evolución de una BD Tn Dn Restricciones estáticas: hacen referencia a un único estado de la base de datos. Estas restricciones restringen los estados válidos con independencia de la secuencia de los mismos. Restricciones dinámicas: hacen referencia a dos o más estados de la base de datos. Estas restricciones restringen las secuencias de estados válidas. Un caso particular de restricciones dinámicas son las restricciones de transición que restringen dos estados consecutivos válidos.
3 Comprobación de la integridad: la comprobación de la integridad en bases de datos consiste en comprobar si el par de estados (D,D') implicados en una transacción T satisface las restricciones de transición y si el estado final D' satisface las restricciones estáticas. Método de comprobación de la integridad: es un procedimiento de decisión tal que, dado un estado D y una restricción de integridad estática W, decide con una respuesta binaria si/no si el estado D satisface/viola la restricción W.
4 La forma más sencilla de comprobar las restricciones estáticas es evaluar cada una de ellas después de la transacción; sin embargo esta aproximación puede ser muy costosa en bases de datos voluminosas. La comprobación de la integridad podría simplificarse si consideráramos sólo los "cambios" que la transacción ha producido en la base de datos. Todos los métodos propuestos para simplificar la comprobación de la integridad suponen que la base de datos era íntegra antes de la transacción. Apoyándose en esta hipótesis, los métodos comprueban sólo instancias de las restricciones generadas a partir de las actualizaciones (inserciones y borrados) de la transacción, evitando comprobar instancias que ya se satisfacían antes de la transacción y que además no se ven afectadas por ésta.
5 Comprobación simplificada de la integridad en bases de datos relacionales: PRECIOS (codprov: D4, codpieza: D1, precio: D7) CP = {codprov, codpieza} CAj = {codprov} ® PROV CAj = {codpieza} ® PIEZA W: "x "y "z ( (precios(x, y, z) ® $w $t (prov(x,w,t)) ) T = { insertar (PRECIOS (pv11,pz3,100)) } D T D’ Si D es un estado íntegro entonces D’ satisface W si y sólo si D’ satisface $w $t (prov (pv11,w,t) )
6 Comprobación simplificada de la integridad en bases de datos relacionales: Paso 1: detectar restricciones de integridad relevantes para la transacción Paso 2: obtener instancias simplificadas de las restricciones de integridad relevantes para la transacción Paso 3: simplificar las instancias de las restricciones de integridad relevantes para la transacción Paso 4: evaluar las instancias simplificadas de las restricciones de integridad relevantes en el nuevo estado
7 Paso 1: detectar restricciones de integridad relevantes para la transacción: W: "x "y "z ( (precios(x, y, z) ® $w $t ( prov(x, w, t)) ) insertar (PRECIOS (-, -,-)) borrar (PROV (-, -,-)) Paso 2: obtener instancias de las restricciones de integridad relevantes para la transacción W: "x "y "z ( (precios(x, y, z) ® $w $t (prov(x, w, t)) ) insertar (PRECIOS (pv11, pz3,100)) W’: (precios (pv11, pz3,100) ® $w $t (prov (pv11, w, t))
8 D’ viola W W’’: $w $t (prov (pv11, w, t)) D’ satisface W si y sólo si D’ satisface W’’ Paso 3: simplificar las instancias de las restricciones relevantes $w $t (prov (pv11, w, t) es falso en D’ Teorema de simplificación Paso 4: evaluar las instancias simplificadas de las restricciones de integridad relevantes en el nuevo estado
9 Las actualizaciones generadas por una transacción no son sólo las explícitamente requeridas por ésta (operaciones que la componen) sino también todas las actualizaciones que se pueden inducir por la presencia de reglas deductivas en la base de datos. Comprobación simplificada de la integridad en bases de datos deductivas:
10 Paso 1: determinar el conjunto de actualizaciones inducidas por la transacción: Act
Paso 2: detectar restricciones de integridad relevantes respecto al conjunto de actualizaciones Act Paso 3: obtener instancias de las restricciones de integridad relevantes Paso 4: simplificar las instancias de las restricciones de integridad relevantes Paso 5: evaluar las instancias simplificadas de las restricciones de integridad relevantes en el nuevo estado Comprobación simplificada de la integridad en bases de datos deductivas:
11 COMP COMPONENTE COMPONENTE (x, y) ¬ COMP (x,z) ÙCOMPONENTE (z, y) COMPONENTE (x, y) ¬ COMP (x, y) Reglas deductivas: Transacción: {insertar (COMP(pz8,pz1))} COMP COMPONENTE Paso 1
12 W: "x "y ( COMPONENTE (x,y) ® Ø COMPONENTE (y,x) ) Restricción de integridad: insertar (COMPONENTE(pz8,pz1)) W’: COMPONENTE (pz8, pz1) ® Ø COMPONENTE (pz1, pz8) W’’: Ø COMPONENTE (pz1, pz8) Ø COMPONENTE (pz1, pz8) es falso en D’ D’ viola W Paso 2 Paso 3 Paso 4 Paso 5
13 Estudio avanzado del problema Enunciado del problema Método de simplificación de Nicolas para base de datos relacionales Concepto de satisfacción Corrección y completitud de un método de simplificación Fases en la comprobación simplificada de la integridad Métodos de comprobación simplificada en bases de datos deductivas: Estudio de un método de simplificación Métodos
14 Enunciado del problema: Dados: • el esquema (L,RI) 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. • un estado D de la base de datos: D = {A: A es un átomo base} (hechos) ? {A? W: A es un átomo y W es una fórmula bien formada} (reglas) tal que D satisface W (para toda W ? RI). • una transacción T formada por dos conjuntos de sentencias de base de datos: – Tins: hechos y reglas que van a ser insertados por la transacción y – Tdel: hechos y reglas que van a ser borrados por la transacción. ( Tins ? Tdel = ?, Tdel ? D y Tins ? D = ? ) . • el estado D' resultante de aplicar a D la transacción T: D' = (D ? Tins) Tdel. Comprobar: D' satisface W (para toda W ? RI).
15 Método de Nicolas para la comprobación simplificada de la integridad en bases de datos relacionales: Dado un estado íntegro D y una transacción T, obtener instancias simplificadas de las restricciones de integridad relevantes para la transacción, que será suficiente comprobar en D‘=T(D) para asegurar su integridad. En el trabajo original de Nicolas, [Nic79], [Nic82], una base de datos relacional se formaliza como una interpretación I de unlenguaje de 1er orden; dicha interpretación se construye a partir de la extensión de la base de datos [NG78]. En esta formalización el concepto de satisfacción utilizado es el siguiente: D satisface W sii |=I W.
16 Método de Nicolas : Ejemplo: D = { p(1,1), p(2,2) q(1,1,1), q(1,2,2), q(2,1,1), q(1,3,3) } RI = { W1 = ?x ?y (p(x,y) ? ?z q(z,x,y)) W2 = ?z ?x ?y (p(x,y) ? q(z,x,y)) }
T: Tins= {p(3,3)} Tdel={q(2,1,1)}
| Página siguiente |