We propose the PSDD as a probabilistic graphical model for domains that are subject to massive logical constraints. Each parameter of a PSDD can be viewed as the probability of making a decision in a corresponding Sentential Decision Diagram (SDD), which is a recently proposed representation of logical constraints. We explore a number of interesting properties of PSDDs, including the independencies that underlie them. We show that the PSDD is a tractable representation, allowing one to compute probabilistic queries in time linear in the PSDD size. We further show how the parameters of a PSDD can be efficiently estimated, in closed form, from complete data. We empirically evaluate the quality of PSDDs learned from data, when we have knowledge, a priori, of the domain logical constraints.