Álgebra relacional

Para saber quem comprou em 5 de janeiro, filtramos Encomenda pela data. Depois ligamos o resultado a Cliente e escolhemos os atributos da resposta.

A álgebra relacional compõe essas operações. Cada uma recebe relações e devolve uma relação. Usamos aqui a álgebra clássica, com conjuntos, sem duplicados e sem ordem de tuplos.

Os operadores essenciais

A seleção $\sigma_p(R)$ conserva os tuplos de R que satisfazem o predicado p. $\sigma_{precoCentimos>3000}(Produto)$ conserva Teclado e Monitor, com todos os seus atributos. A seleção não escolhe colunas.

A projeção $\pi_X(R)$ conserva os atributos X e elimina tuplos repetidos. Se dois produtos distintos se chamarem Rato, $\pi_{nome}(Produto)$ contém Rato uma vez. Uma projeção SQL precisa de DISTINCT para reproduzir essa semântica de conjuntos.

O produto cartesiano $R\times S$ combina cada tuplo de R com cada tuplo de S. Se houver m e n tuplos, o resultado tem $m n$ tuplos, assumindo nomes de atributos desambiguados. Se uma relação estiver vazia, o produto está vazio.

A projeção clássica só escolhe atributos existentes. A projeção generalizada admite também expressões calculadas e nomes novos, como no exemplo seguinte:

$$\pi_{nome, precoCentimos/100.0\to euros}(Produto)$$

É a forma algébrica da lista de SELECT em SQL: cada coluna da resposta indica a expressão e o nome.

A renomeação $\rho$ altera o nome de uma relação ou dos seus atributos, conservando os valores. Escrevemos, por exemplo, $\rho_{C(idCliente,nome,email)}(Cliente)$.

A ordem indicada corresponde à dos atributos na notação do esquema original. Outras convenções de renomeação são possíveis. Explicita a usada.

Na demonstração, a seleção usa preço ≥ limite, com preços em euros. Acrescentámos um segundo produto chamado Rato, de id 13 e preço 30, para observar duplicados. Com limite 30, vê os ids 10, 12 e 13; baixa para 25 e projeta o nome. Entram quatro produtos, mas a projeção só tem três tuplos porque os dois Ratos dão o mesmo nome.

Junções

A teta-junção $R\bowtie_p S$ equivale a $\sigma_p(R\times S)$. O predicado pode usar igualdade ou outras comparações. Numa equijunção, comparamos atributos por igualdade. Atributos do mesmo nome precisam de qualificação ou renomeação.

A junção natural $R\bowtie S$ impõe igualdade em todos os atributos de nome comum e conserva uma cópia de cada atributo comum.

Se não houver nenhum nome comum, equivale ao produto cartesiano. Se houver vários, todos participam, mesmo que não fossem a ligação que tinhas em mente.

Na loja, Cliente(id,nome,email) e Encomenda(id,data,idCliente) têm id em comum, mas um id de cliente não é um id de encomenda. Uma junção natural compararia estes ids erradamente. Usa a condição Cliente.id = Encomenda.idCliente ou renomeia o id do cliente antes da junção natural.

A junção natural de R(A,B) com S(B,C) liga pelo B. A de R(A,B) com T(C,D) produz todas as combinações, porque não há nomes comuns.

Semijunção e agregação

A semijunção $R\ltimes S$ conserva apenas os tuplos de R com alguma correspondência em S. Não acrescenta as colunas de S. Na álgebra de conjuntos, podemos escrevê-la como $\pi_{atributos(R)}(R\bowtie S)$.

Na loja, a semijunção seguinte dá Ana e Rui, uma vez cada, com os atributos de Cliente:

$$Cliente\ltimes_{Cliente.id=Encomenda.idCliente}Encomenda$$

Mia fica de fora. Ana ter duas encomendas não cria duas cópias da cliente. Em SQL, um EXISTS sobre Cliente exprime este teste; uma junção seguida de projeção sem DISTINCT pode manter repetições.

Contar ou somar exige uma extensão da álgebra clássica. Aqui usamos $\gamma$ para agrupamento e agregação. Os slides também apresentam agregações como uma extensão de $\pi$; identifica sempre a convenção usada.

$$\gamma_{idCliente;\,\operatorname{count}(*)\to n}(Encomenda)$$

Agrupamos pelo cliente e chamamos n à contagem:

idCliente	n
1	2
2	1

Duas encomendas para Ana e uma para Rui. Mia não aparece, porque não há tuplos seus em Encomenda. Para mostrar também clientes com zero, é preciso conservar o universo Cliente, como na junção externa em SQL.

União, diferença e interseção

$R\cup S$ contém os tuplos que estão em pelo menos um lado; $R\cap S$, os que estão nos dois; $R-S$, os que estão em R e não em S. Os esquemas têm de ser compatíveis: mesmos atributos, com domínios correspondentes. Renomeia ou projeta antes da operação se necessário.

A diferença não é comutativa. CompraramTeclado − CompraramRato responde a quem comprou teclado e não rato; trocar os lados muda a pergunta. A condição “há uma compra que não é rato” também é diferente de “não há qualquer compra de rato”.

