Ifsttar, SPLOTT David Guerrero

French deep-sea hinterlands

Keywords: Hinterland, Foreland, Containerisation, France, Spatial Interaction Model

Deep-sea hinterlands: Some empirical evidence of the spatial impact of containerization

Introduction: the concept of hinterland is it still relevant?

An attempt has been made to elucidate the spatial structure of French hinterlands after four decades of containerization in this study. The detailed hinterland analysis developed by [START_REF] Charlier | Contribution méthodologique à l'étude des arrière-pays portuaires[END_REF][START_REF] Charlier | L'arrière-pays national du port du Havre : une approche macrogéographique[END_REF] is updated by extending it to the period 1995 2005 and to 95 inland regions.

We first define hinterland as it is central to this paper. The concept of hinterland and its overseas equivalent term foreland were mainly explained before containerization in the middle of 20 th century [START_REF] Sargent | Seaports and hinterlands, Adam and Charles Black[END_REF][START_REF] Amphoux | Des horizons terrestres aux horizons maritimes de l activité portuaire[END_REF]. Both refer to the inland areas served by ports [START_REF] Weigend | The problem of hinterland and foreland as illustrated by the port of Hamburg[END_REF]. As seen in Figure 1, the hinterland of the port [|a] is an inland area [A] that delimits the points of origin and destination of maritime shipments handled by the port [a] Conversely, the foreland of the same port [a] is the set of inland areas served by the port [a] by means of maritime transportation [B,C]. By this definition, a single area [A] acts as the hinterland of one port [a] and also forms part of the forelands of other ports [b and c]. In this schematic context, the hinterland is a spatially continuous area and the foreland is a discontinuous set of land areas interconnected by maritime links. This scheme also postulates exclusive hinterlands that are spatially concentrated around ports. However, this is not always the reality. As early as 1918, Demangeon observed substantial overlap between the hinterlands of the ports of Antwerp, Amsterdam, and Rotterdam [START_REF] Demangeon | Anvers[END_REF].

Containerization has challenged the hypothesis of captive hinterlands that are spatially concentrated around ports. Between 1960s and 2000s, container has brought important changes in liner shipping. In containers, many kinds of cargo can be transported on the same ship, and each container can be easily transferred from one means of transport to another without unpacking. Containerization leads to significant economies in handling and maritime transport [START_REF] De Neufville | Productivity and Returns to scale of container ports[END_REF]. However, the high capital cost of container ships and handling tools necessitate a push for its maximum utilization. This push predisposes spatial concentration of freight flows at one or two big ports by region, marginalizing all other ports, as demonstrated by [START_REF] Mayer | Current trends in Great Lakes shipping[END_REF]. He observed that the combined effect of development of container shipping and the completion of interstate highway network increases the competitive advantages of main ports, also called load centers . These ports are usually located close to large markets and/or to main maritime routes. The spatial impact of containerization has been an ongoing area of study for transportation geographers. [START_REF] Hayuth | Containerisation and the load center concept[END_REF] was the first to formalize the load center concept by developing a spatial model inspired by [START_REF] Taaffe | Transport expansion in underdeveloped countries: a comparative analysis[END_REF] and [START_REF] Rimmer | The search of spatial regularities in the development of Australian seaports 1861-1961[END_REF]. The concept explains how the development of a hub-and-spokes network leads to concentration of cargo flows in a few ports, inland centres, and transport routes. The further evolution of the port system might lead to deconcentration, when cargo shifts from large ports to smaller or new ports [START_REF] Hayuth | Containerisation and the load center concept[END_REF][START_REF] Notteboom | The peripheral port challenge in container port systems[END_REF][START_REF] Frémont | Northern European range: shipping line concentration and port hierarchy[END_REF].

Figure 1. Schematic representation of hinterlands and forelands Several regional studies provided empirical evidence for the consequences of containerization on hinterlands and forelands. [START_REF] Hoare | British ports and their export hinterlands: A rapidly changing geography[END_REF] found a large overlapping of hinterlands of British ports. He argued that containerization results in shippers preferring to concentrate trade and services to particular overseas destinations at particular ports. Similarly, [START_REF] Slack | Intermodal transportation in North America and the developmentof inland load centres[END_REF] found, in a continental context of the United States, that the development of rail services across the country contributed to the concentration of an increasing share of Far Eastern Trade on the ports of the West Coast to the detriment of those of the East Coast. In both the cases, shippers attempted to minimize the maritime segment of their exports, even if it implied longer inland haulages. They reasoned that the increase of inland haulage can be compensated by overall cost saving achieved by speed of flow and through inland handling costs [START_REF] Hoare | British ports and their export hinterlands: A rapidly changing geography[END_REF]. The geographic configuration of mainland Europe is different, and the distance between ports and markets is generally short, even if it were be increased by the development railway corridors to the hinterland [START_REF] Van Klink | Gateways and intermodalism[END_REF].

The developments discussed above clearly demonstrate that the development of containerization has transformed port hinterlands. Some scholars even go so far as to say that hinterlands no longer matter[s] [START_REF] Hoare | British ports and their export hinterlands: A rapidly changing geography[END_REF]. Although the increase in inter-port competition as a result of containerization has been largely proved [START_REF] Veldman | A model on container port competition: an application for the West European container hub-ports[END_REF]Buckmann, 2003, Ng, 2006), empirical investigation on the changes of hinterlands due to containerization remains scarce, largely because of lack of data. Therefore, the purpose of this paper is to study the containerization impact on port hinterlands by providing empirical evidence.

The rest of this article is structured as follows. Our hypotheses are explained in Section 2 and an overview of the data and methods used are provided. Section 3 examines how French hinterlands are shared between global and secondary ports. Section 4 introduces a spatial interaction model to measure the differences between hinterlands for different types of cargo. Section 5 explores the link between hinterland and foreland for the two main French container ports, Le Havre and Marseilles, for trade with United States and East Asia. Section 6 presents the conclusions and some implications for policymakers.

Analyzing French hinterlands: Data and methods

When studying maritime flows at a national level, delineating hinterlands proves to be difficult. Even only if the ports located inside France are taken into account, some big ports such as Le Havre and Marseilles obviously serve wider territories. In addition, other ports located outside France (like Antwerp and Rotterdam) also handle French cargo flows.

Unfortunately, in Western Europe a large-scale geographic database of freight flows is not available as in the United States (PIERS). Empirical evidence on freight flows can be gathered only from enquiries (shippers survey), which are not comprehensive on a E.U.-wide basis. For these reasons, we decided to make use of national data, although we know it is an imperfect proxy of a much wider phenomenon.

Information about freight flows is available from databases generated by French Foreign Trade Statistics Bureau (2005), providing disaggregated and exhaustive data of the value and weight of trade (in euros and tonnes). We collected data of Foreign Trade Flows for 1995, 1999, 2003, and 2005. The advent of an internal European Union market on the January 1, 1993 that led to removal of customs formalities (the traditional source of statistical data on international trade) between Member States enforced the adoption of a new data collection system, Intrastat, as the basis for statistics on intra-EU trade. The introduction of Intrastat involved a methodological break with the past and reduced the quality of statistics. But these changes have not affected much of the customs formalities for EU trade outside EU (imports and exports). For these reasons, we made use of data available for French maritime trade outside EU. This narrows the focus of this paper to deep-sea freight flows.

The year 2005 was chosen for this study. Since 2007, with new simplifications of Customs declarations, trade data in tonnes is no more available. This development implied a lowering of data quality after 2007, since goods having the same value can have very different weights, and then be carried in a very different manner. The authors are aware that change happens in hinterlands rather slowly and therefore have decided to adopt 2005 data in euros and tonnes instead of more recent data only in euros.

The spatial units used are the départements1 , French equivalent of Chinese xiàn, U.S. counties, Japanese ken, or European NUTS-3. We selected 94 mainland départements, excluding those of Corsica and Overseas French Territories.

Customs offices located in French ports were aggregated into ports (Figure 4). Information about ports of foreign countries that handle French foreign trade is only available at the country level. Then, we have divided the ports into two types of entities: (a) 16 individual ports located in France and (b) 5 foreign country port sets, which handle together 98% of the value and 97% of the tonnes of French foreign trade.

