Pierre Genevès

Nabil Layaïda

Vincent Quint

Ensuring Query Compatibility with Evolving XML Schemas

Keywords: XML, Schema, Queries, XPath, Evolution, Compatibility, Analysis XML, Schema, Requêtes, XPath, Evolution, Compatibilité, Analyse

During the life cycle of an XML application, both schemas and queries may change from one version to another. Schema evolutions may affect query results and potentially the validity of produced data. Nowadays, a challenge is to assess and accommodate the impact of theses changes in rapidly evolving XML applications.

This article proposes a logical framework and tool for verifying forward/backward compatibility issues involving schemas and queries. First, it allows analyzing relations between schemas. Second, it allows XML designers to identify queries that must be reformulated in order to produce the expected results across successive schema versions. Third, it allows examining more precisely the impact of schema changes over queries, therefore facilitating their reformulation.

Introduction

XML is now commonplace on the web and in many information systems where it is used for representing all kinds of information resources, ranging from simple text documents such as RSS or Atom feeds to highly structured databases. In these dynamic environments, not only data are changing steadily but their schemas also get modified to cope with the evolution of the real world entities they describe.

Schema changes raise the issue of data consistency. Existing documents and data that were valid with a certain version of a schema may become invalid on a new version of the schema (forward incompatibility). Conversely, new documents created with the latest version of a schema may be invalid on some previous versions (backward incompatibility).

In addition, schemas may be written in different languages, such as DTD, XML Schema, or Relax-NG, to name only the most popular ones. And it is common practice to describe the same structure, or new versions of a structure, in different schema languages. Document formats developed by W3C provide a variety of examples: XHTML 1.0 has both DTDs and XML Schemas, while XHTML 2.0 has a Relax-NG definition; the schema for SVG Tiny 1.1 is a DTD, while version 1.2 is written in Relax-NG; MathML 1.01 has a DTD, MathML 2.0 has both a DTD and an XML Schema, and MathML 3.0 is developed with a Relax-NG schema and is expected to have also a DTD and an XML Schema. An issue then is to make sure that schemas written in different languages are equivalent, i.e. they describe the same structure, possibly with some differences due to the expressivity of the language [START_REF] Murata | Taxonomy of XML schema languages using formal language theory[END_REF]. Another issue is to clearly identify the differences between two versions of the same schema expressed in different languages. Moreover, the issues of forward and backward compatibility of instances obviously remain when schema languages change from a version to another.

Validation, and then compatibility, is not the only purpose of a schema. Validation is usually the first step for safe processing of documents and data. It makes sure that documents and data are structured as expected and can then be processed safely. The next step is to actually access and select the various parts to be handled in each phase of an application. For this, query languages play a key role. As an example, when transforming a document with XSL, XPath queries are paramount to locate in the original document the data to be produced in the transformed document.

Queries are affected by schema evolutions. The structures they return may change depending on the version of the schema used by a document. When changing schema, a query may return nothing, or something different from what was expected, and obviously further processing based on this query is at risk. These observations highlight the need for evaluating precisely and safely the impact of schema evolutions on existing and future instances of documents and data. They also show that it is important for software engineers to precisely know what parts of a processing chain have to be updated when schemas change. In this paper we focus on the XPath query language which is used in many situations while processing XML documents and data. The XSL transformation language was already mentioned, but XPath is also present in XLink and XQuery for instance.

Related Work

Schema evolution is an important topic and has been extensively explored in the context of relational, object-oriented, and XML databases. Most of the previous work for XML query reformulation is approached through reductions to relational problems [START_REF] Beyer | DB2/XML: designing for evolution[END_REF]. This is because schema evolution was considered as a storage problem where the priority consists in ensuring data consistency across multiple relational schema versions. In such settings, two distinct schemas and an explicit description of the mapping between them are assumed as input. The problem then consists in reformulating a query expressed in terms of one schema into a semantically equivalent query in terms of the other schema: see [START_REF] Deutsch | XML queries and constraints, containment and reformulation[END_REF][START_REF] Yu | Semantic adaptation of schema mappings when schemas evolve[END_REF] and more recently [START_REF] Moon | Managing and querying transaction-time databases under schema evolution[END_REF] with references thereof.

In addition to the fundamental differences between XML and the relational data model, in the more general case of XML processing, schemas constantly evolve in a distributed, independent, and unpredictable environment. The relations between different schemas are not only unknown but hard to track. In this context, one priority is to help maintaining query consistency during these evolutions, which is still considered as a challenging problem [START_REF] Sedlar | Managing structure in bits & pieces: the killer use case for XML[END_REF].

The work found in [START_REF] Moro | Preserving xml queries during schema evolution[END_REF] discusses the impact of evolving XML schemas on query reformulation. Based on a taxonomy of XML schema changes during their evolution, the authors provide informal -not exact nor systematic -guidelines for writing queries which are less sensitive to schema evolution. In fact, studying query reformulation requires at least the ability to analyze the relationship between queries. For this reason, a closely related work is the problem of determining query containment and satisfiability under type constraints [START_REF] Benedikt | XPath satisfiability in the presence of DTDs[END_REF][START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF]. The work found in [START_REF] Benedikt | XPath satisfiability in the presence of DTDs[END_REF] studies the complexity of XPath emptiness and containment for various fragments (see [START_REF] Benedikt | XPath leashed[END_REF] and references thereof for a survey).

The main distinctive idea pursued in this paper is to develop a logical approach for guiding schema and query evolution. In contrast to the classical use of logics for proving properties such as query emptiness or equivalence [START_REF] Benedikt | XPath satisfiability in the presence of DTDs[END_REF][START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF], the goal here is different in that we seek to provide the necessary tools to produce relevant knowledge when such relations do not hold.

Outline

The rest of this paper is organized as follows: the next section introduces our framework, Section 3 presents its underlying logic, and Section 4 presents predicates for characterizing the impact of schema changes. We report on experiments on realistic scenarios in Section 5 before we conclude in Section 6.

Analysis Framework

Our framework allows the automatic verification of properties related to XML schema and query evolution. In particular, it offers the possibility of checking fine-grained properties on the behavior of queries with respect to successive versions of a given schema. The system can be used for checking whether schema evolutions require a particular query to be updated. Whenever schema evolutions may induce query malfunctions, the system is able to generate annotated XML documents that exemplify bugs, with the goal of helping the programmer to understand and properly overcome undesired effects of schema evolutions. For these purposes, our framework relies on the combination and joint use of several contributions:

• an extension of the logic introduced in [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF] to deal with XML attributes (Sections 2 and 3);

• a set of logical features and high-level predicates specifically designed for studying and characterizing schema and query compatibility issues when schemas evolve (Section 4);

• a range of applications and procedures to cope with schema and query evolution (Section 5);

• a full implementation of the whole system, including:

a parser for reading the problem description (text file), which in turn use specific parsers for schemas (Section 2.2), queries (Section 2.3), logical formulas (Section 3.2), and predicates (Section 4);

compilers for translating schemas and queries into their logical representations (Sections 3.3 and 3.4);

an optimized solver first described in [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF]10] for checking satisfiability of logical formulas in time 2 O(n) where n is the formula size; -and a counter example XML tree generator (described in [10]).

Figure 1 illustrates how the previous software components are combined and used together, in a simplified overview of the global framework. We next introduce the data model we consider for XML documents, schemas and queries.

XML Trees with Attributes

An XML document is considered as a finite tree of unbounded depth and arity, with two kinds of nodes respectively named elements and attributes. In such a tree, an element may have any number of children elements, and may carry zero, one or more attributes. Attributes are leaves. Elements are ordered whereas attributes are not, as illustrated on Figure 4. In this paper, we focus on the nested structure of elements and attributes, and ignore XML data values.

Type Constraints

As an internal representation for tree grammars, we consider regular tree type expressions (in the manner of [START_REF] Hosoya | Regular expression types for XML[END_REF]), extended with constraints over attributes.

Assuming a set of variables ranged over by x, we define a tree type expression as follows:

τ Our tree type expressions capture most of the schemas in use today [START_REF] Murata | Taxonomy of XML schema languages using formal language theory[END_REF][START_REF] Bex | Expressiveness of XSDs: from practice to theory, there and back again[END_REF]. In practice, our system provides parsers that convert DTDs, XML Schemas, and Relax NGs to this internal tree type representation. Users may thus define constraints over XML documents with the language of their choice, and, more importantly, they may refer to most existing schemas for use with the system.

Queries

The set of XPath expressions we consider is given by the syntax shown on Figure 2. The semantics of XPath expressions is described in [START_REF] Clark | XML path language (XPath) version 1.0, W3C recommendation[END_REF], and more formally in [START_REF] Wadler | Two semantics for XPath[END_REF]. We observed that, in practice, many XPath expressions contain syntactic sugars that can also fit into this fragment. Figure 3 presents how our XPath parser rewrites some commonly found XPath patterns into the fragment of Figure 2, where the notation (axis::nt) k stands for the composition of k successive path steps of the same form: axis::nt/.../axis::nt k steps .

3 Logical Setting trees may be used instead of unranked trees without loss of generality. In the sequel, we rely on a simple "first-child & next-sibling" encoding of unranked trees. In this encoding, the first child of an element node is preserved in the binary tree representation, whereas siblings of this node are appended as right successors in the binary representation. Attributes are left unchanged by this encoding. For instance, Figure 5 presents how the sample tree of Figure 4 is mapped.

