Computer implemented methods for identifying denial constraints are provided herein. The denial constraints can be used with a database schema R. A predicate space P can be generated for an instance I in the schema R. An evidence set EviI can be generated. The evidence set EviI can include sets of satisfied predicates in the predicate space P for each instance I. A minimal set of predicates can be identified for the evidence set EviI. Valid denial constraints can be identified from the minimal set by inverting the predicates in the minimal set.