Closed Predicates in Description Logics: Results on Combined Complexity
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.
AMW