Query Languages

• Theorem 3. All FO+ and Datalog queries are eventually computable.

• The set of source-range-restricted variables in a Datalog rule r is the minimum set of variables in r satisfying

  • if R(u) occurs in the body of a rule, R is some idb predicate and x is one of the variables of u, then x is source-range-restricted
  • if x is the source constant or x is source-range-restricted and Ref(x,y,z) occurs in the body of the rule, then y,z are source-range-restricted, and
  • if x is the source constant or x is source-range-restricted and Val(x,y) occurs in the body of the rule, then y is source-range-restricted

• A rule is source-safe (ss) if all its variables are source-range-restricted. A program is source-safe is all its rules are source safe.

Previous slide

Next slide

Back to first slide

View graphic version