Mehwish Alam
email: mehwish.alam@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Lattice-Based Views over SPARQL Query Results

Keywords: Formal Concept Analysis, SPARQL Query Views, Lattice-Based Views

SPARQL queries over semantic web data usually produce a huge list of tuples as answers that may be hard to understand and interpret. Accordingly, this paper focuses on Lattice Based View Access (LBVA), a framework based on Formal Concept Analysis, to provide a view using View By clause based on a concept lattice. This lattice can be navigated for retrieving or mining specific patterns in query results.

Introduction

At present, the Web has become a potentially large repository of knowledge, which is becoming main stream for querying and extracting useful information. In particular, Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] provides a method for publishing structured data in the form of RDF. These RDF resources are interlinked with each other to form a cloud. SPARQL queries are used in order to make these resources usable, i.e., queried. Queries in natural language against standard search engines sometimes may require integration of data sources. The standard search engines will not be able to easily answer these queries, e.g., Currencies of all G8 countries. Such a query can be formalized as a SPARQL query over data sources present in LOD cloud through SPARQL endpoints for retrieving answers. Moreover, these queries may generate huge amount of results giving rise to the problem of information overload [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF]. A typical example is given by the answers retrieved by search engines, which mix between several meanings of one keyword. In case of huge results, user will have to go through a lot of results to find the interesting ones, which can be overwhelming without any specific navigation tool. Same is the case with the answers obtained by SPARQL queries, which are huge in number and it may be harder for the user to extract the most interesting patterns. This problem of information overload raises new challenges for data access, information retrieval and knowledge discovery w.r.t web querying.

This paper proposes a new approach based on Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]). It describes a lattice-based classification of the results obtained by SPARQL queries by introducing a new clause "View By" in SPARQL query. This framework, called Lattice Based View Access (LBVA), allows the classification of SPARQL query results into a concept lattice, referred to as a view, for data analysis, navigation, knowledge discovery and information retrieval purposes. The View By clause enhances the functionality of already existing Group By clause in SPARQL query by adding sophisticated classification and Knowledge Discovery aspects. Here after, we describe how a lattice-based view can be designed from a SPARQL query. Afterwards, a view is accessed for analysis and interpretation purposes which are totally supported by the concept lattice. In case of large data only a part of the lattice [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF] can be considered for the analysis.

The intuition of classifying results obtained by SPARQL queries is inspired by web clustering engines [START_REF] Carpineto | A survey of web clustering engines[END_REF] such as Carrot21 . The general idea behind web clustering engines is to group the results obtained by query posed by the user based on the different meanings of the terms related to a query. Such systems deal with unstructured textual data on web. By contrast, there are some studies conducted to deal with structured RDF data. In [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF], the authors introduce a clause Categorize By to target the problem of managing large amounts of results obtained by conjunctive queries with the help of subsumption hierarchy present in the knowledge base. By contrast, the View By clause generates latticebased views which provide a mathematically well-founded classification based on formal concepts and an associated concept lattice. Moreover, it also paves way for navigation or information retrieval by traversing the concept lattice and for data analysis by allowing the extraction of association rules from the lattice. Such data analysis operations allow discovery of new knowledge. Additionally, unlike Categorize By, View By can deal with data that has no schema (which is often the case with linked data). Moreover, View By has been evaluated over very large set of answers (roughly 100,000 results) obtained over real datasets. In case of larger number of answers, Categorize By does not provide any pruning mechanism while this paper describes how the views can be pruned using icerberg lattices.

The paper is structured as follows: Section 2 describes the motivation. Section 3 gives a brief introduction of the state of the art while Section 4 defines LBVA and gives the overall architecture of the framework. Section 5 discusses some experiments conducted using LBVA. Finally, Section 6 concludes the paper.

Motivation

In this section we introduce a motivating example focusing on why LOD should be queried and why the SPARQL query results need classification. Let us consider a query searching for museums where the exhibition of some artists is taking place along with their locations. A standard query engine is not adequate for answering such kind of questions as it will produce a separate list of museums with the artists whose work is displayed there and a separate list of museums with their locations. However, a direct query over LOD will perform resource integration to provide answers to the query. This query generates a huge amount of results, which further needs manual work to group the interesting links.