<r c=" " a=" " b=" "> <s d=" "> <v/><w/><x e=" "/> </s> <t/>  </r> XML Notation The logic we introduce below, used as the core of our framework, operates on such binary trees with attributes.

Logical Formulas

The concrete syntax of logical formulas is shown on Figure 6, where the metasyntax X means one or more occurences of X separated by commas. The reader can directly use this syntax for encoding formulas as text files to be used with the system described in Section 2 [START_REF] Genevès | A satisfiability solver for XML and XPath[END_REF]. This concrete syntax is used as a single unifying notation throughout all the paper.

The semantics of logical formulas corresponds to the classical semantics of a µ-calculus interpreted over finite tree structures. A formula is satisfiable iff there exists a finite binary tree with attributes for which the formula holds at some node. This is formally defined in [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF], and we review it informally below through a series of examples.

INRIA ϕ ::= formula T true F false l element name p atomic proposition # start context ϕ | ϕ disjunction ϕ & ϕ conjunction ϕ => ϕ implication ϕ <=> ϕ equivalence (ϕ) parenthesized formula ˜ϕ negation
ϕ existential modality <l>T attribute named l $X variable let $X = ϕ in ϕ binder for recursion predicate predicate (See Section 4) p ::= program inside modalities 1 first child 2 next sibling -1 parent -2
previous sibling There is a difference between an element name and an atomic proposition2 : an element has one and only one element name, whereas it can satisfy multiple atomic propositions. We use atomic propositions to attach specific information to tree nodes, not related to their XML labeling. For example, the start context (a reserved atomic proposition) is used to mark the starting context nodes for evaluating XPath expressions.

The logic uses programs for navigating in binary trees: the program 1 allows to navigate from a node down to its first successor and the program 2 for navigating from a node down to its second successor. The logic also features converse programs -1 and -2 for navigating upward in binary trees, respectively from the first successor to its parent and from the second successor to its previous sibling. Table 1 gives some simple formulas using modalities for navigating in binary trees, together with sample satisfying trees, in binary and unranked tree representations.

The logic allows expressing recursion in trees through the recursive binder. For example the recursive formula:

let $X = b | <2>$X in $X
means that either the current node is named b or there is a sibling of the current node which is named b. For this purpose, the variable $X is bound to the subformula b | <2>$X which contains an occurence of $X (therefore defining

Sample Formula

Tree XML

a & <1>b

a b  a & <1>(b & <2>c) a b c <c/> e & <-1>(d & <2>g) d e g <d><e/></d><g/> f & <-2>(g & ~<2>T)
none none Table 1: Sample Formulas and Satisfying Trees.

the recursion). The scope of this binding is the subformula that follows the "in" symbol of the formula, that is $X. The entire formula can thus be seen as a compact recursive notation for a infinitely nested formula of the form:

b | <2>(b | <2>(b | <2>(...)))
Recursion allows expressing global properties. For instance, the recursive formula:

~let $X = a | <1>$X | <2>$X in $X
expresses the absence of nodes named a in the whole subtree of the current node (including the current node). Furthermore, the fixpoint operator makes possible to bind several variables at a time, which is specifically useful for expressing mutual recursion. For example, the mutually recursive formula:

let $X = (a & <2>$Y) | <1>$X | <2>$X, $Y = b | <2>$Y in $X
asserts that there is a node somewhere in the subtree such that this node is named a and it has at least one sibling which is named b. Binding several variables at a time provides a very expressive yet succinct notation for expressing mutually recursive structural patterns (that are common in XML Schemas, for instance).

From a theoretical perspective, the recursive binder let $X = ϕ in ϕ corresponds to the fixpoint operators of the µ-calculus. It is shown in [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF] that the least fixpoint and the greatest fixpoint operators of the µ-calculus coincide over finite tree structures, for a restricted class of formulas called cycle-free formulas. Translations of XPath expressions and schemas presented in this paper always yield cycle-free formulas (see [10] for more details).

INRIA

Compilation of Queries

The logic is expressive enough to capture the set of XPath expressions presented in Section 2.3. For example, Figure 7 illustrates how the sample XPath expression: child::r[child::w/@att] is expressed in the logic. From a given context in an XML document, this expression selects all r child nodes which have at least one w child with an attribute att. Figure 7 shows how it is expressed in the logic, on the binary tree representation. The formula holds for r nodes which are selected by the expression. The first part of the formula, ϕ, corresponds to the step child::r which selects candidates r nodes. The second part, ψ, navigates downward in the subtrees of these candidate nodes to verify that they have at least one immediate w child with an attribute att. This example illustrates the need for converse programs inside modalities. The translated XPath expression only uses forward axes (child and attribute), nevertheless both forward and backward modalities are required for its logical translation. Without converse programs we would have been unable to differentiate selected nodes from nodes whose existence is simply tested. More generally, properties must often be stated on both the ancestors and the descendants of the selected node. Equipping the logic with both forward and converse programs is therefore crucial. Logics without converse programs may only be used for solving XPath emptiness but cannot be used for solving other decision problems such as containment efficiently.

