Antoine Amarilli
email: antoine.amarilli@ens.fr

Pierre Senellart
email: pierre.senellart@telecom-paristech.fr

On the Connections between Relational and XML Probabilistic Data Models

Keywords: probabilistic data, relational data, XML

A number of uncertain data models have been proposed, based on the notion of compact representations of probability distributions over possible worlds. In probabilistic relational models, tuples are annotated with probabilities or formulae over Boolean random variables. In probabilistic XML models, XML trees are augmented with nodes that specify probability distributions over their children. Both kinds of models have been extensively studied, with respect to their expressive power, compactness, and query efficiency, among other things. Probabilistic database systems have also been implemented, in both relational and XML settings. However, these studies have mostly been carried out independently and the translations between relational and XML models, as well as the impact for probabilistic relational databases of results about query complexity in probabilistic XML and vice versa, have not been made explicit: we detail such translations in this article, in both directions, study their impact in terms of complexity results, and present interesting open issues about the connections between relational and XML probabilistic data models.

Introduction

A variety of systems have been put forward to represent probabilistic data and cover the needs of the various applications that produce and process uncertain data. In particular, both relational [START_REF] Suciu | Probabilistic Databases[END_REF] and XML [START_REF] Kimelfeld | Probabilistic XML: Models and complexity (September 2011[END_REF] probabilistic data models have been studied in depth, and have been investigated in terms of expressive power, query complexity, underlying algorithms, update capabilities, and so on. Similarly, systems have been developed to query probabilistic relational databases (e.g., MayBMS [START_REF] Huang | MayBMS: a probabilistic database management system[END_REF] and Trio [START_REF] Widom | Trio: A system for integrated management of data, accuracy, and lineage[END_REF]) or probabilistic documents (e.g., ProApproX [START_REF] Souihli | Optimizing approximations of DNF query lineage in probabilistic XML[END_REF] and [START_REF] Hollander | Storing and querying probabilistic XML using a probabilistic relational DBMS[END_REF]). By and large, these two lines of work have been conducted independently, and the results obtained have not been connected to each other.

The purpose of this article is to give a general overview of probabilistic relational and XML data models, describe the various query languages over these models, present how one can encode queries and probabilistic instances of each one of these models into the other, and investigate the consequences of these encodings in terms of complexity results. We focus specifically on the existence and efficiency of translations across models, and on the transposition of query complexity results, rather than on a systems aspect. Section 2 introduces the probabilistic representation systems we consider, and Section 3 the corresponding query languages. We describe encodings of relations into XML in Section 4, and of XML into relations in Section 5.

Data Models

Probabilistic data models are a way to represent a probability distribution over a set of possible worlds that correspond to possible states of the data. We focus on the discrete and finite case where the set of possible worlds is finite; each possible world is associated with a probability value, i.e., a rational in (0, 1], such that the sum of probabilities of all possible worlds is 1. States of the data that are not part of the set of possible worlds have a probability of 0.

A straightforward probabilistic data model is to materialize explicitly the collection of possible worlds with their probability. However, this straightforward representation is not compact; it is as large as the number of possible worlds, and any operation on it (such as answering a query) must iterate over all possible worlds. For this reason, probabilistic data models usually represent the set of possible worlds and the probability distribution in an implicit fashion.

Probabilistic data models usually achieve a trade-off between expressiveness and computational complexity: ability to represent as many different kinds of distributions as possible on the one hand, tractability of various operations on the model, such as querying, on the other hand. In this section, we present probabilistic data models for relational data and for XML data: in both settings, we will move from the less expressive to the more expressive.

Relational models

Probabilistic models for relational data have usually been built on top of models for representing incomplete information. Incomplete information defines a set of possible worlds (the possible completions of the existing information), and probabilistic models usually add some probability scores for each of the possible worlds. See [START_REF] Suciu | Probabilistic Databases[END_REF] for a general survey of probabilistic relational models.

The tuple-independent model. One of the simplest ideas to define a probabilistic relational model is the tuple-independent model [START_REF] Lakshmanan | ProbView: A flexible probabilistic database system[END_REF][START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF] (also known as tables with maybe tuples [START_REF] Green | Models for incomplete and probabilistic information[END_REF] or probabilistic ?-tables [START_REF] Sarma | Working models for uncertain data[END_REF]). In this model, a probabilistic database is an ordinary database where tuples carry a probability of actually occurring in the database, independently from any other tuple. Formally, given a relational schema 𝛴, an instance ̂ 𝐷 of the probabilistic relational schema  𝛴 is defined as a 𝛴-instance in which every tuple 𝑅(a) is annotated with a rational probability value Pr ) , the product of the probabilities in ̂ 𝐷 of retaining the tuples occurring in 𝐷 and dropping the others (note that the second product is infinite but has finite support). Since each tuple is either retained or dropped, there are 2 | ̂ 𝐷| possible worlds of non-zero probability, and we can check that their probabilities sum to 1. This model is simple but not very expressive because of the independence assumption. As an example, if the original schema has a predicate 𝑅(𝐴, 𝐵) with a key constraint 𝐴 → 𝐵, we cannot give non-zero probability to instances {𝑅(𝑎, 𝑏)} and {𝑅(𝑎, 𝑏 ′ )} without giving non-zero probability to instance {𝑅(𝑎, 𝑏), 𝑅(𝑎, 𝑏 ′ )} that violates the key constraint.

The block-independent-disjoint model. An extension of the tuple-independent model to support simple mutually exclusive choices is the block-independent disjoint model [START_REF] Barbará | The management of probabilistic data[END_REF][START_REF] Ré | Materialized views in probabilistic databases: for information exchange and query optimization[END_REF]. In this variant, we assume that every predicate 𝑅 of 𝛴 is of the form 𝑅(K, A), where the attributes have been partitioned into two sets: K, the possible worlds key, and A, the value attribute set. Besides, we require that the key constraint K → A holds. The BID schema ̂ 𝛴 is defined as before with the added constraint that )

with the added constraint that there are no duplicate facts 𝑅(k, a) and 𝑅(k, a ′ ) for any 𝑅(K, A) ∈ ̂ 𝛴, K ∈ K, a, a ′ ∈ A, a ̸ = a ′ (otherwise the probability is 0).

An example BID database, consisting of a single Customer(Id, Name, City) relation (where Id is the key) is given in Fig. 1. Mutually exclusive names and cities are given for the two customers, with the possibility also that neither customer exists in a possible world. Such an uncertain table may be obtained, for instance, following a data integration process from conflicting sources.

Intuitively, instances are drawn from a BID instance by picking one of the mutually exclusive choices of a within each block defined by a choice of k, and doing so independently across the blocks. The BID model is more expressive than the tuple-independent model (which can be seen as the case in which all attributes of every predicate are taken as the possible worlds key K).

Of course, the structure of the BID model is still unable to represent many kinds of probability distributions. For instance, if instance {𝑅(𝑎, 𝑏), 𝑅(𝑎 ′ , 𝑏 ′ )} has non-zero probability in a relation whose possible worlds key is the first attribute, then instances {𝑅(𝑎, 𝑏)} and {𝑅(𝑎 ′ , 𝑏 ′ )} will also have non-zero probability. The pc-tables model. We will now present a much more expressive model: probabilistic 𝑐-tables (a.k.a. pc-tables) [START_REF] Green | Models for incomplete and probabilistic information[END_REF][START_REF] Huang | MayBMS: a probabilistic database management system[END_REF]. To simplify the writing, we will restrict our exposition to Boolean pc-tables, that are known to be as expressive as general pc-tables [START_REF] Green | Models for incomplete and probabilistic information[END_REF]. Given a relational schema 𝛴, an instance ̂ 𝐷 of the probabilistic relational schema ̂ 𝛴 is a 𝛴-instance which annotates every tuple 𝑅(a) with a Boolean formula Con ̂ 𝐷 (𝑅(a)) over a global finite set of variables 𝒱 and provides an additional relation 𝐵 assigning a probability value Pr ̂ 𝐷 (𝑥) ∈ (0, 1] to each variable 𝑥 ∈ 𝒱 occurring in the instance (intuitively, the probability that 𝑥 is true). Given an assignment 𝜈 from the set 𝒱 of Boolean assignments (i.e., functions from 𝒱 to Boolean values {t, f}), we define 𝐷 𝜈 to be the 𝛴-instance obtained from ̂ 𝐷 by removing each fact 𝑅(a) such that Con ̂ 𝐷 (𝑅(a)) evaluates to f under 𝜈. We then define the probability of assignment 𝜈 as: Pr

( 1 -Pr ̂ 𝐷 (𝑥) ) ) . The probability of a 𝛴-instance 𝐷 is then: Pr ̂ 𝐷 (𝐷) = ∑ 𝜈∈𝒱 s.t. 𝐷𝜈 =𝐷 Pr ̂ 𝐷 (𝜈).
Intuitively, 𝛴-instances are obtained by drawing an assignment of the variables independently according to 𝐵 and keeping the facts where the condition is true.

It is not very hard to see that any probability distribution over any finite set of possible worlds can be modeled with a pc-table, given sufficiently many tuples and variables. In particular, BID tables can be expressed as pc-tables, and a direct polynomial-time translation is straightforward.

XML Models

