This paper presents a mechanism for rewriting SPARQL queries based on complex ontology correspondences. While the usefulness 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 relationships 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.
A SPARQL query is intrinsically related to the ontological model that describes
the RDF source. To federate knowledge from different sources described by
various 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
important to bridge the gap of semantic heterogeneity between knowledge bases.
Ontology matching [
Simple correspondences can be easily used to transform SPARQL queries.
The usual approach (integrated in the Alignment API [
Our approach is based on a set of rules for rewriting a subset of SELECT SPARQL queries from complex correspondences involving an equivalence relation 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 inspired 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
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 = fc1; c2; :::; cng, 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 2 O, and eO0 refers to a subset of elements 2 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 9hasDecision:Acceptance (2) 1http://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 equivalent 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 object property hasDecision is restricted to an individual of the type Acceptance.
For representing complex correspondences, the EDOAL language has been
proposed [
Example 1 <entity1>
<edoal:Class rdf:about="&cmt;Chairman"/> </entity1> <entity2> <edoal:Class> <edoal:or rdf:parseType="Collection"> <edoal:Class rdf:about="&ekaw;Demo_Chair"/> <edoal:Class rdf:about="&ekaw;OC_Chair"/> <edoal:Class rdf:about="&ekaw;PC_Chair"/> <edoal:Class rdf:about="&ekaw;Session_Chair"/> <edoal:Class rdf:about="&ekaw;Tutorial_Chair"/> <edoal:Class rdf:about="&ekaw;Workshop_Chair"/> </edoal:or> </entity2> <measure rdf:datatype="&xsd;float">1.0</measure> <relation>Equivalence</relation> Example 2 <entity1>
<edoal:Class rdf:about="&ekaw;Accepted_Paper"/> </entity1> <entity2> <edoal:Class> <edoal:and rdf:parseType="Collection"> <edoal:Class rdf:about="&cmt;Paper"/> <edoal:AttributeDomainRestriction> <edoal:onAttribute>
<edoal:Relation rdf:about="&cmt;hasDecision"/> </edoal:onAttribute> <edoal:class>
<edoal:Class rdf:about="&cmt;Acceptance"/> </edoal:class> </edoal:AttributeDomainRestriction> </edoal:and> </edoal:Class> </entity2> <measure rdf:datatype="&xsd;float">1.0</measure> <relation>Equivalence</relation> 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:<http://confOf#>), gives an example of a class expression 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.
2http://oaei.ontologymatching.org/2015/conference/data/cmt.owl 3http://oaei.ontologymatching.org/2015/conference/data/ekaw.owl 4http://oaei.ontologymatching.org/2015/conference/data/confof.owl Example 3 Example 4 <entity1>
<edoal:Relation rdf:about="&ekaw;writtenBy"/> </entity1> <entity2> <edoal:Relation> <edoal:inverse>
<edoal:Relation rdf:about="&cmt;writePaper"/> </edoal:inverse> </edoal:Relation> </entity2> <measure rdf:datatype="&xsd;float">1.0</measure> <relation>Equivalence</relation> <entity1>
<edoal:Class rdf:about="&ekaw;Early-Registered_Participant"/> </entity1> <entity2> <edoal:Class> <edoal:and rdf:parseType="Collection"> <edoal:Class rdf:about="&confOf;Participant"/> <edoal:AttributeValueRestriction> <edoal:onAttribute>
<edoal:Property rdf:about="&confOf;earlyRegistration"/> <edoal:onAttribute> <edoal:comparator rdf:resource="&edoal;equals"/> <edoal:value>
<edoal:Literal edoal:type="xsd;boolean" edoal:string="true"/> </edoal:value> </edoal:AttributeValueRestriction> </edoal:and> </edoal:Class> </entity2> <measure rdf:datatype="&xsd;float">1.0</measure> <relation>Equivalence</relation> 3
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 [
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 + j 0 0 ) W HERE f TQO g 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. 8t 2 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; ClassIDjClassConstructionjClassConstruction; i hRelationID; RelationIDjRelationConstructionjRelationRestriction; i hP ropertyID; P ropertyIDjP ropertyConstructionjP 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 rewriteClassObject 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 subject 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 TQCOlass, are structured as 8t 2 TQCOlass; t = hs; p; oOi , where 8 s is a variable > >>< p is rdf:type > oO is a ClassID > > : 9 < oO; oO0 ; >
A class triple is identified if its object oO is a ClassID and if there is a correspondence 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 object 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 having 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 { + rewriteClassObject(s; p; e2O0 ) + } +...+ UNION { + rewriteClassObject(s; p; enO0 ) +} Table 1 shows an example of query rewriting based on the complex correspondence of Example 1, involving a class construction with OR. 5For sake of clarity and simplicity, we do not represent string delimiters.
(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 : 3. ClassRestrsictpionv :.ReMsItNrUicStio{n +onrcelwasrsietxepCrleassssioOnbstjaekcets(si;npto;ea1Oc0c)ou+nt}relation or property expressions noted relation(oO0 ) or property(oO0 ). The transformation 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 transformation 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 expression 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 rewriteClassObject 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 correspondence of Example 2 involving this kind of restriction.
Query for Ekaw Transformed query for Cmt ?S}zELErCdTf:?tyzpeWHeEkRaEw:{Accepted_Paper. ???SzzvEaLrErc_CdmtTfte::mth?pyazpseDrWedHccfEmi:RtstE:iyopP{neape?crvm.atr:_Atcecmepp.tance. } 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 expression. 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 actual 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 2 f=; <; >g. 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.
SELECT ?z WHERE { ?z rdf:type ekaw:Early-Registered_Participant. } Predicate triples, denoted by TQPOredicate have the following structure : 8t 2 TQPOredicatet = hs; pO; oi , where 8 s is a variable > >>< pO = a RelationId or PropertyId > o is a variable, an instance or a literal > > : 9 < pO; pO0 ; >2 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 between relation or property expressions designated by p1O0 , p2O0 , pnO0 . The transformation of the relation triple depends on the operator of the construction. (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 introduced. 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 variables v1, v2, etc. are introduced to complete the chain between the subject s and the object o. If the relation expression pO0 is a RelationExpression, 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. Inverting 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 RelationExpression 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) 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 corresponding 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 considered. 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 knowledge 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 organization8. 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) 6http://oaei.ontologymatching.org/2015/ 7http://ontology.irstea.fr/AgronomicTaxon 8http://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. Simultaneously, 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 rewritten 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 correspondences of Example 4 and the simple correspondence ekaw : authorOf conf Of : writes. As stated above, although the generated query is not syntactically equivalent to the reference query for ConfOf, they retrieve the same set of instances. The whole set of rewritten queries is available online10.
SELECT ?person WHERE { SELECT ?person WHERE{ ?person :authorOf ?paper. ?person ?paper a :Paper. :earlyRegistration true. ?person rdf:type ?person :writes ?papier. :Early-Registered_Participant.} ?papier a :Paper.}
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 9https://www.irit.fr/recherches/MELODI/telechargements/alignements.zip 10https://www.irit.fr/recherches/MELODI/telechargements/requetesgenerees.zip formatted queries composed of triples whose subject is a variable. Instance alignments 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 (subsumption and equivalence). Moreover, some EDOAL syntax of concepts have not been implemented, such as functions on literal (string concatenation, arithmetic operations, etc. that could be used in particular for value restrictions). Finally, property value restrictions is another EDOAL expression that was not implemented because it is more likely to be found in (n:m) correspondences. We plan to address all these points in future work.