Vittorio Luca

Sartori

Hélène Waeselynck

Jérémie Guiochet

Pairwise Testing Revisited for Structured Data With Constraints

Keywords: pairwise testing, combinatorial testing, software testing, multiplicity, structured data model, test case generation

Pairwise testing (PT) exercises the interactions of pairs of input parameters. The approach is classically defined for a flat set of parameters, the number of which is fixed. Such a definition does not fit well with applications that process structured data like XML and JSON documents. This paper revisits the PT concepts to accommodate hierarchical data structures. The choices and pairs are created by considering the multiplicity of data instances, their access paths and common ancestors. The revised PT approach is implemented on top of on a recent data generation tool, TAF. TAF mixes random sampling and constraint solving to produce diverse data from XML-based models. Our PT implementation interacts with TAF by inserting pair coverage constraints into the models. It monitors overall coverage progress by XPath queries on the data returned by TAF. The approach is demonstrated for two data models: a 3D scene for an agricultural robot, and a population of taxpayers for a tax management system.

I. INTRODUCTION

Any software, service, or system, defines an input space that cannot be exhaustively explored. Combinatorial testing [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF] is a widespread approach to select test cases in spaces characterized by a set of parameters. The domains of the parameters are partitioned into classes of values, forming the choices for each parameter. Combinatorial testing then covers tuples of choices coming from different parameters, in order to exercise their interaction. Empirical studies have shown that most of the interaction bugs involve the combination of a few parameters. Hence, a widely used combinatorial testing strategy is pairwise testing (PT), where the tuples are simply pairs (checking 2-way interactions).

The PT algorithms classically consider a flat set of parameters, the number of which is fixed. Such a definition does not fit well with applications that process structured data like XML and JSON documents. The input space consists of data elements of various types, embedded into other elements with multiplicity. This cannot easily be brought back to a flat set of interacting parameters. For example, let us assume that an XML input describes a population of person elements, having some age and hobby attributes. The structure and multiplicity cannot be ignored, since the interactions (age, hobby) may be covered in the context of one person instance, or of different ones. Moreover, there are various population sizes to cover, and various possible shapes of persons (e.g., a person may or not have children). To further complicate things, the shape and numerical content of the data may have to satisfy semantic constraints. For instance, too young persons cannot have children.

Our work revisits the PT concepts to accommodate hierarchical data structures with constraints. The contributions are the following:

• We formalize the PT problem for input data trees labeled by element names. The definitions of choices and pairs consider the multiplicity of elements, their access paths and common ancestors. The coverage checks are expressed by XPath queries on the data trees. To the best of our knowledge, this is the first PT formalization attempt in the context of rich inputs like XML documents. • We demonstrate an implementation of the formalization on top of a recent tool, TAF [START_REF] Robert | TAF: a tool for diverse and constrained test case generation[END_REF]. TAF mixes random sampling and constraint solving to generate instances of XML-based data models. We propose two PT algorithms that leverage this tool: 1) unguided, where TAF freely produces data instances and we monitor coverage progress, and 2) guided, where we insert pair coverage constraints into the data models to drive TAF. We also study greedy variants of the algorithms, seeking to cover the greatest number of new pairs at each iteration. • The algorithms are applied to two examples of data models with constraints: a 3D scene for an agricultural robot, and a population of taxpayers for a tax management system. Section II discusses related work. Section III presents the formalization of the PT problem, by successively revisiting the concepts of test parameters, choices and pairs. Section IV introduces the implementation on top of TAF, and Section V gives the experimental results for the two case studies. Section VI concludes the paper with future directions II. RELATED WORK Combinatorial testing (CT) uses a set of parameters to build the test suite, which will contain combinations of choices partitioning these parameters [START_REF] Kuhn | Introduction to Combinatorial Testing[END_REF]. The CT algorithms generate mathematical objects called covering arrays, which represent test suites at an abstract level. The abstract test cases of the suite, represented by the choices they cover, must then be concretized to come up with real test cases.

There are various techniques to build a covering array [START_REF] Kuhn | Chapter one -combinatorial testing: Theory and practice[END_REF]: algebraic techniques, greedy algorithms, heuristic search, and constraint satisfaction. Greedy algorithms can work onerow-at-a-time, like AETG [START_REF] Cohen | The automatic efficient test generator (AETG) system[END_REF], or horizontally and vertically expanding the solution, like IPOG [START_REF] Lei | IPOG: A general strategy for t-way software testing[END_REF]. Some CT tools support (propositional) constraints, like ACTS [START_REF] Yu | ACTS: A combinatorial test generation tool[END_REF] or PICT [START_REF]Pict microsoft github[END_REF].

The most difficult aspect in the application of CT is the modeling of the input domain, to come up with an adequate abstraction in terms of parameters and choices. One of the popular methods to help in the modeling task is the Classification Tree Method [START_REF] Grochtmann | Classification trees for partition testing[END_REF] (CTM). CTM provides a structured approach to identify and refine the important characteristics of a system. Note that having a tree model does not mean that the test cases themselves have a tree structure. This is just a convenient abstraction to organize characteristics down to parameters and choices. The tree must be flattened to obtain a set of parameters with their choices, so that CT tools can be used [START_REF] Sandin | Enhanced classification tree method for modeling pairwise testing[END_REF]. If the tree has constraints (e.g., a constraint on the presence of related nodes), the flattening algorithm must take care that the node-level constraints are translated into parameter-level ones [START_REF] Kitamura | Combinatorial testing for tree-structured test models with constraints[END_REF].

Some authors have studied the application of CT for cases where the data is inherently structured, like ontologies or XML documents. Klück et al. propose an algorithm to flatten ontologies [START_REF] Klueck | Using ontologies for test suites generation for automated and autonomous driving functions[END_REF], so that they can be fed into a CT tool. The flattening manages the inheritance and composition relations, but does not consider other types of dependencies, like the ones introduced by semantic constraints. Multiplicity is managed by having a different variable for each possible instance (hence m variables if the multiplicity is bounded by m), with a special choice epsilon (ϵ) indicating that this instance is absent and has no value. This processing of multiplicity can only accommodate a small m. Borazjani et al. [START_REF] Borazjany | An input space modeling methodology for combinatorial testing[END_REF] address input models that can have the structure of graphs and apply CT to XML data. Rather than flattening the structure, they propose a compositional approach with unit and integration steps. During integration, the covering arrays from the unit steps are merged to form larger arrays. The compositional building of covering arrays has been further formalized by Kampel et al. [START_REF] Kampel | Combinatorial methods for modelling composed software systems[END_REF]. The formalization does not address multiplicity, and the whole approach assumes that the unit models are independent. Constraints relating them could make the CT problem non-compositional.

In contrast to the flattening or compositional approaches, we do not attempt to bring back the test generation problem to a problem (or set of problems) that falls in the scope of CT tools. Rather, we feel free to depart from the classical framework. It allows us to provide a formalization fully tailored to models with structure, a high degree of multiplicity, and constraints relating arbitrary elements. We then demonstrate the feasibility of an implementation. To accommodate constraints, it directly generates concrete test data from the model with the help of a powerful solver (e.g., an SMT solver).

Our formalization establishes a bridge between CT and a large body of work on structured data like XML documents. As a theoretical foundation for such documents, related work has studied tree data models, their specification and queries.

The specification uses schema languages, such as DTD, W3C XML Schema, and RELAX NG. They have different expressive powers to define structural shapes [START_REF] Murata | Taxonomy XML schema languages using formal language theory[END_REF]. RELAX NG has the full power of regular tree grammars, which define tree languages that can be recognized by tree automata. XSD is less expressive, restricted to a subset called single-type tree grammars, and DTD is even less expressive. In our work, we consider single-type tree models that do not contain recursive definitions. The querying of trees has yielded the development of languages like XPath [START_REF]XML Path Language (XPath)[END_REF], which we conveniently use for checking the coverage provided by the generated data.

III. PAIRWISE TESTING WITH MULTIPLICITY AND

STRUCTURE

This section formalizes pairwise testing from structured data models. It introduces a number of definitions and examples, ended by the symbol ♢.

A. Data models under consideration

This paper uses the running example of an agricultural robot named Oz [START_REF] Robert | TAF: a tool for diverse and constrained test case generation[END_REF]. The robot has to perform weeding missions in crop fields. The UML class diagram in Figure 1 specifies test cases for a simulation platform that creates virtual crop fields. A test case is composed of a mission (tuned by a set of parameters), a terrain with its heightmap, and a field containing multiple rows of vegetables. OCL constraints (not shown) further specify the shape and content of a test case.

