Lista de AlgRel

Prévia do material em texto

UUEERRJJ 
FFAACCUULLDDAADDEE DDEE EENNGGEENNHHAARRIIAA 
DEPARTAMENTO DE ENGENHARIA DE SISTEMAS E COMPUTAÇÃO 
ENGENHARIA DE SISTEMAS B 
ÁÁLLGGEEBBRRAA RREELLAACCIIOONNAALL 
LLiissttaa ddee EExxeerrccíícciiooss 
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; 
• que o número de tuplas gerado pelo produto cartesiano é igual ao produto do 
número de tuplas das tabelas operandas; 
• que no caso dos operandos R1 e R2 o produto cartesiano produzirá o máximo de 
5.000 tuplas (100*50). 
Temos que: 
• no mínimo, nenhuma tupla do produto cartesiano atenderá à condição (C = D); 
• no máximo, todas as tuplas do produto cartesiano atenderão à essa condição. 
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á quando R4 estiver totalmente contida em R3. 
Nesse caso, o número de tuplas da união será igual ao número de tuplas de R3 
(25). 
Logo, max(E3) = 35 e min(E3) = 25 
4. E4 ���� E1 ||X| R2 (left-join) 
 C = D 
Considerando que: 
• a relação E1 possui no mínimo zero e no máximo 5.000 tuplas; 
• a relação R2 possui 50 tuplas; 
• o produto cartesiano de E1 por R2 terá no máximo 250.000 tuplas (i.e. 5000*50); 
e 
• a junção à esquerda inclui todas as tuplas de E1, incluindo aquelas que não 
satisfazem a condição de seleção (C = D); 
Temos que: 
• o máximo de tuplas em E4 será igual 250.000, quando todas as tuplas do produto 
cartesiano satisfizerem a condição (C = D); 
• o mínimo de tuplas em E4 será igual 5.000, quando nenhuma tupla do produto 
cartesiano satisfizer a condição (C = D). 
Logo, max(E4) = 250.000 e min(E4) = 5.000 
5. E5 ���� E1 |X|| R2 (right-join) 
 C = D 
