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 |