We will now present probabilistic models for XML data. This presentation is inspired by [START_REF] Kimelfeld | Probabilistic XML: Models and complexity (September 2011[END_REF] in which more details can be found. Given an infinite set of labels ℒ, an XML document is a rooted, unordered, directed, and finite tree where each node has a label in ℒ. For simplicity, we will always require that the root of an XML document (probabilistic or not) has a fixed label 𝜎 r ∈ ℒ. We denote by 𝒳 the collection of XML documents over ℒ.

The PrXML {ind} data model. We define a probabilistic document in the PrXML {ind} model as an XML document over ℒ ∪ {ind} (ind for independent), where the outgoing edges of ind nodes carry a rational number in (0, 1] as label. Such documents will define a probability distribution over 𝒳 that we will describe as a sampling process: in a top-down fashion, for every ind node 𝑥, independently choose to keep or discard each of its children according to the probability label on each outgoing edge, and, in the father 𝑦 of 𝑥, replace 𝑥 by the descendants of 𝑥 that were chosen, removing 𝑥 and its unchosen descendants. Perform this process independently for every node ind.

Once all ind nodes have been processed and removed in this way, the outcome is ar XML document over ℒ, and its probability is the conjunction of the independent events of all the results of the draws at ind nodes. The probability of a document is the sum of the probability of all outcomes leading to it. Note that multiple different outcomes may lead to the same document.

The PrXML {mux} data model. In the same fashion, we can define the PrXML {mux} data model (mux for mutually exclusive), in which we also require that the outgoing edges of each mux node 𝑥 carry a rational number in (0, 1] as label such that the labels of all the outgoing edges of 𝑥 sum to at most 1. The sampling process proceeds as described above, except that each mux node choses at most one of its children according to the probability label on each outgoing edge.

Of course, we can define the PrXML {ind,mux} data model as the data model in which both ind and mux nodes are allowed, which was studied under the name ProTDB in [START_REF] Nierman | ProTDB: Probabilistic data in XML[END_REF]. An example PrXML {ind,mux} is given in Fig. 3; as we shall see in Section 4, it is an encoding of the BID database of Fig. 1.

The PrXML {fie} data model. Finally, we define the PrXML {fie} data model (fie for formula of independent events), in which the outgoing edges of fie nodes are labeled with Boolean formulae on some finite set 𝒱 of Boolean variables and in which we are given a rational probability value 𝑃 (𝑥) in (0, 1] for each variable 𝑥 ∈ 𝒱. The sampling process is to draw independently the truth value of each 𝑥 ∈ 𝒱 according to the probability 𝑃 (𝑥), and replace each fie node by its children for which the Boolean formula appearing as an edge label evaluates to t under the assignment that was drawn.

Expressive power and compactness. PrXML {ind} and PrXML {mux} are incomparable in terms of expressive power [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]: some probability distributions can be expressed by one and not by the other. Thus, PrXML {ind,mux} is strictly more expressive than these two, and it is easy to see that one can actually use it to represent any finite probability distribution over 𝒳 (recall that the root label of all possible documents is fixed).

Any PrXML {ind,mux} probabilistic document can be transformed in polynomial time into an PrXML {fie} document (where all Boolean formulae are conjunctions) which yields the same probability distribution: ind nodes can be encoded with fie nodes by creating one Boolean variable for each of their descendants; a similar encoding exists for mux nodes by first encoding 𝑛-ary mux nodes in a subtree of binary mux nodes, and then replacing each binary mux node by one fie node whose children are labeled by 𝑥 and ¬𝑥, where 𝑥 is a fresh Boolean variable with adequate probability.

On the other hand, no polynomial time translation exists in the other direction [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF], even when considering PrXML {fie} probabilistic documents with conjunctions only. In other words, though PrXML {ind,mux} and PrXML {fie} have the same expressive power, the latter can be exponentially more compact than the former.

Querying Probabilistic Data

Up to this point, we have described probabilistic data models that serve as a concise representation of a probability distribution on a set of possible worlds. However, the main interest of such models is to use them to evaluate queries on all possible worlds simultaneously and return the aggregate results as a probability distribution on the possible answers. For clarity of the exposition, we restrict ourselves to Boolean queries, that are either true or false on a given possible world. Extensions to non-Boolean queries are straightforward.

More formally, given some probabilistic data model, given a probabilistic instance ̂ 𝑀 defining a probability distribution over possible worlds X, and given a Boolean query 𝑞 that can be evaluated on each 𝑋 ∈ X to produce either t or f, we define the probability of 𝑞 on ̂ 𝑀 as: q( ̂ 𝑀 ) = ∑ 𝑋∈X s.t. 𝑞(𝑋)=t Pr ̂ 𝑀 (𝑋). Evaluating q on ̂ 𝑀 means computing the probability of 𝑞 on ̂ 𝑀 . This is called the possible-worlds query semantics.

In this section, we present known results about the complexity of query evaluation under this semantics. The query is always assumed to be fixed, i.e., we discuss the data complexity of query evaluation.

We will need some basic notions about complexity classes for computation and counting problems [START_REF] Papadimitriou | Computational Complexity[END_REF]. The class FP is that of computation problems solvable in deterministic polynomial time, while #P problems are those that can be expressed as the number of accepting runs of a polynomial-time nondeterministic Turing machine. A computation problem is in FP #P if it can be solved in deterministic polynomial time with access to a #P oracle. A problem is FP #P -hard if there is a polynomial-time Turing reduction from any FP #P problem to it.

Relational models

Typical query languages on relational data include conjunctive queries (CQs, i.e., select-project-joins), unions of conjunctive queries (disjunctions of conjunctive queries, a.k.a. UCQs), and the relational calculus. A CQ is hierarchical if for any two variables 𝑥 and 𝑦, either the intersection of the set of atoms that contain 𝑥 with that of 𝑦 is empty, or one of them is contained in the other (this notion can be extended to arbitrary relational calculus queries, see [START_REF] Suciu | Probabilistic Databases[END_REF]). A CQ is without self-join if all atoms bear distinct relation names.

For instance, a simple CQ for the database of Fig. 1, testing whether any customer is located in Boston, is 𝑞 Boston = ∃𝑥∃𝑦 Customer(𝑥, 𝑦, Boston). This query, having a single atom, is trivially hierarchical and without self-joins. It is easy to see that qBoston ( D) = 0.55, where ̂ 𝐷 is the database of Fig. 1. Extensive results exist about the complexity of evaluating the probability of a query for these various query languages over the tuple-independent, BID, and pc-tables models. We refer to [START_REF] Suciu | Probabilistic Databases[END_REF] for a detailed overview and summarize here the main results:

-Query evaluation for relational calculus queries over pc-tables is FP #P [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF].

-CQs of only one atom are already FP #P -hard over pc-tables, even when the Boolean formulae in the pc-table are restricted to conjunctions [START_REF] Valiant | The complexity of computing the permanent[END_REF]. -For UCQs over tuple-independent databases, there is a dichotomy between FP #P -hard queries and FP queries [START_REF] Dalvi | Computing query probability with incidence algebras[END_REF]; however, the only known algorithm to determine the complexity of a query is doubly exponential in the query size, and the exact complexity of this problem is unknown. -A similar dichotomy, but with a polynomial-time test, holds for CQs without self-joins over BIDs. [START_REF] Dalvi | Management of probabilistic data: foundations and challenges[END_REF] -A CQ without self-joins is FP #P -hard over tuple-independent databases if and only if it is not hierarchical. [START_REF] Dalvi | Efficient query evaluation on probabilistic databases[END_REF] Being non-hierarchical is a sufficient condition for any relational calculus query to be FP #P -hard.

XML models

Tree-pattern queries with joins. The first query language that we will consider on XML data are tree-pattern queries with joins (TPQJs). A TPQJ 𝑞 is a rooted, unordered, directed and finite tree whose nodes are labeled either with elements of ℒ or with variable symbols taken from some infinite fixed set of variables 𝒱, and whose edges are either child or descendant edges. Given an assignment 𝜈 : 𝒱 → ℒ, we define the application of 𝜈 to 𝑞 (written 𝑞[𝜈]) as the tree where each label 𝑥 ∈ 𝒱 is replaced by 𝜈(𝑥). A match of 𝑞 in an XML document 𝑑 is an assignment 𝜈 and a mapping 𝜇 from the nodes of 𝑞[𝜈] to the nodes of 𝑑 such that: 1. For any child edge 𝑥 → 𝑦 in 𝑞[𝜈], 𝜇(𝑦) is a child of 𝜇(𝑥) in 𝑑.

2. For any descendant edge 𝑥 → 𝑦 in 𝑞[𝜈], 𝜇(𝑦) is a descendant of 𝜇(𝑥) in 𝑑.

For any node 𝑥 of 𝑞[𝜈]

, its label is the same as that of 𝜇(𝑥) in 𝑑. Intuitively, we match the query with some part of the document so that child, descendant, and fixed label constraints are respected, and all the occurrences of a variable are mapped to nodes with the same label. Tree-pattern queries (TPQs) are TPQJs where all variable symbols are distinct.

We show in Fig. 2 an example TPQJ. Here, 𝑥 and 𝑦 are variables, all other labels are from ℒ. We can show that this query, when evaluated on the PrXML {ind,mux} tree of Fig. 3, yields a probability of 0.55.

Monadic second-order logic with joins. A more expressive query language for XML documents is monadic second-order tree logic with value joins (MSOJ). Remember that a monadic second-order formula is a first-order formula extended with existential and universal quantification over node sets. An MSOJ query is a monadic second-order formula over the predicates 𝑥 → 𝑦 (𝑦 is a child of 𝑥), 𝜆(𝑥) (𝑥 has label 𝜆), and 𝑥 ∼ 𝑦 (𝑥 and 𝑦 have same label, a.k.a. value join).

A MSO query is an MSOJ query without any value join predicate.

Query complexity. We refer to [START_REF] Kimelfeld | Probabilistic XML: Models and complexity (September 2011[END_REF] for a survey of query complexity in probabilistic XML and summarize here the main results:

-Query evaluation for TPQJs over PrXML {fie} is FP #P [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML[END_REF].

-For MSO queries over PrXML {ind,mux} , query evaluation is linear-time [START_REF] Cohen | Running tree automata on probabilistic XML[END_REF].

-Any non-trivial TPQ is FP #P -hard over PrXML {fie} , even when the Boolean formulae of the document are restricted to conjunctions [START_REF] Kimelfeld | Query evaluation over probabilistic XML[END_REF].

-If a TPQJ has a single join (i.e., a single variable appears twice in the query), then the following dichotomy holds over PrXML {ind,mux} [START_REF] Kharlamov | Value joins are expensive over (probabilistic) XML[END_REF]: if it is equivalent to a join-free query, it is linear-time; otherwise it is FP #P -hard. Testing for this equivalence is Σ P 2 -complete. It is open whether this still holds for TPQJs with more than one join. Note that this list of results has some similarity with that in the relational setting: a broad FP #P membership result, hardness of models with Boolean formulae, even with just conjunctions, and a dichotomy between FP #P -hard queries and FP queries for some class of queries over "local" models. In the following, we establish connections between relational and XML settings, exploring whether this yields any connections between these complexity results.

From Relations to XML

We explain here how to encode probabilistic relational data models into probabilistic XML.

Encoding instances. Given a relational schema 𝛴 = {(𝑅 𝑖 (𝐴 𝑖 𝑗 ))}, we will define the node labels ⟨⊤⟩, ⟨𝑅 𝑖 ⟩, ⟨𝐴 𝑖 𝑗 ⟩, along with labels representing all possible constants as text values. The root label of XML documents will always be ⟨⊤⟩. XML representations of instances of the schema will obey the following DTD:

⟨⊤⟩ : (⟨𝑅 1 ⟩ * , ..., ⟨𝑅 𝑛 ⟩ * ) ∀𝑖, ⟨𝑅 𝑖 ⟩ : (⟨𝐴 𝑖 1 ⟩, ..., ⟨𝐴 𝑖 𝑛𝑖 ⟩) ∀𝑖, 𝑗, ⟨𝐴 𝑖
𝑗 ⟩ : #PCDATA We now define the encoding ⟨𝐷⟩ of an instance 𝐷 of 𝛴. The encoding ⟨𝑅 𝑖 (𝑎 1 , ..., 𝑎 𝑛𝑖 )⟩ of the fact 𝑅 𝑖 (𝑎 1 , ..., 𝑎 𝑛𝑖 ) is the subtree whose root has label ⟨𝑅 𝑖 ⟩ and children ⟨𝐴 𝑖 𝑗 ⟩, each child ⟨𝐴 𝑖 𝑗 ⟩ having as child one text node with a label ⟨𝑎 𝑗 ⟩ representing the corresponding 𝑎 𝑗 . The encoding ⟨𝐷⟩ of a full instance 𝐷 is the XML document whose root has one child ⟨𝑅 𝑖 (𝑎 1 , ..., 𝑎 𝑛𝑖 )⟩ per fact 𝑅 𝑖 (𝑎 1 , ..., 𝑎 𝑛𝑖 ) ∈ 𝐷.

Encoding probabilistic instances. We will now define the encoding ⟨ ̂ 𝐷⟩ of probabilistic instances ̂ 𝐷 for the various probabilistic relational data models that we described in Section 2.1. The encodings will be given in the probabilistic XML data models of Section 2.2. When we say that we "encode" one probabilistic data model into another, we mean that the following property holds:

∀ ̂ 𝐷, 𝐷, Pr ⟨ ̂ 𝐷⟩ (⟨𝐷⟩) = Pr ̂ 𝐷 (𝐷) (1)
Proposition 1. Any tuple-independent database can be encoded in linear time as a PrXML {ind} probabilistic document.

Proof. Given a tuple-independent probabilistic instance ̂ 𝐷, we encode it as a PrXML {ind} document ⟨ ̂ 𝐷⟩ whose root has an ind node as its only child. We root as children of this node the subtrees encoding each of the tuples of ̂ 𝐷, where the probability of the tuple is indicated on the edge attaching it to the ind node. It is easy to see that Equation (1) holds with this encoding.

⊓ ⊔ Proposition 2. Any BID can be encoded in linear time as a PrXML {ind,mux} probabilistic document.

Proof. Consider a BID probabilistic ̂ 𝛴-instance ̂ 𝐷. We will first define an encoding for the blocks of ̂ 𝐷, before defining the encoding ⟨ ̂ 𝐷⟩ of ̂ 𝐷. For all 𝑅(K, A, 𝑃 ) ∈ ̂ 𝛴, for all k ∈ K such that 𝑅(k, a, 𝑝) ∈ ̂ 𝐷 for some (a, 𝑝) ∈ A × 𝑃 , we first define ⟨𝑅(k, , )⟩ as the subtree whose root has label ⟨𝑅⟩, has |K| children ⟨𝐾 𝑗 ⟩ whose children are text nodes ⟨𝑘 𝑗 ⟩ representing the associated 𝑘 𝑗 , and has as (|K| + 1)-th child a mux node; as children of this mux node, we put one ind node per a ∈ A such that 𝑝 = Pr ̂ 𝐷 (𝑅(k, a)) is > 0, with 𝑝 as edge label. As children of each of these ind nodes, with edge probability 1, we put |A| nodes ⟨𝐴 𝑗 ⟩ with children text nodes ⟨𝑎 𝑗 ⟩.

Hence, for each 𝑅(K, A, 𝑃 ) ∈ ̂ 𝛴, for each choice of k ∈ K, the mux node will select one of the possible choices of a ∈ A based on their probability in ̂ 𝐷, those choices being independent between all of the mux nodes.

As expected, we define ⟨ ̂ 𝐷⟩ to be the PrXML {mux} document whose root has one child ⟨𝑅(k, , )⟩ per possible choice of 𝑅(K, A, 𝑃 ) ∈ ̂ 𝛴 and 𝑅(k, , ) ∈ ̂ 𝐷.

⊓ ⊔

This construction is illustrated in Fig. 3, which is a PrXML {ind,mux} encoding of the BID database in Fig. 1. Proposition 3. Any pc-table can be encoded in linear time as a PrXML {fie} probabilistic document with the Boolean formulae unchanged.

Proof. Consider a probabilistic ̂ 𝛴-instance ̂ 𝐷 in the pc-table formalism. We will set ⟨𝒱⟩ (the variable set for the PrXML {fie} formalism) to be the variable set 𝒱 of ̂ 𝐷, and will simply take ⟨𝑃 ⟩(⟨𝑥⟩) to be Pr ̂ 𝐷 (𝑥). We now define ⟨ ̂ 𝐷⟩ as the PrXML {fie} document whose root has a fie node as its only child. This node has as descendants the subtrees encoding each of the tuples of ̂ 𝐷, where the condition of the tuple is indicated on the edge attaching it to the fie node.

⊓ ⊔ Encoding queries. We will now show how a query 𝑞 on a relational instance 𝐷 is encoded as a query ⟨𝑞⟩ on its XML encoding ⟨𝐷⟩. Of course, we will ensure that queries commute with encodings, i.e., the following property holds:

∀ ̂ 𝐷, 𝑞, 𝑞 ( ̂ 𝐷 ) = ⟨𝑞⟩ (⟨ ̂ 𝐷 ⟩) (2)
Proposition 4. A CQ can be encoded as a TPQJ in linear time.

Proof. The encoding ⟨𝑎⟩ of a constant 𝑎 is its textual representation, and the encoding ⟨𝑥⟩ of a variable 𝑥 of the query is a TPQJ variable. The encoding ⟨𝐹 ⟩ of an atomic formula 𝐹 = 𝑅(𝑧 1 , ..., 𝑧 𝑛 ) over the relation 𝑅(𝐴 1 , ..., 𝐴 𝑛 ) is the subtree whose root has label ⟨𝑅⟩ and has 𝑛 children; each child has label ⟨𝐴 𝑖 ⟩ and has one child ⟨𝑧 𝑖 ⟩. The encoding ⟨𝑞⟩ of a CQ 𝑞 is a tree whose ⟨⊤⟩-labeled root has one child ⟨𝐹 ⟩ per atomic formula 𝐹 in 𝑞.

⊓ ⊔

This encoding is shown in Fig. 2, a TPQJ that encodes 𝑞 Boston . We rediscover with this result the FP #P membership of CQ evaluation over pc-tables given that of TPQJ over PrXML {fie} . We also obtain the FP #P -hardness of TPQJ over PrXML {ind} given that of CQs over tuple-independent databases. We can finally use this result to find individual hard TPQJ queries as those that are encodings of hard CQs over tuple-independent databases (e.g., non-hierarchical CQs). Proposition 5. A query in the relational calculus can be encoded as an MSOJ query in linear time; the resulting query does not have any second-order quantifier, i.e., it is actually a first-order query with joins.

Proof. Let 𝑞 be a relational calculus query. We denote by 𝑉 and 𝐶 respectively the set of variables and constants appearing in 𝑞. For each variable 𝑥 in 𝑉 , and each occurrence of 𝑥 in 𝑞, we introduce a new variable 𝑥 𝑖 . We encode subgoals 𝑅(𝑧 1 , ..., 𝑧 𝑛 ) for the relation 𝑅(𝐴 1 , ..., 𝐴 𝑛 ) by the following formula: ∃𝑦 ⟨𝑅⟩(𝑦) ∧ ⋀ 𝑗 ∃𝑤 (𝑦 → 𝑤 ∧ ⟨𝐴 𝑗 ⟩(𝑤) ∧ 𝑤 → ⟨𝑧 𝑗 ⟩) where the encoding ⟨𝑧 𝑖 ⟩ of a constant 𝑎 is a fresh variable 𝑐 𝑎 and the encoding of a variable 𝑥 is the encoding ⟨𝑥 𝑖 ⟩ of the fresh variable for this specific occurrence of 𝑥. Let ⟨𝑞⟩ ′ be the MSO formula obtained from 𝑞 by encoding all of its subgoals in this way. The MSOJ query ⟨𝑞⟩ is

⟨𝑞⟩ ′ ∧ (⋀ 𝑥∈𝑉 ∃𝑥 ⋀ 𝑖 𝑥 ∼ 𝑥 𝑖 ) ∧ (⋀ 𝑐𝑎 𝑎(𝑐 𝑎 )
) where all 𝑥 𝑖 's and 𝑐 𝑎 's are existentially quantified at the top level.

⊓ ⊔

As an immediate consequence of this encoding, if the original first-order query is read-once (no query variable is used twice), it is linear-time to evaluate it over BIDs thanks to the linear-time evaluation of MSO over PrXML {ind,mux} . Read-once queries are of limited interest, however.

From XML to Relations

We now show, in the reverse direction, how to encode probabilistic XML instances into probabilistic relational models. This problem has been explored in [START_REF] Hollander | Storing and querying probabilistic XML using a probabilistic relational DBMS[END_REF] with two solutions proposed: Schema-based: adapted inlining Assume we have a DTD for possible XML documents. This method transforms a PrXML {ind,mux} probabilistic document (but it is easy to adapt the technique to PrXML {fie} ) into a pc-table whose schema is derived from the DTD, adapting techniques from [START_REF] Shanmugasundaram | Relational databases for querying XML documents: Limitations and opportunities[END_REF] for storing XML documents into relations. Queries are translated as in [START_REF] Shanmugasundaram | Relational databases for querying XML documents: Limitations and opportunities[END_REF], which may result in queries involving a fixpoint operator in the case of recursive DTDs. Schemaless: adapted XPath accelerator In the absence of a schema, Hollander and van Keulen propose to transform PrXML {ind,mux} probabilistic documents (again, the same would hold with PrXML {fie} ) into pc-tables by using a pre/size/level encoding as in MonetDB/XQuery [START_REF] Boncz | MonetDB/XQuery: a fast XQuery processor powered by a relational engine[END_REF]. Queries are then translated into queries with inequality predicates and arithmetic.

These two translations are used to show that probabilistic XML can be queried on top of a probabilistic relational engine, Trio in [START_REF] Hollander | Storing and querying probabilistic XML using a probabilistic relational DBMS[END_REF] or MayBMS in [START_REF] Stapersma | Efficient query evaluation on probabilistic XML data[END_REF]. However, we present here an alternative translation that has the advantage of transforming TPQJs into CQs, without any need for recursion or inequality predicates.

Encoding instances. Let 𝑑 be an XML document. We construct the relational schema 𝛴 = {Label (id , lab), Child (id , cid ), Desc(id , did ), Root(id )} and encode each node 𝑛 by a unique ID ⟨𝑛⟩. The encoding ⟨𝑑⟩ of 𝑑 is a relation over 𝛴 defined as follows:

for every node 𝑛 of 𝑑 with label 𝑙, we add a fact Label (⟨𝑛⟩, ⟨𝑙⟩); for every edge (𝑛, 𝑛 ′ ) in 𝑑, we add a fact Child (⟨𝑛⟩, ⟨𝑛 ′ ⟩); for every node 𝑛 and descendant 𝑛 ′ of 𝑛 in 𝑑, we add a fact Desc(⟨𝑛⟩, ⟨𝑛 ′ ⟩); we add a single fact Root(⟨𝑟⟩) for the root 𝑟 of 𝑑. Note that this construction is quadratic at worst since we may add linearly many Desc facts for every node 𝑛.

Encoding probabilistic instances. We will now encode a probabilistic XML document d from Section 2.2 into a probabilistic relational instance ⟨ d⟩ of Section 2.1. Again, the goal is to have an encoding that satisfies [START_REF] Suciu | Probabilistic Databases[END_REF].

We start with a negative result that shows that tuple-independent databases or even BIDs are unusable for encoding even simple probabilistic documents: Proposition 6. No probabilistic document of PrXML {ind,mux} with more than one possible world can be encoded as a BID (with the instance encoding above).

Proof. Assume by way of contradiction we have such a document d and its encoding ⟨ d⟩. Since d has more than one possible world, it contains at least one ind or mux node, say 𝑥, and there is a child 𝑦 of 𝑥 such that the edge probability label between 𝑥 and 𝑦 is 𝑝 < 1. Let 𝑧 be the lowest ancestor of 𝑥 that is neither an ind or mux node; if 𝑦 is itself an ind or mux node, we take 𝑦 to be its highest descendant that is neither an ind or mux node.

There exists possible worlds 𝑑 and 𝑑 ′ of d such that, in ⟨𝑑⟩, Child (⟨𝑧⟩, ⟨𝑦⟩) and Desc(⟨𝑧⟩, ⟨𝑦⟩) holds, while in ⟨𝑑 ′ ⟩, neither of these facts hold. But then, since the Child and Desc tables are fully independent in a BID, there is a possible world of ⟨ d⟩ where Child (⟨𝑧⟩, ⟨𝑦⟩) holds and Desc(⟨𝑧⟩, ⟨𝑦⟩) does not, which is absurd, since no encoding of a possible world of d verifies this.

⊓ ⊔

This result may seem to be an artifact of the particular encoding of instances we chose. However, there is something deeper happening here: BIDs are not able to correlate probabilities of tuples, which means they will not be able in particular to represent hierarchies of ind nodes [START_REF] Abiteboul | On the expressiveness of probabilistic XML models[END_REF]. More generally, the main issue comes from the fact that BIDs are not a strong representation system [START_REF] Sarma | Working models for uncertain data[END_REF] for the language of (non-Boolean) conjunctive queries: the output of a conjunctive query over BIDs cannot in general be represented as a BID; on the other hand, PrXML {ind,mux} can represent any discrete probability distribution, and can therefore represent the output of any query over PrXML {ind,mux} . This mismatch means it is hopeless to come up with an alternative way of encoding instances that would make BIDs sufficient to encode PrXML {ind,mux} .

On the other hand, pc-tables can encode probabilistic XML documents:

Proposition 7. Any PrXML {ind,mux} or PrXML {fie} probabilistic document can be encoded as a pc-table in cubic time.

Proof. We restrict to PrXML {fie} since PrXML {ind,mux} can be tractably encoded into PrXML {fie} . We first remove every fie node of the probabilistic document by connecting each non-fie descendant 𝑛 ′ of a fie node to its lowest non-fie ancestor 𝑛, labeling the edge (𝑛, 𝑛 ′ ) with the conjunction of all formulae appearing as labels on the edges of the original path from 𝑛 to 𝑛 ′ . We then construct a pc-table from this document as if it were a non-probabilistic document, except that to each tuple Child (⟨𝑛⟩, ⟨𝑛 ′ ⟩) we add the Boolean condition that appears as label on (𝑛, 𝑛 ′ ), and to each tuple Desc(⟨𝑛⟩, ⟨𝑛 ′ ⟩) we add the conjunction of all Boolean conditions that appear as labels on the edges of the path between 𝑛 and 𝑛 ′ . At worst, this results in a cubic construction: for every node, for every descendant of this node, we have a condition that has at most linear size. ⊓ ⊔ Encoding queries. Again, our goal is an encoding of tree queries that satisfies (2).

Proposition 8. A TPQJ can be encoded as a CQ in linear time.

Proof. Let 𝑞 be a TPQJ. The CQ ⟨𝑞⟩ is the conjunction of the following atomic formulae:

for every node 𝑛 of 𝑞 with constant or variable label 𝑙, an atom Label (⟨𝑛⟩, ⟨𝑙⟩); for every child edge (𝑛, 𝑛 ′ ), an atom Child (⟨𝑛⟩, ⟨𝑛 ′ ⟩) for every descendant edge (𝑛, 𝑛 ′ ), an atom Desc(⟨𝑛⟩, ⟨𝑛 ′ ⟩). ⊓ ⊔

This can be used to reestablish the FP #P membership of TPQJ over PrXML {fie} from the similar result over relations, or, for example, the FP #P -hardness of any encoding of a TPQJ with a single join. Note that the encoding of any TPQ with depth greater than 1 will be non-hierarchical but still tractable on the encodings of PrXML {ind,mux} : we cannot just use the fact that non-hierarchical queries are intractable since we are working with a specific class of databases.

MSOJ queries cannot be encoded into the relational calculus, since they can express such things as the existence of a path between nodes of a graph (this graph being represented as a tree, e.g., as in Section 4), which is impossible to test in first-order logic. [START_REF] Libkin | Elements of Finite Model Theory[END_REF]

Conclusion

We have thus established connections between probabilistic relational and XML models, showing how probabilistic instances and queries from one model can be encoded into the other. Though we can rediscover some general results in this way (such as the FP #P -completeness of query evaluation), we also see that results over probabilistic XML (such as the linear-time evaluation of MSO queries, or the dichotomy for TPQJ queries with a single join) are not direct translations of similar results in the relational case but deep consequences of the true structure.

To go further, one direction would be to look at the tree-width (of the data structure, of the queries, of the Boolean formulae) as an indicator of the tractability of a query; Jha and Suciu have shown [START_REF] Jha | On the tractability of query compilation and bounded treewidth[END_REF] that it is tractable to evaluate the probability of a bounded tree-width Boolean function. It is still an open problem to understand the dependency between the tree-width of a query lineage and the tree-width of the query, of the data and of the Boolean formulae. This could suggest new tractable classes of probabilistic relational databases, inspired by the tractable classes of probabilistic XML.

We have restricted our study to discrete finite probabilistic distributions; models for discrete infinite distributions arise naturally in probabilistic XML [START_REF] Benedikt | Probabilistic XML via Markov chains[END_REF] by adding probabilities to an XML schema [START_REF] Abiteboul | Finding optimal probabilistic generators for XML collections[END_REF]; their meaning is less clear in the relational setting. Probabilistic models with continuous distributions can also be defined in the relational [START_REF] Cheng | Evaluating probabilistic queries over imprecise data[END_REF] and XML [START_REF] Abiteboul | Capturing continuous data and answering aggregate queries in probabilistic XML[END_REF] cases, though the precise semantics can be tricky. Moreover, no strong representation systems (say, for conjunctive queries) involving continuous distributions have been put forward yet.

̂

  𝐷 (𝑅(a)) ∈ (0, 1] (with tuples absent from ̂ 𝐷 having probability 0). The probability of a 𝛴-instance 𝐷 according to ̂ 𝐷 is

  , A) and possible worlds key k ∈ K. Intuitively, for each k, there is a probability distribution on the possible exclusive choices of a (including the default option of choosing no a). A ̂ 𝛴-instance ̂ 𝐷 defines the probability distribution Pr

Fig. 1 . 1 BostonFig. 3 .

 113 Fig. 1. Example BID database

Fig. 2 .

 2 Fig. 2. Example of a TPQJ to encode Customer(𝑥, 𝑦, Boston) ⟨⊤⟩ ⟨Customer⟩


Nicolas Macorps

Pierre Labadie
email: pierre.labadie@u-bordeaux.fr

François Lestremau

Azziz Assoumani

Hélène Budzinski

Per-and polyfluoroalkyl substances (PFAS) in surface sediments: Occurrence, patterns, spatial distribution and contribution of unattributed precursors in French aquatic environments

Keywords: PFAS, emerging contaminants, sediment, TOP assay, hierarchical cluster analysis Highlights

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Per-and polyfluoroalkyl substances (PFAS) have been extensively used since the 1950s in numerous industrial applications such as in the fluoropolymer industry, domestic products or aqueous filmforming foams (AFFFs) [START_REF] Buck | Perfluoroalkyl and polyfluoroalkyl substances in the environment: Terminology, classification, and origins[END_REF][START_REF] Glüge | An overview of the uses of per-and polyfluoroalkyl substances (PFAS)[END_REF]. They are of major environmental concern because of their persistence, bioaccumulative properties and toxicity [START_REF] Ahrens | Polyfluoroalkyl compounds in the aquatic environment: a review of their occurrence and fate[END_REF]. The worldwide presence in aquatic environments of perfluoroalkyl acids (PFAAs), in particular perfluoroalkyl carboxylates (PFCAs) and perfluoroalkyl sulfonic acids (PFSAs), has been substantially reported [START_REF] Ahrens | Polyfluoroalkyl compounds in the aquatic environment: a review of their occurrence and fate[END_REF][START_REF] Houde | Monitoring of Perfluorinated Compounds in Aquatic Biota: An Updated Review: PFCs in Aquatic Biota[END_REF][START_REF] Zareitalabad | Perfluorooctanoic acid (PFOA) and perfluorooctanesulfonic acid (PFOS) in surface waters, sediments, soils and wastewater -A review on concentrations and distribution coefficients[END_REF][START_REF] Pan | Worldwide Distribution of Novel Perfluoroether Carboxylic and Sulfonic Acids in Surface Water[END_REF]. Perfluorooctane carboxylate (PFOA), perfluorooctane sulfonate (PFOS) and their salts have been listed under Annex B and A of the Stockholm Convention [START_REF] Wang | A Never-Ending Story of Per-and Polyfluoroalkyl Substances (PFASs)?[END_REF]). The latter is also listed as a priority pollutant under the Water Framework Directive (WFD) since 2013 (European Commission 2013). As a consequence of PFAS regulation, a shift towards alternative PFAS was initiated in recent years, leading to the phase-out of long-chain compounds and to the increased detection of emerging compounds [START_REF] Xiao | Emerging poly-and perfluoroalkyl substances in the aquatic environment: A review of current literature[END_REF], such as zwitterionic PFAS (e.g. 6:2 fluorotelomer sulfonamidoalkyl betaine (6:2 FTAB)).

Over 4700 PFAS are or have been released on the market, with less than 6% being commercially relevant [START_REF] Cousins | Strategies for grouping per-and polyfluoroalkyl substances (PFAS) to protect human and environmental health[END_REF]. However, the lack of analytical standards and instrument limitations has led to the quantitative monitoring of a limited number of PFAS only [START_REF] Ruan | Analytical methodology for identification of novel per-and polyfluoroalkyl substances in the environment[END_REF]. Applications of other analytical methods such as total/extractible organic fluorine measurements [START_REF] Yeung | Perfluoroalkyl substances and extractable organic fluorine in surface sediments and cores from Lake Ontario[END_REF] or the total oxidizable precursor assay (TOP) [START_REF] Houtz | Oxidative Conversion as a Means of Detecting Precursors to Perfluoroalkyl Acids in Urban Runoff[END_REF] proved useful to account for the non-targeted PFAS fractions [START_REF] Cousins | Strategies for grouping per-and polyfluoroalkyl substances (PFAS) to protect human and environmental health[END_REF]. For instance, the TOP assay, which relies on the oxidative conversion of perfluoroalkyl precursors (pre-PFAAs) into PFCAs, highlighted that unattributed pre-PFAAs contributed for 80% of ∑PFAS in urban sediments [START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. Large fractions of unattributed pre-PFAAs were also found in other environments, e.g. urban runoff, groundwater and urban rivers [START_REF] Houtz | Oxidative Conversion as a Means of Detecting Precursors to Perfluoroalkyl Acids in Urban Runoff[END_REF][START_REF] Houtz | Persistence of Perfluoroalkyl Acid Precursors in AFFF-Impacted Groundwater and Soil[END_REF][START_REF] Ye | Spatial distribution and importance of potential perfluoroalkyl acid precursors in urban rivers and sewage treatment plant effluent -Case study of Tama River, Japan[END_REF][START_REF] Boiteux | Concentrations and patterns of perfluoroalkyl and polyfluoroalkyl substances in a river and three drinking water treatment plants near and far from a major production source[END_REF], but studies remained limited to local and regional scales. Only few studies have explored TOP assay application in sediments, soil or suspended particulate matter [START_REF] Göckener | Long-Term Trends of Per-and Polyfluoroalkyl Substances (PFAS) in Suspended Particular Matter from German Rivers Using the Direct Total Oxidizable Precursor (dTOP) Assay[END_REF][START_REF] Guckert | Combining target analysis with sum parameters-a comprehensive approach to determine sediment contamination with PFAS and further fluorinated substances[END_REF][START_REF] Liu | Per-and Polyfluoroalkyl Substances in Contaminated Soil and Groundwater at Airports: A Canadian Case Study[END_REF]. This promising method is not standardized yet [START_REF] Cousins | Strategies for grouping per-and polyfluoroalkyl substances (PFAS) to protect human and environmental health[END_REF] and it still requires development, especially for solid and complex matrices with organic residues [START_REF] Casson | Integrating total oxidizable precursor assay data to evaluate fate and transport of PFASs[END_REF].

Recent findings on emerging PFAS in aquatic environment were reviewed by [START_REF] Xiao | Emerging poly-and perfluoroalkyl substances in the aquatic environment: A review of current literature[END_REF]. The numerous newly reported PFAS include but are not limited to the following compounds: perfluoroether sulfonic acids (PFESAs) and carboxylic acids (PFECAs) such as 6:2 chlorinated polyfluorinated ether sulfonic acid (6:2 Cl-PFESA), mostly used in electroplating industry in China [START_REF] Wang | Fluorinated alternatives to long-chain perfluoroalkyl carboxylic acids (PFCAs), perfluoroalkane sulfonic acids (PFSAs) and their potential precursors[END_REF], hexafluoropropylene oxide-dimer acid (HFPO-DA) and dodecafluoro-3H-4,8-dioxanonanoate (ADONA), i.e. PFOA replacement in fluoropolymer industry [START_REF] Munoz | Analysis of F-53B, Gen-X, ADONA, and emerging fluoroalkylether substances in environmental and biomonitoring samples: A review[END_REF] or PFECHS, found in hydraulic fluids [START_REF] De Silva | Detection of a Cyclic Perfluorinated Acid, Perfluoroethylcyclohexane Sulfonate, in the Great Lakes of North America[END_REF]). In addition, 6:2 FTAB, found in the betaine-based AFFFs used in firefighting activities [START_REF] Dauchy | Per-and polyfluoroalkyl substances in firefighting foam concentrates and water samples collected near sites impacted by the use of these foams[END_REF], has been internationally reported near AFFF-impacted sites (D'Agostino and Mabury 2017; [START_REF] Munoz | Environmental Occurrence of Perfluoroalkyl Acids and Novel Fluorotelomer Surfactants in the Freshwater Fish Catostomus commersonii and Sediments Following Firefighting Foam Deployment at the Lac-Mégantic Railway Accident[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF]. To further characterize the environmental occurrence of these PFAS, there is a need for spatial distribution studies, based on extended lists of targeted compounds with robust and sensitive methods adapted for newly identified PFAS.

In this context, the present work aimed at investigating i) the occurrence and spatial distribution of a large range of targeted PFAS and ii) the contribution of unattributed pre-PFAAs in surface sediments, collected at French nationwide scale. A previous survey, which monitored 22 individual PFAS, highlighted the ubiquity of PFOS and long-chain PFCAs in sediments, with elevated PFAS levels and distinct molecular patterns near industrial and urban areas [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF]. Here, a method was optimized for the targeted analysis of a much wider range of PFAS (n = 36), combined with an adapted TOP assay procedure. Conversion yields of targeted pre-PFAAs into PFCAs were evaluated for the first time under realistic extraction conditions (i.e. in the presence of organic solvent/salt residues) and the procedure was validated on sediments sample extracts. The newly developed methods were subsequently applied to surface sediments samples (n=43). In addition, the spatial distribution of PFAS and unattributed pre-PFAAs was investigated by combining cluster analysis and a geographic information system (GIS)-based approach.