Considerando que: 
• a relação E1 possui no mínimo zero e no máximo 5.000 tuplas; 
• a relação R2 possui 50 tuplas; 
• o produto cartesiano de E1 por R2 terá no máximo 250.000 tuplas (i.e. 5000*50); 
e 
• a junção à direita inclui todas as tuplas de R2, incluindo aquelas que não 
satisfazem a condição de seleção (C = D); 
Temos que: 
• o máximo de tuplas em E5 será igual 250.000, quando todas as tuplas do produto 
cartesiano satisfizerem a condição (C = D); 
• o mínimo de tuplas em E5 será igual 50, quando nenhuma tupla do produto 
cartesiano satisfizer a condição (C = D). 
Logo, max(E5) = 250.000 e min(E4) = 50 
6. E6 ���� R2 ÷ R4 (divisão) 
Considerando que R2 e R4 possuem o mesmo número de atributos, esta operação é 
inválida, uma vez que a divisão requer que o primeiro operando tenha no mínimo 
um atributo a mais do que o segundo operando. 
7. E7 ���� R2 ÷ R3 (divisão) 
Considerando que a relação R2 possui 50 tuplas e a relação R3 possui 25 tuplas, 
temos que: 
• o máximo de tuplas em E7 será igual 2, quando todas as tuplas de R2 formarem 
um conjunto total de combinações com todas as tuplas de R3. Neste caso, o total 
de tuplas de E7 será igual à divisão do número de tuplas de R2 pelo número de 
tuplas de R3 (i.e. 50/25). 
• o mínimo de tuplas em E7 será igual zero, quando não houver em R2 nenhum 
conjunto de tuplas que represente uma combinação total com todas as tuplas de 
R3. 
Logo, max(E5) = 2 e min(E4) = zero 
B. Dadas duas relações R1 e R2, onde R1 contém n1 tuplas, R2 contém n2 tuplas e 
n2>n1>0, 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. R1 ∪∪∪∪ R2 
Considerando que: 
• R1 e R2 possuem n1 e n2 tuplas, respectivamente; e 
• n2 > n1 > 0; 
Temos que: 
• o máximo de tuplas geradas pela operação de união ocorrerá quando R1 e R2 
forem disjuntas, isto é, quando não possuírem tuplas em comum. Nesse caso, o 
número de tuplas será igual à soma do número de tuplas nas duas relações (n1 + 
n2); 
• o mínimo de tuplas geradas pela operação de união ocorrerá quando R1 estiver 
totalmente contida em R2. Nesse caso, o número de tuplas será igual ao número 
de tuplas de R2 (n2). 
Logo, max(R1 ∪ R2) = n1 + n2 e min(R1 ∪ R2) = n2 
2. R1 ∩∩∩∩ R2 
Da mesma forma: 
• o máximo de tuplas geradas pela operação de interseção ocorrerá quando R1 
estiver totalmente contida em R2. Nesse caso, o número de tuplas será igual ao 
número de tuplas de R1 (n1). 
• o mínimo de tuplas geradas pela operação de interseção ocorrerá quando R1 e R2 
forem disjuntas, isto é, quando não possuírem tuplas em comum. Nesse caso, o 
número de tuplas será igual zero. 
Logo, max(R1 ∩ R2) = n1 e min(R1 ∩ R2) = zero 
3. R1 X R2 
Como a operação de produto cartesiano combina cada tupla do primeiro operando 
com todas as tuplas do segundo operando, sem quaisquer restrições, o número de 
tuplas geradas por essa operação é constante e igual ao produto do número de 
tuplas em ambos os operandos. 
Assim, max(R1 x R2) = min(R1 x R2) = n1 * n2 
4. σσσσa=7 (R1) 
Sabemos que R1 possui 100 tuplas. Se todas elas satisfizerem a condição de seleção 
(a = 7) teremos no máximo 100 tuplas no resultado. Se nenhuma delas satisfizer 
essa condição, teremo no mínimo zero tuplas. 
Assim, max(σ a=7 (R1)) = 100 e min((σ a=7 (R1)) = zero 
5. pipipipia [R1] 
Sabemos que R1 possui 100 tuplas. Se todas elas possuírem o mesmo valor para o 
atributo a, teremos apenas uma tupla no resultado da operação de projeção. Por 
outro lado, se cada tupla de R1 possuir um valor diferente para o atributo a, teremos 
100 tuplas no resultado. 
Assim, max (pia [R1]) = 100 e min (pia [R1]) = 1 
C. Escreva uma expressão que traduza a operação de interseção em termos das 
operações de união e diferença. 
Sabemos que: 
• a operação de união inclui as tuplas de ambas as relações operandas sem 
duplicação; 
• a operação de diferença inclui todas as tuplas do primeiro operando que não estão 
presentes no conjunto de tuplas do segundo operando. 
Assim sendo, se subtrairmos do resultado da união as tuplas que estão em um 
operando mas não estão no outro obteremos as tuplas que estão na sua interseção: 
• R ∩ S = (R ∪ S) – (R – S) – (S – R) 
D. Seja o seguinte esquema de Banco de Dados Relacional: 
LIVRO (Lid, Título, Editora, Assunto) 
AUTOR (Aid, Nome) 
AUTORIA (Lid, Aid) 
EDITORA (Eid, Nome) 
onde Lid, Aid e Eid representam os atributos chaves das suas respectivas relações. 
Escreva as expressões em Álgebra Relacional que resolvem as seguintes consultas: 
1. Nome das editoras que publicaram livros escritos, em parceria, por dois 
ou mais autores. 
R1 � Autoria 
R2 � Autoria 
T � piR1.Lid [ σR1.Aid ≠ R2.Aid ( R1
 |X| R2 ) ] 
 Lid = Lid 
S �piEditora [ T |X| Livro ] 
 Lid = Lid 
2. Nome dos autores que nunca publicaram livros pela editora McGraw-Hill. 
Códigos dos livros publicados pela editora McGraw-Hill: 
R1 � piLid [ σEditora = “McGraw-Hill” (Livro) ] 
Autores que publicaram livros pela editora McGraw-Hill: 
R2 � piAid [ R1 |x| Autoria ] 
 Lid = Lid 
Universo de autores: 
R3 � piAid [Autor] 
Códigos dos autores que nunca publicaram livros pela editora McGraw-Hill: 
R4 � R3 – R2 
Nomes desses autores: 
S � piNome [R4 |X| Autor ] 
 Aid = Aid 
3. Nomes dos autores que só publicaram livros individualmente e sempre 
na mesma editora. 
Autores que publicaram livros em parceria: 
R1 � Autoria 
R2 � Autoria 
R3 � piR1.Aid [ σR1.Aid ≠ R2.Aid ( R1
 |X| R2 ) ] 
 Lid = Lid 
Autores com mais de uma publicação e seus respectivos livros: 
T1 � piR1.Aid, R1.Lid [ σR1.Lid ≠ R2.Lid (R1|X| R2) ] 
 Aid = Aid 
Editoras dos livros publicados por esses autores: 
T2 � piT1.Aid, Livro.Editora [ T1|X| Livro ] 
 Lid = Lid 
Autores com publicações em mais de uma editora: 
R4 � piAid [ σEditora ≠ Editora (T2|X| T2) ] 
 Aid = Aid 
Universo de autores: 
R5 � piAid [Autor] 
Autores que só publicaram livros individualmente: 
R6 � R5 – R3 
Autores que publicaram livros em apenas uma editora: 
R7 � R5 – R4 
Autores que só publicaram livros individualmente e em apenas uma editora: 
R8 � R6 ∩ R7 
Nomes desses autores: 
S ���� pipipipiNome [R8 |X| Autor ] 
 Aid = Aid 
4. Autores que só publicaram livros numa mesma editora. 
Autores com mais de uma publicação e seus respectivos livros: 
R1 � Autoria 
R2 � Autoria 
T1 � piR1.Aid, R1.Lid [ σR1.Lid ≠ R2.Lid (R1|X| R2) ] 
 Aid = Aid 
Editoras dos livros publicados por esses autores: 
T2 � piT1.Aid, Livro.Editora [ T1|X| Livro ] 
 Lid = Lid 
Autores com publicações em mais de uma editora: 
R3 � piAid [ σEditora ≠ Editora (T2|X| T2) ] 
 Aid = Aid 
Universo de autores: 
R4 � piAid [Autor] 
Autores que publicaram livros em apenas uma editora: 
R5 � R4 – R3 
Nomes desses autores: 
S ���� pipipipiNome [R5 |X| Autor ] 
 Aid = Aid 
5. Autores que publicaram livros sobre todos os assuntos registrados no 
banco de dados. 
A consulta inclui o pronome indefinido todos e portanto envolve a operação de 
divisão. Resta apenas determinar a forma das relações operandas que vão atuar 
como dividendo e divisor nessa operação. 
Considerando que: 
• o número de atributos da relação dividendo deve ser pelo menos uma unidade 
maior do que o número de atributos da relação divisora; 
• todo os atributos da relação divisora devem corresponder, em termos de domínio, 
a um subconjunto não vazio dos atributos da relação dividendo; 
• o resultado da operação inclui todos os atributos da relação dividendo que não 
têm correspondência na relação divisora; 
temos que: 
• a relação dividendo deverá incluir, única e exclusivamente, dois atributos: o 
primeiro deles com domínio “código de autor” e o segundo com domínio 
“assunto”, uma vez que o resultado da operação resume-se aos códigos dos 
autores que publicaram livros sobre todos os assuntos; 
• a relação divisora deverá possuir apenas um atributo com domínio “assunto” 
(i.e., um a menos que a relação dividendo). 
Assim; 
Dividendo � piAutoria.Aid, Livro.Assunto [ Autoria |X| Livro ] 
 Lid = Lid 
Divisor � piAssunto [ Livro ] 
Autores que publicaram livros em todos os assuntos: 
S ���� Dividendo ÷ Divisor 
E. Considere o seguinte esquema de BD: 
PACIENTE (Nome, Doença, Tratamento) 
MÉDICO (Nome, Especialidade) 
Assuma que nomes identificam univocamente tanto pacientes como médicos e que 
alguns médicos eventualmente podem tornar-se pacientes. Assuma também que 
doenças e especialidades possuem o mesmo domínio, isto é, gripe pode aparecer 
como doença e como especialidade. Um médico pode ter mais de uma especialidade. 
Um paciente pode ter mais de uma doença e pode receber mais de um tratamento 
para a mesma doença. 
Expresse as consultas abaixo em expressões da Álgebra Relacional. 
• Nomes dos médicos acometidos de uma doença de sua especialidade. 
Neste caso, o médico também é paciente e sua doença é da sua especialidade. 
Logo: 
Médicos que também são pacientes: 
R1 � Médico |X| Paciente 
 Nome = Nome 
Médicos pacientes cuja doença é a mesma da sua especialidade: 
R2 � σEspecialidade = Doença (R1) 
Solução: 
S ���� pipipipiMédico.Nome [ R2 ] 
• Doenças que possuem um único tratamento. 
Universo de doenças: 
R1 � piDoença [ Paciente ] 
Universo de doenças com mais de um tratamento: 
T1 � Paciente 
T2 � Paciente 
R2 � piT1.Doença [ σTratamento ≠ Tratamento ( T1 |X| T2 ) ] 
 Doença = Doença 
Universo de doenças com um único tratamento: 
R5 ���� R1 – R2 
• Nomes dos pacientes que estão sendo submetidos a todos os tratamentos 
para suas doenças. 
 
 
 
F. Seja o seguinte esquema de BD: 
PEÇAS (#p, nome, tipo) 
CONTÉM (#p, #c) 
Onde uma tupla (k, j) de CONTÉM representa o fato de que a peça de código k contém a peça de 
código j. Evidentemente, #p e #c possuem o mesmo domínio. 
Obtenha expressões da Álgebra Relacional que resolvam as seguintes consultas: 
a) Código e nome das peças do tipo parafuso. 
b) Código das peças atômicas, isto é, que não possuem componentes. 
c) Nome e tipo das peças que possuem um ou mais componentes. 
d) Código das peças que não são componentes de nenhuma peça. 
e) Códigos das peças que possuem mais de um componente. 
f) Código das peças que possuem exatamente um componente. 
g) Código das peças compostas que entram na composição de outras peças. 
G. Considere as Relações F e D que representam Funcionários e Dependentes, respectivamente, 
com o seguinte esquema simplificado: 
F(#f, nomef) 
D(#f, nomed, par) 
onde: 
#f: matrícula do funcionário, 
nomef: nome do funcionário, 
nomed: nome do dependente, e 
par: parentesco, que pode ser um dentre: 'filho', 'filha', 'esposa/o', etc. 
Observe que em D, #f é uma chave-estrangeira que casa com a chave-primária #f de F. 
Abaixo é mostrada uma possível instância dessas relações: 
F D 
#f nomef #f nomed par 
01 F1 01 Alice filha 
02 F2 02 Alice esposa 
03 F3 02 Clara filha 
04 F4 03 José filho 
 
Para as instâncias acima obtenha: 
a) F x D 
b) F |x| D, 
c) pi nomef, nomed (F |x| D ) 
d) σ par='filha'(D) 
Obtenha expressões da álgebra relacional que respondem às seguintes consultas: 
a) Nomes e parentescos de todos os dependentes? 
b) Matrículas dos funcionários que possuem dependentes filhas? 
c) Matrículas do funcionários que não possuem dependentes? 
d) Matrículas dos funcionários que possuem algum dependente. 
e) Nomes dos funcionários que possuem uma dependente chamada Alice. 
f) Matrículas dos funcionários que possuem mais de um dependente? 
g) Matrículas dos funcionários que possuem exatamente um dependente? 
h) Matrículas dos funcionários que não têm Alice como dependente. 
i) Matrículas dos funcionários que possuem uma dependente chamada Alice, juntamente com os 
nomes de seus demais dependentes, quando for o caso. 
j) Matrículas dos funcionários que possuem exatamente um dependente.