Consider the following rules:

 

reachable(X,Y) :- flight(X,Y)

reachable(X,Y) :- flight(X,Z), reachable(Z,Y)

where reachable (X, Y) means that city Y can be reached from city X, and flight(X, Y) means that there is a flight to city Y from city X.

a. Construct fact predicates that describe the following:

i. Los Angeles, New York, Chicago, Atlanta, Frankfurt, Paris, Singapore, Sydney are cities.

ii. The following flights exist: LA to NY, NY to Atlanta, Atlanta to Frankfurt, Frankfurt to Atlanta, Frankfurt to Singapore, and Singapore to Sydney. Singapore to Sydney.

b. Is the given data cyclic? If so, in what sense?

c. Construct a model theoretic interpretation (that is, an interpretation similar to the one shown in Figure 25.3) of the above facts and rules.

d. Consider the query reachable(Atlanta,Sydney)? How will this query be executed using naive and seminaive evaluation? List the series of steps it will go through.

e. Consider the following rule-defined predicates:

round-trip-reachable(X,Y) :- reachable(X,Y), reachable(Y,X) duration(X,Y,Z)

Draw a predicate dependency graph for the above predicates.

f. Consider the following query: What cities are reachable in 12 hours from Atlanta? Show how to express it in Datalog. Assume built-in predicates like greater-than(X, V). Can this be converted into a relational algebra statement in a straightforward way? Why or why not?

g. Consider the predicate population(X, Y) where Y is the population of city X. Consider the following query: List all possible bindings of the predicate pair (X,V), where Y is a city that can be reached in two flights from city X, which has over 1 million people. Show this query in Datalog, Draw a corresponding query tree in relational algebraic terms.