Álgebra Relacional

Vou te conduzir agora por um dos temas mais elegantes e, ao mesmo tempo, mais cobrados de toda a disciplina de Banco de Dados: a Álgebra Relacional. Quero que você encare este módulo como o “chassi” sobre o qual o SQL inteiro foi montado. Quando Edgar F. Codd publicou seu modelo relacional em 1970, ele não entregou uma linguagem amigável como o SQL que você digita hoje; ele entregou uma teoria matemática rigorosa, baseada em conjuntos, que descreve exatamente o que significa consultar dados. Toda vez que você escreve um SELECT, o otimizador do seu SGBD traduz aquilo internamente para uma expressão de álgebra relacional, reescreve essa expressão em uma forma equivalente mais barata, e só então executa. Por isso eu insisto: quem domina a álgebra relacional não decora SQL, entende SQL. E numa prova da USP, esse entendimento é o que separa quem acerta as questões de tradução, equivalência e otimização de quem chuta.

A grande sacada da álgebra relacional é que ela é fechada: cada operador recebe uma ou duas relações e devolve outra relação. Isso é o que permite encaixar operadores como peças de Lego, formando expressões aninhadas arbitrariamente complexas. Repare comigo nesse ponto ao longo de todo o texto, porque ele é a essência de tudo.

Por que a álgebra relacional é a base teórica do SQL

Antes de mergulhar nos operadores, deixa eu situar o terreno. A álgebra relacional é uma linguagem procedural: ela diz como obter o resultado, descrevendo uma sequência de operações sobre relações. O parente declarativo dela é o Cálculo Relacional, que diz apenas o que se quer, sem especificar o passo a passo. O SQL fica num meio-termo curioso: sua sintaxe parece declarativa (você descreve o resultado desejado), mas internamente o motor o converte para algo procedural — uma árvore de operadores algébricos.

flowchart LR
    A[Consulta SQL] --> B[Parser e validacao]
    B --> C[Arvore de algebra relacional]
    C --> D[Reescrita e otimizacao algebrica]
    D --> E[Plano fisico de execucao]
    E --> F[Resultado]

Por que isso cai em prova: a banca adora pedir que você traduza uma expressão algébrica em SQL (ou o contrário), ou que reconheça duas expressões como equivalentes. Tudo isso vive sobre a propriedade de fechamento e sobre as equivalências algébricas que veremos na seção de otimização.

Vou trabalhar o módulo inteiro em cima de um pequeno esquema de exemplo, para você fixar visualmente cada operador. Considere as relações Empregados(ID, Nome, Idade, Salario, DeptID) e Departamentos(DeptID, NomeDept). Sempre que possível, mostrarei a definição formal em LaTeX, o resultado em tabela markdown e o SQL equivalente.

Operações primitivas unárias

As operações unárias atuam sobre uma única relação. Elas são as ferramentas de recorte: cortam linhas, cortam colunas ou trocam rótulos.

Seleção (\sigma)

A seleção filtra tuplas (linhas) que satisfazem uma condição booleana. É um recorte horizontal da relação. Formalmente:

\sigma_{\theta}(R) = \{\, t \mid t \in R \;\wedge\; \theta(t) \,\}

onde \theta é um predicado construído com comparadores (=, \neq, <, \leq, >, \geq) e conectivos lógicos (\wedge, \vee, \neg). Para selecionar os empregados com idade superior a 30:

\sigma_{\text{Idade} > 30}(\text{Empregados})

Partindo desta tabela base:

ID	Nome	Idade	Salario	DeptID
1	Ana	28	4000	10
2	Bruno	35	6200	10
3	Carla	42	7500	20
4	Diego	25	3800	NULL

o resultado da seleção é:

ID	Nome	Idade	Salario	DeptID
2	Bruno	35	6200	10
3	Carla	42	7500	20

SELECT * FROM Empregados WHERE Idade > 30;

Note que o predicado da seleção corresponde diretamente à cláusula WHERE. Essa é a tradução mais limpa de toda a álgebra.

