Aula número 9. Dependências funcionais

1. Restrição de dependência funcional

A restrição de exclusividade imposta pelas declarações de chave primária e candidata de uma relação é um caso especial da restrição associada à noção dependências funcionais.

Para explicar o conceito de dependência funcional, considere o exemplo a seguir.

Vamos receber uma relação contendo dados sobre os resultados de uma determinada sessão. O esquema desse relacionamento fica assim:

Sessão (número do livro de registro, Nome completo, Assunto, Avaliar);

Os atributos "Número do boletim de notas" e "Assunto" formam uma chave primária composta (já que dois atributos são declarados como chave) desta relação. De fato, esses dois atributos podem determinar exclusivamente os valores de todos os outros atributos.

No entanto, além da restrição de exclusividade associada a essa chave, a relação deve necessariamente estar sujeita à condição de que um boletim de notas seja emitido para uma determinada pessoa e, portanto, a esse respeito, as tuplas com o mesmo número de boletim de notas devem conter os mesmos valores dos atributos "Sobrenome", "Nome e nome do meio".

Se tivermos o seguinte fragmento de um determinado banco de dados de alunos de uma instituição educacional após uma determinada sessão, em tuplas com um número de notas de 100, os atributos "Sobrenome", "Nome" e "Patronímico" são os mesmos, e os atributos "Assunto" e "Avaliação" - não coincidem (o que é compreensível, pois estão falando de assuntos e desempenhos diferentes neles). Isso significa que os atributos "Sobrenome", "Nome" e "Patronímico" funcionalmente dependente no atributo "Número do boletim de notas", enquanto os atributos "Assunto" e "Avaliação" são funcionalmente independentes.

Assim, o dependência funcional é uma dependência de valor único tabulada em sistemas de gerenciamento de banco de dados.

Damos agora uma definição rigorosa de dependência funcional.

Definição: sejam X, Y subesquemas do esquema da relação S, definindo sobre o esquema S diagrama de dependência funcional X → Y (leia "seta X Y"). Vamos definir restrições de dependência funcional inv<X → Y> como uma declaração de que, em relação ao esquema S, quaisquer duas tuplas que correspondam na projeção no subesquema X também devem corresponder na projeção ao subesquema Y.

Vamos escrever a mesma definição na forma de fórmula:

Inv<X → Y> r(S) = t₁, T₂ ∈ r(t₁[X] =t₂[X] ⇒ t₁[S]=t₂ [Y]), X, Y ⊆ S;

Curiosamente, essa definição usa o conceito de operação de projeção unária, que encontramos anteriormente. De fato, de que outra forma, se você não usar esta operação, para mostrar a igualdade de duas colunas da tabela de relações, e não linhas, entre si? Portanto, escrevemos em termos desta operação que a coincidência de tuplas na projeção sobre algum atributo ou vários atributos (subesquema X) certamente acarretará a coincidência das mesmas colunas-tuplas no subesquema Y caso Y seja funcionalmente dependente de X.

É interessante notar que no caso de uma dependência funcional de Y em X, também se diz que X define funcionalmente S ou o que S funcionalmente dependente em X. No esquema de dependência funcional X → Y, o subcircuito X é chamado de lado esquerdo e o subcircuito Y é chamado de lado direito.

Na prática de projeto de banco de dados, o esquema de dependência funcional é comumente referido como dependência funcional para abreviar.

Fim da definição.

No caso especial, quando o lado direito da dependência funcional, ou seja, o subesquema Y, corresponde a todo o esquema do relacionamento, a restrição de dependência funcional se torna uma restrição de exclusividade de chave primária ou candidata. Sério:

inv r(S) = ∀ t₁, T₂ ∈ r(t₁[K] =t₂ [K] → t₁(S) =t₂(S)), K ⊆ S;