A systematic translation of XPath expressions into the logic is given in [START_REF] Genevès | Efficient static analysis of XML paths and types[END_REF]. In this paper, we extended it to deal with attributes. We implemented a compiler that takes any expression of the fragment of Figure 2 and computes its logical translation. With the help of this compiler, we extend the syntax of logical formulas with a logical predicate select("query", ϕ). This predicate compiles the XPath expression query given as parameter into the logic, starting from a context that satisfies ϕ. The XPath expression to be given as parameter must match the syntax of the XPath fragment shown on Figure 2 (or Figure 3). In a similar manner, we introduce the predicate exists("query", ϕ) which tests the existence of query from a context satisfying ϕ, in a qualifier-like manner (without moving to its result). Additionally, the predicate select("query") is introduced as a shortcut for select("query", #), where # simply marks the initial context node of the XPath expression3 . The predicate exists("query") is a shortcut for exists("query", T). These syntactic extensions of the logic allow the user to easily embed XPath expressions and formulate decision problems out of them (like e.g. containment or any other boolean combination). In the next sections we explain how the framework allows combining queries with schema information for formulating problems.

Compilation of Tree Types

Tree type expressions are compiled into the logic in two steps: the first stage translates them into binary tree type expressions, and the second step actually compiles this intermediate representation into the logic. The translation procedure from tree type expressions to binary tree type expressions is well-known and detailed in [START_REF] Genevès | Logics for XML[END_REF]. The syntax of output expressions follows:

τ ::= binary tree type expression ∅ empty set () empty tree τ | τ disjunction l(a)[x, x]
element definition let x.τ in τ binder Attribute expressions are not concerned by this transformation to binary form: they are simply attached, unchanged, to new (binary) element definitions. Finally, binary tree type expressions are compiled into the logic. The logical translation of an expression τ is given by the function tr(τ ) F T defined below:

tr(τ ) ψ ϕ def = F for τ = ∅, () tr(τ 1 | τ 2 ) ψ ϕ def = tr(τ 1 ) ψ ϕ | tr(τ 2 ) ψ ϕ tr(l(a)[x 1 , x 1 ]) ψ ϕ def = (l & ϕ & tra(a) & s 1 (x 1 ) & s 2 (x 2 )) | ψ tr(let x i .τ i in τ ) ψ ϕ def = let $X i = tr(τ i ) ψ ϕ in tr(τ ) ψ ϕ
where the function s • (•) sets the type frontier:

s p (x) =    ˜
T if x is bound to () ˜
T |
$X if nullable(x)
$X if not nullable(x)
according to the predicate nullable(x) which indicates whether the type T = () bound to x contains the empty tree.

The function tra(a) compiles attribute expressions associated with element definitions as follows: tra(()) In usual schemas (e.g. DTDs, XML Schemas) when no attribute is specified for a given element, it simply means no attribute is allowed for the defined element. This convention must be explicitly stated into the logic. This is the role of the function "notothers(list)" which returns the negated disjunction of all attributes not present in list. As a result, taking attributes into account comes at an extra-cost. The above translation appends a (potentially very large) formula in which all attributes occur, for each element definition. In practice, a placeholder atomic proposition is inserted until the full set of attributes involved in the problem formulation is known. When the whole formula has been parsed, placeholders are replaced by the conjunction of negated attributes they denote. This extra-cost can be observed in practice, and the system allows two modes of operations: with or without attributes4 . Nevertheless the system is still capable of handling real world DTDs (such as the DTD of XHTML 1.0 Strict) with attributes. This is due to (1) the limited expressive power of languages such as DTD that do not allow for disjunction over attribute expressions (like "list | a" ); and, more importantly, (2) the satisfiability-testing algorithm which is implemented using symbolic techniques [10].

Tree type expressions form the common internal representation for a variety of XML schema definition languages. In practice, the logical translation of a tree type expression τ are obtained directly from a variety of formalisms for defining schemas, including DTD, XML Schema, and Relax NG. For this purpose, the syntax of logical formulas is extended with a predicate type(" • ", •). The logical translation of an existing schema is returned by type("f ", l) where f is a file path to the schema file and l is the element name to be considered as the entry point (root) of the given schema. Any occurence of this predicate will parse the given schema, extract its internal tree type representation τ , compile it into the logic and return the logical formula tr(τ ) F T .

Type Tagging

A tag (or "color") is introduced in the compilation of schemas with the purpose of marking all node types of a specific schema. A tag is simply a fresh atomic proposition passed as a parameter to the translation of a tree type expression. For example: tr(τ ) F xhtml is the logical translation of τ where each element definition is annotated with the atomic proposition "xhtml". With the help of tags, it becomes possible to refer to the element types in any context. For instance, one may formulate tr(τ ) F xhtml | tr(τ ′ ) F smil for denoting the union of all τ and τ ′ documents, while keeping a way to distinguish element types; even if some element names are shared by the two type expressions.

Tagging becomes even more useful for characterizing evolutions between successive versions of a single schema. In this setting, we need a way to distinguish nodes allowed by a newer schema version from nodes allowed by an older version. This distinction must not be based only on element names, but also on content models. Assume for instance that τ ′ is a newer version of schema τ . If we are interested in the set of trees allowed by τ ′ but not allowed by τ then we may formulate: tr(τ ′ ) F T &˜tr(τ ) F T If we now want to check more fine-grained properties, we may rather be interested in the following (tagged) formulation:

tr(τ ′ ) F all &˜tr(τ ) ˜old complement

T

In this manner, we can distinguish elements that were added in τ ′ and whose names did not occur in τ , from elements whose names already occured in τ but whose content model changed in τ ′ , for instance. In practice, a type is tagged using the predicate type("f ", l, ϕ, ϕ ′ ) which parses the specified schema, converts it into its logical representation τ and returns the formula tr(τ ) ϕ ′ ϕ . Such kind of type tagging is useful for studying the consequences of schema updates over queries, as presented in the next sections.

Analysis Predicates

This section introduces the basic analysis tasks offered to XML application designers for assessing the impact of schema evolutions. In particular, we propose a mean for identifying the precise reasons for type mismatches or changes in query results under type constraints.

For this purpose, we build on our query and type expression compilers, and define additional predicates that facilitate the formulation of decision problems at a higher level of abstraction. Specifically, these predicates are introduced as logical macros with the goal of allowing system usage while focusing (only) on the XML-side properties, and keeping underlying logical issues transparent for the user. Ultimately, we regard the set of basic logical formulas (such as modalities and recursive binders) as an assembly language, to which predicates are translated.

We illustrate this principle with two simple predicates designed for checking backward-compatibility of schemas, and query satisfiability in the presence of a schema.

• The predicate backward incompatible(τ, τ ′ ) takes two type expressions as parameters, and assumes τ ′ is an altered version of τ . This predicate is unsatisfiable iff all instances of τ ′ are also valid against τ . Any occurrence of this predicate in the input formula will automatically be compiled as tr(τ ′ ) F T &˜tr(τ ) F T . • The predicate non empty("query", τ ) takes an XPath expression (with the syntax defined on Figure 2) and a type expression as parameters, and is

INRIA

unsatisfiable iff the query always returns an empty set of nodes when evaluated on an XML document valid against τ . This predicate compiles into select("query", tr(τ ) F T & #) where the predicate select("query", ϕ) compiles the XPath expression query into the logic, starting from a context that satisfies ϕ, as explained in Section 3.3. This can be used to check whether the modification of the schema does not contradict any part of the query.

Notice that the predicate non empty("query", τ ) can be used for checking whether a query that is valid5 against a schema remains valid with an updated version of a schema. In other terms, this predicate allows determining whether a query that must always return a non-empty result (whatever the tree on which it is evaluated) keeps verifying the same property with a new version of a schema.

A second, more-elaborated, class of predicates allows formulating problems that combine both a query query and two type expressions τ, τ ′ (where τ ′ is assumed to be a evolved version of τ ):

• new element name("query", τ, τ ′ ) is satisfied iff the query query selects elements whose names did not occur at all in τ . This is especially useful for queries whose last navigation step contains a "*" node test and may thus select unexpected elements. This predicate is compiled into:

˜element(τ ) & select("query", tr(τ ′ ) F T )
where element(τ ) is another predicate that builds the disjunction of all element names occuring in τ . In a similar manner, the predicate attribute(ϕ) builds the logical disjunction of all attribute names used in ϕ.

• new region("query", τ, τ ′ ) is satisfied iff the query query selects elements whose names already occurred in τ , but such that these nodes now occur in a new context in τ ′ . In this setting, the path from the root of the document to a node selected by the XPath expression query contains a node whose type is defined in τ ′ but not in τ as illustrated below: node selected by query path from root to selected node contains node in τ ′ \ τ XML document valid against τ ′ but not against τ

The predicate new region("query", τ, τ ′ ) is logically defined as follows:

new region("query", τ, τ ′ ) def = select("query", tr(τ ) F all &˜tr(τ ′ ) ˜old complement T ) &˜added element(τ, τ ′ )
& ancestor( old complement) &˜descendant( old complement) &˜following( old complement) &˜preceding( old complement)

The previous definition heavily relies on the partition of tree nodes defined by XPath axes, as illustrated by Figure 8. The definition of new region("query", τ, τ ′ ) uses an auxiliary predicate added element(τ, τ ′ ) that builds the disjunction of all element names defined in τ ′ but not in τ (or in other terms, elements that were added in τ ′ ). In a similar manner, the predicate added attribute(ϕ, ϕ ′ ) builds the disjunction of all attribute names defined in τ ′ but not in τ . The predicate new region("query", τ, τ ′ ) is useful for checking whether a query selects a different set of nodes with τ ′ than with τ because selected elements may occur in new regions of the document due to changes brought by τ ′ .

• new content("query", τ, τ ′ ) is satisfied iff the query query selects elements whose names were already defined in τ , but whose content model has changed due to evolutions brought by τ ′ , as illustrated below: The definition of new content("query", τ, τ ′ ) follows:

INRIA
new content("query", τ, τ ′ ) def = select("query", tr(τ ) F all &˜tr(τ ′ ) ˜old complement T ) &˜added element(τ, τ ′ ) &˜ancestor(added element(τ, τ ′ )) & descendant( old complement) &˜following( old complement) &˜preceding( old complement)
The predicate new content("query", τ, τ ′ ) can be used for ensuring that XPath expressions will not return nodes with a possibly new content model that may cause problems. For instance, this allows checking whether an XPath expression whose resulting node set is converted to a string value (as in, e.g. XPath expressions used in XSLT "value-of" instructions) is affected by the changes from τ to τ ′ .

The previously defined predicates can be used to help the programmer identify precisely how type constraint evolutions affect queries. They can even be combined with usual logical connectives to formulate even more sophisticated problems. For example, let us define the predicate exclude(ϕ) which is satisfiable iff there is no node that satisfies ϕ in the whole tree. This predicate can be used for excluding specific element names or even nodes selected by a given XPath expression. It is defined as follows:

exclude(ϕ) def = ˜ancestor-or-self(descendant-or-self(ϕ))
This predicate can also be used for checking properties in an iterative manner, refining the property to be tested at each step. It can also be used for verifying fine-grained properties. For instance, one may check whether τ ′ defines the same set of trees as τ modulo new element names that were added in τ ′ with the following formulation:

˜(τ <=> τ ′ ) & exclude(added element(τ, τ ′ ))
This allows identifying that, during the type evolution from τ to τ ′ , the query results change has not been caused by the type extension but by new compositions of nodes from the older type.

In practice, instead of taking internal tree type representations (as defined in Section 2.2) as parameters, most predicates do actually take any logical formula as parameter, or even schema paths as parameters. We believe this facilitates predicates usage and, most notably, how they can be composed together. Figure 9 gives the syntax of built-in predicates as they are implemented in the system, where f is a file path to a DTD (.dtd), XML Schema (.xsd), or Relax NG (.rng). In addition of aforementioned predicates, the predicate predicate ::= select("query") select("query", ϕ) exists("query") exists("query", ϕ)

type("f ", l) type("f ", l, ϕ, ϕ ′ ) forward incompatible(ϕ, ϕ ′ ) backward incompatible(ϕ, ϕ ′ ) element(ϕ) attribute(ϕ) descendant(ϕ) exclude(ϕ) added element(ϕ, ϕ ′ ) added attribute(ϕ, ϕ ′ ) non empty("query", ϕ) new element name("query", "f ", "f ′ ", l) new region("query", "f ", "f ′ ", l) new content("query", "f ", "f ′ ", l) predicate-name( ϕ ) Figure 9: Syntax of Predicates for XML Reasoning.

descendant(ϕ) forces the existence of a node satisfying ϕ in the subtree, and predicate-name( ϕ ) is a call to a custom predicate, as explained in the next section.

Custom Predicates

Following the spirit of predicates presented in the previous section, users may also define their own custom predicates. The full syntax of XML logical specifications to be used with the system is defined on Figure 10, where the metasyntax X means one or more occurrence of X separated by commas. A global problem specification can be any formula (as defined on Figure 6), or a list of custom predicate definitions separated by semicolons and followed by a formula. A custom predicate may have parameters that are instanciated with actual formulas when the custom predicate is called (as shown on Figure 9). A formula bound to a custom predicate may include calls to other predicates,

INRIA

Schema

Variables but not to the currently defined predicate (recursive definitions must be made through the let binder shown on Figure 6).

Framework in Action

We have implemented the whole software architecture described in Section 2 and illustrated on Figure 1 [START_REF] Genevès | A satisfiability solver for XML and XPath[END_REF]. We have carried out extensive experiments of the system with real world schemas such as XHTML, MathML, SVG, SMIL (Table 2 gives details related to their respective sizes) and queries found in transformations such MathML content to presentation [START_REF] Pietriga | MathML content2presentation transformation[END_REF]. We present two of them that show how the tool can be used to analyze different situations where schemas and queries evolve.

Evolution of XHTML Basic

The first test consists in analyzing the relationship (forward and backward compatibility) between XHTML basic 1.0 and XHTML basic 1.1 schemas. In particular, backward compatibility can be checked by the following command:

backward_incompatible("xhtml-basic10.dtd", "xhtml-basic11.dtd", "html")

The test immediately yields a counter example as the new schema contains new element names. The counter example (shown below) contains a style element occurring as a child of head, which is not permitted in XHTML basic 1.0:   <title/>


Lynda Chehami
email: lynda.chehami@uphf.fr

Emmanuel Moulin

Marina Terzi

Non destructive auscultation and imaging of damages by distributed sensor array: step towards passive SHM under real conditions

Keywords: Noise Correlation, Beamforming, Pump-Probe

The passive imaging based on the Green's functions reconstruction from ambient noise correlation became a promising technique in structural health monitoring. Here, this approach is used to detect and locate linear defects (cracks, holes...) in thin reverberant plates with a small number of sensors. Correlation matrices before and after defect occurrence are estimated from friction noise. Based on a dispersive backpropagation algorithm in a thin plate, the differential matrix of correlations (before and after defect) is used for defect localization. This technique shows satisfactory results for linear defects, but refers to a measurement on a baseline healthy sample, which can be strongly affected by environmental conditions. In this context, an active baseline-free damage localization method that uses a repetitive pump-probe experiment, is proposed. A series of experiments are conducted in a thin aluminum plate using 7 PZTs sensors glued at known positions. One transducer generates a high frequency probe wave with central frequency 20 kHz, while a continuous low frequency pump of 1 Hz is produced by a shaker. A steel ball pressed against the plate to mimic a nonlinear defect is considered. The aim here is to produce solidsolid contact that will be modulated by the pump wave, as would be the case for instance in fatigue cracks. In order to enhance this effect, signals recorded at different times (corresponding to different loading states of the contact) are subtracted and back-propagated to locate the origin of the modulation.

Introduction

Twenty years ago, Weaver and Lobkis proposed a new way to exploit and take benefit from noise sources. The authors have experimentally shown on an aluminum block that the cross-correlation of elastic noise between two receivers provide the transient response between the two receiver positions as if one of them acted as an elastic transient source, interpreted as the Green's function GF of the medium [START_REF] Weaver | On the emergence of the Green's function in the correlations of a diffuse field: pulse-echo using thermal phonons[END_REF]. Actually, this property is not limited to thermal noise source but to any noise source distribution that generates an equipartitioned wave-field. In fact, in some situations it is desirable to avoid the need of active energy sources. So, the major interest of this result is the estimation of the GF without requiring any energy source. The main application of the Green's function extraction from noise correlation function (NCF) is in seismology where Artman has demonstrated the universal interest [START_REF] Artman | A return to passive seismic imaging[END_REF]. Passive Green's function estimation also offers promising applications in other domains ranging from ultrasound [START_REF] Mirgorodskii | Experimental Studies of Passive Correlation Tomography of Incoherent Acoustic Sources in the Megahertz Frequency Band[END_REF], underwater acoustics [START_REF] Roux | Extracting coherent wave fronts from acoustic ambient noise in the ocean[END_REF][START_REF] Sabra | Using ocean ambient noise for array self-localization and self-synchronization[END_REF] to medical imaging [START_REF] Sabra | Passive in vivo elastography from skeletal muscle noise[END_REF].

In ultrasound applications, and particularly in structural health monitoring field, power consumption and complexity of the electronics might represent key issues for the standard methods used in active configurations (pitch-catch). An alternative way could then consist in taking benefit of ambient noise to reveal defects (cracks, holes, etc) by passively estimating the GF using the physical principle based on noise correlation approach. Only a few works are devoted to structural health monitoring. In this field, a pioneer work consisted to use the traffic excitation to recover resonant frequencies and modal damping of a bridge from noise cross-correlation [START_REF] Farrar | System identification from ambient vibration measurments on a bridge[END_REF]. Later, this approach have been applied to extract the Rayleigh-Lamb Green's transient responses on plates [START_REF] Sabra | Structural health monitoring by extraction of coherent guided waves from diffuse fields[END_REF][START_REF] Larose | Reconstruction of Rayleigh-Lamb dispersion spectrum based on noise obtained from an air-jet forcing[END_REF]. The method is sufficiently sensitive to observe elastic signature of a plate defect on the cross-correlation [START_REF] Sabra | Structural health monitoring by extraction of coherent guided waves from diffuse fields[END_REF]. To localize a defect, an original method has been proposed [START_REF] Moulin | Applicability of acoustic noise correlation for structural health monitoring in nondiffuse field conditions[END_REF] that is particularly efficient when noise sources distribution is not uniform. The possibility of detecting and localizing defects using ambient noise (friction noise, acoustic noise...) more or less uniformly generated on surface plates has been recently demonstrated in recent works: numerically [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF] and experimentally [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF][START_REF] Chehami | Experimental study of passive defect localization in plates using ambient noise[END_REF][START_REF] Chehami | Nonlinear secondary noise sources for passive defect detection using ultrasound sensors[END_REF]. Some studies on the defect characterization are also derived based on the estimation of the far field pattern called scattering cross-section" [START_REF] Chehami | Scattering cross-section estimation using passive imaging in reverberating elastic plates: Case study of rigid isotropic inclusion[END_REF]. A statistical approach was also proposed by Chehami et al. [START_REF] Chehami | Accuracy of green's function estimation from correlation of diffuse elastic waves on thin plates[END_REF], which relates the similarity between the cross-correlation and the GF to the structural properties of the plate and the number of uncorrelated sources.

Based on all these studies, suitable noise sources for passive imaging application should be uncorrelated, spatially stationary and with wide-band frequency contents in the ultrasound range. This technique shows satisfactory results for linear defects, but requires additional measurements on a baseline intact sample for comparison with the actual one. The matter is that material's characteristics can slowly evolve due to aging, environmental effects, etc. In addition, measurements in the original state of a structure are frequently not available or not possible. The problem can be solved by using nonlinear methods based on strong acoustic nonlinearity induced by damage [START_REF] Novak | Nonlinear acoustic characterization of micro-damaged materials through higher harmonic resonance analysis[END_REF]. In this case, certain nonlinear criterion should be obtained instead of a simple difference in linear properties. In this context, an active baseline-free damage localization method that uses a repetitive pump-probe experiment, is proposed here.

The paper is organized as follows. In Section 2, we study the passive defect localization tested for holes, massive inclusions or even cracks. In Section 3 the baseline free-method base on pump-probe experiment is proposed and tested in mimic defects similarly to a crack or delaminations. Results of localization and imaging are presented and followed by concluding remarks in Section 4.

Passive defect imaging

A reverberating plate with a set of transducers fixed on its surface and subject to ambient acoustic noise is considered. It has been shown in a recent work [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF] that the differential correlation matrix, that is obtained from the subtraction of the correlation matrices with and without defect, is given by

∆C(t) = [∆G(t) -∆G(-t)] ⊗ f (t) + ∆n(t), (1)
where ∆G is the part of the Green's function due to the defect and ∆n the correlation residue (or reconstruction error), depending on the number and the distribution of noise sources. Function f (t) can be considered as a virtual excitation waveform and is given by

f (t) = N S τ a 2Sρh t -∞ R n (τ ) dτ, (2)
with N s is the number of sources, h the plate thickness, ρ the volume density, S the plate area, R n (τ ) the autocorrelation of the noise source and τ a the characteristic attenuation time constant of the plate.

As shown in previous works [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF][START_REF] Chehami | Experimental study of passive defect localization in plates using ambient noise[END_REF], this differential correlation matrix can be used as the input of a defect localization algorithm, as though it was an actively acquired signal matrix. However, two conditions are necessary for efficient detection: first the noise should have non-negligible components in the useful frequency band (where wavelengths are of the same order of magnitude as the defect size) and second, the correlation residue should be small compared to ∆G(t) ⊗ f (t). The second condition means that the noise sources should be both uncorrelated and well distributed over the plate surface or at least, as will be explained later, spatially stationary between the acquisitions with and without defect.

More recently, Chehami et al., have proposed a statical model which quantifies the accuracy of the GF reconstruction called "RNL" to "Relative Noise Level":

RNL(N s ) = 1 N s 5 4 + π η 0 τ a . (3)
As a consequence, for accurate retrieval of a Green's function, the reconstruction error must diminish when increasing the number of sources N s , the damping time τ a , and small plate area. One interesting result is that optimal reconstruction quality would be achieved for negligible attenuation (τ a η 0 ). In that case RNL (α -1)/N s , which implies the existence of a lower bound of the RNL equals to 5/4 N s and 2/N s for the rectangular and the chaotic plate, respectively.

The principle of the imaging algorithm used here is based on in back-propagating each element of indexes (i, j) of the matrix ∆C according to the current pixel position (x, y). The back-propagation function (bpf) of ∆C is given by [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF] bpf

(x,y) (ω) = N R ,N R i=1,j=1(i =j) ∆C ij (ω) e j [di(x,y)+dj (x,y)] k(ω) , (4)
where d i (x, y) is the distance between the i th receiver and the pixel at position (x, y), k(ω) is the wave number of the Lamb mode A 0 , ∆C ij (ω) is the Fourier transform of ∆C ij (t) and N R is the number of elements in the array (eight in this example). Then, by inverse Fourier transform, the pixel energy at position (x,y) is obtained by integrating the back-propagation function over time T 0 (accordingly to the approximation of back-propagation in an infinite plate), i.e.,

E(x, y) = T0/2 -T0/2 bpf (x,y) (t) 2 dt, (5)
where T 0 is typically the inverse of the bandwidth.

The bpf function leads to a constructive sum and a maximum of the pixel intensity on the defect location [START_REF] Chehami | Detection and localization of a defect in a reverberant plate using acoustic field correlation[END_REF]. As for pixels located elsewhere, the obtained intensity is made up of a summation of non-coherent contributions (including correlation residues ∆n, reverberated wavepackets, grating lobes).

To estimate the differential correlation matrix, the 8 receivers record the ambient noise during T = 60 s. The operation is performed one time without the defect and one time with the defect. Then the subtraction of the correlation matrices is performed.

The noise is produced on the plate by rubbing continuously and manually the whole plate surface with a soft scrubbing pad. Material fatigue often appears in the form of local change of physical properties. Therefore we have tested three kinds of defects: The beamformed images obtained with a massive inclusion and hole in the plate are displayed in Fig. 1. We observe that despite the fact that the inclusion is smaller than the hole, the spurious lobe level is higher for this last. This can be explained by the fact that the scattering strength of a hole is quite small for flexural waves. The next challenge is to detect a surface crack and a through-crack. Results for both cracks introduced above are presented in Fig. 2. As can be seen, the defects are successfully detected in both cases because the cracks strongly interact with the acoustic field. The quality of the image obtained with the through-crack informs us about the satisfying reconstruction of the Green's functions. However what is detected here is the strongest point of the defect which is likely the edge of the groove and the shape of the defect is not recovered. To achieve this, a complex inverse problem would have to be solved, which is completely beyond the scope of this paper.

The passive localization method presented here has been shown to be efficient and robust when considering differential mode. 3 Baseline-free repetitive probing method

In order to extend the application range of the correlation technique, a concept of a baseline-free pump-probe method is proposed here in active way for a model defect mimicking the behavior of a real nonlinear one.

In these series of experiments, the objective is to localize the origin of modulation due to a solid-solid contact (here it is a steel ball pressed against the surface of a plate) on a thin plate using ultrasound.

Experimental procedure

An aluminum rectangular plate (1 m × 0.5 m × 3 mm) is horizontally suspended with elastic cords on a metallic support. A 1 cm diameter steel ball is pressed against the top surface of the plate with elastic steel ruler fixed on the support cage (see Fig. 3).

The ball plays the role of a nonlinear defect (i.e., fatigue crack) to be localized. In order to find out the defect position, a pump-probe experiment has been conducted. One PZT patch (glued to the plate to provide acoustical coupling) generates a highfrequency (HF) probe wave which is a 100 ms burst with 1 cycle of 5 Vpp sine wave at f probe = 20 kHz. At the same time, a vibrating shaker rigidly attached to the plate and to the support cage produces a low-frequency (LF) pump wave which is a continuous 3 Vpp sine wave at f pump = 1 Hz. LF shaker parameters are so as plate continuously performs vertical oscillations, in a such a way that the position of the ball and the The idea of these different acquisitions is to collect as much data (information) as possible for different defect state without removing the defect. Elastic rubber cords attaching shaker to the support cage makes the shaker "invisible" in the resulting images (shaker-plate contact assumed to be negligible).

Signal processing and imaging results

Let us denote by s j i (j = 1...M ) the i th acquired signal at known receiver position r j , M is the number of receiving transducers. To enhance the effect of modulation, one should make subtractions between signals at different loading states and the average of all the acquisitions, i.e.,

∆s j i (t) = s j i (t) - 1 N N n=1 s j n (t), (6)
with n = 1...N acquisitions.

We obtain then N × M subtractive matrices which will be the inputs for the beamforming algorithm described in Section 2 (see Eq. 4). The pixel energy is computed according to Eq. 5. Finally, by non coherent summation we get the final image result. On the obtained images we can see that it is possible to localize defect inside and outside the transducers area. In comparison with the results of a conventional backpropagation algorithm applied for baseline experiments (see L. Chehami et al., [START_REF] Chehami | Experimental study of passive defect localization in plates using ambient noise[END_REF]), in the current images signal-noise-ratio (SNR) is lower: there are many artifacts. This can be interpreted by the lack of information about the modulation effects: in contrast to the array of emitters used for baseline experiments, in pump-probing experiments only one transducer plays role of emitter. Finally, we should mention that some problems can occur if during the experiment acoustic emission (squealing effects) appears.

Conclusions

In this work, we have firstly presented an experimental validation of a passive technique for defect localization in metallic plates. We have successfully detected defects from noise generated by different sources between 10 kHz and 40 kHz. Using noise correlation approach, we have experimentally shown that the method is suitable and robust to detect holes, massive inclusions and even surface or through cracks in the plate. Second, we proposed a baseline-free repetitive pump-probe experimental procedure to detect a contact-like nonlinear defect. The localization of the origin of modulation based on adapted back-propagation algorithm has been described. Efficiency of the algorithm has been illustrated with localization of a 1 cm steel ball pressed against vertically oscillating aluminum plate. Imprecision of this algorithm is connected with an asymmetry of transducers geometry (only one of them plays the role of emitter), in contrary to conventional beamforming algorithm, where all the transducers are at the same time both emitters and receivers. Thus, in this configuration there are preferred directions, and a success of defect localization depends on mutual location of defect and transducers. These preliminary experiments are very promising for Structural Health Monitoring applications and are expected to be of considerable value in the future. Further work will focused on the improvement of the SNR images and adapting the current algorithm for passive baseline-free SHM, without need of ultrasonic emitter.

Fig. 1 .

 1 Fig. 1. Beamformed images obtained from ∆C resulting from frictional noise in dB scale. (a) a hole of 15 mm of diameter, located at (1.025, 0.343) m (center of the hole). (b) a massive inclusion of 8 mm diameter, located at (0.58, 0.348) m (center of the inclusion).

Fig. 2 .

 2 Fig. 2. Beamformed images obtained from ∆C resulting from frictional noise in dB scale. (a) surface crack of 30 mm × 1 mm and 2 mm depth, located at (0.82, 0.49) m (center of the crack). (b) a through-crack of 30 mm × 1 mm and 3 mm depth, located at (0.86, 0.54) m (center of the crack).

Fig. 3 .

 3 Fig. 3. (left) Pump-probe experimental setup. (right) Nonlinear defect "solid-solid" contact.

  The obtained results based on this repetitive probing method are shown on Fig.4. The positions of transducers are indicated by crosses and that of the shaker and defect by, respectively, a circle and a square. The origin of coordinates is taken at the left lower corner of the plate. The spatial pixel resolution is ∆x = ∆y= 5 mm. One of the transducers array is used as emitter for each figure.

Fig. 4 .

 4 Fig. 4. Imaging localization results obtained for a nonlinear solid-solid contact located at: (a) [0.695,0.264] m, and (b) [0.4,0.145] m. (a-right) Zoom on the receivers area. The positions of the shaker and defect are, respectively, indicated by a circle and a square. E is the emitter.

Acknowledgment

This work has been supported by the French National Research Agency (ANR): Grant ANR2011-BS09-03901 (PASNI Project), and Grant ANR2017-CE08-0013-01 (PANSCAN project).


N Wartenberg

O Raccurt

D Imbert

M Mazzanti

E Bourgeat-Lami

Luminescent latex particles loaded with anionic lanthanide complexes: versatile platforms for multicolour optical coding

Luminescent polymer latexes based on lanthanide complexes have been synthesized by miniemulsion polymerization. A self-assembled europium complex was embedded into poly(methyl methacrylate) nanoparticles without covalent linking and compared to a commercially-available neutral chelate. The nature of the surfactant was found to have a great impact on the incorporation process for the europium complex and only the latexes stabilized by a cationic surfactant exhibited a luminescence signal. A maximum doping level of about 2% in weight in the final 10 monodispersed particles was obtained. The resulting polymeric luminescent nanoparticles showed good stability over leakage. The described synthetic method was used to incorporate multiple lanthanide complexes into latexes nanoparticles affording multicolour nanolabels. Two series of polymeric latexes bearing codes are presented.

INTRODUCTION

The synthesis of luminescent nanoparticles is an attractive field that has received a lot of interest over the past decade [1][2][3]. A large variety of nanoparticles has already been developed and well described in the literature such as quantum dots [4], dye-doped silica [5] or polymeric nanoparticles [6]. The confinement of thousands of fluorescent molecules at the nanometer scale renders those kinds of particles particularly attractive for biological imaging due to their high sensitivity and selectivity [7]. Encapsulation of fluorophores into particles offers the possibility to functionalize the resulting particles, which is particularly useful for targeting applications [8,9]. More recently, the development of nanoparticles containing tags bearing codes has been extensively studied for multiplex bioassays [10,11] or for products authentication and traceability to ensure the safety and quality of goods and to prevent counterfeits [12]. However, the capacity to read a lot of different emission simultaneously remains a major issue in this field. Indeed, the limitation for providing such complex codes based on luminescence is the number of luminescent molecules that one can effectively use before their emission signals overlap. One way to overcome this limitation is to use lanthanide chelates. Indeed, lanthanide complexes present numerous advantages over organic dyes such as large Stoke shifts, sharp emission spectra, long lifetimes and intrinsic protection against photobleaching [13]. The high potential of lanthanide complexes embedded into nanoparticles has been demonstrated for both silica [14,15] and polymers [16]. Due to their versatile properties and applications, polymeric latexes are used in various areas including textiles, paints, coatings and bioassays [START_REF] Caruso | Colloids and Colloid Assemblies[END_REF][START_REF] Urban | Polymer Dispersions and their 5 industrial applications[END_REF]. Different routes have been explored for adding fluorescent dyes to polymeric nanoparticles. Fluorescent dyes can be adsorbed onto the particle surface [START_REF] Charreyre | [END_REF], copolymerized with the particles using luminescent monomers [20], introduced in the latex particles after their synthesis through diffusion [21,22] or simply trapped inside the particles during polymerization [6]. It has been demonstrated that when luminescent molecules are covalently attached to the particles, they are less prone to leakage issues [2]. However, the chemical structure of the luminescent molecules has to be adapted to allow their covalent attachment to the polymer chains. This can sometime result, depending on the type of modification, on a change of the energy levels of the ligand resulting in a reduced efficiency of the lanthanide luminescence emission [13]. On the other hand, several studies have dealt with non-covalent incorporation by simple dissolution of the dye into the monomer followed by polymerization [11,16]. This loading method is more flexible but then leakage issues may occur [21]. Due to the low water solubility of the luminescent dye, a very convenient process for non-covalent dye encapsulation is miniemulsion polymerization [23]. Miniemulsions are aqueous dispersions of kinetically stabilized submicronic (50-500 nm) monomer droplets prepared by using highshear devices such as ultrasounds or high-pressure homogenizers [24]. Miniemulsion droplets are stabilized against coalescence by using an appropriate surfactant (typically the same as in conventional emulsion polymerization), while monomer diffusion (e.g., Ostwald ripening) can be in principle retarded by the use of highly water-insoluble compounds (so-called hydrophobes) [25]. Hence, if the system is correctly formulated, the nanodroplets become the prevalent locus of nucleation [26]. This means that if one can directly dissolve some products like for instance lanthanide chelates in the monomer phase before it is dispersed, it should be possible to incorporate them into polymer particles through droplet nucleation without changing the identity of the droplets. Indeed, ideally, each of the monomer droplets is converted into a polymer particle of identical chemical composition. A large variety of compounds have been successfully incorporated into polymer latexes using this technique, but only few examples of lanthanide-containing polymer nanoparticles have been reported [11,16,27,28]. Moreover these examples have been limited to neutral complexes. Polymeric nanoparticles incorporating lanthanide complexes capable of providing multiple, non-overlapping emission signals in different UV and Near-IR regions under a unique excitation wavelength are particularly desirable for the development of multimodal tags, bar-codes and lighting devices, but are rare. We have recently reported the synthesis of Ln(pytz) 3 (NHOct 3 ) 3 complexes based on a tridentate pyridine-tetrazolate ligand able to efficiently sensitize every luminescent lanthanide in the visible, the NIR or both regions [29,30]. Here, we report the incorporation procedure for the anionic Eu III complex into poly(methyl methacrylate) (PMMA) nanoparticles through a miniemulsion polymerization process implemented for the incorporation of anionic complexes. We then demonstrate the possibility of the simultaneous incorporation of up to four lanthanide complexes into polymer particles leading to unique and complex optical signatures.

EXPERIMENTAL SECTION

Materials

Tris(dibenzoylmethane)

mono(1,10-phenanthroline) europium(lll) (Eu(dbm) 3 (phen)), trioctylamine and Ln(III) trifluoromethanesulfonate (Ln = Eu, Tb, Sm, Dy) were used as received from Aldrich. Methyl methacrylate (MMA), octadecyl acrylate (ODA), cetyl ammonium bromide (CTAB), sodium dodecyl sulfate (SDS), 2-2'-azobis(2methylpropionamidine) dihydrochloride (AIBA) and potassium persulfate (KPS) were all purchased from Acros Organics, and used without further purification. Lutensol AT-50 was received from BASF. Ultrapure water (18.2 MΩ) was used throughout the experiments.

Preparation of Ln(pytz) 3 (NHOct 3 ) 3

The homoleptic trianionic lanthanide complexes Ln(pytz) 3 (NHOct 3 ) 3 (Scheme 1) were prepared as previously described by reacting three equivalents of the 2,6-bis-tetrazolyl-pyridine ligand (H 2 pytz) with one equivalent of lanthanide trifluoromethanesulfonate in methanol solution in the presence of trioctylamine and the solids were isolated according to the previously reported procedure [29].

Preparation of luminescent PMMA nanoparticles

Two different lanthanide complexes were incorporated in polymeric nanoparticles. The neutral, commercially available Eu(dbm) 3 (phen) lanthanide complex was used as reference and compared with the Eu(pytz) 3 (NHOct 3 ) 3 complex. Three kinds of surfactants were used to investigate their influence on the incorporation efficiency of both chelates. CTAB, SDS and Lutensol AT-50 were used as cationic, anionic and non-ionic surfactants, respectively. The amounts of the compounds used in the reactions are given in Table 1.

The lanthanide complexes were dissolved in a mixture of MMA and ODA. Then, the organic phase was added to the aqueous solution of surfactant under vigorous magnetic stirring. After 30 minutes of pre-emulsification, the solution was sonicated under magnetic stirring in an ice-cooled bath for 10 minutes at 80% amplitude (Branson sonifier 450, 750 W) to form miniemulsion droplets. Then, the miniemulsion was transferred in a three-necked 100 mL round-bottom flask equipped with a condenser. The reaction mixture was heated to 70°C under magnetic stirring and degassed with nitrogen for 15 minutes. The polymerization was initiated by KPS or AIBA (dissolved in 5 g of water and degassed) under nitrogen atmosphere. The reaction was allowed to continue between one and two hours depending on the surfactant used. A similar procedure was used to incorporate mixtures of lanthanide complexes into latex particles. In both cases, samples of final latexes were dialyzed against ultrapure water (3,5 kDa cut off, Roth) for 48 hours to remove unreacted materials and nonincorporated lanthanide complexes before analysis. Several aliquots from non-dialyzed solutions were collected after different periods of time for stability measurements. These aliquots were filtrated with Vivaspin (5 kD molecular weight cut-off) from Sartorius Biolab Products by centrifugation (15 minutes at 8500 rpm). The recovered solutions (free from particles) were analyzed by Inductively Coupled Plasma Mass Spectrometry (ICPMS, HP 4500 series) to evaluate the amount of lanthanide leaking out of the nanoparticles over time and the incorporation efficiency, which was defined as the percentage of lanthanide complex that was effectively incorporated in the particles compared to the quantity initially introduced. Multicolour nanoparticles were prepared by mixing three and four isolated lanthanide complexes, Tb, Eu, Dy and Tb, Eu, Dy, Sm, respectively. The chosen percentages of each metal ion used were calculated taking into account the values of the lanthanide complexes quantum yields 29.1, 70.2, 6.2 and 1.4 for Eu, Tb, Dy and Sm, respectively. The respective quantities used for the preparations of the colour codes with similar luminescence intensities for each lanthanide were: 1.8, 4.7 and 21.3 mg for Tb, Eu and Dy and: 0.4, 1.1, 5.0 and 21.4 mg for Tb, Eu, Dy and Sm corresponding to the ratios 1/3/12/ for Tb/Eu/Dy and 1/3/12/56 for Tb/Eu/Dy/Sm, respectively. The emission spectra of the two samples colour codes were recorded and normalized between 0 and 1 for comparison.

Characterization

Monomer conversion were determined gravimetrically by measuring the solids content of the final latexes. Dynamic Light Scattering (DLS, Nano-ZS from Malvern Instruments) was used to measure the droplet and particle sizes (intensity-averaged hydrodynamic diameters) and the polydispersity (indicated by the poly value -the higher this value, the broader the size distribution). In a typical experiment, samples were diluted in ultrapure water prior to measurement. The dialyzed latexes were characterized by Transmission Electron Microscopy (TEM) (Tecnai G2 S-TWIN, 200kV). Each latex sample was diluted and one drop of the solution was deposited on a carbon-coated copper grid. The sample was dried at ambient temperature and observed at an accelerating voltage of 200 kV. The luminescence spectra and lifetimes were recorded using a modular Fluorolog FL 3-22 spectrometer from Horiba-Jobin Yvon-Spex equipped with a double grating excitation monochromator and a iHR320 imaging spectrometer coupled to a R928P Hamamatsu photomultiplier. All spectra were corrected for detection and optical spectral response (instrumental functions) of the spectrofluorimeter. The ionic Eu(pytz) 3 (NHOct 3 ) 3 chelate forms an ion-pair with the lipophilic trioctylamines and was therefore fully soluble in MMA. The resulting monomer solutions conserved their luminescent properties and were used to generate miniemulsion droplets in the presence of different kinds of surfactants. The results are summarized in Table 2. All samples were colloidally stable and free of coagulum. The MMA conversion was limited to c.a. 90% in case of the non-ionic surfactant and close to 100% (within experimental error) for CTAB and SDS. The particle size was strongly dependent on the nature of the surfactant and was significantly larger for Lutensol AT-50 than for SDS or CTAB as expected. Indeed the stabilization of the miniemulsion by the non-ionic surfactant was less effective [31], leading to an important coalescence phenomenon during the polymerization. The limiting conversion observed for this particular experiment thus probably resides in the larger droplet/particle sizes. Obviously, the non-ionic surfactant does not satisfy the ideal scenario of a one-to-one copy of droplets into particles as attested by the low ratio of the number of particles to the number of droplets, (N p /N d , Table 2). If there is a deviation from unity in this ratio, then it is preferable that it be slightly less than one rather than slightly greater than one. In the second scenario, if N p /N d is greater than one, this implies that new particles have been created during the reaction and these new particles would not contain lanthanide chelates. If N p /N d is lower than one, this means on the contrary that the miniemulsion suffered either droplet-droplet or dropletparticle coalescence which should guaranty that all final latex particles contain some lanthanide complex. In order to confirm the successful encapsulation of the lanthanide complex, the latexes were thoroughly dialyzed against ultrapure water and their emission and excitation spectra were recorded. Europium luminescence was only observed for PMMA nanoparticles stabilized by the cationic surfactant (Figure 1). Indeed, for both Lutensol AT-50 and SDS, the europium signal completely disappeared after dialysis. This result demonstrates that Eu(pytz) 3 (NHOct 3 ) 3 was not incorporated into the polymer latex particles when the latter were stabilized by anionic or non-ionic surfactants. In contrast, the polymer nanoparticles stabilized with CTAB exhibited a strong luminescence after dialysis as shown in Figure 1. Furthermore, it should be noted that the observed maximum emission at 617 nm and the shape of the emission and excitation spectra are in agreement with that of the europium chelate in methanol [29]. Time-resolved luminescence experiments were also carried out on the doped latex and Eu(pytz) 3 (NHOct 3 ) 3 dissolved in methanol to establish whether the fluorescence emission was affected by the PMMA environment. Intensity decay curves could be fitted to single exponentials, yielding luminescence lifetimes of 3.38 ms and 2.92 ms in methanol and PMMA, respectively (Figure S1, Supporting Information). The identical emission spectra (transitions and splitting analysis) and lifetimes found in solution and in the latex particles indicate that the embedded complexes remained intact. In the literature, several neutral lanthanide complexes have been successfully incorporated into polymer latex using various types of surfactants without mention of any difficulty [11,16,27]. The solubility of the luminescent molecule into the monomer seemed to be sufficient to ensure efficient incorporation. The fact that both non-ionic and anionic surfactants lead to non-luminescent polymeric nanoparticles for Eu(pytz) 3 (NHOct 3 ) 3 although the latter is fully soluble in MMA, is likely to reside in the anionic character of the complex. In order to confirm this assumption, two experiments were performed in exactly the same way as for the CTAB and SDS experiments, except that Eu(pytz) 3 (NHOct 3 ) 3 was replaced by Eu(dbm) 3 (phen), which is fully soluble in MMA and exhibits a non-ionic structure. In both cases, the final dialyzed latexes were found to be luminescent indicating successful dye incorporation regardless of the nature of the surfactant (Figure S2, Supporting Information).

Elucidation of the role of the surfactant

The above results show that we did not succeed in incorporating Eu(pytz) 3 (NHOct 3 ) 3 into PMMA latex particles when SDS or Lutensol AT-50 were used as surfactants, even though the complex was fully soluble in MMA. We believe that the trioctylammonium cations that are responsible for the chelate solubility in MMA, interact with the water phase at the monomer droplet/water interface during droplet formation. This could lead to the exclusion of the resulting anionic complex from the monomer droplets. In order to confirm this assumption, we have performed partitioning experiments to estimate the fraction of europium that can migrate in the water phase prior to polymerization. Four mixtures (three containing surfactant and one without surfactant) were prepared according to the same protocol used before except that they were not polymerized. To allow phase separation, ODA was removed from the formulation and the mixtures containing surfactant were not sonified. After decantation, the quantity of Eu(III) into the water phase was determined by ICPMS. A reference experiment in pure water was also conducted in parallel to estimate the water solubility of Eu(pytz) 3 (NHOct 3 ) 3 . The percentages of Eu(III) located in the water phase in the different cases are presented in Figure 2. When SDS or Lutensol AT-50 were used as surfactants, an important quantity of Eu(III) was found to be localized into the water phase. The same behavior was observed in the absence of surfactant, indicating that SDS and Lutensol AT-50 have no significant influence on Eu(pytz) 3 (NHOct 3 ) 3 partitioning. In contrast, the Eu(III) quantity into the water phase was found to be much lower when CTAB was used as surfactant. In this case, the Eu(III) concentration in the water phase was comparable to the Eu(pytz) 3 (NHOct 3 ) 3 water solubility and the slight difference between the two concentrations can be attributed to the MMA water solubility. These results indicate that CTAB could prevent the ionic lanthanide complex from diffusing out of the monomer phase during droplets formation by forming an electrostatic barrier at the monomer droplets/water interphase. In the event that the lanthanide complex could nevertheless migrate to the interface and dissociate, the resulting negatively charged europium chelate would instantaneously recombine with the CTAB molecules adsorbed at the surface of the droplets, which would restabilize the complex. In contrast, when SDS or Lutensol AT-50 were used as surfactants, the lanthanide complex could come in contact with water resulting in the loss of trioctylammonium ions and to a negatively charged lanthanide chelate, no more soluble in MMA. Consequently in those cases, lanthanide chelates are excluded from monomer droplets and the incorporation failed. It is worth noting here that Eu(pytz) 3 (NHOct 3 ) 3 is only partially soluble in water due to the hydrophobic character of the trioctylammonium cations. In contrast, when the lanthanide complex was first solubilized in MMA, the ionic europium chelate could better interact with water as the contact interfacial area was much higher, and thus dissociation of the trioctylammoniumcations was more important in this case.

Properties of Eu(pytz) 3 (NHOct 3 ) 3 -loaded PMMA latex particles stabilized by CTAB

Next, we examined the maximum loading capacity of the PMMA nanoparticles stabilized by CTAB, and their resulting luminescence properties. Several amounts of Eu(pytz) 3 (NHOct 3 ) 3 from 0.3 to 2 wt% (based on monomer) were introduced into MMA, and the resulting mixtures were sonified and polymerized. In all experiments, MMA conversion reached 100% after one hour. All miniemulsions were stable and exhibited a gradual increase in both initial droplet and final particle sizes with increasing the Eu(pytz) 3 (NHOct 3 ) 3 content (e.g., N p /N d remained almost constant) except, for the largest amount where the particles started to aggregate (Table 3). Indeed at 2 wt%, the particle size strongly increased during the polymerization (e.g. N p /N d significantly decreased) and the latex was found to be highly viscous and polydisperse, indicating that a destabilization occurred. Consequently, we did not attempt to increase further the amount of lanthanide complex, as we could not get stable particles for higher loadings. Ritcey et al. [16] found similar results when increasing the amount of europium complex above 2wt% during miniemulsion polymerization of styrene stabilized by SDS. In the present study, the efficiency of the incorporation was found to be constant at 87.0 ± 1.6 % in the entire range of concentrations investigated indicating a very efficient incorporation whatever the amount of complex. In addition, TEM analysis (Figure 3) and DLS measurements showed that the particles were spherical and monodisperse (poly values lower than 0.1, Table 3). As seen in Figure 3a, no black spots could be observed at low loading contents indicating homogeneous incorporation of the lanthanide complex. In contrast, a few black spots could be identified inside the PMMA nanoparticles for higher loading contents (Figure 3b) probably due to slight aggregation of the europium chelates, which may facilitate their observation. Figure 4 shows the evolution of the luminescence intensity with increasing the amount of lanthanide chelates introduced. The intensity increased gradually with increasing the quantity of lanthanide complex. The corresponding lifetimes were found to be constant at 2.88 ± 0.11 ms, which proves that no quenching occurred in the whole range of concentrations investigated. This behavior was confirmed by quantum yield measurements, which also remained constant (Table 4). The strong binding of the large bulky organic ligand prevents intermetallic energy transfers from occurring. This is consistent with the high quantum yields 10 measured for the pure complexes in the solid state [29].

Nevertheless absorption of the PMMA matrix was found to be quite high as indicated by the 20 % decrease of the quantum yield. Based on the particle sizes and the solid contents, the number of complexes per particle could be estimated. Each latex particle contained between c.a. 10 3 and 10 4 chelated lanthanide ions. In order to evaluate the stability over leakage of the lanthanide complex-loaded polymer particles, the europium concentration in the recovered serums (aliquots of water phase free from particles) was determined two weeks and two months after synthesis, and compared to the one after polymerization. The results of Figure 5 show that no leakage occurred in ultrapure water in ambient 35 conditions within the experimental error. Indeed the europium concentration in the water phase was equal to 13.0 ± 1.5 % after two weeks and to 14.4 ± 1.2 % after two months whose values are very close to the one determined immediately after synthesis (e.g. 13.0 ± 1.6 %). Then, it can be concluded that the incorporation 40 was stable over at least two weeks.

Example of multicolor nanoparticle based on lanthanides emission

Eu(pytz) 3 (NHOct 3 ) 3 was used to investigate the incorporation 50 process. It is not expected that the change in lanthanide will affect the synthesis. Then, two mixtures of Ln(pytz) 3 (NHOct 3 ) 3 with Ln = Tb, Eu, Dy and Ln = Tb, Eu, Dy, Sm, respectively, were incorporated into PMMA particles. The same protocol used before was followed and after dialysis, luminescent properties of 55 the resulting latexes were measured. As it is shown in Figure 6, characteristic emission of each lanthanide can be distinguished.

The two samples showed a well-resolved fluorescence with not measurable intermetallic quenching arising from the mixing of the different lanthanide complexes. This result demonstrates that 60 the present system can be used to tailor the emission properties of latex nanoparticles under a single excitation wavelength.

CONCLUSIONS

We described the non-covalent incorporation into PMMA latex particles of a series of original Ln III ion-pair complexes based on a ligand able to sensitize efficiently over ten lanthanide ions after excitation under the same wavelength. This particular chelate was compared to a commercially available neutral complex similar to the ones commonly reported in the literature. It was found more challenging to incorporate the anionic than the neutral lanthanide chelates although both complexes were fully soluble in MMA. Indeed, while the neutral lanthanide complex could be successfully introduced into PMMA nanoparticles regardless of the nature of the surfactant, the Eu(pytz) 3 (NHOct 3 ) 3 chelate was not totally immune to its immediate environment, and required an appropriate choice of surfactant to maintain it inside the particles. Hence, a successful incorporation without covalent attachment 20 and with up to 87% efficiency was achieved in this case when using a cationic surfactant that provided an electrostatic barrier preventing the chelate from diffusing in the water phase. This provides an unprecedented route to the incorporation of ionic lanthanide complexes into polymer nanoparticles. Since many introduced (in the range 0-2 wt% based on polymer). The resulting encoded latex suspensions were found to contain a significant number of lanthanide ions uniformly distributed within the particles. The latexes also proved to have excellent colloidal stability similar to that of the bare latex suspension and 35 good stability over leakage. The same procedure can be used to incorporate a series of lanthanide ions emitting at different wavelengths affording multicolour latex labels. As a proof of concept, multiple different emission spectra could be obtained, with the same excitation wavelength, by mixing up to four 40 lanthanides and by adjusting their molar ratio. Indeed contrary to organic dyes, which possess large emission spectra, sharp lanthanide emissions allow their simultaneous use without overlapping issues. As it is theoretically possible to produce millions of codes by varying the amount of lanthanide ions, the 45 emission range as well as the intensity and time-scale levels, this platform is particularly promising for multiplex detection, and could find applications in biomedicine, in materials coding or in optical photonic devices.

Notes and references

Scheme 1 .

 1 Scheme 1. Chemical structure of the homoleptic trianionic Ln(pytz)3(NHOct3)3 lanthanide complexes.

  ARTICLE TYPE www.rsc.org/xxxxxx | XXXXXXXX 4|Journal Name, [year], [vol], 00-00 This journal is © The Royal Society of Chemistry [year]

Figure 1 .

 1 Figure 1. Excitation and emission spectra of Eu(pytz)3(NHOct3)3loaded PMMA latex particles stabilized by CTAB (ʎan = 617 nm and ʎem = 300 nm).

Figure 2 .

 2 Figure 2. Estimation of Europium partitioning between water and MMA before polymerization for different formulations.

  water phase (%) www.rsc.org/xxxxxx | XXXXXXXX 6|Journal Name, [year], [vol], 00-00 This journal is © The Royal Society of Chemistry [year]

85. 4 aFigure 3 .

 43 Figure 3. TEM images of PMMA latex particles doped with a) 0.3 wt% and b) 1.6 wt% of Eu(pytz)3(NHOct3)3