Projeção (\pi)

A projeção faz o recorte vertical: escolhe um subconjunto de atributos (colunas). Como uma relação é um conjunto matemático e conjuntos não admitem duplicatas, a projeção elimina tuplas repetidas que possam surgir após descartar colunas. Formalmente:

\pi_{A_1, A_2, \dots, A_k}(R)

onde \{A_1, \dots, A_k\} é o subconjunto de atributos retidos. Projetando nome e salário:

\pi_{\text{Nome},\,\text{Salario}}(\text{Empregados})

SELECT DISTINCT Nome, Salario FROM Empregados;

Atenção decisiva: a projeção algébrica é equivalente a SELECT DISTINCT, não ao SELECT simples. O SQL, por padrão, trabalha com multiconjuntos (bags) e mantém duplicatas; a álgebra relacional pura trabalha com conjuntos (sets). Essa diferença entre semântica de conjunto e de multiconjunto é uma das pegadinhas favoritas das bancas.

Renomeação (\rho)

A renomeação troca o nome de uma relação ou de seus atributos, sem alterar o conteúdo. Ela existe por uma necessidade técnica: muitas expressões — sobretudo autojunções — exigem que você distinga duas instâncias da mesma relação. Formalmente:

\rho_{S}(R) \qquad \text{ou} \qquad \rho_{S(B_1, \dots, B_n)}(R)

A primeira forma renomeia a relação para S; a segunda também renomeia os atributos para B_1, \dots, B_n. Por exemplo, para renomear Salario para Remuneracao:

\rho_{E(\text{ID},\,\text{Nome},\,\text{Idade},\,\text{Remuneracao},\,\text{DeptID})}(\text{Empregados})

SELECT
    ID,
    Nome,
    Idade,
    Salario AS Remuneracao,
    DeptID
FROM Empregados AS E;

O AS do SQL faz exatamente o papel do \rho: tanto para colunas quanto para a própria tabela (aliás de tabela).

Operações binárias de conjunto

Agora passamos para operadores que combinam duas relações. Os três primeiros — união, diferença e interseção — herdam diretamente a teoria de conjuntos e exigem uma condição prévia: as relações devem ser compatíveis em união (union-compatible). Isso significa ter o mesmo grau (mesmo número de atributos) e domínios correspondentes compatíveis, posição a posição.

Para ilustrar, considere duas relações com o mesmo esquema, Graduacao(ID, Nome) e PosGraduacao(ID, Nome):

ID	Nome		ID	Nome
1	Ana		2	Bruno
2	Bruno		5	Elena

(à esquerda Graduacao, à direita PosGraduacao)

União (\cup)

A união reúne todas as tuplas presentes em pelo menos uma das relações, sem repetições:

R \cup S = \{\, t \mid t \in R \;\vee\; t \in S \,\}

Resultado de \text{Graduacao} \cup \text{PosGraduacao}:

ID	Nome
1	Ana
2	Bruno
5	Elena

SELECT ID, Nome FROM Graduacao
UNION
SELECT ID, Nome FROM PosGraduacao;

Lembre-se de que UNION elimina duplicatas; se você quisesse manter repetições (semântica de multiconjunto), usaria UNION ALL, que não tem equivalente direto na álgebra de conjuntos pura.

Diferença (-)

A diferença devolve as tuplas que estão em R mas não em S:

R - S = \{\, t \mid t \in R \;\wedge\; t \notin S \,\}

O resultado de \text{Graduacao} - \text{PosGraduacao} (quem é da graduação e não da pós) é:

ID	Nome
1	Ana

SELECT ID, Nome FROM Graduacao
EXCEPT
SELECT ID, Nome FROM PosGraduacao;

A diferença é o único desses três operadores de conjunto que não é comutativo: R - S \neq S - R. Guarde isso.

Interseção (\cap)

A interseção devolve as tuplas presentes em ambas as relações:

R \cap S = \{\, t \mid t \in R \;\wedge\; t \in S \,\}

Resultado de \text{Graduacao} \cap \text{PosGraduacao}:

ID	Nome
2	Bruno

SELECT ID, Nome FROM Graduacao
INTERSECT
SELECT ID, Nome FROM PosGraduacao;

Detalhe formal que a banca explora: a interseção não é primitiva. Ela pode ser derivada da diferença pela identidade R \cap S = R - (R - S). O conjunto verdadeiramente mínimo de operadores primitivos é \{\sigma, \pi, \cup, -, \times, \rho\} — seleção, projeção, união, diferença, produto cartesiano e renomeação. Todo o resto (interseção, junções, divisão) é açúcar derivado desses seis.

Produto cartesiano (\times)

O produto cartesiano combina cada tupla de R com cada tupla de S, concatenando seus atributos. Se R tem cardinalidade |R| e grau n, e S tem |S| e grau m, então R \times S tem cardinalidade |R| \times |S| e grau n + m:

R \times S = \{\, t \cdot u \mid t \in R \;\wedge\; u \in S \,\}

Diferente dos três anteriores, o produto cartesiano não exige compatibilidade de união — pelo contrário, ele costuma ser usado justamente para combinar relações de esquemas distintos. Sozinho ele raramente é útil (o resultado é uma explosão combinatória sem sentido semântico), mas ele é a fundação sobre a qual todas as junções são construídas.

SELECT * FROM Empregados CROSS JOIN Departamentos;

Junções

Aqui mora o coração prático da álgebra relacional. A junção combina tuplas relacionadas de duas relações segundo uma condição, e é, conceitualmente, um produto cartesiano seguido de uma seleção. Vou te mostrar toda a família.

flowchart TD
    PC[Produto cartesiano] --> TJ[Theta-juncao: seleciona pares por condicao]
    TJ --> EQ[Equijuncao: condicao so com igualdade]
    EQ --> NAT[Juncao natural: igualdade nos atributos homonimos, sem duplicar colunas]
    TJ --> OUT[Juncoes externas: preservam nao correspondidos]
    OUT --> LE[Externa esquerda]
    OUT --> RI[Externa direita]
    OUT --> FU[Externa completa]
    NAT --> SEMI[Semijuncao: filtra sem trazer colunas do outro lado]
    NAT --> ANTI[Antijuncao: o complemento da semijuncao]

Theta-junção (\bowtie_\theta)

A junção theta é a forma mais geral. Ela é definida exatamente como um produto cartesiano filtrado por uma condição arbitrária \theta:

R \bowtie_{\theta} S = \sigma_{\theta}(R \times S)

Por exemplo, juntando pedidos a clientes pelo identificador comum:

\text{Pedidos} \bowtie_{\text{Pedidos.ClienteID} = \text{Clientes.ClienteID}} \text{Clientes}

SELECT *
FROM Pedidos P
JOIN Clientes C ON P.ClienteID = C.ClienteID;

Equijunção

A equijunção é simplesmente o caso particular da theta-junção em que \theta usa apenas o operador de igualdade. O exemplo acima já é uma equijunção, pois a condição é uma igualdade. A distinção importa porque há algoritmos de execução (hash join, sort-merge join) que só funcionam — ou funcionam muito melhor — quando a condição é de igualdade. Numa theta-junção com < ou >, o motor frequentemente cai num nested loop, bem mais caro.

Junção natural (\bowtie)

A junção natural é uma equijunção automática sobre todos os atributos de mesmo nome nas duas relações, com a particularidade de que as colunas duplicadas são eliminadas no resultado (aparecem uma única vez). Sejam C os atributos comuns a R e S:

R \bowtie S = \pi_{\,\text{esquema}(R)\,\cup\,\text{esquema}(S)}\big(\sigma_{R.C = S.C}(R \times S)\big)

Com Empregados e Departamentos compartilhando DeptID:

ID	Nome	Idade	Salario	DeptID	NomeDept
1	Ana	28	4000	10	Vendas
2	Bruno	35	6200	10	Vendas
3	Carla	42	7500	20	Engenharia

SELECT * FROM Empregados NATURAL JOIN Departamentos;