The truck time-distances between centroids of départements and ports used in the spatial interaction model have been extracted from ESPON inter-NUTS-3 distance database created by Spiekerman andWegener in 2005. The French Foreign Trade Statistics Bureau (2005) distinguishes between 10 different types of cargo. There is no specification between liner service, which operates on a fixed geographic itinerary and publicly advertised sailing schedule, and tramp service, which operates on an irregular or chartered schedule. In this paper, we consider that liner cargo mainly consists of manufactured goods, usually of high value, including machinery and vehicles. Containerized shipping is assumed to be a subcategory of liner service. A cluster analysis was done on French départements to map their main orientation to ports. The method employed is an ascendant hierarchical classification, obtained from a cross-table of ports and départements. The metric used is distance to chi square, in order to limit the mass effects linked to the largest ports. This method of classification allows characterizing of each département with respect to the average French profile, depending upon the ports or the sets of ports that handle its maritime cargo flows.

A spatial interaction model is employed to analyze the hinterlands for different types of cargo. It allows us to explain the spatial distribution of flows between the ports and the départements, in terms of volumes of trade (in tonnes) of départements and ports and the distance between both. The spatial interaction model used is formulated as follows:

i Oi Bj Dj dij where is the total maritime traffic of the département or the port called i; j is the total maritime traffic of the département or the port called j (see table 1);

is the distance between i and j; is the distance decay parameter; and i and j•are the balancing factors ensuring that the origin i and destination j constraints are satisfied. When a département or a port sends freight traffic, it is referred to as i and when a département or a port receives this traffic, it is referred to as region j.

The choice of measure of distance influences the results of the spatial interaction model. The truck s time-distance has been selected because it seems to be more consistent in the context of France, where road transport plays a largely dominant role in the port s modal split. Moreover, the explanatory power of the model is slightly higher when the truck time-distance is used, as compared to the Euclidean distance.

The data finally used is a matrix of freight flows, usually measured in annual tonnes moved. The value of is the part of the total variance explained by the model. It is a measure of the goodness of fit of the model to explain the spatial distribution of flows between the ports and the départements. An of 100% would indicate that the regression line perfectly fits the data. This means that the spatial distribution of flows between ports and départements can be perfectly predicted by the total traffic of each port, total traffic of each département, and the distance separating both. A second is calculated as a measure of variance specifically explained by distance.

A Poisson regression has been used to fit the spatial doubly constrained model [START_REF] Fotheringham | Spatial Interaction Models : Formulations and Applications[END_REF]O Kelly, 1989, D Aubigny et al., 2000).

Table 1. The matrix of the origin destination of flows between ports and départements

To Port1 Port2 Port Portj Dept1 Dept2 Dept Deptj Total From Port1 0 0 0 0 I11 I12 I1j Tport1 Port2 0 0 0 0 I21 I22 I2j Tport2 Port 0 0 0 0 Porti 0 0 0 0 Ii1 Ii2 Iij Tporti Dept1 I11 I12 I1j 0 0 0 0 Tdept1 Dept2 I21 I22 I2j 0 0 0 0 Tdept2 Dept 0 0 0 0 Depti Ii1 Ii2 Iij 0 0 0 0 Tdepti Total Tport1 Tport2 Tportj Tdept1 Tdept2 Tdeptj T

France: A shared territory between global and secondary ports

In France, Le Havre and Marseilles are the main ports and have been pioneers in containerization [START_REF] Guerrero | The waves of containerization: shifts in global maritime transportation[END_REF]. As soon as 1950 researchers already found that these two ports served more overseas regions than the other ports [START_REF] Amphoux | Des horizons terrestres aux horizons maritimes de l activité portuaire[END_REF][START_REF] Vigarié | Les grands ports de commerce de la Seine au Rhin[END_REF]. Later, in the late 1980s, [START_REF] Marcadon | L'avant-pays des ports français : géopolitique des échanges maritimes entre la France et le monde[END_REF] showed that most of small and middle-sized ports only acted as the node for one or two overseas regions at most, mainly niche markets linked to tramp or short sea shipping. The trade handled by small and middlesized was mainly oriented to the intra-European short sea shipping (United Kingdom, Scandinavian countries) and to the former French colonies in Africa. Between these two distinct packages of ports remained an intermediary category of middle-sized ports of Dunkirk, Bordeaux, Nantes and Sète that serve less overseas regions than the main ports, but much more than the other ports. The resistance to this categorization of intermediary ports could be partly explained by inequalities in containerization rates between various regions of the world in the early 1980s. In a work on port specialization in terms of French foreign trade, Le Havre and the foreign ports of Northern Range (Antwerp, Rotterdam) have been ranked the closest to being regarded as truly global ports [START_REF] Guerrero | Les aires d'influence des ports de la France: entre réseau et gravitation[END_REF]. Most of small and middle-sized ports are specialized in Europe and Africa forelands, both with regard to imports and exports.

Marseilles and Dunkirk enjoy an intermediate position: they are rather close to the small and middle-sized ports for imports and could be termed nearer to global level for exports. In the case of manufactured goods, mostly containerized, Marseilles logically joins the group of global ports for both imports and exports as it handles significant amounts of cargo with main deep-sea markets of East Asia and North America. Finally, a clear hierarchy can be observed between global container ports and secondary ones. The latter are specialized in tramp or short sea shipping markets, mainly linked to Africa, Europe (non-EU countries), and the Middle East [START_REF] Guerrero | Les aires d'influence des ports de la France: entre réseau et gravitation[END_REF]. These results are consistent with those of [START_REF] Gouvernal | Short sea and deep sea shipping markets in France[END_REF], confirming that the majority of deep-sea consignments pass through main container ports. A comparison of the forelands of 2005 with those of the early 1980s indicate dramatic changes, essentially driven by containerization.

The first change is the widening of the gap between global and secondary ports. The structure of forelands follows a hierarchy closer to container shipping: the more diversified forelands are those of the main container ports (Northern Range ports and Marseilles). These ports are global in nature because they handle trade between France and most of the overseas regions.

The intermediary category of middle-size ports no longer exist. The hub and spokes networks of container transportation tend to marginalize ports that are not close to the main routes or main hinterlands.

A second change is the decline in traffic for many overseas regions served by the port of Marseilles, especially for imports. Beyond labor factors (strikes) that are the explanation, there is a deeper reason linked with the geographical position of Marseilles in the main maritime routes of container shipping. The traffic of the port of Marseilles, located at the north of Mediterranean, is essentially generated by its hinterland. Since the development of container hubs in the south of the Mediterranean, shipping companies have started increasingly serving Marseilles by feeder [START_REF] Notteboom | Concentration and load centre development in the European container port system[END_REF], Gouvernal et al., 2005).

In 1980s, in the early stages of containerization, Charlier showed, in the French context, that global ports also had larger hinterlands [START_REF] Charlier | Contribution méthodologique à l'étude des arrière-pays portuaires[END_REF][START_REF] Charlier | L'arrière-pays national du port du Havre : une approche macrogéographique[END_REF]. He also pointed out that overlapping between distinct hinterlands only takes place at the margins, which he called competition margins. This finding for France was slightly different from the substantially overlapping hinterlands observed by Hoare for British ports during the same period.

The analysis of [START_REF] Charlier | Contribution méthodologique à l'étude des arrière-pays portuaires[END_REF] is updated after four decades of containerization in our study.

In order to make our results suitable for an international audience, we have developed a simplified typology dividing hinterlands into four types, depending on the ports that handle their cargo (Figure 3): The Lower Seine ports (Le Havre and Rouen) are analyzed together. These ports handle a large share of the cargo of the départements located in the north-west and the center of France. These two ports are largely complementary to each other, with Le Havre handling general cargo mostly in containers, whereas Rouen handles bulk cargo. Rouen is an urban upstream port that mainly handles bulk quantities. It is the main European port for exports of wheat produced in the French Northern Plains. Le Havre serves the industry in its vicinity (i.e. Renault) and also the region of Paris in which a very high share of French population and GDP is concentrated. Both ports handle substantial amounts of petroleum products, but petroleum traffic has been excluded from this analysis, because their enormous volume is too strong an influence on the result of the model compared to other types of cargo.

