接続するフライトのdestパスにsrcを取得するSqlクエリ

接続フライトを含むdest飛行経路を探したい場合は問題を解決したい場合は可能な限り時間を並べ替えます。接続するフライトのdestパスにsrcを取得するSqlクエリ

私はlistaggのようなものを何とかしてストリングとして中間飛行を集約することができます。

接続フライトの回数に制限と時間をかけます。私は今、スタートとしてこれを持って

は私の乗り継ぎ便

with cap as (select 30 time_cap , 5 connect_cap), 
connecting as 
    (select f1.src src1 
      , f1.dest dest1 
      , f1.stt st1 
      , f1.endt end1 
      , f2.src src2 
      , f2.dest dest2 
      , f2.stt st2 
      , f2.endt end2 
      , (f2.endt - f1.stt) as time 
    from flight f1 
    inner join flight f2 on f1.dest = f2.src 
    where f1.endt < f2.stt)

を与える私のテーブルが

\d+ flight 
            Table "public.flight" 
Column |   Type    | Modifiers | Storage | Stats target | Description 
--------+-----------------------------+-----------+----------+--------------+------------- 
src | character varying(20)  |   | extended |    | 
dest | character varying(20)  |   | extended |    | 
stt | timestamp without time zone |   | plain |    | 
endt | timestamp without time zone |   | plain |    |

次のようになりますこれはすでに乗り越え面接の質問でした。

sqlクエリでグラフbfsの解決策を解決できますか？

動作していないクエリ（疑似コード - 試してみるとうまくいく）でもアプローチしても問題ありません。

以下のクエリでは、最後の目的地が行きたい目的地であるかどうかを確認できる方法を見つけたいと思います。 SQLのツリートラバーサルの問題の

with flight as (select f1.src||'-'||f1.dest||','||f2.src||'-'||f2.dest route 
        , f1.src src1 
        , f1.dest dest1 
        , f1.stt st1 
        , f1.endt end1 
        , f2.src src2 
        , f2.dest dest2 
        , f2.stt st2 
        , f2.endt end2 
        , (f2.endt - f1.stt) as time 
       from flight f1 
       inner join flight f2 on f1.dest = f2.src 
       where f1.endt < f2.stt) 

select string_agg(route,',') from flight ;

クエリ飛行

route | src1 | dest1 |   st1   |  end1   | src2 | dest2 |   st2   |  end2   | time 
---------+------+-------+---------------------+---------------------+------+-------+---------------------+---------------------+---------- 
a-b,b-c | a | b  | 2017-05-17 09:31:56 | 2017-05-17 14:31:56 | b | c  | 2017-05-17 15:31:56 | 2017-05-17 16:31:56 | 07:00:00

出典

2017-10-06 Akshay Hazari

@JacobKrallはい、私は質問 –

を更新した私はかどうかを知りません私が権威ある機関から来たわけではないので、インタビュアーは不公平にしようとしていました。主にインドで起こるあるいは、彼は自分自身の問題の解決策を私から求めようとしていました。私はすでに彼にBFSを使ってこれを行うコードを与えました。ちょうどそれを試してみたかった。 –

明日まで誰も答えなければ、私はそれを試してみましょう。私は一度ここで解決した問題のようです。見てみましょう：https://stackoverflow.com/a/38194463/460557これは日付の期間ですが、飛行経路で使用するために変更することができます。 –

からの出力これらのタイプは、特別な構文WITH RECURSIVEを使用して解決することができます。ソリューションをテストする

、ダミーデータで、以下の表を作成することができます：

CREATE TABLE flight (
    src TEXT 
, dest TEXT 
, stt TIMESTAMP 
, endt TIMESTAMP); 

INSERT INTO flight VALUES 
('SIN', 'DAC', '2016-12-31 22:45:00', '2017-01-01 01:45:00'), 
('DAC', 'SIN', '2017-01-01 16:30:00', '2017-01-01 21:30:00'), 
('SIN', 'DAC', '2017-01-01 22:45:00', '2017-01-02 01:45:00'), 
('DAC', 'DEL', '2017-01-01 10:00:00', '2017-01-01 11:30:00'), 
('DEL', 'DAC', '2017-01-01 12:30:00', '2017-01-01 14:00:00'), 
('DAC', 'CCU', '2017-01-01 10:30:00', '2017-01-01 11:15:00'), 
('CCU', 'DAC', '2017-01-01 11:45:00', '2017-01-01 12:30:00'), 
('SIN', 'DEL', '2017-01-01 11:00:00', '2017-01-01 15:00:00'), 
('DEL', 'SIN', '2017-01-01 16:30:00', '2017-01-01 20:30:00'), 
('CCU', 'DEL', '2017-01-01 12:00:00', '2017-01-01 12:45:00'), 
('DEL', 'CCU', '2017-01-01 13:15:00', '2017-01-01 14:00:00');

再帰CTEのは、完全に理解することは困難ですので、私は作品によって、論理ピースを構築します。

再帰的CTEには2つの部分があります。アンカーサブクエリ&は再帰的サブクエリです。最初にアンカーサブクエリが実行され、空の結果セットが返されるまで再帰的サブクエリが実行されます。トリッキーな部分（少なくとも私にとっては）は、1つのノードから次のノードへの走査を実行する結合を構築しています。

アンカーと再帰的なサブクエリは、UNION ALL（またはときどきUNION）を使用してマージされ、返されます。

我々は、飛行ルートに興味を持っているので、簡単なアンカーサブクエリが開始すると次のようになります

