dimanche 22 mars 2015

SQL query for paths between two states that contain only landlocked states

This is a homework question from Berkeley CS61A(SICP) regarding an SQL query. The idea is to generate paths built out of a chain of adjacent states, where the intermediate states are all landlocked. First, here is the code:



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;

select * from inland_distances where start="CA" and end="WA";


Preliminary info: s1, s2 are columns in the adjacencies table, which lists adjacent states.


Now, I understand the concept of generating a table of chains of landlocked states (of length less than 8), and then attaching a state adjacent to start state at the beginning, and a state adjacent to the final state at the end. What is bothering me is the line:



select s1 as start, s2 as end, 2 as hops from adjacencies union


I though the meaning of this statement is that I might be looking for a path consisting of two adjacent states with no intermediate states, so I should include all the adjacent states in my final table, but then why is "hops" set to 2 and not to 1? Also, when I try commenting out that line, a ton of more rows appear in my table, which seems strange to me because union-ing should INCREASE the number of rows, right? Thanks in advance.


Aucun commentaire:

Enregistrer un commentaire