The hinterland of the port of Marseilles covers the départements located in southern France, almost up to Lyon in the East and Toulouse in the West, with both city regions generating substantial amounts of general cargo. Significant amount of bulk cargo is generated by the chemical industry, metallurgy, and agriculture. Marseille has good maritime connections with Northern Africa, East Asia (except Taiwan, with CKYH alliance3 ), former USSR countries, and the Middle East.

The foreign ports of the Northern Range and Dunkirk share common hinterlands in the north and east of France. They handle a high share of maritime cargo generated by the départements located on the northern and eastern boundaries of France and much larger areas around Strasbourg, Dijon, and in some cases up to Lyon.

The secondary ports essentially have local hinterlands, and sometimes even less. Some of these ports are located on the Atlantic coast and in the Mediterranean close to France s boundary with Spain. The traffic they generate is a result of activities on a smaller scale such as in agriculture, animal farming, forestry products, chemical products, and building materials.

Globally, hinterlands show little variation on the basis of weight or value. More important variations can be found when imports and exports are compared. The core of the hinterlands of global ports remains rather unchanged; what really changes are the margins. Overlapping between the hinterlands of global and secondary ports is often the result of complementarity.

While the global ports handle manufactured cargo flows, the smaller ports take care of bulk cargo, mainly related to agriculture and animal farming. Overlapping between the hinterlands of global ports is much likely due to real competition. This competition takes place essentially in eastern France and mainly concerns the areas of Dijon and Lyon. Secondly, the area around Lille and the regions close to France s border with Belgium are shared between Belgian ports and Dunkirk, and the Lower Seine ports, as outlined before by [START_REF] Charlier | The Benelux Seaport System[END_REF][START_REF] Charlier | Hinterlands, port regionalisation and extended gateways: the case of Belgium and Northern France in[END_REF]. The influence of Dutch ports is much stronger on the region of Strasbourg, which is well connected to Rotterdam by the Rhine waterway. Most of time, hinterlands are spatially continuous, but some exceptions exist, mainly around Lyon, where rude competition exists between all the global ports.

Inland distance matters but not in the same ways for all types of cargo

