Gabriela Montoya

Hala Skaf-Molli

Pascal Molli

Maria-Esther Vidal
email: mvidal@ldc.usb.ve

Efficient Query Processing for SPARQL Federations with Replicated Fragments

Keywords: SPARQL Federation, Replicated Fragments, Source Selection #DBpedia Execution Time (ms)

Low reliability and availability of public SPARQL endpoints prevent real-world applications from exploiting all the potential of these querying infrastructures. Fragmenting data on servers can improve data availability but degrades performance. Replicating fragments can offer new tradeoff between performance and availability. We propose FEDRA, a framework for querying Linked Data that takes advantage of client-side data replication, and performs a source selection algorithm that aims to reduce the number of selected public SPARQL endpoints, execution time, and intermediate results. FEDRA has been implemented on the state-of-the-art query engines ANAPSID and FedX, and empirically evaluated on a variety of real-world datasets.

Introduction

Linked Data [START_REF] Bizer | Linked data -the story so far[END_REF] provides millions of triples for data consumers, however, recent studies suggest that data availability is currently the main bottleneck to the success of the Semantic Web as a viable technology [START_REF] Aranda | Sparql web-querying infrastructure: Ready for action?[END_REF][START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF]. Particularly, it has been reported by Buil-Aranda et el. [START_REF] Aranda | Sparql web-querying infrastructure: Ready for action?[END_REF] that only one third of the 427 public SPARQL endpoints have an availability rate equal or greater than 99%; representing this limitation the major obstacle to developing Web real-world applications that access Linked Data by using these infrastructures. Recently, the Linked Data Fragments (LDF) approach [START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF][START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF] has addressed availability issues by delegating query processing to clients, and by transforming public endpoints into simple HTTP-based triple-pattern fragments providers that can be easily cached by clients. This tradeoff effectively improves data availability, but it can significantly degrade performance [START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF]. However, we speculate that fragments caching approaches like LDF can have two important consequences for consuming Linked Data: (i) Each client is able to process SPARQL queries on replicated fragments cached from servers. Consequently, if clients are ready to cooperate, the cost of executing SPARQL queries can be significantly reduced, and a new compromise between availability and performance can be achieved. (ii) Potentially, clients could cache triple-pattern fragments from different data providers creating new localities for federated queries. Therefore, some joins can be now executed on one machine without contacting the public endpoints. This vision is also clearly proposed by Ibañez [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF], where triple-pattern fragments can be replicated from SPARQL public endpoints, modified Table 1: Execution time and results for the same query over one and two replicas of DBpedia for FedX and ANAPSID locally, and made available through consumer data endpoints. Approaches in [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF][START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF] demonstrate how SPARQL processing resources and simple triple-based fragments can be obtained from data consumers. We believe this represents a new opportunity for federated query processing engines to improve SPARQL query processing performance by taking advantage of opportunistic replication and SPARQL processing offered by data consumers.

However, current SPARQL federated query engines [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF][START_REF] Basca | Avalanche: Putting the spirit of the web back into semantic web querying[END_REF][START_REF] Görlitz | Splendid: Sparql endpoint federation exploiting void descriptions[END_REF][START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF][START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF] may exhibit poor performance in presence of replication. As presented in Figure 1, we duplicated DBpedia and executed a three triple pattern query against one instance and next two instances of DBpedia. We can observe that the performance in terms of execution time and number of results is seriously degraded. This problem has been partially addressed by recent duplicate-aware source selection strategies [START_REF] Hose | Towards benefit-based RDF source selection for SPARQL queries[END_REF][START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF]. The proposed solutions rely on summary of datasets to detect overlapping and do not consider fragments [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF][START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF][START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF]. With fragments, replication is defined declaratively and does not need to be detected.

In this paper, we propose FEDRA, a source selection strategy that exploits fragment definition to select non-redundant data sources. In contrast to [START_REF] Hose | Towards benefit-based RDF source selection for SPARQL queries[END_REF][START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF], FEDRA does not require information about the content of the data sources to detect overlapping. FE-DRA just relies on knowledge about the endpoint replicated fragments to reduce the number of endpoints to be contacted, and delegate join execution to endpoints. FEDRA implements a set covering heuristic [START_REF] Dasgupta | Algorithms[END_REF] to minimize the number of sources to be contacted. The implemented source selection approach ensures that triple patterns in the same basic graph pattern are assigned to the same endpoints, and consequently, it reduces the size of intermediate results. We extend the state-of-the art federated query engines FedX [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF] and ANAPSID [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF] with FEDRA, and compare these extensions with the original engines. We empirically study these engines and the results suggest that FEDRA efficiently reduces the number of public, replicated endpoints, and intermediate results. The paper is organized as follows: Section 2 presents related works. Section 3 describes FEDRA and the source selection algorithm. Section 4 reports our experimental results. Finally, conclusions and future works are outlined in Section 5.

Related Work

In distributed databases, data fragmentation and replication improve data availability and query performance [START_REF] Özsu | Principles of distributed database systems[END_REF]. Linked Data [START_REF] Bizer | Linked data -the story so far[END_REF] is intrinsically a federation of autonomous participants where federated queries are unknown from a single participant, and a tight coordination of data providers is difficult to achieve. This makes data fragmentation [START_REF] Özsu | Principles of distributed database systems[END_REF] and distributed query processing [START_REF] Kossmann | The state of the art in distributed query processing[END_REF] of distributed databases not a viable solution [START_REF] Umbrich | Comparing data summaries for processing live queries over linked data[END_REF] for Linked Data.

Recently, the Linked Data fragments approach (LDF) [START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF][START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF] proposes to improve Linked Data availability by moving query execution load from servers to clients. A client is able to execute locally a restricted SPARQL query by downloading fragments required to execute the query from an LDF server through a simple HTTP request. This strategy allows clients to cache fragments locally and decreases the load on the LDF server. A Linked Data Fragment of a Linked Data dataset is a resource consisting of the dataset triples that match a specific selector. A triple pattern fragment is a special kind of fragments where the selector is a triple pattern; a triple pattern fragment minimizes the effort of the server to produce the fragments. LDF chose a clear tradeoff by shifting query processing to clients, at the cost of slower query execution [START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF]. On the other hand, LDF could create many data consumers resources that hold replicated fragments in their cache and is able to process SPARQL queries. This opens the opportunity to use these new resources to process SPARQL federated queries. FEDRA aims to improve source selection algorithm of federated query engine to consider these new endpoints, and decreases the load on public endpoints.

Col-graph [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF] enables data consumers to materialize triple pattern fragments and to expose them through SPARQL endpoints to improve data quality. A data consumer can update her local fragments and share updates with data providers and consumers. Colgraph proposes a coordination free protocol to maintain the consistency of replicated fragments. Compared to LDF, Col-graph clearly creates SPARQL endpoints available for other data consumers, and allows federated query engines to use local fragments. As for LDF, FEDRA can take advantage of these data consumer resources.

Recently, HiBISCuS [START_REF] Saleem | Hibiscus: Hypergraph-based source selection for SPARQL endpoint federation[END_REF] a source selection approach has been proposed to reduce the number of selected sources. The reduction is achieved by annotating sources with the URIs authorities they contain, and pruning sources that cannot have triples that match any of the query triple patterns. HiBISCuS differs from our aim of both selecting sources that are required to the answer, and avoiding the selection of sources that only provide redundant replicated fragments. While not directly related to replication, Hi-BISCuS index could be used in conjunction with FEDRA to perform join-aware source selection in presence of replicated fragment.

