2013 | OriginalPaper | Buchkapitel
Conjunctive Queries with Negation over DL-Lite: A Closer Look
verfasst von : Víctor Gutiérrez-Basulto, Yazmín Ibañez-García, Roman Kontchakov, Egor V. Kostylev
Erschienen in: Web Reasoning and Rule Systems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
While conjunctive query (CQ) answering over
DL-Lite
has been studied extensively, there have been few attempts to analyse CQs with negated atoms. This paper deepens the study of the problem. Answering CQs with safe negation and CQs with a single inequality over
DL-Lite
with role inclusions is shown to be undecidable, even for a fixed TBox and query.Without role inclusions, answering CQs with one inequality is P-hard and with two inequalities coNP-hard in data complexity.