Consistent Query Answering over Description Logic Ontologies

摘要

Description Logics (DLs) have been widely used in the last years as formal language for specifying ontologies over the web. Due to the dynamic nature of this setting, it may frequently happen that data retrieved from the web contradict the intensional knowledge provided by the ontology through which they are collected, which therefore may result inconsistent. In this paper, we analyze the problem of consistent query answering over DL ontologies, I.e., the problem of providing meaningful answers to queries posed over inconsistent ontologies. We provide inconsistency tolerant semantics for DLs, and study the computational complexity of consistent query answering over ontologies specified in DL-Lite, a family of DLs specifically tailored to deal with large amounts of data. We show that the above problem is coNP-complete w.r.t. data complexity, I.e., the complexity measured w.r.t. the size of the data only. Towards identification of tractable cases of consistent query answering over DL-Lite ontologies, we then study the problem of consistent instance checking, I.e., the instance checking problem considered under our inconsistency-tolerant semantics. We provide an algorithm for it which runs in time polynomial in the size of the data, thus showing that the problem is in PTime w.r.t. data complexity.