Processing Implication on Queries
Xian‐He Sun, Nabil N. Kamel, Lionel Ming-shuan Ni · IEEE Transactions on Software Engineering · 1989
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 σT, 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. © 1989 IEEE