Existing federated query engines [START_REF] Acosta | Anapsid: An adaptive query processing engine for sparql endpoints[END_REF][START_REF] Basca | Avalanche: Putting the spirit of the web back into semantic web querying[END_REF][START_REF] Görlitz | Splendid: Sparql endpoint federation exploiting void descriptions[END_REF][START_REF] Quilitz | Querying distributed RDF data sources with SPARQL[END_REF][START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF] are not able to take advantage of replicated fragments, and data overlapping can seriously degrade their performance as reported in Figure 1 and shown in [START_REF] Montoya | Fedra: Query Processing for SPARQL Federations with Divergence[END_REF][START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF]. We integrated FEDRA within FedX and ANAPSID to make existing engines aware of replicated fragments. With FEDRA, replications as in Figure 1 will be detected, and performance will remain stable.

Recently, QBB [START_REF] Hose | Towards benefit-based RDF source selection for SPARQL queries[END_REF] and DAW [START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF] propose duplicate-aware strategies for selecting sources for federated query engines. Both approaches use sketches to estimate the overlapping among sources. DAW uses a combination of Min-Wise Independent Permutations (MIPs) [START_REF] Broder | Min-wise independent permutations[END_REF], and triple selectivity information to estimate the overlap between the results of different sources. Based on how many new query results are expected to be found, sources below predefined benefits are discarded and not queried.

Compared to DAW, FEDRA does not require to compute data summaries because FEDRA relies on fragment definitions to deduce containments. Computing containments based on fragment descriptions is less expensive than computing data summaries, moreover data updates are more frequent than fragment description updates. FEDRA

Fedra Approach

Fragments and Endpoints Descriptions To define a fragment, we will use the Linked Data Fragment definition given by Verborgh et al. [START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF]. Let U, L, and V denote the set of all URIS, literals and variables, respectively. T ˚" U ˆU ˆpU Y Lq is a finite set of blank-node-free RDF triples. Every dataset G published via some kind of fragments on the Web is a finite set of blank-node free triples; i.e., G Ď T ˚. Any tuple

tp P pU Y Vq ˆpU Y Vq ˆpU Y V Y L) is a triple pattern.
Definition 1 (Fragment [START_REF] Verborgh | Querying datasets on the Web with high availability[END_REF]). A Linked Data Fragment (LDF) of G is a tuple f " xu, s, Γ, M, Cy with the following five elements: i) u is a URI (which is the "authoritative" source from which f can be retrieved); ii) s is a selector; iii) Γ is a set consisting of all subsets of G that match selector s, that is, for every G 1 Ď G it holds that G 1 P Γ if and only if G 1 P dompsq and spG 1 q " true; iv) M is a finite set of (additional) RDF triples, including triples that represent metadata for f; and v) C is a finite set of controls.

We restrict fragments to triple pattern fragments as in [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF][START_REF] Verborgh | Web-scale querying through Linked Data Fragments[END_REF]. Hereafter, we consider that fragments are read-only and data cannot be updated; the fragment synchronization Listing 1.1: C1 Endpoint Description @prefix sd:< h t t p : / / www. w3 . org / ns / s p a r q l´s e r v i c e´d e s c r i p t i o n #>. @prefix dc : <h t t p : / / p u r l . org / dc / elements /1. problem is studied in [START_REF] Ibáñez | Col-graph: Towards writable and scalable linked open data[END_REF]. Consider the federation in Figure 1a, where five data consumer endpoints (C1-C5) include fragments (f1-f9) from public endpoints P1 and P2. Table 1b shows the SPARQL CONSTRUCT query used as a selector for a fragment. Fragments f1, f2, f4, and f9 have as "authoritative" source P1, and fragments f3 and f5-f8 have as "authoritative" source P2. The last column presents the consumer endpoints where fragments are available.

To participate in a FEDRA federation, data consumers annotate each fragment exposed through their endpoints with the fragment selector s and the public endpoint that provides the data u. The vocabulary term sd:endpoint refers to the SPARQL endpoint that publishes the fragment. The vocabulary term dcterms:hasPart introduces a fragment description, the vocabulary term dc:description refers to the SPARQL CONSTRUCT query s, and the vocabulary term dcterms:source specifies u, the fragment "authoritative" source URI. Listing 1.1 shows the description of the endpoint C1 of Figure 1a.

For source selection with replicated fragments, we need to define when a fragment is relevant for answering a query. A fragment is relevant for answering a query, if it is relevant for at least one triple pattern of the query.

Definition 2 (Fragment relevance).

A fragment f " xu, s, Γ, M, Cy is relevant for a triple pattern tp, if the triple pattern evaluated over Γ , vtpw Γ [START_REF] Pérez | Semantics and complexity of SPARQL[END_REF], is not empty.

Consider queries Q1 and Q2 (cf. Listing 1.2), and the federation of Figure 1. Fragments f1 and f9 are relevant for query Q1, while fragments f4, f7, and f8 are relevant for query Q2. We can define two types of containments: containment between SPARQL endpoints and containment between fragments. Definition 3 (Endpoint Containment). Let e1 and e2 be the URI of two SPARQL endpoints that respectively expose fragments f 1 " xu1, s, Γ 1, M 1, C1y and f 2 " xu2 , s, Γ 2, M 2, C2y such that f1 and f2 have the same selector s and the same "authoritative" source (u2 = u1). Then all triples in f2 are contained in f1 and vice versa, i.e., Γ 2 Ď Γ 1 ^Γ 1 Ď Γ 2. And we use the notation e1 Ď s e2, and e2 Ď s e1 to represent the endpoint containment relationship. f1 triples in consumers C1 and C3 from Figure 1 are the same (from Definition 3): C1 Ď s C3 and C3 Ď s C1 where s is f 1 selector. Endpoint containment can be used to reduce the number of endpoints to contact to answer a query. f1 and f9 are relevant for query Q1, from the endpoint containments f1 data is also available through P1, C1, and C3 and f9 data is also available through P1 and C5. Therefore, only one endpoint per fragment needs to be selected to answer the query. A good choice could be C1, Triples of fragment f9 replicated at consumer C5 in Figure 1 are contained in fragment f1 at C1 and C3 (f9 Ď f1) because f1 and f9 share the same "authoritative" source, and all the triples that match predicate p1 and object c1 always matches predicate p1 in f1.

?x2 { C1 } { C3 } ?x2 p4 ?x3 { C2 } { C3 } ?x1 p2 ?x2 { C1 } { C4 } ?x2 p5 ?x3 { C2 } { C4 } ?x1 p3 ?x2 { C1 } { C5 } ?x2 p6 ?x3 { C2 } { C5 } (c) Conditions 1-3 BGP tp D2(tp) BGP1 ?x1 p1 ?x2 { C3 } ?x2 p4 ?x3 { C3 } BGP2 ?x1 p2 ?x2 { C4 } ?x2 p5 ?x3 { C4 } BGP3 ?x1 p3 ?x2 { C5 } ?x2 p6 ?x3 { C5 } (d)
Using fragment containment, contacting C1 or C3 is enough to answer Q1.

