Resumo TI Banco de Dados: Equivalência de Expressões Relacionais

O resumo anterior mostrou que álgebra e cálculo relacional têm o mesmo poder de expressão — a completude relacional. Mas dentro da própria álgebra existe uma outra equivalência, mais prática: a mesma consulta pode ser escrita de várias formas diferentes, combinando os operadores em ordens distintas, e ainda assim produzir exatamente o mesmo resultado. É essa equivalência que todo otimizador de consultas explora por trás dos panos, e é exatamente ela que este resumo formaliza.

Neste resumo, você vai entender as principais regras de equivalência entre expressões da álgebra relacional — comutatividade, associatividade e a possibilidade de “empurrar” seleção e projeção para mais cedo na expressão —, e por que a diferença (−) é a exceção que quebra várias dessas regras.

🔄 Comutatividade: trocar a ordem sem trocar o resultado

Vários operadores da trilha são comutativos — a ordem dos operandos não altera o resultado:

• Seleção em cascata comuta: σ_c1(σ_c2(R)) = σ_c2(σ_c1(R)) — e ambas equivalem a uma única seleção com as condições combinadas por E lógico: σ_c1∧c2(R);
• Produto cartesiano e junção comutam: R × S = S × R e R ⋈ S = S ⋈ R (a ordem das colunas no resultado muda, mas o conteúdo lógico é o mesmo);
• União e interseção comutam: R ∪ S = S ∪ R e R ∩ S = S ∩ R, coerente com a origem desses operadores na teoria de conjuntos, vista nos resumos anteriores.

A diferença não comuta: R − S ≠ S − R em geral — subtrair S de R não é o mesmo que subtrair R de S, o que já era esperado, já que a diferença isola o que está de um lado e não do outro.

🔗 Associatividade: reagrupar sem trocar o resultado

Produto cartesiano, junção, união e interseção também são associativos: (R × S) × T = R × (S × T), e o mesmo vale trocando × por ⋈, ∪ ou ∩. Isso significa que, ao combinar três ou mais relações, a ordem em que os pares são combinados primeiro não muda o resultado final — só pode mudar o custo de processamento, já que relações intermediárias maiores ou menores impactam o desempenho. A diferença, mais uma vez, foge à regra: (R − S) − T não é sempre igual a R − (S − T).

⬇️ Empurrando seleção e projeção para mais cedo

A regra de equivalência mais explorada na prática é a que permite antecipar seleção e projeção, aplicando-as antes de operações mais custosas como junção e produto cartesiano:

• Seleção distribui sobre junção quando a condição usa apenas atributos de um dos lados: σ_c(R ⋈ S) = σ_c(R) ⋈ S, se c referencia só atributos de R — filtrar R antes de juntar produz o mesmo resultado, mas com uma junção sobre uma relação menor;
• Seleção distribui sobre união, interseção e diferença: σ_c(R ∪ S) = σ_c(R) ∪ σ_c(S) — e o mesmo padrão vale para ∩ e −, desde que R e S sejam união-compatíveis (mesmo grau e domínios compatíveis, como formalizado no resumo dos operadores de conjunto);
• Projeção em cascata se reduz à mais restritiva: π_L1(π_L2(R)) = π_L1(R), desde que L1 seja um subconjunto dos atributos de L2 — projetar em cascata equivale a projetar direto na lista final de atributos;
• Seleção e projeção comutam entre si quando os atributos da condição de seleção também estão na lista de projeção: π_L(σ_c(R)) = σ_c(π_L(R)) — se algum atributo usado na condição c não estiver em L, é preciso incluí-lo provisoriamente na projeção interna e só descartá-lo depois da seleção, senão a condição não teria como ser avaliada.

Essas equivalências não mudam o resultado lógico da consulta, mas mudam o tamanho das relações intermediárias geradas ao longo do processamento — filtrar e projetar cedo tendem a reduzir esse tamanho antes das operações mais pesadas.

⚠️ Pegadinhas comuns

• Diferença não é comutativa nem associativa: é a exceção que a banca mais cobra — todos os outros operadores vistos na trilha (×, ⋈, ∪, ∩) são comutativos e associativos, mas a diferença não é nenhuma das duas coisas;
• “Empurrar seleção para antes da junção” só vale com a ressalva de atributos: a condição da seleção só pode ser aplicada antes se envolver exclusivamente atributos do lado para o qual está sendo empurrada — misturar atributos dos dois lados exige manter a seleção depois da junção;
• Equivalência não é sobre custo, é sobre resultado: duas expressões equivalentes sempre produzem a mesma relação de saída — a equivalência não diz que o custo de processamento é igual, só que o resultado lógico é idêntico;
• Projeção em cascata exige relação de subconjunto entre as listas de atributos: π_L1(π_L2(R)) = π_L1(R) só vale se L1 ⊆ L2 — se a lista mais interna já tiver descartado um atributo que a mais externa tentaria usar, a equivalência não se aplica;
• Trocar σ e π também tem ressalva de atributos: só é possível empurrar a projeção para antes da seleção sem ajuste se todo atributo usado na condição já estiver na lista projetada — caso contrário, é preciso projetar também esse atributo “emprestado” e só remover depois de aplicar a seleção.

🎯 Dica Final para a Prova

Sempre que a questão pedir para identificar duas expressões algébricas equivalentes, comece checando se o operador em jogo é ×, ⋈, ∪ ou ∩ (comutativos e associativos) ou − (a exceção). Se a questão descrever “empurrar” seleção ou projeção para antes de uma junção, verifique se a condição ou a lista de atributos respeita a ressalva de pertencer só ao lado correto — é aí que a maioria das pegadinhas mora.

✓ Agora que você conhece as regras que permitem reescrever uma expressão sem mudar o resultado, o próximo passo é ver como um otimizador de consultas usa exatamente essas regras na prática: a otimização algébrica de consultas.

📍Gostou do conteúdo? Deixe um comentário, compartilhe e continue acompanhando o Dicionário do Concurseiro para mais Resumos de TI – Banco de Dados. Aqui você encontra explicações claras, atualizadas e com foco total no que cai em prova!

👉 Em breve no Dicionário do Concurseiro: Resumo TI Banco de Dados: Otimização Algébrica de Consultas

📘 Regras de equivalência não mudam o resultado da consulta — mudam apenas o caminho até ele. Comutatividade, associatividade e antecipação de seleção/projeção são a base de todo otimizador de consultas. Continue estudando!