Scalable Querying Service over Fuzzy Ontologies1

Jeff Z. Pan

Institution
Dept. of Computing Science, Univ. of Aberdeen, Aberdeen, UK

Giorgos Stamou, Giorgos Stoilos

Institution
Dept. of Computer Science, NTUA, Athens, Greece

Stuart Taylor, Edward Thomas

Institution
Dept. of Computing Science, Univ. of Aberdeen, Aberdeen, UK

Abstract:

Fuzzy ontologies are envisioned to be 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 paper, we propose 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 paper reports on implementation of our approach in the fuzzy DL-Lite query engine in the ONTOSEARCH2 system and preliminary, but encouraging, benchmarking results. To the best of our knowledge, this is the first ever scalable query engine for fuzzy ontologies.

Categories & 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

Knowledge Representation, Imprecision, Web Technologies

Keywords

Scalable Fuzzy Reasoning, Expressive Fuzzy Querying, Fuzzy SPARQL, Ontology Search

1. INTRODUCTION

sider speed more important [with weight 0.7] than design
[with weight 0.3]"), so as to exploit fuzzy assertions in fuzzy
Fuzzy ontologies are envisioned to be useful in the Web.
ontologies. To the best of our knowledge, there exist no re-
On the one hand, ontologies serve as basic semantic infras-
port on scalable query engines for fuzzy DL-Lite, let alone
tructure, providing shared understanding of certain domain
supporting more expressive fuzzy query languages.
across different applications, so as to facilitate machine un-
This paper makes the following major contributions:
derstanding of Web resources. On the other hand, being
able to handle fuzzy and imprecise information is crucial to
1. It proposes a general framework, which consists of
the Web. Web data are likely to be uncertain or conflicting
threshold queries and general fuzzy queries (Section
and could raise trust issues. It has been argued that uncer-
3.1), for querying over fuzzy ontologies, covering all the
tainty representation and reasoning could help to harmonise
existing query languages for fuzzy ontologies as well as
and integrate Web data from different sources. To this end,
some new ones that can be customised by users. Com-
W3C has recently set up an incubator group on Uncertainty
paring with Straccia's query language, the threshold
Reasoning for the Web1.
query language is flexible as it allows one to specify a

threshold for each query atom (as shown in the above
This paper is based on a poster titled "Expressive Query-
ing over Fuzzy DL-Lite Ontologies" presented in the 2007
example). In fact, entailment of threshold queries gen-
International Workshop on Description Logics (DL2007).
eralises the entailment problem of fuzzy assertions. On
1http://www.w3.org/2005/Incubator/urw3
the other hand, the general fuzzy query language is a
Copyright is held by the author/owner(s).
2
WWW2008, April 21�, 2008, Beijing, China.
http://www.image.ece.ntua.gr/~nsimou
3
.
http://gaia.isti.cnr.it/~straccia
general form of the fuzzy threshold query language,
the reader to [1]. It should be noted that, even for the small-
which in turn is a general form of Straccia's query lan-
est propositionally closed DL ALC (which only provides the
guage. General fuzzy queries are motivated by the
class constructors 珻, C
D, C
D, R.C and R.C), the
field of fuzzy information retrieval [8] where weighted
complexity of logical entailment is Exptime. Recently, Cal-
Boolean queries [33] have been proposed for retriev-
vanese et. al. proposed DL-Lite, which has a low reasoning
ing fuzzy information from fuzzy relational databases.
overhead (worst case polynomial time) [5]. A DL-Lite on-
Our general fuzzy query language generalises most for-
tology (O) is a set of axioms of the following forms:
mer approaches of weighted Boolean queries [20, 3,
34, 4] and several new approaches, like the p-norm
1. class inclusion axioms: B
C where B is a basic class
approach [21], the geometric mean approach [6], the
B := A | R | R� and C is a general class C :=
so called fuzzy weighted t-norm queries from Chor-
B | 珺 | C1
C2 (where A denotes an named class
taras et. al. [7], which in turn generalise weighted min
and R denotes a named property);
queries [23], and aggregation queries from Vojtas [32].
Thus, the main strength of the general fuzzy query
2. functional property axioms: Func(R), Func(R�), where
language is the openness of the use of semantics of
R is a named property;
conjunction and that of the degree-associated atoms.
3. individual axioms: B(a), R(a, b) where a and b are
Consequently, the framework can accommodate differ-
named individuals.
ent intuitive meaning on the associated degrees, like
preferences, degrees of importance, fuzzy thresholds
Description Logics have a well-defined model-theoretic se-
and more.
mantics, which are provided in terms of interpretations. An
interpretation I is a pair (I, 稩), where I is a non-empty
2. It not only provides an abstract syntax (Section 3.1)
set of objects and 稩 is an interpretation function, which
for the proposed framework, but also shows how to ex-
maps each class C to a subset CI I and each property
tend the SPARQL (a well known Semantic Web query
R to a subset RI I � I.
language) syntax for the proposed query languages in
Typical reasoning ontology services include ontology con-
the framework (Section 3.2). Our extension uses spe-
sistency checking (i.e., whether there exists an interpretation
cially formatted SPARQL comments, thus the fuzzy
of an ontology), subsumption checking (i.e., whether the in-
queries are still valid SPARQL queries, and it does not
terpretation of a class C
affect current SPARQL tools and implementations.
1 is a subset of the interpretation
of a class C2 in all interpretations of the ontology), instance
3. It not only proposes the syntax of query languages, but
checking (i.e. whether an assertion is logically implied by an
also provides semantics (Section 3.1) and algorithms
ontology) and query answering. In this paper, we will focus
for answering such queries over arbitrary fuzzy DL-Lite
on query answering. A conjunctive query (CQ) q is of the
ontologies together with sound and complete proofs
form
(w.r.t. the semantics); and the algorithms cover all the
q(X) Y .conj(X, Y )
(1)
mentioned languages in the framework (Section 3.3).
or simply q(X) conj(X, Y ), where q(X) is called the
4. To the best of our knowledge, it presents the first ever
head, conj(X, Y ) is called the body, X are called the dis-
scalable query engine for fuzzy ontologies, based on
tinguished variables, Y are existentially quantified variables
the ONTOSEARCH2 system4 [16], which consists of,
called the non-distinguished variables, and conj(X, Y ) is a
among others, a query engine for DL-Lite and one for
conjunction of atoms of the form A(v), R(v1, v2), where A, R
fuzzy DL-Lite.
The performance of the fuzzy DL-
are respectively named classes and named properties, v, v1
Lite query engine is evaluated against a benchmark
and v2 are individual variables in X and Y or individual
(a fuzzy variant of the Lehigh University Benchmark
names in O. As usual, an interpretation I satisfies an ontol-
(LUBM) [10], called f-LUBM) that we propose, which
ogy O if it satisfies all the axioms in O; in this case, we say
is the first of its kind and against which future imple-
I is a model of O. Given an evaluation [X S] (where S is
mentations can also be evaluated. The query engine is
a set of individuals), if every model I of O satisfies q[XS],
able to handle millions of individuals, according to the
we say O entails q[XS]; in this case, S is called a solu-
preliminary but encouraging evaluation (Section 4).
tion of q. A disjunctive query (DQ) is a set of conjunctive
queries sharing the same head. Theoretically, allowing only
5. It presents a use cases about searching ontology based
named classes and properties as atoms is not a restriction,
on keyword-plus-entailment searches, so as to show
as we can always define such named classes and properties
how to apply our efficient querying support for fuzzy
in ontologies. Practically, this should not be an issue as
ontologies. The use case application is available online
querying against named relations is a usual practice when
(Section 5).
people query over relational databases.
After some careful query rewriting by DL-Lite reason-