Source Selection Problem (SSP) Given a set of SPARQL endpoints E, a set of public endpoints P, P Ď E, the set of fragments contained in each endpoint as a function frags : Endpoint Ñ set of Fragment, a containment relation among endpoints (given by Definition 3) for f P frags(e i ) ^f P frags(e j ), e i Ď f e j , a containment relation among fragment selectors (given by Definition 4) f l Ď f k , and a SPARQL query Q. Find a map D, such that for each triple pattern tp in Q, D(tp) Ď E and: 1) For each endpoint e that may contribute with relevant data to answer query Q, e is included in D, or D includes another endpoint that contributes with at least the same relevant data as e.

2) D(tp) contains as few public endpoints as possible. 3) size(D(tp)) is minimized for all triple pattern tp in Q. 4) The number of different endpoints used within each basic graph pattern is minimized. Condition 1 states that the selected sources will produce an answer as complete as possible given the set of fragments accessible through the endpoints E, but answer may be incomplete if some fragments definitions are missing. Condition 2 ensures that public endpoints availability problem will be avoided whenever is possible. Condition 3 establishes that the number of selected sources is reduced. Condition 4 aims to reduce the size of intermediate results, and to delegate the join execution to endpoints whenever is possible. Even if the public endpoint can provide all the fragments, the use of several consumer endpoints is preferable. To illustrate these four conditions, consider query Q3 in Figure 2a and fragments and endpoints of Figure 1. Table 2b shows the relevant fragments for Q3 triple patterns, and the endpoints that provide these fragments. For example, for the triple pattern ?x1 p1 ?x2, there are two relevant fragments f 1 and f 9. As previously discussed using endpoint containments, contacting C1 or C3 is enough to answer this triple pattern without contacting the public endpoint. The maps D 1 and D 2 in Figure 2c satisfy the SSP conditions 1-3: all relevant fragments have been included directly or through containment relation, the number of selected endpoints per triple pattern has been minimized, and no public endpoints has been included in the map. However, only the map D 2 satisfies condition 4, as the number of different endpoints selected per basic graph pattern has been also minimized (see Figure 2d). Then, joins are delegated to the selected endpoints, and the size of intermediate results is reduced. Current state-of-the-art [START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF] is triple pattern wise and does not guarantee condition 4.

Source Selection Algorithm Algorithm 1 sketches the FEDRA source selection algorithm. First, the algorithm pre-selects for each triple pattern in Q the sources that can be used to evaluate it (lines 2-29). All the endpoints e and their exposed fragments f are considered (lines 5-27). In line 6, the function canAnswer() is used to determine if endpoint e can provide triples from fragment f that matches triple pattern tp. An initial check based on the selector of f and tp is done, and when it is satisfied, a dynamic check using an ASK query is done to ensure that f is relevant for triple pattern tp (as in Definition 2). An ASK query is used to avoid considering fragments that are not relevant for the triple pattern, in the case the triple pattern has constants where the fragment definition has variables. Query Q3 relevant endpoints and fragments are given in Table 2b.

