Despite the fact that SPARQL is the standard de facto language for querying RDF data, its complexity may restrict its use at a large scale, specially for nonexpert RDF users. Translating natural language queries into SPARQL ones is the object of researches in both Natural Language Processing and Semantic Web fields. Within the SWIP system [11], users express queries in natural language sentences and pre-written query patterns are instantiated with respect to a syntactic analysis of the initial query. Several possible interpretations of the queries are shown to the user which selects the query he/she is interested in. Unlike other proposals, such as the one in [5,4], where user queries are limited to keywords, or in [16], where users can express their queries using a visual query language, the originality of SWIP is related to the use of query patterns.
The main principle behind query patterns states that, in real applications, the submitted queries are variations of few typical query families (i.e., the family of queries asking for the actors playing in movies or the queries asking for the members of a musical band, or the albums of a musical artist). On the one hand, the use of patterns avoids exploring the whole ontology to link the semantic entities identified from the keywords since the potential relations are already expressed in the patterns. The process thus benefits from the pre-established families of frequently expressed queries for which real information needs exist.
A query pattern can also be seen as the projection of a subgraph of the underlying knowledge base, used as a mediator for the translation between the query expressed in natural language and the corresponding SPARQL query. On the other hand, one of the main limitations of the query pattern-based approach is that reusing patterns across different data sources can be done in a very limited extent. For each data source to be queried, the corresponding query patterns have to be (manually) built. Rewriting query patterns based on a vocabulary to query patterns based on another vocabulary is a task that can be carried out with the help of ontology alignments.
This paper discusses the use of complex correspondences for automatic query patterns rewriting. While the usefulness of simple correspondences has long been recognised, query rewriting requires more expressive links between ontology entities expressing the true relationships between them. At a lower level of abstraction, ontology alignments have been used to support the task of SPARQL query rewriting [2,9,8]. However, query patterns and SPARQL refer to different levels of expressivity in their representations, where query patterns are articulated as a set of subpatterns and rely solely on the T Box of ontologies. Hence, we experiment ontology matching approaches in order to find complex correspondences between two ontologies describing two different data collections. From the complex alignments and source query patterns, we rewrite these patterns in order to be able to query the data collection described using the target ontology. Experiments have been carried out on an ontology on the music domain and DBpedia ontology. As a main outcoming, we have a set of manually validated complex correspondences, from which query patterns can be reused across the data sets described using those ontologies.
The rest of the paper is organised as follows. First, we introduce complex correspondences and query patterns ( §2). Then, we present the approach for query pattern rewriting that is based on the use of complex correspondences ( §3). Next, the experiments are discussed ( §4). Finally, we discuss related work ( §5) and conclude the paper ( §6).
Matching two ontologies is the process of generating an alignment between them [6]. An alignment A is directional and refers to a source ontology O and a target ontology O , denoted A O→O : Definition 1 (Alignment). An alignment A O→O between two ontologies O and O is a set of correspondences A O→O = {c 1 , c 2 , ..., c n }, where each c i is a triple e i , e i , r , where:
whether the correspondence is simple, then it relates one and only one entity (i.e., a class or a property) e i of O to one and only one entity e i of O (1:1);
or the correspondence is complex, and it involves one or more entities in a logical formulation (1:n,m:1,m:n), where e i refers to a subset of elements ∈ O, and e i refers to a subset of elements ∈ O , and these elements are related using the constructors of a formal language (First-Order Logic or Description Logics); r is a relation, e.g., equivalence (≡), more general( ), more specific ( ),
holding between e i and e i ; additionally, a value n (typically in [0,1]) is assigned to c i indicating the degree of confidence that the relation r holds between the e and e .
The correspondence e i , e i , r is unique in A O→O . On the other hand, e i or e i may be present in more than one correspondence c i . The alignment A O→O is said complex if it contains at least one complex correspondence. In the rest of this paper, a correspondence c i , which is a triple e i , e i , r (suffix notation), will be noted e i r e i . For example, F ilm W ork is a simple correspondence and asserts that F ilm in O is more specific than W ork in O . On the other hand, we can have the following two complex correspondences :
(1) asserts that a Short F ilm in O is equivalent to a F ilm in O whose duration is less than 59 minutes, and (2) asserts that a Biopic (or biographical film) in O is equivalent to a F ilm in O whose the topic is about a famous person. We can either use First-Order Logic (FOL) or the constructors of Description Logics (DL) for expressing the complex correspondences. In FOL, a class corresponds to a unary predicate with one variable, a property to a binary predicate with two variables, and an instance to a constant. In DL, a class corresponds to a (atomic) concept, a property to a role, and an instance to an individual. We can equally transpose logical statements from DL to FOL, and conversely, as long as the DL fragment is always respected. In particular, we take advantage of the expressivity allowed by SHOIN , describing the following DL operators: ¬C (negation of concepts), C C (intersection or conjunction of concepts), C C (union or disjunction of concepts), ∃R.C (existential restriction), ∀R.C (universal restriction), ≤ nR (at most restriction), ≥ nR (at least restriction). For instance, the formula (1) becomes (3) and the formula (2) becomes (4) :
In a (complex) correspondence formula expressed in FOL, a variable may occur in several entities in left and right operands. Intuitively, two classes referring to the same single variable are bound and are first connected by a simple correspondence (with a subsumption relation, otherwise there is no need for an additional complex correspondence to characterise the entities involved). For instance, the formulas (1) and ( 2) are consistent only if Court metrage F ilm and Biopic F ilm, respectively. The use of DL in (4) requires to explicitly assert the simple correspondence Biopic F ilm first, as we do not know if Biopic is a specialisation or rather a generalisation of F ilm or Celebrity otherwise.
A pattern p O targetting an ontology O is composed of an RDF graph which is the prototype of a relevant family of queries. A pattern can be composed of several subpatterns sp i , such as p O = {sp 1 , sp 2 , ..., sp n }. Subpatterns are assigned minimal and maximal cardinalities, making these subgraphs optional or repeatable when generating the final SPARQL query. Formally, a query pattern can be defined as follows [12]:
Definition 2 (Query pattern). Let G be a graph and v a vertex of the graph, we denote by G\v the graph deprived of the vertex v and all the arcs incident to the vertex. A query pattern p is a triple (G, Q, SP ) such as :
-G is a RDF connected graph that describes the general structure of the pattern and represents a family of requests; -Q is a subset of elements in G, called qualifier elements; these are typical of the pattern and will be taken into account during the association of the user request to the pattern in question. A qualifier element is either a vertex (class or data type), or an arc (object or data property) in G; -SP is the set of subpatterns sp in p such that ∀sp = (SG, v, card min , card max ) ∈ SP , we have:
• SG is a subgraph of G and v is a vertex of SG (and thus of G), such as G\v is not connected (v is a joint vertex in G, also called junction vertex) and admits SG\v as a connected component (i.e. all the vertices in this connected component belong to the subpattern subpattern's graph); • At least one vertex or an arc of SG is a qualifier element; • card min , card max ∈ N et 0 ≤ card min ≤ card max ; are respectively the minimum and maximum cardinality of sp that define the optional and repeatable characteristics of sp.
Figure 2.2 shows an example of a query pattern which deals with the events, and the performers involved, where musical works have been performed (or conversely) with the corresponding artist(s) and release date. The pattern is composed of three subpatterns named live, artist and date. All of them are optional, and only the subpatterns live and artist are repeatable: it is considered that a musical work can have only one release date, but a musical work may be the work of several artists and can be performed many times.
The rewriting approach takes as input a complex alignment A O→O and a set P ={p O 1 ,...,p O n } of query patterns p O i , and outputs a set
The intuition is that every subgraph from the input patterns has potentially a (complex) correspondence associating its entities to entities in the target ontology. We consider that the subpattern is the relevant unit of semantic information constituting the patterns. Each subpattern is ideally replaced with Fig. 1. Query pattern asking for events and their performers, where musical works have been performed (or conversely), with the corresponding artist(s) and release date.
an equivalent subgraph corresponding to a logical statement relating concepts and properties of the target ontology. This statement is the target part of the correspondence, if any in the alignment, in which the source part matches the initial subpattern. But the subpatterns and the correspondences in the alignment may not have the same granularity (correspondences can be either simple or can relate smaller subgraphs). Thus, we define an algorithm that is similar to a Depth-First Search algorithm (DFS) for traversing and searching graph data structures in the input query patterns. It starts at the largest subgraph, i.e. the subpattern, and recursively explores its subgraphs (i.e. subpattern > RDF triples > classes and properties), until a correspondence is found for the considered subgraph (in which case, the target graph is written to the subpattern being outputted) or a class or property is reached. If at the end of this process, there are entities that have not been translated, the whole subpattern will be discarded1 . The operation is repeated for each subpattern in the input patterns.
The approach is inherently limited by the use of ontology alignment, which is itself an incomplete process. The subpattern is the indivisible expression of a need for information: it can be rewritten by chunks but if it is not fully rewritten at the end of the process, it is discarded. Thus, the conservation of the semantics of original patterns directly depends on the completeness of the input alignment (coverage of the source ontology, quality of correspondences, etc.). We consider that some loss of (semantic) information is acceptable, and that it can be filled with other techniques (for instance, by interacting with the user). However, it is out of the scope of this paper. Figure 3 illustrates the rewriting of the pattern depicted in Figure 2.2 (with the input alignment given later in §4.3, Table 1). The subpattern named live is rewritten to live', following the complex correspondence #6 in the alignment. The subpattern named artist is rewritten to artist', following the complex correspondence #2 in the alignment (in this case, only the first term of the disjunction artist author creator musicComposer appears in the resulting subpattern, for the sake of simplicity and readability).
Finally, the subpattern named date could not be directly rewritten since there is no correspondence for this subgraph. Instead, the property release date is rewritten to releaseDate, following a simple correspondence, and the data type xsd:date remains xsd:date.
In a first series of experiments, we used a set of simple correspondences for rewriting patterns. These correspondences come from a merge of alignments generated by OAEI 2012 matching systems (the reader can refer to [7] for details). Overall, 67% of the entities in the Music ontology were covered in the alignment. 25 out of 60 entities in the query patterns for this ontology could be replaced by a target entity (coverage of 41%). In terms of subpatterns, only 2 out of the 19 subpatterns could be fully rewritten using the alignment. Although we have found a handmade (reference) alignment between Music and DBpedia ontologies5 , we could not use it because it is mostly composed by correspondences linking classes only, using subsumption relations, and few equivalences could be inferred from them. Despite the fact that the quality of the alignment from the matchers was not measured, these first experiments highlighted the limitations in replacing individually the entities in the patterns. Nevertheless, we needed to accurately assess this deficiency and to know to what extent we could rewrite query patterns. It turned out that simple correspondences are not sufficient to capture all the meaningful relations between entities of two related ontologies.
Very few systems are able to find complex correspondences. First, we tried the tool described in [14], which finds complex correspondences using a set of predefined patterns. Besides the two ontologies to align, this tool takes an alignment as input. We used the tool on the pair Music-DBpedia, with (i) the handmade alignment between Music and DBpedia ontologies, and (ii) the merged alignment from the matchers used in the preliminary experiments ( §4.2). In both cases, few correct correspondences could be identified. We tried then the successor of this tool described in [15], which benefits of natural language processing techniques instead of requiring an input alignment, and we obtained similar results.
Hence, we manually created a set of 28 complex correspondences (along 11 simple ones) for the pair Music-DBpedia, guided by the query patterns for Music 6 . A subset of them is presented in Table 1. The idea behind using complex correspondences is that every subgraph pattern has potentially a (complex) correspondence in the target ontology. Given that the subpattern is the relevant unit of semantic information constituting the patterns, we isolated them, and for each of them, we tried to find an equivalent logical statement relating concepts and properties of the target ontology. For constructing the complex correspondence set, we used as basis a set of simple correspondences (the left operand refers to an entity of the Music ontology, and the right operand refers to an entity of the DBpedia ontology): MusicalManifestation MusicalWork, MusicalWork ≡ Musical-Work*, MusicArtist ≡ MusicalArtist*, Performance Event, Performer ≡ Mu-sicalArtist, foaf:Group Band, MusicGroup ≡ Band*, SoloMusicArtist Mu-sicalArtist, Track MusicalWork, Track ≡ Song, and Record MusicalWork7 .
For each correspondence, we identified the complex correspondence patterns that characterise it, from the patterns proposed in the literature: Class 1. 12 out of 28 handmade complex correspondences between Music and DBpedia ontologies.
by Attribute Type [14] (CAT), Class by Inverse Attribute Type [14] (CAT-1), Class by Attribute Value [14] (CAV), Attribute Value Restriction [18] (AVR), equivalent to CAV, Property Chain [14] (PC), Aggregation [18] (AGR), equivalent to PC, Inverse Property [15] (IP), Union [18] (OR), and Intersection [18] (AND). Although no new pattern was discovered, stating that, for our case, the patterns proposed in the literature cover all types of generated correspondences, several of our correspondences are in fact compositions of them (Table 1). For instance, the left operand in the correspondence #4 is an assembly of the patterns CAV and CAT. In the scope of this paper, however, we do not define any algebra which would describe how patterns can be composed or associated to represent the structure of complex correspondences (definition of basic properties and laws such as associativity, commutativity and distributivity). We have also manually generated 52 multilingual complex correspondences (along 13 simple correspondences) for the Cinema and DBpedia ontologies. For instance, the correspondence expressing the relation between the artists that are awarded the Cesar Award in Cinema (source ontology) and DBpedia (target ontology) : Artiste ∃estRecompenseA.CesarDuCinema ≡ Artist ∃cesarAward(Award ∃event.F ilmF estival).
From the set of complex correspondences for the pair Music-DBpedia and the query patterns for Music, we applied our approach ( §3) for rewriting Music patterns in terms of the DBpedia vocabulary. Before rewriting patterns, we evaluated the use of these correspondences for rewriting SPARQL queries. For doing so, we defined a set of rules for translating a complex correspondence pattern into RDF graph patterns (Table 2). These rules are intended to be used for guiding the process of SPARQL rewriting. Following these rules, we managed to rewrite the 25 first SPARQL queries from the benchmark training data in QALD 2013 8 . The training data include 100 natural language questions for MusicBrainz with the corresponding SPARQL queries, as well as the answers these queries retrieve. The queries have been rewritten in order to interrogate DBpedia. As an example, consider the query in Table 3 asking if there are members of the Ramones who are not named Ramone (question #25) over MusicBrainz, and the same query rewritten for DBpedia. The MusicBrainz result answers false, while the DBpedia result asserts the opposite. The DBpedia request is not less correct: if we return the actual query solutions (SELECT) instead of testing whether or not the query pattern has a solution (ASK), we find that Clem Burke in DBpedia was a member of The Ramones under the name "Elvis Ramone", while the MusicBrainz data set directly refers to him with this alias. In fact, both sets of instances do not fully intersect and they are not necessarily/correctly interlinked 9 . From this point of view, 18 of the 25 rewritten queries are correct and consistent with the queries for MusicBrainz: they do not necessarily give the same results, but they do answer the same question. 3 of these 18 results give the same number of solutions with exactly the same literals. 5 out of the 7 remaining results give no solution at all (no instance). And finally, the 2 last results are not fully correct since the complex correspondences ahead are not correct themselves. For instance, M usicalM anif estation ∃release type.live M usicalW ork ∃recordedIn.P opulatedP lace turns out to be erroneous since the albums which have been recorded in a recording studio are equally selectable that are further (semi-automatically) enriched by using linguistic, structural and background knowledge-based strategies. Although different strategies have been proposed, very few matchers for generating complex correspondences are available or use EDOAL, an expressive alignment language [3], for representing them. With respect to query patterns rewriting, the problem can be seen, at a lower level of abstraction, as a problem of SPARQL rewriting. Correndo et al. [2] propose a set of SPARQL rewriting rules exploiting both (complex) ontology alignments and entity co-reference resolution. Zheng et al. [20] propose to rewrite SPARQL queries from different contexts, where context mappings provide the articulation of the data semantics for the sources and receivers. Makris et al. [9,8] present the SPARQL-RW rewriting framework that applies a set of predefined (complex) correspondences. They define a set of correspondence types that are used as basis for the rewriting process (i.e., Class Expression, Object Property Expression, Datatype Property, and Individual ). However, the way the set of complex correspondences is established is not described. Our naive approach for rewriting query patterns is close to these SPARQL rewriting proposals in the sense of using complex correspondences. One of the difficulties is the lack of established ways for automatically identifying them. Although m:n complex correspondences are proposed at conceptual level, few concrete examples are available in the literature. Most of our correspondences are n:m. As most proposals, we start from a set of (automatically) discovered simple correspondences. Finally, our method is applied in an applicative context of rewriting patterns for a question answering system over RDF data.
This paper has discussed the use of complex correspondences for rewriting query patterns, aiming at reusing query families across data sets that overlap. Although we could not fully evaluate the rewriting process mainly due to the fact that SWIP does not treat pattern disjunctions, we were able to validate our approach on a subset of manually validated complex correspondences. This opens several opportunities for future work. First, the structure of query patterns in SWIP could evolve so that they match the structure of the complex correspondences we have established. In particular, SWIP would benefit from the disjunction of subpatterns or specification of instances in patterns. Second, we plan to represent our complex correspondences using EDOAL. Third, we plan to formalise the composition of complex correspondence patterns, which are thereby the building blocks to obtain richer correspondences, following a grammar defining a set of rules for rewriting logical statements in FOL or DL. The grammar must define the properties of pattern precedence, transitivity, associativity, commutativity, and distributivity. Finally, we plan to propose an approach for (multilingual) complex correspondence generation, exploiting specially the ABox of ontologies.
within the property recordedIn: we wrongly thought it was reserved for live performances only. Thus, these results allowed us to validate our complex correspondences and remove those that prove to be incorrect.
WHERE { ?band foaf:name 'Ramones' .
?band foaf:name 'Ramones'@en . ?artist foaf:name ?artistname .
?artist foaf:name ?artistname . ?artist mo:member of ?band .
{?band dbo:bandMember ?artist} UNION {?band dbo:formerBandMember ?artist} . FILTER (NOT regex(?artistname,"Ramone")) FILTER (NOT regex(?artistname,"Ramone")) } } Table 3. DBpedia rewritten query (right) from MusicBrainz query (left). Namespace prefix bindings were ommitted (dbo refers to dbpedia and mo to music).
Next, we rewrote the Music query patterns in terms of the DBpedia vocabulary. Using the 11 simple correspondences and the 28 complex correspondences, we achieved a rewriting percentage of 90% of the Music patterns: on the 19 subgraphs (subpatterns) identified in the patterns for Music, we were able to transform 17 of them. For the Cinema patterns, we were able to rewrite 45 out of 51 subpatterns from the Cinema IRIT query patterns. Then, the patterns rewritten from Music were injected in the SWIP system along the DBpedia data set, in order to demonstrate the relevance of rewriting query patterns in the whole process. We managed to run five queries from QALD and originally intended to MusicBrainz. The generated SPARQL queries are (semantically) correct as long as (i) the correspondences involved do not apply any disjunction of terms, which is not currently supported in SWIP (in this case, only the most likely term is kept), and (ii) the source and target in the correspondences involved have the same information level (basically, equivalence).
Rewriting query patterns using complex correspondences is the novel aspect of this paper. With respect to complex correspondence generation, different approaches have emerged in the literature in the last years. A common approach is based on complex correspondence patterns [18,17,14,15] ( §4.3). Walshe [19] proposes refining elementary correspondences by identifying which correspondence pattern best represents a given correspondence. Following a different strategy, Qin et al. [13] propose an iterative process that combines terminological, structural, and instance-based matching approaches for mining frequent queries, from which complex matching rules (represented in FOL) are generated. Nunes et al.
[10] present a two-phase instance-based technique for complex datatype property matching, where the first phase identifies simple property matches and the second one uses a genetic programming approach to detect complex matches. Recently, Arnold [1] uses state-of-the-art matchers for generating initial correspondences