A interseção pode ser escrita só com diferença: $R\cap S=R-(R-S)$. Estes operadores não somam contagens de duplicados, porque a álgebra clássica usa conjuntos.

Uma pergunta completa

Queremos os nomes dos clientes com encomendas em 5 de janeiro de 2026. Seja C a renomeação de Cliente que muda id para idCliente. Primeiro filtramos Encomenda, depois juntamos pelo atributo comum idCliente e finalmente projetamos nome:

$$E_5=\sigma_{data='2026-01-05'}(Encomenda)$$ $$C=\rho_{C(idCliente,nome,email)}(Cliente)$$ $$Resposta=\pi_{nome}(E_5\bowtie C).$$

Lê a árvore de baixo para cima. A junção recebe as encomendas filtradas e os clientes com o id renomeado.

As tabelas intermédias, com os dados da loja:

$E_5$ tem uma linha:

id	data	idCliente
100	2026-01-05	1

$E_5\bowtie C$ acrescenta os atributos de Cliente, incluindo email:

id	data	idCliente	nome	email
100	2026-01-05	1	Ana	ana@example.test

A projeção final devolve o conjunto com um tuplo, {Ana}. Se Ana tivesse duas encomendas nesse dia, a projeção continuaria a mostrá-la uma vez. Para identificar pessoas, conserva o id.

As folhas da árvore são relações e cada nó interior é um operador. A seleção e a renomeação recebem uma relação cada; a junção recebe duas. Ao transformar a árvore, conserva todas as entradas e as colunas de que os operadores precisam.

Clientes sem encomendas

Não podemos descobrir uma ausência filtrando apenas encomendas existentes. Precisamos do conjunto de candidatos e de retirar os que aparecem:

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

Com os dados da loja, Todos é $\{1,2,3\}$ e Compradores é $\{1,2\}$; a diferença é $\{3\}$. Para obter nome e email, juntamos esse resultado com Cliente. A renomeação tornou os esquemas compatíveis.

Divisão: perguntas com todos

Se $R(X,Y)$ regista pares e $S(Y)$ contém os valores exigidos, $R\div S$ devolve os X que estão ligados a todos os Y de S. O esquema da resposta contém os atributos de R que não estão em S.

Suponhamos Comprou(idCliente,idProduto) com $(1,10),(1,11),(1,12),(2,11)$ e Exigido(idProduto) com 10 e 11. O cliente 1 comprou todos os produtos exigidos; o 2 não comprou o 10. A divisão devolve 1.

Pode ser construída com operadores básicos:

$$Candidatos=\pi_X(R)$$ $$Faltas=(Candidatos\times S)-R$$ $$R\div S=Candidatos-\pi_X(Faltas).$$

O produto enumera pares que deveriam existir. A diferença encontra os que faltam:

Candidato	Produto exigido	Está em Comprou?
1	10	sim
1	11	sim
2	10	não, falta
2	11	sim

Só falta (2,10). Projetar o cliente dessa falta dá {2}. Retirá-lo dos candidatos {1,2} deixa {1}, a resposta. Não basta filtrar compras do produto 10 ou 11: isso também aceitaria o cliente 2, que só cumpriu um dos requisitos.

Se S estiver vazia, não falta nenhum requisito e a divisão devolve $\pi_X(R)$. Repara no universo dos candidatos: um cliente que não aparece em Comprou não pertence à projeção inicial. Se quisermos todos os clientes, incluindo os sem compras quando não há requisitos, usamos Cliente como universo e a mesma ideia de retirar faltas. A divisão em SQL explicita esta escolha.

Equivalências e execução

Podemos separar uma seleção conjuntiva: $\sigma_{p\land q}(R)=\sigma_p(\sigma_q(R))$. Se p só usa atributos de R, podemos aplicar essa seleção antes de juntar R com S. Isso pode reduzir o número de tuplos intermédios sem mudar a resposta.

A projeção também pode reduzir atributos antes de uma junção, mas tem de conservar os usados pela condição e os necessários ao resultado. Se retirarmos idCliente antes de ligar as encomendas aos clientes, perdemos a ligação.

Por exemplo, para $R(A,B)$ e $S(B,C)$:

$$\pi_{A,C}(R\bowtie\sigma_{B=1}(S))= \pi_A(\sigma_{B=1}(R))\times\pi_C(\sigma_{B=1}(S)).$$

À esquerda, a junção obriga também B de R a ser 1. À direita, os dois lados já foram filtrados por esse mesmo valor, por isso todas as combinações concordam em B e podemos retirá-lo antes do produto.

Retirar B de R antes do filtro, usando $\pi_{A,C}(\pi_A(R)\times\sigma_{B=1}(S))$, perde a obrigação. Com $R=\{(3,4)\}$ e $S=\{(1,2)\}$, as expressões corretas devolvem vazio, mas esta última devolve $(3,2)$. Já não existe B do lado de R para comparar. Antecipar a projeção exige conferir filtros além das colunas da junção.

Estas equivalências explicam transformações de um otimizador. Não determinam a ordem física exata que o SGBD seguirá. Junções externas e a lógica de NULL exigem cuidados adicionais; não lhes apliques automaticamente todas as identidades da álgebra clássica.