The function subFrag determines if the data provided by one fragment is also provided by another fragment. This function has as arguments the fragments and endpoints that provide them, and also the containment relationships. For each relevant fragment f , it determines if the considered fragment f in endpoint e provides the same data as already found fragments or if it provides at least the same data as already found fragments or if it provides at most the same data as already found fragments (lines 8-22). Function subFrag tests if there is a containment in both senses or only in one of them. Accordingly, the fragment is grouped with the fragments that provide the same data (lines 10-12), some of the already found fragments are not anymore of interest (line 14-15), or it is chosen not to include the fragment (lines [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF][START_REF] Umbrich | Comparing data summaries for processing live queries over linked data[END_REF]. Between the fragments f 1 and f 9 selected as relevant fragments for the first triple pattern of Q3, there is a containment f 9 Ď f 1, and in consequence, only the fragment f 1 needs to be selected. Moreover, f 1 is provided by endpoints C1, C3, and P 1, and as they provide the same data, each of them can be selected alone to provide data for this triple pattern, i.e., they offer alternative sources for the same fragment. Table 2 (left) shows the changes in f ragments for the first triple pattern of Q3 . Contrarily, between the fragments f 7 and f 8 selected as relevant for the second triple pattern of Q2, there is no containment relation, and in consequence, both fragments are selected. Table 2 (right) shows the changes in f ragments for the second triple pattern of Q2.

When the fragment provides non-redundant data, it is included in the selected fragments (lines 23-24). In the previous examples, it happens once for the first triple pattern { { (f7, C3), (f7, P2) }, { (f8, C4) } } 11 { { (f7, C3), (f7, P2) }, { (f8, C4), (f8, P2) } } of Q3 and twice for the second triple pattern of Q2. Function getEndpoints in line 28 takes the endpoints of fragments, and when for one subset fs there are endpoints in E -P, then all endpoints in P are removed. In the previous examples, the public endpoints are removed and the value of G(?x1 p1 ?x2) is {{C1,C3}}, and the value of G(?x1 p7 ?x3) is {{ C3 },{C4}}. At the end of the first for loop (lines 3-29), a set whose elements are a set of endpoints and fragments that can be used to evaluate the triple pattern is produced for each triple pattern in the query. All the endpoints in the same set offer the same data for that fragment, and during execution only one of them needs to be contacted. And different elements of this resulting set correspond to different fragments that should be considered in order to obtain an answer as complete as possible, modulo the considered fragments. For queries Q2 and Q3, C1 and C3 provide the same data for the first triple pattern of Q3, and C3, C4 provide different data for the second triple pattern of Q2 .

Next, for each basic graph pattern, a general selection takes place, considering the pre-selected sources for each triple pattern in the basic graph pattern. This last part can be reduced to the well-known set covering problem, and an existing heuristic like the Fig. 3: Set covering instances of S and C for the query Q2 and federation given in Figure 1. For each element in G(tp), one element is included in set S. For each endpoint in G, one set is included in collection C and its elements are the elements of S related to the endpoint one given in [START_REF] Dasgupta | Algorithms[END_REF] may be used to perform the procedure indicated in line 33. To use the set covering heuristic, an instance of the set covering problem is produced in line 32 using bgp G3 . Figure 3a shows G values obtained after lines 3-29 loop has ended for query Q2, and S instance for the set covering problem. For each set in G(tp), one element is included in S, e.g., for set {C2,C3}, the element s 1,1 is included in S. We have used subscripts i,j to denote that the element comes from the triple pattern i, and it is the j-th element coming from this triple pattern. The collection C is composed of one set for each endpoint that is present in G, and its elements are the elements of S related to each endpoint. Figure 3b shows the instance of C for this example. The collection C' obtained in line 33 is {C3,C4}, as the union of C3 and C4 is equals to S, and there is no smaller subset of C that can achieve this. The instruction in line 35 removes from each G(tp) the elements that do not belong to C'. In the example, C2 is removed from G(?x1 p4 ?x2). A last step may be performed to choose among endpoints that provide the same fragment and ensure a better query processing by existing federated query engines (lines 38-40). Nevertheless, these alternative sources could be used to speed up query processing, e.g., by getting a part of the answer from each endpoint.

Experiments

We conducted many experimentations in different setups to demonstrate the impact of FEDRA on existing approaches, complete results are available at the FEDRA web site 4 . The performance of the FedX and the ANAPSID query engines is our baseline. (d) Federations

Table 3: Datasets, queries and federations characteristics. For the datasets: the version, number of different triples (# DT), and predicates (# P). For the queries: the number of queries with 1 triple pattern (ST), 2, 3 or 4 triple patterns in star shape (S) or path shape (P). Also the number of queries with: joins (J), optionals (OP), unions (U), filter (F), regex expressions (R), limit (L), and order by (OB). For the federations: the number of fragments definitions (FD), endpoints exposing one and two fragments (E1F, E2F) acteristics of the evaluated datasets. We studied the datasets and queries used in [START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF] 5 . However, we modified the queries to include the DISTINCT modifier in all the queries. Additionally, the ORDER BY clause was included in the queries with the LIMIT clause, in order to make them susceptible to a reduction in the set of selected sources without changing the query answer, and to ensure a semantically unambiguous query answer. Tables 3b and3c present queries characteristics. As federations used in [START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF] do not take into account fragments, they were not reprised. A federation was set up for each dataset; each federation is composed of the triple pattern fragments that are relevant for the studied queries. The federation endpoints offer one or two fragments; endpoints with two fragments offer opportunities to execute joins for the engine. Table 3d shows the federation characteristics. In average, DAW indexes were computed in 2,513 secs, and FEDRA containments in 32 secs. Notice that as FEDRA containments depends only on fragment descriptions, their updates are less frequent than DAW indexes. Virtuoso 6.1.76 endpoints were used. A Virtuoso server was set up to provide all the endpoints as virtual endpoints. It was configured with timeouts of 600 secs. and 100,000 tuples. In order to measure the size of intermediate results, proxies were used to access the endpoints. Implementations: FedX 3.07 and ANAPSID 8 have been modified to call FEDRA and DAW [START_REF] Saleem | Daw: Duplicateaware federated query processing over the web of data[END_REF] source selection strategies during query processing. Thus, each engine can use the selected sources to perform its own optimization strategies. Because FedX is implemented in Java, while ANAPSID is implemented in Python, FEDRA and DAW 9 were implemented in both Java 1.7 and Python 2. Fig. 4: FedX and FEDRA Number of Selected Sources (NSS) when the percentage of known containments is 0%, 25%, 50%, 75% and 100%, for Diseasome Federation grated in FedX and ANAPSID, reducing the performance impact of including these new source selection strategies. Proxies were implemented in Java 1.7. using the Apache HttpComponents Client library 4.3.5. 10Evaluation Metrics: i) Number of Selected Public Sources (NSPS): is the sum of the number of public sources that has been selected per triple pattern. ii) Number of Selected Sources (NSS): is the sum of the number of sources that has been selected per triple pattern. iii) Execution Time (ET): is the elapsed time since the query is posed by the user and the answers are completely produced. It is detailed in source selection time (SST), and total execution time (TET). Time is expressed in seconds (secs.). A timeout of 300 secs. has been enforced. Time was measured using the bash time command. iv) Intermediate Results (IR): is the number of tuples transferred from all the endpoints to the query engine during a query evaluation. v) Recall (R): is the proportion of results obtained by the underlying engine, that are also obtained including proposed strategy.

Impact of the number of containments over FEDRA behavior We study the impact of the number of containments known during the source selection on the number of selected sources and intermediate results size. For each query, the set of known containments have been set to contain 0%, 25%, 50%, 75%, and 100% of the containments concerning the relevant fragments, and queries have been executed in these five configurations. Results show that the number of selected public sources is equal to the number of triple patterns in the queries when no containment is known. However, as soon as some containments are known (25%-100%), this number is reduced to zero. Also, the number of selected sources is considerably reduced when FEDRA source selection strategy is used instead of just using ANAPSID and FedX source selection strategies; see FedX results in Figure 4. ANAPSID results exhibit a similar behavior.

Preservation of the Query Answer The goal of this experiment is to determine the impact of FEDRA source selection strategy on query completeness. Queries were executed using both the ANAPSID and the FedX query engines, and then, we executed the same engines enhanced with the FEDRA source selection strategy. Recall was computed and was 1.0 in the majority of the cases. In few cases the recall was considerably reduced, but these cases correspond to queries with OPTIONAL operator using the FedX query engine, and it was due to an implementation error for this operator. FEDRA only discards relevant sources when relevant fragments data are provided by another source that was already selected. Then, it does not reduce the recall of the answer. Finally, the query engine implementation limitations were also the causes of the reduction of recall.

Source Selection Time To measure the FEDRA and DAW source selection cost, the source selection time using each engine with and without FEDRA or DAW was measured. Results are diverse, for federations with a large number of endpoints like the SWDF federation, the cost of performing the FEDRA source selection is considerably inferior to the cost of contacting all the endpoints using FedX, but similar to the cost of using the ANAPSID source selection strategy. On the other hand, the DAW cost is similar to the FedX cost, and it is considerably superior to the ANAPSID cost. For federations with a small number of endpoints like Geo-coordinates (see Figures 5a and5b), the cost of performing source selection with FEDRA is less expensive than performing just FedX source selection, but more expensive than performing just ANAPSID source selection strategy. And the cost of performing source selection with DAW is more expensive than performing just FedX or ANAPSID source selection strategy. ANAPSID source selection mostly relies on the endpoints descriptions, and avoids to contact endpoints in most cases. On the other hand, FedX source selection strategy relies on endpoint contacts to determine which endpoints can be used to obtain data for each triple pattern. FEDRA source selection is somewhere in the middle, it does contact all the endpoints that are considered relevant according to their descriptions to confirm that they can provide relevant data, and has the added cost of using the containments to reduce the number of selected sources. DAW source selection does not contact sources, but relies on no negligible cost of operating Min-Wise Independent Permutations (MIPs) in order to determine the overlapping sources.

Execution Time To measure the FEDRA and DAW execution time, queries were executed using each engine with and without FEDRA or DAW. For small federations or queries with only one triple pattern, FEDRA and DAW achieve a similar reduction in For D+F, 4 out of 5 queries timed out for 2STAR and 3STAR queries execution time. However, for larger federations and queries with more triple patterns, FEDRA reduction is larger than DAW. In all cases, the reduction is considerable when the combination of FEDRA and the query engine is compared to using the engine alone, e.g., Figure 6b shows the results for the Geo-coordinates federation and FedX. For star-shape queries, the use of FEDRA source selection strategy has made the difference between timing out or obtaining answers. For queries with two triple patterns, this difference is important, as FEDRA enhances FedX to obtain answers in just few seconds. The difference in execution time is a direct consequence of the selected sources reduction. Further, executing the joins in the endpoints whenever it is possible, may reduce the size of intermediate results and produce answers sooner.

Reduction of the Number of Selected Sources

To measure the reduction of the number of selected sources, the source selection was performed using ANAPSID and FedX with and without FEDRA or DAW. For each query, the sum of the number of selected sources per triple pattern was computed, for all the sources and just for the public sources. Figure 6 shows the results for the Geo-coordinates federation and FedX, similar results are observed for the other federations and for ANAPSID. DAW source selection strategy exhibits the same reduction in the total number of selected sources. Consequently, some of the selected public sources are pruned, but as it does not aim to reduce the public sources, it does not achieve a consistent reduction of them. On the other hand, FEDRA has as input the public condition of sources, and as one of its goals is to select as few public sources as possible, it is natural to observe such a reduction consistently for all the query types. FEDRA source selection strategy identifies the relevant fragments and endpoints that provide the same data. Only one of them is actually selected, and in consequence, a huge reduction on the number of selected sources is achieved. Moreover, public endpoints are safely removed from the selected sources as their data can be retrieved from other sources.

Reduction of the Intermediate Results Size

To measure the intermediate results size reduction, queries were executed using proxies that measure the number of transmitted tuples from endpoints to the engines. Additionally, each query was executed against the federation with and without the public endpoint. Figure 7 shows the sizes of intermediate results for the Diseasome federation and FedX combined with FEDRA and DAW; similar results were obtained for the other federations and for ANAPSID. Figure 7a shows that when the public endpoint is part of the federation, DAW source selection strategy leads to executions with considerably less intermediate results.

Figure 7b shows that when the public endpoint is not part of the federation, FE-DRA source selection strategy leads to executions with considerably less intermediate results. Since the FEDRA source selection strategy finds opportunities to execute joins in the endpoints, and mostly, it leads to significant reduction in the intermediate results size. These results are consequence of SSP Condition 4, and cannot be systematically achieved by DAW as it is a triple wise based approach. Nevertheless, as DAW source selection does not avoid public endpoints, it may select to execute all triple patterns in the public endpoint, and this comes with a huge reduction of the size of intermediate results. Figure 7b shows that when this "public endpoint" opportunity to execute all triple patterns in one endpoint is removed, DAW source selection strategy does not consistently reduce the intermediate results size.

Conclusions and Future Works

Recent works on replicated fragments spread data and SPARQL processing capabilities over data consumers. This opens new opportunities for federated query processing by offering new tradeoffs between availability and performance. We presented FEDRA, a source selection approach that takes advantage of replicated fragment definitions to reduce the use of public endpoints as they are mostly overloaded. FEDRA identifies and uses opportunities to perform join in the sources relieving the query engine of performing them, and reducing the size of intermediate results. Experimental results demonstrate that the number of selected sources remains low even when high number of endpoints and replicated fragments are part of the federations. Results rely on con-tainments induced by replicated fragment definitions. Next, selecting the same sources for Basic Graph Patterns triples is a strategy that allows to reduce significantly the number of intermediate results. Perspectives include dynamic discovery of endpoints providing replicated fragments. This allows federated query engines to expand at runtime declared federations with consumer endpoints of interests. Such mechanism can improve both data availability and performances of federated queries in Linked Data.

Table 2 :

 2 f ragments changes due to execution of lines 5-27 of Algorithm 1 for the first triple pattern of Q3 (left) and the second triple pattern of Q2 (right) f1, C1) } } 11 { { (f1, C1), (f1, C3) } } 11 { { (f1, C1), (f1, C3), (f1, P1) f7, C3) } } 24 { { (f7, C3) }, { (f8, C4) } } 11

  7.3.. Thus, FEDRA and DAW were inte-