SELECT src, ARRAY[src] path, dest FROM flight

上記のクエリは、開始の3列、パス&終わり、2番目の列に、我々は変換を有しますsrcフィールドはTEXTからTEXT[]までです。これは厳密には必要ではありませんが、配列を追加するのが簡単であるため、残りのステップを大幅に簡略化します。

上記のアンカークエリを使用して、再帰的cteを定義できるようになりました。

WITH RECURSIVE flight_paths (src, path, dest) AS (
SELECT 
    src 
, ARRAY[src] 
, dest 
FROM flight 
UNION ALL 
SELECT 
    fp.src 
, fp.path || f.src -- appends another 'flight source' 
, f.dest -- updates the dest to the new dest 
FROM flight f 
JOIN flight_paths fp ON f.src = fp.dest 
-- this is the join that links the tree nodes 
WHERE NOT f.src = ANY(fp.path) 
-- this condition prevents infinite recursion by not visiting nodes that have already been visited. 
) SELECT * FROM flight_paths 
-- finally, we can select from the flight_paths recursive cte

上記は、テストデータで136行を返します。最初の15行は以下の通りである：

src path  dest 
SIN {SIN}  DAC 
DAC {DAC}  SIN 
SIN {SIN}  DAC 
DAC {DAC}  DEL 
DEL {DEL}  DAC 
DAC {DAC}  CCU 
CCU {CCU}  DAC 
SIN {SIN}  DEL 
DEL {DEL}  SIN 
CCU {CCU}  DEL 
DEL {DEL}  CCU 
DEL {DEL,CCU} DAC 
DAC {DAC,CCU} DAC 
DEL {DEL,CCU} DEL 
DAC {DAC,CCU} DEL 
DEL {DEL,CCU} DEL 
DAC {DAC,CCU} DEL

この部分、ツリートラバーサルの設定は、再帰CTEを書き込むの最も難しい部分です。さて、トラバーサルが設定されていることを、我々は変更することができます上記のように：

我々は先に、ソース&終わりに開始
に達している
でストップの繰り返し到着（AB）、この例の<出発（BC）

は、src := SIN & dest := CCUを許可すればAB & BCは有効であると洗練できるようになりました

src path dest stt endt SIN {SIN,DAC} CCU 2016-12-31 22:45:00 2017-01-01 11:15:00 SIN {SIN,DAC,DEL} CCU 2016-12-31 22:45:00 2017-01-01 14:00:00

：

WITH RECURSIVE flight_paths (src, path, dest, stt, endt) AS (
SELECT 
    src 
, ARRAY[src] 
, dest 
, stt 
, endt 
FROM flight 
UNION ALL 
SELECT 
    fp.src 
, fp.path || f.src 
, f.dest 
, fp.stt 
, f.endt -- update endt to the new endt 
FROM flight f 
JOIN flight_paths fp ON f.src = fp.dest 
WHERE NOT f.src = ANY(fp.path) 
    AND NOT 'CCU' = ANY(fp.path) 
    -- (2) this new predicate stop iteration when the destination is reached 
    AND f.stt > fp.endt 
    -- (3) this new predicate only proceeds the iteration if the connecting flights are valid 
) 
SELECT * 
FROM flight_paths 
WHERE src = 'SIN' AND dest = 'CCU' 
-- (1) specify the start & end

このコラムstt & endtとして最終便の到着時間として初飛行の出発時刻と2の可能なルートを与えます結果セットは非常に簡単です。で飛行時間に&接続時間を計算する列を追加することもこの時点から非常に簡単です

SELECT * 
FROM flight_paths 
WHERE src = 'SIN' AND dest = 'CCU' 
    AND endt::time < '12:00:00'::time

：としてたとえば、最後のクエリでは、唯一の正午前に目的地に到着する便を返すように変更することができ再帰的なcteを作成し、その2回の述語に合ったフライトをフィルタリングします。私はあなたにこれらの2つのバリエーションを生成するための十分な詳細を与えていただきたいと思います。

pathアレイの長さをフィルタリングすることによって接続数を制限することもできますが、最大接続に達すると再帰的cteの繰り返しを停止するほうが効率的です。

最終的な注意点：以前は物事を単純にするために、最終的な目的地以外の経路で作業しました。 {SIN, DAC, DEL}代わりの便{SIN-DAC, DAC-DEL, DEL-CCU}（または停止オーバー{DAC, DEL}）の配列が、以下に示すように、我々はかなり簡単にそれらの表現を取得することができます：

WITH RECURSIVE flight_paths (src, flights, path, dest, stt, endt) AS (
SELECT 
    src 
, ARRAY[src || '-' || dest] 
, ARRAY[src] 
, dest 
, stt 
, endt 
FROM flight 
UNION ALL 
SELECT 
    fp.src 
, fp.flights || (f.src || '-' || f.dest) 
, fp.path || f.src 
, f.dest 
, fp.stt 
, f.endt 
FROM flight f 
JOIN flight_paths fp ON f.src = fp.dest 
WHERE NOT f.src = ANY(fp.path) 
    AND NOT 'CCU' = ANY(fp.path) 
    AND f.stt > fp.endt 
) 
SELECT flights, stt, endt, path[2:] stopovers 
FROM flight_paths 
WHERE src = 'SIN' AND dest = 'CCU'

出典

2017-10-31 07:56:27

真剣に男。その再帰的なクエリは私の知識に加えられたものです。心が吹いた！尊敬 _/\\_ –

接続するフライトのdestパスにsrcを取得するSqlクエリ

答えて

関連する問題