All types of cargo flows are not equally constrained by distance. The doubly constrained spatial interaction model is used to measure these differences. The distance-decay parameter ( ) can be interpreted as a measure of the decrease of flows between ports and départements with distance, other things being equal. A distance-decay parameter of 0 means that the inland location of a shipper has no influence on port choice. A distance-decay parameter of 5 means that the nearest port is systematically selected. This "distance decay" or "friction of distance" effect varies depending on the type of flows being examined, for example, manufactured cargo as opposed to ores. 2 shows the results of the spatial interaction model. The average value of distancedecay parameter ( for all types is 2,7 (flows in tonnes, without petroleum products), which means a rapid decrease of the intensity of inland flows with an increase in distance. The results for imports ( 2,7) and for exports ( 2,6) are more or less equal and can be compared with the spatial patterns observed in the maps analyzed above (Figure 3). The results of the spatial interaction model show that French hinterlands are strongly distance-constrained. The maritime flows of the départements are usually handled by the nearest ports. From the point of view of the ports, links with local areas tend to be more intense. This finding is consistent with the concept of primary hinterlands introduced by [START_REF] Morgan | The pre-war hinterlands of the German North Sea ports[END_REF], but in the case of French ports, local areas are not necessarily captive, as will be shown later in this paper.

The estimated distance-decay parameters vary significantly between types of cargo (see Figure 4). The highest ( values have been obtained for flows of ores and waste materials of metallurgy ( 5,1) and petroleum products ( 4,4). Other highly distance-constrained flows are those of solid mineral fuel ( = 3,8), fertilizers ( = 3,8), metallurgical products ( = 3,3), and agricultural products ( = 3,1). The ( values obtained for the other types of cargo are weaker than the average: building materials ( =-2,6), animal food ( =-2,2) and chemical products ( =-2,1). The inland flows of manufactured products4 are least constrained by distance ( =-1,4). The value of friction obtained on manufactured flows in France is found to be higher than those obtained in the models of [START_REF] Pitts | Interport competition and cargo tributary areas for international containerised exports from the United States[END_REF] and [START_REF] Levine | Estimating an origin-destination table for U.S. Imports of waterborne containerised freight[END_REF] for U.S. container imports and exports.

For all types of cargo, the explanatory power ( ) of the combined effect of mass (tonnes generated by ports and départements) and distance is high (between 69% for manufactured goods and 94% for ores and waste materials of the metallurgical industry). Moreover, the variance specifically explained by distance (r ) provide interesting information on the degree of overlap between hinterlands of ports, without considering the mechanical effect of mass.

Figure 5. Typology of hinterlands based on the results of geographic and economic model

The high values of r could be associated with captive hinterlands, because most of the variance is explained by distance, that is, flows are handled by the nearest port. On the contrary, low values of r indicate that distance explains only a small part of the spatial distribution of flows, indicating substantially overlapped hinterlands, where competition between ports could virtually take place. Using both values of friction ( and the part of variance specifically explained by distance (r ) for distinguishing and grouping types of cargo flows, one can generalize with respect to the size of ports and the extent and overlapping of hinterlands. Such generalization leads to a typology of hinterlands having four basic types (Figure 5):

-The first type of hinterlands are defined by a weak mass effect and a strong friction (for example, agricultural products). The size of the département is of no consequence, because the activities generating cargo flows do not need to be too close to markets or populations. On the contrary, it is in low densely populated départements that most of flows are generated. The size of ports has no effect. Either small (except the ports of Languedoc) or large ports (except Rouen) can handle this cargo, which mainly consists of dry bulks. Ships are tramping and convey full loads. Shippers search to minimize inland haulage, because this kind of cargo cannot absorb high inland transport costs.

The second type of hinterlands display a strong mass effect and high friction (for example, petroleum products). Short flows predominate in them, because of the high friction or cost of overcoming distance. This is particularly true at the level of port industrial zones where ports and goods are co-located. In the main port industrial zones of Marseilles-Fos, Le Havre, and Dunkirk, most of the traffic is conveyed across relative short distances. Therefore the high value of the distance decay function is strongly driven by intra-port flows, where industrial activities and ports are co-located. It should also be noted that port accessibility has a strong influence in the choice of location of these kind of facilities, such petrochemical plants. This preference for proximity gives competitive advantage to port regions in attracting manufacturing activities [START_REF] Fujita | The role of ports in the making of major cities: selfagglomeration and hub-effect[END_REF]Mori, 1996, cited in Ducruet et al., 2009).

The third type of hinterland has strong mass effect and medium friction (for example, chemical products). In these locations, cargo is shipped over longer distances to the industries and to markets located in inland départements (for example, Lyon area) but there is little overlapping between hinterlands.

The fourth type of hinterlands has strong mass effect and weak friction. In these locations, manufactured cargo flows, where economies of scale of container ports play an important role and cargo is relatively valued high. The setting of hinterland accessibility strategies such as rail shuttles (Van Klink and Van den Berg, 1997, Gouvernal andDaydou, 2005, Debrie and[START_REF] Debrie | Intermodal rail in Western Europe: actors and services in a new regulatory environment[END_REF], barge services (Frémont andFranc, 2010, Franc and[START_REF] Franc | Understanding hinterland service integration by shipping lines and terminal operators: a theoretical and empirical analysis[END_REF] and inland terminals (Notteboom andRodrigue, 2005, Rodrigue et al., 2010) also contribute to the lower friction of distance of these flows, which are mostly containerized. This type of hinterland is strongly influenced by the relative location of the consumer population and national markets. The inland départements that generate the most important manufacturing flows are those of Paris and large cities (with a population in excess of 200,000), where wholesalers are overrepresented [START_REF] Guerrero | Freight flows and urban hierarchy[END_REF]. Largest départements and global ports have the largest flow volume and also undertake some of the longest hauls.

The results provided by the spatial interaction model suggest several things. First, the size of ports and départements are primary variables in explaining the pattern of export flows through the ports in the model. Large ports tend to have the largest number of port calls, serve most destinations , and boast the best of hinterland connections. The trend toward load centering and hubbing by the shipping lines has helped to encourage this trend. Inland urban areas are also crucial, because they help generate increasing amounts of cargo, especially manufactured flows. For the purposes of our study, however, distance remains a strong factor in the flow of cargo via seaports. Most types of cargo experience strong levels of distance-decay for exports and imports. Manufactured goods, mostly containerized, remain distance-constrained, but to a lesser extent than the other types of cargo. This might indicate that distance is a factor to contend with for both containerized and non-containerized cargo, but the dominance of big ports in manufactured goods (that is, containerized) is much important than for the other types of cargo. This tempers the argument that inland distance no longer matters in the seaport used (Van Klink and Van den Berg, 1997).

The model as proposed does not explain a minor proportion of the variance in the dataset.

There are probably some variables, other than volume and distance, which have some effect on spatial structure of flows between ports and départements. Factors such as further information on the maritime portion of the voyage, which are not included in the present dataset, might help increase the explanatory power of the model. Anyway, it remains a fact that there are distinct catchment areas for different overseas regions. This idea is supported by [START_REF] Robinson | The hinterland-foreland continuum : Concept and methodology[END_REF] who drew different tributary areas to the port of Vancouver for trade with Japan and United Kingdom. He found, in the North American context, that hinterlands and forelands were strongly linked and should be analyzed simultaneously.

Containerization has strengthened the link between hinterlands and forelands

To test Robinson s hypothesis on the continuity between hinterland and foreland after containerization, a detailed study on the hinterlands of Le Havre and Marseilles was undertaken. It narrows focus on a longitudinal transect that follows the inland highway between both the ports (figure 6). The graph represents the local share of each port in the total maritime trade of the département. This analysis validates the hypothesis that there exists a hinterland foreland continuum for global ports in France. Marseille s peripheral location at the southern end of France railroad has meant, in effect, that the port s competitors, rather than being on the same coastline, are in fact at the northern end of the highway or at least in the industrial heartland and major Canadian markets. The southward extension of the hinterland of Le Havre for U.S. maritime trade can be easily explained by its very frequent maritime services [START_REF] Frémont | Northern European range: shipping line concentration and port hierarchy[END_REF]. Moreover, Le Havre is the last port of call for most of services between northern Europe and North America. French shippers in the foreland often prefer Le Havre, even if it would mean a larger inland haulage compared to Marseilles.

The situation is slightly different for East Asian trade, although Le Havre has unquestionably more frequent maritime links. This advantage is partially compensated by shorter transit times from Marseilles. The inland distance appears to be the factor that tips the balance in favor of one port or another.

Conclusion

What seems to have emerged from the empirical work of the past dozen years is a compromise vision. Distance matters a lot, though possibly less than it did before modern telecommunications. Borders also matter a lot, though possibly less than they did before free trade agreements. The spaceless, borderless world is still a Platonic ideal, a long way from coming into existence. Krugman, 2004, p. 13 Our results show that ports are not isolated from their hinterlands, and the main cargo flows take place between ports and local regions. In our analysis, the combined effect of the size (volume of cargo generated by ports and départements) and distance accounts for at least 86% variation in total flows and 69% in manufactured flows. The rest is probably due to foreland differentiation discussed earlier, strategies of the transport operators and governments concerning the ports they manage and/or for which they authorize development, specific geographies of niche markets and hub strategies (including direct rail links), and other specificities that cannot be included in a global model. As it is, the importance of distance in explaining hinterlands indicates that current inland connections are stable and path dependent over the long term.

Our results are particularly interesting in the light of Charlier s (1981) finding that French hinterlands remain largely constrained by distance. In our study, whereas the share of the hinterlands between gateways and secondary ports remains unchanged for all types of cargo, only the first can attract manufactured cargo flows. These seemingly contradictory results are in fact consistent one with another. With regard to containerized cargo, a select group of advantaged ports has benefited because containerization at the expense of many other ports, both large and small. With respect to bulks and short sea shipping, equalization is observed provoked by the development of niche markets, mainly driven by agriculture, forage, and forestry products.

Our conclusions are valid only for France. More empirical research is necessary to make further generalization to other European countries. Studies on inland countries such as as Austria show that competition between ports seems to be much fiercer since no single port has a cost advantage over the other ports [START_REF] De Langen | Port competition and selection in contestable hinterlands; the case of Austria[END_REF]. The same gap between inland (competitive) and coastal (less competitive) states has been observed in the United States [START_REF] Pitts | Interport competition and cargo tributary areas for international containerised exports from the United States[END_REF][START_REF] Levine | Estimating an origin-destination table for U.S. Imports of waterborne containerised freight[END_REF]. In Eastern Asia, most of sea markets are located near-shore and therefore hinterlands tend to be concentrated in the regions of ports [START_REF] Lee | A tale of Asia s world ports: the spatial evolution in global hub port cities[END_REF][START_REF] Itoh | Market Area Analysis of Ports in Japan: An Application of Fuzzy Clustering[END_REF]. In the specific case of China, the industrial development of the West is seen to be contributing to the increase of inland haulage and may probably lead to an increase in competition between ports.

There are several implications of this conclusion. First, port authorities must make difficult choices when deciding how and where to concentrate marketing efforts. Sometimes, port authorities tend to focus on competition margins without caring enough about the immediate hinterland wrongly assumed to be captive. This analysis finds that immediate hinterlands are not so captive (cf. Le Havre) and so the demand of local shippers must be taken seriously.

Second, hinterlands go beyond national borders (cf. Belgian and Dutch ports in Northern France). As argued earlier by [START_REF] Baird | Public goods and the public financing of major European seaports[END_REF], partially common hinterlands for global ports suggest the need for a more cohesive European policy for these ports in particular.

Last but not least, the model has also quantified the values of friction for different types of cargo. This is an important finding of our study as it provides an empirical support for visualizing scenarios with regard to the impact of abandoning secondary ports for economic activities such animal feeding. The stronger influence of friction relative to other factors in these hinterlands provides an empirical justification for giving priority to secondary ports in public policies.

The year of observation in this paper is 2005. The global financial crisis of 2008 has considerably impacted European demand for imported goods, implying a decline in traffic. Container throughput figures of main container ports serving France in 2009 were 11% to 19% lower compared to 2008. At the time of writing this paper, it was still too early to determine if the 2008 crisis has increased (or not) the gap between global and secondary ports. [START_REF] Notteboom | Concentration and the formation of multi-port gateway regions in the European container port system: an update[END_REF] points out two developments contributing to the enlargement of the hinterlands of global ports. On one hand, reconfigurations in liner services have resulted in cargo consolidation in larger ports, whereas on the other an increased geographical specialization of global ports is visible vis-à-vis specific overseas maritime regions.

Following the examples of other countries (except Germany), France is expected to implement new rules to promote ecologically sustainable transport (except Ecotax) in the next few years. This will an impact on the price of road transport and will perhaps contribute to attracting containers to secondary ports. It is however not entirely clear at this point to what extent these trends will affect the hinterlands.

Figure 2 .

 2 Figure 2. Ports (and sets of ports) handling French extra-EU Trade (2005)

Figure 3 .

 3 Figure 3. French hinterlands of global and secondary ports

Figure 4 .

 4 Figure 4. Relationship between the distance to the port and the intensity of cargo flows

Figure 6 .

 6 Figure 6. Hinterlands of Le Havre and Marseilles. Trade with East Asia and US

  Marcadon evokes the example of the ports of Sudeste (Brazil), where containerization was less developed. The French shipping company CGM offered adapted services to the handling capacities of South American ports where containerized lines served the East Coast and mixed ships served the West Coast.

In the 2000s, containerization in France proceeded to expand well beyond the level reached in the early 1980s. Most of French deep sea flows of manufactured goods are now transported by the container. In 2012 2 , the main container ports serving France were Le Havre (2.3 M TEUs) on the Northern Range, Marseilles (1 M TEUs) on the Mediterranean, and the foreign Northern Range ports of Antwerp (8.6 M TEUs) and Rotterdam (11.9 M TEUs), which handle a part of French container flows. Other much smaller container ports are Dunkirk and Rouen (0.2 M TEUS each) in the Northern Range, and Nantes-Saint-Nazaire (0.2 M TEUs) and Bordeaux (0.1 M TEUs) in the Atlantic.

Table 2 .

 2 Results of the spatial interaction model

	Type of cargo

Appendix

presents the spatial distribution of French maritime trade outside EU in the départements.

Source : CI Online.

Cosco/K Line/Yang Ming/ Hanjin

The Appendix 3 presents French hinterlands of manufactured cargo, using the same method of the figure

Acknowledgements

This research is part of my unpublished PhD Thesis at University Paris 7 Paris Diderot. Special thanks go, in particular, to my supervisors, Professors Jean Debrie (Univ. Paris 1) and Claude Grasland (Univ. Paris 7), for their helpful suggestions and discussions during the study. I wish to express my gratitude to IFSTTAR and AME-SPLOTT for offering financial assistance and first-class facilities during my study. I also thank the anonymous reviewers for their helpful and constructive comments that contributed to the improvement of the manuscript.


Gabriela Montoya
email: gabriela.montoya@univ-nantes.fr

Luis-Daniel Ibáñez

Hala Skaf-Molli

Pascal Molli
email: pascal.molli@univ-nantes.fr

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

Query Processing for SPARQL Federations with Data Replication

Keywords: Source Selection, SPARQL Endpoints, Data Replication

Data replication and deployment of local SPARQL endpoints improve scalability and availability of public SPARQL endpoints, making the consumption of Linked Data a reality. This solution requires synchronization and specific query processing strategies to take advantage of replication. However, existing replication aware techniques in federations of SPARQL endpoints do not consider data dynamicity. We propose Fedra, an approach for querying federations of endpoints that benefits from replication. Participants in Fedra federations can copy fragments of data from several datasets, and describe them using provenance and views. These descriptions enable Fedra to reduce the number of selected endpoints while satisfying user divergence requirements. Experiments on real-world datasets suggest savings of up to three orders of magnitude.

Introduction

Query limitations imposed by existing public SPARQL endpoints may be too restrictive for real-world applications. Data replication and deployment of local SPARQL endpoints may be a solution to improve data availability and to reduce the workload of public endpoints, and thus, make public endpoints ready for action [START_REF] Aranda | Sparql webquerying infrastructure: Ready for action[END_REF]. However, exposing replicas through local SPARQL endpoints pose two problems. Firstly, querying replicas may produce obsolete answers, whenever Linked Data change [START_REF] Käfer | Observing linked data dynamics[END_REF] and replicas are unsynchronized and diverge with the original sources [START_REF] Dourish | The parting of the ways: Divergence, data management and collaborative work[END_REF]. Secondly, using existing federated engines on replicas may deteriorate their performance because the number of contacted endpoints increases. To illustrate, consider a DBpedia dataset d 1 , and a federation that only accesses a public SPARQL endpoint of DBpedia. Using FedX [START_REF] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF], the execution of a three-triple pattern query with predicates from DBpedia is quite simple because the query can be exclusively executed in one endpoint. If the same query were executed in a federation with several endpoints, we would expect better performance. Surprisingly, this is not the case. Suppose d 2 is a replica of d 1 , and the federation now includes the public DBpedia SPARQL endpoint and another local SPARQL endpoint that accesses d 2 . Since each triple pattern is executed against both endpoints, the query performance deteriorates.

A recent index-based approach named DAW [START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF] has been proposed to detect data duplication and to reduce the number of selected sources. The index is built from data in the federation at a given time. In the previous example, FedX with DAW would contact only one DBpedia endpoint. However, DAW does not consider source dynamicity and consequently, the datasets will diverge whenever data change. In this paper, we propose Fedra, an approach for querying federations of SPARQL endpoints that takes advantage of data replication. Fedra relies on knowledge about replicas to reduce the number of selected sources even in presence of dynamic datasources and divergent replicas. Replicas are defined as SPARQL views [START_REF] Le | Rewriting queries on sparql views[END_REF] and the containment relationship between views. These descriptions are annotated with data provenance and timestamps that identify the state of the original datasource when the replica was created. Divergent replicas will have different timestamps. In the above example, d 1 is the original source, with timestamp t 0 , while d 2 is a replica with the same timestamp, i.e., d 1 and d 2 have the same RDF triples. Suppose that d 1 inserts or deletes some triples, then the timestamp of the new state of d 1 is t 1 , where t 1 > t 0 . Since t 1 > t 0 , d 1 and d 2 diverge, i.e., d 1 has a more recent state than d 2 . The divergence can be computed as the number of operations that need to be integrated into the replica to synchronize it with the original dataset. Depending on the value of the divergence tolerated by a user, the query can be executed against d 2 even if d 1 is not available, at the risk of obtaining an inexact number of answers. Executing queries against replicas allows to overcome public endpoints limitations [START_REF] Aranda | Sparql webquerying infrastructure: Ready for action[END_REF], but to avoid generating obsolete answers, divergence has to be controlled.

Fedra solves the source selection problem in presence of divergence, and it is able to compute the divergence between replicas to decide which sources should be chosen to answer a query. Fedra does not require access to dataset instances to check overlapping. Thus, it can be used in federations with frequently updatable datasets where different replicas coexists.

The main contributions of this paper are: i) Endpoint descriptions in terms of SPARQL views, containment relationships between views, data provenance, and timestamps; ii) Fedra source selection algorithm that reduces the number of selected sources while divergence between replicas is controlled; and iii) an experimental study that reveals the benefits of both exploiting knowledge encoded in endpoint descriptions and controlling divergence to avoid obsolete results.

The paper is organized as follows: Section 2 presents Fedra and the source selection algorithm. Section 3 reports our experimental study. Section 4 summarizes related work. Finally, conclusions and future work are outlined in Section 5.

Fedra Query Processing for SPARQL Federations with Replication

Fedra enables federated engines to take advantage of data replication during query processing. A dataset is a set of RDF triples accessible through a public SPARQL endpoint. A replica is defined as a view expressed as a CONSTRUCT SPARQL query that retrieves a dataset fragment, i.e., a subset of the dataset.

Replicas can be accessible through local SPARQL endpoints and can be part of a federation. Figure (1a) illustrates three fragments of a given dataset D: D1, D2, and D3. D1 and D3 are defined by view V 1, they contain all the triples of D. D2 is defined by view V 2 and corresponds to a subset of D. There is a containment relationship among these datasets, i.e., D ⊑ Given a SPARQL query Q, we are interested in the following source selection problem: selecting the SPARQL endpoints that produce the most complete answer for Q while avoiding the selection of: i) public endpoints, and ii) multiple local endpoints that retrieve the same answer for a given sub-query of Q.

