=Paper=
{{Paper
|id=None
|storemode=property
|title=An FCA Framework for Knowledge Discovery in SPARQL Query Answers
|pdfUrl=https://ceur-ws.org/Vol-1035/iswc2013_poster_5.pdf
|volume=Vol-1035
|dblpUrl=https://dblp.org/rec/conf/semweb/ChekolN13
}}
==An FCA Framework for Knowledge Discovery in SPARQL Query Answers==
https://ceur-ws.org/Vol-1035/iswc2013_poster_5.pdf
An FCA Framework for Knowledge Discovery in
SPARQL Query Answers
Melisachew Wudage Chekol and Amedeo Napoli
LORIA (INRIA, CNRS, and Université de Lorraine), France
{melisachew.chekol,amedeo.napoli}@inria.fr
Abstract. Formal concept analysis (FCA) is used for knowledge dis-
covery within data. In FCA, concept lattices are very good tools for
classification and organization of data. Hence, they can also be used to
visualize the answers of a SPARQL query instead of the usual answer
formats such as: RDF/XML, JSON, CSV, and HTML. Consequently, in
this work, we apply FCA to reveal and visualize hidden relations within
SPARQL query answers by means of concept lattices.
1 Introduction
Recently, the amount of semantically rich data available on the Web has grown
considerably. Since the conception of linked data publishing principles, over 295
linked (open) datasets (LOD) have been produced1 . A reasonable number of
these datasets provide endpoints for accessing (querying) their contents. Query-
ing is mainly done through the W3C recommended query language SPARQL.
The answers of SPARQL queries have often the following formats: RDF/XML,
JSON, CSV, text, TSV, Java Script, XML, Spreadsheet, Ntriples, and HTML. It
might be interesting to analyse, mine, and then visualize hidden relations within
the answers. These tasks can be carried out using Formal Concept Analysis
(FCA).
FCA is used for knowledge discovery within data represented by means of
objects and their attributes [3]. Concept lattices can reveal hidden relations
within data and can be used for organizing, classifying, and even mining data.
A survey of the benefits of FCA to semantic web (SW) and vice versa has been
proposed in [6] (in particular ontology completion [1]). Additionally, studies in
[2] and [4] are based on FCA for managing SW data. The former provides an
entry point to linked data using questions in a way that can be navigated. It
gives a transformation of an RDF graph into a formal context where the subject
of an RDF triple becomes the object, a composition of the predicate and object
of the triple becomes an attribute. The latter obliges the user to specify variables
corresponding to objects and attributes of a context. These variables are used
to create a SPARQL query which is used to extract content from linked data
in order to build the formal context. Following this line, we propose a way to
1
http://linkeddata.org/
2
1 3
SELECT
Keyword Object and Attribute
Query
CONSTRUCT Query CONSTRUCT Query SELECT Query
Linked data
Formal Context Concept Lattice
Fig. 1: Architecture of SPARQL answers organization.
organize Semantic Web data, and more precisely, the organization of SPARQL
query answers by means of concept lattices. As a result, the user is able to
visualize, navigate and classify the answers w.r.t. their context. For that, we
propose the architecture depicted in Figure 1, based on three components which
are discussed below:
1. Keyword search: In this component, a keyword (for instance, “14 juillet”) is
used to search (to find information regarding this word) a specified dataset.
To do so, a URI produced from the keyword is sent to the dataset to check
its existence. When this is the case, a CONSTRUCT query containing the
keyword is directed to the endpoint of the dataset. The answers are collected
and organized to create a formal context as explained in the next section.
2. SELECT Query: This component builds a formal context out of the answers
of a SPARQL query. SPARQL queries are converted into CONSTRUCT
queries to form RDF graphs from the answers. Again, this will be illustrated
in the next section.
3. Variables corresponding to objects and attributes of a formal context: This
component enables the user to precisely specify the objects and attributes
of the formal context. Out of which a SPARQL query is formed and sent
to a chosen SPARQL endpoint. The answers of the query are collected to
build a formal context. From that, a concept lattice is constructed. This is
the approach considered by the authors in [4]. An example is proposed in
the next section.
In each case, the objective is to build a formal context and then to build the
associated concept lattice.
2 Proposal
A formal context represents data using objects and their attributes. Formally, it
is a triple K = (G, M, I) where G is a set of objects, M is a set of attributes,
and I ⊆ G × M is a binary relation. A derivation operator (0 ) is used to compute
formal concepts of a context. Given a set of objects A, a derivation operator 0
computes the maximal set of attributes shared by objects in A and is denoted
by A0 (this is done dually with set of attributes B). A formal concept is a pair
(A, B) where A0 = B and B 0 = A. A set of formal concepts ordered with the set
inclusion relation form a concept lattice [3].
Definition 1 (RDF as a Formal Context). Given an RDF graph G and a
transformation function σ, a formal context is obtained from G as follows:
C
– If ho1 , rdf : type, Ci ∈ G, then σ(ho1 , rdf : type, Ci) =
o1 x
∃R.> ∃R− .>
– If ho1 , R, o2 i ∈ G, then σ(ho1 , R, o2 i) = o1 x
o2 x
We consider a core fragment of RDFS called ρdf [5] which contains the min-
imal vocabulary, ρdf = {sp,sc,type,dom,range}, where sp denotes the
subproperty relation, sc is subclass, and dom stands for domain. This fragment
was proven to be minimal and well-behaved in [5]. Its semantics corresponds to
that of full RDFS. Triples containing schema information are transformed as:
1. If hC1 , rdfs : subClassOf, C2 i ∈ G, then σ(hC1 , rdfs : subClassOf, C2 i) =
∀o ∈ G. (o, C1 ) ∈ I ⇒ (o, C2 ) ∈ I.
2. If hR1 , rdfs : subPropertyOf, R2 i ∈ G, then σ(hR1 , rdfs : subPropertyOf, R2 i)
= ∀o1 , o2 ∈ G. (o1 , ∃R1 .>) ∈ I ⇒ (o1 , ∃R2 .>) ∈ I.
3. If hR, rdfs : domain, Ci ∈ G, then σ(hR, rdfs : domain, Ci) = ∀o1 ∈ G.
(o1 , ∃R.>) ∈ I ⇒ (o1 , C) ∈ I.
4. If hR, rdfs : range, Ci ∈ G, then σ(hR, rdfs : range, Ci) = ∀o2 ∈ G.
(o1 , ∃R− .>) ∈ I ⇒ (o2 , C) ∈ I.
The users above are able to build a formal context from an RDF graph or a set
of SPARQL query answers. Then, there are several algorithms that can compute
the concept lattice associated with a formal context and that can be used in our
framework.
Example: consider a SPARQL query that selects film titles (as objects of the
formal context) and genres (as attributes) from DBpedia to populate a formal
context. Consequently, this formal context is shown in Figure 2.
A possible concept lattice obtained from the formal context associated with
the query answers is depicted in Figure 3. Now we have a classification of the
results of the query w.r.t. a given topic or constraint. Additionally, this is exactly
the same thing as if we were querying the Web with Google and here we have a
classification of the answers w.r.t. a user constraints.
3 Conclusion
SPARQL query answers are provided in different formats (RDF/XML, CSV,
JSON, TTL, and others), which do not reveal hidden semantics in the answers.
Fig. 2: A part of the formal context associated with the query.
Fig. 3: Concept lattice of DBpedia movies and genres.
Concept lattices are useful in this regard. In this work, we used concept lattices
to hierarchically organize and analyse the content of query answers.
This is an ongoing work and we are currently implementing the procedure.
We should investigate how well it scales, given the size of SPARQL query answers
over linked data. Overall, this work shows some of the benefits of FCA that can
be provided to the semantic web.
References
1. Baader, F., Ganter, B., Sertkaya, B., Sattler, U.: Completing description logic knowl-
edge bases using formal concept analysis. In: Proc. of IJCAI. vol. 7, pp. 230–235
(2007)
2. d’Aquin, M., Motta, E.: Extracting relevant questions to an RDF dataset using
formal concept analysis. In: Proceedings of the sixth international conference on
Knowledge capture. pp. 121–128. ACM (2011)
3. Ganter, B., Wille, R.: Formal Concept Analysis. Springer, Berlin (1999)
4. Kirchberg, M., Leonardi, E., Tan, Y.S., Link, S., Ko, R.K., Lee, B.S.: Formal concept
discovery in semantic web data. In: ICFCA. pp. 164–179. Springer-Verlag (2012)
5. Muñoz, S., Pérez, J., Gutierrez, C.: Minimal deductive systems for RDF. In: The
Semantic Web: Research and Applications, pp. 53–67. Springer (2007)
6. Sertkaya, B.: A survey on how description logic ontologies benefit from FCA. In:
CLA. vol. 672, pp. 2–21 (2010)