The great evolution of ontologies during the last decade, bred the need for storage and querying for the Semantic Web. For that purpose, many RDF tools capable of storing a knowledge base, and also performing queries on it, were constructed. Recently, fuzzy extensions to description logics have gained considerable attention especially for the purposes of handling vague information in many applications. In this paper we investigate on the issue of using classical RDF storing systems in order to provide persistent storing and querying over large-scale fuzzy information. To accomplish this we first propose a novel way for serializing fuzzy information into RDF triples thus classical storing systems can be used without any extensions. Additionally, we extend the existing query languages of RDF stores in order to support expressive fuzzy queries proposed in the literature. These extensions are implemented through the FiRE fuzzy reasoning engine, which is a fuzzy DL reasoner for fuzzy-SHIN . Finally, the proposed architecture is evaluated using an industrial application scenario about casting for TV commercials and spots.
Ontologies, through the OWL language [
Fuzzy ontologies are envisioned to be very useful in the Semantic Web. Similar to crisp ontologies, they can serve as basic semantic infrastructure, providing shared understanding of certain domains across different applications. Furthermore, the need for handling fuzzy and uncertain information is crucial to the Web. This is because information and data along the Web may often be uncertain or imperfect.
Therefore sophisticated uncertainty representation and reasoning are
necessary for the alignment and integration of Web data from different sources. This
requirement for uncertainty representation has led W3C to set up the
Uncertainty Reasoning for the World Wide Web XG1. Recently, fuzzy DL reasoners
such as fuzzyDL2 and FiRE3 that can handle imprecise information have been
implemented. Despite these implementations of expressive fuzzy DLs there is still
no other work on persistent storage and querying, besides the work of Straccia
[
The main contributions of this paper are the following: 1. It presents a novel framework for persistent storage and querying of expressive fuzzy knowledge bases, 2. It presents the first ever integration of fuzzy DL reasoners with RDF triple stores, and 3. It provides experimental evaluation of the proposed architecture using a real-world industrial strength use-case scenario.
The rest of the paper is organized as follows. Firstly, in section 2 a short
theoretical description of the fuzzy DL f-SHIN [
The Fuzzy DL fKD-SHIN
In this section we briefly present the notation of DL f-SHIN which is a fuzzy
extension of DL SHIN [
In contrast to crisp DLs, the semantics of fuzzy DLs are provided by a fuzzy
interpretation [
By using fuzzy set theoretic operations the fuzzy interpretation function can
be extended to give semantics to complex concepts, roles and axioms [
A f-SHIN knowledge base Σ is a triple (T , R, A), where T is a fuzzy T Box, R is a fuzzy RBox and A is a fuzzy ABox. T Box is a finite set of fuzzy concept axioms which are of the form C - D called fuzzy concept inclusion axioms and C ≡ D called fuzzy concept equivalence axioms, where C, D are concepts, saying that C is a sub-concept or C is equivalent of D, respectively. Similarly, RBox is a finite set of fuzzy role axioms of the form Trans(R) called fuzzy transitive role axioms and R - S called fuzzy role inclusion axioms saying that R is transitive and R is a sub-role of S respectively. Finally, ABox is a finite set of fuzzy assertions of the form (a : C#$n), ((a, b) : R#$n), where #$ stands for ≥, >, ≤ or <, or a / =. b, for a, b ∈ I. Intuitively, a fuzzy assertion of the form (a : C ≥ n) means that the membership degree of a to the concept C is at least equal to n. 3 3.1
In order to use the existing RDF storing systems to store fuzzy knowledge
without enforcing any extensions we have to provide a way of serializing fuzzy
knowledge into RDF triples. Some work has already been done in this issue. In [
Our syntax becomes obvious in the following example. Suppose that we want to represent the assertion ((paul : T all) ≥ n). The RDF triples representing this information are the following: paul :paulmembTall :paulmembTall :paulmembTall frdf:membership rdf:type frdf:degree frdf:ineqType :paulmembTall .
Tall . “n^^xsd:float” . “=” . where :paulmembPaul is a blank node used to represent the fuzzy assertion of paul with the concept Tall.
On the other hand, mapping fuzzy role assertions is more tricky since RDF does not allow the use of blank nodes in the predicate position. Thus, we have to use new properties for each assertion. Thus, the assertion ((paul, f rank) : F riendOf ≥ n) is mapped to paul frdf:paulFriendOffrank frdf:paulFriendOffrank frdf:paulFriendOffrank frdf:paulFriendOffrank rdf:type frdf:degree frdf:ineqType frank .
FriendOf . “n^^xsd:float” . “=” . 3.2
One of the main advantages of persistent storage systems, like relational databases
and RDF storing systems, is their ability to support conjunctive queries.
Conjunctive queries generalize the classical inference problem of realization of
Description Logics [
q(X) ← ∃Y .conj(X, Y ) or simply q(X) ← conj(X, Y ), where q(X) is called the head, conj(X, Y ) is called the body, 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 respectively concept and role names, v, v1 and v2 are individual variables in X and Y or individuals from the ontology.
Since in our case we extend classical assertions to fuzzy assertions, new
methods of querying such fuzzy information are possible. More precisely, in [
n
q(X) ← ∃Y. !(atomi(X, Y ) ≥ ki),
i=1
(1)
(2)
where ki ∈ [
n
q(X) ← ∃Y. ! (atomi(X, Y ) : ki),
i=1
(3)
where atomi(X, Y ) and ki are as above. As it is shown in [
sup S!∈ΔI×...×ΔI
{tin=1 J (ki, atomiI (v¯)[X"→S,Y "→S!])}.
Similarly we can use fuzzy aggregation functions [
FiRE is a JAVA implementation of a fuzzy reasoning engine for imperfect
knowledge currently supporting f-SHIN . It can be found at http://www.image.ece.
ntua.gr/~nsimou/FiRE/ together with installation instructions and examples.
Its syntax is based the Knowledge Representation System Specification [
Crisp DL reasoners offer reasoning services such as deciding satisfiability, subsumption and entailment of concepts and axioms w.r.t. an ontology. In other words, these tools are capable of answering queries like “Can the concept C have any instances in models of the ontology T ?” (satisfiability of C), “Is the concept D more general than the concept C in models of the ontology T ?” (subsumption C - D) or does axiom Ψ logically follows from the ontology (entailment of Ψ ). 4 http://www.openrdf.org/
These reasoning services are also available by f-SHIN together with greatest
lower bound queries which are specific to fuzzy assertions. FiRE uses the tableau
algorithm of f-SHIN , presented by Stoilos et al [
Finally, FiRE allows the user to make greatest lower bound queries (GLB).
GLB queries are evaluated by FiRE performing entailment queries of the
individual participating in concept of interest for all the degrees contained in the
ABox, using the binary search algorithm in order to reduce the degrees search
space [
FiRE was enhanced by the functionalities of the RDF-Store Sesame (Sesame 2 beta 6). The RDF Store is used as a back-end for storing and querying RDF triples in a sufficient and convenient way. In this architecture the reasoner is the front-end which the user can use in order to store and query a fuzzy knowledge base. Additionally, a user is able to access data from a repository, apply any of the available reasoning services on this data and then store the implicit knowledge extracted from them back in the repository.
Another important benefit from this integration is the use of the query
language SPARQL [
^ has-hairLength(x,y) : 1 ^ Long(y) : 0.8
In case of CTQs, a query is firstly converted from the FiRE conjunctive query syntax to SPARQL query language. Based on the fuzzy OWL syntax in triples that we have defined in section 3.1 the query of Example 1 is as follows in SPARQL. The query results are evaluated by Sesame engine and visualized by FiRE.
SELECT ?x WHERE { ?x ns5:membership ?Node1 . ?Node1 rdf:type ?Concept1 . ?Node1 ns5:ineqType ?IneqType1 . ?Node1 ns5:degree ?Degree1 .
FILTER regex (?Concept1 , "CONCEPTS#Tall") FILTER regex (?IneqType1 ,">") FILTER (?Degree1 >= "0.8^^xsd:float") ?BlankRole2 ns5:ineqType ?IneqType2 . ?BlankRole2 ns5:degree ?Degree2 . ?BlankRole2 rdf:type ?Role2 . ?x BlankRole2 ?y .
FILTER regex (?Role2 , "ROLES#has-friend") FILTER regex (?IneqType1 ,">") FILTER (?Degree2 >= "1.0^^xsd:float") ...
}
In case of general fuzzy conjuctive queries the operation is different. The SPARQL query is constructed in a way that retrieves the participation degrees of every Role or Concept used in the atoms criterions, for the results that satisfy all of the atoms. The participation degrees retrieved for each query atom are then used together with the degree associated weight by FiRE for the ranking procedure of the results according to the selected semantics.
It is worth mentioning that the proposed architecture obviously does not
provide a complete query answering system for f-SHIN since queries are issued
against the stored assertions of the RDF repository. Hence queries that include,
for example, transitive or inverse roles are not correctly evaluated. On the one
hand, query answering for fuzzy-DLs is still an open problem even for
inexpressive fuzzy-DLs while on the other hand, even for classical DLs it is known
that the algorithms are highly complex [
In this section we present the use case of human models utilized for the evaluation of our proposal. The data were taken from a production company database containing 2140 human models. The database contained information on each model regarding their height, age, body type, fitness type, tooth condition, eyecondition and color, hair quality, style, color and length, ending with the hands’ condition. Apart from the above, there were some additional, special-appearance characteristics for certain models such as good-looking, sexy, smile, sporty, etc. introduced by the casting producer. Finally for a minority of models, a castingvideo was stored in the database. The main objective of the production company was to pick a model, based on the above features, who would be suitable for a certain commercial spot. Furthermore, depending on the spot type, inquiries about models with some profession-like characteristics (like teacher, chef, mafia etc.) were also of interest.
Despite the fact that the database information on each model was rich enough, there was great difficulty in querying models of appropriate characteristics. The main reason for that was that the database information was not semantically organized. The various tables of a database made the searching for combined characteristics antiliturgical. Additionally, retrieval of models based on threshold criteria for their age or height was most of the times inaccurate since this kind of information is clearly fuzzy. Hence, selection was restricted among models that had videotaped castings or those that had worked with the producers in previous spots, thus not taking advantage of their database information.
In order to eliminate these limitations we have implemented a fuzzy knowledge base using f-SHIN . For the generation of the fuzzy ABox the characteristics given by numerical values being the height and age, were fuzzified defining new concepts, while the remaining characteristics were used as crisp assertions. Therefore, the fuzzification process of age was made by setting fuzzy partitions depending on age by defining the concepts Kid, Teen, Baby, 20s, 30s, 40s, 50s, 60s and Old. Hence, as can be observed from the age fuzzification graph, a model who is 29 years old participates in both concepts 20s and 30s with degrees 0.35 and 0.65 respectively. Similarly for the fuzzification process of height, the concepts Very Short, Short, Normal Height, Tall and Very Tall were defined. In the case of the height characteristic, the fuzzy partition used for female models was different from the one used for males, since the average height of females is lower than that of males. The fuzzification graphs of age and men’s height are shown in Figure 1. An example of the produced assertions is shown in Example 3. Example 3. An excerpt of ABox for the model michalis1539 is (michalis1539 : 20s ≥ 0.66), (michalis1539 : 30s ≥ 0.33) (michalis1539 : N ormal Height ≥ 0.5) (michalis1539 : T all ≥ 0.5), (michalis1539 : GoodLooking ≥ 1) ((michalis1539, good) : has − toothCondition ≥ 1), (good : Good ≥ 1) In order to permit knowledge-based retrieval of human models we have implemented an expressive terminology for a fuzzy knowledge base. The alphabet of concepts used for the fuzzy knowledge base consists of the features described above while some characteristics like hair length, hair condition etc. were represented by the use of roles.
The effective extraction of implicit knowledge from the explicit one requires an expressive terminology capable of defining higher concepts. In our case the higher domain concepts defined for human models lie into five categories: age, height, family, some special categories and the professions. Hence, the profession Scientist has been defined as male, between their 50s or 60s, with classic appearance who also wears glasses. In a similar way we have defined 33 domain concepts; an excerpt of the T Box can be found in Table 1.
At this point we must mention the fact that the proposed fuzzy knowledge base does not fully utilize the expressivity of f-SHIN . This restriction is due to the application domain (i.e transitive and inverse roles or number restrictions are not applicable in this domain), but nevertheless it is more expressive that an fuzzy DL-Lite ontology. All the experiments were conducted under Windows XP on a Pentium 2.40 GHz computer with 2. GB of RAM.
The described fuzzy knowledge base was used in the evaluation of our approach. Implicit knowledge was extracted using the greatest lower bound service of FiRE, asking for the degree of participation of all individuals, in all the defined domain concepts. The average number of assertions per individual was 13 while the defined concepts were 33, that together with the 2140 individuals (i.e entries of the database) resulted to 29460 explicit assertions and the extraction of 2430 implicit. These results, together with concept and role axioms, were stored to a Sesame repository using the proposed fuzzy OWL triples syntax to form a repository of 529.926 triples.
The average time for the GLB reasoning process and the conversion of explicit and implicit knowledge to fuzzy OWL syntax in triples was 1112 milliseconds. The time required for uploading the knowledge to a Sesame repository depends on the type of repository (Memory or Native) and also on repository’s size. Based on our experiments, we have observed that the upload time is polynomial to the size of the repository but without significant differences. Therefore, the average minimum upload time to an almost empty repository (0-10.000 triples) is 213 milliseconds while the average maximum upload time to a full repository (over 500.000 triples) is 700 milliseconds.
FiRE and Sesame were also examined in the use of expressive fuzzy queries. The performance in this case mainly depended on the complexity of the query but also on the type and size of the repository. Queries using role names in combination with large repositories can dramatically slow down the response. Table 2 illustrates the response times in milliseconds using both types of repositories and different repository sizes. Repository sizes was set by adjusting the number of assertions. As it can be observed, very expressive queries seeking for young female models with beautiful legs and eyes as well as long hair, a popular demand in commercial spots, can be easily performed. It is worth mentioning that these queries consist of higher domain concepts defined in our fuzzy knowledge base.
Since our system is not a sound and complete query answering system for f-SHIN , the GLB service performed before uploading the triples is employed in order to use as much of the expressivity of the language as possible producing new implied assertions.
Furthermore, the results regarding query answering time are also very encouraging, at least for the specific application. Although, compared to crisp querying, over crisp knowledge bases, our method might require several more seconds to be answered (mainly due to post processing steps for GFCQs or due to very lengthy SPARQL queries for CTQs) this time is significantly less, compared to T = {MiddleAged ≡ 40s " 50s,
TallChild ≡ Child # (Short " Normal Height),
Father ≡ Male # (30s " MiddleAged),
Legs ≡ Female # (Normal Height " Tall)
#(Normal " Perfect) # (Fit " PerfectFitness), Teacher ≡ (30s " MiddleAged) # Elegant # Classic, Scientist ≡ Male # Classic # (50s " 60s)
#Serious # ∃has − eyeCondition.Glasses } Table 1. An excerpt of the Knowledge Base (T Box). the time spent by producers on casting (usually counted in days), since they usually have to browse through a very large number of videos and images before they decide. 6
Due to the fact that imperfect information is spread along the web, the effective management of imperfect knowledge is very important for the substantial evolution of the Semantic Web. In this paper, we have proposed an architecture that can be used for storing and querying fuzzy knowledge bases for the semantic web. Our proposal which is based on DL f-SHIN , consists of the RDF triples syntax accommodating the fuzzy element, the fuzzy reasoning engine FiRE and its integration with RDF Store Sesame which permits very expressive fuzzy queries.
The proposed architecture was evaluated using an industrial application scenario about casting for TV commercials and spots. The obtained results are very promising from the querying perspective. From the initial 29460 explicit assertions made by database instances for models, 2430 new implicit assertions where extracted and both uploaded in the Sesame repository. In this way expressive semantic queries like “Find me young female models with beautiful legs and eyes as well as long hair”, that might have proved very difficult or even impossible using the producing company’s database, are applicable through FiRE. This reveals both the strength of knowledge-based applications, and technologies for managing fuzzy knowledge, since a wealth of the information of the databases, like age, height, as well as many high level concepts of the specific application, like “beautiful eyes”, “perfect fitness” and “scientist look” are inherently fuzzy.
As far as future directions are concerned, we intend to further investigate on different ways of performing queries using expressive fuzzy description logics. Finally, it would be of great interest to attempt a comparison between the proposed architecture and approaches using fuzzy DL-lite ontologies and approximation.
Query x ← Scientist(x) x ← Father(x) ≥ 1 ∧ Teacher(x) ≥ 0.8 ∧Normal Height(x) ≥ 0.5.
x ← Scientist(x) : 0.8 x ← Father(x) : 0.6 ∧ Teacher(x) : 0.7 ∧Normal Height(x) : 0.8.
Native Memory 100.000 250.000 500.000 100.000 250.000 500.000 1042 2461 3335 894 2364 3332
This work is supported by the FP6 Network of Excellence EU project X-Media (FP6026978) and K-space (IST-2005-027026).