Álgebra relacional

Regras de conjuntos

A álgebra clássica usa conjuntos: sem duplicados e sem ordem de tuplos. Cada operador recebe relações e devolve uma relação.

Operador	Condição e efeito
Seleção $\sigma_p(R)$	Conserva os tuplos que satisfazem $p$. Não escolhe colunas.
Projeção $\pi_X(R)$	Conserva os atributos $X$. Elimina tuplos repetidos.
Produto $R\times S$	Combina todos os pares; $m$ e $n$ tuplos dão $mn$. Exige nomes desambiguados.
Renomeação $\rho$	Muda nomes de relação ou atributos, sem mudar valores. Explicita a convenção usada.
União $R\cup S$	Tuplos de pelo menos um lado. Esquemas compatíveis.
Interseção $R\cap S$	Tuplos dos dois lados. Vale $R-(R-S)$.
Diferença $R-S$	Tuplos de $R$ ausentes de $S$. Não é comutativa.

A projeção generalizada admite expressões com nomes novos, como preço em euros a partir de cêntimos; a clássica só escolhe atributos existentes. Em SQL, reproduzir a semântica de conjuntos exige DISTINCT.

Que junção usar

• A teta-junção $R\bowtie_p S$ equivale a filtrar o produto: $\sigma_p(R\times S)$. A equijunção compara por igualdade.
• A natural $R\bowtie S$ iguala todos os nomes comuns e conserva uma cópia de cada um. Sem nomes comuns, é o produto cartesiano.
• A semijunção $R\ltimes S$ conserva os tuplos de $R$ com alguma correspondência, sem trazer colunas de $S$.

Cliente(id, ...) com Encomenda(id, ..., idCliente) não se liga naturalmente pelo cliente: o nome comum id compara um cliente com uma encomenda. Liga por Cliente.id = Encomenda.idCliente ou renomeia antes da junção natural.

A agregação $\gamma$ é uma extensão: $\gamma_{idCliente;\,\operatorname{count}(*)\to n}(Encomenda)$ conta encomendas por cliente, mas não cria grupo para Mia, sem encomendas. Para incluir zeros, parte do universo Cliente com junção externa.

Ausências e universais

Para quem nunca comprou, parte de todos os candidatos e retira os que aparecem:

$$Todos=\pi_{id}(Cliente),\quad Compradores=\rho(\pi_{idCliente}(Encomenda)),\quad SemCompra=Todos-Compradores.$$

Renomeia antes da diferença para compatibilizar esquemas. Filtrar só encomendas nunca encontra quem não existe nelas.

Para $R(X,Y)$ e requisitos $S(Y)$, a divisão devolve os $X$ ligados a todos os $Y$:

$$C=\pi_X(R),\qquad F=(C\times S)-R,\qquad R\div S=C-\pi_X(F).$$

$F$ lista os pares em falta. Com compras $(1,10),(1,11),(2,11)$ e requisitos $10,11$, só falta $(2,10)$; a resposta é $\{1\}$. Se $S$ estiver vazio, devolve $\pi_X(R)$; para outro universo de candidatos, declara-o. “Comprou algo diferente de rato” aceita quem também comprou rato; “nunca comprou rato” exige a diferença.

Reescrever sem partir

$\sigma_{p\land q}(R)=\sigma_p(\sigma_q(R))$. Antecipa um filtro que só usa um lado antes da junção; ao antecipar projeções, conserva os atributos da condição e da resposta.

Contraexemplo: com $R(A,B)=\{(3,4)\}$ e $S(B,C)=\{(1,2)\}$, a junção por $B$ dá vazio, mas $\pi_{A,C}(\pi_A(R)\times\sigma_{B=1}(S))$ devolve $(3,2)$. A projeção apagou $B$ antes de exigir a condição.

Estas equivalências orientam um otimizador, não fixam o plano físico. Com NULL ou junções externas, não apliques automaticamente as identidades da álgebra clássica.

Construção da divisão.