| Abstract
|
We consider the problems of query-reachabi … We consider the problems of query-reachability and satisfiability indatalog programs with negation and dense-order constraints. Theseproblems are important in the context of optimization, since solvingthem can detect extraneous rules and predicates. Satisfiability wasshown decidable for pure datalog programs~\cite{Shmu87}; decidabilityfor datalog with dense-order constraints follows from the workof~\cite{KKR90}. Query-reachability was shown decidable for datalogwith dense-order constraints~\cite{LS92}. In this paper, we show thatboth query-reachability and satisfiability are decidable for datalogprograms with dense-order constraints and safe stratified negationprovided that negation is applied only to EDB predicates, or all EDB predicates are unary. We also give a new undecidability result for satisfiability that impliesa new undecidability result for both query-reachability andequivalence. These undecidability results apply to datalog programswith unary IDB predicates, negation, and the interpreted predicate$\not=$. In comparison, note that equivalence is decidable fordatalog programs with only unary IDB predicates (and neither negationnor interpreted predicates)~\cite{CGKV88}.In proving some of the decidability results, we use a rather powerfultool, the {\em query-tree,} which was first used in~\cite{LS92}. Aquery-tree is a finite structure that encodes all symbolic derivationtrees (of a datalog program $P$) that satisfy some given property.Query-trees can also be viewed as a refinement of tree automatatechniques for the special purpose of representing symbolic derivationtrees of datalog programs. The importance of tree-automata techniquesfor decision problems of datalog programs was shown in~\cite{Vard89}.Query-trees can be used not just for decision problems, but also foranalyzing datalog programs and transforming those programs into moreefficient ones. For example, using query-trees, it is rather easy topush the tightest possible constraints to the EDB, and to useconstraints most efficiently during a magic-set evaluation.Conceivably the same could be done by applying tree-automatatechniques directly, but doing so would be considerably moreintricate. So, in essence, our results do not merely provide newdecidable cases, but also imply how to push constraints in thosecases. ply how to push constraints in thosecases.
|
