Deciding query entailment for fuzzy description logic knowledge bases: The f-SH family

Recently, the rapid evolution of large-scale domain ontologies brought about higher requirements for data access in the Semantic Web community. The basic reasoning services for ontologies, however, cannot meet the needs of dealing with complex queries (mainly conjunctive queries) in data-intensive applications. For that purpose, significant research efforts are recently directed toward the design and implemrntatuon of query answering algorithms for ontologies and description logic (DL) knowledge bases (KBs). Many practical tools capable of storing a knowledge base, and also performing queries on it, were constructed. Fuzzy extensions to ontologies and DLs have recently gained considerable attention especially for the purposes of handling vague information in the Semantic Web. In this study, we focus on fuzzy conjunctive queries over fuzzy DL KBs of the expressive f-SH family. We show soundness, completeness and termination of fuzzy query entailment in proper sublogics of f-SHOIQ by providing a corresponding tableau-based algorithm. We show the algorithm is sound for f-SHOIQ, and analyse the reason leading to nontermintion. We close the open problem of the complexity for answering fuzzy conjunctive queries in expressive fuzzy description logics by establishing two complexity bounds: for data complexity, we prove a CONP upper bound, as long as only simple roles occur in the query; Regarding combined complexity, we prove a CO3NEXPTIME upper bound in the size of the knowledge base and the query.