# CSE 444 Homework 4

Objectives:
To understand and be able to manipulate datalog queries
4.2-4.4, 5.10
Number of points:
30
Due date:
November 8
Given the following schema:
Bus(x,y): there is a bus from city x to y.
Train(x,y): there is a train from x to y.
Flight(x,y): there is a flight from x to y.
Altitude(x,a): the altitude of the city x is a.

Write datalog queries to answer the questions below:

1. [5 points] Find all cities that have an altitude of less than 1000 feet
2. [5 points] Find all cities that can be reached from Seattle by a single leg of a journey (one plane flight, one bus trip, or one train trip)
3. [8 points] Find pairs of cities between which there is some connection via a combination of flights, buses and trains.
4. [7 points] Find pairs of cities between which there is some connection via a combination of flights, buses and trains, but the connection city is at monotonically increasing altitudes.

Intepretation of the question should be that if city x is an earlier city in the travel plan than city y, city x is always at a lower (or equal) altitude to city y.

So if we were going from Seattle, to Dallas, to San Francisco, and alt(x) is the altitude of city x, we require alt(Seattle) <= alt(Dallas) <= alt(San Francisco).

5. [5 points] Find pairs of cities between which there is some connection via a combination of flights, buses and trains, but between connection points the altitude difference is no more than 1000 feet.

### Extra credit [10 points]

Given the query q(x):-e1(x,y),e2(y,x), can you rewrite it using the following views, and if so, how (show your rewriting)? If not, why not?
set one:
v1(a,b):-e1(a,b)
v2(c,d):-e2(c,d)
set two:
v3(f):-e1(f,g)
v4(h):-e2(h,i)
set three:
v5(j,k):-e1(j,m),e2(m,k)