Materials and methods

Standards and reagents

A total of 36 individual PFAS were targeted, including eleven PFCAs (C4-C14), five PFSAs (C4,6,7,8,10), three perfluoroalkyl sulfonamides (FOSA, N-MeFOSA and N-EtFOSA), three perfluoroalkyl sulfonamides acetic acids (FOSAA, N-MeFOSAA and N-EtFOSAA), four fluorotelomer sulfonates (4:2, 6:2, 8:2 and 10:2 FTSA), two polyfluoroalkyl phosphoric acid diesters (6:2 and 8:2 diPAP), two FTABs (6:2 and 8:2 FTAB), two chlorinated PFESAs (6:2 and 8:2 Cl-PFESA), one cyclic PFESA (PFECHS), one polyfluoroalkyl carboxylate (5:3 FTCA) and two PFECAs (ADONA and HFPO-DA). In this paper, L-PFOS refers to the linear PFOS isomer and Br-PFOS to the sum of branched PFOS isomers. Full details on chemicals, standard solutions and consumables are provided in the supplementary information (SI, Table S1).

Sampling

To represent the wide variety of environments encountered in French hydrosystems, diverse sampling sites were selected by the French National Institute for Industrial Environment and Risks (INERIS), i.e. sites exhibiting "good ecological status" according to the European Union WFD (European Commission 2000) and sites under heavier anthropogenic pressure (e.g. close to urban, industrial or agricultural areas). Composite surface sediment samples (0-5 cm depth) were collected during a single sampling campaign (September-November 2018) at 43 sites located in the hydrographic network and in coastal areas (Figure 1). Sampling was undertaken during a low-flow period that i) favored the deposition of fine-grained sediments and ii) minimized sediment remobilization. Samples were stored in a cooling box (4°C), pending shipment to the laboratory within 24 h. River flow rate data were obtained from Banque Hydro (<www.hydro.eaufrance.fr>). Full details on sampling site names, locations and types of anthropogenic pressure as determined by INERIS and by the GIS approach are given in Table S2.