V 1 D1, D ⊑ V 2 D2, and D ⊑ V 1 D3.
For the first triple pattern of query in Listing 1, Fedra can select either endpoint E3 or endpoint E5 because they provide access to data defined by the same view. Endpoints E5 and E6 provide access to fragments F 1 and F 2 which are defined by different views, and they may have different instantiations for the second triple pattern; thus, both endpoints E5 and E6 need to be selected. To reduce the number of selected sources, E5 will be chosen instead of E3 because it will also be used for the second triple pattern. This choice gives the opportunity to the query engine of reducing the number of contacted endpoints while it maximizes the number of operations performed by an endpoint.

Describing Local SPARQL Endpoints

In a Fedra federation, datasets accessible through local SPARQL endpoints are described explicitly in terms of views and implicitly, in terms of containment relationships between these views. In addition, they are annotated with data provenance and timestamps. A timestamp states the date when the fragment data is originally published in the public dataset.

Updating Public SPARQL Endpoints

Data accessible through public SPARQL endpoints can be updated, and divergence could exist with their replicas in the local endpoints. For example, DBpedia data frequently change, and existing replicas that do not integrate these last changes will be divergent with data in DBpedia. Fedra can select local endpoints to obtain answers but with some divergence, or it can choose a public SPARQL endpoint, if this is available. Although public SPARQL endpoints offer access to the freshest data, they may time out executing complex or nonselective queries. Therefore, selecting possible divergent local endpoints could be a reliable choice whenever divergence is controlled.

Consider datasets from Figure (1a), where triples k1=(o1 p2 o7) and k2=(o3 p3 o8) are inserted in D after the fragments are created. Figure (2a) presents a possible scenario where dataset D1 has been created at timestamp T+1. D1 contains k1 but not k2. Dataset D2 is created at the timestamp T , and it does not reflect the updates of D. Finally, dataset D3 is created at the timestamp T+2, therefore, it reflects the last state of D, i.e., D3 has the freshest data of the public endpoint. As the triple k2 is not available through endpoint E3, but it is available through endpoint E5, then there is a divergence between the dataset D and its fragments D1 and D2 at T+2.

