Encontre dependências funcionais em bancos de dados com eficiência

Encontrar dependências funcionais em dados é usado em diversas áreas de 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 sobre as próprias dependências статью Anastasia Birillo e Nikita Bobrov. Desta vez, Anastasia, formada este ano pelo Centro de Informática, partilha o desenvolvimento deste trabalho no âmbito do trabalho de investigação que defendeu no centro.

Seleção de tarefas

Enquanto estudava no centro de CS, comecei a estudar a fundo bases de dados, nomeadamente, a procura de dependências funcionais e diferenciais. Esse tópico estava relacionado ao tema do meu curso na universidade, então, enquanto trabalhava no curso, comecei a ler artigos sobre diversas dependências em bancos de dados. Escrevi uma resenha sobre esta área - uma das minhas primeiras artigos em inglês e o submeteu à conferência SEIM-2017. Fiquei muito feliz quando descobri que afinal ela foi aceita e resolvi me aprofundar no assunto. O conceito em si não é novo - começou a ser utilizado na década de 90, mas ainda hoje é utilizado em diversas áreas.

Durante meu segundo semestre no centro, iniciei um projeto de pesquisa para melhorar algoritmos para encontrar dependências funcionais. Ela trabalhou nisso junto com Nikita Bobrov, estudante de graduação da Universidade Estadual de São Petersburgo, na JetBrains Research.

Complexidade computacional de busca de dependências funcionais

O principal problema é a complexidade computacional. O número de possíveis dependências mínimas e não triviais é limitado acima pelo valor Onde — número de atributos da tabela. O tempo de operaçã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 de busca de leis federais em um PC desktop comum 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 de conjuntos de dados que consistem em centenas de atributos (até 200) e centenas de milhares de linhas aproximadamente ao mesmo tempo. No entanto, isto não é suficiente: 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ções de partições

Na primeira parte do trabalho, desenvolvemos esquemas de cache para uma classe de algoritmos que utilizam o método de intersecção de partições. Uma partição para um atributo é um conjunto de listas, onde cada lista contém números de linha com os mesmos valores para um determinado atributo. Cada uma dessas listas é chamada de cluster. Muitos algoritmos modernos usam partições para determinar se uma dependência é mantida ou não, ou seja, eles aderem ao lema: Dependência mantido se . Aqui uma partição é designada e o conceito de tamanho da partição é usado - o número de clusters nela. Algoritmos que utilizam partições, quando a dependência é violada, adicionam atributos adicionais ao lado esquerdo da dependência, e então a recalculam, realizando a operação de interseção de partições. Esta operação é chamada de especialização nos artigos. Mas notamos que partições para dependências que só seriam retidas após algumas rodadas de especialização podem ser reutilizadas ativamente, o que pode reduzir significativamente o tempo de execução dos algoritmos, uma vez que a operação de interseção é cara.

Portanto, propusemos uma heurística baseada na Entropia de Shannon e na Incerteza de Ginny, bem como nossa métrica, que chamamos de Entropia Reversa. É uma ligeira modificação da Entropia de Shannon e aumenta à medida que a singularidade do conjunto de dados aumenta. A heurística proposta é a seguinte:

é — grau de exclusividade da partição recentemente calculada E é a mediana dos graus de exclusividade dos atributos individuais. Todas as três métricas descritas acima foram testadas como uma métrica de exclusividade. Você também pode notar que existem dois modificadores na heurística. O primeiro indica o quão próxima a partição atual está da chave primária e permite armazenar em cache em maior medida as partições que estão longe da chave potencial. O segundo modificador permite monitorar a ocupação do cache e, assim, incentiva a adição de mais partições ao cache se houver espaço livre disponível. A solução bem-sucedida deste problema permitiu acelerar o algoritmo PYRO em 10-40%, dependendo do conjunto de dados. É importante notar que o algoritmo PYRO é o mais bem sucedido nesta área.

Na figura abaixo você pode ver os resultados da aplicação da heurística proposta em comparação com uma abordagem básica de cache de lançamento de moeda. O eixo X é logarítmico.

Uma forma alternativa de armazenar partições

Propusemos então uma forma alternativa de armazenar partições. As 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 compactação para armazenamento de partições, ou seja, armazenamento intervalado de valores em clusters de partições:

$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{Primeiro intervalo}, underbrace{7, 8}_{Segundo intervalo}, 10}}\ downarrow{ Compressão} \ pi(X) = {{underbrace{$, 1, 5}_{Primeiro~intervalo}, underbrace{7, 8}_{Segundo~intervalo}, 10}}$$display$$

Este método foi capaz de reduzir o consumo de memória durante a operação do algoritmo TANE de 1 a 25%. O algoritmo TANE é um algoritmo clássico para busca de leis federais, utiliza partições durante seu trabalho. Como parte da prática, foi escolhido o algoritmo TANE, pois era muito mais fácil implementar nele o armazenamento intervalado do que, por exemplo, no PYRO para avaliar se a abordagem proposta funciona. Os resultados obtidos são apresentados na figura abaixo. O eixo X é logarítmico.

Conferência ADBIS-2019

Com base nos resultados da pesquisa, em setembro de 2019 publiquei um artigo Cache inteligente para descoberta eficiente de dependências funcionais na 23ª Conferência Europeia sobre Avanços em Bases de Dados e Sistemas de Informação (ADBIS-2019). Durante a apresentação, o trabalho foi destacado por Bernhard Thalheim, figura importante na área de bancos de dados. Os resultados da pesquisa formaram a base da minha dissertação de mestrado em matemática e mecânica na Universidade Estadual de São Petersburgo, durante a qual ambas as abordagens propostas (cache e compressão) foram implementadas em ambos os algoritmos: TANE e PYRO. Além disso, os resultados mostraram que as abordagens propostas são universais, pois em ambos os algoritmos, com ambas as abordagens, foi observada uma redução significativa no consumo de memória, bem como uma redução significativa no tempo de operação dos algoritmos.

Fonte: habr.com