Introdução às Dependências Funcionais

Neste artigo falaremos sobre dependências funcionais em bancos de dados – o que são, onde são usadas e quais algoritmos existem para encontrá-las.

Consideraremos dependências funcionais no contexto de bancos de dados relacionais. Resumindo, nesses bancos de dados as informações são armazenadas na forma de tabelas. A seguir, usaremos conceitos aproximados que não são intercambiáveis ​​​​na teoria relacional estrita: chamaremos a própria tabela de relação, as colunas - atributos (seu conjunto - um esquema de relação) e o conjunto de valores de linha em um subconjunto de atributos - uma tupla.

Por exemplo, na tabela acima, (Benson, M, M órgão) é uma tupla de atributos (Paciente, Paulo, Médico).
Mais formalmente, isso é escrito da seguinte forma: [Paciente, Gênero, Médico] = (Benson, órgão M, M).
Agora podemos introduzir o conceito de dependência funcional (FD):

Definição 1. A relação R satisfaz a lei federal X → Y (onde X, Y ⊆ R) se e somente se para quaisquer tuplas , ∈ R é válido: se [X] = [X], então [S] = [S]. Neste caso, dizemos que X (o determinante, ou conjunto definidor de atributos) determina funcionalmente Y (o conjunto dependente).

Em outras palavras, a presença de uma lei federal X → Y significa que se tivermos duas tuplas em R e eles correspondem em atributos X, então eles coincidirão em atributos Y.
E agora, em ordem. Vejamos os atributos Paciente и Género para o qual queremos descobrir se existem dependências entre eles ou não. Para tal conjunto de atributos, podem existir as seguintes dependências:

1. Paciente → Gênero
2. Gênero → Paciente

Conforme definido acima, para que a primeira dependência seja mantida, cada valor de coluna exclusivo Paciente apenas um valor de coluna deve corresponder Género. E para a tabela de exemplo este é realmente o caso. Porém, isso não funciona na direção oposta, ou seja, a segunda dependência não é satisfeita e o atributo Género não é um determinante para Paciente. Da mesma forma, se tomarmos a dependência Médico → Paciente, você pode ver que ele foi violado, pois o valor Robin este atributo tem vários significados diferentes - Ellis e Graham.

Assim, as dependências funcionais permitem determinar as relações existentes entre conjuntos de atributos de tabelas. A partir daqui consideraremos as conexões mais interessantes, ou melhor, tais X → Yo que eles são:

• não trivial, isto é, o lado direito da dependência não é um subconjunto do lado esquerdo (Y̸⊆X);
• mínimo, ou seja, não existe tal dependência Z → YQue Z ⊂ X.

As dependências consideradas até aqui eram estritas, ou seja, não previam nenhuma violação na tabela, mas além delas, existem também aquelas que permitem alguma inconsistência entre os valores das tuplas. Tais dependências são colocadas em uma classe separada, chamada aproximada, e podem ser violadas para um certo número de tuplas. Este valor é regulado pelo indicador de erro máximo emax. Por exemplo, a taxa de erro = 0.01 pode significar que a dependência pode ser violada por 1% das tuplas disponíveis no conjunto de atributos considerado. Ou seja, para 1000 registros, no máximo 10 tuplas podem violar a Lei Federal. Consideraremos uma métrica ligeiramente diferente, com base em valores diferentes aos pares das tuplas que estão sendo comparadas. Para vício X → Y na atitude r é considerado assim:

Vamos calcular o erro para Médico → Paciente do exemplo acima. Temos duas tuplas cujos valores diferem no atributo Paciente, mas coincidem Doutor: [Médico, Paciente] = (Robin, Ellis) E [Médico, Paciente] = (Robin, Graham). Seguindo a definição de erro, devemos levar em consideração todos os pares conflitantes, o que significa que haverá dois deles: (, ) e seu inverso (, ). Vamos substituí-lo na fórmula e obter:

Agora vamos tentar responder à pergunta: “Para que serve tudo isso?” Na verdade, as leis federais são diferentes. O primeiro tipo são aquelas dependências determinadas pelo administrador na fase de design do banco de dados. Eles geralmente são poucos, rígidos e a principal aplicação é a normalização de dados e o design de esquemas relacionais.

O segundo tipo são as dependências, que representam dados “ocultos” e relacionamentos anteriormente desconhecidos entre atributos. Ou seja, tais dependências não foram pensadas no momento do design e são encontradas para o conjunto de dados existente, para que posteriormente, com base nas diversas leis federais identificadas, possam ser tiradas quaisquer conclusões sobre as informações armazenadas. São justamente com essas dependências que trabalhamos. Eles são tratados por todo um campo de mineração de dados com diversas técnicas de pesquisa e algoritmos construídos com base neles. Vamos descobrir como as dependências funcionais encontradas (exatas ou aproximadas) em quaisquer dados podem ser úteis.

