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

An update on query answering with restricted forms of negation

Gutierrez Basulto, Victor, 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. pp. 75-89. 10.1007/978-3-642-33203-6_7

Full text not available from this repository.


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: 16 Aug 2018 16:22

Citation Data

Actions (repository staff only)

Edit Item Edit Item