Homework 3 (due 4/22)
CSC 543

We covered material on spatial networks and how they can be represented in SQL and Oracle specifically. Some of this material is in chapter 6 of Shekhar, Chawla's Spatial Databases, a Tour. More advanced material (some of which we'll talk about next time) is in chapter 10 of Pro Oracle Spatial, by Kothuri, Godfrind and Beinat , Apress, 2004 (available online through books 24 x 7 at the library).

I distributed the document How to get SQLDeveloper and set up your Oracle Account, which describes how to set up your oracle account and use SQLDeveloper to access it (as I did in class). (You can use your own system if you prefer, however, the class examples will be geared towards Oracle's version of SQL; some of the spatial features we'll see later will require recent versions of Oracle.)

For a quick reference on PL/SQL, see techonthenet, for some simple PL/SQL examples, see Ullman's page (for loops with cursors we don't use fetch though, the "for cursor in ..." paradigm is easier).

Submission: you can submit the homework by hardcopy in class or by sending it to me as an email.

1. [CONNECT_BY, 20pt] Here's a partially fictitious miniworld:

Students have a unique ID and name. Classes have a unique ID and name, some classes require other classes as prerequisites, e.g. CSC 212 requires CSC 211, CSC 383 requires CSC 212, and CSC 421 requires CSC 202 and CSC 383. In other words, each class has a list of immediate prerequisites (e.g. the list for CSC 421 contains CSC 202 and CSC 383, the list for CSC 202 is empty), meaning all the courses on the list should have been taken before enrolling in the requiring course. Students enroll in a particular class in a particular quarter of a particular year.

Implement a small database (around 10 students, 10 classes, 10 enrollments) and write a query that verifies for a given student and class that the student has fulfilled all the prerequisites of the class, where we now check even prerequisites of prerequisites, and so on. E.g. a student enrolled for CSC 421 must have taken CSC 202 and CSC 383, but also CSC 212 (since that's required by CSC 383) and CSC 211 (since that's required by CSC 212).

For extra credit make the prerequisite structure more realistic (e.g. the real prerequisite of CSC 421 is CSC 202 and (CSC 383 or CSC 393), that is allow or conditions).

2. [Some Topological Queries] Upload the simplified CTA network (the version without geometric data).

a) [10pt] Write a query that lists all stops reachable from Howard using only brown and red lines.

b) [10pt] Write a function that, given a station as input, computes how many stations are exactly one stop away from that station.

c) [Extra Credit] Write a query (in SQL or PL/SQL) that given two stations returns the shortest connection between the two stations and also tells you how often you have to change lines.

d) [Extra Credit] For a given station the largest distance of any other station is a measure of how central the station is. Call a station central if it minimizes the largest distance of any other station. E.g. 95th clearly is not central (the largest distance of any other station from it is 5: Cottage Grove, obviously Adams beats that, but Adams isn't central either). Write a query that returns all central stations (functions might come in handy).

3. [Some Geometric Queries] Upload the simplified CTA network (with geometric data) we saw in class.

a) [10pt] Write a query that finds the station that has the largest number of stations within a mile of it. (As part of the SQL establishing the network you get a function Euclid that calculates the distance between two stations.)

b) [10pt] Write PL/SQL for a function that, given a station, finds the station closest to it (other than itself).

c) [Extra Credit] Extend your function from b) to take a second argument k and return the kth-closest station (so b solves the special case k = 1).

Marcus Schaefer
Last updated: April 15th, 2009.