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 speci c patterns in query results.
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) [
This paper proposes a new approach based on Formal Concept Analysis
(FCA [
The intuition of classifying results obtained by SPARQL queries is inspired
by web clustering engines [
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 de nes LBVA and gives the overall architecture of the framework. Section 5 discusses some experiments conducted using LBVA. Finally, Section 6 concludes the paper. 2
In this section we introduce a motivating example focusing on why LOD should be queried and why the SPARQL query results need classi cation. 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 1 http://project.carrot2.org/index.html 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., hsubject; predicate; objecti, which is represented as node-and-arc-labeled directed graphs. SPARQL2 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.1.
Listing 1.1: SPARQL Query Museum 1 SELECT ?museum ? c o u n t r y ? a r t i s t WHERE f 2 ?museum r d f : t y p e dbpedia owl : Museum . 3 ?museum dbpedia owl : l o c a t i o n ? c i t y . 4 ? c i t y dbpedia owl : c o u n t r y ? c o u n t r y . 5 ? p a i n t i n g dbpedia owl : museum ?museum . 6 ? p a i n t i n g dbpprop : a r t i s t ? a r t i s t g 7 GROUP BY ? c o u n t r y ? a r t i s t 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: Pablo Picasso Musee d'Art Moderne France Leonardo Da Vinci Musee du Louvre France Raphael Museo del Prado Spain
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 rst 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 classi cation 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, rst the concept containing all the museums
displaying the work of Goya is obtained and then the speci c concept Goya and
UK is retrieved by drilling down. Finally, the answer is National Gallery.
2 http://www.w3.org/TR/rdf-sparql-query/
(a) Classes of Museums w.r.t Artists and
Countries, e.g., the concept on the top left corner
with the attribute France contains all the French
Museums. (VIEW BY ?museum)
(b) Classes of Artists w.r.t Museums and
Countries. (VIEW BY ?artist)
Formal Concept Analysis (FCA): FCA [
In order to restrict the number of concepts in some cases iceberg concept
lattices can be used [
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 Sm of an attribute m of a manyvalued context is a one-valued context (Gm; Mm; Im) with m(G) = Sm for m 2 M and then the new set of attributes is Ms = Sm2M Sm. During plain scaling the object set G remains unchanged, every many-valued attribute m is replaced by the scale attributes of scale Sm.
FCA also allows knowledge discovery using association rules.
DuquenneGuigues (DG) basis for implications [
In this paper, we propose an approach called Lattice Based View Access for classi cation 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 de ne views over RDF data by processing the set of tuples returned by the SPARQL query as answers.
SPARQL Queries with Classi cation Capabilities: The idea of introducing a View By clause is to provide classi cation 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 ?v1 ?v2 : : : ?vn WHERE f condition/pattern g VIEW BY ?vl. More formally, \view by(vl) : q( !v)" where !v is a vector of variables containing free variables called answer variables and vl 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(v1; v2; : : : ; vn) yields a set of tuples R = f(X1i ; X2i ; : : : ; Xni)g, where i = f1; : : : ; kg 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, v1 = artist is the object variable, v2 = museum and v3 = country are the attribute variables and Figure 1a shows the generated view. In Figure 1b, we have; v1 = artist is the object variable, v2 = museum and v3 = 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 vl be the object variable in !v = (v1; v2; : : : ; vn), Xli be the answers obtained for vl, then attribute variables will be v1; : : : ; vl 1; vl+1; : : : ; vn. The answers associated to attribute variables can be given as fX1i ; X2i ; : : : ; Xi ; l 1 Xli+1; : : : ; Xnig. Then, G = fXli; i = 1; : : : ; kg and M is the set of many valued attributes, given as M = fv1; v2; : : : ; vl 1; vl+1; : : : ; vng and W represents the attribute values, i.e., W = fX1i ; X2i ; : : : ; Xli 1; Xli+1; : : : ; Xnig. The occurrence of an object and an attribute together in R = f(X1i ; X2i ; : : : ; Xni)g 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 = fM useeduLouvre; M useodelP radog. The attribute variables artist,country provide the set of attributes M = fartist; countryg and the tuples related to the variables provide attribute values, w1 = fRaphael; LeonardoDaV incig and w2 = fF rance; Spain U Kg. The obtained many-valued context is shown in Table 1. The corresponding nominally scaled one-valued context is shown in Table 2.
Museum Musee du Louvre Musee d'Art Moderne Museo del Prado National Gallery
Artist Country fRaphael, Leonardo Da Vinci, Caravaggiog fFranceg
fPablo Picassog fFranceg fRaphael, Caravaggio, Francisco Goyag fSpaing fLeonardo Da Vinci, Caravaggio, Francisco Goyag fUKg
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 e cient implementation for building a concept lattice [
Interpretation Operations over a Lattice-Based Views: A formal context e ectively takes into account the relations by keeping the inherent structure of Museum Musee du Louvre Musee d'Art Moderne Museo del Prado National Gallery
Artist Country
Raphael Da Vinci Picasso Caravaggio Goya France Spain UK 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 speci c concepts or rolled up to nd 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 lter 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 speci c 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 speci c answer, the user can browse through lattice and obtain Museo Del Prado. 5 5.1
DBpedia is currently comprised of a huge amount of RDF triples in many
different languages which re ects 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 [
?movie rdf:type dbpedia-owl:Film . ?movie dbpprop:genre ?genre . ?movie dbpprop:country ?country .g VIEW BY ?movie
The obtained concept lattice contained 1395 concepts. Out of which 201 concepts on the rst 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 rst 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 nd movies which are made in collaboration with several countries. For example, The Scorpion King was made in collaboration with United States, Germany and Belgium. 5.2
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 rst 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 speci c 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 than DBpedia, which points towards the completion of YAGO. This fact is actually useful in nding 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 lm 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 online3.
In LBVA, we introduce a classi cation 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.