Sample preparation and analysis

Upon arrival at the laboratory, sediment able samples were sieved (< 2mm). Two aliquots (15 mL) were taken for the characterization of total organic carbon (TOC) content and the determination of the fine fraction content (i.e. silt content, < 63 µm). Sediment samples were freeze-dried, finely grounded with a ball mill (< 250 µm) and stored at room temperature in amber glass jars prior to extraction.

The sample extraction procedure was adapted from a previous study carried out by our group [START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. Briefly, sediments (1 g dry weight, dw) were supplemented with internal standards (ISs, 2 ng each) and extracted using microwaved-assisted solvent extraction with 250 mM CH3COONH4 in MeOH (12 mL), followed by filtration on glass wool and graphitized carbon clean-up. Extracts were evaporated to approximately 300 µL under a gentle nitrogen stream at 40 °C and stored at -20°C prior to analysis. Procedural blanks consisted of extraction solvent, while spiked controls (i.e. accuracy assessment) consisted of sediment samples spiked with PFAS (i.e. in-house reference material); in both cases, ISs were added at the beginning of the procedure.

Targeted PFAS analysis was performed using liquid chromatography electrospray ionization coupled with tandem mass spectrometry (LC-ESI-MS/MS) on a 1290 LC system interfaced with a 6495 triple quadrupole mass spectrometer (Agilent Technologies, Massy, France). Due to the inclusion of FTABs in this work, the ESI source was set on fast polarity switching mode. Further details are provided in the SI (Table S3 and Table S4).

Total oxidizable precursor (TOP) assay

The sediment extract oxidation procedure was adapted from Simonnet-Laprade et al. ( 2019) with some modifications. Sediments (0.2 g) were first extracted and cleaned up as described above for targeted analysis. Extracts were then reduced to approximately 100 µL, transferred into 125 mL HDPE bottles and evaporated to dryness at room temperature under a nitrogen stream. Next, 100 mL of ultra-pure water amended with 200 mM K2S2O8 and 500 mM NaOH were added to the bottles, followed by sonication (20 min) to assist PFAS dissolution. Extracts were incubated at 85°C for 6h, then cooled down and neutralized with HCl (3M) (i.e. 1-2 mL). To prevent their oxidation, ISs (4 ng each) were added at this stage. Samples were subsequently extracted on Strata X-AW cartridges and analyzed with LC-ESI-MS/MS. Oxidation procedural blanks consisted of extraction solvent that was submitted to the TOP assay as described for sediment sample extracts.

The conversion rates of targeted precursors into PFCAs upon oxidation (Table S5) were determined on spiked extraction solvent (n = 5), i.e. 12 mL of MeOH + 250 mM CH3COONH4 concentrated to approximately 100 µL. TOP assay data were used i) to calculate the increase of ∑PFCAs (termed ∆PFCAs hereafter and expressed on a molar basis) and ii) to estimate the total extractable amount of ∑pre-PFAAs (herein termed ∑pre-PFAAstotal). Conversion rates were used to determine the fraction of ∆PFCAs resulting from the oxidation of targeted pre-PFAAs that, in turn, allowed for the estimation of PFCA amounts resulting from the oxidation of unattributed pre-PFAAs (∑pre-PFAAsunattributed).