Fig. 5 :

 5 Fig. 5: Source selection time (SST) for Geo-coordinates federation. The FedX (F, left) and the ANAPSID (A, right) query engines are combined with FEDRA (F+F and F+A), and DAW (D+F and D+A)

Fig. 6 :

 6 Fig.6: Number of Selected Sources and Total Execution Time (TET) for Geocoordinates federation and the FedX (F) query engine. FedX is also combined with FEDRA and DAW source selection strategies (F+F and D+F). For F, 4 out of 5 queries timed out for each query type. For F+F, 4 out of 5 queries timed out for 3STAR queries. For D+F, 4 out of 5 queries timed out for 2STAR and 3STAR queries

Fig. 7 :

 7 Fig. 7: Intermediate results size for Diseasome federation and FedX (F). FedX is also combined with FEDRA and DAW source selection strategies (F+F and D+F)

  C5 or C3, C5; this will reduce the load of the public endpoint P1 and will improve P1 availability. By contacting only C1, C5 or C3, C5, complete query answers are obtained because the triple pattern fragment defines a copy of the data source using the fragment selector. Another type of containment that allows to reduce the number of sources to be contacted is defined based on the fragment selector.

	Conditions 1-4
	Fig. 2: SSP solutions for query Q3: (a): Query Q3, (b):Relevant fragments for Q3, (c):
	Maps D 1 and D 2 that satisfy Source Selection Problem (SSP) conditions 1-3., (d): Map
	D 2 that satisfies Source Selection Problem (SSP) conditions 1-4

Definition 4 (Fragment Containment). Let f 1 " xu, s1, Γ 1, M 1, C1y and f 2 " xu, s2, Γ 2, M 2, C2y be two fragments that share the same "authoritative" source u, and a triple pattern tp. If for all possible values of Γ 1 and Γ 2, always the triples in Γ 1 that match tp are also in Γ 2, i.e., vtpw Γ 1 Ď vtpw Γ 2 . Then, regarding tp, f 1 is contained in f 2. And we use the notation f1 Ď f2.

  Algorithm 1 Source Selection algorithm

	Require: Q: SPARQL Query; E: set of Endpoints; frags :	20:	end if
		Endpoint Ñ set of Fragment; P : set of Endpoint; Ď f :	21:	end if
		Endpoint ˆEndpoint; Ď : BGP ˆBGP	22:	end for
	Ensure: D: map from Triple Pattern to set of Endpoints.	23:	if include then
	1: function SOURCESELECTION(Q,E,frags,P,Ď f ,Ď)	24:	fragments.add({(f,e)})
	2: triplePatterns Ð get triple patterns in Q 3: for each tp P triplePatterns do 4: fragments Ð H 5: for each e P E ^f P frags(e) do 6: if canAnswer(e, f, tp) then 7: include Ð true 8: for each fs P fragments do 9: (f',e') Ð take one element of fs	25: 26: end if end if 27: end for 28: G(tp) Ð getEndpoints(fragments) 29: end for each 30: basicGP Ð get basic graph patterns in Q 31: for each bgp P basicGP do 32: (S, C) Ð minimal set covering instance using
	10: 11: 12: 13: 14: 15: 16: 17: 18: 19:	then	bgp G 33: C' Ð minimalSetCovering(S, C) if subFrag(f,e,f',e',Ď f ,Ď) ^subFrag(f',e',f,e,Ď f ,Ď) 34: for each tp P bgp do fs.add((f,e)) 35: G(tp) Ð filter G(tp) according to C' include Ð false 36: end for each else 37: end for each if subFrag(f',e',f,e,Ď f ,Ď) then 38: for each tp P domain(G) do fragments.remove(fs) 39: D(tp) Ð for each set in G(tp) include one element else 40: end for each if subFrag(f,e,f',e',Ď f ,Ď) then 41: return D include Ð false end if 42: end function

  General results are the comparison of performance of FedX alone, FedX+DAW, FedX+FEDRA, same thing for ANAPSID. Compared to FedX and ANAPSID, FEDRA should reduce selected sources significantly and speed up queries execution time. Compared to DAW, we expect FEDRA to achieve same source reduction but without pre-computed MIPS index, and generate less intermediate results thanks to endpoints reduction and to finding join opportunities. Datasets, Queries and Federations Benchmark: we used Diseasome, Semantic Web Dog Food, LinkedMDB, and DBpedia geo-coordinates datasets, Table3ashows char-

	Dataset	Version date # DT	# P
	Diseasome	19/10/2012 72,445 19
	Semantic Web Dog Food 08/11/2012 198,797 147
	DBpedia Geo-coordinates 06/2012 1,900,004 4
	LinkedMDB	18/05/2010 3,579,610 148

