Conjunctive queries with negation over DL-Lite: A closer look

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Ibanez-Garcia, Yazmin, Kontchakov, Roman and Kostylev, Egor V. 2013. Conjunctive queries with negation over DL-Lite: A closer look. Presented at: Web Reasoning and Rule Systems - 7th International Conference, RR 2013, Mannheim, Germany, 27-29 July 2013. Published in: Faber, Wolfgang and Lembo, Domenico eds. Web Reasoning and Rule Systems: 7th International Conference, RR 2013, Mannheim, Germany, July 27-29, 2013. Proceedings. Lecture Notes in Computer Science Springer, pp. 109-122. 10.1007/978-3-642-39666-3_9

Preview

PDF - Accepted Post-Print Version Download (403kB) | Preview

Abstract

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.

Item Type:	Conference or Workshop Item (Paper)
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Springer
Date of First Compliant Deposit:	5 June 2018
Last Modified:	23 Oct 2022 13:52
URI:	https://orca.cardiff.ac.uk/id/eprint/111952

Citation Data

Cited 12 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item