É só que ao definir uma dependência funcional, ao invés do subesquema X, você precisa pegar a designação da chave K, e ao invés do lado direito da dependência funcional, subesquema Y, pegar todo o esquema de relações S, ou seja, de fato, a restrição à unicidade das chaves de relações é um caso especial de restrição de dependência funcional quando o lado direito é igual a esquemas de dependência funcional em todo o esquema de relacionamento.

Aqui estão alguns exemplos da imagem de dependência funcional:

{Número do livro de contas} → {Sobrenome, Nome, Patronímico};

{número do boletim de notas, assunto} → {nota};

2. Regras de inferência de Armstrong

Se qualquer relação básica satisfaz dependências funcionais definidas por vetores, então com a ajuda de várias regras de inferência especiais é possível obter outras dependências funcionais que esta relação básica certamente irá satisfazer.

Um bom exemplo dessas regras especiais são as regras de inferência de Armstrong.

Mas antes de prosseguirmos com a análise das próprias regras de inferência de Armstrong, vamos introduzir um novo símbolo metalinguístico "├", que se chama símbolo de meta-afirmação de derivabilidade. Este símbolo, ao formular regras, é escrito entre duas expressões sintáticas e indica que a fórmula à sua direita é derivada da fórmula à sua esquerda.

Vamos agora formular as próprias regras de inferência de Armstrong na forma do seguinte teorema.

Teorema. As seguintes regras são válidas, chamadas regras de inferência de Armstrong.

Regra de Inferência 1. ├ X → X;

Regra de Inferência 2. X → Y├ X ∪ Z → Y;

Regra de Inferência 3. X → Y, Y ∪ W → Z ├ X ∪ W → Z;

Aqui X, Y, Z, W são subesquemas arbitrários do esquema da relação S. O símbolo de meta-enunciado de derivabilidade separa listas de premissas e listas de asserções (conclusões).

1. A primeira regra de inferência é chamada de "reflexividade" e diz o seguinte: "a regra é deduzida:" X implica funcionalmente X "". Esta é a mais simples das regras de derivação de Armstrong. Ela é derivada literalmente do nada.

É interessante notar que uma dependência funcional que tem ambas as partes esquerda e direita é chamada reflexivo. De acordo com a regra da reflexividade, a restrição da dependência reflexiva é realizada automaticamente.

2. A segunda regra de inferência é chamada de "reposição" e diz o seguinte: "se X determina funcionalmente Y, então a regra é derivada: "a união dos subcircuitos X e Z implica funcionalmente Y". A regra de conclusão permite expandir o lado esquerdo da restrição de dependência funcional.

3. A terceira regra de inferência é chamada de "pseudotransitividade" e diz o seguinte: "se o subcircuito X implica funcionalmente o subcircuito Y, e a união dos subcircuitos Y e W implica funcionalmente Z, então a regra é derivada: "a união dos subcircuitos X e W determina funcionalmente o subcircuito Z"".

A regra de pseudotransitividade generaliza a regra de transitividade correspondente ao caso especial W: = 0. Vamos dar uma notação formal desta regra:

X→Y, Y→Z ├X→Z.

Deve-se notar que as premissas e conclusões dadas anteriormente foram apresentadas de forma abreviada pelas designações de esquemas de dependência funcional. Na forma estendida, eles correspondem às seguintes restrições de dependência funcional.

Regra de Inferência 1. inv r(S);

Regra de Inferência 2. inv r(S) ⇒ inv r(S);

Regra de Inferência 3. inv r(S) & inv r(S) ⇒ inv r(S);

Desenhar evidência essas regras de inferência.

1. Prova da regra reflexividade segue diretamente da definição da restrição de dependência funcional quando o subesquema X é substituído pelo subcircuito Y.

De fato, tome a restrição de dependência funcional:

inv r(S) e substituir X em vez de Y, obtemos:

inv r(S), e esta é a regra da reflexividade.

A regra da reflexividade está provada.

2. Prova da regra reposição Vamos ilustrar em diagramas de dependência funcional.

O primeiro diagrama é o diagrama do pacote:

premissa: X → Y

Segundo diagrama:

conclusão: X ∪ Z → Y

