dataesr/scientific-paragraphs-categorization huggingface dataset:
3: Each triple pattern is translated into a subquery according to the set of xR2RML mappings identified. A sub-query consists of operators of the abstract query language and atomic abstract queries. §4. 4: We enforce several optimizations on the resulting abstract query, e. g. self-joins or self-unions elimination. Our pivot abstract query language complies with the grammar depicted in Def. 1. It derives from the syntax and semantics of SPARQL  [27] : the language keeps the names of several SPARQL operators (UNION, LIMIT, FILTER) and prefers the SQL terms INNER JOIN ON and LEFT OUTER JOIN ON to refer to join operations more explicitly. A notable difference with SPARQL is that, in the tree representation of a query, the leaves of a SPARQL query are triple patterns. Conversely, the leaves of an abstract query are Atomic Abstract Queries ( §4.
3). The INNER JOIN and LEFT OUTER JOIN operators stem from the join constraints implied by shared variables. Somehow, the second INNER JOIN in Def. 1, including the "AS child " and "AS parent" notations, is entailed by the join constraints expressed in xR2RML mappings using referencing object maps and properties rr:child and rr:parent. Notation v 1 ,. v n , in the join operators, stands for the set of SPARQL variables on which the join is to be performed. Notation <Ref> stands for any valid xR2RML data element reference, i. e. a column name for a tabular data source, an XPath expression for an XML database, a JSONPath expression for a NoSQL document store such as MongoDB and CouchDB, etc. The first query transformation step is implemented by function trans m depicted in Def. 2. It rewrites a well-designed SPARQL graph pattern  [27]  into an abstract query while making no assumption with respect to the target database query capabilities.
SPARQL rewriting methods reviewed in section 2 generally adopt a bottom-up approach where, typically, a SPARQL FIL-TER translates into an encapsulating query (e. g. a SELECT-WHERE clause in the case of SQL). Thus, filters in the outer query do not contribute to the selectivity of inner-queries that may return large intermediate results. This flaw is commonly worked out in a subsequent SQL query optimization step, or by assuming that the underlying database engine can take care of this optimization. In our context though, we cannot assume that the target query can be optimized nor that the database query engine is capable of doing it. We therefore consider SPARQL filters at the earliest stage: function trans m pushes SPARQL filters down into the translation of each inner query in order to return only necessary intermediate results.
With the example of query Q 2 (Listing 1. 3), the From part for tp 1 simply consists of the logical source of <#Mbox>: db. people. find({'emails':{$ne: null}}). -Project. Traditionally, the projection part of a database query restricts the set of attributes that must be returned in the query response. In relational algebra, this is denoted by the projection operator π: π a1,. an (R) denotes the tuple obtained when the attributes of tuple R are restricted to the set {a 1 ,. a n }. Similarly, the Project part of an atomic abstract query is a set of xR2RML references. For each variable in the triple pattern, the xR2RML references in the term map matched with that variable are projected. In our running example, the subject and object of tp 1 are ?x and ?mbox1. They are matched with the subject and object maps of mapping <#Mbox>.
Thus, the corresponding xR2RML references within these subject map and object map must be projected. Hence the Project part for tp 1 : {$. id AS ?x, $. emails. * AS ?mbox1}. Furthermore, the child and parent joined references of a referencing object map must be projected in order to accommodate databases that do not support joins. In the relational database case, these projections would be useless since the database can compute the join internally. But the abstract query must accommodate any target database, hence the systematic projection of joined references. -Where. The Where part is a set of conditions about xR2RML references. They are produced by matching each term of a triple pattern tp with its corresponding term map in mapping M : the subject of tp is matched with M 's subject map, the predicate with M 's predicate map and the object with M 's object map.
Abstract Query Optimization At this point, the method we have exposed translates a SPARQL graph pattern into an effective abstract query, i. e. that preserves the semantics of the SPARQL query. Yet, shortcomings such as unnecessary complexity or redundancy may lead to the generation of inefficient queries, and consequently yield poor performances. Although we may postpone the query optimization to the translation into a concrete query language, it is beneficial to figure out which optimizations can be done at the abstract query level first, and leave only database-specific optimizations to the subsequent stage. SPARQL-to-SQL methods proposed various SQL query optimizations such as  [39, 32, 14]. In this section, we review some of these techniques, referring to the Listing 1. 5. Optimization of transm(gp2) (Listing 1.
4) by self-join elimination terminology defined in  [39]. We show how these optimizations can be adapted to fit in the context of our abstract query language. In particular, we show that our translation method implements some of these optimizations by construction. In addition, we propose a new optimization, the Filter Propagation, that, to our knowledge, was not proposed in any SPARQL-to-SQL rewriting method. Filter Optimization. In a naive approach, strings generated by R2RML templates are dealt with using an SQL comparison of the resulting strings rather than the database values used in the template. Typically, when the translation of an R2RML template relies on the SQL string concatenation, a SPARQL query can ben rewritten into something like this: In our approach, equality conditions apply to xR2RML references rather than on the template-generated values, hence the Filter Optimization is enforced by construction.
Using joins commutativity, those two queries can be merged into a single one depicted in the third atomic abstract query in Listing 1. 5  8. Self-Union Elimination. A UNION operator can be created either due to the SPARQL UNION operator or during the translation of a triple pattern to which several mappings are bound (in function transT P m ). Analogously to the Self-Join Elimination, a union of several atomic abstract queries sharing the same logical source can be merged into a single query when they have the same From part. Constant Projection. The Constant Projection optimization detects cases where the only projected variables in the SPARQL query are matched with constant values in the bound mappings. In the relational database context, it has been referred to as the Projection Pushing optimization  [39].
Let us consider the example query below: SELECT DISTINCT ? p WHERE {? s ? p ? o }. In a naive approach, all mappings are bound to the triple pattern ?s ?p ?o. Hence, the resulting abstract query is a union of the atomic queries derived from all the possible mappings. In other words, this query will materialize the whole database before it can provide an answer. Very frequently, xR2RML predicate maps are constant-valued: the predicate is not computed from a database value, on the contrary it is defined statically in the mapping. This is typically the case in our running example that has only constant predicate maps (values of property rr:predicate: foaf:knows and foaf:mbox (Listing 1. 1). In such cases, given that the SPARQL query retrieves only DISTINCT values of the predicate variable ?p, no query needs to be run against the database at all: it is sufficient to collect the distinct constant values that variable ?p can be matched with.
Application to the MongoDB NoSQL Database In the previous section, we have exhibited an abstract query model and a method to translate a SPARQL graph pattern into an optimized abstract query, relying on the xR2RML mapping of a target database to RDF. We now want to illustrate the effort it takes to translate from the abstract query language towards a concrete query language with a somewhat different expressiveness. To this end, we consider the MongoDB NoSQL database. Its JSON-based data model and its query language differ greatly from SQL-based systems for which many rewriting works have been proposed. Hence, we believe that it should provide an interesting illustration of our method. Besides, MongoDB has become a popular NoSQL actor in recent years. It is provided as a service by major cloud service providers and tends to become common within the scientific community, suggesting that it is increasingly adopted as a commonplace database.
In this section, we first glance at the MongoDB query language, and we describe an abstract representation of MongoDB queries (section 5. 1). Then, we show that the translation from the abstract query language towards Mon-goDB is made challenging by the expressiveness discrepancy between the two languages (section 5. 2) and we describe a complete method to achieve this. Finally, we summarize the whole SPARQL-to-MongoDB process orchestration, from the SPARQL graph pattern translation until the generation of the RDF triples that match this graph pattern (section 5. 3).
The MongoDB Query Language MongoDB comes with a rich set of APIs to allow applications to query a database in an imperative way. In addition, the MongoDB interactive interface defines a JSON-based declarative query language consisting of two query methods. The find method retrieves documents matching a set of conditions and returns a cursor to the matching documents. Optional modifiers amend the query to impose limits and sort orders. Alternatively, the aggregate method allows for the definition of processing pipelines: each document of a collection passes through each stage of a pipeline thereby creating a new collection. This allows for a richer expressiveness but comes with a higher resource consumption that entails less predictable performances. Thus, as a first approach, this work considers the find query method, hereafter called the MongoDB query language.
Its concrete representation is: $and : [ {" p. 0": {$eq :10}} , {" q ": {$elemMatch : {$eq :" val "}}} ] To achieve a translation from the abstract query language towards the Mon-goDB query language, we must figure out which components of an abstract query have an equivalent MongoDB rewriting, and, conversely, which components shall be computed by the query-processing engine. Below, we analyze the possible situations. -Inner and left outer joins. MongoDB find queries do not support joins. Consequently, there does not exist any MongoDB query that would be equivalent to the INNER JOIN and LEFT OUTER JOIN operators. These operators need to be processed by the query-processing engine by joining the RDF triples generated for both sub-queries. -UNION. The rewriting of the UNION operator depends on the graph patterns to which it applies.
Let us consider the following SPARQL graph pattern, where tp n is any triple pattern: { tp1. tp2. } UNION { tp3. tp4. } Each member of the union translates into an INNER JOIN. Since joins cannot be processed within MongoDB, the outer UNION operator cannot be processed within Mon-goDB either. The issue occurs likewise as soon as one of the members is either an INNER JOIN or LEFT OUTER JOIN. Under some circumstances, a UNION operator may be translated into the MongoDB $or operator. Yet, the Mon-goDB language definition imposes specific restrictions as to how operators can be nested. Consequently, in a first approach, we always shift the processing of the UNION abstract operator to the query-processing engine. Further works could attempt to characterize more specifically the situations where a UNION can be processed within MongoDB.
More generally, the translation from the abstract query language towards MongoDB consists of two steps depicted in Fig. 2. In step 1 (detailed in section 5. 2), the translation of each atomic abstract query towards MongoDB amounts to translate projections of JSONPath expressions (Project part) into MongoDB projection arguments, and conditions on JSONPath expressions (Where part) into equivalent abstract MongoDB queries. Several shortcomings may appear at this stage, such as unnecessary complexity or untranslatable conditions. Thus, in step 2 (detailed in section 5. 2) each abstract MongoDB query is optimized and rewritten into valid, concrete MongoDB queries. In the current status of this work, we do not consider the translation of SPARQL filters (conditions sparqlFilter ) for the sake of simplicity.
Yet, this rewriting may be hindered by three potential issues: (i) During the translation process, nested OR or AND clauses may be produced, as well as sibling WHERE clauses. Such unnecessary complexity may yield an underperforming query. (ii) It may not be possible to translate some JSONPath expressions into equivalent MongoDB operators. This occurs with specific JSONPath array slice notations, or in JSONPath expressions assuming that the root document is an array field and not a document field (which is forbidden in MongoDB). In such cases, a NOT SUPPORTED clause tracks the location of this failed translation. (iii) The MongoDB $where operator passes a JavaScript expression or function to the query system. It provides greater flexibility than other operators, however it is valid only in the top-level query document: it cannot be used inside a nested query such as the $elemM atch operator.
, Q m ) such that ∀i ∈ [1, m] Q i is a valid MongoDB query, i. e. Q i does not contain any not supported clause, and a where clause only shows at the top-level of Q i. Completeness: Executing Q against the database retrieves all the documents matching condition C. If Q contains at least one not supported clause, then Q may retrieve additional documents that do not match condition C. A corollary of Theorem 1 is that, using the xR2RML mapping of a MongoDB database to RDF, we can rewrite any SPARQL 1. 0 graph pattern into an abstract query whose atomic abstract queries are valid MongoDB queries or unions of valid MongoDB queries.
e. JSONPath expressions for MongoDB) that must be projected. The Where part consists of isNotNull, equals and sparqlFilter conditions on JSONPath expressions. In step 2, function proj translates each projected JSONPath expression into a MongoDB projection argument, function trans translates each isNotNull and equals condition into an abstract representation of a MongoDB query (section (section 5. 2), and function rewrite (section 5. 2) optimizes and rewrites this abstract representation into a concrete MongoDB query or a union of concrete MongoDB queries. Two steps remain, that we have not described yet. In step 3, the concrete queries are executed against the database. In step 4, the result JSON documents are translated into RDF triples according to the xR2RML mappings, then the query processing engine evaluates the abstract query by computing the INNER/LEFT OUTER JOIN, UNION, FILTER and LIMIT operators.
Experimentation and Evaluation To date, to our knowledge, the method proposed in this paper and the MongoDBenabled ontop software  [8]  are the only approaches meant to query arbitrary MongoDB documents with SPARQL. So far though, this ontop version is not available for test, which hinders possible performance comparison. Additionally, no benchmark similar to the Berlin SPARQL Benchmark for relational databases  [6]  exists so far for querying NoSQL databases with SPARQL. Therefore, in this section, we describe a real-world use case that we used to build a test database, and we report experimental results with respect to the effectiveness and performance of our approach.
Prototype Implementation Morph-xR2RML is the prototype implementation we developped to evaluate the effectiveness of the xR2RML mapping language and the SPARQL-to-MongoDB method proposed in this paper. It comes with connectors for the MySQL and Postgres relational databases, and for the MongoDB document store. It can process an xR2RML mapping graph in either the data materialization or the query rewriting modes. Morph-xR2RML is available on GitHub 9  under the Apache 2. 0 license, it is written in the Scala programming language. It is based on and extends the Morph-RDB  [29]  R2RML implementation. We performed a substantial code refactoring in order to isolate any RDB-related code into a dedicated software module. As a result, our prototype is extensible by design: supporting a new type of database amounts to create a new software module that implements a given set of interfaces, thereby encapsulating and isolating any database-specific concerns from the rest of the project code.
Following this approach, we developed a connector for the MongoDB document store, to translate MongoDB JSON documents into RDF and rewrite SPARQL queries into MongoDB queries. Morph-xR2RML relies on several open-source Java APIs, the most salient ones are listed here. Jena 10  is a well known Java framework consisting of several APIs meant to build Semantic Web Data applications. We use the Jena RDF API that helps handle RDF triples and graphs. MongoDB comes with a native Java API  11  that allows for imperative style querying only. The Jongo API  12  builds on top of it to translate a declarative MongoDB query (a find query in our case) into imperative code. Lastly, Jayway JsonPath 13  is a Java implementation of the JSONPath language. The query rewriting experimentation we report in this section was conducted on a server equipped with a 3.
Experimentation Database TAXREF  [15]  is the French national taxonomic register for fauna, flora and fungus, maintained and distributed by the French National Museum of Natural History (MNHN). It is a manually curated register of all the species inventoried in metropolitan France and overseas territories, organized as a hierarchy of over 485. 000 scientific names (in version 9) that mark a national and international consensus. As an example, the listing below shows a JSON excerpt from TAXREF's Web service 14 , describing the common dolphin species (Delphinus delphis). Annotation "habitat":1 states that it lives in a marine habitat, annotation "rang":"ES" states that the taxon belongs to the "species" taxonomical rank. Annotation "fr":"P" characterizes one of its biogeographical statuses: it states that Delphinus delphis is present in mainland France.
{ " codeTaxon ":"60878" , " codeReference ":"60878" , " codeParent ":"191591" , " rang ":" ES " , " libelleNom ":" Delphinus delphis " , " libelleAuteur ":" Linnaeus , 1758" , " no mV e rn ac ul a ir e ":" Dauphin commun " , " n o m V e r n a c u l a i r e A n g l a i s ":" Common Dolphin " , " url ":" http :// inpn. mnhn. fr / espece / cd_nom /60878" , " habitat ":"1" , " fr ":" P " , (. ) } We are involved in an on-going collaboration with TAXREF experts from MNHN, aimed to publish TAXREF on the Web of Data as a SKOS thesaurus  [9]. In this context, we imported into a MongoDB database the JSON representation of TAXREF v9. 0, wherein each of the 485. 189 JSON documents accounts for one scientific name, may it be a taxon reference of synonymous name. Listing 1. 7 exemplifies the SKOS modeling with taxon Delphinus delphis and its synonym Delphinus vulgaris.
The taxon is represented as a SKOS concept (line 10). The skos:broader property models the relationships towards the parent taxon in the classification (line 13), i. e. genus Delphinus in this example. The taxon reference and synonymous names are represented as SKOS-XL labels (lines 23-33), referred to with properties skosxl:prefLabel and skosxl:altLabel respectively (lines  [14] [15]. The taxonomical rank, habitat and bio-geographical status are properties of the SKOS concept (lines 16-21), while the authorities and vernacular names are properties of SKOS labels (lines  25-27 and 31-33). Leveraging this existing database, we set up an experimentation of the SPARQLto-MongoDB query rewriting. In the next section, we shortly describe the xR2RML mappings designed for the experimentation.
Experimentation xR2RML Mapping Graph The xR2RML mapping graph designed to generate the TAXREF-based SKOS thesaurus is provided in the xR2RML GitHub repository  15. It consists of 90 mappings, a somewhat high number that spawns from the distance between the internal structure of TAXREF JSON documents and the targeted SKOS modeling. We illustrate this distance with an example. Habitats are coded in TAXREF with integer values, e. g. value '1' represents the marine habitat, '2' represents fresh water, etc. Translating the marine habitat into URI http://inpn. mnhn. fr/taxref/habitat#1 would be straightforward using a template that would append the value read from the database to http://inpn. mnhn. fr/taxref/habitat#. A single mapping would be sufficient to generate the triples related to all types of habitat.
Experimentation Results In section 5, we showed that atomic abstract queries can be translated into equivalent MongoDB queries, but other operators of the abstract query language (INNER JOIN, LEFT OUTER JOIN, UNION) must be computed by the     query along with the corresponding triple pattern and semantics, the number of results it retrieves from the database, and the average time it took to process the query (the query processing spans the SPARQL query rewriting, the query evaluation against MongoDB and the RDF triples generation). For each query, 10 measures were performed: we report the average value and standard deviation. The last column gives the average processing time per query result, that converges towards 0. 48ms. Figure  4  depicts the average query processing time (fourth column of Table  1 ) as a function of the number of results (blue line).
Q3, Q4 and Q5 show a similar overhead of approximately 19%. Although we could expect the overhead percentage to be constant with higher numbers of results, it reaches 32% for Q6. A detailed analysis shows that the difference lies in the time needed to generate the RDF triples. Compared to Q5, the number of results in Q6 increases by 77% while the materialization time increases by 120%. The variable term in Q3, Q4 and Q5 is a blank node whereas it is a URI in Q6. A tentative explanation is that Morph-xR2RML may be faster when producing blank nodes than when producing URIs, unless this difference lies in the Jena API on which Morph-xR2RML relies to handle RDF triples. Further works should consider using more substantial databases to assess this difference with more precision. In any case, the processing performed by Morph-xR2RML adds no more than a 30% overhead to the time needed to query the database and retrieve the results.
9. The first atomic query retrieves 1 document from the database, while the second and third queries retrieve 257,965 documents each. Executed naively, the inner-most join computes the join of 257,965 triples with another 257,965 triples generated from the same database documents. With a smarter join ordering, the triple produced by the first atomic query is joined with the 257,965 triples of the second one to produce two triples (taxon 60585 has two synonyms), that, in turn, are joined with the 257,965 triples of the third query. Yet, two joins of 257,965 triples with one then two triples have to be performed. Some tests show that the time needed to complete this query is in the order of 4 minutes. The Filter Propagation optimization leverages some situations where, within the join of two sub-queries, a condition on a variable shared by both subqueries can be propagated from one sub-query to the other.