This lab is due at 11:59pm on 12/03/2014.
When you are done with this lab, submit Questions 1-4 (provided in the starter file lab11.sql). Please also download states.sql, which contains the data needed for this lab. The rest are questions that are considered extra practice — they can be found in the the lab11_extra.sql file. It is recommended that you complete these problems in your own time.
In this lab, we will be writing recursive SQL queries on a database containing the adjacency information between the 48 mainland states and Washington DC.
First take a look at states.sql
and how the tables in it are structured. There
are three main tables that you will be querying.
states
: US States + DC - HI - AK, represented by their two letter
abbreviations.adjacencies
: All pairs of states that are adjacent to each otherlandlocked
: Landlocked (not adjacent to ocean) statesYou will write all your solutions in this lab in the starter file provided. To run your solutions, you can either of the following commands:
$ sqlite3 < <filename>.sql
$ sqlite3 --init <filename>.sql
As a warm-up, write a query that selects all the states adjacent to California. You should get the following output:
CA|AZ
CA|NV
CA|OR
select * from adjacencies where s1 = "CA";
Create a new table distances
, which contains the lengths of all the possible
paths with less than or equal to 15 border crossings between any two states. For
example, we can get from California to Texas with 3 crossings by passing through
Arizona and New Mexico, but we can also get there taking a different path using
more border crossings. The following query should return the lengths of possible
paths between CA and WI:
sqlite3> select * from distances where start = "CA" and end = "WI" order by hops;
CA|WI|6
CA|WI|7
CA|WI|8
CA|WI|9
CA|WI|10
CA|WI|11
CA|WI|12
CA|WI|13
CA|WI|14
CA|WI|15
You will need to write recursive SQL queries to build up this table, starting with paths with one border crossing.
create table distances as
with
distance(start, end, hops) as (
select s1, s2, 1 from adjacencies union
select path.start, hop.s2, path.hops + 1
from distance as path, adjacencies as hop
where path.end = hop.s1 and
path.hops < 15
)
select * from distance;
select end from distances where start = "CA" and hops = 3;
An alphabetical path is a path between a sequence of states, visiting each state in alphabetical order. Write a query that finds all the alphabetical paths with 6 or more hops. Your query should output:
IA,IL,IN,KY,MO,NE,SD,WY
IA,IL,IN,KY,MO,TN,VA,WV
AL,FL,GA,NC,TN,VA,WV
IA,IL,IN,KY,MO,NE,SD
IA,IL,IN,KY,MO,NE,WY
IA,IL,IN,KY,MO,OK,TX
IA,IL,IN,KY,MO,TN,VA
IA,IL,IN,KY,OH,PA,WV
IA,IL,IN,KY,TN,VA,WV
IA,IL,IN,MI,OH,PA,WV
IA,IL,KY,MO,NE,SD,WY
IA,IL,KY,MO,TN,VA,WV
IL,IN,KY,MO,NE,SD,WY
IL,IN,KY,MO,TN,VA,WV
Remember you can use the ||
operator in SQL to concatenate two strings, and
comparison operators such as <
or >
to find out the alphabetical order of
two strings.
with
paths(s, n, last) as (
select state, 1, state from states union
select s || "," || s2, n+1, s2
from paths, adjacencies where s1=last and s1 < s2
)
select s from paths where n > 6 order by -n;
Create a table inland_distances
, which contains the lengths of possible paths
with less than 10 border crossings between two states that enter only landlocked
states along the way. We can then find the lengths of inland paths between CA
and WA:
sqlite3> Lengths of inland paths between CA and WA:
CA|WA|3
CA|WA|4
CA|WA|5
CA|WA|6
CA|WA|7
CA|WA|8
CA|WA|9
CA|WA|10
We can also find the states that are 2 inland hops from CA:
sqlite3> select end from inland_distances where start = "CA" and hops = 2;
AZ
CA
ID
NM
NV
OR
UT
create table inland_distances as
with
inland(start, end, hops) as (
select state, state, 0 from landlocked union
select start, s2, hops + 1
from inland, adjacencies, landlocked
where end = s1 and s2 = state and hops < 8
)
select s1 as start, s2 as end, 2 as hops from adjacencies union
select start.s1 as start, end.s2 as end, hops+2 as hops
from adjacencies as start, adjacencies as end, inland
where start.s2 = start and end.s1 = end;
This lab is shorter than usual, so if you've finished early, feel free to work on the homework!