Linked Open Data represents data as RDF (Resource Description Framework) graphs. An RDF graph is a set of RDF triples, i.e., subject, predicate, object , which is represented as node-and-arc-labeled directed graphs. SPARQL 2 is the standard query language for querying RDF graphs, which is based on matching graph patterns against RDF graphs. According to the scenario described above, the SPARQL query is shown in Listing 1. This query retrieves the list of museums along with the artists whose work is exhibited in a museum along with the location of a museum. Lines 5 and 6 of this query retrieve information about the artists whose work is displayed in some museum. More precisely, the page containing the information on a museum (?museum) is connected to the page of the artists (?artist) through a page on the work of artist (?painting) displayed in the museum. An excerpt of the answers obtained by Group by clause is shown below: The problem encountered while browsing such an answer is that there are thousands of results to navigate through. Even after using the Group By clause the answers are arranged into several small groups because first there is more than one grouping criteria and second, there are many values of the variables in the Group By clause. By contrast, the clause View By activates the LBVA framework, where a classification of the statements is obtained as a concept lattice (see Figure 1a). The concept lattice shown in Figure 1a is labeled in a reduced format (reduced labeling), meaning that if a parent class contains an attribute then this attribute is also inherited by its children concepts. Let us consider the parent concept has the attribute France then its two children concepts also have the attribute France. Now if the museums in UK displaying the work of Goya are to be retrieved, first the concept containing all the museums displaying the work of Goya is obtained and then the specific concept Goya and UK is retrieved by drilling down. Finally, the answer is National Gallery.

≤ K as (A 1 , B 1 ) ≤ (A 2 , B 2 ) ⇔ A 1 ⊆ A 2 (⇔ B 2 ⊆ B 1 ). Consequently, L K = C K , ≤ K
forms the concept lattice of K. There exist several algorithms [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF] to build a concept lattice which also focus on efficiency of building the lattices for large number of objects.

In order to restrict the number of concepts in some cases iceberg concept lattices can be used [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF], which contain only the top most part of the lattice. Formally, let B ⊆ M and let minimum support, denoted by minsupp, be an integer representing a support threshold value. For a given concept (A,B), the support of B is the cardinality of A denoted by |A|. Relative support is given by |A|/|G| and belongs to the interval [0, 1]. An intent B in concept (A,B) is said to be frequent as soon as supp(B) = |A|/|G| ≥ minsupp. Likewise, a concept is called a frequent concept if its intent is frequent. The set of all frequent concepts of K, for a given threshold, is called an iceberg concept lattice of K. Along with iceberg lattices a stability index is also used for filtering the concepts. The stability index shows how much the concept intent depends on particular objects of the extent.

In some cases, a many-valued context is obtained instead of a formal context. A many-valued context is denoted by (G, M, W, I), where G is the set of objects, M is the set of attributes, W is the set of attribute values for each attribute and I represents a ternary relation between G, M, W , denoted as I ⊆ G × M × W . However, in order to obtain a one-valued binary context from the many valued context, scaling procedure is adopted. A scale S m of an attribute m of a manyvalued context is a one-valued context (G m , M m , I m ) with m(G) = S m for m ∈ M and then the new set of attributes is M s = m∈M S m . During plain scaling the object set G remains unchanged, every many-valued attribute m is replaced by the scale attributes of scale S m .

FCA also allows knowledge discovery using association rules. Duquenne-Guigues (DG) basis for implications [START_REF] Guigues | Familles minimales d'implications informatives résultant d'un tableau de données binaires[END_REF] is the minimal set of implications equivalent to the set of all valid implications for a formal context K = (G, M, I). An implication over the attribute set M in a formal context is of the form B 1 → B 2 , where B 1 , B 2 ⊆ M . The implication holds iff every object in the context with an attribute in B 1 also has all the attributes in B 2 . For example, when (A 1 , B 1 ) ≤ (A 2 , B 2 ) in the lattice, we have that B 1 → B 2 . DG-basis represents all information lying in the concept lattice.

Lattice Based View Access

In this paper, we propose an approach called Lattice Based View Access for classification of SPARQL query results in the form of a concept lattice referred to as view. In the scenario of LOD, the RDF data and query processing procedure can not be controlled. Here we define views over RDF data by processing the set of tuples returned by the SPARQL query as answers.

SPARQL Queries with Classification Capabilities: The idea of introducing a View By clause is to provide classification of the results and add a knowledge discovery aspect to the results w.r.t the variables appearing in View By clause. Initially, the user poses SPARQL query of the form SELECT ?v 1 ?v 2 . . . ?v n WHERE { condition/pattern } VIEW BY ?v l . More formally, "view by(v l ) : q( -→ v )" where -→ v is a vector of variables containing free variables called answer variables and v l is a variable in the SELECT clause of SPARQL query providing the viewing criteria. The evaluation of query q over RDF triple store generates answers in the form of tuples. A tuple is a vector of terms (set of constants) mapped to the answer variables in query q. The processing of a SPARQL query

q( - → v ) = q(v 1 , v 2 , . . . , v n ) yields a set of tuples R = {(X i 1 , X i 2 , . . . , X i n )}
, where i = {1, . . . , k} where each tuple provides an elementary answer to the query q( -→ v ).

Following the example in section 2, let us consider the user gives " VIEW BY ?artist" instead of Group By clause for the query in Listing 1.1. Then, v 1 = artist is the object variable, v 2 = museum and v 3 = country are the attribute variables and Figure 1a shows the generated view. In Figure 1b, we have; v 1 = artist is the object variable, v 2 = museum and v 3 = country are attribute variables.

