for decision problems of datalog programs was shown in [Var89]. Conceivably the results we present could be obtained by applying tree-automata techniques directly, but doing so would be considerably more intricate.
2 Satisfiability, Query-Reachability and
In this paper we consider datalog programs that may have safe stratified negation and dense-order constraints (i.e., the interpreted predicates 6=, =, <, and <=). Note that = is naturally expressed in datalog by using multiple occurrences of the same variable.
A datalog program P has IDB and EDB predicates, and one of the IDB predicates is the query predicate. The result of a datalog program P for an EDB D, denoted P (D), is the relation computed for the query predicate when P is applied to D. It is convenient to assume that distinct programs have disjoint sets of IDB predicates. We denote programs by upper case letters (possibly with a subscript); the corresponding lower case letter denotes the program's query predicate (e.g., P1 and p1).
We investigate four properties of datalog programs: satisfiability, query-reachability, equivalence and containment.
Definition 2.1 (Satisfiability): An IDB predicate s of a program P is satisfiable if there is some EDB D, such that P defines a nonempty relation for s. 2
Definition 2.2 (Query-Reachability): Consider an atom q( 1; : : : ; n) where q is either an EDB or IDB predicate and each i is either a variable or a constant. The atom q( 1; : : : ; n) is query-reachable with respect to program P if for some EDB D, there is a derivation tree d of a fact for the query predicate p, such that the derivation tree d has a positive ground atom that matches q( 1; : : : ; n). 2
Definition 2.3 (Containment and Equivalence): A program P1 is contained in a program P2, written P1 ? P2, if for all EDBs D, P1(D) ? P2(D). Programs P1 and P2 are equivalent, written P1 ? P2, if P1 ? P2 and P2 ? P1. 2
The problems of equivalence, containment, satisfiability and query-reachability are closely related. The rest of this section investigates the relations between the problems, summarized in Figure 1.
Containment and Equivalence
Proposition 2.1 An instance P1 ? P2 of the containment problem can be reduced to an instance P1 ? P2 of
the equivalence problem without introducing negation or increasing the arity of predicates.
An instance P1 ? P2 of the equivalence problem can be reduced to (1) an instance P1 ? P2 of the containment problem by either increasing the arity of predicates or introducing negation, or (2) two instances P1 ? P2 and P2 ? P1 of the containment problem. 2
Satisfiability and Query-Reachability
Proposition 2.2 An instance of the satisfiability problem can be reduced to an instance of the query-reachability problem without introducing new rules or predicates. 2
Lemma 2.3 An instance of the query-reachability problem can be reduced to an instance of the satisfiability problem by doubling the arity of the predicates. 2
Equivalence and Satisfiability
The following relates the satisfiability problem to the complement of the equivalence and containment problems (P1 6? P2 and P1 6? P2).
Proposition 2.4 An instance of the satisfiability problem can be reduced to either an instance of the form P1 6? P2 or an instance of the form P1 6? P2 by introducing one new trivial rule. 2
Lemma 2.5 An instance P1 6? P2 can be reduced to an instance of the satisfiability problem by adding rules that apply negation just once to a 0-arity predicate and do not increase the arity of predicates. 2
Finally, since it follows from [Shm87, UV88] that both containment and equivalence are undecidable for datalog programs with binary IDB predicates (and no negation or interpreted predicates), we get the following.
Corollary 2.1 Query-reachability and satisfiability are undecidable for datalog programs with binary (and 0- arity) IDB predicates and stratified negation; a single occurrence of negation, in a rule of the form q :? q1; :q2 (where q, q1, and q2 are 0-arity predicates) is sufficient for undecidability. 2
In Section 5 we prove a result that implies the following theorem.
Theorem 2.2 Containment, equivalence, query reachability, and satisfiability are all undecidable for datalog programs with unary (and 0-arity) IDB predicates, negation on nonrecursive predicates, and <>. The usage of <> can be eliminated by introducing a pair of binary nonrecursive IDB predicates. 2