AG Datenbanken und Informationssysteme · Institut für Informatik · Universität Göttingen Database Theory Winter Term 2013/14 Prof. Dr. W. May 4. Unit: Datalog Discussion by 15./22.1.2014 Exercise 1 (Äquivalenz von Algebra und Datalog) Show that for every expression of the relational algebra there is an equivalent stratified Datalog program. Exercise 2 (Datalog to Algebra) Consider the translation of Datalog programs with a distinguished answer predicate to the relational algebra. • Given a rule B ← C1 ∧ . . . ∧ Cn ∧ Dn+1 ∧ Dn+k where the Ci are positive literals and the Di are negative literals, give an algebra expression that returns the relation defined by it. • Which additional construct must also be translated? • Consider the following program (arbitrary arity of predicates, each rule assumed to be safe): res(. . . ) :- p(. . . ), q(. . . ), ¬ r(. . . ). res(. . . ) :- p(. . . ), s(. . . ), ¬ t(. . . ). p(. . . ) :- u(. . . ), v(. . . ). p(. . . ) :- w(. . . ). t(. . . ) :- x(. . . ), y(. . . ). where q, r, s, u, v, w, x, y are EDB relations. Give the algebra expression that corresponds to the res predicate. Exercise 3 (Stratified Datalog) Give an example for the nonmonotonicity of the stratified semantics, show that for a stratifiable program P there can be multiple minimal models. Exercise 4 (Datalog-Anfragen an Mondial: Schweizer Sprachen) Give Datalog programs for the following queries against the Mondial database. Compare with the same queries in the algebra and in the relational calculus. a) b) c) d) All All All All codes codes codes codes of of of of countries countries countries countries in in in in which which which which some language is spoken that is also spoken in Switzerland. only languages are spoken that are not spoken in Switzerland. only languages are spoken that are also spoken in Switzerland. all languages are spoken that are spoken in Switzerland. Exercise 5 (Datalog-Anfragen an Mondial: Landlocked) • Give a Datalog program that returns the names of al countries that have no coast. • Give a Datalog program that returns the names of al countries that have no coast and that have no neighbor country that has any coast. • Give the dependency graph of your program. Asking ?- hasnonlandlockedneighbor(C) yields many countries several times, e.g., MK (Macedonia) three times since C2 can be bound by three ways to coastal neighbors: AL, GR, BG. This can be avoided by a Prolog cut in the “subquery” that searches for possible C2 bindings: Exercise 6 (Aggregation in Datalog/XSB) Define the aggregation operators in XSB in a module aggs.P. The syntax of the comparison predicates and of the arithmetic operators is given in Sections 3.10.5 (Inline Predicates) and 4.3 (Operators) of the XSB Manual Part I. Then use aggs.P for answering the following queries in Datalog: a) b) c) d) Give Give Give Give for each country the name and the number of neighbors. the name of the country that has the highest number of neighbors (and how many). the average area of all continents (to test avg). the average latitude and longitude of all cities.
© Copyright 2019 ExploreDoc