Consistency checking and querying in probabilistic databases under integrity constraints

• We incorporate denial constraints into probabilistic relational databases (PDBs).
• The semantics of PDBs is the set of interpretations consistent with the constraints.
• We investigate the consistency checking and the query answering problems.
• Tractable and hard cases are identified.
• Tractability is shown to depend on the data and/or the syntax of constraints.

We address the issue of incorporating a particular yet expressive form of integrity constraints (namely, denial constraints) into probabilistic databases. To this aim, we move away from the common way of giving semantics to probabilistic databases, which relies on considering a unique interpretation of the data, and address two fundamental problems: consistency checking and query evaluation. The former consists in verifying whether there is an interpretation which conforms to both the marginal probabilities of the tuples and the integrity constraints. The latter is the problem of answering queries under a “cautious” paradigm, taking into account all interpretations of the data in accordance with the constraints. In this setting, we investigate the complexity of the above-mentioned problems, and identify several tractable cases of practical relevance.