# Lab 11: SQL

## Submission

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.

## SQL

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 other
• `landlocked`: Landlocked (not adjacent to ocean) states

You 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``````

### Question 1

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";``

### Question 2

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;``````

### Question 3

Write a query that lists all the states 3 hops from California. Note that California itself is such a state.
``select end from distances where start = "CA" and hops = 3;``

### Question 4

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;``````

### Question 5

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;``````

## Homework

This lab is shorter than usual, so if you've finished early, feel free to work on the homework!