Dependência funcional - Functional dependency

Na teoria do banco de dados relacional , uma dependência funcional é uma restrição entre dois conjuntos de atributos em uma relação de um banco de dados. Em outras palavras, uma dependência funcional é uma restrição entre duas chaves. Dada uma relação R e conjuntos de atributos , diz-se que X determina funcionalmente Y (escrito X → Y ) se e somente se cada valor de X em R está associado precisamente a um valor de Y em R ; R é então dito para satisfazer${\ displaystyle X, Y \ subseteq R}$ a dependência funcional X → Y . De forma equivalente, a projecção é uma função , ou seja, Y é uma função de X . Em palavras simples, se os valores dos atributos X são conhecidos (digamos que são x ), então os valores dos atributos Y correspondentes ax podem ser determinados procurando-os em qualquer tupla de R contendo x . Habitualmente X é chamado o determinante conjunto e Y o dependente conjunto. Um FD dependência funcional: X → Y é chamado trivial se Y é um subconjunto de X . ${\ displaystyle \ Pi _ {X, Y} R}$

Em outras palavras, uma dependência FD: X → Y significa que os valores de Y são determinadas pelos valores de X . Dois tuplos que partilham os mesmos valores de X terá, necessariamente, os mesmos valores de Y .

A determinação de dependências funcionais é uma parte importante do projeto de bancos de dados no modelo relacional e na normalização e desnormalização do banco de dados . Uma aplicação simples de dependências funcionais é o teorema de Heath ; ele diz que uma relação R sobre um conjunto de atributos U e satisfazendo uma dependência funcional X → Y pode ser dividida com segurança em duas relações com a propriedade de decomposição de junção sem perdas , a saber, em que Z = U - XY são os demais atributos. (As uniões de conjuntos de atributos são habitualmente denotadas por meras justaposições na teoria do banco de dados.) Uma noção importante neste contexto é uma chave candidata , definida como um conjunto mínimo de atributos que determinam funcionalmente todos os atributos em uma relação. As dependências funcionais, junto com os domínios de atributo , são selecionadas de modo a gerar restrições que excluam o máximo possível de dados inadequados para o domínio do usuário do sistema. ${\ displaystyle \ Pi _ {XY} (R) \ bowtie \ Pi _ {XZ} (R) = R}$

Uma noção de implicação lógica é definida para dependências funcionais da seguinte maneira: um conjunto de dependências funcionais implica logicamente outro conjunto de dependências , se qualquer relação R satisfazendo todas as dependências de também satisfaz todas as dependências de ; isso geralmente é escrito . A noção de implicação lógica para dependências funcionais admite uma axiomatização sólida e finita completa , conhecida como axiomas de Armstrong . ${\ displaystyle \ Sigma}$${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma}$${\ displaystyle \ Gamma}$${\ displaystyle \ Sigma \ models \ Gamma}$

Exemplos

Carros

Suponha que alguém esteja projetando um sistema para rastrear veículos e a capacidade de seus motores. Cada veículo possui um número de identificação de veículo exclusivo (VIN). Alguém escreveria VIN → EngineCapacity porque seria impróprio para o motor de um veículo ter mais de uma capacidade. (Supondo, neste caso, que os veículos tenham apenas um motor.) Por outro lado, EngineCapacity → VIN está incorreto porque pode haver muitos veículos com a mesma cilindrada.

Essa dependência funcional pode sugerir que o atributo EngineCapacity seja colocado em uma relação com o VIN da chave candidata . No entanto, isso pode nem sempre ser apropriado. Por exemplo, se essa dependência funcional ocorre como resultado das dependências funcionais transitivas VIN → VehicleModel e VehicleModel → EngineCapacity, então isso não resultaria em uma relação normalizada.

Palestras

Este exemplo ilustra o conceito de dependência funcional. A situação modelada é a de estudantes universitários que visitam uma ou mais palestras em cada uma das quais são atribuídos um assistente de ensino (TA). Vamos supor ainda que cada aluno está em algum semestre e é identificado por um ID de número inteiro único.

Notamos que sempre que duas linhas nesta tabela apresentam o mesmo StudentID, elas também têm necessariamente os mesmos valores de Semestre. Este fato básico pode ser expresso por uma dependência funcional:

• ID do aluno → Semestre.

Observe que se uma linha fosse adicionada onde o aluno tivesse um valor de semestre diferente, a dependência funcional FD não existiria mais. Isso significa que o FD está implícito nos dados, pois é possível ter valores que invalidariam o FD.

Outras dependências funcionais não triviais podem ser identificadas, por exemplo:

• {ID do aluno, palestra} → TA
• {ID do aluno, palestra} → {TA, Semestre}

Este último expressa o fato de que o conjunto {StudentID, Lecture} é uma superchave da relação.

Modelo de departamento de funcionário

Um exemplo clássico de dependência funcional é o modelo de departamento de funcionário.

Este caso representa um exemplo em que várias dependências funcionais são incorporadas em uma única representação de dados. Observe que, como um funcionário só pode ser membro de um departamento, o ID exclusivo desse funcionário determina o departamento.

