SQL 3
Recursão em SQL
AULA 7
PGC 107 - Sistemas de Banco de Dados
Profa. Sandra de Amo
Pós-graduação em Ciência da Computação – UFU
2012-2
Recursão em SQL 3
Definição de relações intensionais:
WITH R1 AS < regras que definem R1 > ,
RECURSIVE R2 AS <regras que definem R2>
< consulta SQL envolvendo R >
R = predicado intensional que define a consulta
Recursão em SQL3
A cláusula WITH tem a seguinte forma:
1.
A palavra chave WITH
2.
Uma ou mais definições de relações, separadas por vírgulas
3.
Se a relação sendo definida é recursiva, preceder a definição
pela palavra chave RECURSIVE.
4.
Nome da relação sendo definida
5.
Palavra chave AS
6.
Uma consulta final (não ligada por vírgula com a
precedente), que pode se referir às relações definidas
anteriormente, e que forma o resultado da consulta
especificada pela cláusula WITH
Exemplo
WITH RECURSIVE Conecta(O,D) AS
(2)
(SELECT O, D FROM Voos)
(3)
UNION
(4)
(SELECT R1.O, R2.D
(5)
FROM Conecta AS R1, Conecta AS R2
(6)
WHERE R1.D = R2.O)
(7) SELECT * FROM Conecta
(8) WHERE O = ‘SP’ OR D = ‘SP’
(1)
Recursão Linear
Uma única ocorrência na cláusula FROM da
definição da relação recursiva
WITH RECURSIVE R AS
(.... SELECT FROM R...)


Alguns SGBDs não suportam consultas com
recursão não-linear
Exemplo (Corrigindo o código do
exemplo anterior)
WITH RECURSIVE Conecta(O,D) AS
(2)
(SELECT O, D FROM Voos)
(3)
UNION
(4)
(SELECT Voos.O, Conecta.D
(5)
FROM Voos, Conecta
(6)
WHERE Voos.D = Conecta.O)
(7) SELECT * FROM Conecta
(8) WHERE O = ‘SP’ OR D = ‘SP’
(1)
Exemplo (Corrigindo o código do
exemplo anterior)
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
WITH
Pairs AS SELECT O,D FROM Voos,
RECURSIVE Conecta(O,D) AS
Pairs
UNION
(SELECT Pairs.O, Conecta.D
FROM Pairs, Conecta
WHERE Pairs.D = Conecta.O )
SELECT * FROM Conecta
WHERE O = ‘SP’ OR D = ‘SP’
Negação estratificada em SQL3


Definições de relações com dependência
negativa devem ser estratificadas
Exemplo

