Com es pot preservar la consistència de les dades?

Enviat per Xavier Oriol el Dv, 21/07/2017 - 11:55

Introducció

És innegable que, a ple segle XXI, tota empresa que s'apreciï es gestiona mitjançant algun tipus de sistema d'informació. Així, a ningú se li fa estrany pensar que tot hospital, banc, o universitat té a darrere un sistema d'informació que registra les dades dels seus pacients, clients o estudiants.
Malauradament, és possible que algun usuari del sistema, innocent o amb mala bava, modifiqui incorrectament les dades que s'hi enregistren. Aquestes incorreccions donen lloc a inconsistències. Per exemple, un administratiu despistat pot indicar que el director de l'oficina d'un banc del carrer Aribau és un treballador d'una oficina de Travessera de les Corts. En aquest cas, és innegable pensar que l'estat de les dades és inconsistent en tant com un director de banc no pot córrer tan de pressa.
El problema de què parlarem en aquest article és com evitar les inconsistències de les dades. El tema és suficientment complex com per fer-ne una tesi doctoral, i suficientment actual com per defensar-la abans d'anar de vacances, però mirarem de donar-ne en aquest article només quatre pinzellades bàsiques.

Definint restriccions d'integritat

Si volem que el sistema d'informació no enregistri estats de dades inconsistents, primerament, necessitem que el sistema sàpiga distingir quins estats de dades són inconsistents. L'estratègia bàsica seguida en l'enginyeria del software i les bases de dades per distingir els estats consistents dels inconsistents és la definició de restriccions d'integritat. Una restricció d'integritat és una condició que tot estat consistent de les dades satisfà. Per tant, si la restricció es viola, ens trobem, de totes totes, davant d'un estat de dades inconsistent.

Per exemple, en el nostre banc podríem definir la restricció "Tot director d'una oficina és treballador de la seva pròpia oficina". De violar-se aquesta condició, ens trobem davant d'un estat inconsistent de les dades.

Evidentment, el llenguatge natural és ambigu, pel que necessitem escriure les restriccions amb un llenguatge formal. Algunes possibilitats són: OCL, SQL Assertions, o fins i tot, lògica de primer ordre. En aquest article, ens decantarem per aquesta última opció. Així per exemple, podríem escriure l'anterior restricció com: 

“Per tot x, y. Dirigeix(x, y) ^  ¬TreballaA(x, y) -> violació”

És a dir “Si una persona X dirigeix una oficina Y, però X no treballa a Y, llavors, es produeix una violació de la restricció”.

Comprovant les restriccions

Una estratègia senzilla per comprovar les restriccions és fent ús de consultes SQL. En concret, podríem fer una consulta que ens retorni tots aquells directors que no són treballadors de la mateixa oficina, és a dir, una consulta que ens retorni els directors que violen la condició. Per exemple:

SELECT *
FROM Dirigeix AS D
LEFT JOIN Treballa AS T A ON (D.director = T.treballador and D.oficina = T.oficina)
WHERE T.treballador IS NULL

El problema d'aquesta solució és que no és incremental. Per fer-nos-en una idea: imaginem-nos un banc amb 3200 oficines, on totes elles satisfan la condició que el seu director treballa a la mateixa oficina. De cop, afegim en el sistema que l'Isidre és el nou director de l'oficina del Carrer Aribau. Clarament, el resultat d'aquesta modificació de les dades pot ser inconsistent si l'Isidre no treballa a l'oficina del Carrar Aribau. És ben cert que podríem detectar aquesta possible inconsistència mitjançant la consulta anterior, però hi ha un problema: la consulta anterior comprova si l'Isidre treballa al Carrer Aribau (fins aquí bé), però també comprova que els altres 3199 directors de banc enregistrats a la taula "Dirigeix" que sabem que fins ara dirigien les seves respectives oficines i pels que no hem aplicat cap modificació en absolut, segueixin satisfent la restricció. Si en lloc de parlar de milers de tuples, parléssim de milions de tuples, el problema d'eficiència seria evident per si mateix.

Una solució incremental consisteix en, assumint que fins ara les dades són consistents, comprovar únicament si les dades afectades per la modificació violen o no les restriccions d’integritat. En el nostre cas, només volem comprovar si l’Isidre treballa a l’oficina del Carrer Aribau, i prou. És a dir, volem comprovar una tupla (no milers, ni tampoc milions).

Comprovant les restriccions incrementalment

