The e ciency of SPARQL query evaluation against Linked Open Data may bene t from schema-based indexing. However, many data items come with incomplete schema information or lack schema descriptions entirely. In this position paper, we outline an approach to an indexing of linked data graphs based on schemata induced through Formal Concept Analysis. We show how to map queries onto RDF graphs based on such derived schema information. We sketch next steps for realizing and optimizing the suggested approach.
The ease of consuming Linked Open Data (LOD) depends on the availability of schema information. This holds for tasks such as browsing, where a user may not know the structure of the data found in a dataset, or querying, where schema information could be used for query optimization. In the LOD setting a query can be evaluated against the original LOD datasets through query federation or by evaluating it centrally against a LOD crawl. In both scenarios, the e ciency of query evaluation may be improved by identifying those datasets schematically matching the query { maybe partially { while leaving out others.
In the LOD cloud schema information is sparse, as many data items come
with incomplete schema information or lack schema descriptions entirely.
Methods for schema induction and ontology learning have been studied to remedy
this problem ([
To our knowledge, FCA has not been used for constructing indices, that
allow a schema-oriented query-to-graph mapping. Particularly, we are not aware
of previous work on mapping queries to formal contexts. We expect that FCA
will bene t this kind of indexing through the formally sound construction of
schemata that are free of external heuristics and concise at the same time. In
this paper, we outline an approach for such a schema index and point to future
work on an implementation.
For our approach to schema indexing, we propose a property-based schema
induction using FCA. Property-based type clustering is discussed in literature
as a remedy for the schema sparsity in LOD datasets. The feasibility of such
approaches has been analyzed in [
Schema induction, the learning of schema information from data, is a way to
handle schema sparsity. [
FCA has been applied to problems related to ontology learning. In [
We combine the induction of schema with building and providing an index
for query-to-graph mapping. An index for subgraph querying is presented in
[
In the following we give a short introduction to Formal Concept Analysis (FCA), a method for conceptual knowledge discovery and representation, as well as the basics of RDF and SPARQL.
We lend the following de nitions 1, 2, 3 from [
A formal concept is a pair (A; B) with A0 = B and B0 = A. A is the extent,
B is the intent of the concept. As in [
Formal concepts fall naturally into a hierarchy, called a concept lattice, by a subconcept-superconcept-relation de ned via the subset relations over G and M , respectively.
De nition 3 ( ). For two concepts (A1; B1), (A2; B2) [
RDF Datasources of the LOD cloud contain RDF1 data. For now, we abstract from the possibility of blank nodes in RDF data.
De nition 4 (RDF Graph). Given the set of RDF resource identi ers U and
the set of literals L and having the set of RDF terms T := U [ L: An RDF graph
is a set of RDF triples D f< s; p; o > js 2 U; p 2 U; o 2 T g. We further de ne
the set of all known RDF graphs D := fDjD is a known graphg.
SPARQL A language for formulating graph oriented queries against RDF
datasets is SPARQL2. For this paper, we will focus on Basic Graph Patterns
that are used for formalizing graph pattern matching and, thus, are
fundamental to SPARQL(cf. [
De nition 5 (Basic Graph Pattern). Given a set V of variable names, a Triple Pattern tp is a triple (s; p; o) 2 (U [V ) (U [V ) (T [V ). A Basic Graph Pattern (BGP) of a query q is a set containing a number of Triple Patterns. We abbreviate the set of all queries only containing a single BGP as BGP .
With this restriction to single-BGP queries, we de ne the solution to a query
q through matching its BGP against the RDF graph D as q(D) (cf. [
An example for a BGP and a possible solution is given in g. 1 b), c). 4
In a query federation system a central query processor accepts and processes queries by dispatching (parts of) the queries to datasets (i.e., computing nodes serving them). In the case of LOD these datasets are graphs. The schema index maps queries onto minimal sets of graphs required for evaluating the given 1 Resource Description Framework; http://www.w3.org/TR/rdf-concepts/ 2 http://www.w3.org/TR/sparql11-overview/ (a) album title ex:abbey:road "Abbey Road" ex:quadrophenia "Quadrophenia" ...
...
(c) queries. The optimal schema index minimizes the subset of all known RDF graphs to be used for returning the complete solution of a query q: Di(q) = argminDj D^q(Dj)=q(D)jDj j: (1)
The improvement of e ciency of query evaluation then depends on the number of graphs left out of Di(q). Judging a graph to be relevant for query evaluation may be based on a schematic match of a query and the graph.
In our approach the matching will be informed by an underlying lattice of property type clusters induced from the graph data via FCA. With our approach, the schema index constructs and maintains a schema lattice covering every graph encountered. We build this lattice by applying FCA on a formal context extracted from an RDF graph.
De nition 6 (Resource-Feature Map). We de ne a feature domain F as the set of all known predicates p encountered in D. A resource-feature map f : D U ! 2F assigns an RDF resource r the set of describing features found in a graph: f (D; r) = fp 2 F j9o 2 T :< r; p; o >2 Dg.
Example 1. f (gex; ex:quadrophenia) = fex:title; ex:tracksg There are other possible manifestations of such a resource-feature map. For example, one could (also) map the types assigned to resources through rdf:type. De nition 7 (Schema Lattice). We de ne a graph-covering formal context K := (U; F; If ) with the set of resources U , the feature domain F and If := f(r; p)j9D 2 D; 9r 2 U : p 2 f (D; r)g. The schema lattice LS = (L(U; F; If ); ) is the lattice constructed from K via FCA.
While extracting features given in the graphs, the schema index will also store the set of graphs contributing individual features to the subsequent lattice construction.
De nition 8 (Feature-contributing Graph). For an RDF resource r and a feature p 2 F , we de ne a set of feature-contributing graphs as (r; p) = fDjp 2 f (D; r)g. For the features of an intent B, we de ne the set of contributing graphs as 0(B) = fDj9p 2 B; 9r 2 U : D 2 (r; p)g.
We conceive the schema index as a pair (LS ; ) of the schema lattice LS and a function mapping queries to indexed graphs. In order to look up graphs that a query should be evaluated against, the schema index then derives the queries type information through the Query-Type Map function: De nition 9 (Query-Type Map). The Query-Type Map BGP ! 2F that maps a query q to a set of intents (q). is a function :
For a query q the schema index returns the set of schematically appropriate graphs as follows: (q) = fDjD 2 0(B) for some B 2 (q)g:
For our running example (cf. g. 1), the graph gex would be returned for the BGP, as here fex:title, ex:tracksg constitutes an intent re ected in the query. 5
In this position paper, we sketch the idea of a schema index for a query-to-graph
mapping. For constructing the index we aim at an automatic schema induction
process through FCA. We hypothesize that FCA is a good method for this use.
One, it is independent of external factors, such as expert involvement as in [
Our proposition is that the schema index returns the graphs necessary for a complete query evaluation: q( (q)) = q(D) (for every query q) (2) However, (q) may return graphs that might be disregarded for evaluating BGP. Hence, the proposed schema index is not necessarily optimal. For a future implementation we plan to approximate the optimal case (cf. (1)). This must only be done to a degree that is sensible, since potential savings in execution time are being countered by costs for building and looking up the index.
Towards a realization of the proposed schema index, we expect to face questions such as for the size of formal contexts as given through the feature domains of a graph. Next steps for our research will also involve empirical analysis of runtime behaviour and scalability of FCA in the LOD use scenario. We have indications that in spite of exponential worst-case complexity, the property-based clustering of data items may lead to empirically acceptable runtime behaviour. A further question in this context is how to e ciently update existing lattices, when, e.g., encountering further features of an object while still ingesting a graph in a stream-based fashion. For such a scenario, we will also look into what lattice construction algorithm to choose. Finally, we plan to address the problems of reducing the size of formal contexts and lattices through appropriate data preparation and cleansing lattices of "noisy" concepts.