Designing a Formal Context (G, M, W, I):

The results obtained by the query are in the form of set of tuples, which are then organized as a many-valued context. Among the variables one variable appears in the View By clause and is considered as the object variable. All the other variables are considered as attribute variables. Let v l be the object variable in -→ v = (v 1 , v 2 , . . . , v n ), X i l be the answers obtained for v l , then attribute variables will be v 1 , . . . , v l-1 , v l+1 , . . . , v n . The answers associated to attribute variables can be given as {X i 1 , X i 2 , . . . , X i l-1 , X i l+1 , . . . , X i n }. Then, G = {X i l , i = 1, . . . , k} and M is the set of many valued attributes, given as M = {v 1 , v 2 , . . . , v l-1 , v l+1 , . . . , v n } and W represents the attribute values, i.e., W = {X i 1 , X i 2 , . . . , X i l-1 , X i l+1 , . . . , X i n }. The occurrence of an object and an attribute together in R = {(X i 1 , X i 2 , . . . , X i n )} gives the ternary relation I.

Let us continue the example discussed in section 2. The answers are organized into many-valued context as follows. The distinct values of the variable ?museum are kept as a set of objects, so G = {M useeduLouvre, M useodelP rado}. The attribute variables artist,country provide the set of attributes M = {artist, country} and the tuples related to the variables provide attribute values, w 1 = {Raphael, LeonardoDaV inci} and w 2 = {F rance, Spain U K}. The obtained many-valued context is shown in Table 1 Building a Concept Lattice: Once the context is designed, a concept lattice (view) can be built using an FCA algorithm. This step is straight forward as soon as the context is provided. In the current study, we used AddIntent, which is an efficient implementation for building a concept lattice [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF]. At the end of this step the concept lattice is built and the interpretation step can be considered. However, one limitation of the systems based on FCA is that they may encounter exponential time and space complexity in the worst case scenario for generating a concept lattice [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]. A view on SPARQL query in section 2, i.e, a concept lattice corresponding to Table 2 is shown in Figure 1a.

Interpretation Operations over a Lattice-Based Views: A formal context effectively takes into account the relations by keeping the inherent structure of the relationships present in LOD as object-attribute relation. When a concept lattice is built, each concept keeps a group of terms sharing some attribute. This concept lattice can be navigated for searching and accessing particular LOD elements through the corresponding concepts within the lattice. This lattice can be drilled down from general to specific concepts or rolled up to find the general ones. For example, for retrieving the museums where there is an exhibition of Caravaggio's paintings, it can be seen in the concept lattice shown in Figure 1a that the paintings of Caravaggio are displayed in Musee du Louvre, Museo del Prado and National Gallery. Now, in order to filter it by country, i.e., obtain French museums displaying Caravaggio. Musee du Louvre can be retrieved by navigating the same lattice. To retrieve museums located in France and Spain, a general concept containing all the French Museums with Caravaggio's painting is retrieved and then a specific concept containing the museums in France or Spain displaying Caravaggio can be accessed by navigation. The answer obtained will be Musee du Louvre and Museo del Prado. After obtaining the view, i.e., the concept lattice, it can be accessed to obtain the DG-basis of implications. For example, the rule Goya, Raphael, Caravaggio → Spain suggests that in Spain there exists a museum displaying the work of Goya, Raphael, Caravaggio (this implication is obtained from the view in Figure 1a). In order to get more specific answer, the user can browse through lattice and obtain Museo Del Prado.

Experimentation

DBpedia

DBpedia is currently comprised of a huge amount of RDF triples in many different languages which reflects the state of Wikipedia. Due to information extraction from crowd-sourced web site, triples present on DBpedia may contain incorrect information. Even if Wikipedia contains correct information, a parser may pick up wrong information [START_REF] Wienand | Detecting incorrect numerical data in dbpedia[END_REF]. Due to the above described reasons some of the properties may not be used uniformly. In the current experiment, we extracted the information about movies with their genre and location.

SELECT ?movie ?genre ?country WHERE { ?movie rdf:type dbpedia-owl:Film . ?movie dbpprop:genre ?genre . ?movie dbpprop:country ?country .} VIEW BY ?movie

The obtained concept lattice contained 1395 concepts. Out of which 201 concepts on the first level were evaluated manually for correctness of the information about the movie genre. 141 concepts kept the genre information about the movie. 45% of these concepts contained wrong genre information as its intent (see first three concepts in Table 3). In such a case, the generated latticebased view helps in separating music genre from the movie genre and further guide in introducing a new relation such as soundtrackGenre and adding new triples to the knowledge base, for example, dbpedia:The Scorpion King, dbpedia-owl:soundtrackGenre, dbpedia:Hard Rock. Moreover, If we observe the obtained view, it can be seen that there are too few movies from countries other than United States and India. For example, C#4 and C#5 are the classes for movies from United States and India, where there are 1225 movies from India in DBpedia and 750 movies from United States. Finally, it can be concluded that the information present on DBpedia still needs to be corrected and completed.

