We demonstrate that, ignoring computational constraints, it is possible to release privacy-
preserving databases that are useful for all queries over a discretized domain from any given 
concept class with polynomial VC-dimension.  We show a new lower bound for releasing databases 
that are useful for halfspace queries over a continuous domain.  Despite this, we give a 
privacy-preserving polynomial-time algorithm that releases information useful for all halfspace
queries, for a slightly relaxed definition of usefulness.  Inspired by learning theory, we 
introduce a new notion of data privacy, which we call distributional privacy, and show that it 
is strictly stronger than the prevailing privacy notion, differential privacy.