  In this paper, we study the complexity of answering conjunctive queries (CQ)
with inequalities). In particular, we are interested in comparing the
complexity of the query with and without inequalities. The main contribution of
our work is a novel combinatorial technique that enables us to use any
Select-Project-Join query plan for a given CQ without inequalities in answering
the CQ with inequalities, with an additional factor in running time that only
depends on the query. The key idea is to define a new projection operator,
which keeps a small representation (independent of the size of the database) of
the set of input tuples that map to each tuple in the output of the projection;
this representation is used to evaluate all the inequalities in the query.
Second, we generalize a result by Papadimitriou-Yannakakis [17] and give an
alternative algorithm based on the color-coding technique [4] to evaluate a CQ
with inequalities by using an algorithm for the CQ without inequalities. Third,
we investigate the structure of the query graph, inequality graph, and the
augmented query graph with inequalities, and show that even if the query and
the inequality graphs have bounded treewidth, the augmented graph not only can
have an unbounded treewidth but can also be NP-hard to evaluate. Further, we
illustrate classes of queries and inequalities where the augmented graphs have
unbounded treewidth, but the CQ with inequalities can be evaluated in
poly-time. Finally, we give necessary properties and sufficient properties that
allow a class of CQs to have poly-time combined complexity with respect to any
inequality pattern. We also illustrate classes of queries where our
query-plan-based technique outperforms the alternative approaches discussed in
the paper.