2. PRELIMINARIES

ers [5], query answering over DL-Lite ontologies can be car-
ried out by an SQL engine, so as to take advantage of exist-
2.1 DL-based Ontologies and Query Answer-
ing query optimisation strategies and algorithms provided
ing
by modern database management systems.
Due to the limitation of space, we do not provide a formal
2.2 f-DL-LITE
introduction of Description Logics (DLs), but rather point
Straccia [29] proposed fuzzy DL-Lite (or f-DL-Lite for
4http://www.ontosearch.org/
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
Besides disallowing several expressive OWL DL construc-
is a property, a and b are individuals and n is a real number
tors, DL-Lite restricts the use of several of the allowed con-
in the range [0, 1]. The semantics of f-DL-Lite ontologies is
structors and especially w.r.t. which side of class axioms
defined in terms of fuzzy interpretations [27]. A fuzzy in-
they can appear. Thus, the definition of an abstract syn-
terpretation is a pair I = (I, 稩) where the domain I is
tax is slightly trickier than that of OWL. In OWL DL, for
a non-empty set of objects and 稩 is a fuzzy interpretation
example, disjointness, equivalence and subclass axioms are
function, which maps:
defined by the following abstract syntax:
axiom ::= `DisjointClasses(' description description
� an individual a to an element of aI I,
{ description } `)' |
� a named class A to a membership function AI : I
`EquivalentClasses(' description { description } `)' |
`SubClassOf(' description description `)'
[0, 1], and
where "description" can be any OWL DL class description.
� a named property R to a membership function RI :
In DL-Lite, only basic classes are allowed on the left-hand
I � I [0, 1].
side of axioms, while general classes are allowed only on the
Using the fuzzy set theoretic operations [11], fuzzy inter-
right-hand side. Thus, the above abstract syntax should be
pretations can be extended to interpret f-DL-Lite class and
adjusted to:
property descriptions. Following Straccia [29], we use the
axiom ::= `DisjointClasses(' basicClass basicClass
Lukasiewicz negation, c(a) = 1 - a and the G╫del t-norm
{ basicClass } `)' |
for interpreting conjunctions, t(a, b) = min(a, b). The se-
`EquivalentClasses(' basicClass { basicClass } `)' |
mantics of f-DL-Lite class and property descriptions, and
`SubClassOf(' basicClass generalClass ')'
f-DL-Lite axioms are depicted in Table 1. Given the above
where "basicClass" and "generalClass" represent the basic
semantics, it is obvious that crisp assertions B(a), R(a, b)
and general classes of DL-Lite, respectively. The abstract
are special forms of fuzzy assertions where n = 1.
syntax for these two elements should also follow the restric-
tions of DL-Lite; e.g., a "generalClass" can be an inter-
Syntax
Semantics
section of classes while a basic class is not. By using the
R
(R)I(o1) = sup {RI(o1, o2)}
RDF/XML serialisation mapping described for OWL DL,
o2I
珺
(珺)I(o) = 1 - BI(o)
one is able to obtain DL-Lite and f-DL-Lite ontologies in
C
RDF/XML syntax. For example, the following class axiom
1
C2
(C1
C2)I(o) = t(CI1(o), CI2(o))
R-
(R-)I(o
in RDF/XML syntax is a valid DL-Lite axiom,
2, o1) = RI (o1, o2)
B
C
o I, BI(o) CI(o)
Func(R)
o
<owl:Class rdf:ID="C">
1 I , {o2 | RI (o1, o2) > 0} = 1
B(a) n
BI(aI) n
<rdfs:subClassOf>
<owl:Class>
R(a, b) n
RI(aI, bI) n
<owl:intersectionOf rdf:parseType="Collection">
<owl:Class>
<owl:complementOf>
Table 1: Semantics of f-DL-Lite class and property
<owl:Restriction>
descriptions, and f-DL-Lite axioms
<owl:onProperty rdf:resource="#R"/>
<owl:someValuesFrom rdf:resource="&owl;Thing"/>
Similarly to crisp DL lite, fuzzy-DL-Lite, provides means
</owl:Restriction>
to specify role-typing and participation constraints but in-
</owl:complementOf>
</owl:Class>
terestingly it assigns fuzzy meaning on them. More pre-
<owl:Class>
cisely, a role-typing assertion of the form R
A1 (resp.
<owl:complementOf rdf:resource="#A"/>
R-
A2) states that the first (resp. second) component
</owl:Class>
of R belongs to A
</owl:intersectionOf>
1 (resp. A2) at-least to the membership
degree that the relation R holds, i.e. RI(aI, bI) AI
</owl:Class>
1 (aI )
(resp. (R-)I(bI, aI) = RI(aI, bI) AI
</rdfs:subClassOf>
2 (bI )).
</owl:Class>
2.3 Abstract and RDF/XML Syntax
which corresponds to the axiom C
琑
珹.
Since DL-Lite (resp. f-DL-Lite) is a sub-language of OWL
Finally, fuzziness in the individual axioms of f-DL-Lite is
(resp. f-OWL DL), we provide an abstract and RDF/XML
defined by a restriction of the abstract syntax of facts of
syntax for DL-Lite and f-DL-Lite ontologies in this sub-
f-OWL DL presented in [26], since we are only allowing the
section, following the paradigm of OWL DL [18]. OWL
inequality "". The abstract syntax is the following:
DL ontologies in RDF/XML syntax can be generated from
individual ::= `Individual(' [individualID] {annotation}
those written in the abstract syntax, using the official map-
{`type'( type `)' [ineqType] [degree]}
ping between the two kind of syntax provided in [18]. Our
{value [ineqType] [degree] } `)'
proposed abstract syntax for DL-Lite core is based on that
ineqType ::= `>='
of the DL-Lite specified in the OWL1.1 member submission
degree
::= real-number-between-0-and-1-inclusive
(an extension of OWL DL) in the tractable fragments doc-
ument [9]. It is slightly different from that in the OWL 1.1
Similarly, we can follow the RDF/XML serialization pro-
document, mainly due to the fact that it uses the OWL DL
posed in [26] to have fuzzy individual axioms in a f-DL-Lite
syntax (which is slightly different from that of OWL 1.1)
file. For example, stating that o is Heavy to degree at-least
and RDF/XML serialisation.
0.7 could be specified by the following RDF/XML syntax.
entails qT (denoted as O |= qT ) if every interpretation I of
<Heavy rdf:about="o" owlx:ineqType="" owlx:degree="0.7"/>
O satisfies the following condition: for each atom A(v)
t1 (R(v1, v2) t2) of qT , we have AI(v)XS t1 (resp.
RI(v
The full specification of the f-DL-Lite (and consequently
1, v2)XS t2). In this case, S is called a solution of
q
DL-Lite) abstract syntax can be found in the Appendix.
T .
A disjunctive threshold query (DTQ) is a set of con-
junctive threshold queries sharing the same head.
The ONTOSEARCH2 system allows users to submit their
crisp and fuzzy ontologies to its repository. Furthermore, it
3.1.2 General Fuzzy Queries
provides an RDF/XML syntax checker for DL-Lite.
Since f-DL-Lite associates assertions with degrees of truth,
another useful feature for its query language is to associate

3. QUERYING F-DL-LITE ONTOLOGIES

degrees of truth with answers in answer sets of queries over
In this section, we present a general framework for rep-
f-DL-Lite ontologies. In threshold queries, an evaluation
resenting expressive fuzzy queries over f-DL-Lite ontologies.
[X S] either satisfies the query entailment or not; hence,
More precisely, we will introduce two query languages for f-
answers of such queries are crisp. In this subsection, we
DL-Lite ontologies. The first language extends conjunctive
introduce general fuzzy queries which allow fuzzy answers.
queries with thresholds for atoms in queries. Entailment of
Syntactically, like the query language proposed in [33] and
threshold queries generalises the entailment problem of fuzzy
threshold queries, general fuzzy conjunctive queries (GFCQ)
assertions. The second language is a general fuzzy query lan-
extend the atoms A(v), R(v1, v2) of conjunctive queries of
guage, motivated by the field of fuzzy information retrieval
the form (1) into ones with the following form A(v) : k1, R(v1,
[8], where weighted Boolean queries have been proposed [33,
v2) : k2, where k1, k2 (0, 1] are degrees. .
20, 3, 34]. As it was showed in [4] most of these approached
The strength of the general fuzzy query language is the
could be represented under a general framework using gen-
openness of the use of fuzzy operations. Indeed, as many
eral fuzzy operators, like t-norms and fuzzy implications.
theoretical and practical studies [32, 4] have pointed out,
Our general fuzzy query language extends these results by
the choice of fuzzy operations is usually context dependent.
allowing more fuzzy operators and thus generalising many
Following the style of the semantics of fuzzy-SWRL [17] the
of the recent approaches like the query language proposed
existential quantifier is interpreted as sup, while we leave
in [29] for fuzzy DL-Lite, weighted t-norm queries [7], which
the semantics of the conjunction (G) and that of the degree-
in turn generalise weighted min queries [23], p-norms [21],
associated atoms (a) open. To simplify the presentation of
fuzzy aggregations [32] and the geometric mean [6]. In order
the semantics, we use a unified representation atomi(�br> v) for
to enable such types of queries in the Semantic Web, we also
atoms in general fuzzy conjunctive queries. Given an f-DL-
propose the extension of the SPARQL [19] query language,
Lite ontology O, an interpretation I of O, a general fuzzy
so as to represent the queries in our general framework. In
conjunctive query qF and an evaluation [X S], the degree
what follows, we first introduce these new query languages,
of truth of qF under I is
providing their syntax and semantics. We then present the
extension of SPARQL, and finally we provide algorithms of
d =
sup
{Gni=1 a(ki, atomIi(痸)[XS,Y S ])}
S I 追贩譏
query answering for queries in the proposed query languages.
where k
3.1 Two New Query Languages
i (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
3.1.1 Threshold Queries
is called a candidate solution of qF . When d > 0, S : d is
As noted in [5] in DL-Lite the instance checking prob-
called a solution of qF . Furthermore, the semantic functions
lem is a special case of conjunctive queries. Since f-DL-Lite
should satisfy the following condition:
extends DL-Lite with fuzzy assertions, it would be natural
to define a query language so that the entailment of such
If atomIi(痸)[XS,Y S ]) = 0 for all possible S , d = 0. (2)
queries could generalise entailment checking of fuzzy asser-
A general fuzzy disjunctive query (GFDQ) is a set of gen-
tions. Accordingly, we define conjunctive threshold queries
eral fuzzy conjunctive queries sharing the same head. The
(CTQ) which extend atoms A(v), R(v1, v2) in conjunctive
disjunction is interpreted as the s-norm (u) of disjuncts.
queries of the form (1) into the following forms A(v)
In what follows, we give some examples of the semantic
t1, R(v1, v2) t2, where t1, t2 (0, 1] are thresholds. It
functions for conjunctions and degree-associated atoms.
turns out that threshold queries are very important types of
queries since in [13] the authors used them in order to devise
1. Fuzzy threshold queries: If we use t-norms (t) as the
a reasoning algorithm for the fuzzy language fuzzy-CARIN.
semantic function for conjunctions and R-implications
(t) [11] as the semantic function for degree-associated
Example 1. We can query models who are tall with a
atoms, we get fuzzy threshold queries, in which the
degree no less than 0.7 and light with a degree no less than
degree of truth of qF under I is
0.8 with the following conjunctive threshold query:
d =
sup
{tn
q(v) Model(v) 1, Tall(v) 0.7, Light(v) 0.8.
i=1 t(ki, atomI
i (�br> v)[XS,Y S ])}.
S I 追贩譏
It is obvious that threshold queries are more flexible than
Given some S , if for all atoms we have atomIi(痸)[XS,
queries of the form (1) in that users can specify different
Y S ] ki, since t(x, y) = 1 when y x [11], we have
thresholds for different atoms in their queries.
d = 1; this corresponds to threshold queries introduced
Formally, given an f-DL-Lite ontology O, a conjunctive
earlier. On the other hand, different from threshold
threshold query qT and an evaluation [X S], we say O
queries, if 0 < atomIi(痸)[XS,Y S ] < ki, then d = 0
because of use of the R-implication which filters (pe-
where k = maxni=1 ki. The main idea of this type of
nalises) the degree atomIi(痸)[XS,Y S ] against the
queries is that they provide an aggregation type of op-
fuzzy threshold ki.
eration, on the other hand an entry with a low value
As it was shown in [4] many of the approaches for
for a low-weighted criterion should not be critically pe-
weighted Boolean queries that have been proposed [3,
nalized. Moreover, lowering the weight of a criterion
20] are actually special cases of fuzzy threshold queries.
in the query should not lead to a decrease of the rel-
evance score, which should mainly be determined by
2. Straccia's query language [29] : It is also a sub-language
the high-weighted criteria (see [7] for more details).
of the fuzzy threshold query language, where all ki = 1.
Yager [34], proposes the use of and S-implication [11]
Since t(1, y) = y [11], the degree of truth of qF under
(in contrast to R-implications of fuzzy threshold queries),
I is
i.e. the function:
d =
sup
{tni=1 atomIi(痸)[XS,Y S ]}.
n
S I 追贩譏
d =
sup
{min u(1-ki, atomIi(痸)[XS,Y S ])},
S I 追贩譏
i=1
3. Fuzzy aggregation queries: If we use fuzzy aggregation
n
This is a special case of fuzzy weighted t-norms, where
functions [11], such as G(x) =
i=1 xi
n
, for conjunc-
k
k = 1, since t(1, a) = a. A similar approach was pro-
i=1
i
tions and a(ki, y) = ki y as the semantic function
posed by Sanchez [23].
for degree-associated atoms, we get fuzzy aggregation
queries, in which the degree of truth of q
It is easy to show that all the above four specific fuzzy
F under I is
query languages satisfy the condition (2).
n
k
d =
sup
i=1
i atomI
i (�br> v)[XS,Y S ]
n
.
k
3.2 Supporting Querying with SPARQL
S I 追贩譏
i=1
i
After presenting the abstract syntax and semantics of our
Moreover, we can show that many existing approaches
proposed languages, in this section, we show how to extend
of weighted Boolean queries could be represented un-
the syntax of SPARQL [19], a well known Semantic Web
der the framework of fuzzy aggregation queries. More
query language, for the proposed languages. We call our
precisely, Salton, Fox and Wu [21] proposed the model
extension f-SPARQL. SPARQL is a query language (candi-
of p-norms where the semantic function is given by the
date recommendation from the W3C Data Access Working
following equation:
Group) for getting information from RDF graphs. SPARQL
allows for a query to constitute of triple patterns, conjunc-
n
1/w
(atomI
tions, disjunctions and optional patterns. A SPARQL query
d =
sup
i=1
i (�br> v)[XS,Y S ])w
n
is a quadruple Q = (V, P, DS, SM ), where V is a result
S I 追贩譏
form, P is a graph pattern, DS a data set and SM a set
where w
of solution modifiers. Among others, SPARQL allows for
1 = w2 = . . . = wn = w and w (0, +].
On the other hand, S.J. Chen and S.M. Chen [6] pro-
select queries, formed in a SELECT-FROM-WHERE manner.
pose the geometric mean [11] as a semantic function
The result form represents the set of variables appearing in
for weighted Boolean queries:
the SELECT, the dataset forms the FROM part, constituted
by a set of IRIs of RDF documents, while the graph pattern
n
1/w
forms the WHERE part which is constituted by a set of RDF
d =
sup
atomIi(痸)[XS,Y S ]
.
triples.
S I 追贩譏
i=1
Under the framework of fuzzy aggregation functions
Query
::= Prologue ( SelectQuery | ConstructQuery
both these equations are special cases of the gener-
| DescribeQuery | AskQuery )
alized mean function which is given by the equation
SelectQuery
::= `SELECT' ( `DISTINCT' | `REDUCED' )?
n
1/w
(Var+ | `*') DatasetClause*
d
i=1 aw
i
w =
where w R. If w (0, +]
WhereClause SolutionModifier
n
WhereClause
::= `WHERE' ? GroupGraphPattern
then we have the approach of Salton et. al. [21], while
GroupGraphPattern ::= `{' TriplesBlock? ( ( GraphPatternNotTriples
if w 0, then function d converges to the geomet-
| Filter ) `.' ? TriplesBlock? )* `}'
ric mean [11]. Additionally, from this analysis we can
very easily suggest a totally new semantic function by
In order to maintain backward compatibility with exist-
letting w = -1, which gives the function of harmonic
ing SPARQL tools, we propose to use specially formatted
mean:
SPARQL comments to specify extra information needed in
our proposed languages (see Table 2). Firstly, one should
declare the query type before a select query. For example,
n
d =
sup
.
#TQ# declares a threshold query, while #GFCQ:SEM=FUZZY
n
1
S I 追贩譏
i=1
atomI (�br> v)
THRESHOLD# declares a general fuzzy query, with the fuzzy
i
[XS,Y S ]
threshold semantic functions. Secondly, following each triple
4. Fuzzy weighted t-norm queries: If we use generalised
in the WHERE clause, one can use #TH# (resp. #DG#) to
weighted t-norms [7] as the semantic function for con-
specify a threshold in a threshold query (resp. a degree in
junction, we get fuzzy weighted queries, in which the
a general fuzzy query). For instance, the threshold query
degree of truth of qF under I is
presented in Example 1 (Section 3.1) can be represented by
n
the following f-SPARQL query:
d =
sup
{min u(k-ki, t(k, atomIi(痸)[XS,Y S ]))},
S I 追贩譏
i=1
#TQ#
Query
::=
Prologue ( QueryType SelectQuery |
ConstructQuery | DescribeQuery | AskQuery )
TriplesBlock
::=
TriplesSameSubject ( `.' TripleWeight Degree TriplesBlock? )?
QueryType
::=
`#TQ# \n' | `#GFCQ:SEM=' FuzzySemantics `# \n'
FuzzySemantics
::=
`AGGREGATION' | `FUZZYTHRESHOLD' |
`FUZZYTHRESHOLD-1' | `FUZZYWEIGHTEDNORMS'
TripleWeight
::=
`#TH#' | `#DG#`
degree
::=
real-number-between-0-and-1-upper-inclusive
Table 2: Syntax of Fuzzy SPARQL
SELECT ?x WHERE {
query q against the normalised set T of the class axioms
?x rdf:type Model .
#TH# 1.0
by the procedure PerfectRef(q, T ), which returns a set Q
?x rdf:type Tall .
#TH# 0.7
of (conjunctive) queries; (iv) transformation of the set Q
?x rdf:type Light .
#TH# 0.8
of (conjunctive) queries into SQL queries by the procedure
}
SQL(Q), as well as the evaluation of SQL(Q) by the proce-
dure Eval(SQL(Q), DB(A)).
In the case of general fuzzy queries, one must specify the se-
As steps (i) and (ii) are very similar to those for the crisp
mantic functions (i.e. a and G). Below is an example fuzzy
case, here we focus on steps (iii) and (iv) on answering con-
threshold query.
junctive threshold queries and general fuzzy queries.
#GFCQ:SEM=FUZZYTHRESHOLD#
SELECT ?x WHERE {
?x rdf:type Model .
#DG# 1.0
3.3.1 Answering Threshold Queries
?x rdf:type Tall .
#DG# 0.7
Given an f-DL-Lite ontology O, a conjunctive threshold
?x rdf:type Light .
#DG# 0.8
query qT , the procedure AnswerT(O, qT ) computes the solu-
}
tions of qT w.r.t. O, following the above steps (i) - (iv).
Table 2 presents the f-SPARQL syntax. f-SPARQL ex-
tends two of SPARQL's elements, namely the "Query" and
Algorithm A-1: AnswerT(O, qT )
the "TriplesBlock" element. As illustrated above, each select
1: T = Class-Axioms(O)
query is extended with the element QueryType. In particu-
2: T = Normalise(T ) //normalisation of class axioms
lar, for general fuzzy queries, the declaration `#GFCQ:SEM='
3: A = Individual-Axioms(O)
is followed by the element FuzzySemantics, which is used
4: DB(A) = Store(A) //normalisation and storage of individual
axioms
to specify the semantic functions, such as the ones we pre-
5: if Consistency(O, T ) = false then
sented in the previous section. More precisely, we use the
6:
return inconsistent //O is inconsistent
keywords `FUZZYTHRESHOLD', `FUZZYTHRESHOLD-
7: end if
1', `AGGREGATION' and `FUZZYWEIGHTEDNORMS'
8: return Eval(SQLT(PerfectRefT(qT ,T )),DB(A))
to indicate the four fuzzy general queries we introduced in
Section 3.1.2. When one uses `FUZZYTHRESHOLD-1', the
Algorithm A-2: SQLT(Q)
fuzzy threshold is set as 1, and the values specified by the
1: QS :=
#TH# comments are ignored. Finally, the "TriplesBlock"
2: for every query q in Q do
element is extended with the elements TripleWeight and De-
3:
sc:=Select-Clause(q) //construct the select-clause of q
gree, which are used to associated a threshold or weight with
4:
fc:=From-Clause(q) //construct the from-clause of q
5:
wc1:=WC-Binding(q) //construct the part of the where-
each triple of the SPARQL query.
clause about binding
3.3 Query Answering
6:
wc2:=WC-Threshold(q) //construct the part of the where-
clause that relates to thresholds
It should be noted that the query languages in the previ-
7:
QS := QS Construct-SQL(sc,fc,wc1,wc2)
ous sections can be used with any fuzzy ontology languages.
8: end for
In order to provide efficient query answering services using
9: return QS
our proposed query languages, we choose f-DL-Lite as our
The algorithms need some explanations. Firstly, if O is
fuzzy ontology language. This sub-section provides algo-
inconsistent, query answering is meaningless, since every tu-
rithm to answer threshold queries and general fuzzy queries
ple is a solution of every query w.r.t. O.
over f-DL-Lite ontologies.
Secondly, the procedure PerfectRefT(qT ,T ) of reformulat-
Algorithms for answering queries in f-DL-Lite mainly con-
ing an input conjunctive threshold query qT (into a set of
sist of four steps (like the algorithm for crisp DL-Lite [5]):
conjunctive queries) is essentially the same as the PerfectRef
(i) normalisation of the set T of the class axioms of O by
(q,T ) for DL-Lite [5]. Here we do not repeat PerfectRef(q,T )
the procedure Normalise(T ), which returns the normalised
but explain its main ideas instead. PerfectRefT(qT ,T ) rewrites
set T of class axioms; (ii) normalisation and storage of the
atoms in qT based on positive inclusions (PIs) in T . For
set A of individual axioms in O by the procedure Store(A)
example, given a PI B
B1, if B1(v) k is an atom of
that normalise A and returns the relational database DB(A)
qT and B is a named class A (resp. of the form R, or of
of A, as well as checking the consistency of O by the pro-
the form R-), B1(v) k can be rewritten as A(v) k
cedure Consistency(O, T ); (iii) reformulation of the input
(resp. R(v, ) k, or R( , v) k, where
represent non-
distinguished non-shared variables5). The generated query
5: return ANS
can be further written, based on the PIs in T . It can be
The main tasks of Answer
shown that such rewriting process always terminates [5], and
F are (i) to look for candidate
solutions in which the degree is larger than 0, and then (ii) to
it produces a set of generated conjunctive queries from the
calculate the precise degree. The task (i) can be performed
input query qTQ.
by the DL-Lite query engine, since in the crisp case, the
Thirdly, the procedure SQLT(Q) transforms a set of con-
degree is either 0 or 1 (larger than 0). In other words, the
junctive threshold queries into SQL queries in an obvious
DL-Lite procedures Eval, SQL, PerfectRef can be reused here
way, taking into accounts the thresholds. Namely, it use
(line 9 of Algorithm A-3). The task (ii) is done by the
Select-Clause, From-Clause, WC-Binding and WC-Threshold
procedure Cal, which is a general algorithm to calculate the
to construct the select-clauses, from-clauses and where-clauses
degree of each tuple S in the answer set SS returned by the
of SQL queries, respectively. Due to limitation of space, we
DL-Lite engine, based on the chosen semantic functions a
do not provide full details of these procedures but illustrate
and G. Accordingly, we have the following theorem.
them with the following example. Given the query q(v)
Model(v) 1, Tall(v) 0.7, Light(v) 0.8, Select-Clause(q)
Theorem 2. Let O be an f-DL-Lite ontology, qF a gen-
returns the select-clause `SELECT tabModel[0]', From-Clause(q)
eral fuzzy conjunctive query and S : d a pair of a tuple of
returns the from-clause `FROM tabModel, tabTall, tabLight', WC-
constants together with a truth degree, a a semantic func-
Binding(q) returns the binding part of the where-clause `WH-
tion for conjunctions and G a semantic function for degree-
ERE tabModel[0] = tabTall[0], tabModel[0] = tabLight[0]' and WC-
associated atoms. S : d is a solution of qF w.r.t. O iff
Threshold(q) returns the threshold-related part of the where-
(S : d) AnswerF(O, qF ,a,G).
clause `tabModel[1] 1, tabTall[1] 0.7, tabLight[1] 0.8'.
Construct-SQL puts all these together and returns the cor-
responding SQL query `SELECT tab

4. IMPLEMENTATION AND EVALUATION

Model[0] FROM tabModel,
tabTall, tabLight WHERE tabModel[0] = tabTall[0], tabModel[0] =
tab
4.1 Implementation
Light[0], tabModel[1] 1, tabTall[1] 0.7, tabLight[1] 0.8'.
Our implementation is based on the ONTOSEARCH2
Theorem 1. Let O be an f-DL-Lite ontology, qT a con-
system6 [16, 31], which is an infrastructure for support-
junctive threshold query and S a tuple of constants. S is a
ing ontology searching and query answering. The f-DL-Lite
solution of qT w.r.t. O iff S AnswerT(O, qT ).
query engine is implemented as an extension of the crisp
DL-Lite query engine in ONTOSEARCH2 [15], so as to sup-
Proof: (Sketch) The proof of correctness is straight for-
port threshold queries and general fuzzy queries. The core
ward. The procedure AnswerT differs from that of DL-Lite
part of the f-DL-Lite query engine includes implementations
mainly in that it needs to take care of the thresholds (line
of Algorithms A-1 to A-4, which are presented in Section
6 of Algorithm A-2) when constructing SQL queries. Given
3.3. The system was written in Java 5 and uses PostgreSQL
an evaluation [X S] an atom A(v) t1 (R(v1, v2) t2),
8.1 RDBMS for the repository storage. PostgreSQL was
if tabA
[1] t
[2] t
setup with default installation, no additional configuration
[XS]
1 (resp. tabR[XS]
2), then we have
AI(v)
was performed.
[XS] t1 (resp. RI (v1, v2)[XS] t2). The proof
for the other direction is similar.
Users of the f-DL-Lite query engine can submit f-DL-Lite
ontologies via the Web interface of ONTOSEARCH26, and
3.3.2 Answering General Fuzzy Queries
then submit f-SPARQL queries against their target ontolo-
Similarly, given an f-DL-Lite ontology O, a general fuzzy
gies. The fuzzy query engine operates in two modes: TQ
conjunctive query q
mode (for threshold queries) and GFCQ mode (for general
F , the procedure AnswerF(O, qF ) com-
putes the solutions of q
fuzzy queries). When users submit an f-SPARQL query,
F w.r.t. O.
the fuzzy query engine parses it, so as to determine the
query type (whether the query is a threshold query or a
Algorithm A-3: AnswerF(O, qF , a, G)
general fuzzy query), as well as the thresholds (for threshold
1: T = Class-Axioms(O)
queries) or degrees (for general fuzzy queries), depending on
2: T = Normalise(T ) //normalisation of class axioms
the query types. Accordingly, the fuzzy query engine oper-
3: A = Individual-Axioms(O)
4:
ates in either TQ mode (Algorithms A-1 and A2) or GFCQ
DB(A) = Store(A) //normalisation and storage of individual
axioms
mode (Algorithms A-3 and A-4).
5: if Consistency(O, T ) = false then
Besides the DL-Lite query engine and the f-DL-Lite query
6:
return inconsistent //O is inconsistent
engine, the ONTOSEARCH2 system consists of other com-
7: end if
ponents, such as the ontology search engine. In Section 5, we
8: q = Remove-Degrees(qF ) //q is transformed from qF by re-
will show how the ontology search engine uses the f-DL-Lite
moving the degrees from qF
9:
query engine to perform keyword-plus-entailment searches.
return Cal(qF , EvalSQL(PerfectRef(q,T )),DB(A)), a, G)
4.2 Benchmark and Evaluation
Algorithm A-4: Cal(qF , SS, a, G)
In this section, we present some preliminary evaluation of
1: ANS :=
2:
the f-DL-Lite query engine presented in Section 4.1. We will
for every tuple S SS do
3:
AN S := AN S Cal-Soln(q
first discuss the benchmark that we used in the evaluation,
F , S, a, G) //Calculate the solu-
tion S : d based on the semantic functions a and G
and then present the the evaluation results.
4: end for
To the best of our knowledge, there exists no benchmark
for query answering over fuzzy ontologies that we could use
5A variable is non-shared if it does not appear in the body
of the query for more than once.
6http://www.ontosearch.org/
to evaluate our f-DL-Lite query engine. Accordingly, we
propose a fuzzy variant of the well known Lehigh University
Table 3: Results of some f-LUBM queries
Benchmark (LUBM), called f-LUBM, which is the first of
its kind and against which future implementation of f-DL-
Query
T [1] (ms)
T [10] (ms)
T [50] (ms)
Lite query engines can also be evaluated. f-LUBM allows
f-LUBM-Q15 (TQ)
179
536
1061
the use of fuzzy classes and restricts the expressive power
f-LUBM-Q16 (GFCQ)
220
683
1887
of the underlying ontology to that of f-DL-Lite. More pre-
crisp-1
152
422
891
cisely, we added two fuzzy classes to the LUBM University
f-LUBM-Q17 (TQ)
532
845
2922
ontology, namely "Busy" and "Famous". The former one
f-LUBM-Q18 (GFCQ)
520
973
3654
is determined by the number of courses taught or taken by
crisp-2
494
892
2523
a member of staff or student, while the latter one is deter-
mined by the number of papers published. The values are
calculated using the s-shaped curve functions kf (n) to cal-
culate the fuzzy value for fame given n papers published,
and k
set (containing 6,888,642 individuals), it only took the f-DL-
b(n) to calculate the fuzzy value for busyness given n
courses taken:
Lite query engine (up to) a few seconds to answer each of
k
the tested queries.
f (n) =
2
- 1,
k
- 1
1+exp(-0.1n)
b(n) =
2
1+exp(-0.4n)
Based on the above two fuzzy classes, 4 extra queries are
introduced to f-LUBM (there are 14 queries in LUBM). The

5. USE CASE: ONTOLOGY SEARCHING

first two are simple queries that ask for famous ones.
This section presents an online application6, the ontol-
f-LUBM-Q15(v)
Famous(v) 0.5
ogy search engine in the ONTOSEARCH2 system, of the
f-LUBM-Q16(v)
Famous(v) : 0.5
f-DL-Lite query engine presented in Section 4. One of the
major limitations of existing ontology search engines is that
f-LUBM-15 is a threshold query, while f-LUBM-16 is a gen-
searching is only based on keywords and metadata infor-
eral fuzzy query. The other two queries ask for all busy
mation of ontologies, rather than semantic entailments of
students which were taught by famous members of staff.
ontologies (e.g., one wants to search for ontologies in which
f-LUBM-Q17 (v1)
Student(v1), Buzy(v1) 0.5, Faculty(v2),
BassClarinet is a sub-class of Woodwind). On the other hand,
Famous(v2) 0.5, teacherOf (v2, v3),
searching only based on semantic entailments might not be
takesCourse(v1, v3)
ideal either, as synonyms appearing in the metadata could
f-LUBM-Q18 (v1)
Student(v1), Buzy(v1) : 0.5, Faculty(v2),
not be exploited.
Famous(v2) : 0.5, teacherOf (v2, v3),
By making use of the f-DL-Lite query engine, our ontology
takesCourse(v1, v3)
search engine supports keyword-plus-entailment searches, such
Like in LUBM, it is possible to create arbitrarily large
as searching for ontologies in which class X is a sub-class of
datasets for individual axioms, generated by a Java pro-
class Y, and class X is associated with the keywords "Bass"
gram in f-LUBM (http://www.csd.abdn.ac.uk/sttaylor/f-
and "Clarinet", while class Y is associated with the keyword
LUBM.zip). To test the f-DL-Lite query engine, we created
"Woodwind". The search could be represented as the fol-
datasets containing 1, 10 and 50 universities, with the largest
lowing threshold query:
data set (for 50 universities) containing 6,888,642 individu-
1: #TQ#
als. We used fuzzy aggregation queries as representatives for
2: SELECT ?x WHERE {
GFCQs in our test. In order to investigate the overhead of
3:
?x hasKeyword i-bass . #TH# 0.6
fuzzy queries, we compare the performance in the f-DL-Lite
4:
?x hasKeyword i-clarinet . #TH# 0.6
query engine with the DL-Lite query engine, which is used
5:
?x rdfs:subClassOf ?y .
to answer the following two crisp queries.
6:
?y hasKeyword i-woodwind . #TH# 0.7}
crisp-1(v)
Famous(v)
crisp-2(v1)
Student(v1), Buzy(v1), Faculty(v2),
where i-bass, i-clarinet and i-woodwind are representative
Famous(v2), teacherOf (v2, v3),
individuals for keywords "Bass", "Clarinet" and "Wood-
takesCourse(v1, v3)
wind", resp. The thresholds 0.6 and 0.7 can be specified
by users.
The results are shown in Table 3. The first column lists
In order to support keyword-plus-entailment searches, our
the queries used in the test. The second (resp. third and
ontology search engine, for each indexed ontology, stores
fourth) column show the time (in millisecond) needed to
its semantic approximation (in DL-Lite) [15] and accompa-
answer the queries for 1 university (resp. 10 and 50 uni-
nies each ontology in its repository with an f-DL-Lite meta-
versities). In general, the evaluations match nicely with our
ontology, which (i) materialises all TBox reasoning based
expectation: crisp queries are faster than CTQs as the sys-
on the semantic approximation and, most importantly, (ii)
tem needs to take care of more joins due to the thresholds,
uses fuzzy assertions to represent associations of each class
while CTQs are faster than GFCQs as the former ones do
(property) and keywords7 appearing in the metadata of the
not require post-processing to calculate the degrees. Fur-
ontology, with some degrees. Keywords appearing in the on-
thermore, it is encouraging to see that the performance of
tology metadata are associated with scores based on ranking
the fuzzy query engine is in most cases close to the perfor-
factors8. We use these scores to calculate the tf � idf [22] for
mance of the crisp query engine. With the smallest data
set, it is has almost identical performance, particularly on
7As mentioned above, keywords are represented by repre-
the more complex queries. As more data must be evalu-
sentative individuals.
ated, the performance drops slightly. For the largest data
8http://www.seomoz.org/article/search-ranking-factors
each keyword, and normalise them using a sigmoid function
7. REFERENCES
such as the one shown in (3) to a degree between 0 and 1.
[1] F. Baader, D. L. McGuiness, D. Nardi, and
P. Patel-Schneider, editors. Description Logic
2
Handbook: Theory, implementation and applications.
w(n) =
- 1
(3)
1.2-n + 1
Cambridge University Press, 2002.
[2] F. Bobillo, M. Delgado, and J. G磑mez-Romero. A
Hence, the ontology search engine can use the f-DL-Lite
crisp representation for fuzzy SHOIN with fuzzy
query engine to query across all the meta-ontologies in its
nominals and general concept inclusions. In Proc. of
repository, so as to support keyword-plus-entailment searches.
the 2nd International Workshop on Uncertainty
Further discussions of this use case go beyond the scope of
Reasoning for the Semantic Web (URSW 06), Athens,
this paper.
Georgia, 2006.
[3] A. Bookstein. Fuzzy requests: An approach to

6. DISCUSSIONS

weighted boolean searches. Journal of the Americal
How to apply Description Logic based ontologies in the
Society for Information Science, 31:240�7, 1980.
Web has been a pressing issue for the Semantic Web com-
[4] G. Bordogna, P. Bosc, and G Pasi. Fuzzy inclusion in
munity [14]. Web applications require ontology engines to
database and information retrieval query
be able to handle fuzzy and imprecise data in an efficient
interpretation. In Proceedings of the 1996 ACM
and scalable manner, which has been a big challenge for
symposium on Applied Computing, pages 547�1,
existing fuzzy ontology engines. In this paper, we tackle
1996.
this issue by providing efficient and scalable query services
[5] D. Calvanese, G. De Giacomo, D. Lembo,
for lightweight fuzzy ontologies (in f-DL-Lite), based on the
M. Lenzerini, and R. Rosati. DL-Lite: Tractable
the two novel query languages we proposed for fuzzy on-
description logics for ontologies. In Proc. of AAAI
tologies. To the best of our knowledge, this paper is the
2005, 2005.
first to report on implementations and evaluations of scal-
[6] S.J. Chen and S.M. Chen. A new method for fuzzy
able and expressive conjunctive query answering over fuzzy
information retrieval based on geometric-mean
ontologies. Our online use case application shows that the
averaging operators. In Workshop on Artificial
f-DL-Lite query engine can be used to enable keyword-plus-
Intelligence.
entailment searches.
[7] A. Chortaras, G. Stamou, and A. Stafylopatis.
Our proposed query languages are related with weighted
Adaptation of weighted fuzzy programs. In Proc. of
Boolean queries [33, 4, 21] proposed in the field fuzzy infor-
the International Conference on Artificial Neural
mation retrieval [8]. On the one hand, motivated by these
Networks (ICANN 2006), pages 45�. Springer, 2006.
extensions we propose a completely novel query language,
[8] V. Cross. Fuzzy information retrieval. Journal of
that of threshold queries, which is very important since it
Intelligent Information Systems, 3:29�, 1994.
generalises the entailment of fuzzy assertions. On the other
[9] B. C. Grau. Tractable fragments of the OWL 1.1 web
hand, the main strength of the proposed general fuzzy query
ontology language.
language is its openness of the use of semantics generalising
http://www.w3.org/Submission/owl11-tractable/,
most previous approaches, like those based on fuzzy implica-
2006.
tions [4], aggregation functions [21, 6, 32], Straccia's query
language [29] for fuzzy DL-Lite and weighted t-norm queries
[10] Y. Guo, Z. Pan, and J. Heflin. LUBM: A Benchmark
[7]. With the general fuzzy query language, we could pro-
for OWL Knowledge Base Systems. Journal of Web
vide top-k query answering service over f-DL-Lite ontolo-
Semantics, 3(2):158�2, 2005.
gies, similar to that proposed by Straccia [30] for a variant
[11] G. J. Klir and B. Yuan. Fuzzy Sets and Fuzzy Logic:
of DL-Lite ontologies. In short, the openness of the use of
Theory and Applications. Prentice-Hall, 1995.
fuzzy semantics and the generality of the presented algo-
[12] Y. Li, B. Xu, J. Lu, and D. Kang. Discrete tableau
rithms make the fuzzy querying service more adaptable for
algorithms for FSHI. In Proceedings of the
different application needs.
International Workshop on Description Logics (DL
One aspect of our future work is to investigate scalable
2006), Lake District, UK, 2006.
querying services for more expressive fuzzy ontology lan-
[13] T. Mailis, G. Stoilos, and G. Stamou. Proceedings of
guages, such as Fuzzy OWL [26]. Another part of our fu-
the first international conference on web reasoning and
ture work should also consist of a survey on which query
rule systems (RR-07), 2007. In Expressive Reasoning
language/semantics could/should be used in what scenarios
with Horn Rules and Fuzzy Description Logics, 2007.
in Web applications.
[14] P. Mika. Ontologies are us: A unified model of social
networks and semantics. In 4th International Semantic
Acknowledgements
Web Conference (ISWC 2005), 2005.
This research was partially supported by the Nuffield FONTO-
[15] J. Z. Pan and E. Thomas. Approximating OWL-DL
Rule project (NAL/32794), the FP6 Network of Excellence
Ontologies. In Proc. of the 22nd National Conference
EU project Knowledge Web (IST-2004-507842), Integrated
on Artificial Intelligence (AAAI-07), 2007. To appear.
EU project X-Media (IST-2004-026978) and the Advanced
[16] J. Z. Pan, E. Thomas, and D. Sleeman.
Knowledge Technologies (GR/N15764/01). Giorgos Stoilos
ONTOSEARCH2: Searching and Querying Web
was also partially supported by the Greek Secretariat of Re-
Ontologies. In Proc. of WWW/Internet 2006, pages
search and Technology (PENED Ontomedia 03 ED 475).
211�8, 2006.
[17] J.Z. Pan, G. Stoilos, G. Stamou, V. Tzouvaras, and
I. Horrocks. f-SWRL: A fuzzy extension of SWRL.
Journal on Data Semantics, Special Issue on
This appendix contains a detailed presentation of the ab-
Emergent Semantics, 4090:28�, 2006.
stract syntax of fuzzy-DL-Lite. Firstly, we present the ab-
[18] P. F. Patel-Schneider, P. Hayes, and I. Horrocks.
stract syntax of crisp DL-Lite by restricting the elements of
OWL Web Ontology Language Semantics and
the OWL DL syntax. Then, we provide the definition of in-
Abstract Syntax. Technical report, W3C, Feb. 2004.
dividual axioms in fuzzy-DL-Lite which additionally contain
W3C Recommendation.
a membership degree and an inequality type.
[19] E. Prud'hommeaux and A. Seaborne. SPARQL query
Class Axioms
language for RDF, 2006. W3C Working Draft,
http://www.w3.org/TR/rdf-sparql-query/.
axiom
::= `Class(' classID [`Deprecated'] `complete'
[20] T. Radecki. Fuzzy set theoretical approach to
{annotation} { basicClass } `)'
document retrieval. Journal of Information Processing
axiom
::= `Class(' classID [`Deprecated'] `partial'
& Management, 15:235�5, 1979.
{annotation} { generalClass } `)'
[21] G. Salton, E.A. Fox, and H. Wu. Extended boolean
axiom
::= `DisjointClasses(' basicClass basicClass
information retrieval. Journal of Communications of
{ basicClass } `)' |
ACM, 26:1022�36, 1983.
`EquivalentClasses(' basicClass { basicClass } `)' |
[22] G. Salton and M. J. McGill. Introduction to modern
`SubClassOf(' basicClass generalClass ')'
information retrieval. McGraw-Hill, 1983.
basicClass
::= classID | restriction
[23] E. Sanchez. Importance in knowledge systems.
generalClass ::= basicClass | `complementOf(' { basicClass } `)' |
Information Systems, 14(6):455�4, 1989.
`intersectionOf(' { generalClass } `)'
[24] G. Stoilos, N. Simou, G. Stamou, and S. Kollias.
restriction
::= `restriction(' individualvaluedPropertyID
Uncertainty and the semantic web. IEEE Intelligent
`someValuesFrom( owl:Thing )' `)'
Systems, 21(5):84�, 2006.
Property Axioms
[25] G. Stoilos, G. Stamou, J. Z. Pan, V. Tzouvaras, and
I. Horrocks. Reasoning with very expressive fuzzy
axiom ::= `ObjectProperty(' individualvaluedPropertyID
description logics. Journal of Artificial Intelligence
[`Deprecated'] { annotation }
Research, 30(5):273�0, 2007.
[ `inverseOf(' individualvaluedPropertyID `)' ]
[26] G. Stoilos, G. Stamou, V. Tzouvaras, J.Z. Pan, and
[`Functional' | `InverseFunctional' ]
I. Horrocks. Fuzzy OWL: Uncertainty and the
{ `domain(' generalClass `)' } { `range(' generalClass `)' } `)'
semantic web. In Proc. of the International Workshop
on OWL: Experiences and Directions, 2005.
Fuzzy Assertions
[27] U. Straccia. Reasoning within fuzzy description logics.
Journal of Artificial Intelligence Research, 14:137�6,
individual ::= `Individual(' [individualID] {annotation}
2001.
{`type'( type `)' [ineqType] [degree]}
[28] U. Straccia. Description logics with fuzzy concrete
{value [ineqType] [degree] } `)'
domains. In 21st Conf. on Uncertainty in Artificial
ineqType ::= `>='
Intelligence (UAI-05), Edinburgh, 2005.
degree
::= real-number-between-0-and-1-inclusive
[29] U. Straccia. Answering vague queries in fuzzy
value
::= `value(' individualvaluedPropertyID individualID ')' |
DL-Lite. In Proceedings of the 11th International
`value(' individualvaluedPropertyID individual ')'
Conference on Information Processing and
type
::= description
Management of Uncertainty in Knowledge-Based
Systems, (IPMU-06), pages 2238�45, 2006.
[30] 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 Intelligence (JELIA-06), 2006.
[31] E. Thomas, J. Z. Pan, and D. Sleeman.
ONTOSEARCH2: Searching Ontologies Semantically.
In Proc. of OWL Experience Workshop, 2007.
[32] P. Vojt碼s. Fuzzy logic programming. Fuzzy Sets and
Systems, 124:361�0, 2001.
[33] W.G. Waller and D.H. Kraft. A mathematical model
of a weighted boolean retrieval system. Journal of
Information Processing & Management, 15:247�0,
1979.
[34] R.R Yager. A note on weighted queries in information
retrieval systems. Journal of the Americal Society for
Information Science, 38:23�, 1987.
APPENDIX
A. ABSTRACT SYNTAX OF F-DL-LITE