Fuzzy description logics (FDLs) have arisen as suitable formalisms for representing and reasoning with the vague or imprecise knowledge that is intrinsic to many application domains. They extend classical description logics by allowing additional truth degrees that lie between the classical “true” and “false” values. These truth degrees typically belong to a subset of the interval [0; 1]. For example, in a cloud computing environment, one might be interested in modeling the notion of an overused component. This is a typical example of an imprecise concept, since it is impossible to give a precise point where a component starts being overused. Instead, in FDLs, all components are assigned the degree to which they are being overused, where a higher degree implies a more extensive usage. For example, an idle component is overused with degree 0, while a component running at half its capacity might be overused to degree 0:8. The axioms hOverused(cpuA) 0:8i; hServer u 9hasPart:Overused v ServerWithLimitedResources express that object cpuA is overused to a degree of at least 0:8, and that every server that has an overused part is a server with limited resources with a degree of at least 0:9, respectively. The different concept constructors are interpreted by a t-norm and its associated operators [13]. One important t-norm is the Łukasiewicz t-norm, which is defined by x y := maxfx + y 1; 0g. Since dealing with infinitely many truth degrees easily leads to undecidability of reasoning [1, 7, 12], we focus on finitely valued FDLs, where the degrees are ? This work was partially supported by DFG under grant BA 1122/17-1 'FuzzyDL' (S. Borgwardt), the European project Optique (T. Mailis), the Cluster of Excellence 'cfAED' (R. Peñaloza), and EPSRC grant EP/J0083-46/1 'PrOQAW: Probabilistic Ontological Query Answering on the Web' (A.-Y. Turhan). ?? The work was developed while the author was still affiliated with TU Dresden and the Center for Advancing Electronics Dresden, Germany.
ordered in a finite chain. In this case, standard reasoning in expressive FDLs has
been shown to be decidable, and in the same complexity class, as reasoning in
their classical counterparts [
A reasoning problem extensively studied for DLs over the last years is (conjunctive) query answering, together with the associated query entailment problem. Briefly, a conjunctive query q is a finite set of concept and role atoms, which intuitively are ABox assertions that might contain variables in place of individuals. An ontology O entails the query q if every model I of O has a match for q; that is, if all the variables in q can be mapped to elements of the domain of I in a way that all the atoms are satisfied. In FDLs, the matches of an atom need not be absolute, but might also hold with a truth degree between 0 and 1.
The existence of intermediate truth degrees gives rise to two different notions of conjunctive queries that can be entailed by a fuzzy ontology. The first one, called threshold conjunctive query, extends the notion of an atom to express additionally the least degree to which the atom must be satisfied in each model. Thus, for example, we can ask whether server1 is fast (to degree 0.8) and has an overused (to degree 0.6) component through the threshold query fFast(server1) 0:8; hasPart(server1; x) 1;
Overused(x) 0:6g: (1) Such a query is entailed by O if every model of O has a match with at least the given degrees. Notice that the result of a threshold query entailment check is either “yes” (if the query is entailed by O) or “no.” There are no intermediate degrees associated with these answers.
The second type of query, called fuzzy conjunctive query, asks for the best entailment degree; i.e., the largest possible degree d such that every model of the ontology has a match to degree at least d. For example, using the fuzzy conjunctive query fFast(server1); hasPart(server1; x);
Overused(x)g; (2) we can find the best degree to which server1 is fast and has an overused component, where the conjunction between the atoms is interpreted using a t-norm. In the case of fuzzy conjunctive queries, there is only one degree that is global for the whole match of the query. Thus, it is possible that the threshold query above is not entailed (i.e., answers “no”) while this fuzzy conjunctive query returns a positive degree.
We propose a query answering procedure based on the crispification approach. In addition to crispifying the ontology, we also translate a threshold query into a classical conjunctive query that preserves the semantics w.r.t. the crispified ontology. For example, the threshold query (1) is crispified into the classical conjunctive query fFast 0:8(server1); hasPart 1(server1; x);
Recall that Fast 0:8 is a classical concept name from the crispified ontology. Thus, deciding entailment of this conjunctive query suffices for deciding entailment of the original threshold query.
A similar translation is used for fuzzy conjunctive queries, except that the result is a union of conjunctive queries, where each conjunctive query considers a certain combination of individual degrees whose combination leads to the entailment of the fuzzy query. For example, to decide whether the fuzzy conjunctive query (2) is entailed to a degree of at least 0:8, say in the presence of the degree set f0; 0:2; 0:4; 0:6; 0:8; 1g, one has to consider a union of several CQs such as fFast 0:8(server1); fFast 1(server1);
hasPart 1(server1; x); hasPart 1(server1; x);
where the t-norm of the individual degrees is equal to 0:8. After the translation, one can use any existing query answering system for classical DLs.
While studying the crispification approach for expressive FDLs, we
encountered two issues. First, we noticed that some of the previous crispification
approaches, such as those in [
Using this normalization step, we are able to prove tight complexity bounds
for answering threshold conjunctive queries; the complexity is always the same
as for classical conjunctive query answering (in DLs more expressive than ALCH
that do not have number restrictions). Unfortunately, the translation of fuzzy
conjunctive queries causes an exponential blow-up, which is avoided when the
simple Gödel t-norm x y := minfx; yg is used. Moreover, the data complexity of
classical query answering in DLs is not affected when considering finitely valued
semantics, as the reduction of the ABox (the data) is linear. Finally, our method
for fuzzy query answering can be applied to any crispification approach, i.e. also
in the cases that correctly handle number restrictions [
More details can be found in [