Methods for identifying denial constraints
AssigneeQatar Foundation
InventorsIhab Francis Ilyas Kaldas, Paolo 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.
Claims14
A computer implemented method of identifying denial constraints and correcting a database instance I, 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;
- correcting the database instance using the derived set of valid denial constraints;
- and
- providing a scoring function to provide a ranking of discovered denial constraints, wherein the scoring function comprises assigning an interestingness score Inter(φ) to each denial constraint φ, the score Inter(φ) being a weighted combination of succinctness and coverage of each denial constraint φ, wherein the discovered denial constraints having the interestingness scores below a threshold value are pruned.
A system operable to identify denial constraints and correct a database instance I, the denial constraints being for use with a database schema R, the system comprising:
- a hardware processor:
- an algorithm executed by the processor and 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;
- an algorithm executed by the processor and 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;
- an algorithm executed by the processor and 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;
- an algorithm executed by the processor to correct the database instance I using the identified denial constraints;
- and
- an algorithm executed by the processor to provide a scoring function to provide a ranking of discovered denial constraints,
- wherein the scoring function comprises assigning an interestingness score Inter(φ) to each denial constraint φ, the score Inter(φ) being a weighted combination of succinctness and coverage of each denial constraint φ, and wherein the discovered denial constraints having the interestingness scores below a threshold value are pruned,
- wherein the succinctness is defined as:
- Succ
-
- (
- φ
- )
- =
- Min
-
- (
- {
- Len
-
- (
- ϕ
- )
- |
- ∀
- ϕ
- }
- )
- Len
-
- (
- φ
- )
- ,
- wherein the coverage is defined as:
- Coverage
-
- (
- φ
- )
- =
- ∑
- k
- =
- 0
-
- φ
- ·
- Pres
-
- -
- 1
-
-
- kE
-
- *
- w
-
- (
- k
- )
-
- I
-
- ×
- (
-
- I
-
- -
- 1
- )
- .
Dependencies are inferred from the claim text.