/******************************************************
Criação do BD com dados de voos
*******************************************************/
CREATE SCHEMA aula21;
SET SEARCH_PATH TO aula21;

CREATE TABLE voo(
	nvoo	INTEGER		PRIMARY KEY, 
	origem  VARCHAR(30)	NOT NULL, 
	destino VARCHAR(30)	NOT NULL,
	partida	TIME		NOT NULL,
	chegada TIME		NOT NULL);


INSERT INTO voo VALUES (105, 'Chicago', 'Pittsburgh', '8:00', '9:15');
INSERT INTO voo VALUES (104, 'Chicago', 'Detroit', '8:50', '9:30');
INSERT INTO voo VALUES (107, 'Detroit', 'New York', '11:00', '12:30');
INSERT INTO voo VALUES (109, 'Pittsburgh', 'New York', '10:00', '12:00');
INSERT INTO voo VALUES (205, 'Chicago', 'Las Vegas', '14:00', '17:00');
INSERT INTO voo VALUES (101, 'Los Angeles', 'Chicago', '5:30', '7:30');
INSERT INTO voo VALUES (201, 'Las Vegas', 'Tucson', '17:40', '19:00');
INSERT INTO voo VALUES (210, 'Tucson', 'Albuquerque', '19:30', '20:30');
INSERT INTO voo VALUES (310, 'Dallas', 'Albuquerque', '9:30', '11:00');
INSERT INTO voo VALUES (325, 'Los Angeles', 'Dallas', '6:15', '8:15');
INSERT INTO voo VALUES (425, 'Albuquerque', 'Los Angeles', '21:30', '23:00');


/******************************************************
Exemplos de consultas recursivas sobre a tabela Voo
*******************************************************/

-- (a) Escreva uma consulta SQL que retorne os pares de cidade (x,y) tais que é possível chegar em y a partir de x, por meio de um ou mais voos realizados num mesmo dia.

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )
SELECT origem, destino FROM Conectadas;
	

-- (b) Encontre o menor tempo de viagem entre Los Angeles e New York, por meio de nenhuma ou mais conexões realizadas num mesmo dia.

-- Solução 1
WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )
SELECT MIN(chegada - partida) FROM Conectadas WHERE origem = 'Los Angeles' and destino = 'New York';

-- Solução 2: muda a base da recursão, que passa a considerar somente as cidades ligados por um voo direto de Los Angeles. Essa solução é mais eficiente que a anterior (pois reduz o número de tuplas envolvidas nas junções feitas  na recursão)
WITH RECURSIVE ConectadasLA(cidade,partida,chegada) AS (
	(SELECT destino, partida, chegada FROM Voo WHERE origem = 'Los Angeles')
	UNION
	(SELECT V.destino, C.partida, V.chegada 
		FROM ConectadasLA as C, Voo as V 
		WHERE C.cidade = V.origem and C.chegada < V.partida) )
SELECT MIN(chegada - partida) FROM ConectadasLA WHERE cidade = 'New York';

	
-- (c) Escreva uma consulta SQL que retorne os pares de cidade (x,y) tais que é possível chegar em y a partir de x  numa mesma data, mas não existe um voo direto de  x para y.

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )
(SELECT origem, destino FROM Conectadas)
EXCEPT
(SELECT origem, destino FROM Voo);


-- (d) Escreva uma consulta SQL que retorne os pares de cidade (x,y) tais que é possível chegar em y a partir de x numa mesma data pegando 3 ou mais voos.

-- Solução 1: usa como base para a recursão os pares de cidades que estão conectadas entre si por meio de 3 voos

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT V1.origem, V3.destino, V1.partida, V3.chegada 
		FROM Voo as V1, Voo as V2, Voo as V3 
		WHERE V1.destino = V2.origem AND V2.destino = V3.origem 
		       AND V1.chegada < V2.partida AND V2.chegada < V3.partida)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )
SELECT distinct origem, destino FROM Conectadas;


-- Solução 2: faz a recursão da mesma forma que no item (a), mas inclui na relação recursiva (= tabela temporária) o número de vôos usados para conectar cada par de cidades. Depois, na resposta final, seleciona somente os pares ligados por um número de voos >= 3.
   
WITH RECURSIVE Conectadas(origem,destino,partida,chegada,qtde_voos) AS (
	(SELECT origem, destino, partida, chegada, 1 FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada, (C.qtde_voos+1) 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )
SELECT distinct origem, destino FROM Conectadas WHERE qtde_voos >= 3;


--(e) Encontre todas as cidades possíveis de se alcançar a partir de Los Angeles fazendo uma conexão em Las Vegas (podem haver outras conexões, eventualmente) numa mesma data.

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )

SELECT destino FROM Conectadas WHERE origem = 'Las Vegas' 
	AND EXISTS (SELECT * FROM Conectadas WHERE origem =  'Los Angeles' AND destino = 'Las Vegas');

	
-- (f) Encontre o número de todos os voos que não partem de Los Angeles ou de uma cidade que é possível alcançar a partir de Las Vegas por voo direto ou por uma ou mais conexões  numa mesma data.

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )

SELECT nvoo FROM Voo WHERE origem <> 'Los Angeles' 
	AND origem NOT IN (SELECT destino FROM Conectadas WHERE origem = 'Las Vegas');


-- (g) Escreva uma consulta SQL que retorne o conjunto de pares de cidades (x,y) tais que é possível chegar em y a partir de x  numa mesma data e que, a partir de y, pode-se chegar a no máximo uma cidade.

WITH RECURSIVE Conectadas(origem,destino,partida,chegada) AS (
	(SELECT origem, destino, partida, chegada FROM Voo)
	UNION
	(SELECT C.origem, V.destino, C.partida, V.chegada 
		FROM Conectadas as C, Voo as V 
		WHERE C.destino = V.origem and C.chegada < V.partida) )

SELECT nvoo FROM Voo WHERE destino NOT IN 
	(SELECT origem FROM Conectadas GROUP BY origem HAVING COUNT(DISTINCT destino) > 1);