Figure 4 .

 4 Figure 4. Luminescence intensity at 617 nm as a function of the

Figure 5 .

 5 Figure 5. Europium concentrations in the serum (in percentage of the total amount introduced) after two weeks and two months as a function of the 45

8|Journal

  Name, [year], [vol], 00-00 This journal is © The Royal Society of Chemistry [year]

Figure 6 .

 6 Figure 6. Normalized emission spectra of a) Ln(pytz)3(NHOct3)3 in methanol (2.3•10 -3 M, Ln = Sm, Eu, Tb, Dy) and b, c) Ln(pytz)3(NHOct3)3-loadedPMMA latex particles under 300 nm irradiation.Ln=Eu,Tb,Dy (b) and Ln=Eu,Tb,Dy,Sm (c).

  (pytz)3(NHOct3)3-loaded PMMA latex particles, excitation and emission spectra of Eu(dbm)3(phen)-loaded PMMA latex particles stabilized by SDS, emission spectra of Ln(pytz)3(NHOct3)3 in methanol 70 (Ln=Sm, Tb , Eu and Dy) and equations used to determine the number of lanthanide complexes per particle and the incorporation efficiency]. See DOI: 10.1039/b000000x/

Table 1 .

 1 Standard procedure for the preparation of PMMA luminescent particles by miniemulsion polymerization.

	Compound		Amount (g)
	MMA		10.0
	Lanthanide complex		0.050
	ODA		0.4
	SDS/Lutensol AT-50/CTAB	0.075/0.15/0.075
	KPS/AIBA a		0.1
	Water		50
	a The nature of the initiator depends on the type of surfactant used.
	KPS was used for both SDS and Lutensol AT-50 while AIBA was
	used for CTAB
	RESULTS AND DISCUSSION
	Preparation	and	characterization	of
	Eu(

pytz)3(NHOct3)3-loadedPMMA latex particles

