Given a consistent knowledge base formed by a set of constraints, effi
cient query answering (e.g., checking whether a set of constraints is
consistent with the knowledge base or necessarily true in it) is pract
ically very important. In the paper we consider bounds on differences
(which are an important class of constraints based on linear inequalit
ies) and we analyze the computational complexity of query answering. M
ore specifically, we consider various common types of queries and we p
rove that if the minimal network produced by constraint satisfaction a
lgorithms (and characterizing the solutions to a set of constraints) i
s maintained, then the complexity of answering a query depends only on
the dimension of the query and not on the dimension of the knowledge
base (which is usually much larger than the query). We also analyse ho
w the approach can be used to deal efficiently with a class of updates
to the knowledge base. Some applications of the results are sketched
in the conclusion.