Cuidado prático: a junção natural é elegante na teoria, mas perigosa na prática, porque ela junta por qualquer coluna homônima. Se duas tabelas tiverem por acaso uma coluna criado_em, a NATURAL JOIN vai casar também por ela, gerando resultados errados e silenciosos. Por isso, no mundo real, prefere-se a equijunção explícita com JOIN ... ON ou USING. Repare que o Diego, sem departamento (DeptID = NULL), desapareceu do resultado — toda junção interna descarta os não correspondidos.

Junções externas

As junções externas resolvem exatamente esse desaparecimento: elas preservam as tuplas sem correspondência, preenchendo com \textsf{NULL} os atributos do lado faltante. Há três variantes.

A junção externa à esquerda (R \bowtie_{\text{E}} S) preserva todas as tuplas de R:

ID	Nome	DeptID	NomeDept
1	Ana	10	Vendas
2	Bruno	10	Vendas
3	Carla	20	Engenharia
4	Diego	NULL	NULL

SELECT E.ID, E.Nome, E.DeptID, D.NomeDept
FROM Empregados E
LEFT OUTER JOIN Departamentos D ON E.DeptID = D.DeptID;

A junção externa à direita (R \bowtie_{\text{D}} S) faz o simétrico: preserva todas as tuplas de S. Suponha que exista um departamento 30 - Marketing sem nenhum empregado; ele apareceria com NULL nas colunas de empregado:

SELECT E.Nome, D.DeptID, D.NomeDept
FROM Empregados E
RIGHT OUTER JOIN Departamentos D ON E.DeptID = D.DeptID;

A junção externa completa (R \bowtie_{\text{C}} S) preserva os não correspondidos de ambos os lados — tanto o Diego sem departamento quanto o Marketing sem empregados entrariam no resultado:

SELECT E.Nome, D.NomeDept
FROM Empregados E
FULL OUTER JOIN Departamentos D ON E.DeptID = D.DeptID;

Vale uma relação útil para memorizar: a junção interna é sempre um subconjunto da externa, e a completa é a “união” das três visões. Formalmente, R \bowtie S = (R \bowtie_{\text{E}} S) restrita às tuplas sem \textsf{NULL} introduzido.

Semijunção (\ltimes) e antijunção (\triangleright)

A semijunção devolve as tuplas de R que têm correspondência em S, mas sem trazer as colunas de S. É um filtro de existência:

R \ltimes S = \pi_{\,\text{esquema}(R)}(R \bowtie S)

SELECT *
FROM Empregados E
WHERE EXISTS (
    SELECT 1 FROM Departamentos D WHERE D.DeptID = E.DeptID
);

A antijunção é o complemento exato: devolve as tuplas de R que não têm correspondência em S:

R \triangleright S = R - (R \ltimes S)

SELECT *
FROM Empregados E
WHERE NOT EXISTS (
    SELECT 1 FROM Departamentos D WHERE D.DeptID = E.DeptID
);

A antijunção traz justamente o Diego, o empregado órfão de departamento. Semijunção e antijunção são operadores que o otimizador adora, porque permitem responder perguntas de existência sem materializar a junção completa — um ganho de desempenho real em consultas com EXISTS e NOT EXISTS.

Divisão (\div)

A divisão é o operador mais sofisticado e, não por acaso, o mais cobrado em questões difíceis. Ela responde a perguntas do tipo “todos”: quais elementos de uma relação estão associados a todos os elementos de outra? É a operação inversa do produto cartesiano. Sejam R com esquema \{A, B\} e S com esquema \{B\}:

R \div S = \{\, t[A] \mid t \in R \;\wedge\; \forall s \in S,\; (t[A], s) \in R \,\}

Em palavras: R \div S contém os valores de A que aparecem em R emparelhados com cada valor de B presente em S. Considere Habilidades(EmpID, Habilidade) e queremos os empregados que dominam todas as habilidades exigidas por um projeto. Com a relação de requisitos S = \pi_{\text{Habilidade}}(\sigma_{\text{Projeto} = \text{'X'}}(\text{Requisitos})):

