  Learning constraint networks is known to require a number of membership
queries exponential in the number of variables. In this paper, we learn
constraint networks by asking the user partial queries. That is, we ask the
user to classify assignments to subsets of the variables as positive or
negative. We provide an algorithm, called QUACQ, that, given a negative
example, focuses onto a constraint of the target network in a number of queries
logarithmic in the size of the example. The whole constraint network can then
be learned with a polynomial number of partial queries. We give information
theoretic lower bounds for learning some simple classes of constraint networks
and show that our generic algorithm is optimal in some cases.
