When the inputs are conjunctive queries with #, 5, or < as built-in predicates, the query containment problem 'is Qr 5 Qz?,, is I$-complete and, thus, highly intractable.In this paper, we investigate the impact of syntactic and structural conditions on the computational complexity of tho query containment problem for safe conjunctive queries with discquation # as a built-in predicate.In the case of Np~r~', conjunctive queries (no built-in predicates), it is known that the boundary between polynomial-time solvability and NP-completeness is crossed, when the number of occurrcnccs of any database predicate in Qr increases from two to three, We show here that, as regards safe conjunctivc qucrics with disequations, the same syntactic condition dolincatcs the boundary between membership in coNP and II?$completencss,Moreover, it is also known that the "pure" conjunctive query containment problem is solvable in polynomial time, if the hypergraph associated with the database predicates of Qz is acyclic.In contrast, we show that the vory samo structural condition does not lower the computational complexity of the containment problem for safe conjunctivc queries with disequations, that is, the problem remnins II~completc.We also analyze the computational complexity of the quary equivalence problem for conjunctive queries with disequations, when one of the two queries is fixed.We show that this problem can be DP-complete, where DP is the class of nil decision problems that are the conjunction of a problem in NP and a problem in coNP.It follows that, as regards conjunctive queries with disequations, the complexity of the query cquivalcncc problem may be higher than the complexity of the query containment problem, when one of the two qucrics is fixed.

Structural approximation theory seeks to provide a framework for expressing optimization problems, and isolating structural or syntactic conditions that explain the (apparent) difference in the approximation properties of different NP-optimization problems. In this paper, we initiate a study of structural approximation using integer programming (an optimization problem in its own right) as a general framework for expressing optimization problems. We isolate three classes of constant-approximable maximization problems, based on restricting appropriately the syntactic form of the integer programs expressing them. The first of these classes subsumes MAX /spl Sigma//sub 1/, which is the syntactic version of the well-studied class MAX NP. Moreover, by allowing variables to take on not just 0/1 values but rather values in a polylogarithmic or polynomial range, we obtain syntactic maximization classes that are polylog-approximable and poly-approximable, respectively. The other two classes contain problems, such as MAX MATCHING, for which no previous structural explanation of approximability has been found.