Oxidation performances in the presence of matrix residues were assessed through the triplicate analysis of two sediments with contrasted TOC content. Details on conversion rate determination, oxidation performances on sediments and calculations are provided in the "TOP assay" section of the SI.

Quality control

For analytes quantified in procedural blanks (Table S6), data were blank-corrected and limits of detection (LODs) were either based on blanks or on signal-to-noise as described elsewhere [START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. LODs were in the range 0.006-0.78 ng g -1 dw (Table 1) and limits of quantification (LOQs) were determined as 10/3*LODs.

As regards targeted analyses, whole method recoveries for spiked sediments were in the range 80-120% except for 6:2 FTAB and 8:2 FTAB (67% and 62%, respectively) and relative standard deviations (RSD) remained generally below 20% except for FTSAs (21-26%) (Table S7). Accuracy was determined with sediments spiked with ISs and analytes at the beginning of the procedure (1 ng g -1 each); values were in the range 80-120% except for 6:2 FTAB, 8:2 FTAB, 8:2 diPAP and PFBS (60%, 58%, 122% and 122%, respectively). TOP assay validation details are given in the "TOP assay" section of the SI.

Statistics

The R statistical software (R version 4.0.5, R core team 2021) was used to perform statistical analyses.

To account for non-detects (i.e. < LOD), descriptive statistics, correlations and differences between groups were calculated using functions from the NADA-R package [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF]. Descriptive statistics for compounds with > 80% non-detected values were not computed and were reported as "NC" (not calculated) [START_REF] Helsel | Brominated flame retardants and perfluoroalkyl substances in sediments from the Czech aquatic ecosystem[END_REF]. Hierarchical cluster analysis based on Ward's minimum variance classification and Euclidian distance between variables (break-in set at 4 clusters) was computed with the FactoMiner package (function hclust) for R. Details on the GIS method are provided in the SI (section "GIS approach").

Results and discussion

Optimization of extraction and TOP methods

Due to the inclusion of FTABs in the list of targeted PFAS, the method from [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF] had to be adapted (i.e. extraction solvent). Preliminary results revealed that when using MeOH + 0.2% NH4OH as extraction solvent, low recovery yields were achieved for zwitterionic analytes (c.a. 30 %) (Figure S4). However, the addition of ammonium acetate (250 mM) to MeOH dramatically improved FTAB recoveries (> 60%); this solvent also proved suitable for the extraction of the other classes of PFAS targeted in this work (i.e. recoveries in the range 80-110%). Such improvement in the extraction of FTABs and several other unfrequently reported PFAS classes has previously been documented on soils [START_REF] Munoz | Optimization of extraction methods for comprehensive profiling of perfluoroalkyl and polyfluoroalkyl substances in firefighting foam impacted soils[END_REF]) but it is reported here for the first time for sediments. S5). Conversion yields of targeted pre-PFAAs were, however, different between the two conditions. In ultra-pure water, N-MeFOSAA was nearquantitatively converted to PFOA with C5-C7 PFCAs as minor oxidation products, in good agreement with the literature [START_REF] Martin | Zwitterionic, cationic, and anionic perfluoroalkyl and polyfluoroalkyl substances integrated into total oxidizable precursor assay of contaminated groundwater[END_REF][START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. Conversely, when tests were performed on spiked solvent, a mixture of C4-C8 PFCAs was generated (Table S5), with good reproducibility. All tested pre-PFAAs displayed similar trends. The increase in reagent concentrations may alter oxidation profiles towards shorter PFCAs [START_REF] Göckener | Transfer of Per-and Polyfluoroalkyl Substances (PFAS) from Feed into the Eggs of Laying Hens. Part 1: Analytical Results Including a Modified Total Oxidizable Precursor Assay[END_REF][START_REF] Liu | Near-Quantitative Defluorination of Perfluorinated and Fluorotelomer Carboxylates and Sulfonates with Integrated Oxidation and Reduction[END_REF], which requires specific analytical methods [START_REF] Janda | Closing the gap -inclusion of ultrashort-chain perfluoroalkyl carboxylic acids in the total oxidizable precursor (TOP) assay protocol[END_REF][START_REF] Martin | Zwitterionic, cationic, and anionic perfluoroalkyl and polyfluoroalkyl substances integrated into total oxidizable precursor assay of contaminated groundwater[END_REF]. Hence, incomplete mass balance was achieved and, consequently, ∆PFCAs and ∑pre-PFAAsunattributed reported thereafter should be viewed as low estimates. However, it should be emphasized that we conducted conversion experiments under conditions similar to those used for samples (i.e. in the presence of solvent and salt residues). This point has, to the authors' knowledge, never been investigated for the application of the TOP assay to sediments and previous results published in the literature may therefore have been biased. It is noteworthy that the complete conversion of pre-PFAAstargeted was observed when the TOP assay was applied on sediments samples with contrasted TOC contents (Figure S3), which illustrates the robustness of the procedure. Overall, the optimized extraction step improved the recovery of target pre-PFAAs belonging to different PFAS groups with very different chemistries. It is therefore reasonable to assume that this procedure also enhanced the recovery of unattributed precursors, thereby increasing the relevance of the TOP assay performed under such conditions.

Targeted analysis

Detection frequency and levels

Overall, PFAS were detected in 86 % of sediment samples (Table 1). L-PFOS, PFDoDA and PFOA were the most detected compounds (detection frequency: 75%, 71% and 71%, respectively) with median concentrations of 0.44, 0.13 and 0.07 ng g -1 dw, respectively. Emerging PFAS such as HFPO-DA, ADONA, 6:2 Cl-PFESA and 8:2 Cl-PFESA were not detected in the samples analyzed in this work, suggesting the current lower use and emission of these compounds on the French territory compared to other parts of the world [START_REF] Pan | Worldwide Distribution of Novel Perfluoroether Carboxylic and Sulfonic Acids in Surface Water[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF]. The infrequently reported 6:2 FTAB, 10:2 FTSA and 5:3 FTCA were detected in > 35% of samples, while 8:2 FTAB was less often detected (detection frequency: 24.4 %); for all these compounds, the median concentration was lower than the LOD.

The median concentration of ∑PFAS was 1.3 ng g -1 dw, which is larger than in a previous French nationwide survey performed in 2012 (0.48 ng g -1 dw) [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF]. However, it should be kept in mind that i) a larger list of PFAS was targeted in this study, including 6:2 FTAB and 8:2 FTAB that were found in the ng g -1 range, and ii) sampling sites were different. High levels of FTABs have been reported near point sources [START_REF] Boiteux | Analysis of 29 per-and polyfluorinated compounds in water, sediment, soil and sludge by liquid chromatography-tandem mass spectrometry[END_REF][START_REF] Munoz | Environmental Occurrence of Perfluoroalkyl Acids and Novel Fluorotelomer Surfactants in the Freshwater Fish Catostomus commersonii and Sediments Following Firefighting Foam Deployment at the Lac-Mégantic Railway Accident[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF][START_REF] Meng | Legacy and emerging per-and polyfluoroalkyl substances (PFASs) in Dagang Oilfield: Multimedia distribution and contributions of unknown precursors[END_REF]. Such compounds were previously semi-quantified through suspect screening analysis on a limited number of samples (n = 12 / 129) from the 2012 survey [START_REF] Munoz | Analysis of zwitterionic, cationic, and anionic poly-and perfluoroalkyl surfactants in sediments by liquid chromatography polarity-switching electrospray ionization coupled to high resolution mass spectrometry[END_REF] ; their presence in French aquatic environment at similar levels than L-PFOS was therefore confirmed in this study at large spatial scale, advocating for their inclusion in targeted analysis lists.

