Consistent query answering for primary keys in Datalog
From MaRDI portal
Publication:2035471
Abstract: We study the complexity of consistent query answering on databases that may violate primary key constraints. A repair of such a database is any consistent database that can be obtained by deleting a minimal set of tuples. For every Boolean query q, CERTAINTY(q) is the problem that takes a database as input and asks whether q evaluates to true on every repair. In [KW17], the authors show that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either in P or coNP-complete, and it is decidable which of the two cases applies. In this paper, we sharpen this result by showing that for every self-join-free Boolean conjunctive query q, the problem CERTAINTY(q) is either expressible in symmetric stratified Datalog or coNP-complete. Since symmetric stratified Datalog is in L, we thus obtain a complexity-theoretic dichotomy between L and coNP-complete. Another new finding of practical importance is that CERTAINTY(q) is on the logspace side of the dichotomy for queries q where all join conditions express foreign-to-primary key matches, which is undoubtedly the most common type of join condition.
Recommendations
- Consistent query answering for primary keys in logspace
- Taming primary key violations to query large inconsistent data via ASP
- Consistent query answering for self-join-free conjunctive queries under primary key constraints
- Why is it hard to obtain a dichotomy for consistent query answering?
- On the data complexity of consistent query answering
- A dichotomy in the complexity of counting database repairs
- Why is it hard to obtain a dichotomy for consistent query answering?
Cites work
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- scientific article; zbMATH DE number 7561483 (Why is no real title available?)
- A SAT-based system for consistent query answering
- A dichotomy in the complexity of counting database repairs
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A survey of the data complexity of consistent query answering under key constraints
- An introduction to description logic
- Answer sets for consistent query answering in inconsistent databases
- Complexity of conservative constraint satisfaction problems
- Consistent query answering for self-join-free conjunctive queries under primary key constraints
- Database Theory - ICDT 2005
- Elements of finite model theory.
- Finite model theory and its applications.
- First-order query rewriting for inconsistent databases
- Inconsistency-Tolerant Querying of Description Logic Knowledge Bases
- Locality of order-invariant first-order formulas
- On the data complexity of consistent query answering over graph databases
- On the relationship between consistent query answering and constraint satisfaction problems
- Scalar aggregation in inconsistent databases.
- Tight hardness for shortest cycles and paths in sparse graphs
- Undirected connectivity in log-space
- Why is it hard to obtain a dichotomy for consistent query answering?
Cited in
(9)- Modern Datalog Engines
- A simple algorithm for consistent query answering under primary keys
- A survey of the data complexity of consistent query answering under key constraints
- A dichotomy in the complexity of consistent query answering for queries with two atoms
- Why is it hard to obtain a dichotomy for consistent query answering?
- A remark on the complexity of consistent conjunctive query answering under primary key violations
- Consistent query answering for self-join-free conjunctive queries under primary key constraints
- Why is it hard to obtain a dichotomy for consistent query answering?
- A dichotomy in the complexity of counting database repairs
This page was built for publication: Consistent query answering for primary keys in Datalog
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035471)
