Consider the following rules:
reachab \(\operatorname{le}(X, Y):-f 7 i g h t(X, Y)\)
reachable \((X, Y):-\text { flight }(X, Z), \text { reachab }\rceil e(Z, Y)\)
where reachable \((X, Y)\) means that city \(Y\) can be reached from city \(X,\) and
f7ight \((\mathrm{X}, \mathrm{Y})\) means that there is a flight to city \(Y\)
from city \(\mathrm{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. (Note: No flight in reverse direction can be automatically assumed.)
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(AtTanta, 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):-\) reachab 7 e \((X, Y),\) reachab 7 e \((Y, X)\)
duration \((x, Y, z)\)
Draw a predicate dependency graph for the above predicates. (Note:
dura\(\operatorname{tion}(X, Y, Z)\) means that you can take a flight from \(X\)
to \(Y\) in \(Z\) hours.
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, Y) .\) 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 \((\mathrm{X}, \mathrm{Y}),\) where \(\mathrm{Y}\) is a city that can be
reached in two flights from city \(\mathrm{x}\) which has over 1 million people.
Show this query in Datalog. Draw a corre. sponding query tree in relational
algebraic terms.
