Methods for Identifying Denial Constraints
AssigneeQatar Foundation
InventorsPaolo PAPOTTI, Xu CHU
Life of this patent
Estimating the term…
Abstract
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.
Claims17
A computer implemented method of identifying denial constraints and correcting a database instance, the denial constraints being for use with a database schema R, the method comprising:
- generating candidate predicates using attributes of the database schema R;
- generating a predicate space P using the candidate predicates;
- determining a set of satisfied predicates using at least two tuples of the database instance, wherein the set of satisfied predicates are an evidence set;
- determining a minimal cover set for the satisfied predicates of the evidence set;
- deriving a set of valid denial constraints using the minimal cover set and inverse satisfied predicates for the minimal cover set;
- and
- correcting the database instance using the derived set of valid denial constraints.
A system operable to identify denial constraints and correct a database instance, the denial constraints being for use with a database schema R, the system comprising:
- a mechanism operable to generate candidate predicates using attributes of the database schema R and a predicate space P for an instance I in the schema R using the generated candidate predicates;
- a mechanism operable to determine a set of satisfied predicates using at least two tuples of the database instance I, wherein the satisfied predicates are an evidence set;
- a mechanism operable to identify a minimal set of predicates for the evidence set, and to identify valid denial constraints from the minimal set by inverting the predicates in the minimal set;
- and
- a mechanism to correct the database instance I using the identified denial constraints.
Dependencies are inferred from the claim text.