The concept lattice can help in obtaining classes of movies w.r.t countries also. As this approach provides an added value to the already existing Group By clause, it is possible to find movies which are made in collaboration with several countries. For example, The Scorpion King was made in collaboration with United States, Germany and Belgium.

YAGO

The construction of YAGO ontology is based on the extraction of instances and hierarchical information from Wikipedia and Wordnet. In the current experiment, we posed a similar query to YAGO with the View By clause. While querying YAGO it was observed that the genre and location information was also given in the subsumption hierarchy of ontology. The first level of the obtained view kept the groups of movies with respect to their languages. e.g., the movies with genre Spanish Language Films. However, as we further drill down in the concept lattice we get more specific categories which include the values from the location variable such as Spain, Argentina and Mexico. Finally, it can be concluded that YAGO provides a clean categorization of movies by making use of the partially ordered relation between the concepts present in the concept lattice. YAGO also learns instances from Wikipedia and it contains many movies from all over the world. This observation gives the idea about the strong information extraction algorithm as it contains more complete information.

DG-Basis of Implications for YAGO and DBpedia were computed. The implications were naively pruned with respect to support threshold. For DBpedia, the number of rules obtained were 64 for a support threshold of 0.11%. In case of YAGO, around 1000 rules were extracted on support threshold of 0.2%. Table 4 contains some of the implications obtained for both the datasets. It can be clearly observed that the support for the implications is much larger in YAGO Impl. ID Supp. Implication YAGO 1.

96 wikicategory RKO Pictures films → United States 2.

46 wikicategory Oriya language films → India DBpedia 3.

3 Historical fiction → United Kingdom@en 4.

3 Adventure fiction, Action fiction → Science fiction than DBpedia, which points towards the completion of YAGO. This fact is actually useful in finding regularities in the SPARQL query answers which can not be discovered from the raw tuples obtained. For example, rule#1 states that RKO picture films is an American film production and distribution company as all the movies produced and distributed by them are from United States. Moreover, rule#2 says that all the movies in Oriya language are from India.

Which actually points to the fact that Oriya is one of many languages that is spoken in India. On the other hand, some of the rules obtained from DBpedia are incorrect. For example, rule#3 states the strange fact that all the historical fiction movies are from United Kingdom. Same is the case with rule#4 which states that all the movies which are Adventure fiction and Action fiction are also Science Fiction, which may not actually be the case. Through the comparison of the DG-Basis for both the datasets it can be observed that the YAGO may be more appropriate for further use by the application development tools and knowledge discovery purposes.

For each of the above queries we tested how our method scales with growing number of results. The number of answers obtained by DBpedia were around 4000 and the answers obtained by YAGO were 100,000. The experimental results of the runtime for the building the concept lattice are shown in Figure 2. Visualization of these experiments along with the implementation can be accessed online 3 .

In LBVA, we introduce a classification framework based on FCA for the set of tuples obtained as a result of SPARQL queries over LOD. In this way, a view is organized as a concept lattice built through the use of View By clause that can be navigated where information retrieval and knowledge discovery can be performed. Several experiments show that LBVA is rather tractable and can be applied to large data. For future work, we intend to use pattern structures with a graph description for each considered object, where the graph is the set of all triples accessible w.r.t reference object.

2Fig. 1 :

 1 Fig. 1: Lattice Based Views w.r.t Museum's and Artist's Perspective .

