bacharel
FACULDADE DE ENGENHARIA
DEPARTAMENTO DE ENGENHARIA DE SISTEMAS E COMPUTAÇÃO
ENGENHARIA DE SISTEMAS B
ÁLGEBRA RELACIONAL
Lista de Exercícios
A.
Considere as seguintes relações:
R1 (A:Dom1; B:Dom2; C:Dom3)
R2 (D:Dom3; E:Dom4)
R3 (F: Dom4)
R4 (G:Dom3; H:Dom4)
onde A, B, C, D, E, F, G e H representam atributos e Domi representa os domínios de valores desses atributos. Suponha, ainda, que R1, R2, R3 e R4 possuam 100, 50, 25 e
10 tuplas, respectivamente. Calcule o máximo e o mínimo de tuplas na relação resultante de cada uma das seguintes expressões da Álgebra Relacional:
1.
E1 R1 |X| R2
(equi-join)
C=D
Considerando que:
a operação de junção é equivalente a uma operação de seleção sobre o produto cartesiano das tabelas operandas;
o número de tuplas gerado pelo produto cartesiano é igual ao produto do número de tuplas das tabelas operandas;
no caso dos operandos R1 e R2 esse número é igual a 5.000 tuplas
(100 x 50).
Temos que:
no máximo, a condição (C = D) será válida para todas as 5.000 tuplas do produto cartesiano;
no mínimo, nenhuma tupla do produto cartesiano atenderá a condição
(C = D).
Logo, max(E1) = 5.000 e min(E1) = 0
2.
E2 E1 |X| R3
(equi-join)
E=F
Da mesma forma, considerando que:
a relação E1 possui no mínimo zero e no máximo 5.000 tuplas; e
a relação E3 possui 25 tuplas;
Temos que:
o produto cartesiano de E1 por R3 terá no máximo 125.000 tuplas
(i.e. 5000*25);
a condição de seleção (E = F) será válida no máximo para todas essas tuplas e no mínimo para nenhuma delas.
Logo, max(E2) = 125.000 e min(E2) = 0
3.
E3 R3 R4
(união)
Considerando que R3 e R4 possuem 25 e 10 tuplas, respectivamente, temos que:
o máximo de tuplas de E3 ocorrerá quando R3 e R4 forem disjuntas, isto é, quando não possuírem tuplas em comum. Neste caso, o número de tuplas da união será igual à soma do número de tuplas nas duas relações (35);
o mínimo de tuplas de E3 ocorrerá