La cerca de dependències funcionals a les dades s'utilitza en diverses àrees de l'anàlisi de dades: gestió de bases de dades, neteja de dades, enginyeria inversa de bases de dades i exploració de dades. Ja hem publicat sobre les pròpies dependències Anastasia Birillo i Nikita Bobrov. En aquesta ocasió, Anastasia, graduada del Centre d'Informàtica d'enguany, comparteix el desenvolupament d'aquest treball dins del treball de recerca que va defensar al centre.
Selecció de tasques
Mentre estudiava al centre de CS, vaig començar a estudiar en profunditat les bases de dades, és a dir, la recerca de dependències funcionals i diferencials. Aquest tema estava relacionat amb el tema del meu treball del curs a la universitat, així que mentre treballava en el treball del curs, vaig començar a llegir articles sobre diverses dependències a les bases de dades. Vaig escriure una ressenya sobre aquesta àrea, una de les meves primeres en anglès i el va presentar a la conferència SEIM-2017. Em vaig alegrar molt quan vaig saber que era acceptada després de tot i vaig decidir aprofundir en el tema. El concepte en si no és nou: es va començar a utilitzar als anys 90, però fins i tot ara s'utilitza en moltes àrees.
Durant el meu segon semestre al centre, vaig iniciar un projecte de recerca per millorar els algorismes per trobar dependències funcionals. Va treballar-hi juntament amb l'estudiant de postgrau de la Universitat Estatal de Sant Petersburg Nikita Bobrov a JetBrains Research.
Complexitat computacional de la recerca de dependències funcionals
El principal problema és la complexitat computacional. El nombre de dependències mínimes i no trivials possibles està limitat a dalt pel valor 
On 
- nombre d'atributs de la taula. El temps de funcionament dels algorismes depèn no només del nombre d'atributs, sinó també del nombre de files. A la dècada dels 90, els algorismes de cerca de lleis federals en un ordinador d'escriptori normal podien processar conjunts de dades que contenien fins a 20 atributs i desenes de milers de files en fins a diverses hores. Els algorismes moderns que s'executen en processadors multinucli detecten dependències per a conjunts de dades que consisteixen en centenars d'atributs (fins a 200) i centenars de milers de files aproximadament al mateix temps. Tanmateix, això no és suficient: aquest moment és inacceptable per a la majoria de les aplicacions del món real. Per tant, hem desenvolupat enfocaments per accelerar els algorismes existents.
Esquemes de memòria cau per a interseccions de particions
A la primera part del treball, vam desenvolupar esquemes de memòria cau per a una classe d'algorismes que utilitzen el mètode d'intersecció de particions. Una partició per a un atribut és un conjunt de llistes, on cada llista conté números de línia amb els mateixos valors per a un atribut determinat. Cada llista d'aquestes s'anomena clúster. Molts algorismes moderns utilitzen particions per determinar si es manté una dependència o no, és a dir, s'adhereixen al lema: Dependència 
celebrat si 
. Aquí 
es designa una partició i s'utilitza el concepte de mida de la partició: el nombre de clústers que hi ha. Els algorismes que utilitzen particions, quan es viola la dependència, afegeixen atributs addicionals al costat esquerre de la dependència i, a continuació, el tornen a calcular, realitzant l'operació d'intersecció de particions. Aquesta operació s'anomena especialització en els articles. Però ens vam adonar que les particions per a dependències que només es conservarien després d'unes quantes rondes d'especialització es poden reutilitzar activament, cosa que pot reduir significativament el temps d'execució dels algorismes, ja que l'operació d'intersecció és cara.
Per tant, vam proposar una heurística basada en l'entropia de Shannon i la incertesa de Ginny, així com la nostra mètrica, que vam anomenar Entropia inversa. És una lleugera modificació de Shannon Entropy i augmenta a mesura que augmenta la singularitat del conjunt de dades. L'heurística proposada és la següent:
Aquí 
— grau d'unicitat de la partició calculada recentment 
I 
és la mediana dels graus d'unicitat dels atributs individuals. Les tres mètriques descrites anteriorment es van provar com a mètrica d'unicitat. També podeu notar que hi ha dos modificadors a l'heurística. El primer indica fins a quin punt està la partició actual de la clau primària i us permet emmagatzemar a la memòria cau en major mesura aquelles particions que estan lluny de la clau potencial. El segon modificador us permet controlar l'ocupació de la memòria cau i, per tant, anima a afegir més particions a la memòria cau si hi ha espai lliure disponible. La solució exitosa d'aquest problema ens va permetre accelerar l'algorisme PYRO en un 10-40%, depenent del conjunt de dades. Val la pena assenyalar que l'algoritme PYRO és el de més èxit en aquesta àrea.
A la figura següent podeu veure els resultats de l'aplicació de l'heurística proposada en comparació amb un enfocament bàsic d'emmagatzematge a la memòria cau de monedes. L'eix X és logarítmic.
Una forma alternativa d'emmagatzemar particions
Aleshores vam proposar una forma alternativa d'emmagatzemar particions. Les particions són un conjunt de clústers, cadascun dels quals emmagatzema nombres de tuples amb valors idèntics per a determinats atributs. Aquests clústers poden contenir seqüències llargues de nombres tuples, per exemple, si les dades d'una taula estan ordenades. Per tant, vam proposar un esquema de compressió per emmagatzemar particions, és a dir, l'emmagatzematge d'intervals de valors en grups de particions:
$$display$$pi(X) = {{relaç inferior{1, 2, 3, 4, 5}_{Primer interval}, clau inferior{7, 8}_{Segon interval}, 10}}\ fletxa avall{ Compressió} \ pi(X) = {{Cerca inferior{$, 1, 5}_{Primer~interval}, clau inferior{7, 8}_{Segon~interval}, 10}}$$display$$
Aquest mètode va ser capaç de reduir el consum de memòria durant el funcionament de l'algorisme TANE de l'1 al 25%. L'algoritme TANE és un algorisme clàssic per a la recerca de lleis federals que utilitza particions durant el seu treball. Com a part de la pràctica, es va escollir l'algorisme TANE, ja que era molt més fàcil implementar-hi l'emmagatzematge d'intervals que, per exemple, a PYRO per avaluar si funciona l'enfocament proposat. Els resultats obtinguts es presenten a la figura següent. L'eix X és logarítmic.
Jornada ADBIS-2019
A partir dels resultats de la investigació, el setembre de 2019 vaig publicar un article a la 23a Conferència Europea sobre Avenços en Bases de Dades i Sistemes d'Informació (ADBIS-2019). Durant la presentació, el treball va ser destacat per Bernhard Thalheim, una persona rellevant en el camp de les bases de dades. Els resultats de la investigació van ser la base de la meva tesi al màster en matemàtiques i mecànica de la Universitat Estatal de Sant Petersburg, durant la qual es van implementar els dos enfocaments proposats (caching i compressió) en ambdós algorismes: TANE i PYRO. A més, els resultats van mostrar que els enfocaments proposats són universals, ja que en ambdós algorismes, amb ambdós enfocaments, es va observar una reducció significativa del consum de memòria, així com una reducció important del temps de funcionament dels algorismes.
Font: www.habr.com
