CSE 350: Advanced Database Topics
Fall 2003, Dina Q Goldin

Homework 2
due 10/14/03

• For Datalog coding problems, you are expected to test your queries and to debug them until they are correct. Remember – queries are correct if they work for all databases, not just the ones we give you.

• Try to make your Datalog programs as simple (as few rules) as possible.  Feel free to reuse the same subqueries for the different queries within the same problem.
• Please email the code as ASCII attachments to <dqg@cse.uconn.edu>. Also, submit a hardcopy printout of these files with the rest of HWK3.

Problem 1.

Express the queries from HWK 1, Problem 1 in Datalog.  Name this file “xxx_pr1hwk2.P”, where xxx is your last name.  (You can test your queries on the College Database file we have provided for you, but remember – it should work for all database instances!)

Problem 2.

(i)        Create a Datalog database “xxx_db2.P” (where xxx is your last name) for the Train and Plane connections between cities, consisting of two relations Train(city, next_city) and Plane(city, next_city).  Populate it with the following facts:

train(boston,providence).

train(providence,new_haven).

train(new_haven,new_york).

train(new_york,philadelphia).

train(philadelphia,washington).

plane(boston,new_york).

plane(new_york,washington).

plane(providence,philadelphia).

plane(boston,hartford).

plane(hartford,philadelphia).

plane(portland,boston).

(ii)        Write a stratified Datalog program to answer the following queries, creating a file “xxx_pr2hwk2.P”. You are encouraged to reuse earlier predicates when defining later ones.

(a)  train_only(a,b): Find the pairs of stations (a,b) such that one can go from a to b by train but not by plane.

(b)  pure_plane_path(a,b): a pure plane path from a to b is a plane itinerary from a to b such that for all consecutive stops c,d along the way, one cannot go from c to d by train.  Find the pairs of stations (a,b) such that there is a pure plane path from a to b.

(c)  neither_alone(a,b): Find the pairs of stations (a,b) such that b can be reached from a by some combination of plane or train, but not by either train or plane alone.

(iii)       Show the predicate dependency graph for part (ii)

Problem 3.

Redo Problem 2(ii) in Recursive SQL (as proposed in the handouts we studied)

Problem 4.

Prove the model intersection property (Lemma 8.8, page 193 of textbook).

Problem 5.

This problem deals with topic covered in the guest lecture by Prof. Shvartsman, on Sep. 16. The topic deals with replicated consistent object implementation (he handed out several copies of a paper and gave web search keywords.)

In the lecture, 2-phase algorithms were given for read and write operations on atomic (aka linearizable) replicated objects. Each phase access a majority (or a quorum) of replicas.

Consider what happens if all agents have a GPS (global positioning system) device that provides global time to the agents (same time for all agents).

(a)    Does this allow us to simplify the algorithm for write?  If yes, how and why? If not, why not?

(b)    What about the algorithm for read? If yes, how and why? If not, why not?