\pi_{\text{EmpID},\,\text{Habilidade}}(\text{Habilidades}) \div S

EmpID	Habilidade
1	SQL
1	Python
2	SQL

Dividindo por S = \{\text{SQL}, \text{Python}\}, só o empregado 1 sobrevive, pois só ele tem as duas habilidades.

SELECT DISTINCT h.EmpID
FROM Habilidades h
WHERE NOT EXISTS (
    SELECT s.Habilidade
    FROM Requisitos s
    WHERE s.Projeto = 'X'
    AND NOT EXISTS (
        SELECT 1 FROM Habilidades h2
        WHERE h2.EmpID = h.EmpID
        AND h2.Habilidade = s.Habilidade
    )
);

O padrão clássico: não existe DIVIDE em SQL. A divisão se traduz pelo idioma do duplo NOT EXISTS — “não há nenhuma habilidade exigida que esse empregado não possua”. Memorize esse padrão; ele é a tradução canônica de “para todos” em SQL, que internamente só tem quantificador existencial.

Agrupamento e agregação (\gamma)

A álgebra relacional original de Codd não tinha agregação — é uma das limitações que veremos adiante. A álgebra relacional estendida introduziu o operador de agrupamento, geralmente denotado por \gamma (ou \mathcal{G}). Ele particiona a relação por valores de atributos de agrupamento e aplica funções agregadas (SUM, AVG, COUNT, MAX, MIN) a cada grupo:

_{G_1, \dots, G_k}\,\gamma\,_{F_1(A_1), \dots, F_m(A_m)}(R)

onde G_i são os atributos de agrupamento e F_j(A_j) são as funções agregadas. Para o salário médio por departamento:

_{\text{DeptID}}\,\gamma\,_{\text{AVG}(\text{Salario})}(\text{Empregados})

DeptID	salario_medio
10	5100
20	7500

SELECT DeptID, AVG(Salario) AS salario_medio
FROM Empregados
GROUP BY DeptID;

Os atributos de agrupamento viram o GROUP BY; as funções agregadas viram a lista de seleção. Filtros sobre os próprios agregados, no SQL, vão para o HAVING — algo que, na álgebra estendida, é uma seleção aplicada depois do \gamma.

Construção de expressões, ordem de avaliação e otimização

Como a álgebra é fechada, expressões complexas nascem do aninhamento de operadores. Veja a consulta “nomes dos empregados de TI que ganham mais de 5000”:

\pi_{\text{Nome}}\Big(\sigma_{\text{Salario} > 5000}\big(\text{Empregados} \bowtie \sigma_{\text{NomeDept} = \text{'TI'}}(\text{Departamentos})\big)\Big)

A ordem de avaliação segue regras familiares: parênteses primeiro, depois operadores unários, depois binários, e da esquerda para a direita no mesmo nível. Mas o ponto realmente importante para a prova é que expressões diferentes podem ser equivalentes — produzem o mesmo resultado com custos distintos. É disso que vive o otimizador.

A heurística mais conhecida é o pushdown de seleção (empurrar a seleção para baixo na árvore). Pela equivalência

\sigma_{\theta}(R \bowtie S) \equiv \sigma_{\theta}(R) \bowtie S \quad \text{(quando } \theta \text{ só envolve atributos de } R\text{)},

podemos reescrever

\pi_{\text{Nome}}\big(\sigma_{\text{Salario} > 5000}(\text{Empregados} \bowtie \text{Departamentos})\big)

como

\pi_{\text{Nome}}\big(\sigma_{\text{Salario} > 5000}(\text{Empregados}) \bowtie \text{Departamentos}\big).

A diferença é enorme: na primeira forma, juntamos tudo e só depois filtramos; na segunda, filtramos Empregados antes de juntar, reduzindo drasticamente o tamanho da relação que entra na junção. Junção é cara (muitas vezes O(|R| \cdot |S|) no pior caso); reduzir os operandos antes é o ganho mais barato e mais efetivo que existe.