Sejam as tuplas iguais em X ∪ Z. Então elas são iguais em X. De acordo com a premissa, elas serão iguais em Y também.

A regra de reabastecimento é comprovada.

3. Prova da regra pseudotransitividade também vamos ilustrar em diagramas, que neste caso em particular serão três.

O primeiro diagrama é a primeira premissa:

premissa 1: X → Y

premissa 2: Y ∪ W → Z

E, finalmente, o terceiro diagrama é o diagrama de conclusão:

conclusão: X ∪ W → Z

Sejam as tuplas iguais em X ∪ W. Então elas são iguais tanto em X quanto em W. De acordo com a Premissa 1, elas também serão iguais em Y. Portanto, de acordo com a Premissa 2, elas serão iguais em Z também.

A regra da pseudotransitividade está provada.

Todas as regras são comprovadas.

3. Regras de inferência derivadas

Outro exemplo de regras pelas quais se pode, se necessário, derivar novas regras de dependência funcional são as chamadas regras de inferência derivadas.

Quais são essas regras, como elas são obtidas?

Sabe-se que se outras são deduzidas de algumas regras já existentes por métodos lógicos legítimos, então essas novas regras, chamadas derivados, pode ser usado junto com as regras originais.

Deve-se notar especialmente que essas regras muito arbitrárias são "derivadas" precisamente das regras de inferência de Armstrong pelas quais passamos anteriormente.

Vamos formular as regras derivadas para derivar dependências funcionais na forma do seguinte teorema.

Teorema

As regras a seguir são derivadas das regras de inferência de Armstrong.

Regra de Inferência 1. ├ X ∪ Z → X;

Regra de Inferência 2. X → Y, X → Z ├ X ∪ Y → Z;

Regra de Inferência 3. X → Y ∪ Z ├ X → Y, X → Z;

Aqui X, Y, Z, W, como no caso anterior, são subesquemas arbitrários do esquema da relação S.

1. A primeira regra derivada é chamada regra da trivialidade e lê-se assim:

"A regra é derivada: 'a união dos subcircuitos X e Z implica funcionalmente X'".

Uma dependência funcional com o lado esquerdo sendo um subconjunto do lado direito é chamada trivial. De acordo com a regra da trivialidade, as restrições de dependência triviais são aplicadas automaticamente.

Curiosamente, a regra da trivialidade é uma generalização da regra da reflexividade e, como esta, pode ser derivada diretamente da definição da restrição de dependência funcional. O fato de que esta regra é derivada não é acidental e está relacionado à completude do sistema de regras de Armstrong. Falaremos mais sobre a completude do sistema de regras de Armstrong um pouco mais tarde.

2. A segunda regra derivada é chamada regra de aditividade e diz o seguinte: "Se o subcircuito X determina funcionalmente o subcircuito Y, e X simultaneamente determina funcionalmente Z, então a seguinte regra é deduzida dessas regras: "X determina funcionalmente a união dos subcircuitos Y e Z"".

3. A terceira regra derivada é chamada regra de projetividade ou a regrareversão de aditividade". Lê-se da seguinte forma: "Se o subcircuito X determina funcionalmente a união dos subcircuitos Y e Z, então a seguinte regra é deduzida desta regra: "X determina funcionalmente o subcircuito Y e ao mesmo tempo X determina funcionalmente o subcircuito Z" ", ou seja, de fato, esta regra derivada é a regra de aditividade invertida.

É curioso que as regras de aditividade e projetividade aplicadas às dependências funcionais com as mesmas partes esquerdas permitem combinar ou, inversamente, dividir as partes direitas da dependência.

Na construção de cadeias de inferência, após formular todas as premissas, aplica-se a regra da transitividade para incluir uma dependência funcional com o lado direito na conclusão.

Desenhar evidência regras de inferência arbitrárias listadas.

1. Prova da regra trivialidades.

Vamos realizá-lo, como todas as provas posteriores, passo a passo:

1) temos: X → X (da regra da reflexividade da inferência de Armstrong);

