第二部分数据集 - 公共交通 Schema
公共交通数据集Fahrplan在 https://hyper-db.de/interface.html 可以直接使用。另外在这个网页不允许进行写操作:insert, update, delete之类的transactional query。当然create table和drop table也不被允许。
本地载入改数据集： https://segmentfault.com/a/1190000021623693#item-3-3
英文Schema：
德文Schema：
有关英文Schema：在我的文章提到这一块内容。德文schema可以直接在HyPer网页接口运行。这里为了方便大家直接在网页上运行，我采用德文schema。
Schma和大部分SQL语句来自Prof. Alfons Kemper, Ph.D.的课件和书。
课件：
- https://db.in.tum.de/teaching/bookDBMSeinf/folien/?lang=de
- https://db.in.tum.de/teaching/bookDBMSeinf/folien/pdf/Kapitel4.pdf?lang=de
书： https://db.in.tum.de/teaching/bookDBMSeinf/?lang=de
熟悉数据集
首先我们先运行一些简单SQL，来认识一下这个数据集内之间的关系。
-
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出发，我们现在(current_time)能赶上的交通工具：
select *
from fahrplan
where abfahrt > current_time and von = 'Garching, Forschungszentrum'
order by abfahrt
- 搜索两个车站，这俩之间需要3分钟到5分钟能够到达(注意第一天午夜发车，第二天凌晨到达的情况):
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>
很显然下面的写法会忽略第一天午夜发车，第二天凌晨到达的情况:
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 -- 不能是环
)
select *
from fahrplan_rec
-
fr.ankunft <= f.abfahrt：我们的前提 -
fr.von != f.nach: 排除我们从A到A(即成环的情况)。
列出所有可能的公共交通连接 + 乘车时间 ＋ 等车时间：
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
列出所有可能的公共交通连接 + 乘车时间 ＋ 等车时间 + 转乘次数：
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到达，而且没有任何一个另外的公共交通迟出发但是也能在10:30之前到, 而且总时间更少, 而且换乘数也更少：
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
这个图是一个有向无环图(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') -- 第二个联通部分
), 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;
很容易发现closure是一个对称的关系(symmetric relation):
这时候我们用UNION ALL是肯定不会终止的，因为UNION ALL采用包语义(Bag Semantics)，它不会消除重复(duplicates)。
而UNION采用集合语义(Set Semantics)，它会消除重复。
该文章遵循创作共用版权协议 CC BY-NC 3.0，要求署名、非商业 、保持一致。在满足创作共用版权协议 CC BY-NC 3.0 的基础上可以转载，但请以超链接形式注明出处。文章仅代表作者的知识和看法，如有不同观点，可以回复并讨论。
