CSE 444 Homework 4

Objectives:
To understand and be able to manipulate datalog queries
Reading Assignments:
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)
Please answer the following questions
[No points this time, but we'd appreciate answers]
  1. How long did it take you to complete this assignment?
  2. What did you like the best about this assignment?
  3. What did you like the least about this assignment?
  4. What helped you learn the best in this assignment?