Consistency checking and querying in probabilistic databases under integrity constraints

DOI10.1016/J.JCSS.2014.04.026MaRDI QIDQ2453564zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

probabilistic databasesconsistency checkingintegrity constraints

Mathematics Subject Classification ID

Database theory (68P15)

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.

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

Cites work

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

Cited in

(8)

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

Describes a project that uses

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)