Consistency checking and querying in probabilistic databases under integrity constraints

DOI10.1016/J.JCSS.2014.04.026zbMATH Open1311.68053arXiv1303.3233OpenAlexW2021490548MaRDI QIDQ2453564FDOQ2453564

Authors: Sergio Flesca, Filippo Furfaro, Francesco Parisi 

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1303.3233

Recommendations

• Probabilistic query answering over inconsistent databases
• Complexity Results for Probabilistic Datalog
• A survey of the data complexity of consistent query answering under key constraints
• Complexity of repair checking and consistent query answering
• Database Repairing and Consistent Query Answering

zbMATH Keywords

probabilistic databasesconsistency checkingintegrity constraints

Mathematics Subject Classification ID

Database theory (68P15)

Cites Work

• The complexity of optimization problems
• Probabilistic logic
• A linear programming approach to reasoning about probabilities
• Title not available (Why is that?)
• Title not available (Why is that?)
• A logic for reasoning about probabilities
• Query answering under probabilistic uncertainty in Datalog\(+/-\) ontologies
• Probabilistic logic programming
• Treewidth in Verification: Local vs. Global
• An analysis of first-order logics of probability
• Probability logic
• Managing and mining uncertain data
• Scalar aggregation in inconsistent databases.
• Degrees of acyclicity for hypergraphs and relational database schemes
• Title not available (Why is that?)
• Probabilistic logic programming with conditional constraints
• Probabilistic satisfiability
• Easy cases of probabilistic satisfiability
• Title not available (Why is that?)

Cited In (8)

• On efficiently estimating the probability of extensions in abstract argumentation frameworks
• Efficient monochromatic and bichromatic probabilistic reverse top-\(k\) query processing for uncertain big data
• Probabilistic spatio-temporal knowledge bases: capacity constraints, count queries, and consistency checking
• Title not available (Why is that?)
• On the complexity of probabilistic abstract argumentation frameworks
• On repairing and querying inconsistent probabilistic spatio-temporal databases
• On measuring inconsistency in definite and indefinite databases with denial constraints
• A L1 Minimization Optimal Corrective Explanation Procedure for Probabilistic Databases

Uses Software

• ProbView
• MayBMS

This page was built for publication: Consistency checking and querying in probabilistic databases under integrity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453564)