• ID do funcionário → Nome do funcionário
• ID do funcionário → ID do departamento

Além dessa relação, a tabela também possui uma dependência funcional por meio de um atributo não chave

• ID do Departamento → Nome do Departamento

Este exemplo demonstra que embora exista um ID do funcionário FD → ID do departamento - o ID do funcionário não seria uma chave lógica para a determinação do ID do departamento. O processo de normalização dos dados reconheceria todos os FDs e permitiria ao designer construir tabelas e relacionamentos que são mais lógicos com base nos dados.

Propriedades e axiomatização de dependências funcionais

Dado que X , Y e Z são conjuntos de atributos em uma relação R , pode-se derivar várias propriedades de dependências funcionais. Entre os mais importantes estão os seguintes, geralmente chamados de axiomas de Armstrong :

• Reflexividade : Se Y for um subconjunto de X , então X → Y
• Aumento : Se X → Y , então XZ → YZ
• Transitividade : Se X → Y e Y → Z , então X → Z

A "reflexividade" pode ser enfraquecida para justa , ou seja, é um axioma real , onde as outras duas são regras de inferência adequadas , mais precisamente dando origem às seguintes regras de consequência sintática: ${\ displaystyle X \ rightarrow \ varnothing}$

${\ displaystyle \ vdash X \ rightarrow \ varnothing}$
${\ displaystyle X \ rightarrow Y \ vdash XZ \ rightarrow YZ}$
${\ displaystyle X \ rightarrow Y, Y \ rightarrow Z \ vdash X \ rightarrow Z}$.

Essas três regras são uma axiomatização sólida e completa das dependências funcionais. Essa axiomatização às vezes é descrita como finita porque o número de regras de inferência é finito, com a ressalva de que o axioma e as regras de inferência são todos esquemas , o que significa que X , Y e Z variam em todos os termos básicos (conjuntos de atributos).

Ao aplicar aumento e transitividade, pode-se derivar duas regras adicionais:

• Pseudotransitividade : Se X → Y e YW → Z , então XW → Z
• Composição : Se X → Y e Z → W , então XZ → YW

Também se pode derivar as regras de união e decomposição dos axiomas de Armstrong:

X → Y e X → Z se e somente se X → YZ

Encerramento da dependência funcional

O fechamento é essencialmente o conjunto completo de valores que podem ser determinados a partir de um conjunto de valores conhecidos para um determinado relacionamento usando suas dependências funcionais. Um usa os axiomas de Armstrong para fornecer uma prova - isto é, reflexividade, aumento, transitividade.

Dado e um conjunto de FDs que se mantém em : O fechamento de em (denotado ⁺ ) é o conjunto de todos os FDs que são logicamente implícitos por . ${\ displaystyle R}$${\ displaystyle F}$${\ displaystyle R}$${\ displaystyle F}$${\ displaystyle R}$${\ displaystyle F}$${\ displaystyle F}$

Fechamento de um conjunto de atributos

O fechamento de um conjunto de atributos X em relação a é o conjunto X ⁺ de todos os atributos que são funcionalmente determinados por X usando ⁺ . ${\ displaystyle F}$${\ displaystyle F}$

Exemplo

Imagine a seguinte lista de FDs. Vamos calcular um fechamento para A a partir dessa relação.

1. A → B
2. B → C 3. AB → D

O encerramento seria o seguinte:

a) A → A (pela reflexividade de Armstrong)
b) A → AB (por 1. e (a))
c) A → ABD (por (b), 3 e transitividade de Armstrong)
d) A → ABCD (por (c) ), e 2)

O fechamento é, portanto, A → ABCD. Ao calcular o fechamento de A, validamos que A também é uma boa chave candidata, pois seu fechamento é cada valor de dados no relacionamento.

Capas e equivalência

Capas

Definição : abrange se cada FD em puder ser inferido . cobre if ⁺ ⊆ ⁺ Cada conjunto de dependências funcionais tem uma capa canônica . ${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle G}$${\ displaystyle F}$

Equivalência de dois conjuntos de FDs

Dois conjuntos de FDs e sobre o esquema são equivalentes, escritos ≡ , se ⁺ = ⁺ . Se ≡ , então é uma cobertura para e vice-versa. Em outras palavras, conjuntos equivalentes de dependências funcionais são chamados de coberturas uns dos outros. ${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle R}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle G}$

Tampas não redundantes