Divergence is an editing distance between a public dataset and a replica. It can be defined as the number of the insert and delete operations that need to be applied to the replica in order to synchronize it with the original dataset. An operation in the public data introduces divergence with a replica, whenever it inserts or deletes a triple k that is relevant to a view V of the replica, i.e., there is an instantiation of V that includes k. In the above example, triple k1=(o1 p2 o7) inserted into D at T+1 is relevant to V 1 and V 2, while triple k2=(o3 p3 o8) inserted to D at T+2 is only relevant to view V 1. However, D1 and D2 do not include k2 and k1, respectively. Thus, only one insertion needs to be performed on D1 and D2 to reach convergence, i.e., their divergence is 1. Divergence of D3 is 0 because D3 is up to date with D. In general divergence of a replica D1 with respect to dataset D can be defined as in Equation 1, where k is a triple in D.

Divergence(D1, D) = Σ k∈inserts(D)∧date(D1)<date(k)≤date(D) 1 +Σ k∈deletes(D)∧date(D1)<date(k)≤date(D) 1 (1)
Divergence defined in Equation 1 is for replicas of D that contain all its triples. If a replica only includes a subset of D, i.e., it is defined by a view that does not retrieve all its triples, then divergence can be defined as in Equation 2. Predicate

matches(p, V) is satisfied if triple k is relevant for view V . Divergence(D1, D) = Σ k∈inserts(D)∧date(D1)<date(k)≤date(D)∧matches(k,V ) 1 +Σ k∈delete(D)∧date(D1)<date(k)≤date(D)∧matches(k,V ) 1
(2) Live updates of DBpedia3 can be used to compute divergence between a replica of DBpedia and the public DBpedia relying on the timestamp of the last update performed at a given time. If we consider a version of DBpedia of May 13, 2013 and a replica defined by view V whose last update was done on May 1st, 2013, then divergence can be computed as the sum of the number of inserts and deletes performed during days 2-13 of May that are relevant to view V .

Source Selection Algorithm

Algorithm 1 selects the endpoints that can answer each triple pattern in a query, and the views that define the datasets accessible through these endpoints (e and v in line 7). The function canAnswer can be implemented using an ASK query for dynamic data, or relying on view definition for more stable data. origin function is used to determine if one of the already considered endpoints provides the same data that e for the fragment defined by v; in that case, e is included in f ragment as a valid alternative to obtain data provided by the other members of f ragment (lines 11-13). If the data is already provided by another endpoint f , then it is not necessary to consider e (lines 16-17, 20-21). If the data provided by a set of endpoints f ragment is already provided by e, then it is enough to query e and f ragment can be safely removed from the endpoints to query (lines 14-15, 18-19). When the user provides a threshold of divergence T D, then this can be included in line 7 as divergence(e, v) ≤ T D. This algorithm produces a list whose elements are list of equivalent endpoints under a given view. This means that they offer the same fragment defined by the view, then during execution only one of them needs to be contacted. And different elements of this resulting list correspond to different fragments that should be considered in order to obtain an answer as complete as possible, modulo the considered endpoints and the allowed divergence threshold.

After the source selection per triple pattern is done, a source selection for the whole query is performed, this is presented in Algorithm 2. We can perform the source selection using an heuristic for the finding the minimal set cover [START_REF] Dasgupta | Algorithms[END_REF]. In the set cover problem, given a set of elements S and a collection of subsets of set C, the goal is to obtain a collection C ′ , C ′ ⊆ C, such that all the elements in S belong to at least one element in C ′ , and C ′ has the minimal size possible.

for each k ∈ tp(Q) do ⊲ k is a triple pattern in Q 3:
endpoints ← ∅

4:

for each e ∈ Es do

5:

for each v ∈ views(e) do

6:

if canAnswer(e, v, k) then

7:

include ← true

8:

for each f ragment ∈ endpoints do

9:

(f, w) ← getOne(f ragment)

10:

if origin(e, v) = origin(f, w) ∧ v ∈ containedIn(w) ∧ w ∈ containedIn(v

33: end function

Consider a triple k1, such that D(k1) = {(v1, {e1, e2}), (v2, {e3}), (v3, {e4, e5})}, this means that to obtain all the possible bindings for k1, then it should be evaluated in at least one endpoint of each of the sets, for example, evaluating it in e1, e3 and e5 would be enough. We can model each endpoint by one subset of the collection C, and the elements of each subset are the triples that can be evaluated by the corresponding endpoint. In order to respect the different fragments (three in the example), we include as many different elements in S as different fragments should be considered (three in the example). In the example: k1 1 ∈ e1, k1 1 ∈ e2, k1 2 ∈ e3, k1 3 ∈ e4 and k1 3 ∈ e5 (lines 2-13) The selected collection defines the endpoints where each triple pattern should be evaluated (lines 15-24). The overloadedEndpoints variable allows to restrict the set of endpoints where the triples are evaluated.

Algorithm 2 Source Selection algorithm

Experiments

We formulate the following research questions for a given SPARQL query: RQ1) can Fedra reduce the number of selected sources?, RQ2) can Fedra reduce the number of selected public endpoints?, RQ3) can Fedra select sources that produce more complete answers?, and RQ4) Fedra can select sources that satisfy a user threshold of divergence. How does increasing the threshold affect the completeness of the answer?. Datasets and Query Benchmarks: we used the datasets Diseasome and Publication 4 , and executed 89 queries where 59 queries are those executed in [START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF] and 30 conjunctive queries that are composed of a larger number of triple patterns. The queries are composed of single triple pattern queries (ST), star shaped queries of 2-6 triple patterns (2S-6S), and path queries of 2-4 triple patters (2P-4P). Contents of these datasets were characterized using conjunctive star-shaped CONSTRUCT queries such that the union of their evaluation provides the whole dataset. The views were randomly produced such that they have between two and ten triple patterns, and they contain as much overlap as possible, i.e., triples are considered for all the views they can match. For the Diseasome federation 58 views were generated, and 508 views for the Publication federation. In order to reproduce a realistic scenario, we consider that few views are highly used and many views are rarely used. Hence the views were sorted according to their i.e., for how many queries they are useful, and distributed using a power law distribution over a set of endpoints 5 . Samples of the power law distribution determines in how many endpoints each view is assigned, and a uniform distribution is used to assign them to endpoints. Parameters of the power law distribution are X min =2 and α=2.5. The number of local endpoints for the Diseasome federation is 18, and for Publication is 345. Virtuoso6 endpoints are used, and timeouts were set up to 1,800 secs. and 100,000 tuples. Table (1a) shows data distribution over ten of the endpoints of the federation for Diseasome, and Listings ( 3) and ( 4) present the views that define two fragments of Diseasome7 .

Divergence among replicas:

We have created two divergent datasets of Diseasome: Diseasome1 and Diseasome2. Diseasome1 is composed of 90% of the Diseasome tuples, while Diseasome2 has just 80% of these triples. The removed triples were selected following an uniform distribution over all the views. In the divergent setup the included data in each endpoint was uniformly taken from Diseasome, Diseasome1, and Diseasome2. The number of views that belong to each dataset per endpoint in this setup is shown in Implementations: Fedra is implemented in Java 1.7 and the Jena 2.11.0 library8 . Fedra produces SPARQL 1.1 queries where each triple pattern is annotated with a service clause that indicates where it will be executed. These queries are posed to FedX3.09 , one state-of-the-art SPARQL 1.1 federated engine.

Evaluation Metrics: i) Number of Triple-Wise Selected Public Endpoints (SPE):

corresponds to the sum of the number of times the public endpoint has been selected per triple pattern. ii) Number of Triple-Wise Selected Sources (NTWSS): corresponds to the sum of the number of different sources that has been selected per triple pattern. iii) Execution Time (ET): corresponds to 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 query execution by the underlying engine (ETUE). Time is expressed in seconds (secs.). A timeout of 300 secs. has been enforced for ETUE. SST was measured using System.currentTimeMillis() provided by Java and divided by 1000, and ETUE corresponds to the absolute wall-clock system time as reported by the Python time.time() function. iv) Re-call (R): corresponds to the size of the intersection between the obtained answers and the expected answers divided by the number of expected answers; where the expected answers are the ones obtained from an endpoint containing the whole dataset. v) Duplicates (Du): corresponds to the percentage of duplicates present in the answer. This is computed as (1precision)×100, where precision is defined as the size of the intersection between the obtained answers and the expected answers divided by the number of obtained answers; duplicates are considered.

