Abdoul Macina
email: macina@i3s.unice.fr

Johan Montagnat
email: johan.montagnat@cnrs.fr

Olivier Corby
email: olivier.corby@inria.fr

A SPARQL distributed query processing engine addressing both vertical and horizontal data partitions Un moteur de traitement de requêtes SPARQL distribuées optimisé pour les partitions de données verticales et horizontales

Keywords: Distributed Query Processing, SPARQL, Linked data

An increasing number of linked knowledge bases are openly accessible over the Internet. Distributed Query Processing (DQP) techniques enable querying multiple knowledge bases coherently. However, the precise DQP semantics is often overlooked, and query performance issues arise.

In this paper, we propose a DQP engine for distributed RDF graphs, adopting a SPARQL-compliant DQP semantics. We improve performance through heuristics that generate Basic Graph Pattern-based sub-queries designed to maximise the parts of the query processed by the remote endpoints.

We evaluate our DQP engine considering a query set representative of most common SPARQL clauses and different data distribution schemes. Results show a significant reduction of the number of remote queries executed and the query execution time while preserving completeness.

Un nombre grandissant de bases de connaissances liées sont exposées à travers l'Internet. Le traitement de requêtes distribuées (DQP) permet d'interroger des bases de connaissances multiples simultanément. Cependant, la sémantique DQP précise est souvent négligée, et des problèmes de performance doivent être traités.

Dans ce papier, nous proposons un moteur DQP pour l'interrogation de graphs RDF distribués, conforme à la sémantique de SPARQL. Nous en améliorons la performance grâce à des heuristiques qui génèrent des sous-requêtes à partir de schémas de graphes basiques (BGPs) de manière à maximiser la partie de la requête traitée par les serveurs de données distants.

Nous évaluons notre moteur DQP à travers un ensemble de reqêtes représentatives de clauses SPARQL les plus répendues et des schémas de distribution des données divers. Les résultats montrent un réduction significative du nombre de requêtes exécutées et du temps de traitement sans altération de la complétude des résultats.

INTRODUCTION

The Semantic Web development led to the dissemination of open linked knowledge bases in RDF format 1 , distributed world-wide over the Internet. The use of unique Internationalized Resource Identifiers (IRIs) to identify data elements and the sharing of these universal identifiers over multiple data sets create a network of connections between knowledge bases that are operated independently. SPARQL [START_REF] Garlik | SPARQL 1.1 Query Language[END_REF] is an expressive language and widely adopted standard for RDF graphs querying. It only partially addresses the problem of querying data distributed over different graphs though, providing a low-level interface to express data distributionspecific queries. The aim of this work is to enable SPARQL querying over multiple RDF knowledge bases transparently. We adopt a user-centric vision, where the result of a SPARQL query applied to a set of graphs should be identical to the result that would be obtained by applying the same query to a virtual graph aggregating all target graphs.

Two main approaches are typically considered to implement querying over distributed data sources [START_REF] Haas | Optimizing queries across diverse data sources[END_REF]: materialisation (also referred to as Extract-Transform-Load) where all data is collected to a single database, thus implementing the virtual data source to be queried, and Distributed Query Processing (DQP), where original queries are transformed, applied to target data sources, and their results integrated. Although materialisation is much simpler to implement, it suffers many drawbacks among which the time and space needed to integrate all data. In this paper, we are more particularly interested in SPARQL DQP for RDF data sources. We investigate (i) the problem of the SPARQL query semantic preservation in a DQP context, which involves query rewriting, and (ii) an optimisation technique to improve query performance, taking into account the way data is partitioned over multiple data sources.

After a study of the state of the art, this paper describes the semantic that we adopt for SPARQL queries in a DQP context in Section 3. Our goal is to preserve SPARQL semantics and expressiveness as much as possible. The DQP process described matches the user-centric vision of a virtual knowledge graph aggregating all data. The problem of query rewriting is outlined and a query decomposition technique that intends to push as much as possible of the original query towards the remote sources for maximal filtering of the query results is proposed. In Section 4, we describe our query engine architecture and the algorithms implementing our DQP optimisation strategy. Results are presented in Section 5 based on different types of SPARQL query clauses and different types of data partitioning.

STATE OF THE ART 2.1 RDF data stores distribution context

The RDF W3C recommendation is commonly used for data representation on the Semantic Web. An RDF dataset may be modelled as a graph composed by a set of triples (subject, predicate, object) where subjects and objects are nodes and predicates are the labels of edges linking subjects and objects. Subjects are IRIs (Internationalised Resource Identifiers) or blank nodes, predicates are IRIs and objects are IRIs, blank nodes or literal values. A blank node is a local resource without IRI. RDF triples may belong to named graphs, which correspond to different (possibly overlapping) RDF data sub-graphs. RDF triples without explicit named graph attachment belong to the default graph.

Two main approaches may be considered to query distributed RDF data sets [START_REF] Hartig | Linked data query processing[END_REF]. When the focus is on processing very large graphs, one usualy considers a graph data structure distributed over multiple storage resources. The problem addressed is then the balancing of graph data over multiple storage nodes and the efficiency of the data structure used to split the graph (e.g. [START_REF] Peng | Processing SPARQL queries over distributed RDF graphs[END_REF]). This approach is based on the hypothesis that the graph data can be redistributed so as to improve the performance of the distributed graph querying algorithm used. Conversely, when the focus is on querying legacy linked RDF data stores distributed over the Internet and accessible through SPARQL endpoints, data cannot be repartitioned. The complete graph data structure does not exist as such. Instead, the legacy RDF graphs are implicitly connected through shared IRIs: since IRIs are uniques, nodes using the same IRI in different graphs are identical. This approach is often referred to as federated SPARQL querying (e.g. [START_REF] Schwarte | Fedx: optimization techniques for federated query processing on linked data[END_REF]). Our work falls into this second category.

Legacy data sets stored in independent SPARQL endpoints may typically be vertically partitioned, when different kinds of data are stored in disjoint data sources, horizontally partitioned, when the same kind of data is stored and distributed in several data sources, or a mix of both, when part of the data is vertically partitioned and part is horizontally partitioned (general case). In RDF graphs, vertical partitioning corresponds to the case where predicates are partitioned among the data stores: a given predicate can only be found in a single data store. Conversely, horizontal partitioning corresponds to the case where all predicates can be founds in several data sources.

SPARQL query language

SPARQL is the most common query language used for RDF data. SPARQL queries are composed of two main clauses: the first one specifies the query form (SELECT, CONSTRUCT, ASK, or DESCRIBE), while the second one is a WHERE clause specifying a basic graph pattern to be matched by queried graph resources. In the remainder of this paper, we focus on SELECT query form without loss of generality. Most of the DQP processing complexities lies in the queries WHERE clause.

Let us consider a data set representing an organisation composed by some teams divided into groups. Each group has a number of members. Consider the example SPARQL query Q1 below:

query results

global joins

Applying Q1 to a single data source containing all data will return the group name and its number of members for each group in the "SPARKS" team in the database. In this paper however, we will consider data distributed in several sources and accessed through a DQP server as illustrated in Figure 1. The client sends SPARQL queries to the DQP server. The server splits queries to submit sub-queries to remote endpoints. Each endpoint processes locally the subqueries received and returns partial results. Results are processed on the server side and returned to the client. Join operations may be evaluated locally at an endpoint level or globally at the server level, joining data retrieved from different data sources. In the remainder of this paper, we will refer to local joins to refer to endpoint-level joins and distributed joins to refer to server-level joins.

