[SQL]高級SQL-遞歸(2)

第二部分數(shù)據(jù)集 - 公共交通 Schema

公共交通數(shù)據(jù)集Fahrplan在　https://hyper-db.de/interface.html　可以直接使用。另外在這個網(wǎng)頁不允許進行寫操作:insert, update, delete之類的transactional query。當然create table和drop table也不被允許。

本地載入改數(shù)據(jù)集： https://segmentfault.com/a/1190000021623693#item-3-3

英文Schema： Fahrplan = \{\underline{From\_, To\_, Line\_}, depart, arrival\}

德文Schema： Fahrplan = \{\underline{Von, Nach, Linie}, Abfahrt, Ankunft\}

有關英文Schema：在我的文章提到這一塊內(nèi)容。德文schema可以直接在HyPer網(wǎng)頁接口運行。這里為了方便大家直接在網(wǎng)頁上運行，我采用德文schema。

Schma和大部分SQL語句來自Prof. Alfons Kemper, Ph.D.的課件和書。

課件：

書：　https://db.in.tum.de/teaching/bookDBMSeinf/?lang=de

熟悉數(shù)據(jù)集

首先我們先運行一些簡單SQL，來認識一下這個數(shù)據(jù)集內(nèi)之間的關系。

  • von這一行字符串(string)匹配：
select distinct von
from fahrplan
where von like '%Garching%'

             von             
-----------------------------
Garching
Garching, Forschungszentrum
Garching-Hochbrück
(3 rows)
  • case
select linie,
       case
           when linie like 'U%' then 'U-Bahn'
           when linie like 'S%' then 'S-Bahn'
           else 'Bus/Tram'
           end as public_transportation
from fahrplan

 linie | public_transportation 
-------+-----------------------
 U6    | U-Bahn
 U6    | U-Bahn
 U6    | U-Bahn
 U6    | U-Bahn
 U6    | U-Bahn
 U6    | U-Bahn
 690   | Bus/Tram
(7 rows)
  • 求從Garching, Forschungszentrum出發(fā)，我們現(xiàn)在(current_time)能趕上的交通工具：
select *
from fahrplan
where abfahrt > current_time and von = 'Garching, Forschungszentrum'
order by abfahrt
  • 搜索兩個車站，這倆之間需要3分鐘到5分鐘能夠到達(注意第一天午夜發(fā)車，第二天凌晨到達的情況):
with duration as (
    select *,
    (case when ankunft < abfahrt then 60 * 60 * 24 - extract(epoch from abfahrt - ankunft)
          else extract(epoch from ankunft - abfahrt)
    end) as duration_in_sec
    from fahrplan
)

select *
from duration
where duration_in_sec between 3*60 and 5*60

或者

with duration as (
    select *,
    (case when ankunft < abfahrt then 60 * 60 * 24 - extract(epoch from abfahrt - ankunft)
          else extract(minute from ankunft - abfahrt)
    end) as duration_in_min
    from fahrplan
)

select *
from duration
where duration_in_min between 3 and 5

</br>

很顯然下面的寫法會忽略第一天午夜發(fā)車，第二天凌晨到達的情況:

select *
from fahrplan
where extract(epoch from ankunft - abfahrt) between 3*60 and 5*60

select *
from fahrplan
where extract(minute from ankunft - abfahrt) between 3 and 5

列出所有可能的公共交通連接：

with recursive fahrplan_rec as (
    -- von -> nach
    select von, nach, abfahrt, ankunft from fahrplan
    union all
    -- fr. von -> fr.nach = f.von -> f.nach 多走一步
    -- 從fr.von到f.nach
    select fr.von, f.nach, fr.abfahrt, f.ankunft
    from fahrplan_rec fr, fahrplan f
    where fr.nach = f.von and fr.ankunft <= f.abfahrt and fr.von != f.nach -- 不能是環(huán)
)

select *
from fahrplan_rec
  • fr.ankunft <= f.abfahrt：我們的前提
  • fr.von != f.nach: 排除我們從A到A(即成環(huán)的情況)。

列出所有可能的公共交通連接 + 乘車時間 ＋ 等車時間：

with recursive fahrplan_rec_linie as (
    -- von -> nach
    select
        von,
        nach,
        abfahrt,
        ankunft,
        ankunft - abfahrt as fahrtzeit,
        INTERVAL '00:00:00' as wartezeit
    from fahrplan
    union all
    -- fr. von -> fr.nach = f.von -> f.nach 多走一步
    -- 從fr.von到f.nach
    select
        fr.von,
        f.nach,
        fr.abfahrt,
        f.ankunft,
        fr.fahrtzeit + (f.ankunft - f.abfahrt),
        fr.wartezeit + (f.abfahrt - fr.ankunft)
        from fahrplan_rec_linie fr, fahrplan f
    where fr.nach = f.von and fr.ankunft <= f.abfahrt and fr.von != f.nach
), fahrplan_rec as (
    select
        von,
        nach,
        abfahrt,
        ankunft,
        fahrtzeit,
        wartezeit,
        fahrtzeit + wartezeit as reisezeit
    from fahrplan_rec_linie
)

select *
from fahrplan_rec

列出所有可能的公共交通連接 + 乘車時間 ＋ 等車時間 + 轉(zhuǎn)乘次數(shù)：

with recursive fahrplan_rec_linie as (
    -- von -> nach
    select
        von,
        nach,
        abfahrt,
        ankunft,
        linie as aktuelle_linie,
        0 as umstiege,
        ankunft - abfahrt as fahrtzeit,
        INTERVAL '00:00:00' as wartezeit
    from fahrplan
    union all
    -- fr. von -> fr.nach = f.von -> f.nach 多走一步
    -- 從fr.von到f.nach
    select
        fr.von,
        f.nach,
        fr.abfahrt,
        f.ankunft,
        f.linie,
        fr.umstiege +
            case
                when f.linie != fr.aktuelle_linie or f.abfahrt > fr.ankunft then 1
                else 0
            end,
        fr.fahrtzeit + (f.ankunft - f.abfahrt),
        fr.wartezeit + (f.abfahrt - fr.ankunft)
        from fahrplan_rec_linie fr, fahrplan f
    where fr.nach = f.von and fr.ankunft <= f.abfahrt and fr.von != f.nach
), fahrplan_rec as (
    select
        von,
        nach,
        abfahrt,
        ankunft,
        umstiege,
        fahrtzeit,
        wartezeit,
        fahrtzeit + wartezeit as reisezeit
    from fahrplan_rec_linie
)

select *
from fahrplan_rec

10:30之前從Fr?ttmaning到達Garching, Forschungszentrum

我們需要一次好的公共交通：最遲需要在10:30到達，而且沒有任何一個另外的公共交通遲出發(fā)但是也能在10:30之前到, 而且總時間更少, 而且換乘數(shù)也更少：

with recursive fahrplan_rec_linie as (
    -- von -> nach
    select
        von,
        nach,
        abfahrt,
        ankunft,
        linie as aktuelle_linie,
        0 as umstiege,
        ankunft - abfahrt as fahrtzeit,
        INTERVAL '00:00:00' as wartezeit
    from fahrplan
    union all
    -- fr. von -> fr.nach = f.von -> f.nach 多走一步
    -- 從fr.von到f.nach
    select
        fr.von,
        f.nach,
        fr.abfahrt,
        f.ankunft,
        f.linie,
        fr.umstiege +
            case
                when f.linie != fr.aktuelle_linie or f.abfahrt > fr.ankunft then 1
                else 0
            end,
        fr.fahrtzeit + (f.ankunft - f.abfahrt),
        fr.wartezeit + (f.abfahrt - fr.ankunft)
        from fahrplan_rec_linie fr, fahrplan f
    where fr.nach = f.von and fr.ankunft <= f.abfahrt and fr.von != f.nach
), fahrplan_rec as (
    select
        von,
        nach,
        abfahrt,
        ankunft,
        umstiege,
        fahrtzeit,
        wartezeit,
        fahrtzeit + wartezeit as reisezeit
    from fahrplan_rec_linie
)