3 Background

 3 Formal Concept Analysis (FCA): FCA[START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a mathematical framework used for a number of purposes, among which classification and data analysis, information retrieval and knowledge discovery[START_REF] Carpineto | Concept data analysis -theory and applications[END_REF]. Let G be a set of objects and M a set of attributes, andI ⊆ G × M arelation where gIm is true iff an object g ∈ G has an attribute m ∈ M . The triple K = (G, M, I) is called a "formal context". Given A ⊆ G and B ⊆ M , two derivation operators, both denoted by ′ , formalize the sharing of attributes for objects, and, in a dual way, the sharing of objects for attributes: A ′ = {m ∈ M | gIm f or all g ∈ A}, B ′ = {g ∈ G | gIm f or all m ∈ B}. The two derivation operators ′ form a Galois connection between the powersets ℘(G) and ℘(M ). Maximal sets of objects related to maximal set of attributes correspond to closed sets of the composition of both operators ′ (denoted by ′′ ). Then a pair (A, B) is a formal concept iff A ′ = B and B ′ = A. The set A is the "extent" and the set B is the "intent" of the formal concept (A, B). The set C K of all concepts from K is partially ordered by extent inclusion (or dually intent inclusion), denoted by

Fig. 2 :

 2 Fig. 2: Experimental Results.

Table 1 :

 1 . The corresponding nominally scaled one-valued context is shown in Table 2. Many-Valued Context (Museum).

	Museum		Artist			Country
	Musee du Louvre	{Raphael, Leonardo Da Vinci, Caravaggio}	{France}
	Musee d'Art Moderne		{Pablo Picasso}		{France}
	Museo del Prado		{Raphael, Caravaggio, Francisco Goya}	{Spain}
	National Gallery	{Leonardo Da Vinci, Caravaggio, Francisco Goya} {UK}
			Artist			Country
	Museum	Raphael Da Vinci Picasso Caravaggio Goya France Spain UK
	Musee du Louvre	×	×	×	×
	Musee d'Art Moderne		×		×
	Museo del Prado	×		×	×	×
	National Gallery		×	×	×	×

Table 2 :

 2 One-Valued Context KMuseum.

Table 3 :

 3 Some Concepts from L DBpedia (Concept Lattice for DBpedia)

	ID Supp. Intent
	C#1 17 Hard Rock
	C#2 15 Contemporary R&B
	C#3 18 Jazz
	C#4 750 United States
	C#5 1225 India
	C#6	6	France

Table 4 :

 4 Some implications from DG-Basis of Implication (YAGO, DBpedia)

	Execution Time (in seconds)	0.05 0.10 0.15 0.20				Execution Time (in seconds)	40 60 80 100 120
							20
		0.00					0
		20	40	60	80	100	20	40	60	80	100
				Number of Tuples in %					Number of Tuples in %

http://project.carrot2.org/index.html

http://webloria.loria.fr/ ~alammehw/lbva/


Mehwish Alam

Amedeo Napoli

Lattice-Based View Access: A way to Create Views over SPARQL Query for Knowledge Discovery

Keywords: Formal Concept Analysis, SPARQL Query Views, Lattice-Based Views, SPARQL, Classification

The data published in the form of RDF resources is increasing day by day. This mode of data sharing facilitates the exchange of information across the domains. Although it provides easier ways in the use of data such as through SPARQL queries. These queries over semantic web data usually produce list of tuples as answers which may be huge in number or may require further manipulation so that it can be understood and interpreted. Accordingly, this paper introduces a new clause View By in the SPARQL query for creating semantic views over the raw SPARQL query answers. This approach namely, Lattice-Based View Access (LBVA), is a framework based on Formal Concept Analysis (FCA). It provides a classification of the answers of SPARQL queries based on a concept lattice, that can be navigated for retrieving or mining specific patterns in query results w.r.t. user constraints. In this way, the concept lattice can be considered as a materialized view of the data resulting from a SPARQL query.

Introduction

A considerable amount of Semantic Web (SW) data is already available on the web. Thus many agents are looking for more and more data present in the form of ontologies and RDF triples. Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] is a huge source of RDF resources interlinked with each other to form a cloud. SPARQL queries are used in order to make these data usable by domain experts and software agents. Sometimes queries are executed which may generate huge amount of results giving rise to the problem of information overload [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF]. A typical example is the answers retrieved by search engines, which may mix between several meanings of one keyword. In case of huge results, many results are navigated to find the interesting links, which may be overwhelming without any navigation tool. Same is the case with the answers obtained by SPARQL queries, which may be huge in number and it may be harder to extract the most interesting patterns. This problem of information overload raises new challenges for data modeling and analysis and calls for improving data access, information retrieval and knowledge discovery w.r.t web querying.

In order to deal with the problem of information overload, this paper proposes a new approach based on Formal Concept Analysis (FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]), which provides a lattice-based classification of the results obtained by SPARQL queries w.r.t user constraints. This new framework, namely Lattice Based View Access (LBVA), allows the classification of SPARQL query results into a concept lattice, referred to as views, for data analysis, knowledge discovery and information retrieval purposes. Based on one SPARQL query several views can be generated from different perspectives. In addition, LBVA allows for navigation over SPARQL query results. Here after, we describe how the views (a view corresponds to a concept lattice) can be designed from a SPARQL query and the result which is returned. Moreover, the analysis and the interpretation of the views is totally supported by the concept lattice. In case of large data only a part of the lattice can be considered for the analysis using the technique of iceberg lattices.

The intuition of classifying results obtained by querying LOD is inspired by web clustering engines [START_REF] Carpineto | A survey of web clustering engines[END_REF] such as Carrot21 . The general idea behind web clustering engines is to group the results obtained by query posed by the user based on the different meanings of the terms related to a query. Such systems deal with unstructured textual data on web. However, there are some studies conducted to deal with structured RDF data. In [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF], the authors target the problem of managing large amounts of results obtained by conjunctive queries with the help of subsumption hierarchy present in the knowledge base. On the other hand, latticebased views provide classification based on the formal concepts and a partially ordered organization of the results. It also opens possibilities for navigation or information retrieval by traversing the concept lattice and for data analysis by allowing the extraction of association rules from the lattice. Additionally, unlike [START_REF] Claudia D'amato | Categorize by: Deductive aggregation of semantic web query results[END_REF], LBVA also deals with data that has no schema (which is often the case with linked data).