2) ainda temos: X ∪ Z → X (obtido pela primeira aplicação da regra de conclusão de inferência de Armstrong, e depois como consequência do primeiro passo da prova).

A regra da trivialidade foi comprovada.

2. Faremos uma prova passo a passo da regra aditividade:

1) temos: X → Y (esta é a premissa 1);

2) temos: X → Z (esta é a premissa 2);

3) temos: Y ∪ Z → Y ∪ Z (da regra da reflexividade da inferência de Armstrong);

4) temos: X ∪ Z → Y ∪ Z (obtido pela aplicação da regra da pseudotransitividade da inferência de Armstrong, e depois como consequência do primeiro e terceiro passos da prova);

5) temos: X ∪ X → Y ∪ Z (obtido pela aplicação da regra da pseudotransitividade de inferência de Armstrong, e segue da segunda e quarta etapas);

6) temos X → Y ∪ Z (segue do quinto passo).

A regra da aditividade está provada.

3. E finalmente, construiremos uma prova da regra projetividade:

1) temos: X → Y ∪ Z, X → Y ∪ Z (esta é uma premissa);

2) temos: Y → Y, Z → Z (derivado usando a regra de reflexividade de inferência de Armstrong);

3) temos: Y ∪ z → y, Y ∪ z → Z (obtido da regra de conclusão de inferência de Armstrong e o corolário do segundo passo da prova);

4) temos: X → Y, X → Z (obtido pela aplicação da regra da pseudotransitividade da inferência de Armstrong, e depois como consequência do primeiro e terceiro passos da prova).

A regra da projetividade está provada.

Todas as regras de inferência derivadas são comprovadas.

4. Completude do sistema de regras de Armstrong

Seja F(S) um dado conjunto de dependências funcionais definidas sobre o esquema de relação S.

Denotado por inv a restrição imposta por este conjunto de dependências funcionais. Vamos anotá-lo:

inv r(S) = ∀X → Y ∈F(S) [inv r(S)].

Assim, esse conjunto de restrições impostas pelas dependências funcionais é decifrado da seguinte forma: para qualquer regra do sistema de dependências funcionais X → Y pertencentes ao conjunto de dependências funcionais F(S), a restrição de dependências funcionais inv r(S) definido sobre o conjunto da relação r(S).

Deixe que alguma relação r(S) satisfaça essa restrição.

Aplicando as regras de inferência de Armstrong às dependências funcionais definidas para o conjunto F(S), pode-se obter novas dependências funcionais, como já dissemos e provamos anteriormente. E, o que é indicativo, a relação F(S) irá satisfazer automaticamente as restrições dessas dependências funcionais, como pode ser visto na forma estendida das regras de inferência de Armstrong. Lembre-se da forma geral dessas regras de inferência estendidas:

Regra de Inferência 1. inv r(S);

Regra de Inferência 2. inv r(S) ⇒ inv<X ∪ Z → Y> r(S);

Regra de Inferência 3. inv r(S) & inv ∪ W → Z> r(S) ⇒ inv<X ∪ W→Z>;

Voltando ao nosso raciocínio, vamos reabastecer o conjunto F(S) com novas dependências derivadas dele usando as regras de Armstrong. Aplicaremos este procedimento de reabastecimento até que não tenhamos mais novas dependências funcionais. Como resultado dessa construção, obteremos um novo conjunto de dependências funcionais, chamado fecho conjunto F(S) e denotado F⁺Diversidade, Igualdade e Compromisso para com a Sociedade.

De fato, tal nome é bastante lógico, pois nós pessoalmente, através de uma longa construção, "fechamos" o conjunto de dependências funcionais existentes sobre si mesmo, acrescentando (daí o "+") todas as novas dependências funcionais resultantes das existentes.

Deve-se notar que esse processo de construção de um fechamento é finito, pois o próprio esquema de relações, sobre o qual todas essas construções são realizadas, é finito.