SPARQL was natively designed for querying remote data sources. Beyond a graph query and update language, SPARQL defines a protocol for transferring queries towards remote servers (SPARQL endpoints) and returning result sets. The SPARQL language also defines a SERVICE clause aiming at applying a sub-query to a specific endpoint identified by its access URI. A SPARQL query can thus be composed by several SERVICE clauses computed on different endpoints, which results are combined together.

A strong limitation of the SERVICE clause in a DQP context is that a query has to be manually decomposed into multiple sub-queries to apply to several data sources. This requires the user to have a precise knowledge of the data partitioning model in the data sources. In the Q1 example above, if data is split between a data source S1 containing all ns:team and ns:group relations, and a data source S2 containing all ns:name and ns:members relations for instance, Q1 will return no results, whether applied to S1 or applied to S2 independently (as it involves joining groups which are distributed among S1 and S2). Using SPARQL, a user would have to rewrite the query to decompose it into two SERVICE sub-clauses: a SERVICE clause targeting S1 to retrieve all (?team, ?group) tuples and a SERVICE clause targeting S2 to retrieve all (?group, ?name, ?members) tuples, before joining all data on groups.

SPARQL queries are usually designed to apply to a single data source and designing SERVICE clause-based SPARQL queries to access distributed RDF data may become very cumbersome or even humanly intractable in the case of complex queries rewriting. A technique to implement SPARQL DQP is to automate the rewriting of SPARQL queries into multiple SERVICE clauses. As we will see in Section 3, although this technique is sound it may prove unacceptably inefficient when processing the resulting query and further query optimisation is needed.

Query decomposition strategies

To evaluate SPARQL queries in DQP mode, different strategies may be considered. As discussed above, applying the original query to partial data sources is likely to return a subset of the expected results only since data from different sources need to be joined. A proper DQP strategy will therefore decompose the original query into sub-queries that are relevant for each data source and compute joins later on. Distributed querying typically implies four main steps [START_REF] Özsu | Principles of Distributed Database Systems[END_REF]:

1. Sources selection: All data sources are not necessarily containing data that is relevant for a given query. Source selection identifies data sources that are likely to contribute to the result set in order to avoid unnecessary processing.

2. Query planning is a query analysis steps aimed at identifying various optimisations that can be applied by transforming the initial query while preserving its semantics, such as reordering query parts.

3. The query rewriting step decomposes the original query into a set of sub-queries to be distributed to the remote data servers. It both ensures preservation of the original query semantics and takes into account the performance of the sub-queries to be processed. As a general rule, the more selective the query sent to a remote server, the more efficient the processing.

4. The Query evaluation step finally executes the query plan and collects results from all sub-queries generated. Partial results thus aggregated often require further processing (different result sets typically need to be joined) to compute final results.

Sources selection requires information on the sources content. This information is usually acquired prior to query processing, either through data statistics collection on the endpoints, or by probing the endpoints through source sampling queries.

Query planning and query rewriting involve decomposing the original query into source-specific sub-queries so as to retrieve all data that contributes to the final result set. In SPARQL, Triple-based evaluation is the finest-grained and simplest query decomposition strategy. It consists in decomposing the query into each of its triple patterns (4 TPs in the case of Q1 for instance), evaluating each TP on the source independently, collecting the matching triples on the server side and joining the results. The obvious drawback of evaluating triples patterns individually is that many triples may be retrieved from the sources and returned to the server, just to be filtered out by the join operations. If this strategy is returning correct results (all potentially matching triples are necessarily returned), it is often inefficient. A simple optimisation consists in computing nested loop joins for triple patterns with join conditions. This limits the number of triples returned to the server for post-processing, but at the cost of many remote queries generation.

Conversely, the BGP-based strategy consists in evaluating Basic Graph Patterns (BGPs) sub-queries. BGPs are groups of triple patterns. Their evaluation potentially involves processing joins at the endpoint level (local joins), which is more efficient than retrieving all possible triples at the server level before computing joins (distributed joins). The use of SPARQL SERVICE clauses is a typical way of sending BGPs for evaluation on remote endpoints. However, as discussed before, a BGP could return a subset of the expected results only, due to the need to compute joins between data distributed in different data stores. In the case of vertically partitioned data sets, a whole partition is contained in a single server, to which a global BGP can be sent through a SERVICE clause. In case of horizontally partitioned data sets, BGPs can still be computed but different BGPs may be needed depending on the endpoints content.

To preserve the semantics of the original query, it is mandatory to carefully split it into sub-queries that do not cause results losses. The larger BGPs can be evaluated independently in each data source, the more efficient the query. Yet, the data distribution scheme needs to be taken into account to ensure that a BGP does not filter results too much for complete query processing. An hybrid BGP-Triple evaluation strategy computes the largest BPGs usable without alterating the results. It mixes the evaluation of BGPs and TPs at the endpoints level to collect a super-set of the final results over which remaining join operations can be computed at the server level. The difficult part of hybrid strategies is to estimate the most efficient BPGs to process for each data source and the combinations of TPs that complete the query.

Main federated SPARQL DQP engines

Naive DQP implementations may lead to a tremendous number of remote queries and generate large partial result sets. The optimization of DQP is therefore critical and many related work primarily address the problem of query performance. This is the case for several DQP engines designed to query RDF data stores with SPARQL, such as DARQ [START_REF] Quilitz | Querying distributed rdf data sources with sparql[END_REF], FedX [START_REF] Schwarte | Fedx: optimization techniques for federated query processing on linked data[END_REF], SPLENDID [START_REF] Görlitz | SPLENDID: SPARQL Endpoint Federation Exploiting VOID Descriptions[END_REF], and ANAPSID [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF]. Their data sources selection and query decomposition strategies are described below.

Sources selection

Most existing engines rely on prior information on sources content for sources selection. DARQ relies on service descriptions to identify relevant sources. The descriptors provide information on predicate capabilities and statistics in-formation on triples hosted in each source. However, unbound predicates (i.e. variables as predicates) are not handled by DARQ. SPLENDID index manager uses statistical data on sources expressed through the Vocabulary of Interlinked Data (VoID [START_REF] Alexander | Describing linked datasets -on the design and usage of void, the vocabulary of interlinked datasets[END_REF]), to build an index of predicates and their cardinality. This index is computed through SPARQL ASK queries for triple patterns with bound variables and by assigning all sources to triple patterns with unbound predicates. ANAPSID source selection is based on a catalog of predicates, concepts capabilities and statistics. The statistics are updated dynamically by the query engine during queries evaluation.

Rich prior information on data sources content is useful to implement elaborated source selection strategies. However, it requires specific instrumentation of data sources, and therefore do not apply to regular SPARQL endpoints. FedX also performs source selection optimisation but unlike the previous approaches, without prior knowledge on sources. Only SPARQL ASK queries are sent to identify the relevant sources for query predicates. Similarly, our DQP engine is based on SPARQL ASK queries for sources statistics collection.

Query rewriting