Table 3

 3 Miniemulsion polymerization of MMA stabilized by CTAB in the presence of various amounts of Eu(pytz)3(NHOct3)3.

	Eu(pytz)3(NHOct3)3	Monomer	Droplet	Particle	Poly value b	Np/Nd	Incorporation Efficiency
	content (wt%) a	conversion (%)	diameter (nm) b	diameter (nm) b			(%)
	0	97.7	89	105	0.028	0.66	-
	0.3	99.9	102	122	0.013	0.47	85.7
	0.5	99.7	119	136	0.050	0.54	87.5
	0.8	99.9	106	132	0.010	0.42	88.5
	1.0	99.9	140	144	0.015	0.74	87.6
	1.6	100	167	174	0.010	0.71	87.0
	2.0	99.8	223	376	0.437	0.17

Table 4

 4

	. Number of Eu(pytz)3(NHOct3)3complexes incorporated per
	particles and corresponding quantum yields.
	Eu(pytz)3(NHOct3)3co ntent (wt%) a	Quantum Yield (%) b c	Number of complexes per particle d
	0.3	39	60	841
	0.5	41	63	2329
	0.8	40	60	3115
	1.0	38	58	5567
	1.6	40	61	14321
	2.0	39	60	-e

a Initial content relative to MMA. b Measured with water as reference. c Measured with PMMA as reference. d Calculated from DLS particle size and solids content. e Not calculated due to the high polydispersity.

