Abstract. We study the problem of answering queries over sources with limited access patterns. The problem is to decide whether a given query Q is feasible, i.e., equivalent to an executable query Q' that observes the limited access patterns given by the sources. We characterize the complexity of deciding feasibility for the classes CQ-neg (conjunctive queries with negation) and UCQ-neg (unions of CQ-neg queries): Testing feasibility is just as hard as testing containment and therefore Pi_2^p-complete. We also provide a uniform treatment for CQ, UCQ, CQ-neg, and UCQ-neg by devising a single algorithm which is optimal for each of these classes. In addition, we show how one can often avoid the worst-case complexity by certain approximations: At compile-time, even if a query Q is not feasible, we can find efficiently the minimal executable query containing Q. For query answering at runtime, we devise an algorithm which may report complete answers even in the case of infeasible plans and which can indicate to the user the degree of completeness for certain incomplete answers.