BGP-based query evaluation is implemented by all federated SPARQL query engines listed above to improve performance. DARQ also add filters to BGP-based sub-queries for more selectivity. However, in all these approaches, BGP generation is only considered for triples patterns relevant to a single source (vertically partitioned data). Regarding SPARQL language expressiveness, only ANAPSID can cope with the SPARQL 1.1 standard. FedX, SPLENDID and DARQ support SPARQL 1.0, which does not include the SPARQL SERVICE clause. The hybrid strategy described in this paper can generate BGPs for both vertical and horizontal data partitions. The heuristic implemented aims at creating the largest possible BGPs and applying as much as possible filtering at the endpoints level to minimize the number of queries generated, and the number of partial results collected for post processing at the DQP server level.

DISTRIBUTING SPARQL QUERIES

In this work, we more specifically address the query rewriting step of the DQP process. The objective is to develop a SPARQL DQP engine that (i) is fully compatible with the SPARQL 1.1 standard while preserving performance and (ii) can adapt to the existing data partitioning scheme.

DQP query performance is a major issue. As outlined in Section 2.4, it is often dealt with in the litterature by only considering a subset of the SPARQL standard, making assumptions on the data distribution or considering instrumented endpoints. To remain user-centric, our approach does not make any constraining assumption on the kind of request applied (full SPARQL compliance), on the data partionning scheme (endpoints are pre-existing and no attempt is made to redistribute the data), nor on the endpoints capability (standard third party SPARQL endpoints can be queried).

By giving language expressiveness the highest priority, we ensure that users will not be limited by the query language and that results returned will be complete with regards to the existing standard. To alleviate the resulting performance problem, we propose a query rewriting heuristic that tackles all kinds of data partitioning schemes (vertical and/or horizontal), using only limited knowledge on endpoints content, that can be inferred through regular SPARQL queries.

Since automated query rewriting to adapt a SPARQL query to data distributed over different sources is not part of the SPARQL standard, a clear semantics for SPARQL DQP first needs to be defined. It should be noted that none of the approaches cited above investigates the DQP semantics.

Distributed SPARQL query semantics

Most works on SPARQL DQP make the assumption that users expect the SPARQL engine to return the same result whether processing a single or multiple data sources. Intuitively, this corresponds to evaluating the original SPARQL query against an aggregated data graph, defined as the set union of all data source triples lists. Implementing this semantics is not straightforward though. Moreover, there are particularities of RDF graphs to be considered to define a precise semantics for the evaluation of SPARQL queries on multiple data sources: named graphs, data replication, blank nodes and redundant results.

Named graphs: Named graphs are sub-graphs in an original RDF graph, identified by an IRI. The RDF standard does not anticipate data distributed over multiple data stores. As a consequence, the fact that the same IRI for named graphs appears in different RDF stores does not imply anything on the relations between these named graphs. In the DQP context, we consider that data associated to the same named graph IRI belongs to a single named graph, even if it is distributed in different sources. This is coherent with the idea of aggregating all data sources into a single virtual graph. In addition, IRI are usually specific enough to prevent most accidental collisions between names.

Data replication: In a distributed context, it is common to replicate data items over several data servers to improve availability. RDF triples may thus be replicated in different servers. When evaluating a query, an RDF triple should be accounted for only one time, even if it is replicated over different servers. This is coherent with the aggregated graph view, which cannot contain duplicated triples.

Blank nodes: By definition, blank nodes are locally scoped nodes which identifier (if any) is not an IRI. Hence identifiers of two blank nodes from two different data stores may collide. In the DQP context, blank nodes identifier collisions may occur either for unrelated nodes from two data sources that accidentally share the same identifier, or because a blank node was replicated over different stores. Since it is not possible to discriminate between these two cases automatically, we make the assumption that blank nodes between different sources always differ. If triples containing blank nodes need to be replicated, care should be taken to assign IRIs to these nodes before duplication (a process known as skolemization).

Redundant results: Finally, SPARQL can return some results multiple times in a result multiset, if same values match several graph patterns in the original query. In a distributed context, data replication is also likely to lead to redundant results if the same triple is accounted for several time in a query. However, this redundancy in results is only a side effect of data duplication that would disappear if data was aggregated in a single virtual graph. The query engine therefore needs to detect which redundant results are legitimate (products of the SPARQL evaluation) and which ones are side effects and should be filtered out.

Hybrid query rewriting

We use the following formalism to compute BGPs in our hybrid query evaluation strategy: the G1 operator describes all join operations (distributed and local) when evaluating a SPARQL query, the L1 operator corresponds to local joins computed by endpoints and the D 1 operator corresponds to distributed joins computed by the DQP server.

Let TP = {tp1, . . . , tpn} be the set of triple patterns from the WHERE clause of a SPARQL query and S1 . . . Sm be a set of RDF data sources interfaced through SPARQL endpoints: To illustrate these operators, let us consider the execution of query Q1 introduced in Section 2.2 (TP = {?team ns:team "SPARKS", ?team ns:group ?group, ?group ns:name ?name, ?group ns:members ?members}) over the two distributed data sources S1 and S2 described below: S1 S2 t1 ns:team "SPARKS" t1 ns:team "SPARKS" t1 ns:group g1 t1 ns:group g2 g1 ns:name "Modalis" g2 ns:name "Wimmics" g1 ns:members 12 g2 ns:members 9 t1 ns:group g3 g3 ns:name "MinD" g3 ns:members 7