Molecular patterns and spatial distribution

L-PFOS was the prevalent compound, i.e. accounting for 38% of ∑PFAStargeted on average, in agreement with previous studies [START_REF] Helsel | Brominated flame retardants and perfluoroalkyl substances in sediments from the Czech aquatic ecosystem[END_REF][START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF][START_REF] Pignotti | Seasonal variations in the occurrence of perfluoroalkyl substances in water, sediment and fish samples from Ebro Delta (Catalonia, Spain)[END_REF]. It was followed by 6:2 FTAB and PFDoDA (11% and 10% respectively) (Table S8). Overall, ∑pre-PFAAstargeted was variable and represented on average 29 ± 26 % of ∑PFAStargeted; 6:2 FTAB and 8:2 FTAB accounted for a large fraction of ∑pre-PFAAstargeted (21 ± 29% and 13 ± 23%, respectively) (Figure S5), which is consistent with other studies [START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF][START_REF] Meng | Legacy and emerging per-and polyfluoroalkyl substances (PFASs) in Dagang Oilfield: Multimedia distribution and contributions of unknown precursors[END_REF]). When detected, 5:3 FTCA represented 2-14% of ∑PFAS, suggesting that significant biotransformation of fluorotelomer-based products such as fluorotelomer alcohol or FTSAs may have occurred at some sites [START_REF] Butt | Biotransformation pathways of fluorotelomer-based polyfluoroalkyl substances: A review[END_REF]).

