With an increased interest in machine processable data, more and more data is now published in RDF (Resource Description Framework) format. This RDF data is present in independent and distributed resources which needs to be centralized, navigated and searched for domain specific applications. This paper proposes a new approach based on Formal Concept Analysis (FCA) to create a navigation space over semantic web data. This approach uses an extension of FCA and takes RDF triples and RDF Schema present on several independent sources and provide centralized access over the data resulting from several resources. Afterwards, SPARQL queries can be posed over this navigation space to access these distributed resources from one platform for information retrieval purposes.
With the efforts of Semantic Web community many technologies have been
offered for publishing machine-readable data on web. It annotates textual data
with meta-data and makes it available in the form of ontologies and RDF graphs.
One of the emerging source of such data are published in the form of Linked Open
Data (LOD) cloud [
This structured format leads to other kind of challenges. One of the
basic characteristics of Semantic Web is that it follows a decentralized
publication model, meaning that the RDF graphs are published in several distributed
resources, instead of creating one knowledge-base of statements any one can
contribute new statements and make it publicly available. These resources have
nothing in common except some shared terms. These decentralized graphs should
be integrated through machine/software agents to provide domain specific
applications. Moreover, external schemas in the form of ontologies or taxonomies
can be linked to these data to make sense based on real world conception. Some
of the resources may only consist of ontological information and may not
contain the instantial information such as SWRC ontology [
The current paper introduces a new framework based on Formal Concept
Analysis [
The paper is structured as follows: section 2 gives the motivating example, section 3 introduces the basic notion of Pattern Structures with an example. Section 4 details the framework of semantic pattern structures for creating schema rich navigation space over RDF data. Section 5 defines the querying mechanism over the obtained navigation space. Section 6 describes the experimental results of the framework. Section 7 discusses the related work while Section 8 concludes the paper. 2
For instance, if a patient has been prescribed some Cardiovascular Agent (CVA) and after a while he is looking for a replacement for his drug because it causes some allergic condition as a side effect. For finding solution, the doctor should be able to access this information for obtaining the suggestions for replacing patient’s drug which is used for the same purpose but does not cause the side effect reported by the patient. All the required information is present in different data sources: – Drugbank1 contains information about drugs with their categories and the proteins it targets. – SIDER2 contains drug with their specific side effects. – The category of drugs CVA exists in MeSH 3.
– Allergic conditions which is a class of side effects exists in MedDRA4. The information required by the domain expert cannot be obtained by posing a simple query on Google. SPARQL queries over each resource should be written to obtain this answer, which further needs manual work to obtain the required suggestions as the answers are in the form of list. In order to access such kind of information, all the data sets must be accessed simultaneously and there should be a single information space for accessing all the desired information through navigation and simple SPARQL queries.
In the current study, we propose a generic framework that provides one space for accessing several data sources related to some domain. The framework proposed in this study is generic because it can be applied to any domain having related information scattered over several resources. Based on the requirements of the user and the applications, the navigation space can be defined on a limited number of factual RDF triples. For example, in case of a cardiologist, he will only be interested in Cardiovascular Agents or some related categories of drugs. This way the application will include the drugs which are Cardiovascular Agents and its related categories. Only a subset of datasets should be considered according to the requirements of the applications. These specification are described by the domain expert as a starting point for narrowing down the huge cloud of Linked Data present on-line. 3 3.1
Recently, Linked Open Data (LOD) [
Practically, we consider RDF data w.r.t. three levels according to the value of predicate.
– An RDF triple is at the schema level when the predicate has a reserved value from RDFS vocabulary such as rdfs:subClassOf, rdfs:Class (represented as sc and Class respectively in the rest of the paper). The keyword rdfs:Class is used to declare that a set of resources is constituting a class and rdfs:subClassOf states that all the instances of one class are the instances of another class. For example, in Table 2, the schema level is given by triples t6, t8. An example of the tree structure contained in an RDF schema (in the rest of the paper when we use RDF Schema/schema we mean the tree structure created by rdfs:subClassOf) related to the drug side effect and their categories is shown in Figures 1 and 2 respectively. – An RDF triple is at the type level if it keeps the mappings from an instance to its class and states that a resource is an instance of a class. The RDF triple is at this level when the predicate has a reserved value from RDF vocabulary such as rdf:type (represented as type in the rest of the paper).
For example, in Table 2, the type level is given by triples t4, t5, t7. – An RDF triple is at factual level when the predicate is related to the domain knowledge and is not a keyword from RDF vocabulary. For example, in Table 2, the factual level is given by t1, t2, t3.
Table 2 keeps RDF triples from several resources. The information about the
side effect of the drugs shown in triples t1, t2 is present on SIDER7 database
which keeps the side effects of the drugs contained on the packaging of the drug.
The information about the categories of the drugs shown in triples t3 is present
on DrugBank8, which keeps detailed information about each of the drugs and
the proteins it targets. The schema level information about the drug side effects
shown in t5, t6 are present in The Medical Dictionary for Regulatory Activities
6 http://www.w3.org/TR/rdf-schema/
7 http://sideeffects.embl.de/
8 http://www.drugbank.ca/
(MedDRA) Terminology9 which is the international medical terminology. Finally
the schema level information related to the drug category shown in triples t7, t8
is present in MeSH (Medical Subject Headings)10 is a controlled vocabulary
thesaurus which along with other tree structures keeps classification of drug
categories.
A standard query language for accessing RDF graphs is SPARQL11 which mainly
focuses on graph matching. A SPARQL query is composed of two parts the head
and the body. The body of the query contains the Basic Graph Patterns (it is
contained in the WHERE clause of the query). It is composed of complex graph
patterns that may include RDF triples with variables, conjunctions,
disjunctions and constraints over the values of the variables. These graph patterns are
matched against the RDF graph and the matched graph is retrieved and
manipulated according to the conditions given in the query. The head of the query is an
expression which indicates how the answers of the query should be constructed.
For instance, consider a simple SPARQL query SELECT ?x ?y WHERE { ?x p1
?y}, then the basic graph pattern ?x p1 ?y will be matched against the triples
containing p1 as predicate i.e., t1 and t2 (see Table 2). Thus the answer of the
query will be (s1, o1), (s1, C2).
9 http://www.meddra.org/
10 http://www.ncbi.nlm.nih.gov/mesh
11 http://www.w3.org/TR/rdf-sparql-query/
Formal Concept Analysis [
A pattern structure is a triple pG, pD, [q, δq, where G is the set of entities12, pD, [q is a meet-semilattice of descriptions D and δ : G Ñ D maps an entity to a description. More intuitively, a pattern structure is the set of objects with their descriptions with a similarity operation [ on them which represents the similarity of objects. This similarity measure is idempotent, commutative and associative. If pG, pD, [q, δq is the pattern structure then the derivation operators can be defined as:
A : ¦ δpgq gPA d : tg P G|d δpgqu f or A G f or d P D Now the pattern concept can be defined as follows: Definition 1 (Pattern Concept). A pattern concept of a pattern structure “G, pD, [q, δ” is a pair pA, dq where A G and d P D such that A d and A d , where A is called the concept extent and d is called the concept intent.
Finally, the obtained concept lattice is called as pattern concept lattice, which keeps partially ordered relations between the pattern concepts. 4
The decentralization issue is raised when many entities are contributing statements and making it publicly available. Either they are publishing same data using different vocabularies or related data which is distributed over several resources. To provide centralized access over distributed resources this section discusses a framework called Semantic Pattern Structures. This new framework is called Semantic Pattern Structures (SPS) because it is based on Pattern Structures and it deals with data in the form of triples and it classifies these triples with respect to RDF Schema present in the form of taxonomy. This way the final navigation space also keeps the semantic information i.e., background knowledge. The idea underlying the SPS is to create a concept lattice directly from an RDF graph and use the associated RDF Schema present on Linked Open Data to 12 We rename an object in Pattern Structures as an entity to avoid confusion with the object in an RDF triple. be accessed within one concept lattice. This concept lattice provides search and navigation capabilities over RDF data as well as over the RDF Schema to answer certain queries of the domain expert. The obtained lattice does not only provides access to several data sources but is also a materialization of the associated RDF Schema.
For creating one navigation space over RDF as well as RDF Schema, the first task is to define RDF triples in terms of patterns structures i.e., specifying the entities, their descriptions and the mapping from entities to description. The second task is to select a suitable RDF Schema associated to these RDF triples from distributed data sources based on domain knowledge. After these two preprocessing steps, we define a similarity measure [ over two descriptions which we generalize to the set of descriptions. After defining the similarity measure, we explain how a semantic pattern concept lattice is built using this similarity measure. Finally, we interpret, provide navigation and querying capabilities over the obtained pattern concept lattice. 4.1
Firstly, we represent factual RDF triples about certain domain as entities and their descriptions. According to section 3.3, pattern structures are given as pG, pD, [q, δq. The descriptions D are termed as semantic descriptions and are denoted as Ds. An RDF triple store containing factual level information consists of statements of the form xsi, pj , oky, where i t1, . . . , nu, j t1, . . . , qu, k t1, . . . , mu. Then, the set of subjects si are mapped to the entities in G. As the set of entities G represent the subjects in triples, we represent it as S.
Regarding the type of each object set which is the range of same predicate a suitable RDF Schema is obtained by locating the terms in the closely related RDF Schema. This selection is done based on domain knowledge. RDF Schema contains many constructs such as property, sub-property etc. along with sc and information but in this work we use the RDF Schema predicates such as type and sc introduced in section 3.1. First, the mapping from object to its type is obtained such as xok, type, C1y i.e., ok is an instance of class C1. Each object is then replaced by its corresponding class i.e., ok is replace by C1. Now, the considered taxonomy information used for defining the similarity measured is present in the RDF Schema by following the predicates such as rdf s : subClassOf, skos : broader e.g., xC1, sc, C6y, i.e., C1 is subclass of C6. Note that we do not extract the trees, we follows this predicate while defining the similarity in the next section.
For instance, to obtain generic drug categories such as cardiovascular agents or generic side effects such as allergic conditions we further add the class information related to each of the objects in the triples. For example, (ok,type,C2) meaning that ok is an instance of class C2. Afterwards, we select all the super classes of the current class in the RDF Schema. For example, for C2, we have C7, C11 and C13. An RDF Schema for drug side effect and drug category is shown in Figure 1 and Figure 2 respectively.
C13 C6 C1
C11
C7 C2
C12
C10 C8 C3
C9 C4
C5
D6 D4 D1
D9 D8
D7
D5 D2
D3 Fig. 1: RDF Schema for Side Effects (MedDRA) Fig. 2: RDF Schema for Drug Category (MeSH) pT1q. pT2q.
The pair ppj : Ckq gives a description dij P Ds. The mapping of entities to description δ : S Ñ Ds is given as follows: let si P S then δpsiq tdi1, . . . , diqu where i P t1, . . . , nu and dij tpj : tC1, C4, . . . , Cmuu where j P t1, . . . , qu. Finally, the semantic pattern structures are given as pS, pDs, [q, δq. Consider the running scenario described before. As the drugs in the DrugBank and SIDER are same and are the subjects then the triples t1, t2, t3 in Table 2 are represented as pS, pDs, [q, δq where the entity S has the description δps1q = {(p1 : tC1, C2, C3u), (p2 : tD2u) }. The descriptions are based on same subjects having different descriptions belonging to different resources i.e., side effect and category. Finally, with respect to the triples in Table 2, the subjects in the RDF triples are mapped to the entities, S {s1, s2, . . . }, the descriptions are given as Ds = {(p1 : tC1, C2, C3, . . . }) , (p2 : tD1, D2, . . . u)}.
Entities S Descriptions Ds {(p1 : tC1, C2, C3u), (p2 : tD2u)} {(p1 : tC1, C4, C5u), (p2 : tD3u)} {(p1 : tC2u), (p2 : tD3u)} {(p1 : tC3, C4, C5u), (p2 : tD8u)} {(p1 : tC1, C3u), (p2 : tD2u)}
Similarity Operation ([) over Descriptions
For defining the similarity operation over the semantic description Ds, we use
the notion of least common subsumer (lcs). Here we re-write the definition of a
least common subsumer of two classes in a RDF Schema T given in [
pS, ¤q, a least common subsumer E of two classes C and D (lcs(C,D) for short) in a partially ordered set is a class such that C E and D E and E is least i.e., if there is a class E1 such that C E1 and D E1 then E E1. Example 1. Let us consider C3 and C5. Then according to the RDF Schema in Figure 1, the common subsumers of C3 and C5 are C10, C12, C13 and lcspC3, C5q C10.
ity over set of descriptions, LCS is computed pairwise for classes in two different sets of description and then only the most specific classes are picked.
Let s1 and s2 be two entities such that s1, s2 P S and the mapping δ is given as follows δps1q d1 tp1 : tC1, C2, C3uu and δps2q d2 tp1 : tC1, C4, C5uu. The similarity is always computed w.r.t the same predicate, here p1. A dual similarity measure is defined to ensure classification of triples with respect to objects as well as with respect to classes from RDF Schema. The similarity measure is computed based on the taxonomy given in Figure 1. According to the current approach a pairwise similarity measure is computed between the two sets of classes connected through some predicate. For example, δps1q [ δps2q xp1 : tC1, C2, C3uy [ xp1 : tC1, C4, C5uy. Meaning that δps1q [ δps2q p1 : xlcspC1, C1q, lcspC1, C5q, . . . y. Then, δps1q [ δps2q p1 : tC1, C10, C11, C13u. As we have C1 ¤ C11 ¤ C13 and C10 ¤ C13 then we pick only the specific classes i.e., C1 and C10. Finally, δps1q [ δps2q p1 : tC1, C10u.
Now let us consider the complete descriptions of the two entities i.e., δps1q {(p1 : tC1, C2, C3u), (p2 : tD2u)} and δps2q {(p1 : tC1, C4, C5u), (p2 : tD3u)}. Then, δps1q [ δps2q {(p1 : tC1, C2, C3u), (p2 : tD2u)} [ {(p1 : tC1, C4, C5u), (p2 : tD3u)}. The set of least common subsumers for p1 will be C1, C10. The least common subumer between p2 : tD3u and p2 : tD2u is p2 : tD5u. Finally, the similarity between these two drugs will be {(p1 : tC1, C10u), (p2 : tD5u)}.
The proposed similarity measure fulfills the property of a similarity operator
i.e., commutative, associative and idempotent [
For building the semantic pattern concept lattice using the above similarity measure over several RDF Schemas, according to the running example, δps1q [ δps2q tpp1 : tC1, C10uq, pp2 : tD5uqu. The semantic pattern concept lattice is built according to definition 1. For instance, ts1, s2ul tpp1 : tC1, C10uq, pp2 : tD5uqu but tpp1 : tC1, C10uq, pp2 : tD5uqu l ts1, s2, s5u. This way we obtain K#2 (see Figure 3) with 3 drugs giving the concept a support of 3. Finally, the pattern concept lattice is built for Table 3 with respect to T1(Figure 1) and T2(Figure 2). This pattern concept lattice is shown in Figure 3 and the details of each of the pattern concept is shown in Table 4.
K#5
K#4
K#6 K#7
K#3
K#8 K#2 K#0
K#9 K#10 K#13 K#1
K#11
K#12
This pattern concept lattice not only serves as a navigation space but also provides clustering of RDF triples w.r.t. some Schema. Each of the pattern concepts is a cluster of triples. For instance, consider the simplest example in Table 4 i.e., K#1, where there is only one entity in the extent, then this cluster contains the triples tps1, p1, C1q, ps1, p2, D2q, . . . u. Here it can be seen that all the classes are connected to single subject S through two predicates. This space can further be navigated to provide the required information to the user without the technical background of Semantic Web. Let us consider, if user is looking for drugs causing side effect C10, the located pattern concept will be K#9 which contains all the drugs causing some allergic conditions. Afterwards, if the user is looking for some very specific allergic condition such as C3 then he can simply navigate downwards to obtain more specific concept i.e., K#10 which contains all the drugs which cause the side effect C3. Let us consider the scenario described in section 2, here the user will be looking for cardiovascular agents (D5) which do not cause any allergic conditions. In this case first the concept containing all the cardiovascular agents are located i.e., K#4 afterwards the lattice is further navigated downwards to obtain the drugs causing C10 (allergic conditions) i.e., K#2. Now the drugs which are in K#4 and not in K#2 are the CVAs which do not cause allergic conditions. 5
For the user with the basic knowledge of SPARQL queries, this navigation space can be easily accessed by posing simpler queries. This sub-lattice gives additional information related to the query (detailed below). The obtained pattern concept lattice keeps the materialized RDF Schema meaning that it does not require the query to perform reasoning. It also allows for accessing several resources from one platform. This navigation space allows queries which are subject, predicate or object bound. In this section we describe simple as well as complex SPARQL queries that can be posed over the this navigation space. Simple queries refer to the queries with simple Basic Graph Patterns such a single triple pattern in the WHERE clause of the SPARQL query, on the other hand, complex queries allow joins and negations. 5.1
Simple queries include subject, predicate or object bound queries. Subject-bound queries refer to the queries where the value of the subject in an RDF triple xs, p, oy is known while the values of predicate, object and classes of objects are to be retrieved. Let a SPARQL query be SELECT ?p ?o WHERE {si ?p ?o}, where si is a known subject and a pattern concept be pA, dq such that si P A. The BGP in this query is (si ?p ?o), this BGP is matched against the RDF graph present in the pattern concept lattice. The answer of the query will be the object concept tsiul tdiu where di P d where d is the intent of the concept pA, dq. Note that this object concept is already computed while building a pattern concept lattice. In other words, all the predicate-object pairs tdiu connected to the subject si in the RDF graph G are returned as a result. For example, if user wants to know complete information about the drug s1 i.e., its side effect and the category, then SELECT ?p ?o WHERE {s1 ?p ?o}. It will search for object concept in the pattern concept lattice given in Figure 3. For instance, s1l pp1 : tC1, C2, C3u, p2 : tD2uq (K#1) and the answer would be pp1 : tC1, C2, C3u, p2 : tD2uq. The first part of the answer pp1 : tC1, C2, C3u belongs to SIDER while p2 : tD2u belongs to DrugBank. However, because of the strong lattice-structure a sub-lattice is retrieved by navigating to more general concepts (upward navigation) present in the pattern concept lattice i.e., all the concepts connected to K#1 i.e., K#2, K#4, K#5, K#9, K#10, K#13, K#8. Here, K#1 is the focus concept because it keeps the exact answer to the posed SPARQL query and the rest of the concepts contain additional information. This way the user not only gets the desired answer but also some additional information about the drug i.e., the classification of side effects from MedDRA and the features it shares with other drugs and with which drugs it shares certain features. Object-bound queries are answered in the same way as described above by retrieving the attribute concept and the linked concepts. However, in this case the additional information will be retrieved by navigating downwards from the focus concept because it is the object-bound query and objects are contained in the intent of the pattern concepts. 5.2
Now let us consider a slightly more complex query which includes a join and a class resources to be retrieved. If it is specified that the drugs to be retrieved should be Cardiovascular Agent causing some Allergic Condition. Then the SPARQL query with subject-subject join will be as follows:
?drug p2 D5. ?drug p1 C10 }
For obtaining the answer, the BGP in the above query is matched against the concept which contains both the predicates p1 and p2, along with this predicate it keeps the classes of objects CardiovascularAgents (D5) connected to predicate p2 as well as AllergicConditions (C10) connected to the predicate p1. The answer will be ts1, s2, s5u i.e., K#2, which will be the focus concept. However, to obtain more specific information regarding these classes of drug categories and the side effects will be returned by navigating downwards in the concept lattice. Finally, a sub-lattice containing K#2, K#3, K#13, K#1 is returned as an answer to the above query. In this case, the user will have an additional information regarding more specific categories related to Cardiovascular Agents causing Allergic Conditions such as according to K#13 drugs ts1, s5u are D2 and K#3 ts2u is D3. Similarly, specific allergic conditions are also retrieved. 5.3
Now let us move towards the scenario where the doctor is looking for drug replacement for the patient having heart conditions based on its side effects. For replacing the drugs, the system can be queried by locating all the CVAs (this information comes from DrugBank, MeSH in the current navigation space) and then excluding all the CVAs causing Allergic Conditions. The related SPARQL query can be given as follows:
?drug p2 D5. ?drug p1 ?se FILTER (?se != C10) }
The condition is given in the filter clause because SPARQL does not support negation operation directly. In order to do so, all the drugs which are CVAs are retrieved by SPARQL and then it filters the drugs which do not cause allergic conditions. Same is the case with the lattice operation where concept K#4 is selected because it contains all the cardiovascular agents and then a more specific concept is obtained containing the CVAs causing allergic conditions i.e., K#2 and minus operator is applied to perform the desired filtering. The answer obtained is s3.
In a sense, the navigation space follows the query mechanism provided by Google where a query is posed by the user and this query is mapped to a preexisting cluster of documents. In the same way, when a query is posed by the user, our query mechanism maps the query to a cluster of RDF triples, where each element in an RDF triple keeps the URI of a web-page. 6
The current approach was applied to biomedical data. This section details the experimental evaluation for the creation of the navigation space The proposed algorithm was coded in C++ and the experiments was performed using 3GB RAM on Ubuntu version 12.04. 6.1
The datasets containing information about drugs are DrugBank, SIDER, MedDRA and MeSH as described in section 3.1. DrugBank keeps detailed information about each of the drugs, their categories and the proteins it targets. The other database is SIDER which keeps the side effects of the drugs contained on the packaging of the drug. The access to these two data sets is provided by University of Mannheim through two different endpoints1314.
The schema associated to the side effects of the drug is available on
BioPortal [
During this experiment, two subsets of the dataset were considered. Both belonging to two major classes of drugs i.e., Cardiovascular Agents (CVA) and Central Nervous System (CNS). 6.2
In the following, we study the scalability of Semantic Pattern Structures over large dataset. Table 5 precises the statistics of the data. Pattern concept lattices over both the chosen data sources was built in 0-25 seconds for the maximum of 31098 triples. Figure 4b shows the variation in the size of the navigation space for both data sets. The navigation space contains a maximum of around 500000 clusters of triples which were generated in 25 seconds. However, there are several ways to reduce these number of concepts. The filtering based on the depth of classes considered in the taxonomy which allows the reduction in the number of clusters while generating the concept lattice and hence causes decrease in the runtime of creating the navigation space. Most of these very general classes are not very interesting for the domain expert. Moreover, there are several measures such as support, stability and lift which allow post-filtering of the navigation space.
In [
This paper proposes a new approach for navigating semantic web data and targets the capabilities of FCA to deal with RDF data. It provides navigational and search capabilities over RDF triples as well as RDF Schema distributed over several resources. This paper proposes a new similarity measure for pattern structures to deal with RDF data as well as RDF Schema simultaneously, termed as Semantic Pattern Structures. The pattern concepts in the concept lattice are considered as clusters of of RDF triples which can then be navigated and queried by the user.