• G1 (tp1, . . . ,
The 3 join operators defined above produce the following result sets when applied to the S1 and S2 distributed data sources:

Operators

Results retrieved L1 (T P ) { t1, "SPARKS", g1, "Modalis", 12} { t1, "SPARKS", g2, "Wimmics", 9} D1 (T P ) { t1, "SPARKS", g3, "MinD", 7} G1 (T P ) { t1, "SPARKS", g1, "Modalis", 12} { t1, "SPARKS", g2, "Wimmics", 9} { t1, "SPARKS", g3, "MinD", 7} Indeed, L1 (T P ) computes a join of all 4 triple patterns in TP in each data sources, producing one 4-items tuple for each of them (group named "Modalis" in S1 and group named "Wimmics" in S2). However, triples associated to the group named "MinD" are distributed between the two data sources and they do not match the L 1 local join. Conversely, D 1 (T P ) only accounts for distributed triple joins and therefore retrieves the remaining group. Finally, G1 (T P ) is the complete result set, resulting from the union of L1 (T P ) and D1 (T P ) results.

Global join decomposition

The G1 operator is associative and commutative [START_REF] Atre | Left Bit Right: For SPARQL Join Queries with OPTIONAL Patterns (Left-outer-joins)[END_REF][START_REF] Pérez | Semantics and complexity of SPARQL[END_REF]: ∀k < n, G1 (tp1, . . . , tpn) = G1 (tp1, . . . , tp k ) . G1 (tp k+1 , . . . , tpn) = G1 (tp k+1 , . . . , tpn) . G1 (tp1, . . . , tp k ) where " . " represents the binary operator for joins. Consequently, ∀k < n, G1 (tp1, . . . , tpn) = (L1 (tp1, . . . , tp k ) ∪ D1 (tp1, . . . , tp k )) .

(L1 (tp k+1 , . . . , tpn) ∪ D1 (tp k+1 , . . . , tpn)) This equation can be used to compute the global join operation through a combination of local and distributed joins. Two main cases can be considered. In the case where a source does not contain triples matching all triple patterns in TP, L1 (tp1 . . . tpn) is empty and G1 (tp1, . . . , tpn) ≡ D1 (tp1, . . . , tpn). But in the case where a source does not contain triples matching all TP patterns, the G1 operator can be computed as a join of several independent partial joins according to the distribution of triple patterns over sources. The partial joins can be computed as a union of partial L1 and D1.

Hybrid evaluation strategy

Our hybrid evaluation strategy is based on the idea of maximising the part of the query processed by the remote endpoints. It therefore pushes as much as possible SPARQL FILTER clauses into the sub-queries generated to improve partial results filtering at the source. It also exploits the local and distributed join operators composition properties shown above since the partial L1 operators size correspond to the evaluation of the largest possible BGPs at the endpoints level. However, this maximisation is constrained by the fact that TPs should be decomposed in disjoint subsets of triple patterns. The hybrid evaluation strategy requires prior knowledge on the data sources partitioning scheme to decide on the best triple patterns partitionning strategy.

Local joins generation strategy

Triple patterns which predicates are only available in vertical partitions are used to compose BGPs (one BGP per vertical partition) that can be evaluated independently. Among the remaining triple patterns, two criteria are considered with the aim of creating the largest possible BGPs to maximize the computation delegated to each endpoint:

1. Two triple patterns may be grouped into a BGP only when they contain common variables and therefore they represent inner-joins. Indeed in SPARQL, joining triple patterns without common variable corresponds to computing a Cartesian product between the triples matching each pattern. There is no interest in computing BGPs to reduce the number of results retrieved in this case.

2. The distribution of predicates inside horizontally partitioned data sources needs to be taken into account in order to generate the disjoint subsets of triple patterns to use in local joins. Let PH be the set of predicates that are horizontally partitioned among the data sources, we distinguish two cases for each data source:

• Global distribution: all predicates from PH are present in a source (triples matching all triple patterns may be found in this source). If there are common variables between all triple patterns, a global L1 (containing all shared triple patterns) will be generated for this source to handle local joins. Otherwise Triple-based evaluation is used.

• Partial distribution: predicates from PH are partially present in sources (only triples matching a subset of all triple patterns may be found in these sources). A partial L1 is generated for each source using the largest possible number of triple patterns with common variables. The remaining triple patterns (without common variables) will be evaluated through the Triple-based approach.

Each triple pattern should be applied to the target sources only once. Therefore, triple patterns which are already consumed in distributed and local joins are excluded from the L1 subsequently generated.

Distributed joins generation strategy

D1 operators aim at completing L1 query results by only processing distributed joins for horizontal partitions (there is no distributed join for vertical partitions). Thus, each L1 generated has a corresponding D1. For the L1 generation strategy, we distinguish between global D1, when the distribution of predicates is global in a given data source, and partial D1 when it is not.

Unlike the L1 operators, the evaluation of D1 operators computes query results built with at least two distributed sources. To avoid redundancy with query results already handled by L1, D1 operators need to ensure that the query results found are not local to a source (i.e only built with intermediate results from that source). This is implemented through a pruning algorithm that prevents retrieving the last intermediate results of a distributed query from a given data source when all the previous ones came from this same source.

DISTRIBUTED QUERY EXECUTION

KGRAM SPARQL engine

The Knowledge Graph Abstract Machine (KGRAM) [START_REF] Corby | The KGRAM Abstract Machine for Knowledge Graph Querying[END_REF] is an implementation of SPARQL 1.1. It is an open source project structured to be easily extensible. Its code is available from github2 . Among other extension points, KGRAM defines a data producer interface abstracting the data sources connected to the SPARQL server. Data producers may be traditional SPARQL endpoints, alternative database systems, or technical proxies used to connected various data sources.

In an earlier work, we leveraged the data producer interface to implement a meta-producer connecting to several data sources concurrently [START_REF] Corby | KGRAM Versatile Inference and Query Engine for the Web of Linked Data[END_REF].

Hybrid query evaluation strategy

In this work, the KGRAM DQP module has been revised to implement the hybrid optimisation strategy described in Section 3.2.2. In the warmup phase, the module queries remote data sources with SPARQL ASK queries for predicates contained in each of them, to determine the data partitioning scheme. At query execution time, the module computes the sub-queries BGPs and FILTER clauses.

Warmup step

The hybrid query evaluation algorithm makes use of 3 indexes:

• idxTPSources associates to each triple pattern a set of data sources hosting candidate RDF triples. It is used to determine which part of the data is horizontally and vertically partitioned.

• idxSourceTPs associates to each data source, triple patterns which are exclusive to it. It is used to determine if horizontal data fragmentation is total or partial.

• idxTPVariables associates to each triple pattern a set of variables used in this pattern. This index is used to check if several triple patterns have common variables.

From this information, the algorithm rewrites the original query into a set of sub-queries preserving the query semantics. The sub-queries are then evaluated on the remote endpoints and their results joined by the DQP server.

Data

EVALUATION

The evaluation of our KGRAM-DQP implementation addresses both the completeness of the results (with a minimal number of sub-queries processing), and query execution performance. The experiments proposed in this section aim at demonstrating the completeness of the results independently from the data partitioning scheme and the kind of SPARQL SELECT query executed. They are based on the querying of two linked RDF datasets, and a set of representative SPARQL queries covering most common SPARQL clauses. In each case, performance is measured in terms of number of sub-queries generated and computation time. All experiments are ran locally on a single dedicated quad-core laptop (Dell Latitude E6430 running Linux Ubuntu 14.04, 2.7 GHz Intel CPU i7-3740QM, 8 GB RAM) running all SPARQL endpoints and the KGRAM query engine, thus preventing any impact from the network load on performance measurements. To further alleviate any problem related to execution time variations that cannot be controlled in a multi-core multi-threaded execution environment, each experiment is re-executed 6 times and computation times averaged.

Experimental set up

The two experimental data sets used are French geographic 3In each run, our hybrid strategy (Hybrid), that implements BGP-based evaluation of both vertical and horizontal data partitions, is compared to the reference KGRAM implementation (Reference), that implements a triple-based evaluation strategy with BGP generation for vertical partitions only, similarly to other state-of-the-art KGRAM DQP engines. The correctness of the hybrid algorithm is checked first as all hybrid request produce exactly the same results as their reference counter-part. As can be seen, the hybrid strategy is consistently faster that the reference strategy in all cases, with execution time reduced by 1.9% to 76% depending on the test case. The number of sub-queries processed is consistently reduced.

Performance and complexity results

The impact of the hybrid approach depends on the efficiency of BGP-based evaluation which, in turn, depends on the distribution of data queried. Thus, the more L 1 retrieved results compared to D 1, the more efficient the hybrid approach.

In the P1 partitioning scheme, all data is duplicated in two sources. Local joins (L1) will therefore retrieve all the final results. However, the distributed joins (D1) processing is initiated to handle the possible distributed triples and finally deleted by the pruning algorithm to tackle the distributed redundancy issue. Even with this unnecessary processing time, the hybrid approach reduced the processing time by 33% to 53% and the number of sub-queries by 41% to 97% depending on the test query.

In the P2 partitioning scheme, there is no data duplication, and data predicates are globally distributed. More results are retrieved through distributed joins processing. Execution times are consequently higher than in the previous case. The experiments still show a reduction of the processing time by 2.1% to 20% and a reduction of the number of sub-queries by 19% to 48%.

Owing to partial distribution, the P3 partitioning scheme exhibits less selective expressions (partial BGPs) than in the P2 case (global BGP), with a higher chance of matching more results. This explains why the results of the hybrid approach with P3 is more efficient than the results with P2. Furthermore, since the distributed joins are less selective in this case, the pruning algorithm is applied earlier than in the P1 case, which explains why results are improved. In this case, the hybrid approach reduces the processing time by 31% to 80% and the number of sub-queries by 41% to 97%.

CONCLUSIONS

In this paper, we proposed a query semantics for SPARQL queries applied to distributed linked RDF data set and a hybrid query evaluation algorithm to improve performance of DQP queries. Queries are interpreted as if they were ran on a single virtual RDF graph defined as the set union of all target data sets. Replicated data are consistently accounted only once in the query evaluation, named graph sharing the same identifier are considered as identical and blank nodes are considered unique in the complete data set. The query evaluation algorithm proposed decomposes the query into BGP-and Triple Pattern-based SPARQL sub-queries with filters. It aims at maximising the amount of processing handled by the remote endpoints and minimising the amount of data transferred to the DQP server. The strategy implemented delivers improved results in all kinds of data partitioning schemes and all types of SPARQL queries investigated.

Other query optimisation techniques can be considered to further improve the performance of the KGRAM-DQP engine, in particular better source selection and improved sub-queries ordering heuristics. Another important milestone in the future will be to test the KGRAM-DQP engine in a networked environment to assess the impact of network communications in the query process. KGRAM-DQP also needs to be tested against established benchmarks, such as FedBench [START_REF] Schwarte | Fedx: optimization techniques for federated query processing on linked data[END_REF], and compared to existing competitors for query expressiveness and performance.

1 8 }

 8 PREFIX ns : <h t t p : / / examples . f r / team#> 2 SELECT ?name ? members 3 WHERE { 4 ? team ns : team "SPARKS" . 5 ? team ns : group ? group . 6 ? group ns : name ?name . 7 ? group ns : members ? members .This query is composed of 4 triple patterns (TPs) in lines 4 to 7, defining different query patterns for the RDF graph triples, and implicit join operations, when a variable appears in two different TPs.