This example illustrates the kind of test data that we address: hierarchical data structures with multiplicity. The data instances can be modeled as unranked labeled trees, i.e., trees in which nodes can have an arbitrary number of children and are labeled over an alphabet Σ (e.g., Σ = {"F ield ′′ , "Row ′′ , "length ′′ , . . . }). Leaf nodes carry a value, e.g., a row length of 15.0 meters. Values are from basic types such as integers, floating point numbers, strings, and Booleans. Let U be the universe of all such values. We provide below a formal definition for data instance trees (I-trees, for short).

Definition 1 (Data instance tree (I-tree)). A data instance over an alphabet Σ and universe U can be defined as a finite tree structure T Σ,U = (N, Leaf, Comp, λ, V al) where:

• N is the set of nodes, also called the tree domain.

Classically, we define N as a finite, prefix-closed subset of N * (the sequences of natural numbers). Intuitively, the sequences encode the position in the tree. The root node is the empty sequence ϵ, its first child is 0, its second one is 1, and 1 • 2 • 0 is a grand-grand child. Since the sequences are prefix-closed, if n • i ∈ N then n ∈ N . We further require that there is no gap in the numbering: if n • i ∈ N , then n • j ∈ N for all j < i. • Leaf and Comp form a partition of N . Leaf contains all the nodes n such that n•0 / ∈ N , while Comp contains the other nodes. The root is composite: ϵ ∈ Comp.

• λ : N → Σ is the node labeling function.

• V al : Leaf → U is the value function of leaf nodes. ♢ Query languages for data instance trees (e.g., XPath) refer to the notion of access path, which we introduce below.

Definition 2 (Access path). The access path of a node in a Σ-labeled tree is a sequence of labels recursively defined as follows:

• path(ϵ) = λ(ϵ), i.e., the access path to the root is its label.

• path(n•i) = path(n)•λ(n•i), i.e.
, the label of a non-root node is appended to the access path of its parent. ♢ Note that several nodes may have the same access path. In XPath queries, the access paths would be written with the '/' separator, and a query like /T est case/F ield/Row would return the set of all nodes having this access path. Note also that the definition of I-trees does not distinguish element attributes from atomic elements. They may be distinguished by adopting the convention that attribute labels start by the character '@', like in the XPath query /T est case/F ield/Row/@length.

A data model M like the class diagram in Figure 1 restricts the form of the I-trees which are valid test cases. Examples of invalid I-trees would have zero or multiple field nodes under the root (there must be one), or a row length with the value "Hello World!" (must be a numerical value). The trees must also satisfy OCL constraints, not visible in Figure 1. Likewise, XML schemas (DTD, XSD, Relax-NG) or JSON schemas specify permissible structures and values. They can be further constrained, e.g., by schematron rules based on XPath [START_REF] Siegel | Schematron: A language for validating XML[END_REF]. All these modeling notations allow for validation against M : given a candidate I-tree, it is decidable whether the tree is a valid instance of M . We note L(M ) the set of I-trees accepted by M . It corresponds to the valid test input domain. If M involves constraints, the existence of any valid I-tree may not be decidable. As a special case, the existence of any valid tree satisfying a test coverage requirement may not be decidable. Hence, our formalization of pairwise testing cannot exclude the production of infeasible pairs. But pair coverage analysis should be possible thanks to validation procedures.

We leave open which modeling notations to use, but assume that the expression of M can be split into two parts: some structural declarations on the one hand, and constraints on the other hand. E.g., M is a hierarchical class diagram plus OCL constraints, or an XML schema plus schematron rules. We note M dcl the model without the constraints. Ignoring the constraints yields more valid trees, hence L(M dcl ) ⊇ L(M ). The structural notation used for M dcl usually has limited expressiveness. For instance, regular tree grammars are the common foundation of all XML schema languages [START_REF] Murata | Taxonomy XML schema languages using formal language theory[END_REF]. We further require that M dcl possesses the single-type tree property: in the context of an element, the subelements with the same label must be declared having the same type. E.g., a crop field may contain multiple row instances, but there is a single Row class defining them all. As a result, the access path of an I-tree node (e.g., /T est case/F ield/Row) suffices to determine an expected type (e.g., the unique Row definition in this context). We finally require that M dcl does not contain recursive definitions: their consideration is delayed to future work. Definition 3 recaps our requirements on the data model.

Definition 3 (Data model over Σ and D). Let Σ be an alphabet, U a universe of values, and D a set of value domains in P(U). Our work considers data models M over Σ and D, composed of a structural declaration part M dcl and a set of constraints C such that:

• M dcl specifies a single-type tree language over Σ.

• M dcl does not contain recursive definitions.

• For each domain d ∈ D mentioned in M dcl , it is decidable whether any candidate value u ∈ U is in d. • For each constraint c ∈ C, it is decidable whether any candidate I-tree T Σ,U satisfies c. ♢

B. Test parameters revisited

In combinatorial testing, test parameters are first identified, then their value domains are partitioned into choices, and finally the choices of the various parameters are combined. We need to define which parameters should be considered in the data models.

Informally, we will consider all elements declared having a basic type as parameters, i.e., all atomic elements and attributes. For example, a row length is a test parameter. Moreover, we account for the multiplicity of elements: the number of rows is also a parameter. The test coverage will then require I-trees with various sizes and contents.

We extract the parameters from M by processing its structural declaration part M dcl . M dcl may have a design pattern where some reusable definitions are factorized (e.g., inherited classes in UML, global complexT ype definitions in XSD). The processing has first to expand all the references to reusable definitions, yielding nested element declarations. In this "Russian doll" design pattern, the structure of the model mirrors the one of the data instances, which is convenient for our purposes. We then have a second processing step, which extracts information from the "Russian doll". In the content definition of elements, we only keep the information needed for the identification of test parameters: which subelements may appear under which element, with which possible multiplicity, and with which value domain (for atomic elements). It yields a test data specification tree (S-tree). An S-tree is very much like an I-tree, but leaf nodes carry value domains rather than values and we add a multiplicity meta-attribute to all nodes. Definition 4 introduces the structure of an S-tree. Definition 5 provides its relation with M dcl , giving correctness requirements for the S-tree extraction.

Definition 4 (Structure of a test data specification (S-tree)). An S-tree over alphabet Σ and universe of domains D is a structure T Σ,D = (N, Leaf, Comp, λ, T ype, µ) where:

• N , Leaf , Comp and λ are the same as in Definition 1.

Note that the nodes of the S-tree have access paths using Definition 2. • T ype : Leaf → D is the function assigning value domains to leaf nodes. m ∈ µ(n.i) for some non-root node n.i of T Σ,D , if and only if there exists an IT ∈ L(M dcl ) where a node has the same access path as n and exactly m children labeled λ(n.i). ♢

For our running example, where M dcl is the class diagram shown in Figure 1, the extraction of an S-tree is straightforward. There is no inheritance relation to expand, and the notation directly gives the multiplicity of the composition relations. In other notations like XML schemas, the structural constructs may involve regular expressions. For example, M dcl could define an element containing subelements A, B, C with the following pattern: A 2 B + BC * . The S-tree extraction would have to interpret the regex to retrieve the correct multiplicity sets, i.e. {0, 2} for A, {1} for B and N for C.

We derive the set of test parameters from the S-tree nodes having a variable multiplicity or carrying values (leaf nodes). Note that the root cannot yield any parameter: it is not a leaf and its multiplicity is always 1. We encode a parameter by a quadruplet. The first three components uniquely identify the parameter, while the fourth one gives its value domain. The identifying triplet consists of 1) a Boolean value indicating the parameter category (true for multiplicity parameter or f alse for content of a leaf node), 2) its access path split into the parent path (context) and 3) the name of the element of interest. For example, the row multiplicity parameter has the id triplet (true, T est case.F ield, Row) and the value domain N 1 . This is formalized in Definition 6.

Definition 6 (Set of Test parameters from an S-tree). Let T Σ,D = (N, Leaf, Comp, λ, T ype, µ) be an S-tree. The set P ARAM ⊆ B × Σ + × Σ × D is the one built as follows.

• For each non-root node n.i ∈ N such that card(µ(n.i))

> 1, create a parameter (true, path(n), λ(n.i), µ(n.i)).

• For each leaf node n.i ∈ Leaf , create a parameter (f alse, path(n), λ(n.i), T ype(n.i)). ♢

C. Choices revisited

The value domains of parameters are now partitioned into choices. For example, the row multiplicity domain is split into three choices: a small number of rows (say, < 5), a medium one (from 5 to 50) and a large one (> 50). Since we want the coverage of choices to be checkable, we require their definition to explicitly embed a check. The check is a single-variable predicate, written with the usual Boolean, relational and arithmetic operators, and possibly other operators (e.g., on strings). We assume that the choice predicates demonstrably partition the value domain d of the parameter. A choice is then encoded like a parameter, but with a predicate replacing the value domain (e.g., x < 5 replaces N 1 ). Definition 7 (Set of Choices). Let P ARAM ⊆ B×Σ + ×Σ× D be a set of parameters. Given any parameter p ∈ P ARAM , let P RED x (p) be the set of choice predicates proposed for partitioning its value domain. The set CHOICE ⊆ B×Σ + × Σ × p P RED x (p) is the one built as follows:

• for each parameter p = (b, ctx, label, d), for each predicate pr ∈ P RED x (p), create the choice (b, ctx, label, P RED x (p)). ♢

