Datalog: recursion and negation

Recursive rules, evaluation up to the fixed point, safe rules, stratified negation and the SQL equivalent with WITH RECURSIVE.

23 cards
4 topics
Free

Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

Concepts
Questions
Sort and link
Scenarios

A few cards from the deck

Transitive closure: what is it?
Show the answer
The relation containing every pair linked by a path of any length in a starting relation.
If a→b and b→c, the closure also holds a→c. A single recursive rule computes it in Datalog, whereas a plain SELECT cannot.
Arcs: a→b, b→c, c→d. Rules: chemin(X, Y) :- arc(X, Y). and chemin(X, Z) :- arc(X, Y), chemin(Y, Z). How many chemin facts does the fixed point contain?
- 6
- 3
- 5
- 12
Show the answer
6
Round 1: (a,b), (b,c), (c,d). Round 2: (a,c) and (b,d). Round 3: (a,d). Round 4: nothing new. That is 3 + 2 + 1 = 6 pairs. 3 stops at the arcs, 5 misses (a,d), and 12, every pair of distinct nodes, would need arcs in both directions.
A Datalog program is evaluated round by round and stops when a round deduces …: that is the ….
Show the answer
A Datalog program is evaluated round by round and stops when a round deduces no new fact: that is the fixed point.
The last round only serves to observe that nothing changes any more.
Fixed point: what is it?
Show the answer
The set of facts reached when another round of applying the rules deduces nothing new.
Without functions or arithmetic, the number of possible facts is finite: evaluation always stops, even with cycles.
The engine rejects the rule p(X, Y) :- q(X). as unsafe. Which repair is right?
- p(X, Y) :- q(X), not r(Y).
- p(X, Y) :- q(X), r(X, Y).
- p(X, Y) :- not q(X).
- p(X, Y) :- q(X), Y > 0.
Show the answer
p(X, Y) :- q(X), r(X, Y).
Y must appear in a positive atom of the body to have a finite set of values, here r(X, Y). Neither a negation nor a comparison such as Y > 0 binds a variable.

Study this deck