The most contaminated site was located on the Canal de la Deûle (St0112), a few km downstream from the Lille conurbation (> 1 M inhabitants). At this site, ∑PFAS reached 23 ng g -1 dw, of which 45% was due to ∑pre-PFAAstargeted. Out of the fourteen targeted pre-PFAAs, eleven were detected at this site with elevated levels of N-MeFOSAA (2.5 ng g -1 dw) and ∑FTABs (4.9 ng g -1 dw). FOSA, EtFOSAA and 6:2 FTSA, also detected at this site, are known products of the transformation of fluorotelomer-based PFAS (such as 6:2 FTAB) and perfluoroalkane sulfonamido derivatives (FASAs) [START_REF] Liu | Microbial degradation of polyfluoroalkyl chemicals in the environment: A review[END_REF][START_REF] D'agostino | Aerobic biodegradation of 2 fluorotelomer sulfonamide-based aqueous film-forming foam components produces perfluoroalkyl carboxylates: Biodegradation of 2 fluorotelomer sulfonamide surfactants[END_REF]. The Deûle River is characterized by a low water flow rate (mean < 10 m 3 s -1 over the 2005-2010 period) and the sampling site was located i) downstream of a large wastewater treatment plant (WWTP) with a nominal capacity of 620 000 population equivalent and ii) 15 km downstream from the Lille-Lesquin International Airport. Higher number of emerging PFAS and higher PFAS concentration were generally observed near urban center and large WWTP [START_REF] Munoz | Analysis of zwitterionic, cationic, and anionic poly-and perfluoroalkyl surfactants in sediments by liquid chromatography polarity-switching electrospray ionization coupled to high resolution mass spectrometry[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF][START_REF] Ali | Legacy and emerging per-and polyfluorinated alkyl substances (PFASs) in sediment and edible fish from the Eastern Red Sea[END_REF]. Thus, the small dilution capacity of the river combined with large PFAS inputs near the sampling site may likely explain the large fraction of ∑pre-PFAAstargeted as well as the relatively high L-PFOS concentration (5.1 ng g -1 dw).

In order to highlight similarities in PFAS patterns between sites, a hierarchical ascendant classification (HAC) was performed for sampling sites where at least one PFAS was detected. For the sake of HAC interpretation in relation with site typology, we have arbitrarily set the break-in at 4 clusters. This resulted in clusters comprising 12, 1, 15 and 11 sites (Figure 2). No regional effect could be observed in the HAC since sites from different basins were distributed in the different clusters (i.e. the major driver of clustering was land use/human activities rather than geographical location). Cluster #01 grouped sites with low contamination levels (i.e. ∑PFAS < ng g -1 dw) where almost 100% of ∑PFAS (i.e. > 97 %) could be attributed to ∑PFCAs + ∑PFSAs. These sites were generally distant or upstream from major urban centers and they may be mainly contaminated by diffuse inputs such as atmospheric deposition [START_REF] Ahrens | Polyfluoroalkyl compounds in the aquatic environment: a review of their occurrence and fate[END_REF]. Cluster #02 was represented by a single site (St0516) that exhibited high levels of both ∑FTABs (8.4 ng g -1 dw), accounting for 62% of ∑PFAS, and 6:2 diPAP (1.5 ng g -1 dw, 11% of ∑PFAS). This site was located on a small river with a low water flow rate (mean < 1 m 3 s -1 over the 2009 -2020 period) and < 10km from the Toulouse-Blagnac airport where fire-fighting activities involving betaine-based AFFFs may occur on a regular basis [START_REF] Place | Identification of Novel Fluorochemicals in Aqueous Film-Forming Foams Used by the US Military[END_REF]. Clusters #03 and #04 differed from #01 mainly because of their relative contributions of individual pre-PFAAs to ∑pre-PFAAstargeted. Sites associated with Cluster#03 showed ∑PFAS ranging from 1.0 up to 23 ng g -1 dw with a contribution of ∑pre-PFAAstargeted to ∑PFAS mostly dominated by 6:2 FTAB and 8:2 FTAB. Most of the sites from Cluster#03 were located close to large urban centers and influenced by nearby airport activities. Finally, sampling sites belonging to cluster #04 showed a different pre-PFAAs pattern, i.e. ∑pre-PFAAstargeted was dominated by FTSAs and PFOS precursors (e.g. N-MeFOSAA and N-EtFOSAA) ; they were mainly impacted by industrial activities and close to medium size cities (<150 000 habitants).