The concept lattice provides a well founded structure on which a series of interpretations can be carried out. This framework is general and does not depend on any particular domain and may be used in addition with external resources, e.g. domain knowledge.

The paper is structured as follows: Section 1 gives a brief overview of Linked Open Data and gives the motivating example. Section 2 defines LBVA and gives the overall architecture of the framework. Section 3 briefly described the experimentation setting. Finally, Section 4 concludes the paper.

1 Linked Open Data Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] is the way of publishing structured data which helps in the connection between several resources through their schema. LOD represents data in the form of RDF graphs. Given a set of URIs U , blank nodes B and literals L, an RDF triple is represented as t = (s, p, o) ∈ (U ∪ B) × U × (U ∪ B ∪ L), where s is a subject, p is a predicate and o is an object. A finite set of RDF triples is called as RDF Graph G such that G = (V, E), where V is a set of vertices and E is a set of labeled edges and G ∈ G, such that G = (U ∪ B) × U × (U ∪ B ∪ L). Each pair of vertices connected through a labeled edge keeps the information of a statement. Each statement is represented as subject, predicate, object referred to as an RDF Triple. V includes subject and object while E includes the predicate.

SPARQL2 is the standard query language for RDF. In the current work we will focus more on the type of queries whose output performs value selection over the variables matching the patterns (queries containing SELECT clause). Now let us assume that there exists a set of variables V disjoint from U in the above definition of RDF, then

(U ∪ V ) × (U ∪ V ) × (U ∪ V ) is a graph pattern called a triple pattern. If a variable ?X ∈ V and ?X = c then c ∈ U .
Given U , V and a triple pattern t a mapping µ(t) would be the triple obtained by replacing variables in t with U . [[.]] G takes an expression of patterns and returns a set of mappings. Given a mapping µ : V → U and a set of variables W ⊆ V , µ is represented as µ |W , which is described as a mapping such that dom(µ |W ) = dom(µ) ∩ W and µ |W (?X) = µ(?X) for every ?X ∈ dom(µ) ∩ W . Finally, the SPARQL SELECT query is defined as follows: Definition 1. A SPARQL SELECT query is a tuple (W, P ), where P is a graph pattern and W is a set of variables such that W ⊆ var(P ). The answer of (W, P ) over an RDF graph G, denoted by [[(W, P )]] G , is the set of mappings:

[[(W, P )]] G = {µ |W |µ ∈ [[P ]] G }
In the above definition var(P ) is the set of variables in pattern P and variables W in SELECT clause of SPARQL query 3 . Further details on the formalization and foundations of RDF databases are discussed in [START_REF] Arenas | Foundations of rdf databases[END_REF].

Example 1. Consider a query all the bands which play different stringed instruments along with their origin. This example will continue in the rest of this paper. Let us name this query Q, then Q can not be answered by standard search engines as it generates a separate list of bands and stringed instruments requiring multiple resources to be integrated. However, Q can be answered by SPARQL queries over LOD. For example, let us consider the SPARQL query in Listing 1.1 over DBpedia 4 . DBpedia is the central hub of LOD which extracts data from Wikipedia and makes it available in the structured format. ? band dbpedia-owl : bandMember ?member . ?member dbpedia-owl : i n s t r u m e n t ? i n s t r u m e n t . ? i n s t r u m e n t dcterms : s u b j e c t Category : S t r i n g i n s t r u m e n t s . GROUP BY ? i n s t r u m e n t ? o r i g i n

The above SPARQL query returns a list of bands along with the instruments they play and their origin as an answer. An excerpt of the answers is shown below: In case of too many origins GROUP BY clause will lead to many small groups which would be hard for the user to observe with respect to origin or instrument, failing in the task of grouping. A classification technique can be used for navigation or interpretation. For example, Figure 1(a) shows a concept lattice for a small part of query answers. Here we can see classes such as the concept which contains all the bands which play Cuatro. If the search is more specified then the origin of each of the bands can also be retrieved. It is possible to retrieve bands which play Cuatro and are from UK, here Chrome Hoof is the band which plays Cuatro in the current small example. On the other hand, Figure 1(b) shows a concept lattice where musical instruments are classified with respect to bands and their origin, giving a totally different perspective over the same set of answers.

Lattice-Based View Access

In this paper, we propose an approach called Lattice-Based View Access which generates a concept lattice referred to as view. This view provides users with classification, navigation and analysis capabilities over these results. In the scenario of LOD, query processing procedure can not be controlled, so, in our algorithm we do not process the SPARQL query. The views are defined over RDF data by processing the set of tuples returned by the SPARQL query.

