Recursion and Datalog

Question 1

_______ languages extend query languages with recursion

Answer 1

datalog

Question 2

The _______ in a datalog rule contains predicates over variables and constants

Answer 2

head

Question 3

The _______ in a datalog rule contains conjunctions of possibly negated items

Answer 3

body

Question 4

Head variables are implicitly _________ quantified

Answer 4

universally

Question 5

Body variables are implicitly _________ quantified

Answer 5

existentially

Question 6

In datalog rules, if the _______ is true, the ______ is true

Answer 6

body, head

Question 7

Translate the datalog rule Lucky(x) :- Customer(x, y, z), Account(u, z, x, w), w > 10000 to RC

Answer 7

Lucky = { x | 9y, z, u, w Customer(x, y, z)^ Account(u, z, x, w) ^ w > 10000}

Question 8

When converting from datalog to RC, for safety’s sake, every variable in the _____ or ______ needs to appear in one non-negated ___________ atom

Answer 8

Head, body, relational

Question 9

A datalog program is a _____ of datalog rules

Answer 9

set

Question 10

Extensional DB relations are __________ in the database

Answer 10

stored

Question 11

Intensional DB relations are __________ relations

Answer 11

derived

Question 12

EDB relations appear in the _____ of rules

Answer 12

body

Question 13

IDB relations appear in the ____ or _____ of rules

Answer 13

head, body

Question 14

Translate projection_(#2)(R) to datalog

Answer 14

E(x) :- R(y, x)

Question 15

Translate selection_(#1 op c)(R) to datalog

Answer 15

E(x, y) :- R(x, y), x op c

Question 16

Translate R x S to datalog

Answer 16

E(x, y, w, z) :- R(x, y), S(w, z)

Question 17

Translate R - S to datalog

Answer 17

E(x, y) :- R(x, y), ¬S(x, y)

Question 18

Translate R U S to datalog

Answer 18

E(x, y) :- R(x, y) and

E(x, y) :- S(x, y)

Question 19

The head relation of a ______ can appear in its body

Answer 19

rule

Question 20

IDB predicate _______ ____ predicate Q

Answer 20

depends on

Question 21

In a dependency graph, ______ are IDB predicates, and _______ are the dependencies P -> Q

Answer 21

nodes, edges

Question 22

A _______ in the dependency graph means the datalog program as recursive

Answer 22

cycle

Question 23

The _____ never changes

Answer 23

EDB

Question 24

The _____ is initially empty

Answer 24

IDB

Question 25

What is a fixed point?

Answer 25

When the next step of a recursion equals the previous step

Question 26

Recall the SQL query to mimic the ancestor parent datalog rule:
Ancestor(x, y) :- Parent(x, y)
Ancestor(x, y) :- Ancestor(x, z), Parent(z, y)

Answer 26

WITH RECURSIVE Ancestor(name, descendant) AS (
SELECT *
FROM Parent
UNION
SELECT A.name, P.child
FROM Ancestor A, Parent P
WHERE A.descendant = P.name
)
SELECT * FROM Ancestor ;

Question 27

In ___________ recursion, the head relation appears more than once in its body

Answer 27

nonlinear

Question 28

Nonlinear recursion is not _________ in SQL

Answer 28

supported

Question 29

A recursive program with no ________ never ends

Answer 29

fixpoint

Question 30

If a relation S is used positively in the definition of R

then S must be defined ________ or ______________ with R

Answer 30

earlier, simultaneously

Question 31

If a relation S is used __________ in the definition of R

then S must be defined strictly before R

Answer 31

negatively

Question 32

A stratum graph is similar to a dependency graph except that edges are labelled with a “-“ if it is a ________ subgoal

Answer 32

negated

Question 33

A _________ program has no cycle involving at least one negated edge

Answer 33

stratified

Question 34

SQL recursion requires ________ negation and only uses ______ recursion

Answer 34

stratified, linear