Dê os pares de cidades (x,y) para as quais é
possível ir de x para y com a companhia UA, mas
não com a companhia AA.
Exemplo
With
Triples AS SELECT C, O, D FROM Voos,
RECURSIVE Conecta(C,O,D) AS
Triples
Union
(Select Triples. C, Triples.O, Conecta.D
FROM Triples, Conecta
WHERE Triples.D = Conecta.O AND
Triples.C = Conecta.C)
(SELECT O, D FROM Conecta WHERE C = ‘UA’)
EXCEPT
(SELECT O, D FROM Conecta WHERE C = ‘AA’)
Consulta incorreta (não estratificada ! )
WITH
RECURSIVE P(x) AS
(SELECT * FROM R)
EXCEPT
(SELECT * FROM Q),
RECURSIVE Q(x) AS
(SELECT * FROM R)
EXCEPT
(SELECT * FROM P)
SELECT * FROM P
Exercícios
1)
2)
3)
4)
5)
Encontrar as cidades para as quais é possível ir, saindo de SP
e voando pela mesma companhia aérea.
Quais os horários de partida de voos da American Airlines,
saindo de São Paulo e chegando em Miami ?
É possível ir para Paris, saindo de São Paulo, sem passar por
nenhum voo da TAM ? Forneça os horários de partida e
chegada nestes casos.
É possível ir para Paris, saindo de São Paulo, passando por
algum voo da TAM ? Forneça os horários de partida e
chegada nestes casos.
Para Casa: Quais os roteiros com menor número de
conexões entre São Paulo e Paris ?
Outras consultas incorretas (não
estratificadas)
WITH
RECURSIVE P(x) AS
(SELECT x FROM R WHERE x NOT IN Q ),
RECURSIVE Q(x) AS
(SELECT x FROM R WHERE x NOT IN P )
SELECT * FROM P
Por que consultas não estratificadas
são problemáticas ?
Resultado da consulta é
ambíguo
WITH
RECURSIVE P(x) AS
(SELECT x FROM R WHERE x
NOT IN Q ),
RECURSIVE Q(x) AS
(SELECT x FROM R WHERE x
NOT IN P )
SELECT * FROM P
Relações extensionais = R
Relações intencionais = P, Q
Cálculo do ponto fixo:
T0 = {R(a), R(b)}
T1 = {P(a), P(b), Q(a), Q(b)}
T2 = { }
T3 = {P(a), P(b), Q(a), Q(b)}
T4 = { }
......
Problemas com a agregação
WITH
RECURSIVE P(x) AS
(SELECT * FROM R)
UNION
(SELECT * FROM Q),
RECURSIVE Q(x) AS
(SELECT SUM(x) FROM P)
SELECT * FROM P
P(x) :- R(x)
P(x) :- Q(x)
Q(x) :- R(x)
Q(x) :- P(x)
Estratificável
Porém fazendo a agregação
sobre P, ponto fixo não
converge !
Problemas com a agregação
T0 = {R(12), R(34)}
T1 = T0 U{P(12),P(34)}
T2 = T0 U {P(12),P(34),Q(46)}
T3 = T0 U {P(12),P(34),P(46),Q(46)}
T4 = T0 U {P(12),P(34),P(46),Q(92)},
T5 = T0 U {P(12),P(34),P(92),Q(92)}
.....
Portanto
Em SQL3, agregação só é permitida na definição
de relações, se a agregação é feita sobre uma
relação já completamente definida no estrato
precedente.
Diferenças entre consultas incorretas


Recursão não linear : só uma questão de
implementação – pode ser implementada em
alguns SGBDs
Consulta não-estratificada: problema
conceitual, resposta não está bem definida
Não é possivel de ser implementada.
Observações finais


Por que no cálculo do ponto fixo, a cada
iteração os valores das relações aparecendo no
corpo das regras são sempre aqueles definidos
na iteração precedente ?
O que aconteceria se os valores das relações
do corpo das regras fossem sendo atualizados
durante uma mesma iteração ?
Exemplo
WITH
RECURSIVE P(x) AS
(SELECT x FROM R
WHERE x NOT IN Q ),
RECURSIVE Q(x) AS
(SELECT x FROM R
WHERE x NOT IN P )
SELECT * FROM P
Cálculo do ponto fixo
dependeria da ordem
das regras:
Caso 1 :
T0 = {R(a), R(b)}
T1 = {P(a), P(b)}
T2 = {P(a), P(b)}
Caso 2 :
T0 = {R(a), R(b)}
T1 = {Q(a), Q(b)}
T2 = {Q(a), Q(b)}
Exercício
WITH
RECURSIVE P(x) AS
(SELECT * FROM R)
UNION
(SELECT * FROM Q),
RECURSIVE Q(x) AS
((SELECT SUM(x) FROM P)
SELECT * FROM P
Cálculo do ponto fixo
dependeria da ordem das
regras:
Caso 1 :
T0 = {R(12), R(34)}
T1 = {P(12), P(34),Q(46)}
T2 = {P(12),P(34),P(46),Q(92)},....
Caso 2 :
T0 = {R(12), R(34)}
T1 = {P(12),P(34)}
T2 = {Q(46), P(12),P(34),P(46)}
T3 = {Q(92), P(12),P(34),P(92)},...