SPARQL Queries with Classification Capabilities

The idea of introducing a VIEW BY clause is to provide classification of the results and add a knowledge discovery aspect to the results w.r.t the variables appearing in VIEW BY clause. For example, we have a SPARQL SELECT query Q = SELECT ?X ?Y ?Z WHERE {pattern P} VIEW BY ?X then the set of variables V = {?X, ?Y, ?Z}. According to the definition 1 the answer of the tuple (V, P ) is represented as [[({?X, ?Y, ?Z}, P )]] = µ i where i ∈ {1, . . . , k} and k is the number of mappings obtained for the query Q. Here, dom(µ i ) = {?X, ?Y, ?Z} which means that µ(?X) = X i , µ(?Y ) = Y i and µ(?Z) = Z i . Finally, a complete set of mappings can be given as {{?X → X i , ?Y → Y i , ?Z → Z i }}.

Now, variables appearing in the VIEW BY clause are referred to as object variable 7 and is denoted as Ov such that Ov ∈ V . In the current scenario Ov = {?X}. The remaining variables are referred to as attribute variables and are denoted as Av where Av ∈ V such that Ov ∪ Av = V and Ov ∩ Av = ∅.

Example 2.

An alternate query for the query in Listing 1.1 with the VIEW BY clause can be given as:

SELECT ?band ?instrument ?origin WHERE { ?band rdf:type dbpedia-owl:Band. ?band dbpprop:origin ?origin. ?band dbpedia-owl:bandMember ?member . ?member dbpedia-owl:instrument ?instrument . ?instrument dcterms:subject dbpedia8 :Category:String instruments.} VIEW BY ?band Here, V={?band, ?instrument, ?origin} then the evaluation of the SELECT query [[({?band, ?instrument, ?origin}, P )]] will generate the mappings shown in Table 1. Accordingly, dom(µ i ) = {?band, ?instrument, ?origin}. Here, µ 1 (?band) = RHCP , µ 1 (?instrument) = Banjo and µ 1 (?origin) = U S. In the current example, we have, Ov = {?band} because it appears in the VIEW BY clause and Av = {?instrument, ?origin}. Figure 1a shows the generated view when Ov = {?band} and in Figure 1b The results obtained by the query are in the form of set of tuples, which are then organized as a many-valued context. If Ov = {?X} then µ(?X) = {X i } i∈{1,...,k} , where X i denote the values obtained for the object variable and the corresponding mapping is given as {{?X → X i }}. Finally, G = µ(?X) = {X i } i∈{1,...,k} . Let Av = {?Y, ?Z} then M = Av and the attribute values W = {µ(?Y ), µ(?Z)} = {{Y i }, {Z i }} i∈{1,...,k} . The corresponding mapping for attribute variables are {{?Y → Y i , ?Z → Z i }} Consider an object value g i ∈ G and an attribute value w i ∈ W then we have (g i , "?Y ′′ , w i ) ∈ I iff ?X(g i ) = w i , i.e., the value of g i for attribute ?Y is w i , i ∈ {1, . . . , k} as we have k values for ?Y .

Obtaining Binary Context (G, M, I): Afterwards, a conceptual scaling used for binarizing the many-valued context, in the form of (G, M, I). Finally, we have

G = {X i } i∈{1,...,k} , M = {Y i } ∪ {Z i } where i ∈ {1, . . . , k} for object variable Ov = {?X}.
Example 3. In the example Ov = {band}, Av = {instrument, origin}. The answers obtained by this query are organized into a many-valued context as follows: the distinct values of the object variable ?band are kept as a set of objects, so G = {RHCP, Disturbed, . . . }, attribute variables provide M = {instrument, origin}, W 1 = {Banjo, BassGuitar, . . . } and W 2 = {U S, U K, F rance . . . } in a many-valued context. The obtained many-valued context is shown in Table 2. Following the above defined procedure a many-valued context is conceptually scaled to obtain a binary context shown in Table 3. The corresponding concept lattice is shown in Figure 1(a).

× × Disturbed × × Alcestr × × The Solution × × × Chrome Hoof × × Ensamble Gurrufio × × Table 3: Formal Context K DBpedia .

Building a Concept Lattice

Once the context is designed, the concept lattice can be built using an FCA algorithm. This step is straight forward as soon as the context is provided. In the current implementation we use AddIntent [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF] which is an incremental concept lattice construction algorithm. In case of large data iceberg lattices can be considered [START_REF] Stumme | Conceptual clustering with iceberg concept lattices[END_REF]. The use of VIEW BY clause activates the process of LBVA, which transforms the SPARQL query answers (tuples) to a formal context K answers through which a concept lattice is obtained which is referred to as a Lattice-Based View. A view on SPARQL query in section 1, i.e, a concept lattice corresponding to Table 3 is shown in Figure 1a. At the end of this step the concept lattice is built and the interpretation step can be considered.

Interpretation Operations over a Concept Lattice

Navigation Operation and Knowledge Discovery: The obtained concept lattice can be navigated for searching and accessing particular LOD elements. It is possible to drill down from general to specific concepts according to some constraints. For example, in order to search for bands in US playing Banjo, the concept lattice in Figure 1(a) is explored levelwise. First the broader concept contains all the bands from US, RHCP, The Solution, Disturbed. Then, the children concepts contain more specific concepts with the instruments Banjo and Bass Guitar. According to the initial constraint, the attribute concept of Banjo can be selected returning two objects namely RHCP, The Solution. Next, to check which instruments are played in music originating from US, another concept lattice can be explored, where objects correspond to instruments shown in Figure 1(b). The results in this case is the set of objects Bass Guitar, Banjo. FCA provides a powerful means for data analysis and knowledge discovery. Iceberg lattices provide the top most part of the lattice filtering out only general concepts. The concept lattice is still explored levelwise depending on a given threshold. Then, only concepts whose extent is sufficiently large are explored, i.e., the support of a concept corresponds to the cardinal of the extent. If further specific concepts are required the support threshold of the iceberg lattices can be lowered and the resulting concept lattice can be explored levelwise.

Another way of interpreting the data is provided by Duquenne-Guigues basis of implications which takes into account a minimal set of implications which represent all the association rules that can be generated for a given formal context. For example, DG-basis of implications according to the formal context in Table 3 state that all the bands which play Banjo are from US (rule: Banjo → US). Moreover, the rule Venezuela → Cuatro suggests that all the bands from Venezuela play Cuatro. This rule states that Cuatro is widely used in the folk music of Venezuela.

Experimentation

Several experiments were conducted on real datasets. These datasets include DBpedia, Yago [START_REF] Suchanek | Yago: A core of semantic knowledge[END_REF], which is a knowledge base automatically extracted from Wikipedia (infoboxes, categories), Wordnet and Geonames. The experiment was also tested on the biomedical data such as Sider9 and Drugbank10 . Sider keeps the information about the medicines along with their side effects. Drugbank keeps the detailed information about the drugs such as drug category and target proteins. These experiments provide qualitative and quantitative evaluation to our approach. These experiments are not discussed in the current paper due to lack of space. However, the software, a detailed technical report along with the visualization of the SPARQL query views can be accessed online11 .

Conclusion and Discussion

In LBVA, we introduce a classification framework for the set of tuples obtained as a result of SPARQL queries over LOD. We introduce a classification framework based on FCA for organizing a view, i.e., the set of tuples resulting from a SPARQL query. In this way, the view is organized as a concept lattice that can be navigated where information retrieval and knowledge discovery can be performed. For future work, we are interested in working with several object variable allowing to deal with more complex relations, with the help of Relational Concept Analysis (RCA). In addition, here only binary contexts are taken into account. It is possible to go beyond this limitation in using another variation of FCA which is the formalism of pattern structures.

  (a) Classes of Bands w.r.t. Musical Instruments and Countries, e.g., the concept on the top right corner with the attribute Cuatro contains all the bands which play Cuatro. (b) Classes of Musical Instruments w.r.t Bands and their Origin

Fig. 1 :

 1 Fig. 1: Concept Lattices w.r.t Musical Instrument's and Band's Perspective.

dbpedia 5 :

 5 RHCP 6 dbpedia:Banjo dbpedia:US dbpedia:Disturbed dbpedia:Bass Guitar dbpedia:US, dbpedia:The Solution dbpedia:Banjo dbpedia:Sweden.

Table 1 :

 1 , we have; Ov = {?instrument}. Generated Mappings for SPARQL Query Q

		?band	?instrument ?origin
	µ1 RHCP	Banjo	US
	µ2 Disturbed Bass Guitar US
	. . .	. . .	. . .	. . .
	2.2 Designing a Formal Context (G, M, W, I)

Table 2 :

 2 Many-Valued Context representing the answer tuple (Xi, Yi, Zi).

		Band	Instrument	Origin
		RHCP	Banjo	US
		Disturbed	Bass Guitar	US
		Alcest	Bass Guitar France
		The Solution	Banjo	Sweden, US
		Chrome Hoof	Cuatro	UK
		Ensamble Gurrufio Cuatro	Venezuela
	Band	Banjo Bass Guitar Cuatro US Sweden UK France Venezuela
	RHCP

http://project.carrot2.org/index.html

http://www.w3.org/TR/rdf-sparql-query/

In the rest of the paper we denote W as V to avoid overlap between the attribute values W in many-valued context.

http://dbpedia.org/resource/

The object here refers to the object in FCA.

http://dbpedia.org/resource/

http://sideeffects.embl.de/

http://www.drugbank.ca/

http://webloria.loria.fr/ ~alammehw/lbva/