Due to the multiplicity of elements, the coverage of choices may have different meanings. Let us assume that we have a choice for small row lengths (say, ≤ 20.0m). Is the choice covered when all rows have a small length, or does the existence of one small row suffice? This work adopts the existential interpretation, which seems more natural to us.

How to check whether an I-tree covers a choice depends on the used notation. Many query languages are based on XPath, so we use this notation as an example. Example 1 shows how to build an existential XPath query from a choice.

Example 1 (XPath query for checking choice coverage). Let c = (b, ctx, label, pr x ) be a choice. We assume that the ctx expression has the '/' separator between labels. If b = true (multiplicity parameter), we produce a string str = "count(" . label . ")", where count() is the Xpath function for counting nodes. Otherwise str = label. Then, we substitute str for x in pr x : pr = pr x [str/x]. And finally we build the query: "count( " . ctx . "[" . pr. "] ) > 0". For the choice of a small number of rows, this yields: starting from c = (true, T est case/F ield, Row, x < 5), the string str = "count(Row)" is produced, then pr = "count(Row) < 5", and finally "count(/Test case/Field[count(Row) < 5]) > 0". This query searches for the set of field nodes that have a small number of row children, and then checks that the node set is not empty. Similarly, the choice of a small row length gives: "count(/Test case/Field/Row[@length ≤ 20.0]) > 0" ♢

D. Pairs revisited

This paper focuses on pairwise testing, i.e. on the coverage of pairs of choices. For example, a pair requires both a small row length and a high roughness of the terrain, or a small row length combined with a small number of rows. In the usual applications of pairwise testing, the pairs combine all possible choices from any two different test parameters. Then, given an input data, the coverage of the pair (c 1 , c 2 ) conjoins two independent checks: for the coverage of c 1 and the one of c 2 .

The creation and checking of pairs are more complicated in our case, because the parameters are embedded into a data structure with multiplicity. First, the existence of self pairs becomes possible, which come from the same parameter. E.g., multiple rows are possible, hence multiple row lengths occur and we may create pairs testing their interaction. Second, it is less clear how to check for pair coverage. Assume we have a pair (small row length, low vegetable density). Do we mean that the same row has to cover both choices, or can each choice occur independently? The question can be reformulated in terms of the lowest (i.e., farthest from the root) common ancestor of the two covering nodes. In an I-tree, a length node and a vegetable density node can have two types of lowest common ancestor (LCA): F ield or Row. If we admit any of them for the coverage of the pair, the checks of the choices can be independent. If we admit only Row, then the checks are no longer independent: we must search for a row that covers both choices at the same time. Another example is the self pair of two small row lengths. The LCA must be a F ield (since a row has a single length). Again, the checks cannot be independent: we need a single check, asking for at least two small rows in a field.

From what precedes, self pairs and LCAs are new aspects that justify revisiting the notion of pairs. We provide below a generic formalization of pairwise strategies in terms of two meta-parameters: Self , determining whether or not to create self pairs, and Select() determining how to select the permitted LCAs of a pair. We will later give examples of LCA selection functions and XPath coverage checks.

The formalization first introduces the notion of divergence point in the context of a choice (or more generally a parameter), where the context is the access path of its parent (cf. Definition 7). Divergence points are where multiplicity may cause several branches in the I-tree. For example, a row length has the context T est case/F ield/Row, and T est case/F ield is a divergence point. Under a field node, there may be branches for the first row instance, the second one, and so on. A row multiplicity parameter also has the context T est case/F ield/Row, but there is no divergence point. Indeed, there is a single number of rows in the field. Definition 8 formalizes this. Note how the recursive definition of the set of divergence points (sdiv, updated as sdiv ′ ) considers multiplicity parameters (Boolean b is true) like parameters that have at most one instance.

Definition 8 (Divergence point). Let c be a choice (b c , ctx c , label c , pred c ) created from an S-tree T = (N, Leaf, Comp, λ, T ype, µ). Let node : Σ + → N be the function returning the node of T having a given access path. The functions exists since access paths are unique in the S-tree (Definition 5). Let div : B × Σ + × Σ × P(Σ + ) → P(Σ + ) be the recursive function defined as follows: div(b, ctx, label, sdiv) = sdiv ′ if node(ctx) is the root node ϵ, div(f alse, ctx ′ , label ′ , sdiv ′ ) otherwise, Where:

• sdiv ′ = sdiv if b = true or µ(node(ctx.label) ⊆ {0, 1}, • sdiv ′ = sdiv ∪ {ctx} otherwise, • ctx ′ ∈ Σ + and label ′ ∈ Σ are such that ctx =ctx ′ .label ′ . The set of divergence points of c is DIV (c) = div(b c , ctx c , label c , ∅).
Since it contains prefixes of ctx c , the "is-a-prefix-of" string relation, noted ≺, is a strict total order on DIV (c). ♢ Definition 9 uses divergence points to determine the set of possible LCAs for a pair of choices. This is the set from which Select() will extract a subset of allowed LCAs. Basically, the longest common prefix of the contexts of the choices is a possible LCA, and so are all common divergence points. For example, the row length and row vegetable density can be under the same row element (prefix), or under the same field (divergence point) but not the same row. We must however take care of the special case of self pairs. For them, it would be meaningless to consider the common prefix if this is not a divergence point. For example, there is nothing such as a common row parent for two row length choices: each row has a single length. Definition 9 explicitly handles this.

Definition 9 (Set of possible LCAs for a pair of choices). Let c

1 = (b 1 , ctx 1 , label 1 , pred 1 ) and c 2 = (b 2 , ctx 2 , label 2 , pred 2 ) be two choices. Let isSelf (c 1 , c 2 ) be the predicate: b 1 = b 2 ∧ ctx 1 = ctx 2 ∧ label 1 = label 2 .
Let pref ix be the longest common prefix of ctx 1 and ctx 2 . The set of possible LCAs for the pair is the following one:

LCAS(c 1 , c 2 ) = DIV (c 1 ) if isSelf (c 1 , c 2 ), (DIV (c 1 ) ∩ DIV (c 2 )) ∪ {pref ix} otherwise.
Like the sets of divergence points, the sets of possible LCAs are totally ordered by ≺. Each non-empty set has a well-defined least element, and a greatest one. ♢

We are now equipped to define a pairwise strategy in a very generic way. It creates pairs of choices, which may contain self pairs or not, and associates a set of permissible LCAs to them. In Definition 10, we encode this as the production of quadruplets of the form (ch1, ch2, set of possible LCAs, set of permitted LCAs). In this way, the encoding not only makes it explicit which LCAs are desired, but also which LCAs do not count for coverage (retrieved by making the set difference).

Definition 10 (Pairwise strategy with meta-parameters Self and Select()). Let Self ∈ B be the Boolean parameter of the strategy, where a value true indicates that self pairs are to be created, and f alse that they are not. Let Select : P(Σ + ) → P(Σ + ) be the selection function of the strategy. Its input must be a non-empty, totally-ordered set of access paths, from which it extracts a non-empty subset. Let CHOICE be the set of choices according to Definition 7. The strategy creates a set P AIRS, where each element of the set is in CHOICE × CHOICE × P(Σ + ) × P(Σ + ). The set is the one obtained from the following procedure:

• For each c 1 ∈ CHOICE, for each c 2 ∈ CHOICE such that ¬isSelf (c 1 , c 2 ), create the pair (c 1 , c 2 , LCAS(c 1 , c 2 ), Select(LCAS(c 1 , c 2 ))). • If Self = true, for each c ∈ CHOICE such that LCAS(c, c) ̸ = ∅, create the pair (c, c, LCAS(c, c), Select(LCAS(c, c))). ♢
Let us now discuss examples of Select() functions:

• Don't care -all possible LCAs are permitted. Select() is the identity function. • Closest-possible -Select(S) returns the greatest element of S. E.g., a row length and vegetable density must be covered in the context of a same row. Intuitively, the strategy considers that the closer the nodes are in an I-tree, the stronger their semantic interaction is. • Close-enough -The strategy relaxes the closest possible constraint, but still considers a boundary LCA for closeness acceptance. For example, the possible LCAs are lca 1 ≺ lca 2 ≺ lca 3 , and the strategy only retains the LCAs starting from lca 2 . For a boundary lca b , Select(S) returns {lca ∈ S | lca b ⪯ lca}. Intuitively, the strategy is useful when constraints make the closest-possible strategy infeasible for some pairs. • Arbitrary LCA -The strategy selects one arbitrary LCA for each pair of choices. E.g., for some reason, we want the small row length and high vegetable density to occur in different rows, hence the LCA must be a field. Depending on the strategy, the coverage checks can become quite complex. Examples 2 to 4 illustrate cases of increasing difficulty using XPath queries.

Example 2 (XPath queries for checking coverage when no LCA is removed). We discuss cases where Select() retains the entire set of possible LCAs, either because it is the don't care strategy or because the set is a singleton. For a non-self pair, each choice can be independently checked, where the XPaths queries are like in Example 1.

For self pairs such that the choices are actually different (same parameter, but different choice predicates to check), two independent checks still do the job. But for self-pairs with the same predicate (e.g., a small row length in both cases), it would not work to repeat the same existential check twice. Rather, we count the number of occurrences of the choice, and checks whether it is > 1.

♢

(suf 1 /l 1 ) ] [ pred 2 (suf 2 /l 2 ) ] ) > 0.
This check requires the coverage of the pair in the context of lca b and its descendants. ♢ Example 4 (XPath queries for an arbitrary LCA). We discuss the case where the selected LCA is not the greatest one (otherwise, see Example 3). The XPath checks become convoluted. We provide hints on how to do, with the help of an example: a pair (small row length, low vegetable density). The possible LCAs are: T est case/F ield ≺ T est case/F ield/Row. The target LCA is the field. The key is to split the common context according to the first node after the target (here, Row). We would like to find at least two different rows, such as one has a small length and the other has a low vegetable density. Unfortunately, XPath is not convenient for this. We may proceed by three checks performed in parallel. If any one succeeds, then the pair is covered. Each check may involve several queries. The three checks are: 1) Count the number of rows that cover both choices. If the number is > 1, we're done. 2) Search for a row that covers the first choice but not the second one. Search for a row that covers the second choice. If both searches succeeds, we're done. 3) Same as 2), by permuting the first and second choices. ♢

