CS235 home

Homework 4

This week's exercise is an opportunity to write a transitive-closure-like result in the relational algebra, and thus run up against the limits of what is possible. Practically speaking, it illustrates the kind of scenario where the limits of SQL compel you to use a full-fledged programming language to answer a question about your data.

---

East Beast

Assume the existence of an airline called "East Beast." This airline's policy is to offer (domestic) eastbound flights only. This is perhaps not an entirely practical business plan, but it does have the advantage of avoiding cyclic digraphs.

Here is a schema for the East Beast database:

airports(code, name, city, state)
flights(num, src, dst)

"code" and "num" are the (textual) primary keys of the two relations, and "src" and "dst" are foreign keys referencing "code" in airports.

Tuples in the airports and flights relations look like this:

("SEA","Seattle/Tacoma International Airport","Seattle","WA")
("TUL","Tulsa International Airport","Tulsa","OK")

(111,"SEA","TUL")

Write relational algebra expressions to compute the following:

1. The names of the airports reachable from airport with code XYZ in one hop.
2. The names of the airports reachable from airport with code XYZ in two hops.
3. The names of the airports reachable from airport with code XYZ in three hops.
4. The names of the airports reachable from airport with code XYZ in one, two or three hops.

You may bind intermediate results to names across these problems to ease the presentation. In fact, please do. In other words, you are allowed to introduce names for expressions, and later refer to those expressions by those names:

T₁ = A ⋈ B
T₁ ⋈ C
...

Just use a sensible syntax for this, so your intended meaning is clear.

Having completed this exercise, you will appreciate that while you can extend this approach to compute airports reachable from XYZ in any finite number of hops, you cannot write an expression to compute all airports reachable in any number of hops.

---

As you proceed with the work, to develop and confirm your intuition, feel free to write SQL queries against the given database, and check your answers against the diagram given. (Add data to the database as you see fit as well.) As such, you can both build confidence in your results and get a sense of the correspondence between the relational algebra and SQL.

Any and all SQL hacking is not an official part of the homework.

PRAGMA foreign_keys = ON;

DROP TABLE IF EXISTS Flights;
DROP TABLE IF EXISTS Airports;

CREATE TABLE Airports (
  airportCode TEXT,
  name TEXT,
  city TEXT,
  state TEXT,
  PRIMARY KEY (airportCode)
);

INSERT INTO Airports 
VALUES ('SEA','Seattle/Tacoma International','Seattle','WA');

INSERT INTO Airports 
VALUES ('PDX','Portland International Airport','Portland','OR');

INSERT INTO Airports 
VALUES ('SMF','Sacramento International Airport','Sacramento','CA');

INSERT INTO Airports 
VALUES ('TUL','Tulsa International Airport','Tulsa','OK');

INSERT INTO Airports 
VALUES ('DLH','Duluth International Airport','Duluth','MN');

INSERT INTO Airports 
VALUES ('SAT','San Antonio International Airport','San Antonio','TX');

INSERT INTO Airports 
VALUES ('PVD','Theodore Francis Green Memorial State Airport','Providence','RI');

INSERT INTO Airports 
VALUES ('RIC','Richmond International Airport','Richmond','VA');

INSERT INTO Airports 
VALUES ('BTV','Burlington International Airport','Burlington','VT');

CREATE TABLE Flights (
  flightNumber INTEGER,
  src TEXT,
  dst TEXT,
  PRIMARY KEY (flightNumber),
  FOREIGN KEY (src) REFERENCES Airports (airportCode),
  FOREIGN KEY (dst) REFERENCES Airports (airportCode)
);

INSERT INTO Flights VALUES (111,'SEA','TUL');
INSERT INTO Flights VALUES (211,'PDX','TUL');
INSERT INTO Flights VALUES (311,'SMF','DLH');
INSERT INTO Flights VALUES (411,'DLH','PVD');
INSERT INTO Flights VALUES (511,'TUL','RIC');
INSERT INTO Flights VALUES (611,'TUL','BTV');
INSERT INTO Flights VALUES (711,'BTV','PVD');
INSERT INTO Flights VALUES (811,'PDX','SAT');
INSERT INTO Flights VALUES (911,'SAT','BTV');

---

This work is due by Monday, May 11 at 11:59pm. In a hw4 directory, please submit one or more tex source files, a Makefile, and a pdf hw4.pdf.