Lista de Exercicios 1

UNIVERSIDADE FEDERAL DE
UBERLÂNDIA
Programa de Pós Graduação em Ciência da
Computação
Disciplina : Sistema de Bancos de Dados - 20 Semestre 2012
Professora : Sandra Aparecida de Amo
Lista de Exercı́cios no 1
Álgebra Relacional
1. Considere a seguinte declaração do modelo relacional contendo informações sobre a programação cinematográfica da cidade de Uberlândia no ano de 1995 :
FILME(TITULO,DIRETOR,ATOR,GENERO,ANO)
SALA(NomeS,END,TEL)
PROGRAMAÇÃO(CodP, NomeS,TITULOF,DIA,HORA)
Dê a expressão da álgebra relacional correspondente às seguintes consultas a este banco
de dados. Descreva também a árvore correspondente à expressão:
(a) Quais os atores que trabalharam sob a direção de Steven Spielberg?
(b) Quais os filmes anunciados na Sala 3 que não estão anunciados na sala 2?
(c) Quais os filmes cujo ano de produção é anterior à 1960 e que estão passando no dia
3/5/95?
(d) Quais os pares de atores que trabalharam no mesmo filme?
(e) Quais os filmes com Woody Allen como ator ou diretor?
(f) Quais os filmes com Leonardo de Caprio que não passaram em Uberlândia em 1995?
(g) Dê os nomes das salas de cinema que exibiram todos os filmes de Leonardo de
Caprio que sairam entre 1996 e 1997.
2. Considere a seguinte declaração do modelo relacional contendo informações sobre produtos vendidos numa loja de informática:
1
Produto(Fabr, Modelo, Tipo)
PC(Modelo, Velocidade,Ram, HD, CD, Preço)
Laptop(Modelo, Velocidade, Ram, HD, Tela, Preço)
Impressora(Modelo, Cor, Tipo, Preço)
Para cada uma das consultas abaixo, dê uma expressão SQL e uma expressão da álgebra
relacional que realize a consulta: (leia a seção 5.3 do livro ”First Course in Databases
Systems”).
(a) Quais os fabricantes de PC com velocidade de pelo menos 160.
(b) Quais os modelos de impressora que custam mais caro ?
(c) Dê o modelo de produto (PC, laptop ou impressora) correspondente ao preço mais
alto.
(d) Encontre os nomes dos fabricantes de impressora colorida mais barata.
(e) Encontre os nomes do fabricantes que produzem impressora e também produzem
PCs com o mais rápido processador e com o menor quantidade de RAM.
Cálculo Relacional
3. Para cada uma das expressões da álgebra relacional encontradas nos dois exercicios precedentes dê uma consulta do cálculo relacional correspondente.
4. Mostre que todas as expressões do cálculo relacional encontradas no item anterior são
fórmulas “seguras”.
DATALOG
5. Para cada uma das consultas dos dois exercı́cios precedentes construa um programa DATALOG que responde a esta consulta. Mostre que cada programa DATALOG que você
construiu é não-recursivo (analisando seu grafo de dependência)
6. Considere o seguinte esquema de bancos de dados :
Voo(Nvoo, Origem, Destino,Partida, Chegada)
Escreva as seguintes consultas em Datalog. Para cada um dos programas encontrados,
diga se é recursivo ou não.
(a) Encontre todos os números de vôos originando de Miami.
(b) Encontre todos os números de vôos que saem de Chicago depois que o vôo 101
chegue em Chicago, mas não mais do que uma hora depois que este vôo 101 chegue
a Chicago.
2
(c) Encontre todos os números de vôos que não saem de Chicago.
(d) Encontre todas as cidades que é possı́vel alcançar a partir de Chicago fazendo uma
conexão em Detroit (podem haver outras conexões, eventualmente).
(e) Encontre todas as cidades que é possı́vel alcançar a partir de Chicago por vôo direto
ou por uma ou mais conexões, tal que não se gaste mais de uma hora esperando
durante a conexão (isto é, cada vôo de conexão deve partir no máximo uma hora
depois da chegada do vôo precedente).
(f) Encontre o menor tempo de vôo entre Chicago e New York, através de uma ou mais
conexões.
(g) Encontre o número de todos os vôos que não partem de Chicago ou de uma cidade
que é possı́vel alcançar a partir de Chicago por vôo direto ou por uma ou mais
conexões.
7. Para cada programa Datalog não recursivo encontrado no item anterior, construa a expressão da álgebra relacional equivalente. Utilize o algoritmo visto em sala de aula, para
isto.
8. Para cada um dos programas Datalog recursivos encontrados no item precedente, diga
se é estratificado ou não (através da análise de seu grafo de dependência), e em caso
afirmativo, exiba os estratos do programa.
9. Considere a seguinte instância sobre a relação Voos.
NVoo
Origem
Destino
Partida Chegada
105
Chicago
Pittsburgh
8:00
9:15
104
Chicago
Detroit
8:50
9:30
107
Detroit
New York
11:00
12:30
109
Pittsburgh
Nova York
10:00
12:00
205
Chicago
Las Vegas
14:00
17:00
101
Los Angeles
Chicago
5:30
7:30
201
Las Vegas
Tucson
17:40
19:00
210
Tucson
Albuquerque 19:30
20:30
310
Dallas
Albuquerque
9:30
11:00
325
Los Angeles
Dallas
6:15
8:15
425 Albuquerque Los Angeles
21:30
23:00
Encontre a resposta da consulta (d) do exercicio (6) sobre este banco de dados. Descreva
com detalhes o cálculo da resposta desta consulta utilizando:
(a) O método do ponto fixo
(b) O método da resolução
10. Dê as expressões de SQL3 correspondentes às consultas recursivas do exercicio (6).
11. Considere a relação Filme-Sequencia(filme, seq-filme) que armazena tuplas (m, m1), onde
m é tı́tulo de um filme e m1 é o titulo da primeira sequência de m. Por exemplo (Rocky,
Rochy II), (Missão Impossivel, Missão Impossivel II).
3
Define-se uma relação Continuacao tal que uma tupla (m, m0 ) está em Continuacao se m0
é uma das continuação de m, não necessariamente a primeira. Por exemplo, Rocky III é
uma continuação de Rocky.
(a) Escreva uma consulta SQL3 que retorna os pares (x, y) tais que y é uma continuação
de x, mas não uma sequência imediata de x.
(b) Escreva uma consulta SQL3 que retorna os pares (x, y) tais que y é uma continuação
de x, mas não uma sequência imediata de x ou uma sequência de sequência de x.
(c) Escreva uma consulta SQL3 que retorna o conjunto de filmes x que possuem pelo
menos duas sequências diretas. Isto é, existe m e m0 distintos tais que m e m0 são
sequências diretas de x.
(d) Escreva uma consulta SQL3 que retorna o conjunto de filmes x que possuem pelo
menos duas sequências seguidas. Isto é, existe m e m0 distintos tais que m é sequência
direta de x e m0 é sequência direta de m.
(e) Escreva uma consulta SQL3 que retorna o conjunto de pares de filmes (x, y) tais
que y é uma sequência direta de x e y tem no máximo uma sequência direta (ou
nenhuma).
12. Considere as seguintes relações extensionais R e S:
R
a
b
c
d
S
a
c
e
f
Considere a seguinte consulta Datalog
U (x) :- T (x), Q(x)
P (x) :- S(x), ¬U (x)
P (x) :- T (x), ¬S(x)
P (x) :- S(x), ¬Q(x)
Q(x) :- R(x), S(x)
T (x) :- S(x), ¬Q(x)
(a) Esta consulta é estratificável ? Por que ? Em caso positivo forneça uma estratificação
para a consulta.
(b) Calcule a resposta á consulta, utilizando o método do ponto fixo, estrato por estrato.
Descreva todos os passos do cálculo da resposta. A relação da resposta é T .
(c) Dê a expressão SQL3 correspondente a esta consulta Datalog.
13. Considere a seguinte expressão de SQL3:
WITH
RECURSIVE P(X) AS
(SELECT R.X FROM R WHERE R.X NOT IN S),
RECURSIVE S(X) AS
4
(SELECT R.X FROM R,Q WHERE R.X = Q.X) UNION
(SELECT R.X FROM R,P WHERE R.X = P.X)
SELECT * FROM P
A relação R é extensional. Tente encontrar a resposta desta consulta sobre R = {a,b}
através do ponto fixo, e conclua que o método não converge. Portanto, não produz
resposta nenhuma e entra em loop. Explique por que isto acontece (a consulta é estratificável ?)
14. Considere a seguinte expressão de SQL3:
WITH
P(X) AS
(SELECT * FROM R)
UNION
(SELECT * FROM Q),
Q(X) AS
(SELECT count(X) FROM P)
SELECT * FROM Q
A relação R é extensional. Tente encontrar a resposta desta consulta sobre R = {2,4}
através do ponto fixo, e conclua que o método não converge. Portanto, não produz
resposta nenhuma e entra em loop.
15. Proponha um método para determinar se um programa datalog é estratificável e em caso
positivo produzir uma estratificação, somente utilizando o grafo de dependência (com
labels positivos e negativos).
5