Baze de date statistice

Baze de date statistice

O baza de date statistica este o baza de date din care se pot obtine informatii aplicand operatii agregate unor submultimi de elemente continute in ea. Prin formularea unor intrebari, unii utilizatori pot sa obtina informatii la care in mod obisnuit nu au acces. Daca un utilizator nu are acces la campul SALARIU, dar poate face suma salariilor unor submultimi de cel putin m persoane, cu m dat, pentru a afla salariul lui Ionescu el poate calcula suma tuturor salariilor si suma tuturor salariilor fara al lui Ionescu, prin scaderea acestor doua valori rezultand salariul lui Ionescu la care nu avea acces.

Pentru a preveni astfel de situatii, unele sisteme de baze de date tin o evidenta a intrebarilor puse de fiecare utilizator in parte si refuza sa raspunda in anumite conditii:

sunt implicate mai putine inregistrari decat un numar dat m;

sunt implicate mai mult de n-m inregistrari, unde n este numarul total de elemente;

sunt implicate mai mult de p inregistrari comune cu o cerere anterioara; etc.

Fie o baza de date cu n inregistrari ce au valorile v=(v₁,v₂,,v_n) corespunzatoare unui camp care nu este cheie. O cerere liniara este o suma de forma: c₁v₁,c₂v₂,,c_nv_n, unde c_ieste un numar real oarecare pentru orice i. Daca r₁,r₂,,r_q este un numar de q cereri liniare cu r_i=c_i1v_i1++c_inv_in spunem ca baza de date este compromisa daca exista o functie f astfel incat una din valorile v_i se obtine aplicand f valorilor r₁,,r_q – v_i=f(r₁,,r_q).

Daca exista o functie f astfel incat v_i=f(r₁,,r_q), atunci exista o functie liniara g cu aceeasi proprietate, deci exista d₁,,d_q astfel incat d₁r₁+d₂r₂++d_qr_q=v_i.

Daca notam cu M matricea cu q linii si n coloane a coeficientilor cererilor liniare r₁,,r_q si cu d=d₁,d₂,,d_q, rezulta ca baza de date este compromisa daca si numai daca exista un vector d astfel incat dM=(0,,0,1,0,,0). Pentru a nu compromite baza de date, se fac constrangeri de forma:

fiecare linie din M are cel putin m elemente nenule;

oricare doua linii au cel mult k elemente nenule pe coloane comune.

Exemplu: pentru valorile v₁,v₂,v₃,v₄,v₅,v₆,v₇ cu cererile r₁=v₂+v₃+v₄, r₂=v₅+v₆+v₇, r₃=v₁+v₂+v₅, r₄=v₁+v₃+v₆, r₅=v₁+v₄+v₇, baza de date este compromisa deoarece v₁=(r₃+r₄+r₅-r₁-r₂)/3, desi s-ar purea lua m=3 si k=0. Deci, punerea conditiei m=4 sau k=0 poate duce, eventual, la o baza de date care nu este compromisa.

Daca se folosesc cereri liniare in care se folosesc cel putin m valori, doua cereri au in comun cel mult k valori si se cunosc deja p valori, pentru a calcula un nou element necunoscut sunt necesare cel putin (m-p-1)/k+1 cereri.