Processing Implications on Queries

Abstract-The ability to quickly determine how to derive a given query from a set of prestored fragments is highly demanded in many database appliratlons, especially in distributed database syslems. where the communication cost is a major concern. The main difficulty in snlv-ing this problem lies in the implkation problem-given t w o predicates av and or, can ay imply ar(ap + ar)? The implication problem has been solved by cunverting it into a iatisfiability 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 com-parlson operators: =, #, <,>, S. Z, as well as conjunctions and disjunctions are allowed. We proved that the general implication prob-lem is NP-hard. In the case when ‘ ‘ # ” operators are not allowed in uv and disjunctions are not allowed In or, a polynomial time algcwithm is proposed to solve this restrkted implication problem. The influence of the ‘‘# ” operator and disjunctions are studied. Our theoretical re-sults show that for some special cases the polynomial complexity nl-gorithn can solve the implication problem which allows the “ # ” op-erator 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. Index Terms-Database. derivability problem, directed graph, im-plication problem, mathematical lugic, NP-hard, project-select-join queries, satisfiability. I