Hoje, uma das principais aplicações das dependências é a limpeza de dados. Envolve o desenvolvimento de processos para identificar “dados sujos” e depois corrigi-los. Exemplos proeminentes de “dados sujos” são duplicatas, erros de digitação ou erros de digitação, valores ausentes, dados desatualizados, espaços extras e assim por diante.

Exemplo de erro de dados:

Exemplo de duplicatas em dados:

Por exemplo, temos uma tabela e um conjunto de leis federais que devem ser executadas. A limpeza de dados, neste caso, envolve a alteração dos dados para que as Leis Federais fiquem corretas. Neste caso, o número de modificações deve ser mínimo (este procedimento possui algoritmos próprios, nos quais não focaremos neste artigo). Abaixo está um exemplo de tal transformação de dados. À esquerda está o relacionamento original, no qual, obviamente, os FLs necessários não são atendidos (um exemplo de violação de um dos FLs está destacado em vermelho). À direita está o relacionamento atualizado, com as células verdes mostrando os valores alterados. Após esse procedimento, as dependências necessárias passaram a ser mantidas.

Outra aplicação popular é o design de banco de dados. Aqui vale a pena relembrar as formas normais e a normalização. A normalização é o processo de colocar uma relação em conformidade com um determinado conjunto de requisitos, cada um dos quais é definido pela forma normal à sua maneira. Não descreveremos os requisitos de vários formulários normais (isso é feito em qualquer livro do curso de banco de dados para iniciantes), mas apenas observaremos que cada um deles usa o conceito de dependências funcionais à sua maneira. Afinal, os FLs são inerentemente restrições de integridade que são levadas em consideração ao projetar um banco de dados (no contexto desta tarefa, os FLs são às vezes chamados de superchaves).

Vamos considerar sua aplicação para as quatro formas normais da imagem abaixo. Lembre-se de que a forma normal de Boyce-Codd é mais estrita que a terceira forma, mas menos estrita que a quarta. Não estamos considerando este último por enquanto, pois sua formulação requer uma compreensão de dependências multivaloradas, que não nos interessam neste artigo.

Outra área em que as dependências encontraram sua aplicação é a redução da dimensionalidade do espaço de recursos em tarefas como a construção de um classificador Bayes ingênuo, a identificação de recursos significativos e a reparametrização de um modelo de regressão. Nos artigos originais, esta tarefa é chamada de determinação de redundância e relevância de recursos [5, 6], e é resolvida com o uso ativo de conceitos de banco de dados. Com o advento de tais trabalhos, podemos dizer que hoje existe uma demanda por soluções que nos permitam combinar banco de dados, análise e implementação dos problemas de otimização acima em uma única ferramenta [7, 8, 9].

Existem muitos algoritmos (modernos e não tão modernos) para pesquisar leis federais em um conjunto de dados.Esses algoritmos podem ser divididos em três grupos:

• Algoritmos usando travessia de redes algébricas (algoritmos de travessia de rede)
• Algoritmos baseados na busca por valores acordados (algoritmos de conjunto de diferenças e acordos)
• Algoritmos baseados em comparações pareadas (algoritmos de indução de dependência)

Uma breve descrição de cada tipo de algoritmo é apresentada na tabela abaixo:


Você pode ler mais sobre esta classificação [4]. Abaixo estão exemplos de algoritmos para cada tipo:

Atualmente, estão surgindo novos algoritmos que combinam diversas abordagens para encontrar dependências funcionais. Exemplos de tais algoritmos são Pyro [2] e HyFD [3]. Uma análise de seu trabalho é esperada nos próximos artigos desta série. Neste artigo examinaremos apenas os conceitos básicos e o lema necessários para compreender as técnicas de detecção de dependência.

Vamos começar com um simples - conjunto de diferenças e concordâncias, usado no segundo tipo de algoritmo. Conjunto de diferenças é um conjunto de tuplas que não possuem os mesmos valores, enquanto conjunto de acordo, ao contrário, são tuplas que possuem os mesmos valores. Vale ressaltar que neste caso estamos considerando apenas o lado esquerdo da dependência.

Outro conceito importante encontrado acima é a rede algébrica. Como muitos algoritmos modernos operam com base nesse conceito, precisamos ter uma ideia do que seja.

Para introduzir o conceito de rede, é necessário definir um conjunto parcialmente ordenado (ou conjunto parcialmente ordenado, abreviado como poset).

Definição 2. Diz-se que um conjunto S está parcialmente ordenado pela relação binária ⩽ se para todo a, b, c ∈ S as seguintes propriedades são satisfeitas:

1. Reflexividade, isto é, a ⩽ a
2. Antisimetria, isto é, se a ⩽ b e b ⩽ a, então a = b
3. Transitividade, isto é, para a ⩽ b e b ⩽ c segue que a ⩽ c