Escusado será dizer que um encerramento é um superconjunto do conjunto que está sendo fechado (na verdade, é maior!) e não muda de forma alguma quando é fechado novamente.

Se escrevermos o que acabamos de dizer em uma forma formulada, obtemos:

F(S) ⊆ F⁺(S), [F⁺(S)]⁺= F⁺(S);

Além disso, da verdade provada (ou seja, legalidade, legitimidade) das regras de inferência de Armstrong e a definição de fechamento, segue-se que qualquer relação que satisfaça as restrições de um determinado conjunto de dependências funcionais satisfará a restrição da dependência pertencente ao fechamento .

X → Y ∈ F⁺Diversidade, Igualdade e Compromisso para com a Sociedade ⇒ ∀r(S) [inv r(S) ⇒ inv r(S)];

Assim, o teorema da completude de Armstrong para o sistema de regras de inferência afirma que a implicação externa pode ser legitimamente e justificadamente substituída pela equivalência.

(Não consideraremos a prova deste teorema, uma vez que o processo de prova em si não é tão importante em nosso curso particular de aulas.)

<< Voltar: Criando relacionamentos básicos (Símbolos metalinguísticos. Um exemplo de criação de uma relação de base em um registro de pseudocódigo. Restrições de integridade com estado. Restrições de integridade referencial. O conceito de índices. Modificação de relações de base)

>> Encaminhar: Formas normais (O significado de normalizar esquemas de banco de dados. Primeira forma normal (1NF). Segunda forma normal (2NF). Terceira forma normal (3NF). Forma normal de Boyce-Codd (NFBC). Aninhamento de formas normais)

Recomendamos artigos interessantes seção Notas de aula, folhas de dicas:

▪ Microeconomia. Notas de aula

▪ Gestão Estratégica. Notas de aula

▪ História e teoria das religiões. Notas de aula

Veja outros artigos seção Notas de aula, folhas de dicas.

Leia e escreva útil comentários sobre este artigo.

<< Voltar

Últimas notícias de ciência e tecnologia, nova eletrônica:

A existência de uma regra de entropia para o emaranhamento quântico foi comprovada 09.05.2024

A mecânica quântica continua a nos surpreender com seus fenômenos misteriosos e descobertas inesperadas. Recentemente, Bartosz Regula do Centro RIKEN de Computação Quântica e Ludovico Lamy da Universidade de Amsterdã apresentaram uma nova descoberta que diz respeito ao emaranhamento quântico e sua relação com a entropia. O emaranhamento quântico desempenha um papel importante na moderna ciência e tecnologia da informação quântica. No entanto, a complexidade da sua estrutura torna a sua compreensão e gestão um desafio. A descoberta de Regulus e Lamy mostra que o emaranhamento quântico segue uma regra de entropia semelhante à dos sistemas clássicos. Esta descoberta abre novas perspectivas na ciência e tecnologia da informação quântica, aprofundando a nossa compreensão do emaranhamento quântico e a sua ligação à termodinâmica. Os resultados do estudo indicam a possibilidade de reversibilidade das transformações de emaranhamento, o que poderia simplificar muito seu uso em diversas tecnologias quânticas. Abrindo uma nova regra ... >>

Mini ar condicionado Sony Reon Pocket 5 09.05.2024

O verão é uma época de relaxamento e viagens, mas muitas vezes o calor pode transformar essa época em um tormento insuportável. Conheça um novo produto da Sony – o minicondicionador Reon Pocket 5, que promete deixar o verão mais confortável para seus usuários. A Sony lançou um dispositivo exclusivo - o minicondicionador Reon Pocket 5, que fornece resfriamento corporal em dias quentes. Com ele, os usuários podem desfrutar do frescor a qualquer hora e em qualquer lugar, simplesmente usando-o no pescoço. Este miniar condicionado está equipado com ajuste automático dos modos de operação, além de sensores de temperatura e umidade. Graças a tecnologias inovadoras, o Reon Pocket 5 ajusta o seu funcionamento em função da atividade do utilizador e das condições ambientais. Os usuários podem ajustar facilmente a temperatura usando um aplicativo móvel dedicado conectado via Bluetooth. Além disso, camisetas e shorts especialmente desenhados estão disponíveis para maior comodidade, aos quais um mini ar condicionado pode ser acoplado. O dispositivo pode, oh ... >>