Um conjunto de FDs não é redundante se não houver um subconjunto adequado de com ≡ . Se tal existir, é redundante. é uma cobertura não redundante para se é uma cobertura para e não é redundante. Uma caracterização alternativa de nonredundancy é que é não redundante se houver nenhum FD X → Y em tal que - { X → Y } X → Y . Chame uma FD X → Y em redundante em se - { X → Y } X → Y . ${\ displaystyle F}$${\ displaystyle F '}$${\ displaystyle F}$${\ displaystyle F '}$${\ displaystyle F}$${\ displaystyle F '}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle F}$
${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle \ models}$ ${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle F}$${\ displaystyle \ models}$

Aplicações para normalização

Teorema de Heath

Uma propriedade importante (produzindo uma aplicação imediata) das dependências funcionais é que se R é uma relação com colunas nomeadas a partir de algum conjunto de atributos U e R satisfaz alguma dependência funcional X → Y então onde Z = U - XY . Intuitivamente, se uma dependência funcional X → Y se mantém em R , então a relação pode ser dividida com segurança em duas relações ao lado da coluna X (que é uma chave para ) garantindo que quando as duas partes são unidas de volta nenhum dado é perdido, ou seja, um a dependência funcional fornece uma maneira simples de construir uma decomposição de junção sem perdas de R em duas relações menores. Esse fato às vezes é chamado de teorema de Heath ; é um dos primeiros resultados da teoria do banco de dados. ${\ displaystyle R = \ Pi _ {XY} (R) \ bowtie \ Pi _ {XZ} (R)}$${\ displaystyle \ Pi _ {XY} (R) \ bowtie \ Pi _ {XZ} (R)}$

O teorema de Heath diz efetivamente que podemos retirar os valores de Y da grande relação R e armazená-los em um, que não tem repetições de valor na linha de X e é efetivamente uma tabela de pesquisa para Y digitada por X e, conseqüentemente, tem apenas um lugar para atualizar o Y correspondente a cada X ao contrário da "grande" relação R onde existem potencialmente muitas cópias de cada X , cada uma com sua cópia de Y que precisa ser mantida sincronizada nas atualizações. (Essa eliminação de redundância é uma vantagem em contextos OLTP , onde muitas mudanças são esperadas, mas não tanto em contextos OLAP , que envolvem principalmente consultas.) A decomposição de Heath deixa apenas X para atuar como uma chave estrangeira no restante da grande tabela . ${\ displaystyle \ Pi _ {XY} (R)}$${\ displaystyle \ Pi _ {XZ} (R)}$

Dependências funcionais, entretanto, não devem ser confundidas com dependências de inclusão , que são o formalismo para chaves estrangeiras; embora sejam usadas para normalização, as dependências funcionais expressam restrições sobre uma relação (esquema), enquanto as dependências de inclusão expressam restrições entre esquemas de relação em um esquema de banco de dados . Além disso, as duas noções nem mesmo se cruzam na classificação de dependências : dependências funcionais são dependências geradoras de igualdade, enquanto as dependências de inclusão são dependências geradoras de tupla . Impor restrições referenciais após a decomposição do esquema de relação (normalização) requer um novo formalismo, isto é, dependências de inclusão. Na decomposição resultante do teorema de Heath, nada impede a inserção de tuplas em ter algum valor de X não encontrado em . ${\ displaystyle \ Pi _ {XZ} (R)}$${\ displaystyle \ Pi _ {XY} (R)}$

Formas normais

Os formulários normais são níveis de normalização do banco de dados que determinam a "qualidade" de uma tabela. Geralmente, a terceira forma normal é considerada um "bom" padrão para um banco de dados relacional.

A normalização visa libertar o banco de dados de anomalias de atualização, inserção e exclusão. Ele também garante que, quando um novo valor é introduzido na relação, ele tem efeito mínimo no banco de dados e, portanto, efeito mínimo nos aplicativos que usam o banco de dados.

Função irredutível dependendo do conjunto

Um conjunto S de dependências funcionais é irredutível se o conjunto tiver as três propriedades a seguir:

1. Cada conjunto certo de uma dependência funcional de S contém apenas um atributo.
2. Cada conjunto esquerdo de uma dependência funcional de S é irredutível. Isso significa que a redução de qualquer atributo do conjunto esquerdo mudará o conteúdo de S (S perderá algumas informações).
3. Reduzir qualquer dependência funcional mudará o conteúdo de S.

Os conjuntos de dependências funcionais com essas propriedades também são chamados de canônicos ou mínimos . Encontrar tal conjunto S de dependências funcionais que é equivalente a algum conjunto de entrada S 'fornecido como entrada é chamado de encontrar uma cobertura mínima de S': este problema pode ser resolvido em tempo polinomial.

Veja também

• Chase (algoritmo)
• Dependência de inclusão
• Dependência de associação
• Dependência multivalorada (MVD)
• Normalização de banco de dados
• Primeira forma normal

Referências

links externos

• Gary Burt (verão de 1999). "Notas de aula do CS 461 (Sistemas de Gerenciamento de Banco de Dados)" . Universidade de Maryland Departamento de Ciência da Computação e Engenharia Elétrica do Condado de Baltimore .
• Jeffrey D. Ullman. "CS345 Lecture Notes" ( PostScript ) . Universidade de Stanford.
• Osmar Zaiane (9 de junho de 1998). "Capítulo 6: Restrições de integridade" . Notas de aula do CMPT 354 (Database Systems I) . Departamento de Ciência da Computação da Simon Fraser University .