Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs
| Autor: | Thomas Lukasiewicz, Andrius Vaicenavičius, Enrico Malizia |
|---|---|
| Přispěvatelé: | Thomas Lukasiewicz, Enrico Malizia, Andrius Vaicenavicius, LUKASIEWICZ THOMAS, MALIZIA E, VAICENAVIČIUS ANDRIUS |
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
Preferred repairs
Theoretical computer science Computational complexity theory Computer science Semantics (computer science) Ontologie 0102 computer and information sciences Inconsistent data Semantics 01 natural sciences Datalog Cardinality Artificial Intelligence Cardinality (SQL statements) computer.programming_language Datalog+ Inconsistency-tolerant query answering Intersection (set theory) InformationSystems_DATABASEMANAGEMENT General Medicine Computational complexity Range (mathematics) 010201 computation theory & mathematics Query answering computer Repair Existential rule Cardinality-based repairs |
| Zdroj: | Scopus-Elsevier AAAI |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|