flowchart TD
    subgraph Antes
        A1[Juncao Empregados x Departamentos] --> A2[Selecao Salario maior que 5000]
        A2 --> A3[Projecao Nome]
    end
    subgraph Depois
        B1[Selecao Salario maior que 5000 em Empregados] --> B2[Juncao com Departamentos]
        B2 --> B3[Projecao Nome]
    end

As equivalências mais úteis que você deve carregar para a prova são: comutatividade e associatividade da junção (R \bowtie S \equiv S \bowtie R e (R \bowtie S) \bowtie T \equiv R \bowtie (S \bowtie T)), que permitem reordenar a ordem das junções; o pushdown de seleção; e a projeção antecipada, que descarta colunas inúteis cedo para encolher tuplas intermediárias. O otimizador real considera o espaço de planos equivalentes, estima custos com base em estatísticas (cardinalidades, índices) e escolhe o mais barato — exatamente o trabalho descrito naquele diagrama de fluxo lá do início.

Operador algébrico	Construção SQL equivalente
\sigma_{\theta}(R)	SELECT * FROM R WHERE θ
\pi_{A}(R)	SELECT DISTINCT A FROM R
\rho_{S}(R)	... FROM R AS S
R \cup S	R UNION S
R \cap S	R INTERSECT S
R - S	R EXCEPT S
R \times S	R CROSS JOIN S
R \bowtie_\theta S	R JOIN S ON θ
R \bowtie S	R NATURAL JOIN S
R \bowtie_{\text{E}} S	R LEFT OUTER JOIN S
R \ltimes S	WHERE EXISTS (...)
R \triangleright S	WHERE NOT EXISTS (...)
R \div S	duplo NOT EXISTS
\gamma	GROUP BY com agregadas

Limitações que justificam o SQL

Para fechar o raciocínio, vale entender por que o SQL precisou ir além da álgebra de Codd. A álgebra relacional pura não é Turing-completa: ela não exprime consultas recursivas (como o fecho transitivo de uma hierarquia de funcionários), o que o SQL resolve com WITH RECURSIVE. Ela também não tinha agregação nem ordenação nativas — daí a álgebra estendida com \gamma e o ORDER BY do SQL, que, aliás, é uma operação que sai do mundo dos conjuntos, pois introduz ordem onde a relação não tinha. Reconhecer essas fronteiras é o que mostra à banca que você entende a álgebra como modelo, e não como dogma.

Síntese para a prova. A álgebra relacional é a base procedural sobre a qual o SQL é traduzido e otimizado, e seu pilar é a propriedade de fechamento: operador entra com relação, sai com relação. Os seis operadores primitivos são seleção, projeção, união, diferença, produto cartesiano e renomeação; interseção, junções e divisão são todos derivados. Fixe que a seleção (\sigma) é recorte horizontal e vira WHERE; a projeção (\pi) é recorte vertical e vira SELECT DISTINCT, porque a álgebra é de conjuntos e elimina duplicatas, enquanto o SQL é de multiconjuntos. União, diferença e interseção exigem compatibilidade de união, e a diferença não comuta. A junção é um produto cartesiano com seleção: a theta é geral, a equijunção usa só igualdade, a natural casa atributos homônimos eliminando colunas repetidas (e descarta não correspondidos), e as externas — esquerda, direita, completa — preservam os não correspondidos com \textsf{NULL}. Semijunção e antijunção filtram por existência ou ausência sem trazer colunas do outro lado, traduzindo-se em EXISTS e NOT EXISTS. A divisão responde a perguntas de “para todos” e se escreve em SQL com o idioma do duplo NOT EXISTS. O agrupamento (\gamma) da álgebra estendida vira GROUP BY com funções agregadas. E o ouro da otimização está nas equivalências: empurre a seleção para baixo antes das junções, projete cedo e reordene junções, sempre reduzindo os resultados intermediários. Saber justificar por que duas expressões são equivalentes, e qual delas o otimizador prefere, é o que costuma decidir as questões mais difíceis.