Questão de Banco de Dados — SQL — FGV 2023

Álgebra relacional: regras de transformação e otimização de consultas

Gabarito: letra E. As três afirmativas estão corretas: a álgebra relacional fornece regras de transformação que preservam a equivalência entre expressões, e essas regras são a base das otimizações heurísticas que os SGBDs relacionais aplicam sobre consultas SQL — como a cascata de seleções, a comutatividade de seleções e a comutação de seleção com produto cartesiano. O gabarito oficial é a letra E (I, II e III).

A álgebra relacional é uma linguagem formal que define um conjunto de operações sobre relações (tabelas), como seleção (σ), projeção (π), produto cartesiano (×), junção (⋈), união, diferença e interseção. Cada operação recebe uma ou duas relações como entrada e produz uma nova relação como saída. O que a questão cobra é o papel dessas operações no processo de otimização de consultas: quando um SGBD recebe uma consulta SQL, ele a traduz para uma expressão da álgebra relacional (representada como uma árvore de consulta) e, em seguida, aplica regras de transformação para reordenar as operações, buscando um plano de execução mais eficiente.

As regras de transformação são equivalências lógicas entre expressões algébricas. Por exemplo, uma seleção com condição conjuntiva (σc1 AND c2) pode ser desmembrada em uma cascata de seleções individuais; a seleção é comutativa (σc1(σc2(R)) ≡ σc2(σc1(R))); e a seleção pode ser comutada com o produto cartesiano quando a condição envolve apenas uma das relações. Essas regras são chamadas de heurísticas porque, na maioria dos casos, produzem planos mais eficientes, mas não garantem o plano ótimo em todas as situações. O otimizador também pode usar estimativas de custo para escolher entre estratégias alternativas.

Na prática, o processo funciona assim: o SGBD recebe uma consulta SQL, decompõe em blocos SELECT-FROM-WHERE, traduz cada bloco para uma árvore de consulta da álgebra relacional e aplica as regras de transformação para reordenar as operações. Por exemplo, mover a seleção para baixo na árvore (aplicá-la antes da junção) reduz o número de tuplas que participam da junção, tornando a execução mais rápida. Da mesma forma, mover a projeção para baixo reduz o número de atributos nas relações intermediárias. Essas transformações preservam a equivalência lógica, ou seja, o resultado final é o mesmo, mas o custo de execução é menor.

A distinção importante aqui é entre otimização heurística (baseada em regras de reordenação) e otimização baseada em custo (que estima o custo de diferentes planos e escolhe o mais barato). A questão trata da primeira, que é exatamente o que as regras de transformação da álgebra relacional permitem. A pegadinha que a banca explora é confundir essas duas abordagens ou achar que as regras garantem o plano ótimo — elas apenas melhoram a eficiência na maioria dos casos.

Guarde a fronteira entre regras de transformação (equivalências que preservam o resultado) e estratégias de execução (algoritmos que implementam as operações): é exatamente nela que as alternativas se dividem.

Item I — ✅ Correto

A afirmativa I está correta: as regras de transformação gerais da álgebra relacional são amplamente utilizadas pelos SGBDs relacionais para otimizar consultas SQL. Isso é confirmado pelo texto de apoio, que afirma que "as regras de transformação são equivalências lógicas entre expressões algébricas" e que o otimizador "aplica regras de transformação para reordenar as operações, buscando um plano de execução mais eficiente". A otimização heurística é uma das duas técnicas principais empregadas durante a otimização de consultas, conforme descrito no material.

Item II — ✅ Correto

A afirmativa II está correta: as regras de transformação preservam a equivalência entre expressões da álgebra relacional. O texto de apoio afirma que "temos de garantir que as etapas de transformação sempre levem a uma árvore de consulta equivalente" e que "o otimizador de consulta precisa saber quais regras de transformação preservam essa equivalência". Isso é fundamental: sem a preservação da equivalência, o otimizador não poderia reordenar as operações sem alterar o resultado da consulta.

Item III — ✅ Correto

A afirmativa III está correta: as regras de transformação são a base das otimizações heurísticas. O texto de apoio descreve que "as regras costumam reordenar as operações em uma árvore de consulta" e que "uma árvore de consulta pode ser transformada passo a passo em uma árvore de consulta equivalente que é mais eficiente de executar". Exemplos concretos incluem a cascata de seleções (σc1 AND c2 ≡ σc1(σc2(R))), a comutatividade de seleções e a comutação de seleção com produto cartesiano. Essas regras são exatamente o que permite ao otimizador melhorar a eficiência da execução.

Conclusão: corretos os itens I, II e III → portanto a alternativa é a letra E.

Gabarito: letra E