We consider the problem of querying key-value stores in thepresence of semantic constraints, expressed as rules on keys, whose pur-pose is to establish a high-level view over a collection of legacy databases.We focus on the rewriting-based approach for data access, which is themost suitable for the key-value store setting because of the limited ex-pressivity of the data model employed by such systems. Our main con-tribution is a parallel technique for rewriting and evaluating tree-shapedqueries under constraints which is able to speed up query answering. Weimplemented and evaluated our parallel technique. Results show signif-icant performance gains compared to the baseline sequential approach.