=Paper=
{{Paper
|id=Vol-1766/om2016_Tpaper5
|storemode=property
|title=Rewriting SELECT SPARQL queries from 1:n complex correspondences
|pdfUrl=https://ceur-ws.org/Vol-1766/om2016_Tpaper5.pdf
|volume=Vol-1766
|authors=Élodie Thiéblin,Fabien Amarger,Ollivier Haemmerlé,Nathalie Hernandez,Cássia Trojahn
|dblpUrl=https://dblp.org/rec/conf/semweb/ThieblinAHHS16
}}
==Rewriting SELECT SPARQL queries from 1:n complex correspondences==
https://ceur-ws.org/Vol-1766/om2016_Tpaper5.pdf
Rewriting SELECT SPARQL queries from 1:n
complex correspondences
Élodie Thiéblin, Fabien Amarger, Ollivier Haemmerlé, Nathalie Hernandez,
Cassia Trojahn
IRIT & Université de Toulouse 2 Jean Jaurès, Toulouse, France
elodie.thieblin@gmail.com,{fabien.amarger, ollivier.haemmerle,
nathalie.hernandez,cassia.trojahn}@irit.fr
Abstract. This paper presents a mechanism for rewriting SPARQL
queries based on complex ontology correspondences. While the useful-
ness of simple correspondences, involving single entities from both source
and target ontologies, has long been recognized, query rewriting requires
more expressive links between ontology entities expressing the true rela-
tionships between them. Here, complex correspondences, in the format
1:n, between overlapping ontologies are exploited for rewriting SELECT
SPARQL queries, so that they can be expressed over different RDF data
sets in the Linked Open Data. Our approach has been evaluated using
two data sets, one from the agriculture domain and another based on a
reduced set involving the ontologies from the OAEI Conference track.
1 Introduction
A SPARQL query is intrinsically related to the ontological model that describes
the RDF source. To federate knowledge from different sources described by var-
ious ontologies, a SPARQL query must be adapted to each of the knowledge
bases. In order to use the Linked Open Data potential at its best, it is impor-
tant to bridge the gap of semantic heterogeneity between knowledge bases. On-
tology matching [5] is a solution for finding correspondences (i.e., an alignment)
between two ontologies. There are two types of correspondences : simple corre-
spondences and complex correspondences. A simple correspondence matches an
element from the first ontology to its semantically related ontological element
in the second ontology. Nevertheless, simple correspondences cannot cover every
case of use because of the model differences between ontological sources. Com-
plex correspondences palliate the lack of expressiveness of simple alignments.
They extend simple correspondences to correspondences between complex con-
structions of ontological entities of the two ontologies.
Simple correspondences can be easily used to transform SPARQL queries.
The usual approach (integrated in the Alignment API [3]) is to replace the IRI
of an ontological entity in the initial query by the IRI of its corresponding entity.
This approach considers that the correspondence stands for an equivalence rela-
tion. However by using simple correspondences, not all SPARQL queries can be
transformed. In this paper, an approach that exploits complex correspondences
for SPARQL query transformation is proposed. Even though there are only a few
systems able to automatically generate them, manually drawing correspondences
used in the proposed mechanism is likely a less fastidious task than manually
rewriting every SPARQL query for each new RDF-triple store.
Our approach is based on a set of rules for rewriting a subset of SELECT
SPARQL queries from complex correspondences involving an equivalence rela-
tion between ontology entities. These correspondences are expressed in EDOAL,
a language proposed for representing complex correspondences. The approach
has been validated on two data sets. The first one was built to meet the needs
of agriculture experts willing to find cross knowledge about agronomic taxons
between DBpedia and a dedicated knowledge base. The second data set was in-
spired from a subset of queries from the OAEI oa4qa1 task data set and could
be further developed in order to enrich this track.
The rest of the paper is structured as follows. §2 introduces ontology matching
and the EDOAL syntax. §3 discusses related work and §4 presents the rewriting
rules on which our approach is based. §5 discusses the validation of the approach
and §6 concludes the paper and presents perspectives for future work.
2 Ontology matching
Matching two ontologies is the process of generating an alignment A between
two ontologies O and O0 . A is directional, denoted AO→O0 :
Definition 1 (Alignment). An alignment AO→O0 is a set of correspondences
AO→O0 = {c1 , c2 , ..., cn }, where each ci is a triple heO , e0O , ri :
– if the correspondence ci is simple, both eO and eO0 stand for one and only
one entity (i.e., a class or a property) (1:1);
– if the correspondence is complex, at least one of eO or eO0 involves one or
more entities in a logical formulation. The correspondence is therefore (1:n),
(m:1) or (m:n), where eO refers to a subset of elements ∈ O, and eO0 refers
to a subset of elements ∈ O0 . The elements of eO , resp. eO0 form a logical
construction using the constructors of a formal language (First-Order Logic
or Description Logics);
– r is a relation, e.g., equivalence (≡), more general(w), more specific (v),
holding between eO and eO0 ;
The alignment AO→O0 is said complex if it contains at least one complex
correspondence. A correspondence ci , can also be noted eO r eO0 , as for the
complex correspondences in the following.
Chairman ≡ Demo_Chair t OC_Chair t P C_Chair t Session_Chair t
T utorial_Chair t W orkshop_Chair (1)
Accepted_P aper ≡ P aper u ∃hasDecision.Acceptance (2)
1
http://oaei.ontologymatching.org/2015/oa4qa/index.html
Example 1 expresses a complex correspondence between entities from Cmt2
and Ekaw3 ontologies. It states that the concept Chairman of Cmt is equiv-
alent to the union of the concepts Demo_Chair, OC_Chair, P C_Chair,
Session_Chair, T utorial_Chair and W orkshop_Chair of Ekaw. Example
2 expresses a complex correspondence, where the concept Accepted_P aper of
Ekaw is equivalent to the concept P aper of Cmt for which the domain of the ob-
ject property hasDecision is restricted to an individual of the type Acceptance.
For representing complex correspondences, the EDOAL language has been
proposed [6, 3]. It is fit to express simple and complex matching of cardinality
(1:1), (1:n), (n:1) and (n:m). The entities eO and eO0 are represented by expres-
sions (class, relation or property expressions) that can be an ID (or IRI), a con-
struction or a restriction. For a detailed description of EDOAL syntax the reader
can refer to [6]. We illustrate this syntax with the following examples of 1:n com-
plex correspondences given above. We use the prefixes ekaw:,
cmt:. Example 1 presents a class expression involving a class
construction built with a union of concepts, while Example 2 expresses a class
expression involving an attribute domain restriction.
Example 1 Example 2
1.0
Equivalence
1.0
Equivalence
Additional examples of correspondences expressed in EDOAL are presented
in examples 3 and 4. Example 3 shows a correspondence where the relation
writtenBy of Ekaw is equivalent to a relation expression constructed with the
inverse of the relation writeP aper in Cmt. Example 4, involving the ConfOf4
ontology (prefix confOf:), gives an example of a class ex-
pression constructed with an attribute value restriction stating that in Ekaw an
Early-Registered_P articipant is a P articipant for which the value of the data
property earlyRegistration is equal to true in ConfOf.
2
http://oaei.ontologymatching.org/2015/conference/data/cmt.owl
3
http://oaei.ontologymatching.org/2015/conference/data/ekaw.owl
4
http://oaei.ontologymatching.org/2015/conference/data/confof.owl
Example 3 Example 4
1.0
Equivalence
1.0
Equivalence
3 Related Work
A naive approach for rewriting SPARQL queries consists in replacing the IRI of
an entity of the initial query by the corresponding IRI in the alignment, using
simple correspondences. This approach is integrated in the Alignment API [3].
However, it does not take into account the specific kind of relation expressed
in the correspondence (e.g., generalisation or specialization). The approach in
Euzenat et al. [4] aims at writing CONSTRUCT SPARQL queries from complex
alignments. A new knowledge base expressed with the source ontology vocabu-
lary is populated with the instances of the target knowledge base. A rewriting
approach not limited to queries of type CONSTRUCT and that takes advantage of
complex (1:n) alignments has been proposed by Correndo et al. [1]. It applies
a declarative formalism for expressing alignments between RDF graphs. In [2],
a subset of EDOAL expressions are transformed into a set of rewriting rules.
The expressions involving the restrictions on concepts and properties and the
restrictions on property occurrences and values are not featured in the rewriting
rules. Makris et al. [9, 8] present the SPARQL-RW rewriting framework that ap-
plies a set of predefined rules for (complex) correspondences. They define a set
of correspondence types on which the rewriting process is based (i.e., Class Ex-
pression, Object Property Expression, Datatype Property, and Individual ). Zheng
et al. [14] propose a rewriting algorithm that serves the purpose of context (i.e,
units of measure) interchange for interoperability. Finally, Gillet et al. [7] pro-
pose an approach for rewriting query patterns that describe query families, using
complex alignments. In this paper, we propose a set of rules for automatically
rewriting SPARQL queries based on complex alignments. Differently from [4],
our approach rewrites SPARQL queries instead of writing them from a com-
plex alignment. Unlike [2], the proposed mechanism can handle restrictions on
concepts and relations. In comparison with the [9] approach, EDOAL is an al-
ternative to represent alignments in a more expressive (thus complete) way. For
instance, we propose occurrence and property datatype restrictions translation
rules. However, our approach is limited to (1:n) complex alignments and does
not handle initial SPARQL queries containing filters, unions, or other SPARQL
options. The approach is based on the assumption that the queries to be trans-
formed aim at retrieving new instances to meet a certain need. This is why only
T box elements are taken into account. [14] focuses on context correspondences
while our approach intends to translate all T box elements of a query. Finally,
the proposal of [7] rewrites query patterns while we are interested in rewriting
SPARQL queries, in a different level of abstraction. Although our approach relies
on complex correspondences, their generation is out of the scope of this paper.
The reader can refer to [13, 11] on the generation of complex correspondences
based on patterns, linguistic approaches [12], or query mining [10].
4 SPARQL queries reformulation approach
Our approach focuses on the reformulation of a subset of SELECT SPARQL
queries. We consider initial queries, which are to be rewritten, of the type:
QO = SELECT DIST IN CT ? ( V ar + | 0 ∗0 ) W HERE { TQO }
where V ar corresponds to the set of variables used as projection attributes and
TQO stands for the query pattern made of triples expressed using the source
ontology O. A triple t of TQO is composed of a subject s, a predicate p and an
object o. ∀t ∈ TQO , t = hs, p, oi. We only consider triples where s is a variable.
The purpose of our approach is to produce the set TQO0 that contains the
triples expressed according to entities of the ontology O0 , from TQO , by using the
complex alignment AO→O0 . The approach is limited to complex correspondences
(1:n) establishing an equivalence relation between entities of same nature. Such
correspondences involve EDOAL expressions, as follows :
hClassID, ClassID|ClassConstruction|ClassConstruction, ≡i
hRelationID, RelationID|RelationConstruction|RelationRestriction, ≡i
hP ropertyID, P ropertyID|P ropertyConstruction|P ropertyRestriction, ≡i
We also make the assumption that the alignment is complete and covers all
the correspondences required to transform the entities of TQO . We define rules
that take the set of triples TQO as input and generate a SPARQL query. Three
types of triples in TQO are considered : Class Object Triples, Predicate Triples
and Other Triples.
Algorithm 1 depicts the SPARQL query rewriting process. The rewrite-
ClassObject and rewritePredicate functions apply the rules described in the
following sections. These functions are recursive and can call each other. If a
triple is not a Class Object Triples or a Predicate Triples, it means that its sub-
ject s is a variable, its predicate is an object property or a data property for
which no correspondence is needed and its object is either a literal or a variable.
This kind of triple does not need any transformation and is directly added to
the final query. An example of such triple is ?s rdfs:label "a literal".
Algorithm 2 Rewriting mechanism process
new_query ← " "
for all triple t = hs, p, oi in query do
if t is a Class Object Triple then
new_query ← new_query + rewriteClassObject(s,p, oO0 )
else if t is a Predicate Triple then
new_query ← new_query + rewritePredicate(s,pO0 , o)
else
new_query ← new_query + t
end if
end for
return new_query
4.1 Class Object Triples
Class object triples, denoted TQClass
O
, are structured as
s is a variable
p is rdf:type
∀t ∈ TQClass
O
, t = hs, p, oO i , where
oO is a ClassID
∃ < oO , oO0 , ≡> ∈ AO→O0
A class triple is identified if its object oO is a ClassID and if there is a corre-
spondence linking oO to a class expression oO0 in AO→O0 . In the transformation
of a class triple t, its subject s and its predicate p remain the same. Only its ob-
ject oO is transformed according to its equivalent element oO0 in the alignment.
The transformation rules of the rewriteClassObject function depend on the
nature of the expression oO0 , as follows:
1. ClassID: The expression oO0 is aClassID. The transformed triple return by
the function is: s p IRI(oO0 ).
2. ClassConstruction: oO0 is a class construction between two or more class
expressions denoted by: e1O0 , e2O0 , enO0 . The transformation rule depends on
the construction operator.
(a) AND: transforming an intersection consists in rewriting each triplet hav-
ing as subject s, as predicate p and as object a distinct eiO0 expression:
rewriteClassObject(s, p, e1O0 ) + rewriteClassObject(s, p, e2O0 ) +
... + rewriteClassObject(s, p, enO0 )
(b) OR: transforming a union consists in using the SPARQL keyword “UNION”
between the rewriting of each triplet having as subject s, as predicate p
and as object a distinct eiO0 :5
{ + rewriteClassObject(s, p, e1O0 ) + } UNION { + rewriteClassOb-
ject(s, p, e2O0 ) + } +...+ UNION { + rewriteClassObject(s, p, enO0 ) +}
Table 1 shows an example of query rewriting based on the complex cor-
respondence of Example 1, involving a class construction with OR.
5
For sake of clarity and simplicity, we do not represent string delimiters.
Query for Cmt Transformed query for Ekaw
SELECT ?z WHERE {
{?z rdf:type ekaw:Demo_Chair. }
SELECT ?z WHERE { UNION {?z rdf:type ekaw:OC_Chair. }
?z rdf:type cmt:Chairman. UNION {?z rdf:type ekaw:PC_Chair. }
} UNION {?z rdf:type ekaw:Session_Chair. }
UNION {?z rdf:type ekaw:Tutorial_Chair. }
UNION {?z rdf:type ekaw:Workshop_Chair. }}
Table 1. Transformation of a class triple based on the correspondence of Example 1
between a classID and a class construction using the OR rule.
(c) NOT: finding the negation of a class expression consists in finding the set
of triples hs, p, vi, where v is an intermediate variable, and from which
the triples hs, p, e1O0 i are removed :
s p v . MINUS { + rewriteClassObject(s, p, e1O0 ) + }
3. ClassRestriction : Restriction on class expressions takes into account relation
or property expressions noted relation(oO0 ) or property(oO0 ). The transfor-
mation of the class triple depends on the nature of the restriction:
(a) TypeRestriction: this restriction applies to a property expression stated
in oO0 that limits the datatype of the property to a given type. The trans-
formation rule consists in using an intermediate variable v that becomes
the object of a new triple (that will keep on being rewritten according
to the nature of property(oO0 )). The type restriction is applied to v with
the use of a SPARQL FILTER and the datatype(v) function:
rewritePredicate(s, property(oO0 ), v) + FILTER (datatype(v) = type)
(b) DomainRestriction: this restriction limits the range of a relation expres-
sion stated in oO0 to a class expression range(oO0 ) also stated in oO0 .
The rewritePredicate function is called with the relation relation(oO0 )
between the subject s and an intermediate variable v. The rewrite-
ClassObject function is called to assert that v is an instance of the
range(oO0 ) class expression : rewritePredicate(s, relation(oO0 ), v) +
rewriteClassObject(v, rdf:type, range(oO0 ))
Table 2 presents a query transformation example based on the corre-
spondence of Example 2 involving this kind of restriction.
Query for Ekaw Transformed query for Cmt
SELECT ?z WHERE {
SELECT ?z WHERE {
?z rdf:type cmt:Paper.
?z rdf:type ekaw:Accepted_Paper.
?z cmt:hasDecision ?var_temp.
}
?var_temp rdf:type cmt:Acceptance. }
Table 2. Transformation of a class triple based on the correspondence on Example 2
between a classID and a class expression using the DomainRestriction rule.
(c) ValueRestriction: this restriction applies to a relation or property ex-
pression. The rewritePredicate function is called between the subject
s, the relation(oO0 ) or property(oO0 ) and an intermediate variable v.
To restrain the values that can be taken by v, a SPARQL “FILTER” is
used to compare v to a value given in the class expression. In the ac-
tual implementation, the stated value value can only be a literal or an
instance. The comparator cp used in the SPARQL FILTER is one of the
comparators provided by the EDOAL syntax : “=”, “>” and “<”.
rewritePredicate(s, relation/property(oO0 ), v) + FILTER (v cp value)
where cp ∈ {=, <, >}. For a “=” comparator, the resulting query is not
optimal in terms of performance. The rewriting rule exception could be :
rewritePredicate(s, relation/property(oO0 ), value) instead of using an
intermediate variable and a FILTER that applies to it. Table 3 presents
a transformation example based on the correspondence of Example 4.
Query for Ekaw Transformed query for ConfOf
SELECT ?z WHERE {
SELECT ?z WHERE {
?z rdf:type confOf:Participant.
?z rdf:type ekaw:Early-Registered_Participant.
?z confOf:earlyRegistration ?var_temp.
}
FILTER(?var_temp="true"ˆˆ xsd:boolean).}
Table 3. Transformation of a triple using the correspondence of Example 4 between a
class ID and a class expression using the ValueRestriction rule.
(d) AttributeOccurrenceRestriction: this restriction restrains the number of
occurrences of a relation or a property expression. In order to count
this number of occurrences, a SPARQL SELECT is imbricated to link
the subject s to the count countv of an intermediate variable v. The
value of countv is calculated thanks to the SPARQL COUNT function.
The graph pattern in the imbricated SELECT is represented by the call of
rewritePredicate(s, relation/property(oO0 ), v). After the imbricated
SELECT, a FILTER limits the value of countv to the restriction value
valrest with the comparator cp (both stated in the class restriction).
{{SELECT s (COUNT(v) AS countv ) WHERE
{ + rewritePredicate(s, relation/property(oO0 ), v) + }
GROUP BY s.}
FILTER (comptev cp valrest )} , where cp ∈ {=, <, >}
Here, the resulting query could be optimized for a relation or a prop-
erty occurring at least once (count > 0) . Instead of having an imbricated
SELECT, the rewriting rule could be: rewritePredicate(s, relation/property(oO0 ), v)
with v a temporary variable.
4.2 Predicate Triples
Predicate triples, denoted by TQPOredicate have the following structure :
s is a variable
p = a RelationId or PropertyId
O
∀t ∈ TQPOredicate t = hs, pO , oi , where
o is a variable, an instance or a literal
∃ < pO , pO0 , ≡>∈ AO→O0
In predicate triples, pO is either a RelationId or a PropertyId and pO0 is
respectively a relation expression or a property expression. A relation triple is
transformed according to the nature of the expression pO0 .
1. RelationId or PropertyId : the following triple is added to TQO0 : s IRI(pO0 ) o.
2. RelationConstruction or PropertyConstruction: pO0 is a construction be-
tween relation or property expressions designated by p1O0 , p2O0 , pnO0 . The
transformation of the relation triple depends on the operator of the con-
struction.
(a) AND: this construction can be between two or more expressions (relation
expressions resp. property expressions). The rewritePredicate function
is called as follows:
rewritePredicate(s, p1O0 , o) + rewritePredicate(s, p2O0 , o) + ...
+ rewritePredicate(s, pnO0 , o)
(b) OR: this construction can be between two or more expressions (relation
expressions resp. property expressions). A SPARQL UNION links the calls
to rewritePredicate:
{ + rewritePredicate(s, p1O0 , o) +} UNION { + rewritePredicate(s, p2O0 , o)
+ } + ... + UNION { + rewritePredicate(s, pnO0 , o) + }
(c) NOT: the negation of a relation is the subset of all relations minus this
relation. To represent all relations an intermediate variable v is intro-
duced. The negation will be done using a SPARQL MINUS:
s v o . MINUS { + rewritePredicate(s, p1O0 , o) + }
(d) COMPOSE: a relation composition is a relation chain. Intermediate vari-
ables v1 , v2 , etc. are introduced to complete the chain between the sub-
ject s and the object o. If the relation expression pO0 is a RelationExpres-
sion, all the expressions of the chain will be relation expressions. If pO0
is a PropertyExpression, all the expressions of the chain will be relation
expressions except the last one that will be a property expression. We
assume that a composition imbrication or the use of a negation inside a
composition is a modeling problem in the alignment itself.
rewritePredicate(s, p1O0 , v1 ) + rewritePredicate(v1 , p2O0 , v2 )
+ ... + rewritePredicate(vn−1 , pnO0 , o)
(e) INVERSE : this construction only applies to a RelationExpression. In-
verting a relation consists in switching its subject and its object in a
triple. rewritePredicate(o, p1O0 , s) Table 4 gives an example of a triple
transformation based on the correspondence of Example 3.
(f) REFLEXIVE : this construction only applies to a RelationExpression.
This operator is used to specify that a relation links its subject s to itself.
rewritePredicate (s, p1O0 , s)
(g) SYMMETRIC : this construction only applies to a RelationExpression.
This operator is used to specify that a relation is used both ways : it is
the intersection of a relation and its inverse.
rewritePredicate(s, p1O0 , o) + rewritePredicate(o, p1O0 , s)
3. RelationDomainRestriction or PropertyDomainRestriction: these restrictions
limit the domain of a relation or property to a class expression domain(p1O0 )
stated in the relation or property expression.
rewriteClassObject(s, rdf:type, domain(pO0 ))
4. RelationCoDomainRestriction: this restriction restrains the range of a Rela-
tionExpression to a class expression range(pO0 ).
rewriteClassObject(o, rdf:type, range(pO0 ))
5. PropertyTypeRestriction: this restriction limits the datatype of a property
to a given type type in the property expression O0 . A SPARQL FILTER with
the datatype(o) function is used. FILTER (datatype(o) = type)
Query for Ekaw Transformed query for Cmt
SELECT ?z WHERE { SELECT ?z WHERE{
?paper :writtenBy ?author. } ?author cmt:writePaper ?paper. }
Table 4. Transformed of a triple using the correspondence of Example 3 between a
relation ID and a relation construction with the INVERSE constructor.
5 Validation
As far as we know, there is no available data set consisting of two knowledge
bases, a complex and complete alignment between two ontologies and corre-
sponding SPARQL queries for both bases. In the context of the OAEI oa4qa6 , a
data set involving simple alignments is available. In order to fill this gap, we have
manually created two data sets, following the principle of the oa4qa task. The
validation of our mechanism checks that the translated query retrieves the same
results as the reference query. Although these data sets only contain a small
number of queries, it serves as a basis for a first validation of our approach.
Knowledge bases and SPARQL queries. The first data set was built
during a project aiming at collecting knowledge about plant taxonomy. To meet
this need, the knowledge bases Agronomic Taxon7 and DBpedia have been con-
sidered. The task consists of retrieving answers to the following queries:
– qa1: which are the taxa of type species ?
– qa2: which are the taxa having for higher taxonomic rank a family taxon ?
– qa3: which are the taxa of taxonomical rank kingdom ?
– qa4: which are the taxa of taxonomical rank order ?
– qa5: which are the taxa of taxonomical rank genus ?
In order to build this data set, reference SPARQL queries corresponding to the
natural language description above have been written manually for each knowl-
edge base. The same approach was followed to construct the second data set. It
aims at interrogating a subset of the OAEI 2015 ontologies about conference or-
ganization8 . Three ontologies of this data set were considered (Cmt, ConfOf and
Ekaw). We have defined the SPARQL queries answering the following queries :
– qb1: which are the reviewers of accepted papers ? (Ekaw to Cmt)
6
http://oaei.ontologymatching.org/2015/
7
http://ontology.irstea.fr/AgronomicTaxon
8
http://oaei.ontologymatching.org/2015/conference/index.html
– qb2: which are authors of long submissions ? (Ekaw to Cmt)
– qb3: which are the chairmen who have submitted a paper ? (Cmt to Ekaw)
– qc1: which are the early registered participants who authored a submitted
paper ? (Ekaw to ConfOf)
– qc2: which are the late registered participants who wrote a poster ?(Ekaw to
ConfOf)
The three ontologies were populated with instances meeting these needs. Si-
multaneously, the queries were transformed into SPARQL queries specifically
written for each of the knowledge bases.
Complex alignments. 10 complex correspondences (and 1 simple) have
been manually produced between Agronomic Taxon and DBpedia. 8 simple and
6 complex correspondences have been manually produced between the three
ontologies of the Conference data set. The alignments are available online9 .
Discussion. Our validation is based on the manual comparison of the set
of results returned from the automatically rewritten query with respect to the
results of the reference query. Even though the reference query and the rewrit-
ten one differ in terms of syntax, they retrieve the same set of instances. For
example, Table 5 shows the queries considered for the need qc1 described above.
The initial SPARQL query for Ekaw was transformed by using the complex cor-
respondences of Example 4 and the simple correspondence ekaw : authorOf ≡
conf Of : writes. As stated above, although the generated query is not syntac-
tically equivalent to the reference query for ConfOf, they retrieve the same set
of instances. The whole set of rewritten queries is available online10 .
Initial query for Ekaw (a) Reference query for ConfOf Generated query for ConfOf
SELECT ?person WHERE {
?person :writes ?paper.
SELECT ?person WHERE { SELECT ?person WHERE{
?paper a :Paper.
?person :authorOf ?paper. ?person
?person rdf:type :Participant.
?paper a :Paper. :earlyRegistration true.
?person :earlyRegistration
?person rdf:type ?person :writes ?papier.
?v_temp0.
:Early-Registered_Participant.} ?papier a :Paper.}
FILTER(?v_temp0 =
"true"ˆˆxsd:boolean).}
Table 5. Transformation of an initial query in comparison to its reference.
6 Conclusion and perspectives
In this paper, we have presented an approach to rewrite SELECT SPARQL
queries formulated for a particular ontology to interrogate a knowledge base
based on a second ontology using (1:n) complex correspondences. The proposed
approach has been validated on two data sets manually created. There are many
improvements to make to this mechanism. Indeed, the approach is limited to
9
https://www.irit.fr/recherches/MELODI/telechargements/alignements.zip
10
https://www.irit.fr/recherches/MELODI/telechargements/requetesgenerees.zip
formatted queries composed of triples whose subject is a variable. Instance align-
ments are not considered yet. We do not consider as well (n:m) correspondences.
Proposals on complex graph pattern recognition in SPARQL queries would be
interesting to take into account in order to address that matter. Another point
is that we do not distinguish the kind of relation of a correspondence (subsump-
tion and equivalence). Moreover, some EDOAL syntax of concepts have not been
implemented, such as functions on literal (string concatenation, arithmetic op-
erations, etc. that could be used in particular for value restrictions). Finally,
property value restrictions is another EDOAL expression that was not imple-
mented because it is more likely to be found in (n:m) correspondences. We plan
to address all these points in future work.
References
1. Correndo, G., Salvadores, M., Millard, I., Glaser, H., Shadbolt, N.: SPARQL Query
Rewriting for Implementing Data Integration over Linked Data. In: 1st Interna-
tional Workshop on Data Semantics (DataSem 2010) (March 2010)
2. Correndo, G., Shadbolt, N.: Translating expressive ontology mappings into rewrit-
ing rules to implement query rewriting. In: 6th Workshop on Ontology Matching
(2011)
3. David, J., Euzenat, J., Scharffe, F., Trojahn, C.: The Alignment API 4.0. Semantic
Web 2(1), 3–10 (2011)
4. Euzenat, J., Polleres, A., Scharffe, F.: Processing ontology alignments with sparql.
In: International Conference on Complex, Intelligent and Software Intensive Sys-
tems. pp. 913–917 (2008)
5. Euzenat, J., Shvaiko, P.: Ontology Matching. Springer-Verlag, Berlin, Heidelberg
(2007)
6. Euzenat, J., Scharffe, F., Zimmermann, A.: Expressive alignment language and
implementation. Tech. rep., INRIA (2007), http://hal.inria.fr/hal-00822892/
7. Gillet, P., Trojahn, C., Haemmerlé, O., Pradel, C.: Complex correspondences for
query patterns rewriting. In: 8th Workshop on Ontology Matching (2013)
8. Makris, K., Bikakis, N., Gioldasis, N., Christodoulakis, S.: SPARQL-RW: transpar-
ent query access over mapped RDF data sources. In: 15th International Conference
on Extending Database Technology. pp. 610–613. ACM (2012)
9. Makris, K., Gioldasis, N., Bikakis, N., Christodoulakis, S.: Ontology Mapping and
SPARQL Rewriting for Querying Federated RDF Data Sources. In: OTM Confed-
erated International Conferences. pp. 1108–1117 (2010)
10. Qin, H., Dou, D., LePendu, P.: Discovering executable semantic mappings between
ontologies. In: OTM International Conference. pp. 832–849 (2007)
11. Ritze, D., Meilicke, C., Sváb-Zamazal, O., Stuckenschmidt, H.: A pattern-based
ontology matching approach for detecting complex correspondences. In: 4th Work-
shop on Ontology Matching (2009)
12. Ritze, D., Völker, J., Meilicke, C., Sváb-Zamazal, O.: Linguistic analysis for com-
plex ontology matching. In: 5th Workshop on Ontology Matching (2010)
13. Scharffe, F., Fensel, D.: Correspondence patterns for ontology alignment. In:
Knowledge Engineering: Practice and Patterns, pp. 83–92. Springer (2008)
14. Zheng, X., Madnick, S.E., Li, X.: SPARQL Query Mediation over RDF Data
Sources with Disparate Contexts. In: WWW Workshop on Linked Data on the
Web (2012)