From causes for database queries to repairs and model-based diagnosis and back
From MaRDI portal
Publication:2402617
Abstract: In this work we establish and investigate connections between causes for query answers in databases, database repairs wrt. denial constraints, and consistency-based diagnosis. The first two are relatively new research areas in databases, and the third one is an established subject in knowledge representation. We show how to obtain database repairs from causes, and the other way around. Causality problems are formulated as diagnosis problems, and the diagnoses provide causes and their responsibilities. The vast body of research on database repairs can be applied to the newer problems of computing actual causes for query answers and their responsibilities. These connections, which are interesting per se, allow us, after a transition -inspired by consistency-based diagnosis- to computational problems on hitting sets and vertex covers in hypergraphs, to obtain several new algorithmic and complexity results for database causality.
Recommendations
- From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back
- Characterizing and computing causes for query answers in databases from database repairs and repair programs
- Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints
- On the data complexity of consistent query answering
- Disjunctive databases for representing repairs
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1950744 (Why is no real title available?)
- scientific article; zbMATH DE number 2080480 (Why is no real title available?)
- scientific article; zbMATH DE number 1445320 (Why is no real title available?)
- scientific article; zbMATH DE number 2243355 (Why is no real title available?)
- scientific article; zbMATH DE number 2243367 (Why is no real title available?)
- A theory of diagnosis from first principles
- Abduction from logic programs: Semantics and complexity
- An efficient fixed-parameter algorithm for 3-hitting set
- Answer sets for consistent query answering in inconsistent databases
- Appropriate causal models and the stability of causation
- Approximate model-based diagnosis using greedy stochastic search
- Causes and Explanations: A Structural-Model Approach. Part I: Causes
- Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints
- Controlling the complexity in model-based diagnosis
- From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back
- Minimal-change integrity maintenance using tuple deletions
- Model-based and qualitative reasoning: An introduction
- On approximation of the vertex cover problem in hypergraphs
- Parameterized algorithmics for d-HITTING SET
- Parameterized approximation algorithms for hitting set
- Parametrized complexity theory.
- Prioritized repairing and consistent query answering in relational databases
- Provenance propagation in complex queries
- Scalar aggregation in inconsistent databases.
- The complexity of optimization problems
Cited in
(9)- scientific article; zbMATH DE number 7407794 (Why is no real title available?)
- The hardness of resilience for nested aggregation query
- From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back
- Declarative approaches to counterfactual explanations for classification
- Characterizing and computing causes for query answers in databases from database repairs and repair programs
- Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints
- The resilience of conjunctive queries with inequalities
- Answer-set programs for reasoning about counterfactual interventions and responsibility scores for classification
- Score-based explanations in data management and machine learning: an answer-set programming approach to counterfactual analysis
This page was built for publication: From causes for database queries to repairs and model-based diagnosis and back
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2402617)