The range of Du is [0-100], where 0 means that the answer does not contain duplicates, while values close to 100 indicate that duplicate values outnumber the non-duplicate values. vi) Divergence (Div): corresponds to the total number of operations, insertions and deletions, that need to be performed in the relevant replicas to integrate the operations performed in the public dataset that have not been yet included in the relevant replicas. The divergence can be measured in a course-grained way considering the operations over the whole dataset, or fine-grained way considering the operations over a relevant fragment of the dataset. We have use a fine-grained measurement. For these metrics, we report the average value obtained per query type.

Reduction of the Number of Selected Sources

We ran Fedra to compute the selected sources to answer our benchmark queries on the Diseasome and Publication federations, and thus, answer our research questions RQ1 and RQ2. We used FedX to generate the execution plans of the queries, and from them compute the number of selected sources. We hypothesize that Fedra is able to reduce the number of selected sources and the number of selected public endpoints, as far as the containment relationship holds among the replicas and the original dataset. Tables (2a) and (2b) show the NTWSS for Fedra and FedX. These results suggest that our hypothesis are true, and Fedra is able to reduce the number of selected sources up to two orders of magnitude, and the number of selected public endpoints is zero for all the queries but one. We notice that these savings are larger for federations with a large number of endpoints like Publication, and specially for queries with many triple patterns.

Increase of the Recall

We use FedX to run our benchmark queries on the Diseasome and Publication federations, and SPARQL 1.1 queries annotated with service clause according to sources selected by Fedra. To answer our research question RQ3, we hypothesize that Fedra is able to increase the recall (R) of the obtained answers, while keeping duplicates (Du) relatively low. Tables (2a) and (2b) show the R and Du for Fedra and FedX. These results suggest that our hypothesis holds, and Fedra is able to increase recall while producing relatively few duplicates. We notice that these savings are larger for federations with a large number of endpoints like Publication, and specially for queries with many triple patterns.

Answering Queries in Presence of Divergent Data

We use FedX to run our benchmark queries and SPARQL 1.1 queries annotated with service clause according to sources selected by Fedra for the Diseasome federation with divergence and thresholds of 0% and 25%. To answer our research question RQ4, we hypothesize that as the threshold increases, the obtained recall may decrease. Table (3) reports NTWSS, ET, Recall and Duplicate values for Fedra and FedX. These results suggest that our hypothesis is true in most of the cases but not in all. When threshold increases, the recall should decreases. However, when this does not hold, increasing the threshold allows to either: i) reduce the number of selected sources, or ii) select most suitable sources. This happens in query types 3P, 4P, and 6S where the number of queries that time out is reduced from 3, 2, and 5 to 1, 1, and 4, respectively.

Related Work

The Semantic Web community has proposed different approaches to consume Linked Data from federations of endpoints [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] Schwarte | Fedx: Optimization techniques for federated query processing on linked data[END_REF]. Although source selection and query processing techniques have successfully implemented, none of these approaches is able to exploit information about data replication to enhance performance and answer completeness. Recently Saleem et al. propose DAW [START_REF] Saleem | Daw: Duplicate-aware federated query processing over the web of data[END_REF], a source selection technique that relies on data summarization to describe RDF replicas and thus, reduces the number of selected endpoints. For each triple pattern in a SPARQL query, DAW exploits information encoded in source summaries to rank relevant sources in terms of how much they can contribute to the answer. Source summaries are expressed as min-wise independent permutation vectors (MIPs) that index all the predicates in a source. Although properties of MIPs are exploited to efficiently estimate the overlap of two sources, since Linked Data can frequently change, DAW source summaries may need to be regularly recomputed to avoid obsolete answers. To overcome this limitation, Fedra provides a more abstract description of the sources which is less sensible to data changes; data provenance and timestamps are stored to control divergence.

Divergence and data replication, in general, have been widely studied in distributed systems and databases. There is a fundamental trade-off between data consistency, availability and tolerance to failures. In one extreme, distributed systems implement the ACID transactional model and ensure strong consistency [START_REF] Brewer | Pushing the cap: Strategies for consistency and availability[END_REF]. Although ACID transactional models have been extensively implemented, it has been shown that in large-scale systems where data is partitioned, ensuring ACID transactions and mutual consistency is not feasible [START_REF] Brewer | Pushing the cap: Strategies for consistency and availability[END_REF]. Based on these results, Fedra does not rely on strong consistency that would constrain Linked Data participants. Contrary, Fedra exploits source descriptions to reduce the number of contacted endpoints while satisfies divergence thresholds. Thus, depending on the divergence tolerated by a user, a query can be performed against replicas if accessing the original source is not possible.

Conclusions and Future Work

We presented Fedra a source selection approach that takes advantage of replicated data, and reduces the number of selected endpoints given a threshold of divergence. A lower value of divergence allows query engines to produce fresher answers but at the risk of failing to get answers. Contrary, a higher value risks engines to retrieve answers that are obsolete, while chances of producing answers increases as the space of possible selected sources is larger.

In the future, we plan to consider a finer-grained granularity of divergence. Instead of considering divergence of a replica, we will compute divergence for specific predicates, e.g., divergence of predicates that represent links between datasets. In addition, we plan to integrate DAW with Fedra to handle replicas with missing descriptions.

Listing 2 :Fig. 2 :

 22 Fig. 2: Coexisting versions of fragments of dataset D

) then 11 :

 11 fragment.add((e, v)) 12: include ← f alse 13: else if origin(e, v) = origin(f, w) ∧ v ∈ containedIn(w) then 14: endpoints.remove(fragment) 15: else if origin(e, v) = origin(f, w) ∧ w ∈ containedIn(v) then 16: include ← f alse 17: else if f ∈ origin(e, v) ∧ origin(e, v) = origin(f, w) then 18: endpoints.remove(fragment)19:else if e ∈ origin(f, w) ∧ origin(e, v) = origin(f, w) then 20:

  Input: Q: SPARQL Query; Es: set of Endpoints; views : Endpoint → set of views; origin : Endpoint × view → Endpoint; overloadedEndpoints : set of Endpoint; overloadedEndpoints : set of Endpoint; containedIn : view → set of view. Output: E: Dictionary From Triple Pattern to List of Endpoints. 1: usableEndpoints ← Es -overloadedEndpoints 2: D ← tripleSourceSelection(Q, usableEndpoints, views, origin, overloadedEndpoints, con-tainedIn) 3: S ← ∅ 4: C ← ∅ ⊲ C(e) has as default value the empty set 5: for each k ∈ tp(Q) do ⊲ k is a triple pattern in Q for 15: C ′ ← MinimalSetCovering(S, C) 16: endpoints ← getEndpoints(C ′ ) 17: E ← ∅ 18: for each k ∈ tp(Q) do 19:

  The public SPARQL endpoint E1 provides access to D, while local SPARQL endpoints E3, E4, and E5 access D1, D2, and D3, respectively, as seen in Figure(1d). In addition, an endpoint can provide access to data from different datasets like E5 that combines D3 and F 1, as seen in Figure(1d). Public and local SPARQL endpoints can contribute during federated query processing. Therefore, workload on public endpoints can be reduced, and local SPARQL endpoints can replace the public ones whenever they are not available.

			Listing 1: Query Q1
	SELECT DISTINCT ? s ? o ? r
	WHERE {
	? s p1 ? o .
	? o p4 ? r
	}
		D		F
		s1 p1 o1 .		o1 p4 o5 .
		o1 p2 o2.		o2 p4 o5.
		s2 p1 o3. o3 p3 o4		o3 p4 o6. o4 p4 o6
	V1 V2	V1	V3	V4
	D1	D2	D3	F1	F2
	s1 p1 o1 .		s1 p1 o1 .
	o1 p2 o2.		o1 p2 o2.
	s2 p1 o3. o3 p3 o4	s1 p1 o1 . o1 p2 o2	s2 p1 o3. o3 p3 o4	o2 p4 o5	o1 p4 o5 . o2 p4 o5
	(a) Fragment of Dataset D	(b) Fragments of Dataset F
	View		Definition
	V1 CONSTRUCT { ?x p1 ?y . ?y ?p ?z } WHERE { ?x p1 ?y . ?y ?p ?z }
	V2 CONSTRUCT { ?x p1 ?y . ?y p2 ?z } WHERE { ?x p1 ?y . ?y p2 ?z }
	V3	CONSTRUCT { o2 p4 ?x } WHERE { o2 p4 ?x }
	V4	CONSTRUCT { ?x p4 o5 } WHERE { ?x p4 o5 }
			(c) Views definitions
		Dataset D F D1 D2 D3 F1 F2
		Endpoint E1 E2 E3 E4 E5 E5 E6
			(d) Endpoints contents
	Fig. 1: Example of Different Fragments and Containment Relationships

  Algorithm 1 Triple Pattern Source Selection algorithm Input: Q: SPARQL Query Input: Es: set of Endpoints Input: views : Endpoint → set of views ⊲ views offered by each endpoint Input: origin : Endpoint × view → set of Endpoint ⊲ endpoints from which the content of each view is taken Input: overloadedEndpoints : set of Endpoint ⊲ endpoints that should not be selected Input: containedIn : view → set of view ⊲ containment relation among views Output: D: Dictionary From Triple Pattern to List of List of Endpoints ⊲ endpoints where each fragment of each triple pattern can be found

