Deciding Query Entailment for Fuzzy SHIN Ontologies

摘要

Significant research efforts in the Semantic Web community are recently directed toward the representation and reasoning with fuzzy ontologies. As the theoretical counterpart of fuzzy ontology languages, fuzzy Description Logics (DLs) have attracted a wide range of concerns. With the emergence of a great number of large-scale domain ontologies, the basic reasoning services cannot meet the need of dealing with complex queries (mainly conjunctive queries), which are indispensable in data-intensive applications. Conjunctive queries (CQs), originated from relational databases, play an important role as an expressive reasoning service for ontologies. Since, however, the negation of a role atom in a CQ is not expressible as a part of a knowledge base, existing tableau algorithms cannot be used directly to deal with the issue. In this paper, we thus present a tableau-based algorithm for deciding query entailment of fuzzy conjunctive queries w.r.t. fuzzy SHIN ontologies. Moreover, the data complexity problem was still open for answering CQs in expressive fuzzy DLs. We tackle this issue by proving a tight CONP upper bound for the problem in f-SHIN, as long as only simple roles occur in the query. Regarding combined complexity, we prove that the algorithm for query entailment is CO3NExpTime in the size of the knowledge base and the query.