An update on query answering with restricted forms of negation

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Ibanez-Garcia, Yazmin and Kontchakov, Roman 2012. An update on query answering with restricted forms of negation. Presented at: 6th International Conference on Web Reasoning and Rule Systems, Vienna, Austria, 10-12 Sep 2012. Web Reasoning and Rule Systems. LECTURE NOTES IN COMPUTER SCIENCE. pp. 75-89. 10.1007/978-3-642-33203-6_7

Full text not available from this repository.

Abstract

One of the most prominent applications of description logic ontologies is their use for accessing data. In this setting, ontologies provide an abstract conceptual layer of the data schema, and queries over the ontology are then used to access the data. In this paper we focus on extensions of conjunctive queries (CQs) and unions of conjunctive queries (UCQs) with restricted forms of negations such as inequality and safe negation. In particular, we consider ontologies based on members of the DL-Lite family. We show that by extending UCQs with any form of negated atoms, the problem of query answering becomes undecidable even when considering ontologies expressed in the core fragment of DL-Lite. On the other hand, we show that answering CQs with inequalities is decidable for ontologies expressed in DL-Lite H core LitecoreH . To this end, we provide an algorithm matching the known coNP lower bound on data complexity. Furthermore, we identify a setting in which conjunctive query answering with inequalities is tractable. We regain tractability by means of syntactic restrictions on the queries, but keeping the expressiveness of the ontology.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
ISBN:	9783642332029
ISSN:	0302-9743
Last Modified:	23 Oct 2022 13:52
URI:	https://orca.cardiff.ac.uk/id/eprint/111954

Citation Data

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

Actions (repository staff only)

Edit Item