Differentially private algorithms for answering database queries often involve reconstruction of a discrete distribution from noisy measurements. PRIVATE-PGM is a recent exact inference based technique that scales well for sparse measurements and provides consistent and accurate answers. However it fails to run in high dimensions with dense measurements. This work overcomes the scalability limitation of PRIVATE-PGM on dense data by relaxing consistency constraints. Our new approach works with many existing private query answering algorithms and improves scalability or accuracy with no privacy cost.