Incorporating Integrity Constraints in Uncertain Databases

The authors develop an approach to incorporate additional knowledge, in the form of general-purpose Integrity Constraints (ICs), to reduce uncertainty in probabilistic databases. While incorporating ICs improves data quality (and hence quality of answers to a query), it significantly complicates query processing. To overcome the additional complexity, they develop an approach to map an uncertain relation U with ICs to another uncertain relation U?? that approximates the set of consistent worlds represented by U. Queries over U can instead be evaluated over U?? achieving higher quality (due to reduced uncertainty in U??) without additional complexity in query processing due to ICs. They demonstrate the effectiveness and scalability of the approach to large datasets with complex constraints.