Although FTSAs and PFOS precursors were proposed as degradation intermediates from fluorotelomers-based products such as FTABs (D'Agostino and Mabury 2017), peculiar molecular patterns characterized by a large relative contribution of 6:2 FTSA are consistent with sampling sites under industrial pressure [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF]. Finally, coastal sediments (n = 4)

showed ∑PFAS in the range <LOD -1.0 ng g -1 dw, with no distinct molecular pattern.

Given the size of the dataset and the variety in anthropogenic pressure on the different sites, the hierarchical ascendant classification and GIS approach proved useful to highlight specific molecular patterns and identify probable PFAS sources.

Correlations

C8-C14 PFCAs were correlated with each other (Table S9) as well as with L-PFOS, Br-PFOS, FOSA, 10:2 FTSA, FTABs and 5:3 FTCA, which strongly suggests similar sources or fate. N-MeFOSAA was not correlated with FTABs nor 5:3 FTCA, which could be linked to the fact that N-MeFOSAA was not identified as a degradation product of FTABs [START_REF] Shaw | Degradation and defluorination of 6:2 fluorotelomer sulfonamidoalkyl betaine and 6:2 fluorotelomer sulfonate by Gordonia sp. strain NB4-1Y under sulfur-limiting conditions[END_REF], but rather as a PFOS precursor [START_REF] Buck | Perfluoroalkyl and polyfluoroalkyl substances in the environment: Terminology, classification, and origins[END_REF]). Since 5:3 FTCA was found to be a degradation product of FTABs and FTSAs [START_REF] Zhang | Biotransformation potential of 6:2 fluorotelomer sulfonate (6:2 FTSA) in aerobic and anaerobic sediment[END_REF][START_REF] Shaw | Degradation and defluorination of 6:2 fluorotelomer sulfonamidoalkyl betaine and 6:2 fluorotelomer sulfonate by Gordonia sp. strain NB4-1Y under sulfur-limiting conditions[END_REF], the correlation between 5:3 FTCA levels and ∑FTSAs + ∑FTABs levels was tested. This correlation was highly significant (slope = 26.4, Kendall's τ = 0.48, p < 0.001); this also suggests that, along with FTSAs and FTABs, other PFAS not targeted in this work may also contribute to the 5:3 FTCA burden in sediments.

Sediment characteristics such as TOC or silt content were found to be relevant controlling factor of PFAS sediment-water partition coefficients, with TOC content being more influential [START_REF] Munoz | Spatial distribution and partitioning behavior of selected poly-and perfluoroalkyl substances in freshwater ecosystems: A French nationwide survey[END_REF]. Here, the correlation between PFAS levels in sediments and TOC were tested for both legacy PFAAs (considered as benchmark compounds) and for the emerging PFAS most frequently detected (i.e. in > 20 % of samples): 10:2 FTSA, 6:2 FTAB, 8:2 FTAB, and 5:3 FTCA. Significant correlations were found for both legacy and emerging PFAS, except N-MeFOSAA (Table S10). However, Kendall's τ remained relatively low, which might for instance suggest that the interaction with organic carbon is not the only mechanism playing a role in PFAS sorption [START_REF] Barzen-Hanson | Sorption of Fluorotelomer Sulfonates, Fluorotelomer Sulfonamido Betaines, and a Fluorotelomer Sulfonamido Amine in National Foam Aqueous Film-Forming Foam to Soil[END_REF][START_REF] Xiao | Sorption and Desorption Mechanisms of Cationic and Zwitterionic Per-and Polyfluoroalkyl Substances in Natural Soils: Thermodynamics and Hysteresis[END_REF].

Table 1. PFAS detection frequency, concentration range and median observed in sediments (n = 43).

Median values were computed with the Regression on Order Statistics (robust ROS) approach. NC: not calculated (> 80% non-detects).

PFAAs precursors as estimated by oxidation

Contribution of unattributed precursors

Data from the TOP assay revealed the presence of unattributed pre-PFAAs in most samples. Upon oxidation, significant ∆PFCAs values were measured (Table S11) in 37 out of 43 samples (i.e. 86 %). Five samples that displayed ∑PFAS < LOD using targeted analysis showed no significant ∆PFCAs after oxidative treatment. These samples were collected from site with good ecological status (according to the WFD assessment approach) or characterized by a dominance of agricultural activities; they were subjected to little or no urban/industrial pressure, hence probably receiving much lower PFAS inputs.

For samples exhibiting significant ∆PFCAs values, significant increases in C4-C14 PFCA molar concentrations were observed (Table S11). The TOP assay method used in this work led to the formation of a series of PFCAs of different chain lengths and favored the production of short-chain PFCAs in comparison to other methods [START_REF] Houtz | Oxidative Conversion as a Means of Detecting Precursors to Perfluoroalkyl Acids in Urban Runoff[END_REF][START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]; thus, the chain length profiles of unattributed pre-PFAAs could not be directly inferred from the PFCA pattern observed upon oxidation. However, our results provided evidence that unattributed precursors bearing perfluoroalkyl chains with up to 14 (and possibly more) fluorinated carbon atoms were buried in the analyzed sediments. This is consistent with the stronger sorption affinity of longchain PFAS for this matrix [START_REF] Labadie | Partitioning behaviour of perfluorinated alkyl contaminants between water, sediment and fish in the Orge River (nearby Paris, France)[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF]. Similar observations were previously made in a single urban river near Paris (France), i.e. significant formation of C4-C12 PFCAs upon oxidation of sediment extracts [START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. The present study confirms such results and our findings suggest the widespread occurrence of long-chain PFAAs in sediments.

After oxidation, the molar fraction of ∑pre-PFAAsunattributed could be estimated based on the molar concentrations of ∑PFCAs, ∑PFSAs and ∑pre-PFAAstargeted determined through targeted analysis [START_REF] Houtz | Poly-and perfluoroalkyl substances in wastewater: Significance of unknown precursors, manufacturing shifts, and likely AFFF impacts[END_REF][START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF]. The molar fraction of ∑pre-PFAAsunattributed was highly variable across samples and accounted on average for 51 ± 30 % of ∑PFAS (Figure S6). A handful of studies have previously reported on the quantification of unattributed precursors with the TOP assay in sediments, albeit at limited spatial scale [START_REF] Simonnet-Laprade | Biomagnification of perfluoroalkyl acids (PFAAs) in the food web of an urban river: assessment of the trophic transfer of targeted and unknown precursors and implications[END_REF][START_REF] Meng | Legacy and emerging per-and polyfluoroalkyl substances (PFASs) in Dagang Oilfield: Multimedia distribution and contributions of unknown precursors[END_REF]. Here, we provided data that revealed the occurrence of a large but also variable fraction of unattributed pre-PFAAs in sediments at a nationwide scale. These values represented a low estimate of the extractable pre-PFAAs pool, as C2-C3 PFCAs may account for a large fraction of ∆PFCAs, depending on unattributed precursor structure and oxidation pattern [START_REF] Meng | Legacy and emerging per-and polyfluoroalkyl substances (PFASs) in Dagang Oilfield: Multimedia distribution and contributions of unknown precursors[END_REF]. The oxidation of FTABs explained on average 4.3 ± 8.2 % of ∆PFCAs (up to 35 %), illustrating once again the necessity to broaden the scope of targeted PFAS using suitable sample preparation and quantification procedures.

Spatial distribution of pre-PFAAs

∑pre-PFAAsunattributed were positively correlated with ∑PFAStargeted (Figure 3) (slope = 1.02, Kendall's τ = 0.49, p < 0.001), even when excluding site St0112 from cluster#03 that presented the highest values (i.e. slope = 0.84, τ = 0.46, p < 0.001). Therefore, sampling sites with high levels of PFAS appeared more susceptible to present higher levels of unattributed precursors. These results are consistent with studies that investigated the spatial distribution of targeted and unattributed PFAS in water and sediments using high-resolution mass spectrometry, TOP assay or fluorine mass balance [START_REF] Ye | Spatial distribution and importance of potential perfluoroalkyl acid precursors in urban rivers and sewage treatment plant effluent -Case study of Tama River, Japan[END_REF][START_REF] D'agostino | Aerobic biodegradation of 2 fluorotelomer sulfonamide-based aqueous film-forming foam components produces perfluoroalkyl carboxylates: Biodegradation of 2 fluorotelomer sulfonamide surfactants[END_REF][START_REF] Chen | Occurrence and Distribution of Per-and Polyfluoroalkyl Substances in Tianjin, China: The Contribution of Emerging and Unknown Analogues[END_REF].

Clusters determined from the HAC (Figure 2) were reported on Figure 3. Significant differences of ∑pre-PFAAsunattributed between clusters were found (p < 0.01). Sites from Cluster#01 presented low levels of unattributed precursors, contributing for 33 ± 35 % (mean ± standard deviation) to ∑PFAS (Table S12), supporting the prevalence of diffuse PFAS inputs at these sites. The contribution of ∑pre-PFAAsunattributed to ∑PFAS was the highest on average (64 ± 22 % of ∑PFAS) for Cluster#04; for this group of sites, levels of unattributed pre-PFAAs were usually elevated and higher than those of targeted PFAS, which is probably associated with industrial point sources [START_REF] Glüge | An overview of the uses of per-and polyfluoroalkyl substances (PFAS)[END_REF]. Cluster#02 (St0516) and Cluster#03 generally displayed ∑PFAS similar to or higher than ∑pre-PFAAsunattributed; the latter contributed for 48 ± 22% on average to ∑PFAS for these clusters. These sites presented the largest fraction of ∑pre-PFAAstargeted (22 ± 20 % on average) (Table S13), most of which could be attributed to FTABs (up to 29%). Hence, these results further suggest that the ∑FTABs / ∑PFAS ratio could be a good indicator to identify sites under the influence of point source emissions linked to airport activities [START_REF] Xiao | Emerging poly-and perfluoroalkyl substances in the aquatic environment: A review of current literature[END_REF].

In any case, we showed at large spatial scale that, when elevated ∑PFAS levels were quantified (i.e. > 1 ng g -1 ), large fractions of unattributed pre-PFAAs could be expected, especially near urban and industrial areas.

Conclusion

This study examined the occurrence and spatial distribution of targeted and unattributed PFAS in sediments at large spatial scale (i.e. French hydrographic network), through a combination of targeted analysis and TOP assay. Thanks to the improvement of the extraction procedure, the scope of these procedures was broadened to include zwitterionic PFAS, along with anionic and neutral ones. The developed TOP assay procedure provided an original approach for the estimation of extractable ∑pre-PFAAsunattributed in sediments. While L-PFOS remained the major PFAS, several emerging compounds such as 6:2 FTAB, 8:2 FTAB or transformation intermediates (e.g. 5:3 FTCA) were also widely detected.

These compounds significantly contributed to ∑PFAS, thereby confirming the need to extend the range of routinely targeted PFAS. Clustering analysis provided evidence for distinct molecular patterns that were further linked to urban or industrial activities. The TOP assay revealed the occurrence of substantial proportion of unattributed pre-PFAAs in sediments identified as impacted by PFAS point sources, which may be considered as a secondary source of PFAAs in hydrosystems. Thus, these results advocate for the need to use complementary approaches when analyzing PFAS in the aquatic environment; they also highlight the necessity to identify the structure of unattributed precursors (e.g. by suspect screening or non-target screening based on high-resolution mass spectrometry).

Figure 1 .

 1 Figure 1. Map showing the 43 sampling sites.

  The TOP assay procedure was adapted based on the new extraction method. Assessment of molar conversion yields of targeted pre-PFAAs was conducted in ultra-pure water and in spiked extraction solvent. Using concentrations of 150 mM NaOH and 60 mM potassium persulfate (Houtz and Sedlak 2012; Simonnet-Laprade et al. 2019), incomplete conversions were observed in spiked solvent samples (data not shown). Reagent concentrations were increased to 500 mM NaOH and 200 mM potassium persulfate and complete conversion of the tested pre-PFAAs was achieved, except for 8:2 FTSA and 10:2 FTSA (remaining fractions < 10%) (Table

Figure 3 .

 3 Figure 3. Correlation between ∑pre-PFAAsunattributed and ∑PFAStargeted in sediments. Sites are color-coded

Acknowledgments

Sediment samples were provided by the 2018 national prospective campaign on emerging contaminants supervised by OFB (French Office of Biodiversity). This study has been carried out with financial support from the French National Research Agency (ANR) in the frame of the Investments for the Future Programme, within the Cluster of Excellence COTE (ANR-10-LABX-45). CPER A2E (Aquitaine region), E3A (Aquitaine region) and FEDER ("Europe is moving in Aquitaine with the European Regional Development Fund (FEDER)") are also acknowledged for funding. PFAS analyses were performed using

the technical facilities from the PLATINE mass spectrometry platform at UMR 5805 EPOC. We are grateful to A. Coynel (UMR 5805 EPOC) who supplied sediment characteristics data.


Which digital uses for which ecologisation of agriculture? The example of cereal farms

•

  Figure 1 : résultats des classifications sur R