Figure 1

 1 Figure 1: DQP engine Client

Figure 2

 2 Figure 2 displays the performance (execution and processing time) and workload (number of sub-queries generated) for each test query and each partitioning scheme. The execution times shown in Figure 2 (top) are averaged execution time and error bars represent ± 1 standard deviation. The Figure displays groups of 12 measurements for each type of query, shown in the following order: simple SELECT, UNION, MINUS, FILTER, OPTIONAL, and all combined. Each group of 12 measurements is composed of 6 first measurements related to Execution time and 6 last measurements related to Processing time. Each group of 6 measurements shows the Reference and the Hybrid implementations execution time for partitioning schemes P1 (duplication), P2 (global distribution) and P3 (partial distribution). Similarly, Figure 2 (bottom) shows the number of sub-queries processed for each test query. Measurements are further analyzed by partitioning scheme.As can be seen, the hybrid strategy is consistently faster that the reference strategy in all cases, with execution time reduced by 1.9% to 76% depending on the test case. The number of sub-queries processed is consistently reduced.The impact of the hybrid approach depends on the efficiency of BGP-based evaluation which, in turn, depends on the distribution of data queried. Thus, the more L 1

Figure 2 :

 2 Figure 2: Top: query processing time. Bottom: sub-queries generated

  : idxTPSources, queryExpr Result: the set of SPARQL query results foreach tripleP attern ∈ queryExpr do if ( idxT P Sources.get(tripleP attern).size() > 1 )Algorithm 1 describes how BGP expressions are rewritten as unions of L1 and D1 operators, if data is horizontally partitioned, or as a unique L 1 (for each source) if data is vertically partitioned. The input for this algorithm is a queryExpr expression containing the list of triple patterns and the FILTER clauses from the original SPARQL query. Algorithm 3 executes the local and distributed join operations for each triple pattern in the query.

		4.2.3 Query evaluation step
		evaluate:
	Data: idxSourceTPs, idxTPVariables, queryExpr, sourceSet Result: exprResult rewritten query if (globalDistribution(sourceSet, queryExpr, idxSourceTPs)) then if (commonVariables(queryExpr, idxTPVariables))	resultT riples ← ; foreach expr ∈ exprResult do switch expr.getT ype() do case UNION do resultsT riples ← join(resultsT riples, evaluate(expr.lef tOp(), expr.rightOp());
	then	end
	return union(createL1 (queryExpr),	case D1 do
	createD1 (queryExpr));	resultsT riples ← join(resultsT riples,
	else no common variable	evaluateD1 (expr.getT ripleP atterns());
	return queryExpr;	end
	end	case L1 do
	else partial distribution sourceSet.sortByN umberOf P redicates();	resultsT riples ← join(resultsT riples, evaluateL1 (expr.getT ripleP atterns());
	exprResult ← ;	end
	BGP T P List ← ;	end
	foreach s ∈ sourceSet do	end
	tps ← idxSourceT P s.get(s);	return resultT riples;
	if (commonVariables (tps, idxTPVariables)) then ctps = cleanBGP (tps); BGP T P List.add(ctps);	evaluateL1: writes a query with all triple patterns in the expression and sends it to sources containing all edges related to these triple patterns.
	exprResult ← join(exprResult,	evaluateD1 (Algorithm 4): evaluates a set of triple
	union(createL1 (ctps),	patterns in a nested loop join way by writing a query
	createD1 (ctps)));	for each triple pattern, and avoids redundancy by
	end	pruning.
	end f ree T P List ← set substract(queryExpr, BGP T P List);	Algorithm 3: (createL1UnionD1) decomposes joins in a union of local and distributed joins.
	return
	join(exprResult, createD1 (f ree T P List));	then
	end	return
	where:	evaluate(createL1U nionD 1 (queryExpr)); end
	globalDistribution: returns true if all sources contain	end
	triple candidates for all triple patterns in BGPExpr.	return serviceClause(createL1 (queryExpr));
	commonVariables: returns true if a set of patterns	where:
	share variables (and therefore describe a join operation).	serviceClause: generates a SPARQL query with a SERVICE clause to send this BGP to a specific source.
	createL1: creates a BGP expression from a set of triple patterns forming a BGP and add applicable filters from the original query.	createL1UnionD1 (Algorithm 2): joins decomposition.
	createD1: creates a triple-based join expression and add applicable filters from the original query.	evaluate: handles evaluation as explained in section 4.2.3.
	cleanBGP: deletes the triple patterns already handled by another L1 or D1 from a set of triple patterns to keep L1 operators or D1 operators disjoint.	Algorithm 1: determines the joins decomposition strat-egy from a set of triple patterns and the data partitioning scheme.
	Algorithm 2: (createL1UnionD1) decomposes joins in
	a union of local and distributed joins.	4.2.2 Query rewriting step

RDF: http://www.w3.org/TR/rdf11-concepts

KGRAM github repository: https://github.com/ Wimmics/corese

INSEE geographic data set: http://rdf.insee.fr/geo/ cog-2014.ttl.zip

ACKNOWLEDGMENTS

This work was partly funded by the French Government (ANR National Research Agency) through the "Investments for the Future" Program, reference #ANR-11-LABX-0031-01 (Labex UCN@Sophia).

To reproduce a context of both vertical and horizontal partitioning of data, the demographic data set is vertically partitioned (source S1) and the geographic data set is horizontally partitioned in three test cases:

• P1 partitioning (data duplication): the geographic data is duplicated into two distributed sources (S2 and S3), each containing a complete copy of the data. This test case aims at evaluating the handling of redundant results by each evaluation method.

• P2 partitioning (global distribution of predicates): the geographic data is partitioned into two sources (S4 and S5), each containing all predicates related to this data.

• P3 partitioning (partial distribution of predicates): the geographic data is partitioned into three sources (S6, S7 and S8), each containing a subset of predicates related to this data.

The first partitioning aims at testing the handling of redundant results by all evaluation methods, and the two last ones aim at testing the global and partial distribution strategies introduced in Section 3.2.3. The data partitions are summarized in Table 1.

Six evaluation queries (shown below) were selected as a representative set of SPARQL queries covering the most common clauses: the first query is made of a simple SE-LECT clause, the second one introduces a UNION, the third one a MINUS, the fourth one FILTERs, the fifth one an OPTIONAL clause, and the last one is a combination of all clauses. In all evaluations queries, the geographical predicates are prefixed by geo (http://rdf.insee.fr/def/geo) and the demographical predicates are prefixed by demo (http: //rdf.insee.fr/def/demo#). These queries are variations around listing the population count in diverse sub-geographical areas.

Query QSELECT : Several metrics are reported for each experiment to measure computing efficiency, both in term of execution time and amount of queries generated:

• Execution time: total execution time measured on the DQP server.

• Processing time: query execution time, excluding the query analysis and rewriting times.

• # sub-queries: number of sub-queries sent to endpoints for evaluation.


Yinghao Li
email: yinghao.li@oin-paris-saclay.fr

Fabrice Rodriguez

Emmanuel Berthier

Development of the Integrated Urban Hydrological Model URBS: Introduction and Evaluation of a Transfer Module in the Saturated Zone

Keywords: Urban hydrology, groundwater drainage, integrated model, URBS, distributed, saturation

published or not. The documents may come

L'archive ouverte

Development of the Integrated Urban Hydrological Model URBS: Introduction and Evaluation of a Transfer Module in the Saturated Zone

Yinghao LI1,3* , Fabrice RODRIGUEZ2 , Emmanuel BERTHIER 3

INTRODUCTION

Progress in the understanding of hydrological processes on urban catchments and new challenges in urban water management face to climate change stimulate the development of best management practices for stormwater [START_REF] Marsalek | Fifty years of innovation in urban stormwater management: Past achievements and current challenges[END_REF]. These new practices, favoring infiltration of rainwater in the soil, require more understanding of urban water cycle as well as development of integrated modelling tools capable of considering urban hydrological processes as a whole.

Urban runoff as a reaction to storm events depends not only on characteristics of the precipitation it-self but also pre-event moisture state under the ground. This well-know relation in rural catchments hydrology can be extended to urban catchments, despite of the main contribution of impervious surfaces to water runoff. From this point of view, urban soils, recharged continuously by infiltration from land surface, can no longer be neglected in urban runoff analysis, as suggested in [START_REF] Berthier | The role of soil in the generation of urban runoff: development and evaluation of a 2D model[END_REF]. Under influences of underground infrastructures such as the sewer networks, circulation of subsurface water is far from being easily understood. Interactions between sewer system and groundwater remain current topic of research. Groundwater flow representation as an integrated part should be benefit for an urban hydrological modelling tool. The present paper shows a work dedicated to the development of an integrated urban hydrological model. A groundwater flow module is introduced to the URBS model in order to represent water flux of the saturated zone in an adequate and parsimonious manner.

MODEL DEVELOPMENT

A brief recall of the URBS model URBS, short for Urban Runoff Branching Structure, is a distributed hydrological model for urban catchment developed since about 10 years. Detail model descriptions could be found in [START_REF] Rodriguez | A distributed hydrological model for urbanized areas -Model development and application to case studies[END_REF].

Based on urban data banks, URBS models the rainwater fluxes and hydric states of urban soil (saturation level, storage capacity) at the parcel scale, and then coupled with a detailed description of the hydrographic network. A parcel, acting as an urban hydrological element (UHE), is divided into three vertical profiles based on land use: natural soil, street and house. Each profile is composed of four reservoirs representing respectively trees, ground surface, vadose zone and saturated zone. The model capability to correctly simulate flow rate and saturation levels has been proved for Rezé and Gohards catchment of Nantes city [START_REF] Morena | Modélisation hydrologique distribuée en milieu urbanisé[END_REF][START_REF] Rodriguez | A distributed hydrological model for urbanized areas -Model development and application to case studies[END_REF].

Soil processes modelling in URBS and implementation of the saturation module WTI

The soil is represented through a parameterization of the vadose zone and the saturation deficit. Sewer system is represented by its drainage effect for groundwater. The hydraulic conductivity at saturation is Ks nat is assumed to be isotropic and decrease exponentially with depth, as inspired by work on Top Model [START_REF] Beven | A physically based, variable contributing area model for basin hydrology[END_REF].

Lateral flow of the saturated zone between adjacent UHEs is not represented in URBS and the saturation level could be abruptly different from one UHE to another. An attempt on coupling URBS and MODFLOW ® has been realized by [START_REF] Delliou | A study of sewer network impact on urban groundwater by hydrological modelling. 8UDM[END_REF]. The coupling results were not totally satisfying due to various reasons among which we can quote the difference in soil conception in the two models. A suitable approach for developing the saturation modeling should keep the soil configuration of URBS as well as its spatial discretization. [START_REF] Branger | Utilisation d'une plate-forme de modélisation environnementale pour représenter le rôle d'aménagements hydro-agricoles sur les flux d'eau et de pesticides -Application au bassin versant de la Fontaine du Theil[END_REF] developed, for the platform LIQUID, a water transfer module that can simulate lateral flows among irregular flow-generation elements. The so-called WTI (Water Transfer Interface) module has proved to be adequate and robust [START_REF] Branger | Utilisation d'une plate-forme de modélisation environnementale pour représenter le rôle d'aménagements hydro-agricoles sur les flux d'eau et de pesticides -Application au bassin versant de la Fontaine du Theil[END_REF][START_REF] Jankowfsky | Development of a suburban catchment model within the LIQUID® framework[END_REF]. Considering the similarity between the flow-generation elements in LIQUID and UHEs in URBS, we adopted the WTI module for URBS. Figure 1 illustrates the principles of the module implementation. At each time increment, water flow between adjacent UHEs A and B is calculated basing on Darcy's law that is applied on their intersection surface, called "interface". Darcy's equation is given by: where Q A→B is the water flow from UHE_A to UHE_B that can be positive or negative, K int the hydraulic conductivity applied on the interface, S the area of the interface, H A and H B the hydraulic heads, d A + d B the distance of the geometry centers of the UHEs. With respect to the initial model, K int kept the exponential decay in depth. Thus, the volumetric flux through the whole interface was the integration of the flux through each unit surface of the interface.

In URBS, water table is modeled by saturation deficit and substratum is not represented. This

2 Q A→ B =K int . S. H A -H B d A +d B Figure 1. Schematic diagram of the implementation of WTI in URBS.
configuration has been kept for WTI module, i.e. no bottom limit was set for an interface. The total flow through an interface was computed by the improper integral of elemental flows on the interface, as illustrated in Figure 1, and expressed as:

where l is the length of the interface and z wet the wet level of the interface, which is estimated by the weighted average of groundwater levels of UHE_A and UHE_B. Since the limit to -∞ of exponential is 0, the integral converges and the antiderivative is given by: At the end of each time step, the equation was applied for every interface. The total quantity of water in or out of one UHE was obtained by summing on its interfaces with neighbor UHEs. The saturation level of the UHE was then updated for the next time step.

MODEL EVALUATION ON A BASE RUN Methodology for application and evaluation

In order to evaluate the impact of the saturated module to the model (URBS-WTI herein after), a base run has been carried out on Pin Sec catchment for the period 01/01/2006-31/12/2010 at a 5-min time step (Figure 2).

Pin Sec is an urban catchment located in the East part of Nantes city in France. As an experimental catchment of the ONEVU ("Nantes observatory of urban environments"), part of the research federation IRSTV, Pin Sec contains a separated sewer network and has been monitored since several years. The data measured comprises: (i) rainfall intensity; (ii) water table level observation by eight piezometers; (iii) discharge at the outlet of the rainwater drainage network; and (iv) climate data such as Penman-Monteith evapotranspiration.

The urban catchment of Pin Sec is contained in a hydrogeological watershed (120 ha) which is delimited topographically. The model was applied on the whole hydrogeological watershed for which a zero-flux boundary condition has been set. Given the proximity of Pin Sec to Rezé and Gohards catchments (see "A brief recall of the URBS model"), the same parameter values (Table 1) have been kept for the base run. Only the parameters related to WTI module are retained in Table 1. Evaluation of the saturation module focused on four types of results: (1) water budget, (2) volumetric discharge at the stormwater network outlet during rainfall events, (3) saturation levels at the piezometers and (4) standard deviation of the simulated saturation levels of the UHEs.

3

Q A→ B = ∫ z wet ∞ -K s .l. H A -H B d A +d B .exp (-z / M )dz Q A→ B =K s l . M. H A -H B d A +d B .exp (-z wet / M )

Results of the base run

Water budget evaluation. With WTI implemented, the model produced almost the same water budget as its initial version, as illustrated in Table 2. Evapotranspiration (ET) represents more than 40% of the total rainfall. Natural land use, as well as impervious surfaces, contributes to runoff. This natural soil contribution, somewhat surprising by its importance (16.6%), is coherent with the results for Rezé catchment presented in [START_REF] Morena | Modélisation hydrologique distribuée en milieu urbanisé[END_REF], where natural soil runoff amounts to 10% of the total rainfall with initial parameters before calibration.

Groundwater drainage (Qdrain) represents 9.9% of the total rainfall, as divided between the wastewater (6.6%) and stormwater (3.3%) networks.

Discharge simulation. Comparisons of flow volume during rainfall events were based on three criteria: bias criterion (Cb), Nash criterion (denoted Cnash) and the determination coefficient R², as showed in Table 3. The WTI module did not a priori change flow rate simulation of URBS, with relatively low Cb as well as high Cnash and R².

Saturation level simulation. Simulated saturation level at each piezometer is obtained by the average of UHEs situated within a 50-meter circle. The variations in simulated saturation level have certain agreements with observations for both URBS and URBS-WTI, with a mean R² value of 0.7 (Table 3). However, the simulations overestimated saturation levels in the piezometers, with weak Cnash (not presented here). Homogeneous effect of WTI. Figure 3 shows the standard deviation σ of the ground water levels in the UHEs simulated by URBS and URBS-WTI. With WTI, the model had the σ slightly reduced. Seasonal variations of σ have not been palliated. One possible explication is the relative shallow level of the groundwater: compared to climate factors such as precipitation, subsoil water flow may play less important roles to the groundwater level. Summary of the model base run. The base run results of URBS-WTI for the 5-year period with default parameter values were not totally satisfying and revealed a couple of information:

(1) the new module WTI did not influence the general behavior of URBS model (neither deteriorate its simulation quality); (2) contrary to our exceptions, the homogenization effect of the saturation module was not important. The flow exchange generated by WTI module seemed to be overtaken by other processes. In adjusting some parameter values, the model should function differently. A parameter sensitivity study presented below will show us if the model sensitivity has been impacted by the saturation module, as well as if some of the parameters could strengthen its homogenization effect.

SENSITIVITY ANALYSIS Methodology

The model sensitivity should not be different but only for parameters that operate on WTI module, i.e. the hydraulic conductivity at saturation Ks nat and its scaling parameter M, controlling the exponential decrease of the hydraulic conductivity. Given the direct control of the lateral conductivity on WTI flows but not the vertical one, a new parameter Ks lat was introduced to present the lateral hydraulic conductivity. The drainage coefficient λ controls water drainage by sewer network and must have direct impact on groundwater levels.

The simulations have proved to be quite time and memory consuming. Meanwhile, [START_REF] Morena | Modélisation hydrologique distribuée en milieu urbanisé[END_REF] has demonstrated that the model warm-up period was less than 3 months. For these reasons, the sensitivity analysis was based on one-year simulation of 2010. The one-factor-at-time method has been adopted to evaluate the effect of each parameter. The results of each simulation were compared to the base run results based on the outlet flow volume during rainfall events and the saturation levels of the piezometers. For the saturation levels, the criteria (Cb, Cnash and R²) are represented by their mean value of the eight piezometers. For each parameter set, the results of URBS and URBS-WTI were compared.

Results and discussion

Some 40 tests have been taken out with different combinations of values for the three parameters mentioned above. Table 4 summarizes the most meaningful results.

Regarding the model parameter sensitivity, URBS-WTI has not changed much compared to URBS. Both models are sensitive to soil parameters, especially for values which increase water flows, i.e. strong values of Ks lat , M and λ. Meanwhile, with high water flows, URBS-WTI tends to get better results than URBS for flow rate: criteria values had a tendency to be higher. R² of saturation levels are also improved by WTI. Cnash of saturation levels are still weak. This could be explicated by the fact that Nash criterion is more influenced by strong bias. In adjusting certain parameter values, we were able to upgrade Cnash for certain piezometers. But improving the simulation quality for every piezometer at the same time was pratically impossible. Note that the saturation level has been initialized uniformly at the watershed, a distributed saturation level initialization seems worth to be tried.

Based on the sensitivity study results, the "best" parameter set was defined (Table 5). With the calibrated parameter values, criteria values have risen significantly for saturation levels, and in a slight manner for runoff volume (Table 5). Figure 4 illustrates saturation levels at each piezometer simulated both by URBS and URBS-WTI, compared to measurement data. Simulations of Pz3 and Pz5 had satisfying agreement with the observations both in temporal evolution and in absolute water table level, except the fact that some certain increase and decrease were not well reproduced. Pz1, 2, 4, and 7 were well reproduced for their seasonal evolutions, but not the absolute saturation levels. Simulations of Pz6 and Pz8 were mediocre.

As mentioned in the previous paragraph, seeking better simulations results for some of the piezometers in adjusting parameter values were always accompanied by deteriorating simulations in other piezometers. The "best" parameter set was selected from a general view on comparing the criteria values. As for sharp increase and decrease in observation data that were not reproduced, [START_REF] Rodriguez | A distributed hydrological model for urbanized areas -Model development and application to case studies[END_REF] proposed two explications. Whether it is due to climate reasons, e.g. dry (wet) periods causing rapid decrease (increase) groundwater levels that could not be reproduced by the model, or to observation data, e.g. natural variations being fluctuated by unnatural factors (underground construction for example), the phenomena is worth of examinations in future studies. Performance regarding the flow rate has been kept, strong agreement as found between simulation and observation during rainfall events with low values of bias criterion and high values of Cnash and R².

Generally speaking, with WTI the model has improved its capability to simulate groundwater level: the simulated saturation levels by URBS-WTI agreed better to measurement data than that by URBS, except for Pz2 where the two models have given almost the same curve.

Figure 5 illustrates the standard deviation of the simulated saturation levels of the UHEs by the calibrated run. With WTI, saturation levels seem to be efficiently homogenized. Further statistical analysis on the distribution of the saturation level over the catchment through more powerful mathematic methods may be interesting and will be subject of future studies.

Water budget with this calibrated parameter set is presented in Table 6. The main contribution to runoff stems from impervious surfaces, with 16.7% from roofs and 10.3% from streets; the natural soil contribution to flow rate is close to zero. Groundwater drainage by sewer network reached to 30% of the rainfall, which is consistent with the results found other studies [START_REF] Braud | Evidence of the impact of urbanization on the hydrological regime of a medium-sized periurban catchment in France[END_REF][START_REF] Hollis | The quantity of stormwater runoff from ten stretches of road, a car park and eight roofs in Hertfordshire, England during 1983[END_REF][START_REF] Rodriguez | A distributed hydrological model for urbanized areas -Model development and application to case studies[END_REF]. This result reconfirmed the important drainage role of the underground sewer network to soil water.

CONCLUSION

This study has presented a development of the integrated urban hydrological model URBS. A saturation module has been implemented into the model. This module computes water transfer between two water production units (UHEs) corresponding to urban parcels. This module uses Darcy's law that is applied on all the interfaces of two UHEs. The modelling results were compared to piezometric and flow observations on the experimental catchment of Pin Sec based on various criteria. The comparisons confirmed the effectiveness of the module to reproduce saturation levels, particularly its homogenization effect, while keeping the performance in simulating flow rate and water budget of the initial model. The modelling results confirmed the drainage role of sewer network on groundwater. Meanwhile, the assumption according to which water circulation within the urban saturated zone is fully controlled by sewer networks need further examination, as sharp increase and decrease on the observation curves have not been able to be reproduced by the model. Other processes rather than drainage need to be examined.

The evaluation of such module proved to be difficult. On one hand, numerous available observation data by piezometers offered us large possibilities to compare the simulation results; on the other hand, the different evolutions in the piezometric observation made it impossible for the model to reproduce. Urban soil can be highly heterogeneous and groundwater circulations could be quite complex and controlled by various factors, including human activities. Considerations of these factors into the model would be beneficial, but challenging. A comparison with a more detailed 2D-3D groundwater model, such as models based on variable Richard's equation, would possibly offer another angle for judging the performance of URBS-WTI. But representing underground facilities in such models would not be easy work.

In the context of rapid progress in sustainable stormwater management, integrated modelling tools capable of representing the whole water cycle, including subsurface water circulations controlled by drainage processes, as URBS-WTI, could offer a model coupling example and contribute to urban hydrological modelling development.

Figure 2 .

 2 Figure 2. Hydrogeological watershed of Pin Sec.

Figure 3 .

 3 Figure 3. Standard deviation of the ground water level (GWL) simulated by URBS (dotted line) and URBS-WTI (solid line).

Figure 5 .

 5 Figure 5. Standard deviation of the groundwater level simulated by WTI (dashed line) and by URBS-WTI (solid line).

Figure 4 .

 4 Figure 4. Saturation levels observed in piezometers (solid lines) and simulated by URBS (dotted lines) and by URBS-WTI (dashed lines) for the calibrated run.

Table 1 .

 1 Physical parameters and values of URBS-WTI on Pin Sec watershed.

	Parameter	Unit	Description	Value	Variation range
	Ks nat	m/s	Hydraulic conductivity at saturation of the natural land use	1.3e-5	0.2 -3
	M	-	Scaling parameter of the hydraulic conductivity	0.2	1.e-8 -1.e-4
	λ	-	Groundwater drainage coefficient	4	0.05 -10
	Zs_ini	m	Initial uniformed saturation level for the catchment	0.65	0 -100

Table 2 .

 2 Water budget simulated by the base run, expressed in percentage of the rainfall.

		Qroof	Qstr	Qnat	Qdrain	ET	∆storage	P
	URBS/URBS-WTI	16.6	13.9	13.6	9.9	44.9	1.1	100

Table 3 .

 3 (1) Comparison criteria of runoff volumes during rainfall events at the stormwater network outlet of Pin Sec; (2) R² of saturation levels of the eight piezometers (Pz1 -Pz8).

		Runoff		Cb		Cnash		R²
	URBS/URBS-WTI			0.20/0.21		0.724/0.719		0.856/0.863
	Pz1	Pz2	Pz3	Pz4	Pz5	Pz6	Pz7	Pz8	mean
	URBS/URBS-WTI 0.54/0.54 0.74/0.74 0.64/0.64 0.58/0.58 0.54/0.54 0.83/0.83 0.82/0.82 0.88/0.88 0.70/0.70

Table 4 .

 4 Results of the sensitivity analysis.

					Saturation levels			Runoff volume
				Cb	Cnash	R²	Cb	Cnash	R²
	Ref (Ks nat =1.3e-5; M=0.2; λ=4)	-0.72/-0.73	-33.9/-35.4	0.700/0.700	0.20/0.21	0.724/0.719 0.856/0.863
	Ks lat 1e-4 URBS/URBS-WTI -0.64/-0.63	-26.0/-26.1	0.867/0.868	0.04/0.05	0.889/0.890 0.916/0.922
		1e-6 URBS/URBS-WTI -0.76/-0.73	-38.4/-35.3	0.749/0.776	0.37/0.38	0.410/0.399 0.788/0.795
	M	0.1 URBS/URBS-WTI -0.73/-0.73	-35.2/-35.2	0.762/0.762	0.31/0.31	0.541/0.535 0.829/0.829
		2	URBS/URBS-WTI -0.50/-0.43	-14.9/-13.5	0.844/0.821	0.07/0.08	0.882/0.897 0.915/0.932
	λ	0	URBS/URBS-WTI -0.78/-0.76	-41.5/-40.1	0.660/0.701	0.08/0.53	0.082/0.167 0.522/0.832
		30 URBS/URBS-WTI -0.65/-0.65	-27.3/-27.3	0.786/0.786	0.04/0.04	0.889/0.889 0.916/0.916

Table 5 .

 5 Comparison criteria for simulation with calibrated parameters.

	Calibrated parameter values: Ks lat =1.3e-5 m/s; M=2; λ=30
		Saturation level		Runoff volume
	Cb	Cnash	R²	Cb	Cnash	R²
	URBS/URBS-WTI -0.13/-0.07	-4.54/-2.91	0.656/0.733	-0.06/-0.03	0.901/0.904	0.913/0.917

Table 6 .

 6 Water budget simulated by calibrated run, expressed in percentage of the rainfall.

		Qroof	Qstr	Qnat	Qdrain	ET	∆storage	P
	URBS/URBS-WTI	16.7	10.3	0.4	30.9	37.2	4.5	100

Établissement Public Paris-Saclay, 6BD Dubreuil 91400 Orsay, France

 44344 Bouguenais Cedex, France

Cerema, France

ACKNOWLEDGEMENT

This study is financed by research foundation of Paris region and Établissement public Paris-Saclay.