2013/03/13 by Sergio Flesca, Flesca, Sergio, Filippo Furfaro +3
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies #cs.DB
paper · pdf · doi:10.48550/arxiv.1303.3233
Probabilistic databases, Integrity constraints, Consistency checking
arxiv created 2013/03/13 · openalex publication_date 2013/03/13 · arxiv updated 2013/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.