Tal relação é chamada de relação de ordem parcial (frouxa), e o próprio conjunto é chamado de conjunto parcialmente ordenado. Notação formal: ⟨S, ⩽⟩.

Como exemplo mais simples de conjunto parcialmente ordenado, podemos tomar o conjunto de todos os números naturais N com a relação de ordem usual ⩽. É fácil verificar se todos os axiomas necessários foram satisfeitos.

Um exemplo mais significativo. Considere o conjunto de todos os subconjuntos {1, 2, 3}, ordenados pela relação de inclusão ⊆. Na verdade, esta relação satisfaz todas as condições de ordem parcial, então ⟨P ({1, 2, 3}), ⊆⟩ é um conjunto parcialmente ordenado. A figura abaixo mostra a estrutura deste conjunto: se um elemento pode ser alcançado por setas para outro elemento, então eles estão em uma relação de ordem.

Precisaremos de mais duas definições simples do campo da matemática - supremo e ínfimo.

Definição 3. Seja ⟨S, ⩽⟩ um conjunto parcialmente ordenado, A ⊆ S. O limite superior de A é um elemento u ∈ S tal que ∀x ∈ S: x ⩽ u. Seja U o conjunto de todos os limites superiores de S. Se houver um menor elemento em U, então ele é chamado de supremo e é denotado sup A.

O conceito de limite inferior exato é introduzido de forma semelhante.

Definição 4. Seja ⟨S, ⩽⟩ um conjunto parcialmente ordenado, A ⊆ S. O ínfimo de A é um elemento l ∈ S tal que ∀x ∈ S: l ⩽ x. Seja L o conjunto de todos os limites inferiores de S. Se houver um elemento maior em L, então ele é chamado de ínfimo e é denotado como inf A.

Considere como exemplo o conjunto parcialmente ordenado acima ⟨P ({1, 2, 3}), ⊆⟩ e encontre o supremo e o ínfimo nele:

Agora podemos formular a definição de uma rede algébrica.

Definição 5. Seja ⟨P,⩽⟩ um conjunto parcialmente ordenado tal que cada subconjunto de dois elementos tenha um limite superior e inferior. Então P é chamado de rede algébrica. Neste caso, sup{x, y} é escrito como x ∨ y, e inf {x, y} como x ∧ y.

Vamos verificar se nosso exemplo de trabalho ⟨P ({1, 2, 3}), ⊆⟩ é uma rede. Na verdade, para qualquer a, b ∈ P ({1, 2, 3}), a∨b = a∪b, e a∧b = a∩b. Por exemplo, considere os conjuntos {1, 2} e {1, 3} e encontre seu ínfimo e supremo. Se os cruzarmos, obteremos o conjunto {1}, que será o ínfimo. Obtemos o supremo combinando-os - {1, 2, 3}.

Em algoritmos para identificação de problemas físicos, o espaço de busca é frequentemente representado na forma de uma rede, onde conjuntos de um elemento (leia o primeiro nível da rede de busca, onde o lado esquerdo das dependências consiste em um atributo) representam cada atributo da relação original.
Primeiro, consideramos dependências da forma ∅ → Atributo único. Esta etapa permite determinar quais atributos são chaves primárias (para tais atributos não há determinantes e, portanto, o lado esquerdo está vazio). Além disso, esses algoritmos se movem para cima ao longo da rede. Vale ressaltar que nem toda a rede pode ser percorrida, ou seja, se o tamanho máximo desejado do lado esquerdo for passado para a entrada, então o algoritmo não irá além de um nível com esse tamanho.

A figura abaixo mostra como uma rede algébrica pode ser usada no problema de encontrar uma FZ. Aqui cada aresta (X,XY) representa uma dependência X → Y. Por exemplo, passamos do primeiro nível e sabemos que o vício se mantém A→B (mostraremos isso como uma conexão verde entre os vértices A и B). Isso significa que ainda mais, quando subimos ao longo da rede, podemos não verificar a dependência A, C → B, porque não será mais mínimo. Da mesma forma, não verificaríamos se a dependência fosse mantida C → B.

Além disso, como regra, todos os algoritmos modernos para busca de leis federais usam uma estrutura de dados como uma partição (na fonte original - partição removida [1]). A definição formal de uma partição é a seguinte:

Definição 6. Seja X ⊆ R um conjunto de atributos para a relação r. Um cluster é um conjunto de índices de tuplas em r que possuem o mesmo valor para X, ou seja, c(t) = {i|ti[X] = t[X]}. Uma partição é um conjunto de clusters, excluindo clusters de comprimento unitário:

Em palavras simples, uma partição para um atributo X é um conjunto de listas, onde cada lista contém números de linha com os mesmos valores para X. Na literatura moderna, a estrutura que representa as partições é chamada de índice de lista de posições (PLI). Clusters de comprimento unitário são excluídos para fins de compactação PLI porque são clusters que contêm apenas um número de registro com um valor exclusivo que sempre será fácil de identificar.

Vejamos um exemplo. Vamos voltar à mesma tabela com os pacientes e construir partições para as colunas Paciente и Género (uma nova coluna apareceu à esquerda, na qual os números das linhas da tabela estão marcados):

Além disso, de acordo com a definição, a partição da coluna Paciente na verdade estará vazio, pois clusters únicos são excluídos da partição.

As partições podem ser obtidas por vários atributos. E há duas maneiras de fazer isso: percorrendo a tabela, construir uma partição usando todos os atributos necessários de uma vez, ou construí-la usando a operação de intersecção de partições usando um subconjunto de atributos. Os algoritmos de busca de leis federais usam a segunda opção.

Em palavras simples, para, por exemplo, obter uma partição por colunas abc, você pode usar partições para AC и B (ou qualquer outro conjunto de subconjuntos disjuntos) e cruzá-los entre si. A operação de intersecção de duas partições seleciona clusters de maior comprimento que são comuns a ambas as partições.

Vejamos um exemplo:

No primeiro caso, recebemos uma partição vazia. Se você olhar atentamente para a tabela, verá que não há valores idênticos para os dois atributos. Se modificarmos um pouco a tabela (caso da direita), já obteremos uma interseção não vazia. Além disso, as linhas 1 e 2 contêm, na verdade, os mesmos valores para os atributos Género и Médico.

A seguir, precisaremos de um conceito como tamanho da partição. Formalmente:

Simplificando, o tamanho da partição é o número de clusters incluídos na partição (lembre-se de que clusters únicos não estão incluídos na partição!):

Agora podemos definir um dos principais lemas, que para determinadas partições nos permite determinar se uma dependência é mantida ou não:

Lema 1. A dependência A, B → C é válida se e somente se

De acordo com o lema, para determinar se uma dependência é válida, quatro passos devem ser executados:

1. Calcule a partição para o lado esquerdo da dependência
2. Calcule a partição para o lado direito da dependência
3. Calcule o produto da primeira e segunda etapa
4. Compare os tamanhos das partições obtidas na primeira e terceira etapas

Abaixo está um exemplo de verificação se a dependência é válida de acordo com este lema:

Neste artigo, examinamos conceitos como dependência funcional, dependência funcional aproximada, onde são utilizados, bem como quais algoritmos existem para busca de funções físicas. Também examinamos detalhadamente os conceitos básicos, mas importantes, que são usados ​​ativamente em algoritmos modernos para busca de leis federais.

Referências:

1. Huhtala Y. et al. TANE: Um algoritmo eficiente para descobrir dependências funcionais e aproximadas //The Computer Journal. – 1999. – T. 42. – Não. 2. – páginas 100-111.
2. Kruse S., Naumann F. Descoberta eficiente de dependências aproximadas // Proceedings of the VLDB Endowment. – 2018. – T. 11. – Não. 7. – pp. 759-772.
3. Papenbrock T., Naumann F. Uma abordagem híbrida para descoberta de dependência funcional //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – pp.
4. Papenbrock T. et al. Descoberta de dependência funcional: Uma avaliação experimental de sete algoritmos //Proceedings of the VLDB Endowment. – 2015. – T. 8. – Não. 10. – páginas 1082-1093.
5. Kumar A. et al. Participar ou não participar?: Pensando duas vezes antes de ingressar antes da seleção de recursos //Proceedings of the 2016 International Conference on Management of Data. – ACM, 2016. – pp.
6. Abo Khamis M. et al. Aprendizagem em banco de dados com tensores esparsos //Anais do 37º Simpósio ACM SIGMOD-SIGACT-SIGAI sobre Princípios de Sistemas de Banco de Dados. – ACM, 2018. – pp.
7. Hellerstein J.M. et al. A biblioteca analítica MADlib: ou habilidades MAD, o SQL //Proceedings do VLDB Endowment. – 2012. – T. 5. – Não. 12. – pp.
8. Qin C., Rusu F. Aproximações especulativas para otimização de descida de gradiente distribuída em terascale //Proceedings of the Fourth Workshop on Data Analytics in the Cloud. – ACM, 2015. – P. 1.
9. Meng X. et al. Mllib: Aprendizado de máquina no Apache Spark //The Journal of Machine Learning Research. – 2016. – T. 17. – Não. 1. – páginas 1235-1241.

Autores do artigo: Anastasia Birillo, pesquisador da Pesquisa JetBrains, Aluno do centro de CS и Nikita Bobrov, pesquisador da Pesquisa JetBrains

Fonte: habr.com