El mètode que aquí proposem es basa en l’anomenat mètode dels esdeveniments [1, 2]. El mètode dels esdeveniments consisteix a materialitzar en taules SQL les noves tuples que es volen inserir/esborrar a la base de dades. Per exemple, podríem tenir un parell de taules SQL “ins_Dirigeix”, i “ins_Treballa” on podríem apuntar quines noves tuples volem afegir a les taules “Dirigeix” i “Treballa”. Aquestes taules es poden emplenar fàcilment mitjançant triggers que capturin les insercions/esborrats de dades que un usuari vol aplicar.

A partir d’aquí, podríem definir una consulta com:

SELECT *
FROM ins_Dirigeix AS D
LEFT JOIN Treballa AS T A ON (D.director = T.treballador and D.oficina = T.oficina)
LEFT JOIN ins_Treballa AS ins_T A ON (D.director = ins_T.treballador and D.oficina = ins_T.oficina)
WHERE T.treballador IS NULL

És a dir, una consulta que retorni quins són els nous directors de banc que estem afegint tals que no treballen a la seva oficina i pels que tampoc inserim que hi entrin a treballar.

Aquesta consulta detecta una possible manera de violar aquesta restricció a través de modificar les dades, però sens dubte hi ha altres maneres de violar la mateixa restricció. Per exemple, també podem violar la mateixa restricció si esborrem que un director d’una oficina deixa de treballar en la seva oficina (sense esborrar-lo com a director).

I aquí bé la gran pregunta: com es pot generar una consulta SQL per cada manera diferent que existeix de violar una restricció, i garantint que no ens en deixem cap?

La idea bàsica torna a recaure amb el mètode dels esdeveniments. Una tupla P(x) es troba a la base de dades després d’haver aplicat una modificació si i només si:

  • Hem inserit P(x), o
  • P(x) estava a la base de dades, i no l’hem esborrat.

Similarment, podríem definir que una tupla P(x) no es trobarà a la base de dades si i només si:

  • Hem esborrat P(x), o
  • P(x) no estava a la base de dades, i no l’hem inserit

Seguint aquestes equivalències, podem transformar la nostra restricció lògica inicial en les següents 3 regles:

“Per tot x, y. Ins_Dirigeix(x, y) ^ ¬TreballaA(x, y) ^ ¬ins_TreballaA(x, y) -> violació”
“Per tot x, y. Dirigeix(x, y) ^ ¬ del_Dirigeix(x, y) ^ del_TreballaA(x, y) -> violació”
“Per tot x, y. ins_Dirigeix(x, y) ^ del_TreballaA(x, y) -> violació”

Noteu que la primera regla diu que: “Si inserim que X és el nou director de Y quan X no treballa a Y i no inserim que X treballa a Y, llavors, hi ha una violació”. Si ara escrivim una consulta que retorni aquests directors X i aquestes oficines Y que causen la violació, noteu que estem escrivim exactament la consulta SQL anterior. Les altres dues regles són dues altres maneres d’arribar a violar la mateixa restricció a base d’“esborrar que un director deixa de treballar a la seva oficina”, o inserir que “una persona deixa de treballar a la seva oficina al mateix temps amb què el nomenen director”.

Aquest mètode és complet, és a dir, genera totes les regles que permeten detectar totes les possibles formes de violar una mateixa restricció. Traduint aquestes regles a consultes SQL, obtenim el conjunt de consultes que comproven incrementalment les restriccions. Arribats aquí, podríem guardar-nos aquestes consultes com a vistes SQL, i a cada transacció, comprovar que aquestes vistes SQL es mantenen buides.

Una pregunta d’estiu

Arribats aquí però, hom es podria adonar que hem fet una mica de trampes en l’anterior apartat. Efectivament, d’acord amb les equivalències abans citades, hem passat per alt la següent regla:

“Per tot x, y. Dirigeix(x, y) ^ ¬del_Dirigeix(x, y) ^ ¬TreballaA(x, y) ^ ¬ins_TreballaA(x, y) -> violació”

El cas és que aquesta regla no ens cal mai comprovar-la (és a dir, no ens cal traduir-la com a consulta SQL), i és clau no comprovar-la per mantenir l'eficiència del control incremental de les restriccions. Veieu el perquè? Si no ho veieu, no patiu, teniu tot l'estiu per anar-hi pensant...


Referències

  1. A. Olivé “Integrity Constraints Checking In Deductive Databases.” VLDB 1991
  2. A. Urpí, A. Olivé “A method for change computation in deductive databases” VLDB 1992

Segueix-nos a

Els nostres articles del bloc d'inLab FIB

         
         

inLab FIB incorpora esCert

Icona ESCERT

inLab és membre de