A busca de dependencias funcionais nos datos úsase en varias áreas da análise de datos: xestión de bases de datos, limpeza de datos, enxeñaría inversa de bases de datos e exploración de datos. Xa publicamos sobre as propias dependencias Anastasia Birillo e Nikita Bobrov. Desta volta, Anastasia, graduada no Centro de Informática deste ano, comparte o desenvolvemento deste traballo dentro do traballo de investigación que defendeu no centro.
Selección de tarefas
Mentres estudaba no centro de CS, comecei a estudar en profundidade as bases de datos, é dicir, a busca de dependencias funcionais e diferenciais. Este tema estaba relacionado co tema dos meus traballos na universidade, polo que mentres traballaba no curso, comecei a ler artigos sobre varias dependencias nas bases de datos. Escribín unha crítica desta área, unha das miñas primeiras en inglés e presentouno ao congreso SEIM-2017. Estaba moi feliz cando descubrín que era aceptada despois de todo e decidín afondar no tema. O concepto en si non é novo: comezou a usarse nos anos 90, pero aínda agora úsase en moitas áreas.
Durante o meu segundo semestre no centro, comecei un proxecto de investigación para mellorar os algoritmos para atopar dependencias funcionais. Traballou niso xunto coa estudante de posgrao da Universidade Estatal de San Petersburgo Nikita Bobrov en JetBrains Research.
Complexidade computacional da busca de dependencias funcionais
O principal problema é a complexidade computacional. O número de posibles dependencias mínimas e non triviais está limitado anteriormente polo valor onde - Número de atributos da táboa. O tempo de funcionamento dos algoritmos depende non só do número de atributos, senón tamén do número de filas. Na década dos 90, os algoritmos de busca da lei federal nun ordenador de escritorio normal podían procesar conxuntos de datos que conteñan ata 20 atributos e decenas de miles de filas en ata varias horas. Os algoritmos modernos que se executan en procesadores multinúcleo detectan dependencias para conxuntos de datos formados por centos de atributos (ata 200) e centos de miles de filas aproximadamente ao mesmo tempo. Non obstante, isto non é suficiente: tal momento é inaceptable para a maioría das aplicacións do mundo real. Polo tanto, desenvolvemos enfoques para acelerar os algoritmos existentes.
Esquemas de caché para interseccións de particións
Na primeira parte do traballo, desenvolvemos esquemas de caché para unha clase de algoritmos que usan o método de intersección de particións. Unha partición para un atributo é un conxunto de listas, onde cada lista contén números de liña cos mesmos valores para un determinado atributo. Cada unha destas listas chámase cluster. Moitos algoritmos modernos usan particións para determinar se se mantén ou non unha dependencia, é dicir, adhírense ao lema: Dependencia celebrado se . Aquí desígnase unha partición e úsase o concepto de tamaño da partición: o número de clústeres nela. Os algoritmos que usan particións, cando se viola a dependencia, engaden atributos adicionais ao lado esquerdo da dependencia e, a continuación, recalcúlao, realizando a operación de intersección de particións. Esta operación chámase especialización nos artigos. Pero observamos que as particións para dependencias que só se conservarían despois dunhas cantas roldas de especialización poden reutilizarse activamente, o que pode reducir significativamente o tempo de execución dos algoritmos, xa que a operación de intersección é cara.
Polo tanto, propuxemos unha heurística baseada na entropía de Shannon e na incerteza de Ginny, así como na nosa métrica, que chamamos Entropía inversa. É unha lixeira modificación de Shannon Entropy e aumenta a medida que aumenta a singularidade do conxunto de datos. A heurística proposta é a seguinte:
Aquí — grao de unicidade da partición calculada recentemente E é a mediana dos graos de unicidade dos atributos individuais. As tres métricas descritas anteriormente foron probadas como unha métrica de unicidade. Tamén podes notar que hai dous modificadores na heurística. O primeiro indica o preto que está a partición actual da chave primaria e permítelle almacenar na caché en maior medida aquelas particións que están lonxe da clave potencial. O segundo modificador permítelle supervisar a ocupación da caché e, polo tanto, anima a engadir máis particións á caché se hai espazo libre dispoñible. A solución exitosa deste problema permitiunos acelerar o algoritmo PYRO nun 10-40%, dependendo do conxunto de datos. Cabe destacar que o algoritmo PYRO é o máis exitoso nesta área.
Na seguinte figura podes ver os resultados da aplicación da heurística proposta en comparación cun enfoque básico de almacenamento en caché de moedas. O eixe X é logarítmico.
Unha forma alternativa de almacenar particións
Despois propuxemos unha forma alternativa de almacenar particións. As particións son un conxunto de clusters, cada un dos cales almacena números de tuplas con valores idénticos para determinados atributos. Estes clústeres poden conter longas secuencias de números de tuplas, por exemplo se os datos dunha táboa están ordenados. Polo tanto, propuxemos un esquema de compresión para almacenar particións, é dicir, o almacenamento por intervalos de valores en grupos de particións:
$$display$$pi(X) = {{subtítulo{1, 2, 3, 4, 5}_{Primeiro intervalo}, baixo{7, 8}_{Segundo intervalo}, 10}}\ downarrow{ Compresión} \ pi(X) = {{subtítulo{$, 1, 5}_{Primeiro~intervalo}, baixo{7, 8}_{Segundo~intervalo}, 10}}$$mostrar$$
Este método foi capaz de reducir o consumo de memoria durante o funcionamento do algoritmo TANE do 1 ao 25%. O algoritmo TANE é un algoritmo clásico para buscar leis federais; utiliza particións durante o seu traballo. Como parte da práctica, escolleuse o algoritmo TANE, xa que era moito máis doado implementar nel almacenamento de intervalos que, por exemplo, en PYRO para avaliar se o enfoque proposto funciona. Os resultados obtidos preséntanse na seguinte figura. O eixe X é logarítmico.
Conferencia ADBIS-2019
A partir dos resultados da investigación, en setembro de 2019 publiquei un artigo na 23a Conferencia Europea sobre Avances en Bases de Datos e Sistemas de Información (ADBIS-2019). Durante a presentación, o traballo foi sinalado por Bernhard Thalheim, persoa significativa no ámbito das bases de datos. Os resultados da investigación constituíron a base da miña tese no máster en matemáticas e mecánica da Universidade Estatal de San Petersburgo, durante o cal se implementaron os dous enfoques propostos (caching e compresión) en ambos os algoritmos: TANE e PYRO. Ademais, os resultados mostraron que os enfoques propostos son universais, xa que en ambos algoritmos, con ambos enfoques, observouse unha redución significativa no consumo de memoria, así como unha redución significativa no tempo de funcionamento dos algoritmos.
Fonte: www.habr.com