select *
from fahrplan_rec fr
where fr.von = 'Fr?ttmaning' and fr.nach = 'Garching, Forschungszentrum'
      and fr.ankunft <= TIME '10:30:00' and not exists (
          select * from fahrplan_rec fr2
          where fr2.von = fr.von and fr2.nach = fr.nach and fr2.ankunft <= TIME '10:30:00' and
                fr2.abfahrt > fr.abfahrt and fr2.reisezeit < fr.reisezeit and fr2.umstiege < fr.umstiege
          )

union vs. union all

下面我們來研究一下圖論(graph theory)來加強對union和union all的印象。

求從Garching, Forschungszentrum能到達的所有地方(可到達性(st-connectivity))：

with recursive closure as (
    select von, nach
    from fahrplan
    union -- Set(集合)
    select c.von, f.nach
    from closure c, fahrplan f
    where c.nach = f.von
)

select distinct von, nach
from closure
where von = 'Garching, Forschungszentrum'
order by nach

這里只能是union，不能是union all。
比如有A->B, B->A在union all的情況下，不會終止。

求從Garching從兩個方向能到達的所有地方：

with recursive closure as (
    select von, nach
    from fahrplan
    union -- Set(集合)
    select f.von , c.nach
    from fahrplan f, closure c
    where f.nach = c.von
) , connected_graph as (
    select von, nach
    from fahrplan
    union -- Set(集合)
    select c.von , cg.nach
    from closure c , connected_graph cg
    where c.nach = cg.von
)

select distinct *
from connected_graph
where von = 'Garching'
order by von;

再來一個圖論的例子：

dag.png

這個圖是一個有向無環(huán)圖(DAG, directed acyclic graph)。

with recursive graph (von , nach) as (
    -- Basic relation
    values ('a', 'b'),
           ('b', 'c'),
           ('c' ,'d'),
           ('b', 'e'),
           ('f', 'c'),
           ('x', 'y') -- 第二個聯(lián)通部分
), un_dir_graph (von, nach) as (
    -- 無向圖
    (select von, nach
    from graph)
    union all
    (select nach, von
    from graph)
), closure (von, nach) as (
    (select von, nach
    from un_dir_graph)
    union -- Set(集合)
    (select c.von, g.nach
    from closure c, graph g
    where c.nach = g.von)
), connected_graph (von ,nach) as (
    (select nach , von
    from closure)
    union -- Set(集合)
    (select c.von , cg.nach
    from closure c, connected_graph cg
    where c.nach = cg.von)
)

select nach
from connected_graph
where von = 'b' -- Garching
order by nach;

很容易發(fā)現(xiàn)closure是一個對稱的關系(symmetric relation):
\exists (a , b) \in R \Rightarrow (b, a) \in R

這時候我們用UNION ALL是肯定不會終止的，因為UNION ALL采用包語義(Bag Semantics)，它不會消除重復(duplicates)。
而UNION采用集合語義(Set Semantics)，它會消除重復。

該文章遵循創(chuàng)作共用版權協(xié)議 CC BY-NC 3.0，要求署名、非商業(yè) 、保持一致。在滿足創(chuàng)作共用版權協(xié)議 CC BY-NC 3.0 的基礎上可以轉(zhuǎn)載，但請以超鏈接形式注明出處。文章僅代表作者的知識和看法，如有不同觀點，可以回復并討論。

最后編輯于 ：
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

  • 遞歸 Recursion 我們這一篇文章采用并介紹PostgreSQL的SQL遞歸(Recursion)語法。遞歸...
    CakeByTheOcean閱讀 397評論 0贊 1
  • 正文 這里我們會遇到subquery，它可以出現(xiàn)在select子句中或者where子句或者from子句中。它會產(chǎn)生...
    CakeByTheOcean閱讀 344評論 0贊 1
  • 數(shù)據(jù)集 我們這一篇文章采用PostgreSQL的SQL語法。重點我們關注select...from...where...
    CakeByTheOcean閱讀 180評論 0贊 0
  • web應用程序會對用戶的輸入進行驗證，過濾其中的一些關鍵字，這種過濾我們可以試著用下面的方法避開。 1、 不使用被...
    查無此人asdasd閱讀 7,651評論 0贊 5
  • 數(shù)據(jù)集 我們這一篇文章采用PostgreSQL的SQL語法。重點我們關注select...from...where...
    CakeByTheOcean閱讀 241評論 0贊 0

友情鏈接更多精彩內(nèi)容