bgp G represents function domain restriction, i.e., it takes the elements of map G that relates elements in bgp with some set of set of endpoints

https://sites.google.com/site/fedrasourceselection

They are available at https://sites.google.com/site/dawfederation.

http://virtuoso.openlinksw.com/, November 2013.

http://www.fluidops.com/fedx/, September 2014.

https://github.com/anapsid/anapsid, September 2014.

https://hc.apache.org/, October 2014.


J E Mungall

J M Brenan

B Godel

S J Barnes

F Gaillard

Transport of metals and sulphur in magmas by flotation of sulphide melt on vapour bubbles

Emissions of sulphur 1,2 and transition metals 3,4 from magmas in the shallow crust have global impacts on human society by affecting climate after volcanic eruptions 5,6 and by forming giant copper and gold ore deposits, which are massive anomalies of sulphur as well as of the ore metals themselves 3,4,7,8 . These emissions vastly exceed the amounts that could have been derived from the associated magmas themselves 2 . Intrusion of denser, hotter, vapourand sulphide-saturated magma beneath the cooler and more buoyant bodies that are finally erupted is the most probable source of the excess sulphur and metals in eruptive or hydrothermal systems 1,4,9,10 . However, the mechanism for the selective upward transfer of sulphur and metals remains poorly understood, because their main carrier phase, sulphide melt, is dense and is generally assumed to settle to the bottoms of magma bodies. Here we show, by experimental observation and by gas speciation and mass balance models, that such transfers may be achieved by the flotation of compound drops 11 comprising droplets of sulphide melt attached to vapour bubbles. By proposing and demonstrating the feasibility of a novel physical mechanism for upward mobility of sulphide liquids, our work provides a mechanism for massive atmospheric releases of sulphur and contradicts widely held assumptions that dense sulphide liquids rich in sulphur, copper, and gold will remain sequestered in the crust.

Plinian volcanic eruptions typically release as much as 100 times more sulphur than could have been dissolved within the erupted volumes of felsic magma [START_REF] Wallace | The sulfur budget in magmas: Evidence from melt inclusions, submarine glasses, and volcanic gas emissions[END_REF][START_REF] Westrich | Magmatic gas source for the stratospheric SO2 cloud from the June 15, 1991, eruption of Mount Pinatubo[END_REF][START_REF] Gerlach | Vapour saturation and accumulation in magmas of the 1989-1990 eruption of Redoubt Volcano, Alaska[END_REF] . Sulphur is emitted during quiescent periods between eruptions at rates far exceeding plausible rates of supply from the felsic magmas within the shallow volcanic feeders [START_REF] Wallace | The sulfur budget in magmas: Evidence from melt inclusions, submarine glasses, and volcanic gas emissions[END_REF][START_REF] Edmonds | Excess volatiles supplied by mingling of mafic magma at an andesite arc volcano[END_REF] . Excess sulphur emissions result from eruptive tapping of apical gas-rich cupolas containing excess vapour which comprises up to 30 vol% of the magma in shallow intrusions [START_REF] Wallace | Volcanic SO2 emissions and the abundance and distribution of exsolved gas in magma bodies[END_REF][START_REF] Keppler | The distribution of sulfur between haplogranitic melts and aqueous fluids[END_REF] .

Intrusion of sulphur-rich mafic magma immediately prior to eruption, commonly saturated with droplets of an immiscible Fe-(Cu)-(Ni)-S-O liquid (i.e., sulphide liquid) [START_REF] Hattori | High-sulfur magma, a product of fluid discharge from underlying mafic magma: evidence from Mount Pinatubo, Philippines[END_REF][START_REF] Muro | Pre-1991 sulfur transfer between mafic injections and dacite magma in the Mt. Pinatubo reservoir[END_REF] , may trigger eruptions of felsic to intermediate magma, while the bulk of the mafic magma remains at depth [START_REF] Pallister | Magma mixing at Mount Pinatubo: petrographic and chemical evidence from the 1991 deposits[END_REF] .

However the co-erupted excess sulphur vapour at Soufriere and Pinatubo volcanoes was probably supplied previously by degassing of underplated mafic magma over protracted periods [START_REF] Wallace | Volcanic SO2 emissions and the abundance and distribution of exsolved gas in magma bodies[END_REF][START_REF] Wallace | The sulfur budget in magmas: Evidence from melt inclusions, submarine glasses, and volcanic gas emissions[END_REF][START_REF] Edmonds | Excess volatiles supplied by mingling of mafic magma at an andesite arc volcano[END_REF][START_REF] Van Hoose | Sulfur evolution of the 1991 Pinatubo magmas based on apatite[END_REF] .

Transition metals are also transferred from mafic magmas saturated with sulphide liquid into overlying felsic liquids, leading to enrichment of ore-forming elements. Hydrothermal porphyry deposits of Cu and or Au at Pinatubo as well as Bingham Canyon, Utah [START_REF] Hattori | Contribution of mafic melt to porphyry copper mineralization: evidence from Mount Pinatubo, Philippines, and Bingham Canyon, Utah, USA[END_REF] and Bajo de la Alumbrera, Argentina [START_REF] Halter | Magma evolution and the formation of porphyry Cu-Au ore fluids: evidence from silicate and sulfide melt inclusions[END_REF][START_REF] Halter | The origin of Cu/Au ratios in porphyry-type ore deposits[END_REF] , form when those felsic magmas solidify and discharge metal-and sulphur-rich aqueous fluids. Although intimate interactions between mafic and felsic magmas undoubtedly occur, the physical mechanism by which sulphur and metals are transferred between them remains a matter of speculation.

Orthomagmatic ore-forming fluids have ratios of transition metals similar to those of the sulphide liquid from which they were derived by hydration or oxidation during quantitative resorption of sulphide liquid by silicate magma; e.g., Cu/Au at the Bajo de la Alumbrera porphyry Cu-Au deposit [START_REF] Halter | Magma evolution and the formation of porphyry Cu-Au ore fluids: evidence from silicate and sulfide melt inclusions[END_REF] and Cu/Ni and Cu/Co in volcanic gases at Merapi 4 . At the Bajo de la Alumbrera mafic magma mixed with rhyodacite magma to produce hybrid andesites with mixed phenocryst populations containing sulphide melt inclusions [START_REF] Halter | Magma evolution and the formation of porphyry Cu-Au ore fluids: evidence from silicate and sulfide melt inclusions[END_REF] These reactions are favored at low pressure and high H 2 O activity in FeO-poor felsic magmas, especially if vapour is able to leave the system. The mineralized dacite porphyry stocks at Alumbrera were derived from the top of a stratified intrusion, where sulphide melt was not stable, whereas the sulphide melt was present in the more mafic hybrid andesitic melt at the bottom [START_REF] Halter | Magma evolution and the formation of porphyry Cu-Au ore fluids: evidence from silicate and sulfide melt inclusions[END_REF] ; the authors suggest that fluids must have extracted metals and sulphur from the entire stratified magma body despite the shallow intrusions having tapped only the top, while preserving the Cu/Au ratios of the sulphide liquids found only at the base of the system 3 .

