Aula06-Álgebra Relacional

Álgebra Relacional
Os arquivos baseados no modelo relacional são manipulados através de operadores
relacionais. Tais operadores são componentes da álgebra relacional. A execução de cada
um desses operadores, produz uma relação.
A Álgebra relacional compõe-se basicamente de oito operadores distribuídos entre:
Fundamentais:
• Unários: Seleção, Projeção
• Binários: Produto Cartesiano, União e Diferença
Derivados:
• Binários: Intersecção, Junção e Divisão
Especiais:
• Renomeação (unário) e Atribuição
Operador de Alteração (unário)
Podemos considerar como sendo operadores unários, aqueles que operam em uma única
relação. Já os operadores binários, operam em pares de relações. Abaixo, uma breve
descrição de cada um destes operadores:
1. Seleção
Seleciona tuplas que satisfaçam um determinado predicado. É representado pela letra
Sigma (σ).
σ nome_agencia = “Perryride” (Emprestimo)
Agencia Emprestimo
Perryde L_15 Perryde L_16 Total 1500 1600 Figura1. Resultado de σ nome_agencia = “Perryride” (Emprestimo)
Selecionando todas as tuplas cujos totais são superiores a 1200.
σ total > 1200 (Empréstimo)
Predicados:
= (Igual)
≠ (Diferente)
< (Menor que)
≤ (Menor ou igual que)
> (Maior que)
≥ (Maior ou igual que)
^ (e)
V (Ou)
Tuplas que contenham empréstimos acima de 1200, feitos na agência Perriryde.
σ nome_agencia = “Perryride” ^ total > 1200 (Emprestimo)
Prof. Antonio Almeida de Barros Júnior
Pág. 1
2. Projeção
A operação Projecti é primária e retorna o argumento da relação, deixando de lado certos
atributos. É denotada pela letra Pi (π).
π numero_emprestimo, total (Emprestimo)
Emprestimo
L_17 L_15 L_16 ... Total 1500 1600 1200 ... Figura 2. Número do empréstimo e total do empréstimo.
A Operação Relacional de Comparação
Consideramos a consulta: “encontre os clientes que moram em “Harrison””.
π nome_cliente (σ cidade_cliente = “Harrison” (Cliente))
Desde que o resultado de uma operação em álgebra relacional seja do mesmo tipo que
sua entrada (relação), as operações em álgebra relacional podem ser compostas juntas em
uma expressão em álgebra relacional. Tais composições são similares às operações
aritméticas (como +, -, *, e ÷).
3. Produto
A operação Produto Cartesiano, representada por (x), permite-nos combinar informações
de duas relações quaisquer. Representamos o produto das relações r1 e r2 pro r1 x r2.
Neste contexto, é importante o uso de “alias” nos nomes de tabelas e ou campos. O
esquema de relação para r = devedor x empréstimo é:
(Devedor.Nome_Cliente, Devedor.Numero_Emprestimo, Emprestimo.Nome_Agencia,
Emprestimo.Numero_Emprestimo, Emprestimo.Total)
ou
(Nome_Cliente, Devedor.NumeroEmprestimo, Nome_Agencia,
Emprestimo.Numero_Emprestimo, Total)
Devedor. Nome_Cliente NumeroEmprestimo Adams L_16 Adams L_16 Curry L_93 ... ... Nome_Agencia L_11 L_14 L_11
... Emprestimo. Numero_Emprestimo Round Hill Downtown Round Hill
... Total 900 1500 900
... Figura 7. Resultado Devedor x Emprestimo.
Prof. Antonio Almeida de Barros Júnior
Pág. 2
Desta forma, podemos ter n1 tuplas em Devedor e n2 tuplas em Emprestimo. Então
existem n1 x n2 modos de escolher um par de tuplas – uma tupla de cada relação, assim
há n1 x n2 tuplas em r. Nota-se que podemos ter:
t[Devedor.Numero_Emprestimo] ≠ t[Emprestimo.Numero_Emprestimo].
No geral este tipo de relação e a concatenação de r1 com r2.
Resultado:
Uma relação com tuplas obtidas através da concatenação de cada tupla da relação A com
cada tupla da relação B.
4. União
Considere uma consulta para encontrar os nomes de todos os clientes do banco que
tenham uma conta, um empréstimo ou ambos. Note que a relação cliente não possui esta
informação, já que o cliente não precisa ter nem uma conta nem um empréstimo no
banco. Para responder esta consulta, precisamos das informações na relação Depositante
e na relação Devedor.
Nome_Cliente Numero_Conta
Hayes A‐102 Johnson A‐101 Johnson A‐201 Jones A‐217 Lindsay A‐222 Smith A‐215 Turner A‐305 Nome_Cliente Numero_Emprestimo Adams L_16 Curry L_93 Hayes L_15 Jackson L_14 Jones L_17 Smith L_11 Smith L_23 Willians L_17 Figura3. Relações Depositante e Devedor
π nome_cliente (Devedor)
π nome_cliente (Depositante)
π nome_cliente (Devedor) ∪ π nome_cliente (Depositante)
Prof. Antonio Almeida de Barros Júnior
Pág. 3
A relação resultante dessa consulta aparece na figura 4.
Nome_Cliente
Adams Curry Hayes Jackson Jones Smith Willians Lindsay Johnson Turner Figura 4. Nomes de todos os clientes que têm um empréstimo ou uma conta.
OBS: Para realizar a operação de união, é importante que as relações envolvidas
contenham a mesma estrutura.
Resultado:
Uma única relação com a mesma estrutura das relações originais, composta de todas as
tuplas da relação A e da relação B.
5. Diferença
A operação Diferença entre conjuntos denotada por -, permite-nos encontrar as tuplas que
estão em uma relação, mas não em outra. A expressão r-s resulta na relação que contém
as tuplas que estão em r, mas não em s.
Podemos encontrar todos os clientes do banco que possuem contas mas não adquiriram
empréstimos escrevendo:
π nome_cliente (Depositante) - π nome_cliente (Devedor)
Nome_Cliente
Johnson Lindsay Turner Figura 6. Clientes com contas, mas sem empréstimos.
Prof. Antonio Almeida de Barros Júnior
Pág. 4
Resultado:
Uma relação com a mesma estrutura das relações originais, composta de tuplas
pertencentes à relação A e não pertencentes à relação B.
6. Interseção
A primeira operação adicional em álgebra relacional que podemos definir é a interseção
de conjuntos (∩). Suponha que queiramos encontrar todos os clientes que tenham tanto
empréstimo quanto conta.
π nome_cliente (Devedor) ∩ π nome_cliente (Depositante)
Nome_Cliente
Hayes Jones Smith
Figura 5. Clientes com conta e empréstimo no banco.
OBS: Podemos reescrever qualquer expressão em álgebra relacional usando a interseção
de conjuntos por meio de aplicação de um par de operações de diferença de conjuntos.
Para realizar a operação de intersecção, é importante que as relações envolvidas
contenham a mesma estrutura.
r ∩ s = r – (r – s)
Resultado:
Uma única relação com a mesma estrutura das relações originais, composta de tuplas
coincidentes da relação A e da relação B.
Prof. Antonio Almeida de Barros Júnior
Pág. 5
7. Junção
Tipicamente, uma consulta em Produto Cartesiano envolve uma seleção de operações
sobre o resultado desse Produto Cartesiano. Considere a consulta “Encontrar todos os
nomes dos clientes que contenham um empréstimo no banco e encontrar o total
emprestado”.
π Nome_Cliente, Emprestimo.Numero_Emprestimo, Total
(σ Devedor.Numero_Emprestimo = Emprestimo.NumeroEmprestimo (Devedor x
Emprestimo))
A Junção é representada pelo símbolo de “Join” >< . Trata-se de uma operação de
Produto Cartesiano, onde a Seleção obedece a equivalência dos atributos que aparecem e
mambas relações. Vejamos o exemplo anterior:
π Nome_Cliente, Numero_Emprestimo, Total (Devedor >< Emprestimo)
Consideramos duas relações r(R) e s(S). A junção de R e S denotada por R >< S, é uma
relação no esquema R ∪ S formalmente definida como:
r >< s = π R ∩ S (σ r.A1=s.A1 ^ r.A2=s.A2 … r.An=s.An r x s)
em que R ∩ S = {A1, A2, …, An}
Exemplos:
Encontrar os nomes de todas as agências com clients que tenham contas no banco e
morem em “Muriaé”.
π Nome_Agencia (σ Cidade_Cliente = “Muriaé” (Cliente >< Conta >< Depositante))
Encontrar todos os clients que tenham empréstimo e conta no banco.
π Nome_Cliente (Devedor >< Depositante)
Suponha que queiramos encontrar os nomes de todos os clientes que tenham um
empréstimo na agência de “Muriaé”. Podemos precisar, para isso de informações das
relações Devedor e Emprestimo. Se escrevermos:
σ Nome_Agencia = “Muriaé” (Devedor x Emprestimo)
Como operação Produto Cartesiano associa todas as tuplas de Emprestimo a todas as
tuplas de Devedor, sabemos que se um Cliente contrair um empréstimo na agência
“Muriaé”, então existe algumas tuplas em Devedor x Emprestimo que contém o seu
nome.
σ Devedor.Numero_Emprestimo = Emprestimo.Numero_Emprestimo (σ Nome_Agencia
= “Muriaé” (Devedor x Emprestimo))
Prof. Antonio Almeida de Barros Júnior
Pág. 6
A consulta pega apenas as tuplas de Devedor x Emprestimo que pertençam aos que
tenham um empréstimo na agência de “Muriaé”.
Uma vez que queiramos apenas o nome do cliente, podemos fazer uma projeção:
π Nome_Cliente (σ Devedor.Numero_Emprestimo = Emprestimo.Numero_Emprestimo)
(σ Nome_Agencia = “Muriaé” (Devedor x Emprestimo))
8. Divisão
Indicada por ÷, é apropriada para consultas que incluem a frase “para todo”. Suponha que
desejamos encontrar todos os clientes que têm uma conta em todas as agências
localizadas em “Viçosa” pela expressão:
r1 = π Nome_Agencia (σ Cidade_Agencia = “Viçosa” (Agencia))
Para encontar todos os pares (Nome_Cliente, Nome_Agencia) para os quais o cliente tem
conta.
r2 = π Nome_Cliente, Nome_Agencia (Depositante >< Conta)
Agora, precisamos encontrar Clientes que aparecem em r2 com cada nome da agencia em
r1. Para isso, façamos a divisão: π Nome_Cliente, Nome_Agencia (Depositante ><
Conta) ÷ π Nome_Agencia (σ Cidade_Agencia = “Viçosa” (Agencia))
Formalmente, sejam r(R) e s(S) relações, e SR; ou seja, cada atributo do esquema S
também está no esquema R. A relação r÷s é uma relação no esquema R – S. Para isso, as
seguintes condições devem ser satisfeitas:
1. T está em π R-S (r)
2. Para cada tupla ts em s, existe uma tupla TR em r satisfazendo estas duas
condições:
a. tr [S] = ts[S]
b. tr[R-S] = t
Prof. Antonio Almeida de Barros Júnior
Pág. 7
9. Renomeação
De modo diferente das relações no banco de dados, os resultados das expressões de
álgebra relacional não possuem um nome para referenciá-las. É útil poder atribuir-lhes
nomes; o operador renomeação, indicado pela letra grega minúscula ro (ρ), nos permite
fazer isso. Considerando uma expressão de álgebra relacional E, a expressão:
ρx (E)
retorna o resultado da expressão E sob o nome x.
Para ilustrar a renomeação de uma relação, consideramos a consulta “Encontre o maior
saldo no banco”. Nossa estratégia é (1) calcular primeiro uma relação temporária
consistindo nos saldos que não sejam o maior e (2) tomar a diferença de conjuntos entre a
relação πSaldo (Conta) e a relação temporária recém-calculada, para obter o resultado.
Etapa 1: Para calcular a relação temporária, precisamos comparar os valores de todos os
saldos de conta. Fazemos essa comparação calculando o produto cartesiano conta X
conta e formando uma seleção para comparar o valor de quaisquer dois saldos
aparecendo em uma tupla. Primeiro precisamos criar um mecanismo para distinguir entre
dois atributos saldo. Usaremos a operação renomeação para renomear uma referência à
relação conta; portanto, podemos referenciar a relação duas vezes sem ambigüidade.
πConta.Saldo (σ Conta.Saldo < d.Saldo (Conta x ρd (Conta)))
Essa expressão fornece os saldos na relação conta para os quais um saldo maior aparece
em algum lugar na relação conta (renomeada como d). O resultado contém todos os
saldos exceto o maior. A figura abaixo, mostra esta relação.
Saldo 500 400 700 750 350 Figura 7. Resultado da subexpressão
πConta.Saldo (σ Conta.Saldo < d.Saldo (Conta × ρd (Conta))).
A consulta para encontrar o maior saldo no banco pode ser escrita como:
πConta.Saldo (Conta) - πConta.Saldo (σ Conta.Saldo < d.Saldo (Conta × ρd (Conta)))
Prof. Antonio Almeida de Barros Júnior
Pág. 8
A figura 8 mostra o resultado dessa consulta.
Saldo 900 Figura 8. Maior saldo do banco.
10. Atribuição
Algumas vezes é conveniente escrever uma expressão de álgebra relacional atribuindo
partes dela a variáveis de relação temporárias. A operação atribuição, indicada por ←,
age como a atribuição em uma linguagem de programação. Para ilustrar essa operação,
considere a definição de divisão na seção “A operação divisão”. Poderíamos escrever r ÷
s como
temp1 ← πR – S (r)
temp2 ← πR – S ((temp1 × s) - πR – S,S (r))
temp2 ← temp1 - temp2
Com a operação atribuição, uma consulta pode ser escrita como um programa seqüencial
consistindo em uma série de atribuições seguida de uma expressão cujo valor é exibido
como o resultado da consulta.
Prof. Antonio Almeida de Barros Júnior
Pág. 9
Relações
Agencia
Nome_Agencia
Cidade_Agencia
Ativo
Conta
Número_Conta
Nome_Agencia
Saldo
Emprestimo
Numero_Emprestimo
Nome_Agencia
Valor
Devedor
Nome_Cliente
Numero_Emprestimo
Conta Numero_Conta Nome_Agencia Cliente
Nome_Cliente
Rua_Cliente
Cidade_Cliente
Depositante
Nome_Cliente
Numero_Conta
Agencia Saldo Nome_Agencia Cidade_Agencia Ativo A‐101 Downtown 500
Brighton Brooklyn 7,100,000.00
A‐102 Perryridge 400
Downtown
Brooklyn
9,000,000.00
A‐201 Brighton 900
Mianus Horseneck A‐215 Mianus 700
North Town Rye 3,700,000.00
A‐217 Brighton 750
Perryridge Horseneck 1,700,000.00
A‐222 Redwood 700
Pownal Bennigton 3,000,000.00
A‐305 Round Hill 350
Redwood Palo Alto 2,100,000.00
Round Hill Horseneck 8,000,000.00
Emprestimo Numero_Emprestimo Nome_Agencia 400,000.00
Cliente Quantia Nome_Cliente Rua_Cliente Cidade_Cliente L_11 Round Hill 900
Smith
Spring
Pittsfield L_11 Downtown 1500
Brooks
Senator
Brooklyn L_15 Perryridge 1500
Curry North Rye L_16 Perryridge 1300
Glenn Sand Hill Woodside L_17 Downtown 1000
Green Walnut Stamford L_23 Redwood 2000
Hayes Main Harrison L_93 Mianus Johnson Alma Harrison Johnson Main Harrison Lindsay Park Pittsfield Smith North Rye Turner
Putnam
Stamford Williams Nassau 500
Prof. Antonio Almeida de Barros Júnior
Princeton Pág. 10
Depositante Nome_Cliente Devedor Numero_Conta Nome_Cliente Numero_Emprestimo Hayes A‐102 Adams L_16 Johnson A‐101 Curry L_93 Johnson A‐201 Hayes
L_15 Jones A‐207 Jackson
L_14 Lindsay A‐222 Jones L_17 Smith A‐215 Smith L_11 A‐305 Smith L_23 Williams L_17 Turner Referências
a
Silberschatz, A. et al. Sistema de Banco de Dados. Tradução da 5 edição.
Editora Campus. São Paulo. 2006.
Prof. Antonio Almeida de Barros Júnior
Pág. 11