1: function tripleSourceSelection(Q,Es, views, origin, overloadedEndpoints, containedIn) 2:

Table 1 :

 1 Table (1b). Data Distribution over ten endpoints, definitions of three fragments, and number of views that belong to each of the coexisting datasets in the divergent setup composed of Diseasome (D), Diseasome1 (D1), and Diseasome2 (D2).

	Listing 3: view49
	CONSTRUCT WHERE { ? x1 owl : sameAs ? x2 .	Listing 4: view27
	? x1 d i s e a s o m e : g e n e I d ? x3 .	CONSTRUCT WHERE {
	? x1 r d f s : l a b e l ? x4 .	? x1 r d f : t y p e ? x2 .
	? x1 d i s e a s o m e : b i o 2 r d f S y m b o l ? x5 .	? x1 d i s e a s o m e : omimPage ? x3
	? x1 r d f : t y p e ? x6 .	}
	? x1 d i s e a s o m e : h g n c I d ? x7
	}

Table 2 :

 2 Number of Triple-Wise Selected Public Endpoints (SPE), Triple-Wise Selected Sources (NTWSS), Execution Time (ET), Recall and Duplicates (Du) using Fedra and FedX for Diseasome and Publication Federations. For Fedra, ET is detailed in Source Selection Time (SST) and Query Execution Time by the Underlying Engine (ETUE). Relevant results are highlighted in bold.

		(a) Diseasome
	Query	Fedra	FedX
	Type SPE NTWSS SST ETUE Recall Du SPE NTWSS ET Recall Du
	ST 0.00	1.60 1.60 1.28 1.00 21.80 1.00	17.80 1.94 0.88 83.60
	2P 0.00	3.00 3.00 7.15 1.00 48.50 2.00	35.75 96.79 0.50 25.00
	3P 0.00	3.80 3.80 10.38 0.80 59.60 3.00	53.60 38.50 0.21 39.00
	4P 0.00	6.00 6.00 162.44 0.02 48.50 4.00	76.00 324.74 0.00 0.00
	2S 0.00	4.00 4.00 11.64 1.00 48.20 2.00	37.00 169.47 0.40 18.00
	3S 0.40	6.00 6.00 123.17 0.60 34.60 3.00	42.40 174.81 0.40 39.40
	4S 0.00	7.00 7.00 138.97 0.60 0.00 4.00	75.60 240.97 0.00 0.00
	5S 0.00	9.80 9.80 193.15 0.40 0.00 5.00	93.40 253.70 0.00 0.00
	6S 0.00	11.40 11.40 284.58 0.20 0.00 6.00 112.40 257.44 0.00 0.00
		(b) Publication
	Query	Fedra	FedX
	Type SPE NTWSS SST ETUE Recall Du SPE NTWSS ET Recall Du
	ST 0.00	2.20 26.43 3.26 1.00 14.80 1.00 126.60 7.99 0.92 85.40
	2P 0.00	2.29 5.85 19.16 1.00 30.57 2.00	3.60 99.84 0.34 36.57
	3P 0.00	7.86 3.81 51.78 0.86 22.00 3.00 321.57 261.55 0.14 14.29
	4P 0.00	4.25 4.84 4.89 1.00 12.50 4.00 285.75 62.55 0.50 50.00
	2S 0.00	3.20 33.44 26.65 0.80 36.00 2.00 470.80 129.66 0.00 0.00
	3S 0.00	4.20 40.12 66.21 0.60 0.20 3.00 634.40 241.37 0.00 0.00
	4S 0.00	5.20 108.48 190.20 0.40 0.00 4.00 1352.60 316.32 0.00 0.00
	5S 0.00	6.40 134.86 137.06 0.60 0.00 5.00 1528.00 300.17 0.00 0.00
	6S 0.00	8.60 138.42 140.79 0.60 0.00 6.00 1811.60 251.82 0.00 0.00

Table 3 :

 3 Number of Triple-Wise Selected Public Endpoints (SPE), Triple-Wise Selected Sources (NTWSS), Execution Time (ET), Recall (R) and Duplicates (Du) using Fedra and FedX for Diseasome federation with divergence and thresholds of 0 and 25%. For Fedra, ET is detailed in Source Selection Time (SST) and query Execution Time by the Underlying Engine (ETUE).

		(a) Threshold = 0%			(b) Threshold = 25%
	Query	Fedra			Fedra
	Type SPE NTWSS SST ETUE R Du	SPE NTWSS SST ETUE R Du
	ST 0.80	1.40 1.33 1.29 1.00 19.00	0.20	1.40 1.42 1.17 0.88 20.00
	2P 2.00	3.25 2.53 153.83 0.50 24.50	0.25	3.00 2.48 154.57 0.49 10.75
	3P 2.80	4.60 5.93 193.42 0.30 30.00	0.40	3.80 5.84 64.29 0.59 41.20
	4P 3.50	6.00 7.56 302.29 0.00 0.00	0.00	6.00 7.20 155.40 0.02 48.50
	2S 1.60	4.00 2.33 73.13 0.79 29.60	0.00	4.80 2.67 12.63 0.72 49.20
	3S 2.60	4.60 3.96 13.03 0.96 48.60	1.00	5.80 3.90 182.01 0.20 0.00
	4S 3.00	6.20 7.86 95.71 0.58 0.00	0.00	7.20 7.81 85.96 0.32 0.00
	5S 4.20	8.00 9.02 190.70 0.30 0.00	0.00	10.00 9.14 191.16 0.20 0.00
	6S 5.20	10.00 10.31 300.13 0.00 0.00	0.00	11.80 10.79 275.54 0.15 0.00
			(c) FedX
		Query	FedX
		Type SPE NTWSS ET	R Du
		ST 1.00	14.00 1.72 0.91 75.80
		2P 2.00	32.75 79.23 0.50 24.75
		3P 3.00	51.00 34.55 0.25 35.20
		4P 4.00	76.00 304.61 0.00 0.00
		2S 2.00	35.60 142.88 0.60 37.20
		3S 3.00	34.20 152.60 0.60 59.00
		4S 4.00	75.60 300.14 0.00 0.00
		5S 5.00	93.40 300.62 0.00 0.00
		6S 6.00 112.40 302.10 0.00 0.00

http://live.dbpedia.org/liveupdates/

https://sites.google.com/site/dawfederation/data-sets, January 2014.

Library https://github.com/Data2Semantics/powerlaws for power law distribution sampling.

[START_REF] Dasgupta | Algorithms[END_REF] http://virtuoso.openlinksw.com/, November

2013.[START_REF] Dourish | The parting of the ways: Divergence, data management and collaborative work[END_REF] The data distribution of all the endpoints that conform the Federations and the views that describe all their replicated fragments are available at the project website: https://sites.google.com/site/fedrasourceselection/

http://jena.apache.org/, November 2013.

http://www.fluidops.com/fedx/, November 2013.

Acknowledgments. We thank Andreas Schwarte, who provided us with a version of FedX that prints the execution plans.