Solidified remnants of sulphide liquid globules that have undergone breakdown to Cu-sulphide phases and Fe-oxide minerals occur in quenched felsic to intermediate magmas at Pinatubo, Bingham Canyon, Merapi, Popocatepetl, Satsumi-Iwojima, Clear Lake, and Mount St Helens [START_REF] Nadeau | Sulphide magma as a source of metals in arc-related magmatic hydrothermal ore fluids[END_REF][START_REF] Muro | Pre-1991 sulfur transfer between mafic injections and dacite magma in the Mt. Pinatubo reservoir[END_REF][START_REF] Hattori | Contribution of mafic melt to porphyry copper mineralization: evidence from Mount Pinatubo, Philippines, and Bingham Canyon, Utah, USA[END_REF]20 . These examples of sulphide melt which was clearly not at equilibrium with its host magma, have previously been accounted for either as hybrids of sulphide-saturated mafic liquids with initially sulphur-poor felsic magmas, or as the result of vapour transport of sulphur and metals out of mafic magma into felsic magma followed by their reprecipitation in sulphide liquid droplets which subsequently became unstable [START_REF] Hattori | High-sulfur magma, a product of fluid discharge from underlying mafic magma: evidence from Mount Pinatubo, Philippines[END_REF] .

A more parsimonious explanation for addition of sulphur, Cu, and Au to either shallow preeruptive or ore-forming intrusions would have the sulphide melt being physically elevated toward the top of the stratified magma body where it then underwent congruent dissolution via hydration during volatile exsolution. However this possibility has not been entertained

previously because of the well-documented density contrast between sulphide melt and silicate melt, which promotes settling of sulphide liquid toward to the base of a magmatic system.

We have performed experiments in which sulphide melt, silicate melt, and vapour were equilibrated to measure the interface morphologies [START_REF] Mungall | Interfacial tension between magmatic sulfide and silicate liquids: constraints on kinetics of sulfide liquation and sulfide migration through silicate rocks[END_REF][START_REF] Botcharnikov | Behavior of gold in a magma at sulfide-sulfate transition: revisited[END_REF][START_REF] Mungall | Partitioning of platinum-group elements and Au between sulfide liquid and basalt and the origins of mantle-crust fractionation of the chalcophile elements[END_REF] . Sulphide drops preferentially occur at the interface between silicate melt and vapour (Fig. 1a), despite the gravitational body force that tends to pull the sulphide melt to the base of the experimental charge. Topologically identical relationships were observed in evacuated silica tubes with a low-density atmosphere governed by equilibrium with sulphide melt [START_REF] Mungall | Partitioning of platinum-group elements and Au between sulfide liquid and basalt and the origins of mantle-crust fractionation of the chalcophile elements[END_REF] , in a gas-mixing furnace under an inert Ar atmosphere [START_REF] Mungall | Interfacial tension between magmatic sulfide and silicate liquids: constraints on kinetics of sulfide liquation and sulfide migration through silicate rocks[END_REF] , and at 200 MPa under water-saturated conditions with 3.2 wt% H 2 O dissolved in the silicate melt [START_REF] Botcharnikov | Behavior of gold in a magma at sulfide-sulfate transition: revisited[END_REF] , indicating that the surface energies of the interfaces are not dramatically affected by the composition of the vapour phase. Under high acceleration in a centrifuge the sulphide descends to the base of the charge, not in contact with the vapour phase [START_REF] Mungall | Partitioning of platinum-group elements and Au between sulfide liquid and basalt and the origins of mantle-crust fractionation of the chalcophile elements[END_REF] . However, during quench of the centrifuge experiments and consequent degassing of the sulphide droplets, smaller droplets of sulphide melt rise from the main droplet at the base of the charge, pendant from ascending vapour bubbles (Extended Data Figure 2). Where silicate melt, sulphide melt, and vapour have been co-entrapped in minerals [START_REF] Nadeau | Sulphide magma as a source of metals in arc-related magmatic hydrothermal ore fluids[END_REF][START_REF] Metrich | Transfer of sulfur in subduction settings: an example from Batan Island (Luzon volcanic arc, Philippines)[END_REF][START_REF] Timina | Melt evolution during the crystallization of basanites of the Tergesh Pipe, Northern Minusinsk Depression[END_REF] ; sulphide melt always occurs attached to the vapour bubble. Sulphide melt droplets attached to vapour bubbles have been noted in komatiitic Ni sulphide ores [START_REF] Dowling | Komatiites and nickel sulfide ores of the Black Swan area, Yilgarn Craton, Western Australia. 2: Geology and genesis of the orebodies[END_REF] .

We have used high resolution computed X-ray tomography 27 to measure precisely the shapes of interfaces separating sulphide, silicate, and vapour in quenched run products of two experiments (Fig. 1). Comparison of quenched sulphide drops with their shapes as observed in situ at experimental conditions using conventional medical X-radiography [START_REF] Mungall | Interfacial tension between magmatic sulfide and silicate liquids: constraints on kinetics of sulfide liquation and sulfide migration through silicate rocks[END_REF] allows us to estimate qualitatively the interfacial tensions of all three types of interface; sulphide-silicate, sulphide-vapour, and silicate-vapour (Table S1, Extended Data; Supplementary Information).

The shapes of interfaces between sulphide melt and silicate melt are unaffected during quench, permitting quantitative solution of the Bashforth-Adams equation to determine interfacial tensions on quenched experimental run products identical to values determined on Xradiographs of sessile drops imaged in situ at run conditions (Supplementary Information). The shapes of pendant sulphide drops both in situ and in quenched experimental products are such that for small droplets where surface energy dominates over buoyant body forces the total energy of a system containing all three phases is always at a minimum when the sulphide occurs at the interface between silicate melt and vapour, forming a compound drop [START_REF] Neeson | Compound sessile drops[END_REF] . We infer that in any magmatic system undergoing vapour nucleation and bubble growth where sulphide melt is also a stable phase, the sulphide droplets will spontaneously occur attached to vapour bubbles.

We propose that the requirement for sulphur and metals to be transferred from mafic magmas to overlying felsic magmas, whilst preserving metal ratios characteristic of the sulphide melts themselves, is most easily met by upward transport of sulphide as compound drops, lofted by the relatively high buoyancy of the attached vapour bubbles (Figs. 2,3). We have modeled the evolution of vapour bubbles in an idealized closed system undergoing isothermal decompression [START_REF] Gaillard | Atmospheric oxidation caused by a change in volcanic degassing pressure[END_REF] (Supplementary Information). We compare the evolution of an andesitic magma initially comprising 0.1 wt% of vapour at 2600 bars, 1050 C, with that of an initially identical magma also containing compound droplets of sulphide and vapour wherein sulphide comprises 3.3 wt% of the entire system, to simulate the evolution of a single sulphide droplet as a vapour bubble nucleates next to it and then grows during decompression. At all pressures the vapour phase is buoyant with respect to the silicate magma; with the growth of the attached bubble the density of the compound drop falls until it becomes buoyant at pressures less than 2000 bars. By the time the compound drop has risen to pressures less than 1,000 bar, the sulphide drop comprises only 1/25th of the volume of the compound drop, a value that falls to infinitesimal proportions at the lowest pressures. Such small quantities of sulphide liquid adhering to bubbles would be difficult to observe. The gas evolves from CO 2 -rich with sulphur species dominated by H 2 S to being nearly pure H 2 O at low pressure (Fig. 2, inset). At the very lowest pressures SO 2 rises to comprise nearly half of the sulphur budget of the vapour in the case of the compound drop whereas under sulphide-absent conditions the sulphur speciation becomes strongly SO 2 -dominated at very low pressure (Extended Data Fig. 9) . The total mass of sulphur residing in the vapour phase at pressures below 5 bar is 1.3 % of the mass of the magma, more than 20 times higher in the case of the compound drop than in the case of the isolated bubble. Sulphur loads of this magnitude are sufficient to explain the excess sulphur paradox alluded to in the introductory paragraph.

