Questão de Banco de Dados — Consultas e Comandos em SQL — FGV 2023

Consultas SQL: identificando lacunas em sequências de potências de 2

Gabarito: letra E. A consulta correta deve, para cada par de potências consecutivas presentes na tabela (t1 e t2), retornar o intervalo de expoentes ausentes entre elas: log(t1.N,2)+1 (primeiro expoente ausente) e log(t2.N,2)-1 (último expoente ausente), filtrando apenas os pares que são consecutivos na sequência — condição garantida pela subconsulta NOT EXISTS que verifica a inexistência de qualquer potência intermediária entre t1.N e t2.N. A alternativa E é a única que combina corretamente a projeção dos expoentes com a condição de consecutividade.

O problema pede para descobrir os intervalos de expoentes ausentes em uma sequência de potências de 2. A tabela TT contém apenas os valores presentes (por exemplo, 4, 16, 32, 256, 1024). Para cada par de valores consecutivos presentes (t1.N e t2.N, com t1.N < t2.N), os expoentes ausentes entre eles são todos os inteiros x tais que log(t1.N,2) < x < log(t2.N,2). O primeiro ausente é log(t1.N,2)+1 e o último é log(t2.N,2)-1. Por exemplo, entre 4 (expoente 2) e 16 (expoente 4), os ausentes são 3-3; entre 16 (4) e 32 (5), não há ausentes; entre 32 (5) e 256 (8), os ausentes são 6-7; entre 256 (8) e 1024 (10), o ausente é 9-9.

A dificuldade está em garantir que t1 e t2 sejam consecutivos na sequência de potências presentes — ou seja, que não exista nenhuma outra potência entre eles. Se não houvesse essa restrição, qualquer par de valores geraria um intervalo, mesmo que houvesse potências intermediárias presentes. A subconsulta NOT EXISTS resolve isso: ela verifica se não existe nenhuma linha tt tal que t1.N < tt.N AND t2.N > tt.N. Se existir, o par não é consecutivo e é descartado. Essa é a técnica clássica de "gap detection" em SQL, usada para encontrar lacunas em sequências numéricas.

A pegadinha da banca está em duas frentes: (1) a projeção correta dos expoentes — muitos candidatos erram ao usar log(t1.N,2) em vez de log(t1.N,2)+1 para o início do intervalo, ou log(t2.N,2) em vez de log(t2.N,2)-1 para o fim; (2) a condição de consecutividade — a alternativa B usa EXISTS em vez de NOT EXISTS, o que selecionaria exatamente os pares que NÃO são consecutivos, invertendo o resultado. A alternativa D também erra ao usar t1.N < t2.N - 1 em vez da comparação logarítmica, o que não funciona corretamente para potências de 2 (por exemplo, 4 e 8: 4 < 7 é verdadeiro, mas não há ausentes entre eles).

Guarde o critério decisivo: para cada par de potências presentes, o intervalo de expoentes ausentes é [log(t1.N,2)+1, log(t2.N,2)-1], e o par só é considerado se não existir nenhuma potência intermediária. É exatamente essa combinação que separa a alternativa correta das demais.

Alternativa A — ❌ Incorreta

A projeção está errada: usa log(t1.N + 1, 2) e log(t2.N - 1, 2). Isso calcula o logaritmo de (N+1) e (N-1), não o expoente de N. Por exemplo, para t1.N = 4, log(5,2) ≈ 2.32, enquanto o correto seria log(4,2)+1 = 3. A alternativa confunde a operação de somar/subtrair do valor com a operação sobre o expoente. O correto é somar/subtrair do resultado do logaritmo, não do argumento.

Alternativa B — ❌ Incorreta

A projeção está correta (log(t1.N,2)+1 e log(t2.N,2)-1), mas a subconsulta usa EXISTS em vez de NOT EXISTS. A condição EXISTS (select * from TT tt where t1.N > tt.N and t2.N < tt.N) seleciona os pares que possuem pelo menos uma potência intermediária — ou seja, os pares que NÃO são consecutivos. Isso inverte completamente o resultado: em vez de retornar os intervalos de ausentes, retornaria os intervalos entre potências que têm outras potências no meio, o que não faz sentido para o problema. A troca de NOT EXISTS por EXISTS é a pegadinha central desta alternativa.

Alternativa C — ❌ Incorreta

A projeção do primeiro expoente está errada: usa log(t1.N,2) em vez de log(t1.N,2)+1. Isso retornaria o expoente da própria potência presente, não o primeiro expoente ausente. Por exemplo, entre 4 (expoente 2) e 16 (expoente 4), retornaria 2 como início do intervalo, mas o correto é 3. A condição NOT EXISTS está correta, mas a projeção do início do intervalo está deslocada em uma unidade.

Alternativa D — ❌ Incorreta

A projeção do segundo expoente está errada: usa log(t2.N,2) em vez de log(t2.N,2)-1. Isso retornaria o expoente da própria potência presente, não o último expoente ausente. Além disso, a condição t1.N < t2.N - 1 não é equivalente à comparação logarítmica. Para potências de 2, t1.N < t2.N - 1 pode ser verdadeiro mesmo quando não há ausentes (ex.: 4 e 8: 4 < 7 é verdadeiro, mas não há expoente inteiro entre 2 e 3). A subconsulta EXISTS também está invertida, como na alternativa B.

Alternativa E — ✅ Correta ⟵ GABARITO

A projeção está correta: log(t1.N,2)+1 (primeiro expoente ausente) e log(t2.N,2)-1 (último expoente ausente). A condição log(t1.N,2)+1 < log(t2.N,2) garante que há pelo menos um expoente inteiro entre os dois (ou seja, o intervalo não é vazio). A subconsulta NOT EXISTS garante que não existe nenhuma potência intermediária entre t1.N e t2.N, ou seja, que o par é consecutivo na sequência de potências presentes. O ORDER BY 1 ordena pelo primeiro expoente, produzindo os intervalos na ordem correta. Para o exemplo dado (4, 16, 32, 256, 1024), retorna exatamente 3-3, 6-7, 9-9.

Gabarito: letra E