Lab 11: SQL

Table of Contents

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.

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!