A identificação de dependências funcionais em dados é utilizada em diversas áreas da análise de dados: gerenciamento de banco de dados, limpeza de dados, engenharia reversa de banco de dados e exploração de dados. Já publicamos um artigo sobre as próprias dependências. Anastasia Birillo e Nikita Bobrov. Desta vez, Anastasia, graduada este ano pelo Centro de Ciência da Computação, compartilha o desenvolvimento deste projeto de pesquisa, que ela defendeu no centro.
Seleção de tarefas
Durante meus estudos no Centro de Ciência da Computação, comecei a estudar bancos de dados em profundidade, especificamente, a encontrar dependências funcionais e diferenciais. Esse tópico estava relacionado às minhas disciplinas na universidade, então, enquanto trabalhava nelas, comecei a ler artigos sobre várias dependências em bancos de dados. Escrevi uma revisão sobre esse campo — uma das minhas primeiras. Escrevi um artigo em inglês e o submeti à conferência SEIM-2017. Fiquei muito feliz quando foi aceito e decidi aprofundar o tema. O conceito em si não é novo — existe desde a década de 90 — mas ainda encontra aplicação em muitas áreas atualmente.
No meu segundo semestre no centro, iniciei um projeto de pesquisa para aprimorar algoritmos de detecção de dependências funcionais. Trabalhei nele com Nikita Bobrov, um estudante de pós-graduação da Universidade Estadual de São Petersburgo, na JetBrains Research.
Complexidade computacional da busca por dependências funcionais
O principal problema é a complexidade computacional. O número de dependências mínimas e não triviais possíveis é limitado superiormente por 
Onde 
— o número de atributos da tabela. O tempo de execução dos algoritmos depende não apenas do número de atributos, mas também do número de linhas. Na década de 90, algoritmos para detecção de leis federais em um computador desktop típico podiam processar conjuntos de dados contendo até 20 atributos e dezenas de milhares de linhas em até várias horas. Algoritmos modernos executados em processadores multi-core detectam dependências para conjuntos de dados compostos por centenas de atributos (até 200) e centenas de milhares de linhas em aproximadamente o mesmo tempo. No entanto, isso é insuficiente: tal tempo é inaceitável para a maioria das aplicações do mundo real. Portanto, desenvolvemos abordagens para acelerar os algoritmos existentes.
Esquemas de cache para interseção de partições
Na primeira parte deste artigo, desenvolvemos esquemas de cache para uma classe de algoritmos usando o método de interseção de partições. Uma partição para um atributo é um conjunto de listas, onde cada lista contém os números das linhas com os mesmos valores para o atributo em questão. Cada uma dessas listas é chamada de cluster. Muitos algoritmos modernos usam partições para determinar se uma dependência se mantém, ou seja, eles seguem o seguinte lema: Dependência 
é retido se 
. Aqui 
Uma partição é denotada por , e o conceito de tamanho da partição — o número de clusters dentro dela — é utilizado. Algoritmos que usam partições adicionam atributos extras ao lado esquerdo da dependência quando esta é violada, e então recalculam a dependência realizando uma operação de interseção de partições. Essa operação é chamada de especialização em alguns artigos. No entanto, observamos que partições para dependências que serão mantidas somente após várias rodadas de especialização podem ser reutilizadas ativamente, o que pode reduzir significativamente o tempo de execução dos algoritmos, visto que a operação de interseção é custosa.
Portanto, propusemos uma heurística baseada na entropia de Shannon e na incerteza de Gini, bem como em nossa própria métrica, que denominamos Entropia Inversa. Trata-se de uma pequena modificação da entropia de Shannon, que aumenta conforme a singularidade do conjunto de dados aumenta. A heurística proposta é a seguinte:
é 
— o grau de singularidade da partição calculada recentemente 
E 
é a mediana dos graus de unicidade para atributos individuais. Todas as três métricas descritas acima foram testadas como métricas de unicidade. Também é importante notar que a heurística inclui dois modificadores. O primeiro indica a proximidade da partição atual à chave primária e permite um maior armazenamento em cache de partições mais distantes da chave candidata. O segundo modificador monitora a ocupação do cache, incentivando assim a adição de mais partições ao cache quando houver espaço disponível. A solução bem-sucedida desse problema permitiu que o algoritmo PYRO acelerasse em 10 a 40%, dependendo do conjunto de dados. Vale ressaltar que o algoritmo PYRO é o mais eficiente nessa área.
A figura abaixo mostra os resultados da aplicação da heurística proposta em comparação com a abordagem de cache de referência baseada em lançamentos de moeda. O eixo x está em escala logarítmica.
Uma forma alternativa de armazenar partições
Em seguida, propusemos um método alternativo para armazenar partições. Partições são um conjunto de clusters, cada um dos quais armazena números de tuplas com valores idênticos para determinados atributos. Esses clusters podem conter longas sequências de números de tuplas, por exemplo, se os dados em uma tabela estiverem ordenados. Portanto, propusemos um esquema de compressão para armazenar partições, ou seja, o armazenamento intervalar de valores em clusters de partições:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{Compression}\ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
Este método conseguiu reduzir o consumo de memória durante a execução do algoritmo TANE em 1 a 25%. O algoritmo TANE é um algoritmo clássico para busca de zonas lógicas; ele utiliza partições durante sua operação. Para fins práticos, o algoritmo TANE foi escolhido porque a implementação do armazenamento intervalar foi significativamente mais fácil do que, por exemplo, no PYRO, para avaliar a viabilidade da abordagem proposta. Os resultados são apresentados na figura abaixo. O eixo x é logarítmico.
Conferência ADBIS-2019
Com base nos resultados da pesquisa, publiquei um artigo em setembro de 2019. Na 23ª Conferência Europeia sobre Avanços em Bancos de Dados e Sistemas de Informação (ADBIS-2019), o trabalho foi reconhecido por Bernhard Thalheim, figura proeminente na área de bancos de dados. Os resultados da pesquisa serviram de base para minha dissertação de mestrado na Faculdade de Matemática e Mecânica da Universidade Estadual de São Petersburgo, durante a qual ambas as abordagens propostas (cache e compressão) foram implementadas nos algoritmos TANE e PYRO. Os resultados mostraram que as abordagens propostas são universais, visto que ambos os algoritmos demonstraram uma redução significativa no consumo de memória e no tempo de execução.
Fonte: habr.com
