ON SATISFIABILITY, EQUIVALENCE, AND IMPLICATION PROBLEMS INVOLVING CONJUNCTIVE QUERIES IN DATABASE-SYSTEMS

Satisfiability, equivalence, acid implication problems involving conju nctive queries are important and widely encountered problems in databa se management systems. These problems need to be efficiently and effec tively solved. In this paper, we consider queries which are conjunctio ns of the inequalities of the form (X op C), (X op Y), and/or (X op Y + C), where X and Y are two attributes, C is a constant, and op epsilo n/<,less than or equal to,=,not equal,>,greater than or equal to/. The se types of inequalities are widely used in database systems, since th e first type is a selection, the second type is a theta-join, and the third type is a very popular clause in a deductive database system. Th e satisliability, equivalence, and implication problems in the integer domain (for attributes and constants) have been shown to be NP-hard [ 20], [24]. However, we show that these problems can be solved efficien tly in the real domain. The incorporation of the real domain is signif icant, because the real domain is practically and widely used in a dat abase. Necessary and sufficient conditions and algorithms are presente d. A novel concept of the ''module closure'' and a set of sound and co mplete axioms with respect to the ''module closure'' are also proposed to infer all correct and necessary inequalities from a given query. T he proposed axioms generalize Ullman's axioms [27] where queries only consist of theta-joins.