Significant research efforts in the Semantic Web community are recently directed toward the representation and reasoning with fuzzy ontologies. Description logics (DLs) are the logical foundations of standard Web ontology languages. Conjunctive queries are deemed as an expressive reasoning service for DLs. This chapter focuses on fuzzy (threshold) conjunctive queries over knowledge bases encoding in fuzzy DL , the logic counterpart of fuzzy OWL Lite language. It shows decidability of fuzzy query entailment in this setting by providing a corresponding tableau-based algorithm. The chapter shows data complexity for answering fuzzy conjunctive queries in fuzzy is in coNP, as long as only simple roles occur in the query. Regarding combined complexity, this research proves a co3NExpTime upper bound in the size of the knowledge base and the query.
TopIntroduction
The Semantic Web is an extension of the current Web in which the Web information can be given well-defined semantics, and thus enabling better cooperation between people and computers. In order to represent and reason with structured knowledge in the Semantic Web, W3C has developed and recommended the Web Ontology Language (OWL) OWL) (Bechhofer, Van Harmelen, Hendler, Horrocks, McGuinness, Patel-Schneider, Stein, et al., 2004), which comprises three sublanguages of increasing expressive power: OWL Lite, OWL DL and OWL Full. Description logics (DLs) (Baader, Calvanese, McGuinness, Nardi, & Patel-Schneider, 2003), as the logical foundation of the standard Web Ontology Languages, support knowledge representation and reasoning by means of the concepts and roles. The logical counterparts of OWL Lite and OWL DL are the DLs 
and 
, respectively. 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 the real world, there exists a great deal of uncertainty and imprecision which is likely the rule than an exception. Thus, the problems that emerge are how to represent these non-crisp knowledge within ontologies and DLs. Based on Zadeh's fuzzy set theory (Zadeh, 1965), there have been substantial amounts of work carried out in the context of fuzzy extensions of DLs (Straccia, 2001; Stoilos, Stamou, Pan, Tzouvaras, & Horrocks, 2007), and fuzzy ontologies (Stoilos, Simou, Stamou, & Kollias, 2006) are thus established. For a comprehensive review of fuzzy ontologies and fuzzy DLs, the readers can refer to (Lukasiewicz & Straccia, 2008).
Fuzzy DL reasoners (Bobillo & Straccia, 2008; Stoilos et al., 2006) implement most of the standard fuzzy inference services (Straccia, 2001), including checking of fuzzy concept satisfiability, fuzzy concept subsumption, and ABox consistency. In addition, some fuzzy DL reasoners support different kinds of simple queries over a KB 
for obtaining assertional knowledge, such as retrieval, i.e., given a fuzzy KB 
, a fuzzy concept C, and 
, to retrieve all instances o occurring in the ABox, such that 
entails 
, written as 
. In fact, fuzzy DL reasoners deal with these queries by transforming them into standard inference tasks. For example, the retrieval problem 
can be reduced to the (un)satisfiability problem of the KB 
, while the latter one is a standard inference problem.