Processing Implication on Queries.

The ability to quickly determine how to derive a given query from a set of prestored fragments is highly demanded in many database applications, especially in distributed database systems, where the communication cost is a major concern. The main difficulty in solving this problem lies in the implication problem-given two predicates σQ and σT, can σQ imply σT(σQ → σT? The implication problem has been solved by converting it into a satisfiability problem. No detailed study of the implication problem on its own has been presented. In this paper, we study the general implication problem in which all six comparison operators: =, ≠, <, >, ≤, >, as well as conjunctions and disjunctions are allowed. We proved that the general implication problem is NP-hard. In the case when "≠" operators are not allowed in σQ and disjunctions are not allowed in σQ a polynomial time algorithm is proposed to solve this restricted implication problem. The influence of the "≠" operator and disjunctions are studied. Our theoretical results show that for some special cases the polynomial complexity algorithm can solve the implication problem which allows the "≠" operator or disjunctions in the predicates. Necessary conditions for detecting when the "≠" operator and disjunctions are allowed are also given. These results are very useful in creating heuristic methods. [ABSTRACT FROM AUTHOR]