Queries with negation and inequalities over lightweight ontologies

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Ibanez-García, Yazmín, Kontchakov, Roman and Kostylev, Egor V. 2015. Queries with negation and inequalities over lightweight ontologies. Journal of Web Semantics 35 (4) , pp. 184-202. 10.1016/j.websem.2015.06.002

Preview

PDF - Accepted Post-Print Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (301kB) | Preview

Abstract

While the problem of answering positive existential queries, in particular, conjunctive queries (CQs) and unions of CQs, over description logic ontologies has been studied extensively, there have been few attempts to analyse queries with negated atoms. Our aim is to sharpen the complexity landscape of the problem of answering CQs with negation and inequalities in lightweight description logics of the DL-Lite and families. We begin by considering queries with safe negation and show that there is a surprisingly significant increase in the complexity from AC to undecidability (even if the ontology and query are fixed and only the data is regarded as input). We also investigate the problem of answering queries with inequalities and show that answering a single CQ with one inequality over DL-Lite with role inclusions is undecidable. In the light of our undecidability results, we explore syntactic restrictions to attain efficient query answering with negated atoms. In particular, we identify a novel class of local CQs with inequalities, for which query answering over DL-Lite is decidable.

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	Elsevier
ISSN:	1570-8268
Date of First Compliant Deposit:	4 June 2018
Date of Acceptance:	5 June 2015
Last Modified:	29 Nov 2024 21:15
URI:	https://orca.cardiff.ac.uk/id/eprint/111923

Citation Data

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

Actions (repository staff only)

Edit Item