bacharel

UERJ
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á