E. Adding constraints

The construction of the pairs is from an S-tree, which ignores semantic constraints and even some structural ones (e.g., the regular expressions in the content models of XML schemas). Some of these constraints may involve disjunctive cases, like a content model having to match the pattern A 2 B +BC * , or a logical constraint of the form pred 1 ∨pred 2 . We leave open whether such cases should generate new parameters and choices, like predicate parameters with truth value choices. The risk is to get many pairs that are either redundant with existing pairs or infeasible. The improvement in the coverage may not be worth the combinatorial growth. In the case studies we performed, we opted for a compromise: we automatically generate predicate parameters and choices from the constraints, but do not combine them with the others. They yield single choice coverage requirements. Other strategies could have been possible.

Once the list of pairs and single choices is ready, we need a means to produce the covering test cases. The next sections present a solution using a generation tool that mixes random sampling and constraint solving. It allows us to demonstrate an implementation of our (so far, theoretical) PT framework.

IV. INTEGRATION WITH A TEST CASE GENERATOR (TAF)

TAF (Test Automation Framework) [START_REF] Robert | TAF: a tool for diverse and constrained test case generation[END_REF] is a recent tool for generating data structures with constraints. It is opensource [START_REF]Testing Automation Framework[END_REF]. The data models must be written in a tool-specific language based on XML. We briefly present this language that fits well into our formalization assumptions. Next, we describe how to implement pairwise testing on top of TAF.

A. TAF input models

The TAF inputs models are called templates. Listing 1 gives a snippet of the template for Oz, our running example. It contains four types of XML elements: Root, Node (for composite elements, like a row), Parameter (for attributes, like a row length), and Constraint. The parameters can be of type Boolean, string, real, and integer. All value domains must be bounded. Numerical parameters (real and integer) are declared with a min-max range of values. For instance, the row length (Line 6) is between 10.0 and 100.0m. Strings are actually enumerated types, like the set {"cabbage", "leeks"} for the vegetable parameter (Line 3). The parameters and nodes have a nb instances (number of instances) meta-attribute for multiplicity. It has the integer type. A field element (Line 2) has a single instance. The multiplicity of rows (Line 4) is in the range min=1, max=100.

If one ignores constraints, the structure of declarations is simple. It satisfies the single-type tree property. It specifies bounded data instance trees, both horizontally (bounded multiplicity) and vertically (no recursive definition). The language only allows for a Russian doll design pattern (nested declarations, no reusable definitions). The extraction of an S-Tree from a TAF template is direct.

Constraints add expressiveness. For example, the constraint in Line 16 relates the number of rows to a mission parameter. The logical operators have a function notation, e.g., IMPLIES (-,-). This is to facilitate the communication with the backend solver, Z3 [START_REF] De Moura | Z3: an efficient SMT solver[END_REF]. The navigation operator is '\', as in the path expression " ..\field\row.nb instances". Constraints may have universal or existential quantifiers. In Lines 10-12, the quantified variable i allows the expression of a universal property of rows: consecutive rows must have the same length +/-10%. Other constraints not shown in the snippet concern the content pattern of a field (for n rows, it must have n + 1 weed areas and n -1 inner widths).

TAF outputs an XML file for each generated data instance. It gives us an I-tree, to which we apply XPath coverage queries. 1 <root name="test_case"> 2 <node name="field" nb_instances="1"> 3 <parameter name="vegetable" type="string" values= "cabbage;leek"/> 4 <node name="row" min="1" max="100"> 5 <parameter name="length" type="real" 6 min="10.0" max="100.0"/> <node name="mission" nb_instances="1"> <parameter name="is_first_track_outer" type=" boolean"/> <constraint name="first_track" expressions=" IMPLIES(..\field\row.nb_instances EQ 1, .\ is_first_track_outer EQ True)"/>

B. Implementation of pairwise testing on top of TAF

We have developed a parser of TAF templates, which extracts an S-tree and calculates the choices and pairs. For demonstration purposes, the choices are created by a systematic procedure. The definition range of a numerical parameter is uniformly split into three subranges, low, medium, and high. For a number of instances, we consider specifically the value zero if it is in the range, and split the rest of the domain into low, medium, and high values. Enumerated types yield one choice per defined value. The pairs are then formed according to the closest-possible LCA selection strategy with self-pairs.

We also add single choices extracted from the constraints. The constraint expressions are parsed and put in a disjunctive normal form. Then, each expression OR(cond 1 , ..., cond n ) yield n single choices such that cond i (i = 1, .., n) is true. We do not try to combine the truth values of the conditions (e.g., cond 1 is true and the others false), nor do we combine these choices with the parameter choices to form pairs. If the constraint has quantifiers, we interpret all of them as if they were existential. We produce an existential Xpath check for each choice.

We consider several algorithms for the generation of covering test cases.

The first one is unguided. Since TAF has a randomized generation procedure, it produces different valid cases each time it is called. Then, the simplest algorithm is to ask TAF to produce a test case, apply coverage checks, and retain the test case if it covers new elements (new pairs or single choices). The procedure is repeated until all elements are covered or a maximal number of iterations is reached. The second one is guided. Since TAF handles constraints, we can insert covering constraints into the template. For instance, Listing 2 shows the constraint for the pair (small row length, small vegetable density), automatically translated into the TAF language. The iterative building of a test suite is then as follows: select a pair (or single choice) remaining to cover, insert its coverage constraint into the original template and ask TAF to return a test case. If TAF fails to return one, the pair is put into a list of likely infeasible pairs, made available for manual inspection. If it returns one, then the overall coverage is monitored and all newly covered elements are removed from the To-do list. The procedure is iterated until the list is empty. The resulting test suite covers all the elements that TAF could satisfy.

Both the guided and unguided generation can be extended by a greedy procedure that tries to minimize the size of the test suite. It consists in requesting k test cases at each iteration, and retaining the one that covers the greatest number of new elements. This optimization is loosely inspired by the AETG algorithm [START_REF] Cohen | The automatic efficient test generator (AETG) system[END_REF], which also tries different test cases. In the unguided generation, the k cases are freely produced by TAF, with the hope that many new pairs will occur in at least one of them. In the guided generation, the k test cases all cover a target pair, plus hopefully many other ones. The guided-greedy procedure is shown in Figure 2. Note that k = 1 corresponds to the original algorithm without optimization.

V. CASE STUDIES

To demonstrate the approach, two case studies are used. Both have their template available in the TAF repository [START_REF]Testing Automation Framework[END_REF]. The first one, Oz, is the running example of this paper. It comes from an industrial case study, where an agricultural robot was tested in simulation [START_REF] Robert | The virtual lands of oz: testing an agribot in simulation[END_REF]. The second one, Taxpayer, describes the data for an income tax management application [START_REF] Soltana | Practical Constraint Solving for Generating System Test Data[END_REF]. The UML class diagram of Oz can be seen in Figure 1, and the one of Taxpayer in Figure 3. The Oz template has 7 composite elements, 15 parameters, and 5 constraints. TaxPayer has 9 composite elements, 12 parameters and 7 constraints. Since TAF only supports relations, the inheritance is flattened in the template, and associations are modeled by unidirectional compositions.

A. Experiments applying the PT algorithms

Table I shows the number of pairs and single choices automatically created from each template. A preliminary run of the guided generation algorithm allowed us to identify the infeasible pairs, which were confirmed by a manual analysis.

For each case study, we performed experiments to compare the coverage and test suite size supplied by the various generation algorithms. The code is available in a replication package [START_REF]Replication package for pairwise testing revisited for structured data with constraints[END_REF].

