WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I April 21-25, 2008 · Beijing, China Scalable Querying Services over Fuzzy Ontologies Jeff Z. Pan Dept. of Computing Science Univ. of Aberdeen Aberdeen, UK Dept. of Computer Science NTUA Athens, Greece Giorgos Stamou, Giorgo Stoilos Dept. of Computing Science Univ. of Aberdeen Aberdeen, UK Stuar t Taylor, Edward Thomas ABSTRACT Fuzzy ontologies are envisioned to b e useful in the Semantic Web. Existing fuzzy ontology reasoners are not scalable enough to handle the scale of data that the Web provides. In this pap er, we prop ose a framework of fuzzy query languages for fuzzy ontologies, and present query answering algorithms for these query languages over fuzzy DL-Lite ontologies. Moreover, this pap er rep orts on implementation of our approach in the fuzzy DL-Lite query engine in the ONTOSEARCH2 system and preliminary, but encouraging, b enchmarking results. To the b est of our knowledge, this is the first ever scalable query engine for fuzzy ontologies. Categories and Subject Descriptors I.2.3 [Deduction and Theorem Proving]: Uncertainty, "fuzzy", and probabilistic reasoning; I.2.4 [Knowledge Representation Formalisms and Methods]: Representation Languages General Terms Language, Algorithm, Exp erimentation Keywords Semantic Web, Lightweight Ontology Language, Fuzzy Ontology, Scalable Query Answering, Fuzzy SPARQL 1. INTRODUCTION Fuzzy ontologies are envisioned to b e useful in the Web. On the one hand, ontologies serve as basic semantic infrastructure, providing shared understanding of certain domain across different applications, so as to facilitate machine understanding of Web resources. On the other hand, b eing able to handle fuzzy and imprecise information is crucial to the Web. Web data are likely to b e uncertain or conflicting and could raise trust issues. It has b een argued that uncertainty representation and reasoning could help to harmonise and integrate Web data from different sources. To this end, This pap er is based on a p oster titled "Expressive Querying over Fuzzy DL-Lite Ontologies" presented in the 2007 International Workshop on Description Logics (DL2007). W3C has recently set up an incubator group on Uncertainty Reasoning for the Web1 . Although recently there have b een quite a lot of work on Description Logics (DLs) based fuzzy ontology languages, e.g., [27, 26, 17, 12, 2, 25], there exist no fuzzy ontology reasoners that could b e efficient and/or scalable enough to handle the scale of data that the Web provides. Interestingly, there currently exist two fuzzy ontology reasoners, namely the tableaux based fuzzy reasoner FiRE2 [25, 24], which supp orts a nominal and datatyp e-free subset of fuzzy-OWL DL, i.e. fuzzy-S HI N , and the mixed integer programming fuzzy reasoner fuzzyDL3 , which supp orts fuzzy-OWL Lite, namely fuzzy-S HI f (D) [28]. Like their crisp counterparts, fuzzy-S HI N and fuzzy-S HI f (D) come with (at least) EXPTIME computational complexity, thus the scalability of the ab ove systems is doubtful. Following current research developments in crisp DLs, there is an effort on lightweight fuzzy ontology languages. In particular, Straccia [29] extended the DL-Lite ontology language [5] to fuzzy DL-Lite. DL-Lite, which is expressive enough to represent most features of UML class diagrams, enables highly efficient query answering procedures by making use of database technologies. There are ma jor limitations on Straccia's query language for fuzzy DL-Lite: the prop osed query language has the same syntax as the query language of the crisp DL-Lite, and thus does not allow one to sp ecify either thresholds for query atoms (such as "tell me e-shops that are p opular [with degrees at least 0.8] and sell good b ooks [with degrees at least 0.9]"), or weights and preferences on query atoms (such as "get me all cars that are fast and fancy but consider sp eed more imp ortant [with weight 0.7] than design [with weight 0.3]"), so as to exploit fuzzy assertions in fuzzy ontologies. To the b est of our knowledge, there exist no rep ort on scalable query engines for fuzzy DL-Lite, let alone supp orting more expressive fuzzy query languages. This pap er makes the following ma jor contributions: 1. It prop oses a general framework, which consists of threshold queries and general fuzzy queries (Section 3.1), for querying over fuzzy ontologies, covering all the existing query languages for fuzzy ontologies as well as some new ones that can b e customised by users. Comparing with Straccia's query language, the threshold query language is flexible as it allows one to sp ecify a threshold for each query atom (as shown in the ab ove exhttp://www.w3.org/2005/Incubator/urw3 http://www.image.ece.ntua.gr/~nsimou 3 http://gaia.isti.cnr.it/~straccia 2 1 Copyright is held by the International World Wide Web Conference Committee (IW3C2). Distribution of these papers is limited to classroom use, and personal use by others. WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. 575 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I ample). In fact, entailment of threshold queries generalises the entailment problem of fuzzy assertions. On the other hand, the general fuzzy query language is a general form of the fuzzy threshold query language, which in turn is a general form of Straccia's query language. General fuzzy queries are motivated by the field of fuzzy information retrieval [8] where weighted Boolean queries [33] have b een prop osed for retrieving fuzzy information from fuzzy relational databases. Our general fuzzy query language generalises most former approaches of weighted Boolean queries [20, 3, 34, 4] and several new approaches, like the p-norm approach [21], the geometric mean approach [6], the so called fuzzy weighted t-norm queries from Chortaras et. al. [7], which in turn generalise weighted min queries [23], and aggregation queries from Vo jtas [32]. Thus, the main strength of the general fuzzy query language is the op enness of the use of semantics of conjunction and that of the degree-associated atoms. Consequently, the framework can accommodate different intuitive meaning on the associated degrees, like preferences, degrees of imp ortance, fuzzy thresholds and more. 2. It not only provides an abstract syntax (Section 3.1) for the prop osed framework, but also shows how to extend the SPARQL (a well known Semantic Web query language) syntax for the prop osed query languages in the framework (Section 3.2). Our extension uses sp ecially formatted SPARQL comments, thus the fuzzy queries are still valid SPARQL queries, and it does not affect current SPARQL tools and implementations. 3. It not only prop oses the syntax of query languages, but also provides semantics (Section 3.1) and algorithms for answering such queries over arbitrary fuzzy DL-Lite ontologies together with sound and complete proofs (w.r.t. the semantics); and the algorithms cover all the mentioned languages in the framework (Section 3.3). 4. To the b est of our knowledge, it presents the first ever scalable query engine for fuzzy ontologies, based on the ONTOSEARCH2 system4 [16], which consists of, among others, a query engine for DL-Lite and one for fuzzy DL-Lite. The p erformance of the fuzzy DLLite query engine is evaluated against a b enchmark (a fuzzy variant of the Lehigh University Benchmark (LUBM) [10], called f-LUBM) that we prop ose, which is the first of its kind and against which future implementations can also b e evaluated. The query engine is able to handle millions of individuals, according to the preliminary but encouraging evaluation (Section 4). 5. It presents a use cases ab out searching ontology based on keyword-plus-entailment searches, so as to show how to apply our efficient querying supp ort for fuzzy ontologies. The use case application is available online (Section 5). April 21-25, 2008 · Beijing, China 2. PRELIMINARIES 2.1 DL-based Ontologies and Query Answering Due to the limitation of space, we do not provide a formal introduction of Description Logics (DLs), but rather p oint the reader to [1]. It should b e noted that, even for the smallest prop ositionally closed DL ALC (which only provides the class constructors ¬C, C D, C D, R.C and R.C ), the complexity of logical entailment is Exptime. Recently, Calvanese et. al. prop osed DL-Lite, which has a low reasoning overhead (worst case p olynomial time) [5]. A DL-Lite ontology (O) is a set of axioms of the following forms: 1. class inclusion axioms: B C where B is a basic class B := A | R | R¯ and C is a general class C := B | ¬B | C 1 C 2 (where A denotes an named class and R denotes a named prop erty); 2. functional prop erty axioms: Func(R), Func(R¯), where R is a named prop erty; 3. individual axioms: B (a), R(a, b) where a and b are named individuals. Description Logics have a well-defined model-theoretic semantics, which are provided in terms of interpretations. An interpretation I is a pair (I , ·I ), where I is a non-empty set of ob jects and ·I is an interpretation function, which maps each class C to a subset C I I and each prop erty R to a subset RI I × I . Typical reasoning ontology services include ontology consistency checking (i.e., whether there exists an interpretation of an ontology), subsumption checking (i.e., whether the interpretation of a class C1 is a subset of the interpretation of a class C2 in all interpretations of the ontology), instance checking (i.e. whether an assertion is logically implied by an ontology) and query answering. In this pap er, we will focus on query answering. A conjunctive query (CQ) q is of the form q (X ) Y .conj (X, Y ) (1) 4 http://www.ontosearch.org/ or simply q (X ) conj (X, Y ), where q (X ) is called the head, conj (X, Y ) is called the b ody, X are called the distinguished variables, Y are existentially quantified variables called the non-distinguished variables, and conj (X, Y ) is a conjunction of atoms of the form A(v ), R(v1 , v2 ), where A, R are resp ectively named classes and named prop erties, v , v1 and v2 are individual variables in X and Y or individual names in O. As usual, an interpretation I satisfies an ontology O if it satisfies all the axioms in O; in this case, we say I is a model of O. Given an evaluation [X S ] (where S is a set of individuals), if every model I of O satisfies q[X S] , we say O entails q[X S] ; in this case, S is called a solution of q . A disjunctive query (DQ) is a set of conjunctive queries sharing the same head. Theoretically, allowing only named classes and prop erties as atoms is not a restriction, as we can always define such named classes and prop erties in ontologies. Practically, this should not b e an issue as querying against named relations is a usual practice when p eople query over relational databases. After some careful query rewriting by DL-Lite reasoners [5], query answering over DL-Lite ontologies can b e carried out by an SQL engine, so as to take advantage of exist- 576 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I ing query optimisation strategies and algorithms provided by modern database management systems. April 21-25, 2008 · Beijing, China 2.2 f-DL-LITE Straccia [29] prop osed fuzzy DL-Lite (or f-DL-Lite for short), which extends DL-Lite core with fuzzy assertions of the forms B (a) n, R(a, b) n, where B is basic class, R is a prop erty, a and b are individuals and n is a real numb er in the range [0, 1]. The semantics of f-DL-Lite ontologies is defined in terms of fuzzy interpretations [27]. A fuzzy interpretation is a pair I = (I , ·I ) where the domain I is a non-empty set of ob jects and ·I is a fuzzy interpretation function, which maps: · an individual a to an element of aI I , · a named class A to a memb ership function A : [0, 1], and · a named prop erty R to a memb ership function RI : I × I [0, 1]. Using the fuzzy set theoretic op erations [11], fuzzy interpretations can b e extended to interpret f-DL-Lite class and prop erty descriptions. Following Straccia [29], we use the Lukasiewicz negation, c(a) = 1 - a and the Godel t-norm ¨ for interpreting conjunctions, t(a, b) = min(a, b). The semantics of f-DL-Lite class and prop erty descriptions, and f-DL-Lite axioms are depicted in Table 1. Given the ab ove semantics, it is obvious that crisp assertions B (a), R(a, b) are sp ecial forms of fuzzy assertions where n = 1. Syntax R ¬B C1 C2 R- BC Func(R) B (a) n R(a, b) n Semantics (R)I (o1 ) = sup {RI (o1 , o2 )} (¬B )I (o) = 1 - B I (o) I I (C1 C2 )I (o) = t(C1 (o), C2 (o)) (R- )I (o2 , o1 ) = RI (o1 , o2 ) o I , B I (o) C I (o) o1 I , {o2 | RI (o1 , o2 ) > 0} = 1 B I (aI ) n RI (aI , bI ) n o 2 I I I of the DL-Lite sp ecified in the OWL1.1 memb er submission (an extension of OWL DL) in the tractable fragments document [9]. It is slightly different from that in the OWL 1.1 document, mainly due to the fact that it uses the OWL DL syntax (which is slightly different from that of OWL 1.1) and RDF/XML serialisation. Besides disallowing several expressive OWL DL constructors, DL-Lite restricts the use of several of the allowed constructors and esp ecially w.r.t. which side of class axioms they can app ear. Thus, the definition of an abstract syntax is slightly trickier than that of OWL. In OWL DL, for example, disjointness, equivalence and sub class axioms are defined by the following abstract syntax: axiom ::= `DisjointClasses(' description description { description } `)' | `EquivalentClasses(' description { description } `)' | `SubClassOf(' description description `)' where "description" can b e any OWL DL class description. In DL-Lite, only basic classes are allowed on the left-hand side of axioms, while general classes are allowed only on the right-hand side. Thus, the ab ove abstract syntax should b e adjusted to: axiom ::= `DisjointClasses(' basicClass basicClass { basicClass } `)' | `EquivalentClasses(' basicClass { basicClass } `)' | `SubClassOf(' basicClass generalClass ')' where "basicClass" and "generalClass" represent the basic and general classes of DL-Lite, resp ectively. The abstract syntax for these two elements should also follow the restrictions of DL-Lite; e.g., a "generalClass" can b e an intersection of classes while a basic class is not. By using the RDF/XML serialisation mapping describ ed for OWL DL, one is able to obtain DL-Lite and f-DL-Lite ontologies in RDF/XML syntax. For example, the following class axiom in RDF/XML syntax is a valid DL-Lite axiom, Table 1: Semantics of f-DL-Lite class and property descriptions, and f-DL-Lite axioms Similarly to crisp DL lite, fuzzy-DL-Lite, provides means to sp ecify role-typing and participation constraints but interestingly it assigns fuzzy meaning on them. More precisely, a role-typing assertion of the form R A1 (resp. R- A2 ) states that the first (resp. second) comp onent of R b elongs to A1 (resp. A2 ) at-least to the memb ership degree that the relation R holds, i.e. RI (aI , bI ) AI (aI ) 1 (resp. (R- )I (bI , aI ) = RI (aI , bI ) AI (bI )). 2 2.3 Abstract and RDF/XML Syntax Since DL-Lite (resp. f-DL-Lite) is a sub-language of OWL (resp. f-OWL DL), we provide an abstract and RDF/XML syntax for DL-Lite and f-DL-Lite ontologies in this subsection, following the paradigm of OWL DL [18]. OWL DL ontologies in RDF/XML syntax can b e generated from those written in the abstract syntax, using the official mapping b etween the two kind of syntax provided in [18]. Our prop osed abstract syntax for DL-Lite core is based on that which corresp onds to the axiom C ¬R ¬A. Finally, fuzziness in the individual axioms of f-DL-Lite is defined by a restriction of the abstract syntax of facts of f-OWL DL presented in [26], since we are only allowing the inequality "". The abstract syntax is the following: 577 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I individual ::= `Individual(' [individualID] {annotation} {`type'( type `)' [ineqType] [degree]} {value [ineqType] [degree] } `)' ineqType ::= `>=' degree ::= real-number-between-0-and-1-inclusive April 21-25, 2008 · Beijing, China Example 1. We can query models who are tal l with a degree no less than 0.7 and light with a degree no less than 0.8 with the fol lowing conjunctive threshold query: q (v ) Model(v ) 1, Tall(v ) 0.7, Light(v ) 0.8. It is obvious that threshold queries are more flexible than queries of the form (1) in that users can sp ecify different thresholds for different atoms in their queries. Formally, given an f-DL-Lite ontology O, a conjunctive threshold query qT and an evaluation [X S ], we say O entails qT (denoted as O |= qT ) if every interpretation I of O satisfies the following condition: for each atom A(v ) t1 (R(v1 , v2 ) t2 ) of qT , we have AI (v )X S t1 (resp. RI (v1 , v2 )X S t2 ). In this case, S is called a solution of qT . A disjunctive threshold query (DTQ) is a set of conjunctive threshold queries sharing the same head. Similarly, we can follow the RDF/XML serialization prop osed in [26] to have fuzzy individual axioms in a f-DL-Lite file. For example, stating that o is Heavy to degree at-least 0.7 could b e sp ecified by the following RDF/XML syntax. The full sp ecification of the f-DL-Lite (and consequently DL-Lite) abstract syntax can b e found in the App endix. The ONTOSEARCH2 system allows users to submit their crisp and fuzzy ontologies to its rep ository. Furthermore, it provides an RDF/XML syntax checker for DL-Lite. 3.1.2 General Fuzzy Queries Since f-DL-Lite associates assertions with degrees of truth, another useful feature for its query language is to associate degrees of truth with answers in answer sets of queries over f-DL-Lite ontologies. In threshold queries, an evaluation [X S ] either satisfies the query entailment or not; hence, answers of such queries are crisp. In this subsection, we introduce general fuzzy queries which allow fuzzy answers. Syntactically, like the query language prop osed in [33] and threshold queries, general fuzzy conjunctive queries (GFCQ) extend the atoms A(v ), R(v1 , v2 ) of conjunctive queries of the form (1) into ones with the following form A(v ) : k1 , R(v1 , v2 ) : k2 , where k1 , k2 (0, 1] are degrees. . The strength of the general fuzzy query language is the op enness of the use of fuzzy op erations. Indeed, as many theoretical and practical studies [32, 4] have p ointed out, the choice of fuzzy op erations is usually context dep endent. Following the style of the semantics of fuzzy-SWRL [17] the existential quantifier is interpreted as sup, while we leave the semantics of the conjunction (G) and that of the degreeassociated atoms (a) op en. To simplify the presentation of the semantics, we use a unified representation atomi (v ) for ¯ atoms in general fuzzy conjunctive queries. Given an f-DLLite ontology O, an interpretation I of O, a general fuzzy conjunctive query qF and an evaluation [X S ], the degree of truth of qF under I is d= sup S I ×···×I 3. QUERYING F-DL-LITE ONTOLOGIES In this section, we present a general framework for representing expressive fuzzy queries over f-DL-Lite ontologies. More precisely, we will introduce two query languages for fDL-Lite ontologies. The first language extends conjunctive queries with thresholds for atoms in queries. Entailment of threshold queries generalises the entailment problem of fuzzy assertions. The second language is a general fuzzy query language, motivated by the field of fuzzy information retrieval [8], where weighted Boolean queries have b een prop osed [33, 20, 3, 34]. As it was showed in [4] most of these approached could b e represented under a general framework using general fuzzy op erators, like t-norms and fuzzy implications. Our general fuzzy query language extends these results by allowing more fuzzy op erators and thus generalising many of the recent approaches like the query language prop osed in [29] for fuzzy DL-Lite, weighted t-norm queries [7], which in turn generalise weighted min queries [23], p-norms [21], fuzzy aggregations [32] and the geometric mean [6]. In order to enable such typ es of queries in the Semantic Web, we also prop ose the extension of the SPARQL [19] query language, so as to represent the queries in our general framework. In what follows, we first introduce these new query languages, providing their syntax and semantics. We then present the extension of SPARQL, and finally we provide algorithms of query answering for queries in the prop osed query languages. {Gn 1 a(ki , atomI (v )[X S,Y S ] )} i= i¯ 3.1 Two New Query Languages 3.1.1 Threshold Queries As noted in [5] in DL-Lite the instance checking problem is a sp ecial case of conjunctive queries. Since f-DL-Lite extends DL-Lite with fuzzy assertions, it would b e natural to define a query language so that the entailment of such queries could generalise entailment checking of fuzzy assertions. Accordingly, we define conjunctive threshold queries (CTQ) which extend atoms A(v ), R(v1 , v2 ) in conjunctive queries of the form (1) into the following forms A(v ) t1 , R(v1 , v2 ) t2 , where t1 , t2 (0, 1] are thresholds. It turns out that threshold queries are very imp ortant typ es of queries since in [13] the authors used them in order to devise a reasoning algorithm for the fuzzy language fuzzy-CARIN. where ki (0, 1] are degrees ( 1 i n), atomi are atoms in the query, G is the semantic function for conjunctions and a is the semantic function for degree-associated atoms. S : d is called a candidate solution of qF . When d > 0, S : d is called a solution of qF . Furthermore, the semantic functions should satisfy the following condition: If atomI (v )[X S,Y S ] ) = 0 for all p ossible S , d = 0. (2) i¯ A general fuzzy disjunctive query (GFDQ) is a set of general fuzzy conjunctive queries sharing the same head. The disjunction is interpreted as the s-norm (u) of disjuncts. In what follows, we give some examples of the semantic functions for conjunctions and degree-associated atoms. 1. Fuzzy threshold queries : If we use t-norms (t) as the semantic function for conjunctions and R-implications (t ) [11] as the semantic function for degree-associated 578 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I atoms, we get fuzzy threshold queries, in which the degree of truth of qF under I is d= sup S I ×···×I April 21-25, 2008 · Beijing, China degree of truth of qF under I is d= sup S I ×···×I {tn 1 t (ki , atomI (v )[X S,Y S ] )}. i= i¯ {min u(k-ki , t(k, atomI (v)[X S,Y S ] ))}, i¯ i=1 n Given some S , if for all atoms we have atomI (v )[X S , i¯ Y S ] ki , since t (x, y ) = 1 when y x [11], we have d = 1; this corresp onds to threshold queries introduced earlier. On the other hand, different from threshold queries, if 0 < atomI (v )[X S,Y S ] < ki , then d = 0 i¯ b ecause of use of the R-implication which filters (p enalises) the degree atomI (v )[X S,Y S ] against the i¯ fuzzy threshold ki . As it was shown in [4] many of the approaches for weighted Boolean queries that have b een prop osed [3, 20] are actually sp ecial cases of fuzzy threshold queries. 2. Straccia's query language [29] : It is also a sub-language of the fuzzy threshold query language, where all ki = 1. Since t (1, y ) = y [11], the degree of truth of qF under I is d= sup S I ×···×I where k = maxn 1 ki . The main idea of this typ e of i= queries is that they provide an aggregation typ e of operation, on the other hand an entry with a low value for a low-weighted criterion should not b e critically p enalized. Moreover, lowering the weight of a criterion in the query should not lead to a decrease of the relevance score, which should mainly b e determined by the high-weighted criteria (see [7] for more details). Yager [34], prop oses the use of and S -implication [11] (in contrast to R-implications of fuzzy threshold queries), i.e. the function: d= sup S I ×···×I {min u(1-ki , atomI (v )[X S,Y S ] )}, i¯ i=1 n {tn 1 atomI (v )[X S,Y S ] }. i= i¯ This is a sp ecial case of fuzzy weighted t-norms, where k = 1, since t(1, a) = a. A similar approach was prop osed by Sanchez [23]. It is easy to show that all the ab ove four sp ecific fuzzy query languages satisfy the condition (2). 3. Fuzzy aggregation queries : If we use fuzzy aggregation n x = functions [11], such as G(x) = in 1 kii , for conjunci=1 tions and a(ki , y ) = ki y as the semantic function for degree-associated atoms, we get fuzzy aggregation queries, in which the degree of truth of qF under I is n I ¯ i=1 ki atomi (v )[X S,Y S ] n . d= sup S I ×···×I i=1 ki 3.2 Supporting Querying with SPARQL After presenting the abstract syntax and semantics of our prop osed languages, in this section, we show how to extend the syntax of SPARQL [19], a well known Semantic Web query language, for the prop osed languages. We call our extension f-SPARQL. SPARQL is a query language (candidate recommendation from the W3C Data Access Working Group) for getting information from RDF graphs. SPARQL allows for a query to constitute of triple patterns, conjunctions, disjunctions and optional patterns. A SPARQL query is a quadruple Q = (V , P, DS, S M ), where V is a result form, P is a graph pattern, DS a data set and S M a set of solution modifiers. Among others, SPARQL allows for select queries, formed in a SELECT-FROM-WHERE manner. The result form represents the set of variables app earing in the SELECT, the dataset forms the FROM part, constituted by a set of IRIs of RDF documents, while the graph pattern forms the WHERE part which is constituted by a set of RDF triples. Qu e r y S e l e c t Qu e r y ::= Prologue ( SelectQuery | ConstructQuery | Describ eQuery | AskQuery ) Moreover, we can show that many existing approaches of weighted Boolean queries could b e represented under the framework of fuzzy aggregation queries. More precisely, Salton, Fox and Wu [21] prop osed the model of p-norms where the semantic function is given by the following equation: 1/w n I w ¯ i=1 (atomi (v )[X S,Y S ] ) d= sup n S I ×···×I where w1 = w2 = . . . = wn = w and w (0, +]. On the other hand, S.J. Chen and S.M. Chen [6] prop ose the geometric mean [11] as a semantic function for weighted Boolean queries: n 1/w i d= sup atomI (v )[X S,Y S ] ¯ . i S I ×···×I =1 Under the framework of fuzzy aggregation functions b oth these equations are sp ecial cases of the generalized mean function which is given by the equation dw = n w 1/w i=1 ai where w R . If w (0, +] then n we have the approach of Salton et. al. [21], while if w 0, then function d converges to the geometric mean [11]. 4. Fuzzy weighted t-norm queries : If we use generalised weighted t-norms [7] as the semantic function for conjunction, we get fuzzy weighted queries, in which the ::= `SELECT' ( `DISTINCT' | `REDUCED' )? (Var+ | `*') DatasetClause* WhereClause SolutionMo difier WhereClause ::= `WHERE' ? GroupGraphPattern GroupGraphPattern ::= `{' TriplesBlo ck? ( ( GraphPatternNotTriples | Filter ) `.' ? TriplesBlo ck? )* `}' In order to maintain backward compatibility with existing SPARQL tools, we prop ose to use sp ecially formatted SPARQL comments to sp ecify extra information needed in our prop osed languages (see Table 2). Firstly, one should declare the query typ e b efore a select query. For example, #TQ# declares a threshold query, while #GFCQ:SEM=FUZZY THRESHOLD# declares a general fuzzy query, with the fuzzy threshold semantic functions. Secondly, following each triple in the WHERE clause, one can use #TH# (resp. #DG#) to sp ecify a threshold in a threshold query (resp. a degree in 579 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I Query TriplesBlock QueryTyp e FuzzySemantics TripleWeight degree ::= ::= ::= ::= ::= ::= April 21-25, 2008 · Beijing, China Prologue ( QueryType SelectQuery | ConstructQuery | Describ eQuery | AskQuery ) TriplesSameSub ject ( `.' TripleWeight Degree TriplesBlock? )? `#TQ# \n' | `#GFCQ:SEM=' FuzzySemantics `# \n' `AGGREGATION' | `FUZZYTHRESHOLD' | `FUZZYTHRESHOLD-1' | `FUZZYWEIGHTEDNORMS' `#TH#' | `#DG#` real-numb er-b etween-0-and-1-upp er-inclusive Table 2: Syntax of Fuzzy SPARQL a general fuzzy query). For instance, the threshold query presented in Example 1 (Section 3.1) can b e represented by the following f-SPARQL query: #TQ# SELECT ?x WHERE { ?x rdf:type Model . ?x rdf:type Tall . ?x rdf:type Light . } #TH# 1.0 #TH# 0.7 #TH# 0.8 In the case of general fuzzy queries, one must sp ecify the semantic functions (i.e. a and G). Below is an example fuzzy threshold query. #GFCQ:SEM=FUZZYTHRESHOLD# SELECT ?x WHERE { ?x rdf:type Model . #DG# 1.0 ?x rdf:type Tall . #DG# 0.7 ?x rdf:type Light . #DG# 0.8 } Table 2 presents the f-SPARQL syntax. f-SPARQL extends two of SPARQL's elements, namely the "Query" and the "TriplesBlock" element. As illustrated ab ove, each select query is extended with the element QueryType. In particular, for general fuzzy queries, the declaration `#GFCQ:SEM=' is followed by the element FuzzySemantics, which is used to sp ecify the semantic functions, such as the ones we presented in the previous section. More precisely, we use the keywords `FUZZYTHRESHOLD', `FUZZYTHRESHOLD1', `AGGREGATION' and `FUZZYWEIGHTEDNORMS' to indicate the four fuzzy general queries we introduced in Section 3.1.2. When one uses `FUZZYTHRESHOLD-1', the fuzzy threshold is set as 1, and the values sp ecified by the #TH# comments are ignored. Finally, the "TriplesBlock" element is extended with the elements TripleWeight and Degree, which are used to associated a threshold or weight with each triple of the SPARQL query. set A of individual axioms in O by the procedure Store(A) that normalise A and returns the relational database DB(A) of A, as well as checking the consistency of O by the procedure Consistency(O, T ); (iii) reformulation of the input query q against the normalised set T of the class axioms by the procedure PerfectRef (q , T ), which returns a set Q of (conjunctive) queries; (iv) transformation of the set Q of (conjunctive) queries into SQL queries by the procedure SQL(Q), as well as the evaluation of SQL(Q) by the procedure Eval(SQL(Q), DB(A)). As steps (i) and (ii) are very similar to those for the crisp case, here we focus on steps (iii) and (iv) on answering conjunctive threshold queries and general fuzzy queries. 3.3.1 Answering Threshold Queries Given an f-DL-Lite ontology O, a conjunctive threshold query qT , the procedure AnswerT (O, qT ) computes the solutions of qT w.r.t. O, following the ab ove steps (i) - (iv). Algorithm A-1: AnswerT (O , qT ) 1: T = Class-Axioms(O) 2: T = Normalise(T ) //normalisation of class axioms 3: A = Individual-Axioms(O) 4: DB(A) = Store(A) //normalisation and storage of individual axioms 5: if Consistency(O, T ) = false then 6: return inconsistent //O is inconsistent 7: end if 8: return Eval(SQLT (PerfectRefT (qT ,T )),DB(A)) Algorithm A-2: SQLT (Q) 1: QS := 2: for every query q in Q do 3: sc:=Select-Clause(q ) //construct the select-clause of q 4: fc:=From-Clause(q ) //construct the from-clause of q 5: wc1:=WC-Binding(q ) //construct the part of the whereclause about binding 6: wc2:=WC-Threshold(q ) //construct the part of the whereclause that relates to thresholds 7: QS := QS Construct-SQL (sc,fc,wc1,wc2) 8: end for 9: return QS 3.3 Query Answering It should b e noted that the query languages in the previous sections can b e used with any fuzzy ontology languages. In order to provide efficient query answering services using our prop osed query languages, we choose f-DL-Lite as our fuzzy ontology language. This sub-section provides algorithm to answer threshold queries and general fuzzy queries over f-DL-Lite ontologies. Algorithms for answering queries in f-DL-Lite mainly consist of four steps (like the algorithm for crisp DL-Lite [5]): (i) normalisation of the set T of the class axioms of O by the procedure Normalise(T ), which returns the normalised set T of class axioms; (ii) normalisation and storage of the The algorithms need some explanations. Firstly, if O is inconsistent, query answering is meaningless, since every tuple is a solution of every query w.r.t. O. Secondly, the procedure PerfectRefT (qT ,T ) of reformulating an input conjunctive threshold query qT (into a set of conjunctive queries) is essentially the same as the PerfectRef (q ,T ) for DL-Lite [5]. Here we do not rep eat PerfectRef (q ,T ) but explain its main ideas instead. PerfectRefT (qT ,T ) rewrites atoms in qT based on p ositive inclusions (PIs) in T . For example, given a PI B B1 , if B1 (v ) k is an atom of 580 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I qT and B is a named class A (resp. of the form R, or of the form R- ), B1 (v ) k can b e rewritten as A(v ) k (resp. R(v , ) k, or R( , v ) k, where represent nondistinguished non-shared variables5 ). The generated query can b e further written, based on the PIs in T . It can b e shown that such rewriting process always terminates [5], and it produces a set of generated conjunctive queries from the input query qT Q . Thirdly, the procedure SQLT (Q) transforms a set of conjunctive threshold queries into SQL queries in an obvious way, taking into accounts the thresholds. Namely, it use Select-Clause, From-Clause, WC-Binding and WC-Threshold to construct the select-clauses, from-clauses and where-clauses of SQL queries, resp ectively. Due to limitation of space, we do not provide full details of these procedures but illustrate them with the following example. Given the query q (v ) Model(v ) 1, Tall(v ) 0.7, Light(v ) 0.8, Select-Clause(q ) returns the select-clause `SELECT tabModel [0]', From-Clause(q ) returns the from-clause `FROM tabModel , tabTall , tabLight ', WCBinding(q ) returns the binding part of the where-clause `WHERE tabModel [0] = tabTall [0], tabModel [0] = tabLight [0]' and WCThreshold(q ) returns the threshold-related part of the whereclause `tabModel [1] 1, tabTall [1] 0.7, tabLight [1] 0.8'. Construct-SQL puts all these together and returns the corresp onding SQL query `SELECT tabModel [0] FROM tabModel , tabTall , tabLight WHERE tabModel [0] = tabTall [0], tabModel [0] = tabLight [0], tabModel [1] 1, tabTall [1] 0.7, tabLight [1] 0.8'. Theorem 1. Let O be an f-DL-Lite ontology, qT a conjunctive threshold query and S a tuple of constants. S is a solution of qT w.r.t. O iff S AnswerT (O, qT ). Proof: (Sketch) The proof of correctness is straight forward. The procedure AnswerT differs from that of DL-Lite mainly in that it needs to take care of the thresholds (line 6 of Algorithm A-2) when constructing SQL queries. Given an evaluation [X S ] an atom A(v ) t1 (R(v1 , v2 ) t2 ), if tabA[X S] [1] t1 (resp. tabR[X S] [2] t2 ), then we have AI (v )[X S] t1 (resp. RI (v1 , v2 )[X S] t2 ). The proof for the other direction is similar. 3: April 21-25, 2008 · Beijing, China AN S := AN S Cal-Soln(qF , S, a, G) //Calculate the solution S : d based on the semantic functions a and G 4: end for 5: return AN S The main tasks of AnswerF are (i) to look for candidate solutions in which the degree is larger than 0, and then (ii) to calculate the precise degree. The task (i) can b e p erformed by the DL-Lite query engine, since in the crisp case, the degree is either 0 or 1 (larger than 0). In other words, the DL-Lite procedures Eval, SQL, PerfectRef can b e reused here (line 9 of Algorithm A-3). The task (ii) is done by the procedure Cal, which is a general algorithm to calculate the degree of each tuple S in the answer set S S returned by the DL-Lite engine, based on the chosen semantic functions a and G. Accordingly, we have the following theorem. Theorem 2. Let O be an f-DL-Lite ontology, qF a general fuzzy conjunctive query and S : d a pair of a tuple of constants together with a truth degree, a a semantic function for conjunctions and G a semantic function for degreeassociated atoms. S : d is a solution of qF w.r.t. O iff (S : d) AnswerF (O, qF ,a,G). 4. IMPLEMENTATION AND EVALUATION 4.1 Implementation Our implementation is based on the ONTOSEARCH2 system6 [16, 31], which is an infrastructure for supp orting ontology searching and query answering. The f-DL-Lite query engine is implemented as an extension of the crisp DL-Lite query engine in ONTOSEARCH2 [15], so as to supp ort threshold queries and general fuzzy queries. The core part of the f-DL-Lite query engine includes implementations of Algorithms A-1 to A-4, which are presented in Section 3.3. The system was written in Java 5 and uses PostgreSQL 8.1 RDBMS for the rep ository storage. PostgreSQL was setup with default installation, no additional configuration was p erformed. Users of the f-DL-Lite query engine can submit f-DL-Lite ontologies via the Web interface of ONTOSEARCH26 , and then submit f-SPARQL queries against their target ontologies. The fuzzy query engine op erates in two modes: TQ mode (for threshold queries) and GFCQ mode (for general fuzzy queries). When users submit an f-SPARQL query, the fuzzy query engine parses it, so as to determine the query typ e (whether the query is a threshold query or a general fuzzy query), as well as the thresholds (for threshold queries) or degrees (for general fuzzy queries), dep ending on the query typ es. Accordingly, the fuzzy query engine op erates in either TQ mode (Algorithms A-1 and A2) or GFCQ mode (Algorithms A-3 and A-4). Besides the DL-Lite query engine and the f-DL-Lite query engine, the ONTOSEARCH2 system consists of other comp onents, such as the ontology search engine. In Section 5, we will show how the ontology search engine uses the f-DL-Lite query engine to p erform keyword-plus-entailment searches. 3.3.2 Answering General Fuzzy Queries Similarly, given an f-DL-Lite ontology O, a general fuzzy conjunctive query qF , the procedure AnswerF (O, qF ) computes the solutions of qF w.r.t. O. Algorithm A-3: AnswerF (O , qF , a, G) 1: T = Class-Axioms(O) 2: T = Normalise(T ) //normalisation of class axioms 3: A = Individual-Axioms(O) 4: DB(A) = Store(A) //normalisation and storage of individual axioms 5: if Consistency (O, T ) = false then 6: return inconsistent //O is inconsistent 7: end if 8: q = Remove-Degrees(qF ) //q is transformed from qF by removing the degrees from qF 9: return Cal(qF , EvalSQL(PerfectRef (q ,T )),DB(A)), a, G) Algorithm A-4: Cal(qF , S S, a, G) 1: AN S := 2: for every tuple S S S do 5 A variable is non-shared if it does not app ear in the b ody of the query for more than once. 4.2 Benchmark and Evaluation In this section, we present some preliminary evaluation of the f-DL-Lite query engine presented in Section 4.1. We will first discuss the b enchmark that we used in the evaluation, and then present the the evaluation results. 6 http://www.ontosearch.org/ 581 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I To the b est of our knowledge, there exists no b enchmark for query answering over fuzzy ontologies that we could use to evaluate our f-DL-Lite query engine. Accordingly, we prop ose a fuzzy variant of the well known Lehigh University Benchmark (LUBM), called f-LUBM, which is the first of its kind and against which future implementation of f-DL-Lite query engines can also b e evaluated. f-LUBM allows the use of fuzzy classes and restricts the expressive p ower of the underlying ontology to that of f-DL-Lite. More precisely, we added two fuzzy classes to the LUBM University ontology, namely "Busy" and "Famous". The former one is determined by the numb er of courses taught or taken by a memb er of staff or student, while the latter one is determined by the numb er of pap ers published. The values are calculated using the s-shap ed curve functions kf (n) to calculate the fuzzy value for fame given n pap ers published, and kb (n) to calculate the fuzzy value for busyness given n courses taken: kf (n) = 2 1+exp(-0.1n) April 21-25, 2008 · Beijing, China Table 3: Results of some f-LUBM queries Query f-LUBM-Q15 f-LUBM-Q16 crisp-1 f-LUBM-Q17 f-LUBM-Q18 crisp-2 (TQ) (GFCQ) (TQ) (GFCQ) T [1] (ms) 179 220 152 532 520 494 T [10] (ms) 536 683 422 845 973 892 T [50] (ms) 1061 1887 891 2922 3654 2523 - 1, kb (n) = 2 1+exp(-0.4n) -1 set, it is has almost identical p erformance, particularly on the more complex queries. As more data must b e evaluated, the p erformance drops slightly. For the largest data set (containing 6,888,642 individuals), it only took the f-DLLite query engine (up to) a few seconds to answer each of the tested queries. Based on the ab ove two fuzzy classes, 4 extra queries are introduced to f-LUBM (there are 14 queries in LUBM). The first two are simple queries that ask for famous ones. f-LUBM-Q15(v ) Famous(v ) 0.5 f-LUBM-Q16(v ) Famous(v ) : 0.5 f-LUBM-15 is a threshold query, while f-LUBM-16 is a general fuzzy query. The other two queries ask for all busy students which were taught by famous memb ers of staff. f-LUBM-Q17 (v 1) f-LUBM-Q18 (v 1) Student(v 1), Buzy(v 1) 0.5, Faculty(v 2), Famous(v 2) 0.5, teacher Of (v 2, v 3), takesC our se(v 1, v 3) Student(v 1), Buzy(v 1) : 0.5, Faculty(v 2), Famous(v 2) : 0.5, teacher Of (v 2, v 3), takesC our se(v 1, v 3) 5. USE CASE: ONTOLOGY SEARCHING This section presents an online application6 , the ontology search engine in the ONTOSEARCH2 system, of the f-DL-Lite query engine presented in Section 4. One of the ma jor limitations of existing ontology search engines is that searching is only based on keywords and metadata information of ontologies, rather than semantic entailments of ontologies (e.g., one wants to search for ontologies in which BassClarinet is a sub-class of Woodwind). On the other hand, searching only based on semantic entailments might not b e ideal either, as synonyms app earing in the metadata could not b e exploited. By making use of the f-DL-Lite query engine, our ontology search engine supp orts keyword-plus-entailment searches, such as searching for ontologies in which class X is a sub-class of class Y, and class X is associated with the keywords "Bass" and "Clarinet", while class Y is associated with the keyword "Woodwind". The search could b e represented as the following threshold query: 1: #TQ# 2: SELECT ?x WHERE { 3: ?x hasKeyword i-bass . #TH# 0.6 4: ?x hasKeyword i-clarinet . #TH# 0.6 5: ?x rdfs:subClassOf ?y . 6: ?y hasKeyword i-woodwind . #TH# 0.7} where i-bass, i-clarinet and i-woodwind are representative individuals for keywords "Bass", "Clarinet" and "Woodwind", resp. The thresholds 0.6 and 0.7 can b e sp ecified by users. In order to supp ort keyword-plus-entailment searches, our ontology search engine, for each indexed ontology, stores its semantic approximation (in DL-Lite) [15] and accompanies each ontology in its rep ository with an f-DL-Lite metaontology, which (i) materialises all TBox reasoning based on the semantic approximation and, most imp ortantly, (ii) uses fuzzy assertions to represent associations of each class (prop erty) and keywords7 app earing in the metadata of the ontology, with some degrees. Keywords app earing in the ontology metadata are associated with scores based on ranking factors8 . We use these scores to calculate the tf · idf [22] for 7 As mentioned ab ove, keywords are represented by representative individuals. 8 Like in LUBM, it is p ossible to create arbitrarily large datasets for individual axioms, generated by a Java program in f-LUBM (http://www.csd.ab dn.ac.uk/sttaylor/fLUBM.zip). To test the f-DL-Lite query engine, we created datasets containing 1, 10 and 50 universities, with the largest data set (for 50 universities) containing 6,888,642 individuals. We used fuzzy aggregation queries as representatives for GFCQs in our test. In order to investigate the overhead of fuzzy queries, we compare the p erformance in the f-DL-Lite query engine with the DL-Lite query engine, which is used to answer the following two crisp queries. crisp-1(v ) Famous(v ) crisp-2(v 1) Student(v 1), Buzy(v 1), Faculty(v 2), Famous(v 2), teacher Of (v 2, v 3), takesC our se(v 1, v 3) The results are shown in Table 3. The first column lists the queries used in the test. The second (resp. third and fourth) column show the time (in millisecond) needed to answer the queries for 1 university (resp. 10 and 50 universities). In general, the evaluations match nicely with our exp ectation: crisp queries are faster than CTQs as the system needs to take care of more joins due to the thresholds, while CTQs are faster than GFCQs as the former ones do not require p ost-processing to calculate the degrees. Furthermore, it is encouraging to see that the p erformance of the fuzzy query engine is in most cases close to the p erformance of the crisp query engine. With the smallest data http://www.seomoz.org/article/search-ranking-factors 582 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I each keyword, and normalise them using a sigmoid function such as the one shown in (3) to a degree b etween 0 and 1. w(n) = 2 -1 1.2-n + 1 (3) April 21-25, 2008 · Beijing, China 7. REFERENCES [1] F. Baader, D. L. McGuiness, D. Nardi, and P. Patel-Schneider, editors. Description Logic Handbook: Theory, implementation and applications. Cambridge University Press, 2002. [2] F. Bobillo, M. Delgado, and J. G´mez-Romero. A o crisp representation for fuzzy S HOI N with fuzzy nominals and general concept inclusions. In Proc. of the 2nd International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 06), Athens, Georgia, 2006. [3] A. Bookstein. Fuzzy requests: An approach to weighted b oolean searches. Journal of the Americal Society for Information Science, 31:240­247, 1980. [4] G. Bordogna, P. Bosc, and G Pasi. Fuzzy inclusion in database and information retrieval query interpretation. In Proceedings of the 1996 ACM symposium on Applied Computing, pages 547­551, 1996. [5] D. Calvanese, G. De Giacomo, D. Lemb o, M. Lenzerini, and R. Rosati. DL-Lite: Tractable description logics for ontologies. In Proc. of AAAI 2005, 2005. [6] S.J. Chen and S.M. Chen. A new method for fuzzy information retrieval based on geometric-mean averaging op erators. In Workshop on Artificial Intel ligence. [7] A. Chortaras, G. Stamou, and A. Stafylopatis. Adaptation of weighted fuzzy programs. In Proc. of the International Conference on Artificial Neural Networks (ICANN 2006), pages 45­54. Springer, 2006. [8] V. Cross. Fuzzy information retrieval. Journal of Intel ligent Information Systems, 3:29­56, 1994. [9] B. C. Grau. Tractable fragments of the OWL 1.1 web ontology language. http://www.w3.org/Submission/owl11- tractable/, 2006. [10] Y. Guo, Z. Pan, and J. Heflin. LUBM: A Benchmark for OWL Knowledge Base Systems. Journal of Web Semantics, 3(2):158­182, 2005. [11] G. J. Klir and B. Yuan. Fuzzy Sets and Fuzzy Logic: Theory and Applications. Prentice-Hall, 1995. [12] Y. Li, B. Xu, J. Lu, and D. Kang. Discrete tableau algorithms for F S HI . In Proceedings of the International Workshop on Description Logics (DL 2006), Lake District, UK, 2006. [13] T. Mailis, G. Stoilos, and G. Stamou. Proceedings of the first international conference on web reasoning and rule systems (RR-07), 2007. In Expressive Reasoning with Horn Rules and Fuzzy Description Logics, 2007. [14] P. Mika. Ontologies are us: A unified model of social networks and semantics. In 4th International Semantic Web Conference (ISWC 2005), 2005. [15] J. Z. Pan and E. Thomas. Approximating OWL-DL Ontologies. In Proc. of the 22nd National Conference on Artificial Intel ligence (AAAI-07), 2007. To app ear. [16] J. Z. Pan, E. Thomas, and D. Sleeman. ONTOSEARCH2: Searching and Querying Web Ontologies. In Proc. of WWW/Internet 2006, pages 211­218, 2006. [17] J.Z. Pan, G. Stoilos, G. Stamou, V. Tzouvaras, and I. Horrocks. f-SWRL: A fuzzy extension of SWRL. Hence, the ontology search engine can use the f-DL-Lite query engine to query across all the meta-ontologies in its rep ository, so as to supp ort keyword-plus-entailment searches. Further discussions of this use case go b eyond the scop e of this pap er. 6. DISCUSSIONS How to apply Description Logic based ontologies in the Web has b een a pressing issue for the Semantic Web community [14]. Web applications require ontology engines to b e able to handle fuzzy and imprecise data in an efficient and scalable manner, which has b een a big challenge for existing fuzzy ontology engines. In this pap er, we tackle this issue by providing efficient and scalable query services for lightweight fuzzy ontologies (in f-DL-Lite), based on the the two novel query languages we prop osed for fuzzy ontologies. To the b est of our knowledge, this pap er is the first to rep ort on implementations and evaluations of scalable and expressive conjunctive query answering over fuzzy ontologies. Our online use case application shows that the f-DL-Lite query engine can b e used to enable keyword-plusentailment searches. Our prop osed query languages are related with weighted Boolean queries [33, 4, 21] prop osed in the field fuzzy information retrieval [8]. On the one hand, motivated by these extensions we prop ose a completely novel query language, that of threshold queries, which is very imp ortant since it generalises the entailment of fuzzy assertions. On the other hand, the main strength of the prop osed general fuzzy query language is its op enness of the use of semantics generalising most previous approaches, like those based on fuzzy implications [4], aggregation functions [21, 6, 32], Straccia's query language [29] for fuzzy DL-Lite and weighted t-norm queries [7]. With the general fuzzy query language, we could provide top-k query answering service over f-DL-Lite ontologies, similar to that prop osed by Straccia [30] for a variant of DL-Lite ontologies. In short, the op enness of the use of fuzzy semantics and the generality of the presented algorithms make the fuzzy querying service more adaptable for different application needs. One asp ect of our future work is to investigate scalable querying services for more expressive fuzzy ontology languages, such as Fuzzy OWL [26]. Another part of our future work should also consist of a survey on which query language/semantics could/should b e used in what scenarios in Web applications. Acknowledgements This research was partially supp orted by the Nuffield FONTORule pro ject (NAL/32794), the FP6 Network of Excellence EU pro ject Knowledge Web (IST-2004-507842), Integrated EU pro ject X-Media (IST-2004-026978) and the Advanced Knowledge Technologies (GR/N15764/01). Giorgos Stoilos was also partially supp orted by the Greek Secretariat of Research and Technology (PENED Ontomedia 03 ED 475). 583 WWW 2008 / Refereed Track: Semantic / Data Web - Semantic Web I Journal on Data Semantics, Special Issue on Emergent Semantics, 4090:28­46, 2006. P. F. Patel-Schneider, P. Hayes, and I. Horrocks. OWL Web Ontology Language Semantics and Abstract Syntax. Technical rep ort, W3C, Feb. 2004. W3C Recommendation. E. Prud'hommeaux and A. Seab orne. SPARQL query language for RDF, 2006. W3C Working Draft, http://www.w3.org/TR/rdf-sparql-query/. T. Radecki. Fuzzy set theoretical approach to document retrieval. Journal of Information Processing & Management, 15:235­245, 1979. G. Salton, E.A. Fox, and H. Wu. Extended b oolean information retrieval. Journal of Communications of ACM, 26:1022­1036, 1983. G. Salton and M. J. McGill. Introduction to modern information retrieval. McGraw-Hill, 1983. E. Sanchez. Imp ortance in knowledge systems. Information Systems, 14(6):455­464, 1989. G. Stoilos, N. Simou, G. Stamou, and S. Kollias. Uncertainty and the semantic web. IEEE Intel ligent Systems, 21(5):84­87, 2006. G. Stoilos, G. Stamou, J. Z. Pan, V. Tzouvaras, and I. Horrocks. Reasoning with very expressive fuzzy description logics. Journal of Artificial Intel ligence Research, 30(5):273­320, 2007. G. Stoilos, G. Stamou, V. Tzouvaras, J.Z. Pan, and I. Horrocks. Fuzzy OWL: Uncertainty and the semantic web. In Proc. of the International Workshop on OWL: Experiences and Directions, 2005. U. Straccia. Reasoning within fuzzy description logics. Journal of Artificial Intel ligence Research, 14:137­166, 2001. U. Straccia. Description logics with fuzzy concrete domains. In 21st Conf. on Uncertainty in Artificial Intel ligence (UAI-05), Edinburgh, 2005. U. Straccia. Answering vague queries in fuzzy DL-Lite. In Proceedings of the 11th International Conference on Information Processing and Management of Uncertainty in Know ledge-Based Systems, (IPMU-06), pages 2238­2245, 2006. U. Straccia. Towards top-k query answering in description logics: the case of DL Lite. In Proceedings of the 10th European Conference on Logics in Artificial Intel ligence (JELIA-06), 2006. E. Thomas, J. Z. Pan, and D. Sleeman. ONTOSEARCH2: Searching Ontologies Semantically. In Proc. of OWL Experience Workshop, 2007. P. Vo jt´s. Fuzzy logic programming. Fuzzy Sets and a Systems, 124:361­370, 2001. W.G. Waller and D.H. Kraft. A mathematical model of a weighted b oolean retrieval system. Journal of Information Processing & Management, 15:247­260, 1979. April 21-25, 2008 · Beijing, China [18] [34] R.R Yager. A note on weighted queries in information retrieval systems. Journal of the Americal Society for Information Science, 38:23­24, 1987. [19] APPENDIX A. ABSTRACT SYNTAX OF F-DL-LITE This app endix contains a detailed presentation of the abstract syntax of fuzzy-DL-Lite. Firstly, we present the abstract syntax of crisp DL-Lite by restricting the elements of the OWL DL syntax. Then, we provide the definition of individual axioms in fuzzy-DL-Lite which additionally contain a memb ership degree and an inequality typ e. [20] [21] C l a s s A x i o ms ::= `Class(' classID [`Deprecated'] `complete' {annotation} { basicClass } `)' axiom ::= `Class(' classID [`Deprecated'] `partial' {annotation} { generalClass } `)' axiom ::= `DisjointClasses(' basicClass basicClass { basicClass } `)' | `EquivalentClasses(' basicClass { basicClass } `)' | `SubClassOf(' basicClass generalClass ')' basicClass ::= classID | restriction generalClass ::= basicClass | `complementOf(' { basicClass } `)' | `intersectionOf(' { generalClass } `)' restriction ::= `restriction(' individualvaluedPropertyID `someValuesFrom( owl:Thing )' `)' axiom [22] [23] [24] [25] [26] Property Axioms axiom ::= `Ob jectProperty(' individualvaluedPropertyID [`Deprecated'] { annotation } [ `inverseOf(' individualvaluedPropertyID `)' ] [`Functional' | `InverseFunctional' ] { `domain(' generalClass `)' } { `range(' generalClass `)' } `)' [27] [28] [29] Fuzzy Assertions individual ::= `Individual(' [individualID] {annotation} {`type'( type `)' [ineqType] [degree]} {value [ineqType] [degree] } `)' ineqType ::= `>=' degree ::= real-number-between-0-and-1-inclusive value ::= `value(' individualvaluedPropertyID individualID ')' | `value(' individualvaluedPropertyID individual ')' type ::= description [30] [31] [32] [33] 584