50 a

 50 Université de Lyon, Univ. Lyon 1, CPE Lyon, CNRS UMR5265, Laboratoire de Chimie, Catalyse, Polymères et Procédés (C2P2), LCPP group, 43 Bd. du 11 Novembre 1918, F-69616, Villeurbanne, France.Fax: 33 472431768; Tel: 33 472431777; E-mail: bourgeat@lcpp.cpe.fr 55 b Laboratoire de Chimie et de Sécurité des Nano Matériaux, DTNM/LITEN/CEA Grenoble, 17 rue des Martyrs, 38054 Grenoble cedex 9, France. E-mail: wartenbergnicolas@hotmail.fr c Current address: CEA LITEN, National Institute of Solar Energy INES, Solar Technologies Department, Thermal Systems Laboratory, 73377 Le

60

Bourget-du-Lac, France. E-mail: olivier.raccurt@cea.fr d Laboratoire de Reconnaissance Ionique et Chimie de Coordination, Service de Chimie Inorganique et Biologique (UMR E-3 CEA/UJF), CEA-Grenoble, INAC, 17 rue des Martyrs, 38054 Grenoble cedex 9, France.daniel.imbert@cea.fr; marinella.mazzanti@cea.fr 65 † Electronic Supplementary Information (ESI) available: [lifetime of Eu

highly luminescent complexes reported in the literature are ionic [31][32][33][34][35], this opens a wide range of possibility for the design of new luminescent nanoparticles. The europium-based latex nanoparticles show bright luminescence with high quantum yields independently of the amount of lanthanide complex