Closed Predicates in Description Logics: Results on Combined Complexity.
Nhung Ngo, Magdalena Ortiz, Mantas Šimkus · Principles of Knowledge Representation and Reasoning · 2016
In many applications of Description Logic (DL) ontologies, complete information—e.g., stemming from relational databases—interacts with incomplete knowledge. Closed predicates allow to leverage information completeness within the standard open-world semantics of DLs. In this paper we study the (combined) complexity of query answering in the presence of closed predicates, establishing tight complexity results for a range of DLs and query languages. Our results show that consistency testing and instance query answering in the presence of closed predicates is NP-complete even for rich dialects of the DL-Lite family. For EL, in contrast, they are EXPTIME-complete, thus as hard as for ALC and some of its extensions. If (unions of) conjunctive queries (UCQs) are considered, the picture is rather bleak, as 2EXPTIME-hardness holds even for DL-LiteR and EL. Our results also imply 2EXPTIME-hardness of query answering in ALCO for the standard open-world setting. Despite these negative results, we can still identify several useful classes of queries for which the increase in complexity is not so drastic.