Energia do espaço para Starship 08.05.2024

A produção de energia solar no espaço está se tornando mais viável com o advento de novas tecnologias e o desenvolvimento de programas espaciais. O chefe da startup Virtus Solis compartilhou sua visão de usar a Starship da SpaceX para criar usinas orbitais capazes de abastecer a Terra. A startup Virtus Solis revelou um ambicioso projeto para criar usinas de energia orbitais usando a Starship da SpaceX. Esta ideia poderia mudar significativamente o campo da produção de energia solar, tornando-a mais acessível e barata. O cerne do plano da startup é reduzir o custo de lançamento de satélites ao espaço usando a Starship. Espera-se que este avanço tecnológico torne a produção de energia solar no espaço mais competitiva com as fontes de energia tradicionais. A Virtual Solis planeja construir grandes painéis fotovoltaicos em órbita, usando a Starship para entregar os equipamentos necessários. Contudo, um dos principais desafios ... >>

Notícias aleatórias do Arquivo O dano mortal dos cigarros eletrônicos 17.09.2018 Ao usar cigarros eletrônicos, uma proporção significativa de produtos químicos causadores de câncer é depositada nos pulmões, concluíram cientistas da Universidade de Nevada e do Desert Research Institute. Durante o experimento, especialistas analisaram a concentração no corpo de 12 pessoas antes e depois do uso de cigarros eletrônicos de aldeídos, toxinas perigosas, algumas das quais causam câncer. Os cientistas compararam o nível de toxinas na fumaça de um cigarro eletrônico e no ar exalado pelos participantes do experimento enquanto fumavam. De acordo com os resultados do experimento, foi possível estabelecer que a concentração média de aldeídos no ar exalado é dez vezes e meia maior após uma sessão de fumar cigarros eletrônicos do que antes. Os cientistas também descobriram que a concentração de substâncias perigosas como o formaldeído no ar exalado é centenas de vezes menor do que na fumaça de um cigarro eletrônico, o que indica a deposição de uma quantidade significativa dessa substância no corpo humano. O experimento demonstrou o dano potencial dos cigarros eletrônicos devido aos aldeídos em sua fumaça, concluíram os pesquisadores. Anteriormente, os cientistas disseram que o uso de cigarros eletrônicos aumenta o risco de desenvolver câncer bucal tanto quanto fumar cigarros regulares.

Outras notícias interessantes:

▪ ameba em âmbar

▪ Simuladores quânticos analógicos

▪ Umidificador facial portátil Xiaomi Lady Bei

▪ porta no fundo do lago

▪ Telescópio James Webb lançado em órbita

Feed de notícias de ciência e tecnologia, nova eletrônica

Materiais interessantes da Biblioteca Técnica Gratuita:

▪ seção do site Relógios, temporizadores, relés, interruptores de carga. Seleção de artigos

▪ artigo Konstantin Georgievich. Aforismos famosos

▪ artigo Quem e quando usou a música pop para transmitir uma mensagem em código Morse? Resposta detalhada

▪ artigo Rábano comum. Lendas, cultivo, métodos de aplicação

▪ Artigo UMZCH com proteção ambiental profunda. Enciclopédia de rádio eletrônica e engenharia elétrica

▪ artigo 4 cartas e 4 moedas. Segredo do foco

Deixe seu comentário neste artigo:

Todos os idiomas desta página

Arabic	Hebrew	Polish
Bengali	Hindi	Portuguese
Chinese	Italian	Spanish
English	Japanese	Turkish
French	Korean	Ukrainian
German	Malay	Vietnamese

Página principal | Biblioteca | Artigos | Mapa do Site | Revisões do site

www.diagrama.com.ua
2000-2024