Studies On Conjunctive Query Answering Of Fuzzy Description Logic Ontologies

In order to achieve reusability and a high level of interoperability of knowledge, ontologies are commonly used to express domain knowledge in the context of the Semantic Web. Ontology-based knowledge representation and reasoning is the main part of the Semantic Web. Description logics (DLs, for short) are a family of knowledge representation formalisms and the logical foundation of the standard Web Ontology Languages (OWLs). The most prominent feature of DLs is their built-in reasoning mechanism through which implicit knowledge is discovered from explicit information stored in a DL knowledge base (KB). In order to represent the widespread vagueness and imprecision in Semantic Web applications, there have been substantial amounts of work carried out in the context of fuzzy extensions of DLs and ontologies, and corresponding reasoning algorithms and reasoners are thus developed.In data-intensive applications, querying DL knowledge bases or ontologies plays a central role. Simple queries, such as instance retrieval, are relatively weak in expressive power and are unable to effectively express users’query intents. Conjunctive queries (CQs) originated from research in relational databases, and, more recently, have also been identified as a desirable form of querying DL knowledge bases. Conjunctive queries provide an expressive query language with capabilities that go beyond standard instance retrieval. According to the current research progresses in fuzzy extensions of DLs, query answering of (fuzzy) DLs,(fuzzy) DL reasoners and query engines, it is found that1. There is no systematic discussion of query answering of the whole f-DL-Lite family, only one for a certain logic language in the family.2. Existing algorithms are not capable of deciding query entailment problems of expressive f-SH family.3. Existing fuzzy DL reasoners lack the support of answering queries over expressive fuzzy DL knowledge bases. 4. There is no in-depth investigation of complexity and optimization issues of query answering algorithms for fuzzy DLs in the literature.To this end, studies on reasoning and query answering of lightweighted f-DL-Lite family, query entailment problems of f-SH family, the design and implementation of a reasoner supporting query answering of expressive fuzzy DLs, the reduction from query answering of fuzzy OWL ontologies to query entailment of fuzzy DLs are presented. Our main contributions are briefly summarized as follows:1. The query answering problems for the whole f-DL-Lite family is investigated. Firstly, for each logic language in this family, the syntax, semantics and the formal definition of knowledge bases are given. Secondly, by taking f-DLR-LiteFΠ n for example, algorithms for checking consistency of f-DL-Lite knowledge bases are given. On the basis of this, the detailed procedure and algorithm of query answering of f-DLR-Lite FΠ n knowledge bases are proposed, followed by the complexity analysis and the discussion of FOL reducibility.2. Query entailment problems of expressive f-SH family are investigated. Firstly, the syntax and semantics of fuzzy Boolean conjunctive queries and the definition of fuzzy query entailment are given. Secondly, the difference between fuzzy query entailment and entailment of single fuzzy assertion is analyzed, and problems to be solved for deciding entailment of fuzzy Boolean conjunctive queries are identified. Thirdly, the soundness, completeness and termination of fuzzy query entailment in proper sublogics of f-SHOIQ are showed by providing a corresponding tableau-based algorithm. The soundness for f-SHOIQ is shown, and the reason leading to non-termination is identified. Finally, for data complexity, a CONP upper bound is proved, as long as only simple roles occur in the query. Regarding combined complexity, a CO3NEXPTIME upper bound in the size of the knowledge base and the query is proved.3. Based on reasoning algorithm of f-SHOIQ and its sub-logics and query entaiment algorithms of f-SHOIQ and its proper sub-logics, the first reasoner that supports conjunctive query answering of expressive fuzzy DLs is designed and implemented, and is named FReQ. Firstly, main reasoning and querying services provided by FReQ are outlined. Then, a detailed description of FReQ framework and its components is given, and the characteristics and optimization techniques adopted in the process of implementation are well illustrated. Finally, the performances of FReQ before and after optimization are compared, and the reason for this is analyzed.4. Query answering of fuzzy OWL ontologies is investigated. Firstly, the correspondence between fuzzy OWL ontologies and fuzzy DL knowledge bases is established. Secondly, the correspondence between fuzzy SPARQL queries and datalog-like Boolean conjunctive queries is constructed. Finally, on the basis of the aforementioned correspondences, the query answering of fuzzy OWL ontologies is reduced into query entailment of fuzzy DL knowledge bases.