An Approach Towards Classifying and Navigating RDF data based on Pattern Structures Mehwish Alam and Amedeo Napoli LORIA (CNRS – Université de Lorraine) BP 239, 54506 Vandoeuvre-les-Nancy, France {mehwish.alam,amedeo.napoli@loria.fr} Abstract. With an increased interest in machine processable data, more and more data is now published in RDF (Resource Description Frame- work) format. This RDF data is present in independent and distributed resources which needs to be centralized, navigated and searched for do- main 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 re- sources. Afterwards, SPARQL queries can be posed over this navigation space to access these distributed resources from one platform for infor- mation retrieval purposes. Keywords: Formal Concept Analysis, Navigation Space, Linked Open Data, RDF, RDF Schema, Semantic Pattern Structures. 1 Introduction With the efforts of Semantic Web community many technologies have been of- fered 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 [2]. As a contrast to textual resources, LOD does not need extensive preprocessing as it is already annotated in the form of entities and relationships. This structured format leads to other kind of challenges. One of the ba- sic characteristics of Semantic Web is that it follows a decentralized publica- tion 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 ap- plications. Moreover, external schemas in the form of ontologies or taxonomies c 2015 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. Local Proceedings also appeared in ISBN 978-84-606-7410-8, Universidad de Málaga (Dept. Matemática Aplicada), Spain. 34 Mehwish Alam and Amedeo Napoli 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 con- tain the instantial information such as SWRC ontology [11] and some resources may only contain instantial information such as DBLP. The problem of how to provide one platform for accessing several and related semantic web resources to build domain specific applications still persists. This paper focuses on how to link several related heterogeneous RDF resources present on distributed loca- tions containing RDF data and RDF Schema into one space which can further be navigated and searched by the end user. We call it a “navigation space” because it provides centralization over RDF triples and also over RDF Schema belonging to several resources. This space provides navigation and querying over RDF triples as well as RDF Schema. The current paper introduces a new framework based on Formal Concept Analysis [8] which focuses on how a navigation space is created over RDF data by taking into account an existing RDF Schema to provide search capabilities over distributed and heterogeneous Semantic Web resources. In the current study we only consider a part of RDF Schema which keeps subclass-superclass rela- tion. Other constructs such as sub-property and relation between classes are not considered here. FCA alone may not be able to handle the complex data such as RDF data and RDF Schema as it considers only binary data. To deal with this shortcoming, we employ an extension of FCA, namely Pattern Structures [7]. We propose a new framework called Semantic Pattern Structures, that takes RDF triples and the RDF Schema as an input and produces a “navigation space”. This navigation space provides centralization over distributed RDF resources and keeps a partially ordered organization of the classes of RDF triples with respect to RDF Schema from data sources which may or may not be part of LOD. The lattice structure allows for querying over RDF graph w.r.t. subject, predicate and object and makes use of the partial order relation between the concepts. This enables simultaneous search over schema and the facts contained in an RDF graph. This navigation space allows querying using well-documented and well-know query language, SPARQL. Several data sources are simultane- ously queried through one platform. To date this is the first attempt to deal with RDF graph and RDF Schema using pattern structures. The paper is structured as follows: section 2 gives the motivating example, section 3 introduces the basic notion of Pattern Structures with an example. Sec- tion 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 Motivating Example 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 Towards Semantic Indexing over RDF data based on Pattern Structures 35 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 pro- posed 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 Preliminaries 3.1 Linked Open Data Recently, Linked Open Data (LOD) [2] has become a standard for publishing data on-line in the form of Resource Description Framework (RDF)5 which can further be linked to other data sources published in the same format. The idea underlying RDF is based on storing statements about a particular re- source, where each statement is represented as xsubject, predicate, objecty. A 1 http://www.drugbank.ca/ 2 http://sideeffects.embl.de/ 3 http://www.ncbi.nlm.nih.gov/mesh/ 4 http://meddra.org/ 5 http://www.w3.org/RDF/ 36 Mehwish Alam and Amedeo Napoli set of linked statements is referred to as RDF graph which constitutes an RDF triple store. For instance, Table 2 keeps RDF triples for drugs with their side effects and drug categories. The prefixes and full forms of all the abbreviations used in this paper are shown in Table 1. Consider t1 i.e., xs1 , p1 , o1 y, here s1 is subject, p1 is predicate and o1 is the object. A URI U in an RDF graph is a general form of URL. The actual representation of the drug s1 in the form of URI is 1 http://wifo5-04.informatik.uni-mannheim.de/drugbank/ resource/drugs/DB006691 , which is a URI of the DrugBank provided by Uni- versity of Mannheim containing all the information about the drug in the form of triples. DB00669 is the id provided by DrugBank to drug s1 and the name of the drug is obtained by using the rdfs:label predicate defined in RDFS vocab- ulary6 . The subject denotes the resource and the predicate denotes properties of the resource and defines relationship between the subject and the object. In the rest of the paper we use dereferenced resources i.e., s1 instead of complete URI. 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 (rep- resented 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 in- stances 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/ Towards Semantic Indexing over RDF data based on Pattern Structures 37 Abbreviation Term Abbreviation Term p1 http://wifo5-04.informatik.uni-mannheim. p2 http://wifo5-04.informatik.uni-mannheim. de/sider/resource/sider/sideEffect de/drugbank/resource/drugbank/category s1 Sumatriptan C1 Acute Coronary Syndrome s2 Tadalafil C4 Setevens-Johnsons Disorders s3 Theophylline C2 Tachycardia s4 Ticlopidine C3 Urticaria s5 Vardenafil C5 Erythmia Multiforme D1 Fibrinolytic Agents C6 Coronary Artery Disorders D2 Vasoconstrictor Agents C7 Cardiac Arrhythmias D3 Vasodilator Agents C8 Urticarias D4 Fibrin Modulating Agents C9 Allergic conditions NEC D5 Cardiovascular Agents C10 Allergic conditions D6 Molecular Mechanisms of Pharmacological Action C11 Cardiac Disorders D7 Therapeutic Uses C12 Immune System Disorders Table 1: This table keeps the abbreviations of the terms used in the rest of the paper. tid Subject Predicate Object Provenance t1 s1 p1 o1 SIDER t2 s1 p1 C2 SIDER t3 s1 p2 D2 DrugBank t4 s1 type Drug DrguBank t5 o1 type C1 MedDRA t6 C1 sc C6 MedDRA t7 D2 type D5 MeSH t8 D5 sc D7 MeSH ... ... ... ... ... Table 2: RDF triples for the Drug Domain from several resources. (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. 3.2 SPARQL 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, disjunc- tions and constraints over the values of the variables. These graph patterns are matched against the RDF graph and the matched graph is retrieved and manip- ulated 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/ 38 Mehwish Alam and Amedeo Napoli 3.3 Pattern Structures Formal Concept Analysis [8] can process only binary context, more complex data such as graphs, RDF triples can not be directly processed by FCA. Some of the complex data require scaling for these to be considered as binary data. The concept lattice obtained by a binary context mixes between several types of attributes. Pattern structures [7], an extension of FCA, allows direct processing of such kind of complex data such as RDF triples (as we show in this paper). The pattern structures were introduced in [7]. 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 f or A Ď G gPA d˝ :“ tg P G|d Ď δpgqu 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 Towards Semantic Pattern Structures The decentralization issue is raised when many entities are contributing state- ments 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 Struc- tures 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. Towards Semantic Indexing over RDF data based on Pattern Structures 39 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 From RDF Triples to Semantic Pattern Structures 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 , ok y, 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 re- lated 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, C1 y 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, C6 y, 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 infor- mation 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. 40 Mehwish Alam and Amedeo Napoli D9 C13 D8 C11 C12 D6 D7 C6 C7 C10 D4 D5 C1 C2 C8 C9 C3 C4 C5 D1 D2 D3 Fig. 1: RDF Schema for Side Effects (MedDRA) Fig. 2: RDF Schema for Drug Category (MeSH) pT1 q. pT2 q. The pair ppj : Ck q gives a description dij P Ds . The mapping of entities to description δ : S Ñ Ds is given as follows: let si P S then δpsi q “ tdi1 , . . . , diq u where i P t1, . . . , nu and dij “ tpj : tC1 , C4 , . . . , Cm uu 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 δps1 q = {(p1 : tC1 , C2 , C3 u), (p2 : tD2 u) }. 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 s1 {(p1 : tC1 , C2 , C3 u), (p2 : tD2 u)} s2 {(p1 : tC1 , C4 , C5 u), (p2 : tD3 u)} s3 {(p1 : tC2 u), (p2 : tD3 u)} s4 {(p1 : tC3 , C4 , C5 u), (p2 : tD8 u)} s5 {(p1 : tC1 , C3 u), (p2 : tD2 u)} Table 3: RDF Triples as entities S and semantic descriptions Ds . 4.2 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 [9]. Definition 2 (Least Common Subsumer). Given a partially ordered set 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 E 1 such that C Ď E 1 and D Ď E 1 then E Ď E 1 . Towards Semantic Indexing over RDF data based on Pattern Structures 41 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 , C5 q “ C10 . Similarity Operation over Set of Descriptions: For describing the similar- 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 δps1 q “ d1 “ tp1 : tC1 , C2 , C3 uu and δps2 q “ d2 “ tp1 : tC1 , C4 , C5 uu. 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, δps1 q [ δps2 q “ xp1 : tC1 , C2 , C3 uy [ xp1 : tC1 , C4 , C5 uy. Meaning that δps1 q [ δps2 q “ p1 : xlcspC1 , C1 q, lcspC1 , C5 q, . . . y. Then, δps1 q [ δps2 q “ p1 : tC1 , C10 , C11 , C13 u. As we have C1 ď C11 ď C13 and C10 ď C13 then we pick only the specific classes i.e., C1 and C10 . Finally, δps1 q [ δps2 q “ p1 : tC1 , C10 u. Now let us consider the complete descriptions of the two entities i.e., δps1 q “ {(p1 : tC1 , C2 , C3 u), (p2 : tD2 u)} and δps2 q “ {(p1 : tC1 , C4 , C5 u), (p2 : tD3 u)}. Then, δps1 q [ δps2 q “ {(p1 : tC1 , C2 , C3 u), (p2 : tD2 u)} [ {(p1 : tC1 , C4 , C5 u), (p2 : tD3 u)}. The set of least common subsumers for p1 will be C1 , C10 . The least common subumer between p2 : tD3 u and p2 : tD2 u is p2 : tD5 u. Finally, the similarity between these two drugs will be {(p1 : tC1 , C10 u), (p2 : tD5 u)}. The proposed similarity measure fulfills the property of a similarity operator i.e., commutative, associative and idempotent [7]. The number of RDF Schema considered are equal to number of predicates in the entity-description representa- tion of an RDF graph. In the running example, we use two schemas to show that our method can also be easily applied to multiple RDF Schemas which are either independent or parts of the same schema distributed over several resources. 4.3 Building the Semantic Pattern Concept Lattice For building the semantic pattern concept lattice using the above similarity measure over several RDF Schemas, according to the running example, δps1 q [ δps2 q “ tpp1 : tC1 , C10 uq, pp2 : tD5 uqu. The semantic pattern concept lattice is built according to definition 1. For instance, ts1 , s2 ul “ tpp1 : tC1 , C10 uq, pp2 : tD5 uqu but tpp1 : tC1 , C10 uq, pp2 : tD5 uqu l “ ts1 , s2 , s5 u. 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. 42 Mehwish Alam and Amedeo Napoli K#8 K#4 K#9 K#5 K#6 K#2 K#10 K#11 K#13 K#7 K#3 K#1 K#12 K#0 Fig. 3: Pattern Concept lattice for Drugbank K#ID Extent Intent K#1 ts1 u (p1 : tC1 , C2 , C3 u), (p2 : tD2 u) K#2 ts1 , s2 , s5 u (p1 : tC1 , C10 u), (p2 : tD5 u) K#3 ts2 u (p1 : tC1 , C4 , C5 u), (p2 : tD3 u) K#4 ts1 , s2 , s3 , s5 u (p1 : tC11 u), (p2 : tD5 u) K#5 ts1 , s3 u (p1 : tC2 u), (p2 : tD5 u) K#6 ts2 , s3 u (p1 : tC11 u), (p2 : tD3 u) K#7 ts3 u (p1 : tC2 u), (p2 : tD3 u) K#8 ts1 , s2 , s3 , s4 , s5 u (p1 : tC13 u), (p2 : tD8 u) K#9 ts1 , s2 , s4 , s5 u (p1 : tC10 u), (p2 : tD8 u) K#10 ts1 , s4 , s5 u (p1 : tC3 u), (p2 : tD8 u) K#11 ts2 , s4 u (p1 : tC4 , C5 u), (p2 : tD8 u) K#12 ts4 u (p1 : tC3 , C4 , C5 u), (p2 : tD9 u) K#13 ts1 , s5 u (p1 : tC1 , C3 u), (p2 : tD2 u) Table 4: Details of Pattern Concept lattice in Figure 3 4.4 Interpreting and Navigating the Pattern Concept Lattice This pattern concept lattice not only serves as a navigation space but also pro- vides 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 , C1 q, ps1 , p2 , D2 q, . . . 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 techni- cal 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 Towards Semantic Indexing over RDF data based on Pattern Structures 43 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 SPARQL Queries over Pattern Concept Lattice 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 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 tsi ul “ tdi u 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 tdi u 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, sl 1 “ pp1 : tC1 , C2 , C3 u, p2 : tD2 uq (K#1) and the answer would be pp1 : tC1 , C2 , C3 u, p2 : tD2 uq. The first part of the answer pp1 : tC1 , C2 , C3 u belongs to SIDER while p2 : tD2 u 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 44 Mehwish Alam and Amedeo Napoli 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 Queries with Joins 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 re- trieved should be Cardiovascular Agent causing some Allergic Condition. Then the SPARQL query with subject-subject join will be as follows: SELECT ?drug WHERE { ?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 pred- icate 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 , s5 u 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 ad- ditional information regarding more specific categories related to Cardiovascular Agents causing Allergic Conditions such as according to K#13 drugs ts1 , s5 u are D2 and K#3 ts2 u is D3 . Similarly, specific allergic conditions are also retrieved. 5.3 Queries with Filtering Criteria Now let us move towards the scenario where the doctor is looking for drug re- placement 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: SELECT ?drug WHERE { ?drug p2 D5 . Towards Semantic Indexing over RDF data based on Pattern Structures 45 ?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 spe- cific 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 pre- existing 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 Experimentation 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 Drug Search The datasets containing information about drugs are DrugBank, SIDER, Med- DRA and MeSH as described in section 3.1. DrugBank keeps detailed informa- tion 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 BioPor- tal [12], which is a web portal that provides access to a repository of biomedical ontologies. BioPortal is developed by National Center for Biomedical Ontology (NCBO) [10]. The Medical Dictionary for Regulatory Activities (MedDRA) Ter- minology is the international medical terminology. During this experiment we will enrich side effects with schema level information using MedDRA terminol- ogy. In case of the drug categories MeSH vocabulary thesaurus was taken into account. MeSH (Medical Subject Headings) is a controlled vocabulary thesaurus. The drug categories from DrugBank will be enriched with the tree numbers from MeSH vocabulary. The tree numbers arrange the terms from MeSH in a hier- archical manner known as MeSH Tree Structures. In the current experiment we 13 http://wifo5-04.informatik.uni-mannheim.de/drugbank/snorql/ 14 http://wifo5-04.informatik.uni-mannheim.de/sider/snorql/ 46 Mehwish Alam and Amedeo Napoli used the MeSH vocabulary already present in the form of RDF in Bio2RDF [1, 5], which makes the public databases related to Bioinformatics such Kegg, MeSH, HGNC etc. available in the RDF format. 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 Evaluation 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. Datasets No. of Triples No. of Subjects No. of Objects Runtime Cardiovascular Agents 31098 145 927 0-22 sec Central Nervous System 22680 105 1050 0-25 sec Table 5: Statistics of two datasets and navigation space. Fig. 4: Size of the Navigation Space for each dataset. Towards Semantic Indexing over RDF data based on Pattern Structures 47 7 Related work In [6], the author focuses on allowing conceptual navigation to RDF graphs, where each concept is accessed through SPARQL-like queries. However, in our case several RDF graphs are considered and we use the already existing, well- established and well-documented query language, SPARQL. Moreover, [3] in- troduces ontological pattern structures for enriching raw data with EL ontolo- gies. But both the approaches consider only one resource at a time, hence not targeting the problem of decentralization. As a contrast, our approach provide navigation space over RDF graphs as well as schema level information from sev- eral resources allowing user to access information from one platform. In [4], the authors introduce a new clause Categorize By which clusters SPARQL query answers w.r.t to background knowledge present as ontologies. Like our approach, only taxonomy is used for enriching, however, unlike our approach if clusters the answers after obtaining the query answers. As a contrast, our approach provides classification of the RDF triples as well as RDF Schema before hand. After- wards, SPARQL queries are mapped to the existing clusters and the answer is shown to the user. In such a case, the query response time is faster than the Categorize By clause. Moreover, as it provides clustering over answers only, it lacks the capability to provide user with additional information. 8 Conclusion and Future Work This paper proposes a new approach for navigating semantic web data and tar- gets 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. References 1. François Belleau, Marc-Alexandre Nolin, Nicole Tourigny, Philippe Rigault, and Jean Morissette. Bio2rdf: Towards a mashup to build bioinformatics knowledge systems. Journal of Biomedical Informatics, 41(5):706–716, 2008. 2. Christian Bizer, Tom Heath, and Tim Berners-Lee. Linked data - the story so far. Int. J. Semantic Web Inf. Syst., 5(3):1–22, 2009. 3. Adrien Coulet, Florent Domenach, Mehdi Kaytoue, and Amedeo Napoli. Using pattern structures for analyzing ontology-based annotations of biomedical data. In 11th International Conference on Formal Concept Analysis,, 2013. 4. Claudia d’Amato, Nicola Fanizzi, and Agnieszka Lawrynowicz. Categorize by: Deductive aggregation of semantic web query results. In Lora Aroyo, Grigoris An- toniou, Eero Hyvönen, Annette ten Teije, Heiner Stuckenschmidt, Liliana Cabral, and Tania Tudorache, editors, ESWC (1), volume 6088 of Lecture Notes in Com- puter Science, pages 91–105. Springer, 2010. 48 Mehwish Alam and Amedeo Napoli 5. Michel Dumontier, Alison Callahan, Jose Cruz-Toledo, Peter Ansell, Vincent Emonet, François Belleau, and Arnaud Droit. Bio2rdf release 3: A larger, more connected network of linked data for the life sciences. In Posters & Demonstrations Track ISWC., 2014. 6. Sébastien Ferré. Conceptual navigation in RDF graphs with sparql-like queries. In Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010. Proceedings, pages 193–208, 2010. 7. Bernhard Ganter and Sergei O. Kuznetsov. Pattern structures and their projec- tions. In Harry S. Delugach and Gerd Stumme, editors, ICCS, volume 2120 of Lecture Notes in Computer Science, pages 129–142. Springer, 2001. 8. Bernhard Ganter and Rudolf Wille. Formal Concept Analysis: Mathematical Foun- dations. Springer, Berlin/Heidelberg, 1999. 9. Ralf Küsters and Ralf Molitor. Computing least common subsumers in ALEN. In Proceedings of the Seventeenth International Joint Conference on Artificial Intel- ligence, IJCAI, pages 219–224, 2001. 10. Mark A. Musen, Natalya Fridman Noy, Nigam H. Shah, Patricia L. Whetzel, Christopher G. Chute, Margaret-Anne D. Storey, and Barry Smith. The national center for biomedical ontology. JAMIA, 19(2):190–195, 2012. 11. York Sure, Stephan Bloehdorn, Peter Haase, Jens Hartmann, and Daniel Oberle. The swrc ontology - semantic web for research communities. In EPIA, volume 3808 of Lecture Notes in Computer Science, pages 218–231. Springer, 2005. 12. Patricia L. Whetzel, Natalya Fridman Noy, Nigam H. Shah, Paul R. Alexander, Csongor Nyulas, Tania Tudorache, and Mark A. Musen. Bioportal: enhanced func- tionality via new web services from the national center for biomedical ontology to access and use ontologies in software applications. Nucleic Acids Research, 39(Web- Server-Issue):541–545, 2011.