Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

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

Gutierrez Basulto, Victor, 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

[img]
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: 16 Aug 2018 16:22
URI: http://orca.cf.ac.uk/id/eprint/111952

Citation Data

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

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics