Scalable Reasoning with Tractable Fuzzy Ontology Languages

Introduction

Nowadays, many applications and domains use some form of knowledge representation language and exploit their inference mechanisms in order to improve their capabilities and simulate intelligent human behavior. Many such examples exist, like knowledge-based multimedia analysis (Neumann & Möller, 2006; Simou et al., 2008a), bioinformatics (Dameron et al., 2004) and databases (Calvanese et al., 1998) and more. Nevertheless the most prominent example is undoubtedly the World Wide Web aiming for intelligently managing the vast amount of information that lays on the Web. Among several proposals for structuring knowledge in such applications, Description Logic based ontologies seem to be an approach that has gained considerable attention. Description Logics (DLs) (Baader et al., 2002) is a modern knowledge representation formalism that is a fragment of First-Order Logic, enjoying well-defined model-theoretic semantics, decidability and practically efficient reasoning systems. Most importantly expressive DLs form the logical underpinnings of the W3C standard language for representing ontologies in the Semantic Web, namely OWL (Bechhofer et al., 2004; Patel-Schneider et al., 2004). Although several successful OWL DL reasoning systems have been developed, like FaCT++¹ and Pellet², even very basic and inexpressive DLs come with come with (at least) computational complexity. Thus, their ability to scale in large application like the once found on the Web is still an open issue. For those reasons the last years great research effort has been focusing in identifying fragments/clusters of the OWL DL language for which it is known that reasoning is scalable and efficient. This research has led to the development of several languages, but the two most interesting and predominant ones are EL+ (Baader et al.) and DL-Lite (Calvanese et al., 2005; Calavanese et al., 2007). The interesting thing is that these languages will most likely form the logical underpinnings of the OWL 2 EL and OWL 2 QL³ recommendations which consist of profiles/fragments of the upcoming extension of OWL, OWL 2⁴.

Although DLs are relatively quite expressive they feature limitations mainly with what can be said about imperfect (uncertain, vague/fuzzy or imprecise) knowledge. Such types of knowledge appears in many domains but also in several Semantic Web tasks, like in the representation of trust, in knowledge fusion, assessing the similarity between resources and many more. For those reasons fuzzy ontologies are envisioned to be useful in the Web (Stoilos et al., 2006) and fuzzy Description Logics (f-DLs) (Höldobler et al., 2005; Straccia, 2001; Tresp & Molito, 1998) have been proposed as formalisms capable of capturing and reasoning with such knowledge. Research in f-DLs was mainly focused on providing reasoning support for very expressive fuzzy DLs, like reasoning with the f-DL f_KD-SHIN (Stoilos et al., 2007; Stoilos et al. 2005b), reasoning with f_KD-SHI (Li et al., 2006), supporting reasoning in f-DLs that allow for general concept inclusion axioms (Li et al., 2006; Stoilos et al., 2006), fuzzy extensions of the OWL language (Stoilos et al., 2005a) supporting expressive datatypes (Wang et al., 2008) or adding more expressive fuzzy features, like comparison expressions (Kang et al., 2006; Lu et al., 2008) and concept modifiers (Hölldobler et al., 2006; Wang et al., 2006). Interestingly, there also exist two f-DL reasoners, FiRE⁵ (Stoilos et al., 2007), which supports f_KD-SHIN and the fuzzyDL⁶ (Straccia, 2008), which supports f_KD-SHIf(D) and f_L-SHIf(D). Unfortunately, like their crisp counterparts, fuzzy-SHIN and fuzzy-SHIf(D) come with (at least) computational complexity. Additionally, the practical behavior of implementations of such logics would also have to deal with the degrees thus adding more to the practical complexity.