The unguided generation allows TAF a max number of 100 iterations to get a covering suite. It is combined with a greedy optimization with k trials, where k = 1 (TAF baseline), 3, 5, 7. The guided approach, inserting covering constraints into the templates, is also combined with a greedy optimization. In total there are 16 experiments: 8 for each case study-4 unguided and 4 guided-, with "k" of values 1, 3, 5, 7. Each experiment was repeated 50 times (so 50 runs). In each run, the timeout given to TAF to generate a valid test case was 120s in the case of Oz and 200s for Taxpayer, decided empirically. To keep the overall time of the 50 runs tractable, we filtered out the infeasible pairs. Hence, the unsatisfied pairs at the end of a run are all satisfiable.

Tables II and III show the results we obtained. The first four columns, labeled TAF, correspond to the unguided approach where TAF freely produces test cases. The next four correspond to the guided generation. The tables display the supplied coverage, the mean generation time of a run, the mean number of unsatisfied pairs (if any) and the mean size of the produced test suite (i.e., the number of tests cases it contains).

The next sections analyze the coverage and test suite size in greater detail.

B. Coverage

A first observation is that TAF produces sufficiently diverse data for all PT algorithms to be effective. The coverage rate is nearly 100% in each case. However, for Oz, the unguided approaches with k=1,3,5,7 has a mean number of unsatisfied pairs equal to 33.1, 27.0, 20.1, 18.9, compared to the guided approaches having none. It justifies the use of the guided approach to ensure coverage.

For Taxpayer, all the approaches quickly achieve 100% coverage. For Oz, it is interesting to analyze the evolution of the coverage at each iteration of the generation. Figure 4 displays the cumulative coverage at each iteration. The shown experiments are the guided approach with k=1 and k=7, and the unguided approach with k=1 (TAF baseline). The guided approach with k=7 has the steepest growth in coverage and reaches 100% coverage with fewer iterations than the other approaches. The guided k=1 approach also arrives at 100% coverage, but needs more iterations. The unguided approach has the slowest growth. It also has the highest variability, as shown by the shaded areas in Figure 4 that visualize the interquartile ranges.

C. Test suite size

Minimizing the test suite size is important if the tests have to run every time new code is pushed.

The effect of k in the reduction of the test suite size can be seen in Figures 5 and6, where the first four boxplots are . Oz: comparison of the cumulative coverage with the unguided TAF approach with k=1 (TAF baseline) and the guided approach with k=1 and k=7. The shaded areas represent the interquartile range. The y-axis is limited to the upper part of the diagram for better readability. The guided approach median lines are prolonged to make the comparison visually easier. We do not show k=3 and k=5 for the guided approach, because their diagrams would fit between the diagrams of k=1 and k=7.

for the unguided approach (TAF) with k=1,3,5,7, and the four next for the guided one. Note that it may seem that, for Oz, the unguided approach found the minimum of all sizes [START_REF] Murata | Taxonomy XML schema languages using formal language theory[END_REF]. However, let us recall that the coverage is not 100% in that case. Actually, the minimal size of all found covering suites is 15.

Inside each family of approaches (unguided or guided), the higher the k, the lower the median size tends to be, and also the lower the minimal size found over 50 runs, and the lower the maximal size. The shift toward smaller values also surfaces by looking at mean values. From Tables II and III, the tendency seems clear: inside each family of approaches, the mean test suite size always decreases when k increases.

We applied a Mann-Whitney U test to determine the statistical significance of the improvement in the mean test size. The first four rows of Table IV shows the p-values when comparing two guided approaches with different values of k . E.g., the first row compares the mean test sizes supplied by the guided approaches for k=1 and 3. The last two rows compares guided and unguided approaches for the same k. For example, "k=1, TAF1" means the guided approach with k=1 versus the unguided one (TAF) with k=1. The comparison is done for TaxPayer only, because it would not make sense to compare test sizes for different coverage results. In each row, we also provide the Common-Language Effect Sizes (CLES).

The p-values are almost always inferior to 0.05, meaning that it is highly unlikely that the effect is caused by chance. There is just one case in which the p-value is greater than 0.05: Taxpayer when comparing k=5 and k=7 (p-value=0.12). The Common-Language Effect Sizes (CLES) show that there are no small effect sizes (>0.2), there are some medium effect sizes (>0.5), and the others are all large effect sizes (>0.8). The lowest effect size (CLES=0.5596) is related to Taxpayer when comparing k=5 and k=7, which has also the highest p-value. The first row of the table shows that, for the guided approach, the move from the no-optimization case (k=1) to a limited optimization (with only k=3 trials) already has a significant beneficial impact. We conclude that, for the case studies, the guided generation with few optimization trials is a practical approach to produce covering test suites of small sizes.

VI. CONCLUSION

This paper has presented a formalization of pairwise testing in the case of structured data models with constraints and multiplicity. We identified two major differences with the usual "flat" case. First, self pairs become possible, where the parameter of an element occurs in different instances of this element, and we want to test the interactions between these instances. Second, the tested pairs will not be the same depending on the lowest common ancestor (LCA) of the covering element instances. We proposed several strategies to select the LCAs that will count for coverage. We also provided an XPath formalization of the pair coverage analysis.

As a proof-of-concept demonstration, we implemented pairwise testing on top of a data generation tool, TAF. TAF has an input language based on XML and accommodates constraints. We automatically created the pairs to cover and their coverage checks, according to our formalization. We then proposed several generation strategies to build covering test suites with the help of TAF. We applied them to two case studies from real world applications, and successfully produced test suites with 100% coverage of the feasible pairs. A practical approach is to insert the covering constraints into the data models. This guided approach helps to cover pairs that are hard to cover with the native randomized generation of TAF. Moreover, the size of the resulting test suite can be significantly reduced by combining the guided approach with a simple greedy optimization: a few candidate test cases are generated to cover a pair, from which we retain the one providing the highest overall coverage progress.

Future directions include conceptual extensions to the framework as well as alternative implementations. An extension would be to account for recursive definitions, with new parameters related to the depth of the recursion, and new self pairs between elements at a different depth. The generalization to n-way testing may also be considered, but would most probably be limited to don't care LCA selection strategies. Otherwise, the LCA analysis and coverage checks could become cumbersome. Alternative implementations of the generation would add techniques that have been found useful in classical PT, like optimizing the order of the pairs (for the guided approach) or starting from pre-existing seed tests.

Fig. 1 .

 1 Fig. 1. UML class diagram of the Oz robot case study and running example of the paper.

  • µ : N → P(N) is the function assigning a set of multiplicity values to each node. The multiplicity set of the root ϵ must be the singleton {1}. ♢ Definition 5 (Correctness of the S-tree wrt M dcl ). Let M be a data model over Σ and D, and let M dcl be its structural declaration part, defining the tree language L(M dcl ) ⊇ L(M ). The extraction of an S-tree T Σ,D = (N, Leaf, Comp, λ, T ype, µ) from M dcl must satisfy the following properties: • Preservation of the single-type property of M dcl -Two different nodes in T Σ,D cannot have the same access path. • Access paths are untouched -An access path p exists in T Σ,D if and only if there exists an I-tree IT ∈ L(M dcl ) in which a node has this access path. • Value domains are untouched -A value v exists, such that v ∈ T ype(n) for some node n of T Σ,D , if and only if there exists an IT ∈ L(M dcl ) where v appears under the access path of n. • Multiplicity is untouched -A value m exists, such that

7 <

 7 interval" types="forall"11 expressions="row[i]\length INFEQ 1.1 * row[i -1]\length;row[i]\length SUPEQ 0.9 * row[i-1]\length" 12 quantifiers="i" ranges="[1, row.nb_instances -1]"/> 13 14

17 </node> 18 <

 1718 .../> 19 </root> Listing 1. Snippet of the TAF XML template for the robot Oz

  expressions="AND(.\field[a]\row[b]\length SUPEQ 10.0, .\ field[a]\row[b]\length INFEQ 40.0, .\field[a]\row[b]\ vegetable_density SUPEQ 0, .\field[a]\row[b]\ vegetable_density INFEQ 3)" ranges="[0, .\field.nb_instances-1]; [0, .\field[a]\row. nb_instances-1]" /> Listing 2. A coverage constraint added under the root of the Oz template. Note how the path prefixes with common indexes a, b enforce the desired LCA (here, a row).

Fig. 2 .

 2 Fig. 2. Flowchart of the guided generation with k trials.

Fig. 3 .

 3 Fig. 3. UML class diagram of the Taxpayer management application case study.

Fig. 4

 4 Fig.4. Oz: comparison of the cumulative coverage with the unguided TAF approach with k=1 (TAF baseline) and the guided approach with k=1 and k=7. The shaded areas represent the interquartile range. The y-axis is limited to the upper part of the diagram for better readability. The guided approach median lines are prolonged to make the comparison visually easier. We do not show k=3 and k=5 for the guided approach, because their diagrams would fit between the diagrams of k=1 and k=7.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Oz: Boxplots with TAF unguided with k=1,3,5,7 and guided with k=1,3,5,7.

  Example 3 (XPath queries when distant LCAs are removed). The closest-possible and close-enough strategies only remove LCAs that are lower (according to ≺) than a boundary LCA. The boundary may be the greatest LCA (closest possible strategy), or another LCA. We consider pairs for which at least one lower LCA is removed (otherwise, see Example 2). Let ctx 1 and ctx 2 , be the contexts of the choices of the pair, and l 1 and l 2 their labels. The boundary LCA is a prefix of both contexts, so we have: ctx 1 = lca b .suf 1 and ctx 2 = lca b .suf 2 , where the suffixes can be empty. The individual queries for the choice coverage have the general

