Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- Under Cardinality-Based Repairs
Abstract
Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistencytolerant query answering semantics have been proposed, including query answering relative to all repairs, relative to the intersection of repairs, and relative to the intersection of closed repairs. In these semantics, one assumes that the input database is erroneous, and the notion of repair describes a maximally consistent subset of the input database, where different notions of maximality (such as subset and cardinality maximality) are considered. In this paper, we give a precise picture of the computational complexity of inconsistencytolerant (Boolean conjunctive) query answering in a wide range of Datalog± languages under the cardinality-based versions of the above three repair semantics.
Cite
Text
Lukasiewicz et al. "Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- Under Cardinality-Based Repairs." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33012962Markdown
[Lukasiewicz et al. "Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- Under Cardinality-Based Repairs." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/lukasiewicz2019aaai-complexity/) doi:10.1609/AAAI.V33I01.33012962BibTeX
@inproceedings{lukasiewicz2019aaai-complexity,
title = {{Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- Under Cardinality-Based Repairs}},
author = {Lukasiewicz, Thomas and Malizia, Enrico and Vaicenavicius, Andrius},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2019},
pages = {2962-2969},
doi = {10.1609/AAAI.V33I01.33012962},
url = {https://mlanthology.org/aaai/2019/lukasiewicz2019aaai-complexity/}
}