It is quite clear that compound drops, rather than isolated fluids, are necessary to explain the Cu and Au concentrations of the ore-forming fluids at Alumbrera 3,29 (Fig. 3). Model compound drop compositions coincide with the bulk ore [START_REF] Ulrich | Gold concentrations of magmatic brines and the metal budgets of porphyry copper deposits[END_REF] , average ore-forming brines [START_REF] Ulrich | Gold concentrations of magmatic brines and the metal budgets of porphyry copper deposits[END_REF] Within a depressurizing compound drop, the amount of sulphide melt falls as the amount of vapour increases, drawing sulphur into the vapour phase. The metal budget of the compound drop as a whole changes very little because metal is transferred almost quantitatively from the sulphide melt to the vapour. We propose that the ore-forming magmatic volatile phase at Alumbrera shown in Figure 3 was composed of compound drops that completely consumed their attached load of sulphide. The removal of compound drops from deep in the magma plumbing system to shallow levels will effect the same net transfer of metals and sulphur into the shallow hydrothermal system regardless of whether it occurs as modeled here, at equilibrium with the host silicate magma (as would be expected in slowly rising crystal-rich magma), or if it occurs suddenly by rapid flotation of the compound drop from considerable depth (as might occur in hybrid intermediate magma at depth with low crystal content). Both sulphur and metals, formerly contained in sulphide melt at depth, are quantitatively transferred to the vapour phase by the time they reach low pressures.

The key to the process of sulphur and metal transfer to shallow or erupted fluid phases is the buoyancy of the compound drop. If the dense sulphide liquid did not form compound drops, the excess sulphur and metals would remain sequestered deep in the crust.

Our observations of compound sulphide liquid-vapour bubble drop formation demonstrate that whenever magma saturated with sulphide melt undergoes vesiculation and degassing, some or all of the sulphide melt should accompany the vapour phase upward instead of settling to the base of the mafic magma as is generally supposed, constituting a dramatically enhanced vector for upward transfer of sulphur and transition metals to ore-forming systems or to the atmosphere. The implications extend to the transport and deposition of Ni-, Cu-, and Pt-rich sulphides in magmatic ore deposits, where it is clearly not safe to assume that sulphide melt will always tend to migrate downwards into structural traps. Flotation of sulphide drops and their ultimate release to H 2 S-rich vapours may also provide a mechanism to support the recent proposition that catastrophic end-Permian global climate change resulted from massive transfers of Ni to the atmosphere from mafic magmas [START_REF] Rothman | Methanogenic burst in the end-Permian carbon cycle[END_REF] . It is intriguing to note that flotation of sulphide minerals on vapor bubbles is also the principal means used in the beneficiation of the ores that form in these magmatic and hydrothermal systems. in the Supplementary Information. Compound drops (heavy grey arrow) have nearly constant bulk compositions coincident with both ore-forming brines and with average ore at Alumbrera, whereas fluids alone do not ever have compositions similar to ore, even if they separate into metal-rich brines and metal-poor vapours.

Figures:

Methods Summary

Backscattered electron (BSE) images of axial cross sections of experimental charges or published images of charges from previous studies [START_REF] Mungall | Interfacial tension between magmatic sulfide and silicate liquids: constraints on kinetics of sulfide liquation and sulfide migration through silicate rocks[END_REF][START_REF] Botcharnikov | Behavior of gold in a magma at sulfide-sulfate transition: revisited[END_REF][START_REF] Mungall | Partitioning of platinum-group elements and Au between sulfide liquid and basalt and the origins of mantle-crust fractionation of the chalcophile elements[END_REF] were used to estimate the radii and contact angles of interfaces between quenched sulphide liquid, silicate glass, and vapour.

Readers are referred to those previous publications for further details of experimental methods. Because the experiments were all performed in cylindrical capsules, it was assumed that all three types of interface are spherical caps for small drops.

Two experiment run products were scanned at the Australian Resources Research Centre in Perth (Western Australia) using an XRADIA (now Zeiss) XRM 500 high-resolution threedimensional X-ray microscope system. The scanner was set up a voltage of 160 kV, a power of

  Figure 1a: 3D tomographic image of heavy compound drop comprising a small vapour bubble

Figure 1b :

 1b Figure1b: Morphologies of compound drops for various ratios of surface tensions between sulphide melt, silicate melt, and vapour[START_REF] Neeson | Compound sessile drops[END_REF] . In all of the cases shown the volume of the vapour

Figure 2 :

 2 Figure 2: cross sectional cartoon illustrating sulphide flotation in subvolcanic environments.

Figure 3 :

 3 Figure 3: Cu vs Au for modeled and measured compositions of sulphides, fluids, and ores at Alumbrera 3,29 . Model trends run from square terminations at 2600 bar to arrow terminations

  and many of the sulphide melt inclusions from Alumbrera 3 , all close to Cu/Au = 10 4 . Model supercritical vapours at equilibrium with sulphide liquids follow a trend of increasing metal contents with decreasing pressure just below Cu/Au = 10 3 , whereas model supercritical vapours not equilibrated with sulphide liquids have Au contents that fall as pressure decreases but nearly constant Cu contents. Also shown are two trends of coexisting brine and vapour that would form if the modeled supercritical vapours were to fall within the miscibility gap separating hydrosaline

melts (i.e., brines) from low-density aqueous vapours if the system contained sufficient Cl. Subcritical magmatic fluids are not expected to fractionate Cu from Au.

Acknowledgements

. JEM and JMB were supported by Discovery Grants from the Natural Sciences and Engineering Research Council of Canada; BG and SJB were funded by the CSIRO Mineral Resources Research Flagship, FG was supported by the European Research Council (ERC project #279790).

allowing to image the interior of the capsule and to reduce potential artefacts. A total of 2000 projections were used to reconstruct a three-dimensional volume of the sample. The resulting dataset was processed using dedicated image processing procedures using AvizoFire(r) software combined with dedicated CSIRO-developed workflows 27 to separate sulphide droplets from silicate and vapour phases and generate 3-D isosurfaces. Cartesian coordinates of numerous points on each interface were determined using Corel Photopaint TM and used to fit model spherical caps by least squares error minimization for small drops, or compared with the Adams-Bashforth equation for larger sessile drops as described in the Supplementary Information.

Supplementary Information available online

Correspondance and requests for materials should be addressed to JEM.

Author Contributions: JMB did experiments; JEM did modeling of interfaces and metal mass balance and wrote the manuscript; BG did CT scanning and related data reduction; FG did gas speciation modeling, SJB, JMB and JEM contributed to the original concept. All authors discussed the results and edited the manuscript.

Author information: Reprints and permissions information is available at www.nature.com/reprints. The authors declare no competing financial interests.

Correspondence and requests for materials should be addressed to JEM (mungall@es.utoronto.ca).