form: count ( / ctx [ predicate(label) ] ) > 0.

We can manipulate the choice queries to get a single check: count ( / lca b [ pred 1

TABLE IV STATISTICAL

 IV ANALYSIS OF THE MEAN TEST SUITE SIZES. NOTATION K=I MEANS GUIDED, WITH I EQUAL TO THE K UNDER ANALYSIS. TAFI MEANS UNGUIDED WITH K=I.

		Oz		Taxpayer
		P-value	CLES	P-value	CLES
	k=1, k=3	6.98E-16	0.96	3.93E-11	0.8674
	k=3, k=5	0.000005	0.7488	0.010377	0.6212
	k=5, k=7	0.001993	0.6564	0.119922	0.5596
	k=1, k=7	2.45E-18	0.9966	3.89E-15	0.9392
	k=1, TAF1	N/A	N/A	0.000045	0.7246
	k=7, TAF7	N/A	N/A	2.86E-17	0.9762

<constraint name="sentence_286" types="exist;exist"

ACKNOWLEDGMENT

This project has received funding from the European Union's EU Framework Programme for Research and Innovation Horizon 2020 under Grant Agreement No. 812.788.


P Fernandez

O Durieux

B Saint-Jean

Sabatier

Camille Schwab
email: camille.schwab@aphp.fr

J B Escudie

V Savoldelli

C Fernandez

P Durieux

O Saint-Jean

B Sabatier

IATROGENIC RISK FACTORS ASSOCIATED WITH HOSPITAL READMISSION OF ELDERLY PATIENTS: A MATCHED CASE CONTROL STUDY USING A CLINICAL DATA WAREHOUSE -Iatrogenic risk factors for readmission of elderly: a case control study

Keywords: aged, patient readmission, risk factors, data warehouse

Iatrogenic risk factors associated with hospital readmission of elderly patients: A matched case-control study using a clinical data warehouse

We included patients aged 75 and over. Cases consisted of patients readmitted to the emergency department within 30 days of initial discharge. Controls did not return to the emergency department within 30 days. Cases and controls were matched on sex and age because they are known as readmissions risk factors.

After comparison, of the mean or percentage between cases and controls for each variable, we conducted a conditional logistic regression.

Results: The risk factors identified were an emergency admission at the index hospitalization, returning home after discharge, a history of unplanned readmissions, and prescription of nervous system drugs. Otherwise, 11.4% of the readmissions were DRRs, of which 30% were caused by an overdose of antihypertensive. The number of drugs at readmission was higher and potentially inappropriate medications were more widely prescribed for DRRs than for readmissions for other reasons.

What is new and conclusion: In this matched case-control retrospective study, after controlling for gender and age, we identified the typical profile of elderly patients at risk of readmission. These patients had an unplanned admission at the index hospitalization and prescribed nervous system drugs at discharge from the index admission, they have a history of unplanned readmission within 30 days and return home after discharge.

WHAT IS KNOWN

Hospital readmission within 30 days of patient discharge has become a standard to judge the quality of hospitalizations. Among these readmissions, unscheduled hospitalizations directly related to the index hospital stay are considered to be avoidable [START_REF]Comment réduire le risque de réhospitalisations évitables des personnes âgées ?[END_REF] .

The elderly are defined as people over 75 years of age or those over 65 with comorbidities 2 . They show a progressive loss of reserve and adaptive capacity and an overall deterioration in health that can result in disability or loss of independence 3 . Hospitalizations may be particularly deleterious for these patients, making them even more dependent [START_REF] Sager | Functional outcomes of acute medical illness and hospitalization in older persons[END_REF] . It has been estimated that 14% of elderly are at risk for readmission, of which 23% are avoidable [START_REF]Comment réduire le risque de réhospitalisations évitables des personnes âgées ?[END_REF] .

Readmission results from decompensated comorbidities, resulting in overcrowded emergency departments (EDs) and increased hospital expenses [START_REF] Lanièce | Incidence and main factors associated with early unplanned hospital readmission among French medical inpatients aged 75 and over admitted through emergency units[END_REF] . Since 2013, the French Ministry of Health has warned health professionals about the high risk of readmission for the elderly and has made the reduction of readmissions a priority 1 . Various interventions have been tested to reduce readmission rates: discharge planning protocols, comprehensive geriatric assessments, discharge support arrangements, and education [START_REF] Hansen | Interventions to reduce 30-day rehospitalization: a systematic review[END_REF] . However, the "Haute Autorité de Santé" (HAS) advocates identifying frail patients who need these interventions. Indeed, the identification of such patients is essential, as it is not "necessary nor efficient to intervene for every patient" 1 .

Prescribed drug-related readmissions (DRRs) represent between 4.2% 7 and 24.3% 8 of readmissions. They may be due to adverse reactions of drugs prescribed at discharge, suboptimal therapy, or medication nonadherence [START_REF] Dormann | Readmissions and adverse drug reactions in internal medicine: the economic impact[END_REF] . Some drugs are known to be generally associated with poor health outcomes and are listed as potentially inappropriate medications (PIMs) [START_REF] Laroche | Médicaments potentiellement inappropriés aux personnes âgées : intérêt d'une liste adaptée à la pratique médicale française[END_REF][START_REF] Pohl-Dernick | Potentially inappropriate medication in the elderly in Germany: an economic appraisal of the PRISCUS list[END_REF] . The American Geriatrics Society has assembled the latest PIMs list: The American Geriatrics Society Beers Criteria for Potentially Inappropriate Medication Use in Older Adults 12 . However, the results of studies on PIMs and readmissions are conflicting. Hagstrom et al. showed that the prescription of PIMS had no effect on the readmission rate [START_REF] Hagstrom | Association Between Potentially Inappropriate Medication Use in Elderly Adults and Hospital-Related Outcomes[END_REF] , whereas Pavon et al. showed that the prescription of benzodiazepines, which are listed as PIMs, was associated with a higher readmission risk (OR = 1.23) [START_REF] Pavon | Identifying risk of readmission in hospitalized elderly adults through inpatient medication exposure[END_REF] .

The DRRs should be mostly avoidable, with appropriate intervention on the management of the elderly at risk of readmission. It may be possible to identify elderly patients at risk of readmission, particularly DRRs, and implement to reduce avoidable readmissions.

We identified patients at risk of readmission using a clinical data warehouse (CDW). The CDW allows the performance of complex queries while achieving reliable and high-quality results.

OBJECTIVE

The aim of this study was to identify iatrogenic risk factors of readmission.

The secondary objective was to evaluate the rate of DRR among all readmissions and compare it to the rate of readmissions for other reasons.

METHODS

We conducted a retrospective, matched, case-control study to identify non-demographic risk factors of avoidable readmission, specifically DRR.

 Data source:

The hospital is a teaching hospital of 795 beds with 24 clinical departments (15 medical wards and nine surgical units). The clinical information system has been associated with a CDW since 2009, making it possible to reuse healthcare data and clinical research.

All medical records and prescriptions are computerized. The data needed for the study were stored in the CDW and extracted using Oracle® software, or manually by reading the electronic medical record.

An ethics committee approved the study protocol (CERHUPO, CDW_2015_0023).

 Study participants:

Patients were at least 75 years old and admitted to the university hospital from October 1 st , 2014 to September 30 th , 2015.

Cases consisted of elderly patients who experienced an unscheduled readmission within 30 days after the index admission. Readmissions had to originate at the ED to be considered unscheduled. All patients who were readmitted without a prior ED visit were excluded. Readmission included simple ED visits. Controls consisted of elderly patients who had not had any unscheduled readmissions during the 30 days after the index admission. All controls that died during the index hospitalization were excluded.

Cases and controls were randomly matched.

 Study variables:

We identified readmission risk factors by literature review (Table 1). For each risk factor, we listed the category, the odds ratio (or hazard ratio or relative risk), the reference, and the variables to be used in our study. Many readmission risk factors appeared to be already known in the literature, but few were related to the medications prescribed at discharge of the index hospitalization. Age and sex are known to be readmission risk factors [START_REF] Preyde | Evidence-based risk factors for adverse health outcomes in older patients after discharge home and assessment tools: a systematic review[END_REF][START_REF] García-Pérez | Risk factors for hospital readmissions in elderly patients: a systematic review[END_REF][START_REF] Mathew | Risk factors for hospital re-presentation among older adults following fragility fractures: a systematic review and meta-analysis[END_REF] . Thus, controls were matched to cases (1:1), based on their sex and index age (within 5 years), to control for these two risk factors, to have similar populations between cases and controls and to keep patient characteristics, admission characteristics and therapeutic characteristics in the multivariate analysis.

The study variables were:

-Patient characteristics: Marital status, level of social support (living alone or accompanied, nursing home residents or elderly living at home), socioprofessional category, comorbidity (Charlson index), presence of depression, dependence in activities of daily living, and malnutrition. -Admission characteristics: Programmed admission or emergency admission, medical or surgical pattern, primary diagnosis and history of readmission (any hospitalizations followed by an emergency readmission within 30 days describe in the medical record) and length of stay. -Therapeutic characteristics: Each drug listed on the discharge prescriptions was classified according to the ATC (Anatomical Therapeutic Chemical) Classification, whether it was a PIM, and the number of drugs. [START_REF] Lanièce | Incidence and main factors associated with early unplanned hospital readmission among French medical inpatients aged 75 and over admitted through emergency units[END_REF][START_REF] Pavon | Identifying risk of readmission in hospitalized elderly adults through inpatient medication exposure[END_REF][18][START_REF] Marcantonio | Factors associated with unplanned hospital readmission among patients 65 years of age and older in a Medicare managed care plan[END_REF][START_REF] Morrissey | Influence of Drugs, Demographics and Medical History on Hospital Readmission of Elderly Patients: A Predictive Model[END_REF][START_REF] Alassaad | A tool for prediction of risk of rehospitalisation and mortality in the hospitalised elderly: secondary analysis of clinical trial data[END_REF][START_REF] Zanocchi | Early re-hospitalization of elderly people discharged from a geriatric ward[END_REF][START_REF] Kwok | Hospital readmission among older medical patients in Hong Kong[END_REF][START_REF] Franchi | Risk factors for hospital readmission of elderly patients[END_REF][START_REF] Davies | Emergency re-admissions to hospital due to adverse drug reactions within 1 year of the index admission[END_REF][START_REF] Bogaisky | Early hospital readmission of nursing home residents and community-dwelling elderly adults discharged from the geriatrics service of an urban teaching hospital: patterns and risk factors[END_REF]  Study outcomes:

The primary outcome of the study was to identify iatrogenic risk factors of readmission for elderly patients to identify those who require interventions.

The secondary outcomes were to evaluate the rate of DRR among all readmissions and to describe the drug-related problems.

 Statistical analysis:

All statistical analyses were conducted using R software (R Version 3.3.3; 2017-03-06).

Univariate analysis:

We compared the mean (quantitative variables) or percentage (qualitative variables) between cases and controls for each variable to select those for the logistic regression. We used t-tests for the quantitative variables and chi-square tests compare the percentages of qualitative variables.

The selected variables for the multivariate analysis were those that were significant following comparison (p < 0.05) or those with a p-value < 0.10 for risk factors largely described in the literature.

Multivariate analysis:

After generating a diagram of eigenvalues and a performing a factor analysis, we conducted a principal component analysis to determine the correlations between selected variables. Knowledge of the correlations allowed removing variables from the logistic regression. We retained the variable with the smallest p-value when two were correlated. The variables were removed from the logistic regression until most had a significant p-value (<0.05) and a low Akaike criterion (AIC).

Secondary objective:

The secondary outcome was to compare DRR with readmissions for other reasons. We used t-tests and chi-square tests for quantitative and qualitative variables, respectively.

RESULTS

From September 1, 2014 to October 31, 2015, 6,574 elderly patients meeting our criteria were admitted to the hospital. Within 30 days after discharge of the index hospitalization, 422 patients (6.4%) were readmitted, whereas 6,096 were not. These 422 patients were randomly matched with 422 controls among the 6,096 patients, creating 422 case-control pairs. Among the 422 unplanned readmissions, 137 (32.5%) were ED visits, without hospital admission.

 Bivariate analysis:

Bivariate analysis allowed the comparison of cases and controls to select the variables used for multivariate analysis (Table 2).

The patient characteristics of cases significantly differed from controls for the Charlson index and depression, as indicated in the medical record (p = 0.00681 and 0.0281, respectively). The place of residence had a p-value < 0.1 (p = 0.053). There were no statistical differences between the case and control groups for all other variables (marital status, residence, social support, depression, feeding, continence, hygiene, and mobility).

The socio-professional category and nutritional status were removed from statistical analysis because of too much missing data (41% and 59%, respectively).

We then compared the index admission characteristics between cases and controls. By univariate analysis, an unplanned index admission, a medical index admission, a return to home at discharge, and a history of avoidable readmissions were significantly higher for the case than control group (p = 7.43x10 -5 , 0.00313, 0.00346, and 6.79x10 -5 , respectively). There were no statistical differences between the case and control groups for all other variables (length of stay and primary diagnosis).

Finally, we compared the treatment characteristics at discharge of the index hospitalization. Cases significantly differed from controls for the number of drugs (p = 0.00230), polypharmacy (p = 0.0131), PIM (p = 0.00637), systemic hormonal preparations (p = 0.0377) and nervous system drugs (p =0.000556) (ATC Classes H and N). The prescription of drugs of the alimentary tract and metabolism had p-value < 0.1 (p = 0.0672). There was no statistical difference between the case and control groups for the other ATC classes.

 Multivariate analysis:

Selected variables for the multivariate logistic regression analysis were social support (living alone or not), the residence (private home or retirement home), presence of depression or dementia, Charlson index, type of index admission (planned or emergency vs medical or surgical), history of readmission, number of prescribed drugs at discharge of the index hospitalization and polypharmacy, number of PIMs, number of drugs in classes A, H, and N (metabolism, hormonal preparations, and nervous system drugs), and type of discharge (return home or transfer to another health institution). These variables were statistically significant by univariate analysis or highly described in the literature. Following factor analysis and principal component analysis, we observed that planned or unplanned admission and medical or surgical admission were correlated, as well as the number of prescribed drugs and polypharmacy. These correlations helped to construct the logistic regression model (Table 3).

The starting logistic regression model (with all selected variables) had an AIC of 547.813. The conditional logistic regression (Table 3) had an AIC of 537.916. In this model, an index admission in emergency, a return home at discharge, a history of readmissions, and the prescription of nervous system drugs were still significantly associated with the risk of readmission after adjustment for the Charlson index. Thus, an emergency admission at the index hospitalization increased the readmission risk (OR = 1.96, 95%CI = 1.41-2.71).

Returning at home after discharge and having history of unplanned readmissions also increased the risk of readmission (OR = 1.84 and 1.66, respectively), as well as the prescription of nervous system drugs (OR = 1.81, 95% IC: 1.30-2.52). Among all the 844 subjects, 43 (5.1%) who had an index admission in emergency, a return to home at discharge, a history of readmissions, and the prescription of nervous system drugs were readmitted. On the contrary, 8 (0.95%) patients had none of these characteristics.

 Secondary objective:

In this study, 11.4% of the readmissions were DRRs, of which 30% were caused by an overdose of antihypertensive drugs, leading to falls and hypotension (6.4% and 8.5% of the reasons for DRR, respectively).

The number of drugs at readmission was higher and PIMs were more widely prescribed for DRRs than for readmissions for other reasons (p = 6.688x10 -5 , and 0.00837, respectively).

WHAT IS NEW AND DISCUSSION

In our study, after controlling for gender and age, patients at risk of readmission had an unplanned admission at the index hospitalization and prescribed nervous system drugs at discharge from the index admission. Furthermore, they had a history of unplanned readmission at 30 days and returned home after discharge.

Unplanned admissions were mostly related to a medical pattern. This correlation can be explained by comorbidities that lead to decompensation of a chronic condition and thus unplanned admission. Moreover, comorbidities [START_REF] García-Pérez | Risk factors for hospital readmissions in elderly patients: a systematic review[END_REF][START_REF] Franchi | Risk factors for hospital readmission of elderly patients[END_REF] and medical admissions [START_REF] Davies | Emergency re-admissions to hospital due to adverse drug reactions within 1 year of the index admission[END_REF] are known factors of readmission. Thus, these two readmission risk factors show that an unplanned admission is also a risk factor for readmission. Indeed, in 2012, Van Walraven et al. had already found that unplanned admission was a readmission risk factor, as it is one of the variables of the clinical LACE index [START_REF] Van Walraven | Derivation and validation of an index to predict early death or unplanned readmission after discharge from hospital to the community[END_REF] .

We also found that the prescription of nervous system drugs at discharge, including antidepressants, increases readmission risk. Although patient and admission characteristics are well known readmission risk factors, therapeutic risk factors have only recently been studied. The link between psychotropic drugs and readmission has been previously shown [START_REF] Pavon | Identifying risk of readmission in hospitalized elderly adults through inpatient medication exposure[END_REF] , especially for DRR [START_REF] Chayé | Hospital readmission induced by adverse drug reaction: a pilot study in a post-emergency unit of a French university hospital[END_REF] . Indeed, psychotropic drugs (class ATC N) are highly responsible for adverse drug reactions [START_REF] Jolivot | A systematic review of adult admissions to ICUs related to adverse drug events[END_REF] .

A history of admissions or ED visits is known to be a risk factor for readmissions. Indeed, in a systematic review, Garcia-Perez et al. found that patients admitted in the previous three or six months had an increased risk of readmission [START_REF] García-Pérez | Risk factors for hospital readmissions in elderly patients: a systematic review[END_REF] . Furthermore, these variables are part of two existing clinical scores for predicting readmission risk: previous hospital admission for the HOSPITAL score [START_REF] Donzé | Potentially avoidable 30-day hospital readmissions in medical patients: derivation and validation of a prediction model[END_REF] and ED use in the previous 30 days or hospitalization in the previous 90 days for the Triage Risk Screening Tool (TRST) [START_REF] Meldon | A brief risk-stratification tool to predict repeat emergency department visits and hospitalizations in older patients discharged from the emergency department[END_REF] . However, we demonstrate here that patients with a history of unplanned readmission within 30 days, i.e., any hospitalization followed by an unplanned readmission within 30 days, were more likely to be readmitted. This may be because readmitted patients have chronic comorbidities at high risk of decompensation: a comorbidity that decompensates once can certainly decompensate again.

The secondary outcome of this study was to describe DRRs in cases. Patients with a DRR had more PIM's prescribed than those readmitted for reasons other than an adverse drug reaction. To our knowledge, no previous study has investigated the impact of PIMs on DRRs. However, JM. Pavon et al. [START_REF] Pavon | Identifying risk of readmission in hospitalized elderly adults through inpatient medication exposure[END_REF] and H. Chayé et al. [START_REF] Chayé | Hospital readmission induced by adverse drug reaction: a pilot study in a post-emergency unit of a French university hospital[END_REF] showed a link between psychotropic and cardiological drugs and readmission (including DRR).

This study had several limitations and strengths. The main limitation was that we did not consider readmission to another facility as the electronic health records were limited to readmissions in the same hospital. There was also a misclassification bias: we did not consider unscheduled readmissions which didn't originate from an ED visit, because the distinction from scheduled admissions was not possible using the CDW. Thus, we may have underestimated the readmission rate, since controls might have been readmitted to another health institution or died after the index hospitalization. A matched case-control study design prevents this limitation. Finally, only readmissions annotated as iatrogenic were considered for be DRRs, which may have led to an underestimation of the DRR rate.

The strength of this study is its focus on iatrogenic risk factors. These risk factors are modifiable by actions taken at discharge, unlike patient and admissions characteristics.

In conclusion, this study identified several readmission risk factors: emergency admission at the index hospitalization, the prescription of nervous system drugs, and a history of unplanned readmissions. We will be able to use these factors to identify patients at risk of readmission during their hospitalization, and offer them a program at discharge to reduce this risk, such as a comprehensive chronic treatment review with education on the selfmanagement of the disease and transition-of-care communication. Indeed, thanks to the computerized medical records, patients presenting at least one of the identified risk factors will be selected to have the discharge program. A clinical score including the identifying risk factors will also be researched. Multimodal geriatric discharge planning intervention has already shown its efficacity [START_REF] Legrain | A new multimodal geriatric discharge-planning intervention to prevent emergency visits and rehospitalizations of older adults: the optimization of medication in AGEd multicenter randomized controlled trial[END_REF] . Identifying patients at risk will help to select those for whom such planning intervention would be efficient.

Activity of daily living

Becoming dependent for feeding (ADL-Katz scale) OR = 1.9 [1.2 -2.9] Lanièce et al. [START_REF] Lanièce | Incidence and main factors associated with early unplanned hospital readmission among French medical inpatients aged 75 and over admitted through emergency units[END_REF] Dependence for feeding, continence, mobility, and hygiene

OR = Odd-ratio, HR = Hazard Ratio, RR = Relative Risk

Discharge

Elderly adults discharged to nursing homes after a hospitalization had a 41% higher chance of 30-day hospital readmission than those discharged to the community.

Bogaisky et al. [START_REF] Bogaisky | Early hospital readmission of nursing home residents and community-dwelling elderly adults discharged from the geriatrics service of an urban teaching hospital: patterns and risk factors[END_REF] Return home or transfer

History of readmission

Previous hospital admission (

Table 1 : Risk Factors Described in The Literature

 1

		Risk factors	OR (or HR or RR) [95%CI]	References	Variables selected for our study
			Patient characteristics
	Sex Age	Women Age > 80 years	OR = -1.539 OR = 1.8 [1.02 -3.2]	Fethke et al. 18 Marcantonio et al. 19	Matching for sex and age
	Marital status	Widow Single	OR = 1.745 OR = 2.195 [0.979 -4.919]	Fethke et al. 18 Morrissey et al. 20	Single = divorced, single or widow Maried = maried or living together
	Residence	Living in a home for the elderly Living in a convalescent home	HR = 1.617 [1.176 -2.224] RR = 1.9 [1.1 -3.3]	Alassaad et al. 21 Zanocchi et al. 22	Private home or Home for the elderly
	Social support	Poor familial support according to patient	RR = 2.7 [1.2 -6.1]	Kwok et al. 23	Living alone or not
	Education
	level	Medium-High education level	RR = 1.8 [1.1 -3.6]	Zanocchi et al. 22	Socio-professional category
		Pulmonary disease Cancer	HR = 1.834 [1.296 -2.595] HR = 1.659 [1.198 -2.297]	Alassaad et al. 21
	Comorbidities	CIRS Score Liver disease	OR = 2.24 [1.25 -4.03] OR = 2.32 [ 1.42 -3.77]	Franchi et al. 24	Charlson Index, depression, prescription of antidepressant
		Cardio-vascular disease	OR = 1.48 [1.0 -2.17]		drugs
		Charlson index > 2	RR = 1.8 [1.1-3.6]	Zanocchi et al. 22
		Antidepressant prescription	HR = 0.573 [0.410 -0.799]	Alassaad et al. 21

Table 1 : Risk Factors Described in The Literature -Continued Risk factors OR (or HR or RR) [95%CI] Reference Variables of our study Admission characteristics

 1

	Type of admission	78.4% of medical readmitted patients vs 65.8% medical non-readmitted patients (p < 0.0001)	Davis et al. 25	Planned admission or emergency, medical, or surgical admission
	Length of stay (LOS)	LOS (days)	RR = 3.2 [1.5-7.3]	Zanocchi et al. 22	LOS (days)
	Primary diagnosis		See comorbidities		Primary diagnosis

Table 2 : Univariate analysis

 2

	Variables	Cases	Controls	p-value
		N = 422	N = 422
	Patient Characteristics
	Marital status: n (%)			0.534
	Single	230 (56.1%) 210 (53.7%)
	Residence: n (%)			0.053 •
	Private home	382 (90.5%) 397 (94.1%)
	Home for elderly	40 (9.5%)	25 (5.9%)
	Social support: n (%)			0.174
	Living alone	159 (39.2%) 164 (44%)
	Living with someone	247 (60.8%) 25 (5.9%)
	Comorbidities: n (%)
	History of myocardial infarction: n	39 (9.2%)	35 (8.3%)	0.626
	(%)
	Congestive heart failure: n (%)	240 (56.9%) 22 (52.6%)	0.213
	Chronic arterial occlusive disease	49 (11.6%)	43 (10.2%)	0.508
	of the lower extremities: n (%)
	History of stroke: n (%)	36 (8.5%)	40 (9.5%)	0.631
	Dementia: n (%)	103 (24.4%) 77 (18.2%)	0.029
	Chronic pulmonary disease: n (%) 67 (15.9%)	69 (16.4%)	0.852
	Connective tissue diseases: n (%)	27 (6.4%)	26 (6.2%)	0.887
	Gastroduodenal ulcer: n (%)	42 (10%)	38 (9.0%)	0.638
	Diabetes: n (%)	72 (17.1%)	66 (15.6%)	0.577
	Kidney disease: n (%)	72 (17.1%)	58 (13.7%)	0.182
	Malignant disease: n (%)	160 (37.9%) 146 (34.6%) 0.316
	Charlson Index: m (sd)	6.82 (1.94)	6.45 (1.99)	0.00681**
	Depression (notified in medical record): n	51 (12.1%)	32 (7.6%)	0.0281*
	(%)
	Feeding: n (%)			0.818
	Dependent	23 (5.5%)	27 (6.4%)
	Partial dependence	92 (21.8%)	94 (22.3%)
	Independent	307 (72.7%) 301 (71.3%)
	Continence: n (%)	302 (71.6%) 311 (73.7%) 0.487
	Hygiene			0.571
	Dependent	63 (14.9%)	61 (14.5%)
	Partial dependence	178 (42.2%) 165 (39.1%)
	Independent	181 (49.9%) 196 (46.4%)
	Mobility: n (%)			0.568
	Bedridden	57 (13.5%)	60 (14.2%)
	Partial dependence	168 (39.8%) 153 (36.3%)
	Independent	197 (46.7%) 209 (49.5%)
	Index Admission Characteristics
	Admission planned or emergency: n (%)		7.43x10 -5 ***