Freddy Munoz

Benoit Baudry

Olivier Barais

A classification of invasive patterns in AOP

Keywords: Aspect-oriented programming, Classification system, Invasive AOP Pas de motclef

Aspect-Oriented Programming (AOP) improves modularity by encapsulating crosscutting concerns into aspects. Some mechanisms to compose aspects allow invasiveness as a mean to integrate concerns. Invasiveness means that AOP languages have unrestricted access to program properties. Such kind of languages are interesting because they allow performing complex operations and better introduce functionalities. In this report we present a classification of invasive patterns in AOP. This classification characterizes the aspects invasive behavior and allows developers to abstract about the aspect incidence over the program they crosscut.

Introduction

Aspect-oriented Programming (AOP) is a paradigm that enhances current approaches to modularizing software. AOP enables separation of concerns that crosscut the implementation of a system. This is done by encapsulating crosscutting concerns into single units called aspects. An aspect itself is composed of several units that realize the crosscutting behavior. Aspects also provide pointing elements that designate well defined points in the program execution or structure. These are the points where the program executes the crosscutting behavior. Different approaches to AOP have been proposed [START_REF] Kiczales | Aspect oriented programming[END_REF][START_REF] Mezini | Conquering aspects with caesar[END_REF][START_REF] Suvée | Jasco: an aspectoriented approach tailored for component based software development[END_REF][START_REF] Suvée | A symmetric and unified approach towards combining aspect-oriented and component-based software development[END_REF][START_REF] Pawlak | Spoon: annotation-driven program transformation -the aop case[END_REF][START_REF] Bockisch | Adapting virtual machine techniques for seamless aspect support[END_REF]. Each of these approaches provide a different mechanism to compose aspects with the base program. These composition mechanisms range from simple program augmentation to more complex operations such as behavior replacement.

Invasive composition mechanism allow developers to manipulate almost any structure and behavior of the base program. Invasive AOP approaches realize invasive composition mechanism. Invasiveness is the ability of invasive AOP to manipulate the program structures and behavior. Invasive AOP provides several strategies to manipulate the base program. These strategies range from less invasive such as the augmentation of a procedure execution to more invasive ones such as the replacement of a procedure execution.

This report presents a classification system for invasive AOP. This classification system focuses on the invasive behavior of aspects over the base program. We construct this classification system by studying the invasive structures of AspectJ [3], however, we think that it can be adapted to other invasive languages.

The reminder of this report is organized as follows. In section 2 we study the AspectJ structures in order to derive our classification of invasive AOP. In section 3 we introduce our classification of invasive aspects. In section 4 we discuss related work. Finally section 5 concludes.

Classifying Invasive AOP

Each programming paradigm promotes its own way to encapsulate concerns. For example, the object-oriented paradigm encapsulates concerns in classes, fields and methods. It also defines a protection level for each one of them. This ensures that properties will be accessed according to their permission.

Invasiveness breaks the encapsulation that each paradigm promotes and provides a mean to access protected properties. For example, aspects can access classes, methods and fields whatever their permission. Developers can fruitfully use invasiveness. For example, they can use it to check the preservation of system properties [START_REF] Wampler | Contract4J for design by contract in Java: Design patternlike protocols and aspect interfaces[END_REF]. However, developers can use invasiveness to invalidate some desirable system properties, intentionally or unintentionally.

The duality in the usage of invasiveness motivates us to propose a classification system for invasive AOP. Our classification system provides the following benefits.

It enables the characterization of aspects with precise invasive behavior (invasive pattern).

It enables developers to reason about aspects and discriminate when they could represent a risk to the base program.

We build the classification system by studying the invasive structures available in AspectJ. Once identified the different possibilities it provides, we proceed to derive our classification system.

Running example

To illustrate our characterization approach, in listing 1 we present the skeleton implementation of an ordered list class (MyArrayList). All the attributes in this list are private to the class. Elements added using the add method (line 8) are stores in the elements array (line 2). Elements are retrieved by using the get method (line 11). The specific position of an element in the elements array is obtained by using the indexOf method (line 12). An element is removed from the list by using the remove method (lines 13-14), this method removes an element by using its position or the original element. The first and last element in the list are retrieved by using the methods first and last (lines 15,16). All the elements in the list can be removed by using the clear method (line 9). Listing 2 presents the code of our example aspect. This aspect (MyAspect) realizes a set of advices an Inter-type declarations that affect in different ways the MyArrayList class. The declaration in line 3 introduces the parent interface Comparable into the MyArrayList class hierarchy. The inter-type in line 5 adds the method compareTo to the MyArrayList class. Analogously, the inter-type of line 7 adds the field maxSize. The advice in lines 9-12 execute a logging facility just before the execution of the add method. The advice in lines 14-19 print a message into the standard output before and after the execution of the add method. The advice in lines 21-24 replaces the execution of the first method and executes the last method instead. The advice in lines 26-32 executes the add method only when non null values are passed as parameters. The advice in INRIA lines 34-42 adds each element of a collection into the list. The advice in lines 44-48 replaces the parameter object (object to be inserted) by an string, then the string is inserted instead of the object. The advice in lines 48-52 reads the field current size and print it to the standard output. Finally, the advice in lines 54-57 decreases the value of currentSize by 1. In AspectJ, aspects are composed of advices, pointcuts, inter-type declarations and inter-type parent declarations. Advices are used to modify the program flow and write or read fields. An advice can be declared inside a privileged aspect, which means that it is enabled to ignore the object-oriented access policy. Inter-type declarations are used to introduce methods and fields into a target class. Inter-type parent declarations are declarations of inheritance that modify the class hierarchy.

public
public
AspectJ allows developers to implement various behaviors on advices. We summarize them by using the actions advices may perform in the following list. AspectJ allows developers to modify the program structure. We summarize the modifications developers can implement on aspects in the following list. It is worth to remark that these modifications are performed at the aspect level.

The aspect inserts new fields into a target class by using an inter-type declaration. (Listing 2, line 7)

The aspect inserts new methods into a target class by using an inter-type declaration. (Listing 2, line 5)

The aspect modifies the class hierarchy by using an inter-type parent declaration. (Listing 2, line 3) These list of interventions range from simple augmentation to more invasive ones like complete replacing the target method or write a protected field. We motivate our classification on these factual intervention we proceed to identify different invasive behavior that we call invasiveness patterns.

Classification System

We can identify three axes for our classification. The first corresponds to how developers can use advices to affect the program control flow. The second corresponds to how developers can use advices to affect the data flow, changing fields, methods parameters and returning values. The third corresponds to how developers can use aspects to modify the program structure.

Control Flow

Classifies advices according to the behavioral interaction between them and the methods it crosscuts.

Augmentation : After crosscutting, the body of the method is always executed.

The advice augments the behavior of the method it crosscuts with new behavior that does not interfere with the original behavior. The advices in Listing 2, lines 9-12, 14-19 realize the invasiveness pattern Augmentation.

Replacement : After crosscutting, the body of the method is never executed. The advice completely replaces the behavior of the method it crosscuts with new behavior. This kind of advices eliminate a part of the base code. The advice in Listing 2, lines 21-24 realizes the invasiveness pattern Replacement. The advice in lines 59-63 is an special case of Replacement, this because it executes the original behavior to later replace the obtained result.

Conditional replacement : After crosscutting, the body of the method is not always executed. The advice conditionally invokes the body of the method and potentially replaces its behavior with new behavior. Examples of this kind of advices are advices realizing transaction, access control, etc. Listing 2, lines 26-32 realizes the invasiveness pattern Conditional replacement.

Multiple : After crosscutting, the body of the method is executed more than once. The advice invokes two or more time the body of the method it crosscuts generating potentially new behavior. The advice in Listing 2, lines 34-40 realizes the invasiveness pattern Multiple.

Crossing : After crosscutting, the advice invokes the body of a method (or several methods) that it does not crosscut. The advice have a dependency to the class owning the invoked method(s). The advice in Listing 2, lines 9-12 realizes the invasiveness pattern Crossing.

Data Access

Classifies advices according to the access they perform to object fields and method arguments.

Write : After crosscutting, the advice writes an object field. This access breaks the protection declared for the field and can modify the behavior of the underlying computation. The advice in Listing 2, lines 54-57 realizes the invasiveness pattern Write.

Read : After crosscutting, the advice reads an object field. This access breaks the protection declared for the field and can potentially expose sensitive data. The advice in Listing 2, lines 48-52 realizes the invasiveness pattern Read.

Argument passing : After crosscutting, the advice modifies the arguments of the method it crosscuts and then invokes the body of the method. The body of the method always executes at least once. The advice in Listing 2, lines 42-46 realizes the invasiveness pattern Argument passing.

Structural

Classifies aspects according to the modification performed they perform to the existing structure of a class.

Hierarchy : The aspect modifies the declared class hierarchy. For example, the aspect adds a new parent interface to an existing one. An example of this is the declaration in Listing 2, line 3.

Field addition : The aspect adds new fields to an existing class declaration. These fields depending on their protection can be acceded by referencing an object instance of the affected class. An example of this is the declaration in Listing 2, line 7.

Operation addition : The aspect adds new methods to an exiting class declaration. These methods depending on their protection can be acceded by referencing an object instance of the affected class. An example of this is the declaration in Listing 2, line 5.

INRIA

The groups we have presented describe the aspect invasive behavior in different dimensions, and most of them are complementary. For example, an advice cannot perform data access without executing and therefore a Write advice can also realize and Augmentation advice. However, some classification categories are incompatible, Augmentation, Replacement and Conditional Replacement cannot co-exist in the same advice.

Note that this classification is still incomplete. It does not address cases like the exceptions raised by advices. However, it allows us to characterize the behavioral interaction between advices and methods, major structure modifications and data access.

Related work

In [START_REF] Rinard | A classification system and analysis for interactions in aspect-oriented programs[END_REF] categories of direct and indirect interactions between aspects and methods are identified. Direct interaction is whether an advice interferes with the execution of a method, whereas indirect is whether advices and methods may read/write the same fields. This classification is similar to ours, however, it addresses a different dimension. We identify invasiveness patterns instead of direct/indirect interactions.

Katz [START_REF] Katz | Diagnosis of harmful aspects using regression verification[END_REF] recognizes the fact that aspects can be harmful to the base code and the need of specification on aspect-oriented applications. Our approach agrees with his ideas and likewise we propose a mean to write such specifications. Furthermore, he describes three groups of advices according to their properties. Spectative aspects, which do not influence the underlying computation, Regulatory aspects, which change the control flow but do not affect existing fields, and Invasive aspects, which affect existing fields. This classification is similar to ours, however, our characterization of is more fine grained. The two first correspond to our behavioral classification and the last to our data access classification.

Clifton and Leavens propose Spectators and Assistants [START_REF] Clifton | Observers and assistants: A proposal for modular aspect-oriented reasoning[END_REF]. Spectators are advices that do not affect the control flow of the advised method and do not affect existing fields. Assistants can change the control flow of the advised method and affect existing fields. Spectator are similar to our classification category Augmentation and Read in the sense that they do not interfere with the mainline computation or write fields. All other classification categories are equivalent to Assistants. Nevertheless, we have achieved a more fine granularity level in our classification.

Conclusions and Future work

In this report we have presented a characterization of invasive behavior. Such a characterization is encoded as a classification of invasive aspect oriented programing. The component of this classification represent invasiveness patterns, i.e. the ways in which AOP can be invasive.

The characterization of invasive aspects allow developers to recognize and reason about the potential risks introduced by aspects into the base program. We think that this is the first step to a bigger specification framework that will make developers more confident in AOP. In future work we will explore the creation of an aspects -base program specification framework.

  The advice does not modify the behavior of the methods it crosscuts. (Listing 2, lines 9-12, 14-19)The advice replaces the behavior of the methods it crosscuts, the original methods are never invoked. (Listing 2, lines 21-24) The advice conditionally replaces the behavior of the methods it crosscuts. (Listing 2, lines 26-32) The advice replaces the behavior of the methods it crosscuts. It invokes two or more time the original method. (Listing 2, lines 34-40) INRIA The advice invokes a method declared outside its declaring aspect. (Listing 2, line 11) The advice changes the argument values of the methods it crosscuts. (Listing 2, lines 42-46) The advice replaces the result of the method execution. (Listing 2, lines 59-63 The advice reads or writes object fields values. (Listing 2, lines 50, 56)

RR n 6501

Contents


M Vidament

J L Larry

G Arnaud

M Magistrini

F Clement

Effect of stabling stallions with mares during the non-breeding season on semen collection behaviour, semen characteristics and testosterone plasma concentration

Effect of stabling stallions with mares during the non-breeding season on semen collection behaviour, semen characteristics and plasma testosterone concentrations

Marianne Vidament, J.L. Larry, Guillaume Arnaud, Michèle Magistrini, F.

Clement

To cite this version:

Marianne Vidament, J.L. Larry, Guillaume Arnaud, Michèle Magistrini, F. Clement. Effect of stabling stallions with mares during the non-breeding season on semen collection behaviour, semen characteristics and plasma testosterone concentrations. 9. International Symposium on Equine Reproduction, International Society of Equine Reproduction (ISER). INT., Aug 2006, Kerkrade, Netherlands. hal-

Introduction

There is growing evidence that reproductive physiology of stallions may be modified by social conditions. In free-running horses, the plasmatic testosterone level of harem stallions is higher than those of bachelor stallions [START_REF] Mcdonnell | Bachelor and harem stallion behavior and endocrinology[END_REF]. Housing stallions together in boxes without mares could resemble bachelor social condition [START_REF] Mcdonnell | Reproductive behavior of stallions and mares : comparison of free-running and domestic in-hand breeding[END_REF]. The aim of this study was to measure the effect of various types of domestic housing to reproduce harem and bachelor social conditions on specific reproductive parameters and semen collection behaviour.

Materials and methods

Twelve stallions (age in 2001: 5 + 1.3 years (sd)) were used in two experiments. Before each experiment, stallions were housed in groups without direct or indirect contact with females. Then half the stallions were housed with mares either pregnant (Experiment 1) or altrenogest-treated (Experiment 2) and half the stallions were housed singly in one barn without mares. The stallions were checked at 4 periods: prior to and 22-27, 57-62, 83-113 days after their stabling with the mares. The last two ejaculates of five daily collections ( obtained on a phantom in the presence of a castrated mare) were analyzed for total volume, and for concentration, total number, motility, % live spermatozoa and morphology of the spermatozoa. The width of the testicles was evaluated ultrasonographically. The latencies for erection, ejaculation and from first ejaculation to second erection (= refractory latency, 60 min if no 2 nd erection) were recorded. Plasma testosterone concentrations were measured 2 weeks before, during the first week after housing with the mares, weekly for 3 weeks, and every other week until the end of experiment.

Experiment 1.

From mid-September to mid-December 2001, six "Treated" stallions were housed in a Barn A, singly with one mare on each side according to the scheme: one mare, one stallion, one *This paper is part of the special issue entitled Proceedings of the Ninth International Symposium on Equine Reproduction, Guest Edited by Margaret J. Evans. 1 Corresponding author. Tel: +33 2 47 42 77 00 ; fax: +33 2 47 42 77 43. E-mail address: vidament@tours.inra.fr (M. Vidament).

Comment citer ce document : Vidament, M., Larry, J.L., Arnaud, G., Magistrini, M., Clément, F. ( 2006). Effect of stabling stallions with mares during the non-breeding season on semen collection behaviour, semen characteristics and plasma testosterone concentrations. In: Proceedings of the Ninth International Symposium on Equine Reproduction (p. 50-53). Animal Reproduction Science, 94 (1-2).

mare then an empty pen and again one mare, one stallion and one mare in the barn A. Each pen (3 x 5.8 m) had horizontal metallic pipes spaced 0.22 m apart separating neighbouring pens. This allowed visual, auditory and limited tactile (heads, legs) communication. Six "Control" stallions were housed singly in a barn B, separated from the barn A only by a very large door, left open.

Experiment 2.

From mid-October 2002 to mid-February 2003, six "Treated" stallions were housed with two mares into 100 m 2 pens (mini-harems) in two different barns (one barn with four harems, and one barn with two harems). Each mini-harem was next to another mini-harem, allowing visual, auditory and limited tactile communication through horizontal thick bars spaced 0.45 m apart. Six "Control" stallions were housed singly in another barn, with no contact at all with mares (neither visual nor vocal). At the end of the experiment (119 days), mares were removed and, five days later, Treated stallions were housed singly in another barn until end of march 2003 and sampled for testosterone measurement.

Results

In Experiment 1, Treated stallions remained quiet in their pens and took no interest in their neighbouring mares. None of the parameters measured in spermatozoa, blood or testis were significantly influenced either by treatment or by interaction of treatment x time (Fig. 1).

In Experiment 2, Treated stallions herded and actively guarded their two mares, running along the fence between the two harems. A global treatment effect and a treatment x time interaction were observed for gel volume, gel free volume, refractory latency (P<0.05) with a marked increase at 22 days in Treated stallions and a normalization at 113 days. Sperm concentration was similarly affected with a marked decrease at 22 days and at 57 days. None of the other parameters measured was significantly influenced by these two effects (Fig. 2). At 22 days, ejaculation latency was higher in Treated group (P<0.01).

Discussion

In this study, housing stallions next to mares or with mares has not increased testosterone concentrations, quantity and quality of spermatozoa, nor did it benefit semen collection behaviour. The type of mares (pregnant mares or altrenogest treated mares) have been chosen to bring a standardized socio-sexual stimulation to each stallion in that season of year and to avoid mating, and it is likely that cyclic mares would have produced better stimuli. The fact that experiments took place in the non-breeding season was not a drawback in terms of the physiology of the stallions. Although the hypothalamic-pituitary-testicular axis of normal stallions has a lower activity in the non-breeding season, it is much more responsive, to a GnRH challenge for instance [START_REF] Roser | Seasonal effects on seminal quality, plasma hormone concentrations, and GnRHinduced LH response in fertile and subfertile stallions[END_REF].

In Experiment.2, refractory latency increased strongly at 22 and 57 days, although erection and first ejaculation latencies, demonstrating that refractory latency is a more sensitive criterion for libido evaluation, as suggested by S. McDonnell (University of Pennsylvania, personal communication). It was often observed that Treated stallions with no second erection in 60 min during the test, presented an erection immediately when they returned to their harem. It is possible that, in our experiments, the housing and semen collection conditions could have induced complex and contradictory stimuli.

Both the volume of filtered semen and the volume of gel increased transiently at 22 and 57 days, but returned to pretreatment level at 113 days. It is well-known that long-lasting Comment citer ce document : Vidament, M., Larry, J.L., Arnaud, G., Magistrini, M., Clément, F. ( 2006). Effect of stabling stallions with mares during the non-breeding season on semen collection behaviour, semen characteristics and plasma testosterone concentrations. In: Proceedings of the Ninth International Symposium on Equine Reproduction (p. 50-53). Animal Reproduction Science, 94 (1-2).

teasing or long-lasting erection before ejaculation lead to increased volume of ejaculate [START_REF] Ionata | Effect of supplementary sexual preparation on semen characteristics of stallions[END_REF].

In conclusion, the two types of housing of stallions and mares that were tested failed to increase parameters associated with male reproductive performance. Other housing schemes must be studied to find optimal was of doing so.

Fig. 1 :

 1 Fig. 1 : Reproductive characteristics of stallions before and after housing next to pregnant mares (Experiment 1: 6 Treated stallions and 6 Control stallions, mean ± S.E.M).

Fig. 2 :

 2 Fig. 2: Reproductive characteristics of stallions before and after housing with mares treated with altrenogest (Experiment2: 6 Treated stallions and 6 Control stallions, mean ± sem, ** P<0.001, *** P<0.0001)

Acknowledgements :

To S. McDonnell (for experimental design), S. Canepa (for testosterone dosage), all persons in Chamberet (for animal managing), JM. Yvon (for continuous help), French National Stud (Haras Nationaux) and INRA for financial support.


Slawomir Staworko

Emmanuel Filiot

Jan Chomicki

Querying Regular Sets of XML Documents ⋆

We investigate the problem of querying (regular) sets of XML documents represented with tree automata and we consider n-ary tree automata queries whose expressive power captures MSO on trees. Because finite automata can represent infinite sets of documents, we propose the notions of universal and existential query answers, answers that are present resp. in all and some documents. We study complexity of query answering and show that computing existential query answers is in PTIME if we assume the arity of the query to be a fixed parameter. On the other hand, computing universal query answers is EXPTIMEcomplete, but we show that it is in PTIME if we assume that the query is fixed (data complexity). Finally, we argue that the framework captures problems central to many novel XML applications like querying inconsistent XML documents. In particular, we demonstrate how to use our framework to compute consistent query answers in XML documents that do not satisfy the schema. This solution significantly extends our previous results in this area.

Introduction

In this paper we investigate the problem of querying potentially large sets of XML documents having a small compact representation by a finite tree automaton. Our work is inspired by the problem of evaluating a query in a document that possibly does not satisfy the schema. Since the satisfaction of the schema is usually assumed during formulation of a query, evaluation of the query against a document that does not satisfy the schema may yield incorrect and misleading answers. This problem has been previously recognized in the setting of relational databases [START_REF] Arenas | Consistent Query Answers in Inconsistent Databases[END_REF] and the proposed framework of repairs and consistent query answers (CQA) has been adapted to semi-structured databases [START_REF] Staworko | Validity-Sensitive Querying of XML Databases[END_REF][START_REF] Flesca | Repairs and Consistent Answers for XML Data with Functional Dependencies[END_REF][START_REF] Flesca | Querying and Repairing Inconsistent XML Data[END_REF]. A repair is a document satisfying the schema and obtained from the original document by a minimal number of standard edit operations [START_REF] Abiteboul | Incremental Maintenance for Materialized Views over Semistructured Data[END_REF][START_REF] Balmin | Incremental Validation of XML Documents[END_REF]: inserting, deleting, and modifying an element of the document. An answer is consistent (also called valid) if it is an answer to the query in every repair.

Our research shows that the set of repairs of a document is a regular language that has a compact representation by a finite (weighted) tree automata.

This reduces the problem of querying the set of repairs to a more general problem of querying a regular set of documents represented by a tree automaton. Because the set of documents represented by an automaton can be very large, an approach where we return the collection of the sets of answers in every tree may be simply inappropriate for many applications. Consequently, we propose two ways of computing answers to queries in sets of documents: (i) universal answers that are present in every document and (ii) existential answers that are present in some document. Obviously, universal answers capture consistent answers. We also note that the existential answers capture the notion of possible answers, i.e. the answers that are present in some repair [START_REF] Flesca | Repairs and Consistent Answers for XML Data with Functional Dependencies[END_REF], often considered next to consistent answers in the framework of CQA. Another motivation to study the problem of querying regular sets of documents is that there are other frameworks where the queries are evaluated not on the instance itself but rather on the set of instances obtained by some (often nondeterministic) process from the original one. An example is XML data exchange [START_REF] Arenas | XML Data Exchange: Consistency and Query Answering[END_REF]: the queries are formulated against target schema whose instances (called solutions) are obtained from a source instance with a set of source-to-target dependencies specifying how the parts of the source instance translate to an instance in target schema. In the data exchange scenario, the notion of universal and existential answers coincide resp. with certain and maybe answers [START_REF] Libkin | Data Exchange and Incomplete Information[END_REF]. It is, however, yet to be seen if the set of solutions can be represented by a tree automaton. Now, we briefly summarize our contributions:

-We define the problem of universal and existential querying of sets of documents represented by a finite tree automaton with attribute values and we consider n-ary queries expressed with tree automata.

-We thoroughly study the complexity of computing existential and universal answer. For computing existential answers, we show that its combined complexity is NP-complete, but its complexity parametrized by the arity of the query is FPT (Fixed Parameter Tractable) [START_REF] Fellows | Parameterized Complexity: The Main Ideas and Connections to Practical Computing[END_REF]. This result is not surprising as the number of answers to an n-ary query can be exponential in n. Computing universal answers is, however, EXPTIME-complete in terms of both the combined and parametric complexity. On the other hand we show that its data-complexity is PTIME.

-We show how to compute consistent query answers by constructing a repair automaton that defines the set of all repairs of a document w.r.t. a schema (expressed with a tree automaton). This extends our previous results [START_REF] Staworko | Validity-Sensitive Querying of XML Databases[END_REF][START_REF] Staworko | Declarative Inconsistencies Handling in Relational and Semistructured Databases[END_REF] in several directions: (i) we consider n-ary automata queries whose expressive power captures MSO as compared to a restricted class of unary Core XPath queries, (ii) schema can be expressed using tree automata which are strictly more expressive than DTDs, (iii) we show that data complexity of computing consistent answer to any n-ary automata query is PTIME, (iv) we consider a more general set of editing tree operations that allow to operate on inner nodes as compared to operations on leaves only.

Related work [START_REF] Flesca | Repairs and Consistent Answers for XML Data with Functional Dependencies[END_REF] investigates querying XML documents that are valid but violate functional dependencies. Two repairing actions are considered: updating element values with a null value and marking nodes as unreliable. Such nodes are simply omitted in the query answers. Only simple descending path queries a 1 /a 2 / . . . /a n are considered. A polynomial algorithm for computing consistent and possible answers is presented. [START_REF] Flesca | Querying and Repairing Inconsistent XML Data[END_REF] considers editing operations operating on leaves only to define the set of repairs for consistent querying of documents that violate functional dependencies. A different, set-theoretic, notion of minimality is used when defining repairs. Both consistent and possible answers are considered. For restricted classes of functional dependencies and DTDs a polynomial algorithm is proposed to compute consistent answers to n-ary conjunctions of path expressions. [START_REF] Frick | Query Evaluation on Compressed Trees[END_REF] considers evaluation of monadic Datalog queries on compressed trees (represented by a tree automaton) and shows that combined complexity is PSPACEcomplete and data complexity is PTIME. We note that this framework is close to existential querying: a (finite) set of trees can be gathered in one tree with a new root symbol. The difference between the complexity results (for unary queries we have polynomial algorithm in terms of combined and data complexity) comes from different representations of queries. [START_REF] Lohrey | The Complexity of Tree Automata and XPath on Grammar-compressed Trees[END_REF] extends this approach to trees represented by straight-line context-free grammars which is strictly stronger than regular languages.

[21] study the problem of checking if a document is within a specified alignment distance to the given schema. We note that the edit distance is more general than the alignment distance which imposes certain conditions on the sequence of editing operations [START_REF] Bille | Tree Edit Distance, Aligment and Inclusion[END_REF] and hence our approach is more general. A compact representation of all repairs (obtained with restricted sequences of editing operations) as a regular language is also presented.

The paper is organized as follows. Section 2 contains basic XML notions and streaming tree automata. In Section 3 we define existential and universal answers to n-ary queries and present algorithm for computing them. In Section 4 we study computational implications of our framework. Section 5 shows how to use our framework to compute consistent query answers. Because of space limitations the proofs are omitted; they can be found in the appendix available at [START_REF] Staworko | Querying Regular Sets of XML Documents[END_REF].

Basic notions

Trees and streams

We model XML documents using ordered unranked trees whose nodes are labeled with elements of a finite set of symbols Σ. Every node is additionally labeled with an attribute whose value is drawn from an infinite set Λ. We denote the set of all trees by T . The size of t, denoted by |t|, is the number of nodes of t.

In our framework only the attribute values are used to define query answers. The attributes of a tree can store unique node identifiers and we call such trees standard. In general, however, the attribute can store (possibly repeated) data values.

In this paper we work mainly with the serialized version of trees, i.e. wellformed sequences of opening and closing tags (corresponding to a preorder traversal of the tree) with attribute values associated to the opening tags. The set of all tags is Σ ♦ = { a |a ∈ Σ} ∪ { /a |a ∈ Σ}. When working with a serialized version of a tree e 1 , . . . , e n we write tag(e i ) for the tag of e i and att(e i ) for the attribute value of e i . Given a tree t its serialized version is denoted by t. We

c l 0 a l 1 b l 2 a l 3 b l 4 a l 5 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 tag c a /a b /b a /a b /b a /a /c att l0 l1 -l2 -l3 -l4 -l5 - - Fig. 1.
An example of a tree t0 and the corresponding tag sequence use also unranked terms over the signature Σ × Λ to represent trees. Figure 1 contains an example of a tree t 0 = c l0 (a l1 , b l2 , a l3 , b l4 , a l5 ) and its serialization.

Streaming tree automata

To capture regular tree languages we use streaming tree automata [START_REF] Gauwin | Complexity of Earliest Query Answering with Streaming Tree Automata[END_REF] which are Visibly Pushdown Automata [START_REF] Alur | Visibly Pushdown Languages[END_REF] working on serializations of unranked trees. They are allow to capture Extended DTDs [START_REF] Kumar | Visibly Pushdown Automata for Streaming XML[END_REF] which makes them equivalent to standard (ranked) tree automata working on encodings of unranked trees [START_REF] Comon | Tree Automata Techniques and Applications[END_REF].

We choose this model because it is better fitted to capture repairs of XML documents: repairs are obtained by edit operations on nodes and those easily translate to string edit operations on pairs of matching tags. We also extend this model by allowing it to specify attribute values: this way the repairs can be defined in terms of the attribute values of the original document. For simplicity of presentation we fix the set of attribute values Λ.

Definition 1. An attributed streaming tree automaton Essentially, an attributed STA is a push-down automaton working on sequences of tags with the stack manipulation restricted to: placing a symbol on the stack when reading an opening tag, and removing top symbol from the stack when reading a closing tag. A configuration is an tuple (q, ᾱ, s), where q is the current state, ᾱ is the current stack, and s is the remaining (possibly unbalanced) tag sequence. The move relation → M is a binary relation on configurations defined as follows:

(attributed STA) is a tuple M = (Σ, Γ M , Q M , I M , ∆ M , F M ), where Σ is a finite set of node labels, Γ M is a finite set of stack symbols, Q M is a finite set of states, and I M ⊆ Q M is the set of initial states, F M ⊆ Q M is the set of final states. ∆ M is a finite set of
(i) (q, ᾱ, e • s) → M (p, γ • ᾱ, s) if q a :γ ---→ l p ∈ ∆ M , tag(e) = a , and if l = * , then att(e) = l . (ii) (q, γ • ᾱ, e • s) → M (p, ᾱ, s) if q /a :γ ----→ p ∈ ∆ M and tag(e) = /a . → *
M is the reflexive and transitive closure of → M . The tree language of M is defined as

L(M ) = {t | (q, ε, t) → * M (p, ε, ε), q ∈ I M , p ∈ F M }.
An STA is an attributed STA that imposes no restrictions on the attribute values, i.e. it uses only * . Then, we also omit the attribute labels altogether. Figure 2 contains an example of an STA M 0 that recognizes trees with root label c satisfying the DTD D 0 given by the rules:

c → (a • b) * • a, a → ǫ, b → ǫ.
We observe that the tree t 0 (Fig. 1) satisfies M 0 . Weighted STAs To represent the sets of minimal repairs we further extend attributed STAs by assigning to every transition its weight, a non-negative real value. The weights are used to restrict the set of recognized trees to those with a run of minimal summary weight. More formally, a weight of a run is the sum the weights of the transition used at each step. For a tree (with an accepting run) we associate the minimal weight of its accepting run. L(M ) contains only the trees that whose weight is equal to the minimum of weights of all trees (with an accepting run).

STA queries

We define an n-ary query as a function that takes a tree and returns a set of n-ary tuples of values from Λ (that are used in the tree).

To define an n-ary query we use an extension of (standard) STAs where with every opening transition we associate a set of variables X ⊆ {x 1 , . . . , x n } that indicates the positions of the resulting tuple (x 1 , . . . , x n ) that are to be filled when the transition is used in a run (the positions are filled with the attribute value). Each position of the resulting tuple has to be filled exactly once during a run, otherwise the run is non-accepting. The set of query answers consists of all tuples obtained from all accepting runs. We use name STA queries to refer to such automata and to distinguish them from STAs we use Greek capital letters Φ, Ψ, . . .. We also put the sets X in the superscript of the opening transitions. (Fig. 1) this query has two answers: (l 1 , l 2 ) and (l 3 , l 4 ). We define query answers formally as follows. A configuration of an n-ary STA query Φ is an element (q, ᾱ, s, τ ), where q, ᾱ, and t are as before, and τ ∈ (Λ ∪ {⊥}) n is the tuple of values assigned so far, with ⊥ (the null value) indicating that the value has not been yet assigned. We define the move relation analogously:

(i) (q, ᾱ, e • s, τ ) → Φ (p, γ • ᾱ, s, τ ′ ) if q a :γ ---→ p ∈ ∆ Φ , tag(e) = a , τ i = ⊥ for every x i ∈ X, and τ ′ = τ [X/att(e)],
(ii) (q, γ • ᾱ, e • s, τ ) → Φ (p, ᾱ, s, τ ) if q /a :γ ----→ p ∈ ∆ Φ and tag(e) = /a . Again, → * Φ is the reflexive and transitive closure of → Φ . The set of answers to an n-ary STA query

Φ in t is QA(Φ, t) = {τ ∈ Λ n |(q, ε, t, (⊥, . . . , ⊥)) → * Φ (p, ε, ε, τ ), p ∈ I Φ , q ∈ F Φ }.
It is known [START_REF] Gauwin | Complexity of Earliest Query Answering with Streaming Tree Automata[END_REF] that over standard trees n-ary STA queries have the same expressive power as MSO formulas with n free variables over the first-child, next-sibling signature of unranked trees In particular, STA queries subsume unary CoreXPath queries. It should be noted, however, that similarly translating an MSO formulas may yield a automata of non-elementary size [START_REF] Thatcher | Generalized Finite Automata with an Application to a Decision Problem of Second-order Logic[END_REF][START_REF] Gauwin | Complexity of Earliest Query Answering with Streaming Tree Automata[END_REF]. This generally applies also to CoreXPath queries, but it can be easily seen that simple descending XPath queries with no test expressions translate to STA queries of linear size.

Existential and universal querying of attributed STAs

Now, we consider querying sets of trees defined by attributed STAs. First, we note that the set of trees defined by an attributed STA may be infinite and even if the STA is weighted, the number of trees may be exponential in the size of the automaton (modulo different attribute values). Therefore, an approach where we return the collection of the sets of answers obtained in every tree may be inappropriate for many applications. Consequently, we propose two ways of querying sets of trees.

Definition 2 (Universal and existential answers). Given a (possibly weighted) attributed STA M such that L(M ) = ∅ and n-ary STA query Φ

-the universal answers to Φ in M are QA ∀ (Φ, M ) = t∈L(M ) QA(Φ, t), -the existential answers to Φ in M are QA ∃ (Φ, M ) = t∈L(M ) QA(Φ, t).
We note that the language defined by a weighted automaton is empty if and only if the corresponding automaton without weights defines an empty language. Emptiness of an attributed STA can be tested in cubic time using the classical algorithm for PDAs. Because our algorithms have complexity of a higher degree, from now on we will assume that we always deal with automata defining nonempty language. Also, the set QA ∀ (Φ, M ) is always finite, but QA ∃ (Φ, M ) may be infinite if M uses wildcards. Hence, we also allow to use wildcards in answers to finitely represent QA ∃ . Now, we present Algorithm 1 computing existential answers to an n-ary query Φ in an attributed STA M . This algorithm is is based on a product technique ------→ X:=l (p2, q2) :≡ p1

x:γ 1 ---→ X p2 ∈ ∆Φ ∧ q1 x:γ 2 ---→ l q2 ∈ ∆M , 1: for (u, v) ∈ Q 2 do 2: T0[u, v] = ( {(⊥, . . . , ⊥)}, if u = v, ∅, otherwise. 3: for i ← 1, . . . , n|Q| 2 do 4: for (u, v) ∈ Q 2 do 5: Hi[u, v] = Ti-1[u, v] 6:
for j ← 1, . . . , ⌈log(n|Q| 2 )⌉ do 7:

for

(u, v) ∈ Q 2 do 8: Hi[u, v] ← Hi[u, v] ∪ S {merge(Hi[u, w], Hi[w, v])|w ∈ Q} 9: for (u, v) ∈ Q 2 do 10: Ti[u, v] ← Ti-1[u, v] ∪ S {assignX (Hi[u ′ , v ′ ], l)|u a :γ ---→ X:=l u ′ ∧ v ′ /a :γ ----→ v} 11: return {τ ∈ (Λ ∪ { * }) n |τ ∈ T n|Q| 2 [u, v] ∧ u ∈ I ∧ v ∈ F } end function
of the two input automata. Essentially, it evaluates the query on every tree of height and width ≤ n|Q| 2 , where Q = Q Φ × Q M . This procedure yields correct results thanks to pumping properties of STAs. In particular, if there is a tree t ∈ L(M ) and tuple τ ∈ QA ∃ (Φ, t), there is also a tree t * whose depth and width is bounded by n|Q| 2 , such that t * ∈ L(M ) and τ ∈ QA ∃ (Φ, t * ). Consequently, we need to consider query runs of depth and width bound by n|Q| 2 . This space can be explored with a simple dynamic programming technique because runs of an STA on a tree share the structure of the tree. In particular, T i and H i store all tuples "collected" from runs on resp. trees and hedges (sequences of trees) of depth ≤ i and width ≤ n|Q| 2 . We use assign X (A, l) to assign the value l on positions X to every tuple from A (tuples having a value different from ⊥ on those positions are discarded). merge(A, B) returns the set of merged tuples from sets A and B (two tuples having assigned value on the same position cannot be merged). An easy complexity analysis shows that: Theorem 1. For an attributed STA M and n-ary query Φ Algorithm 1 computes

QA ∃ (Φ, M ) in time O((|Φ||M |) 6 |Dom(M )| 2n ).
Extending the algorithm to weighted attributed STAs is not difficult because minimal runs enjoy optimal substructure properties. Also, if we first perform the run of the algorithm on the attributed STA where every attribute value has been replaced by one unique constant, we can find which tuples in the intermediate steps are removed by the apply and merge operations. This allow us to replace the |Dom(M )| 2n factor by 2 2n |QA ∃ (Φ, M )|.

Corollary 1. For any weighted attributed STA M and n-ary query Φ the set

QA ∃ (Φ, M ) can be computed in time O(2 2n (|Φ||M |) 6 |QA ∃ (Φ, M )|).
We observe that the high complexity in terms of |M | comes from the particular pumping properties of STAs. We note, however, that the algorithm could be easily adapted to standard tree automata working on binary representation of unranked trees. Those automata enjoy nicer pumping properties and in particular the complexity would be cubic in terms of the size of the input automata.

To compute universal answers we observe that QA ∀ (Φ, M ) ⊆ QA ∃ (Φ, M ). Instead of computing universal answers directly, we compute QA ∃ (Φ, M ) and on every tuple we perform tuple check, i.e. we find if the tuple is an answer in every tree. Because we use it as a tool for analyzing the complexity of universal and existential query answers, we formally define it: Existential (universal) tuple check is a decision problem where given an attributed STA M , an n-ary STA query Φ, and a tuple τ ∈ (Λ ∪ { * }) n find if τ is an existential (universal resp.) answer to Φ in M .

Theorem 2. Universal tuple check can be decided in time

O(f (|Φ|)|M | 3 )), where f (|Φ|) = 2 |Φ| 2 2 2n (and O(f (|Φ|)log(|M |)|M | 4 )) if M is weighted).
Consequently, we obtain a characterization of the simple procedure of computing universal answers.

Corollary 2. For any weighted attributed STA M and n-ary query Φ the set

QA ∀ (Φ, M ) can be computed in time O(2 |Φ| 2 2 2n |Φ| 6 |M | 6 |QA ∃ (Φ, M )|).
Now, we analyze tractability of computing existential and universal query answers by investigating the complexity of universal and existential tuple check (defined in the previous section). We start with combined complexity where all the elements are considered to be the part of the input. Theorem 3. Combined complexity of existential and universal tuple check are NP-complete and EXPTIME-complete respectively. We remark that the EXPTIME-hardness is proved with a reduction of the containment problem of two tree automata to a universal tuple check where one of the automata is treated as a 0-ary query.

Next, we observe that if the arity of the query is fixed, then the existential tuple check can be done in polynomial time. Moreover, the degree of the polynomial does not depend on the arity of the query. Hence, we can characterize the (multiplicative) fixed parametric complexity [START_REF] Fellows | Parameterized Complexity: The Main Ideas and Connections to Practical Computing[END_REF]. Corollary 3. When the arity of the STA query is a parameter, the existential tuple check is FPT (Fixed Parameter Tractable). We note that universal tuple check remains intractable when fixing the arity of the query as the EXPTIME-hardness proof uses an STA query of arity 0.

Finally, Theorem 2 give us a characterization of data complexity [START_REF] Vardi | The Complexity of Relational Query Languages[END_REF] of universal query answers (the query is assumed to be fixed).

Corollary 4. Data complexity of universal tuple check is PTIME.

Consistent querying of XML documents

We recall the basic notions of the framework of consistent query answers for semistructured databases. The process of repairing an XML document is modeled with the standard edit operations on trees: (i) renaming the node, (ii) deleting a node (different than the root) which involves promoting its children to the parent of the node (placed in the same order from the position of the node), and (iii) inserting a node (different than the root) with a possible adoption of a list of subsequent children from the parent of the node (dual to the delete operation). With every editing operation we associate a cost: c R , c D , and c I the costs for renaming, deleting, and inserting a node respectively. We note, however, that our approach can be easily extended to weights that depend on properties of the node, for example its label.

The edit distance d(t 1 , t 2 ) between two trees t 1 and t 2 is the minimal cost of transforming t 1 to t 2 with a series of edit operations. Given a tree t and an STA M (expressing the schema), we define the distance between t and M , denoted d(M, t), as the minimum edit distance between t and any t ′ valid w.r.t. M .

A repair of t w.r.t. M is a tree t ′ ∈ L(M ) such that d(t, t ′ ) = d(t, M ). By Rep(t, M ) we denote the set of all repairs of t w.r.t. M . Given an n-ary STA query Φ we say that a tuple τ is a consistent (or valid) answer to Φ in t w.r.t. M if and only if τ is an answer to Φ in every repair of t w.r.t. M . By CQA(Φ, t, M ) we denote the set of all consistent answers to Φ in t w.r.t. M .

Repair automaton

In this part we define a weighted attributed STA that defines the set of all repairs of a document. For ease of construction we allow the use of ǫ-transitions. As they have no attribute value and perform no operations on the stack, we can easily remove them by standard closure (remembering to aggregate the weight). Also, we make a natural assumption that the schema does not allow an empty tree. Definition 3. Let M be an STA, t be a tree with n nodes, and t = (e 1 , . . . , e 2n ) be the serialization of t. Assume that the nodes of t are numbered with consecutive natural numbers 0, 1, . . . , n -1 in the standard document order. For an opening or closing tag e i let m i be the number assigned to that node.

The repair automaton of t w.r.

t. M is a weighted attributed STA R(t, M ) = (Σ, Γ R , Q R , I R , ∆ R , F R ) where: Γ R = Γ M ∪ Γ M × {1, . . . , n}, Q R = I M × {0} ∪ Q M × {1, . . . , 2n -1} ∪ F M × {2n}, I R = I M × {0}
, and F R = F M × {2n}. The state (q, i) will be denoted as q i . The transitions of ∆ R (with their attributes and weights) capture edit operations performed on the tag stream as follows:

q i-1 x:(γ,mi)

-----→ att(ei)

p i renaming e i to x if tag(e i ) = x and doing nothing if tag(e i ) = x, for every i ∈ {1, . . . , 2n} and every q

x:γ

--→ p ∈ ∆ M ; its weight is c R /2 if tag(e i ) = x and 0 if tag(e i ) = x.
q i x:γ --→ p i inserting x (before e i ), for every i ∈ {2, . . . , 2n -1} and every q

x:γ --→ p ∈ ∆ M ; its weight is c I /2 and it is attributed with * if x is an opening tag.

q i-1 ε -→ q i deleting e i , for every i ∈ {2, . . . , 2n -1} and every q ∈ Q M ; its weight is c D /2. Example 1. Figure 4 contains the repair automaton of the tree t 1 = c l0 (a l1 , b l2 ) (Fig. 1) and the STA M 0 (Fig. 2). The weights are assumed to be w R = w I = w D = 1. Because this graph is very intricate, for clarity we present in all details only the transitions that produce the minimal trees. Also, γ j i is short for (γ i , j). R(t 1 , M 0 ) defines the set of trees {c l0 (a l1 )} ∪ {c l0 (a l1 , b l2 , a l )|l ∈ Λ}, i.e. the set of repairs of t 1 w.r.t. M 0 . Theorem 4. For any tree t, any STA M , and any STA query Φ we have that Rep(t, M ) = L(R(t, M )) and CQA(Φ, t, M ) = QA ∀ (Φ, R(t, M )).

Complexity analysis

From Corollary 2 we get directly: Corollary 5. The data complexity of computing consistent answers to an n-ary query w.r.t. an STA is PTIME.

To further analyse the tractability of consistent query answers we investigate the complexity of the problem of tuple check for consistent query answers [START_REF] Staworko | Declarative Inconsistencies Handling in Relational and Semistructured Databases[END_REF]. Similarly to universal answers the problem is intractable. /c : γ0 q 0 0 q 1 0 q 1 1 q 1 2 q 1 3 q 1 4 q 1 5 q 2 0 q 2 1 q 2 2 q 2 3 q 2 4 q 2 5 q 3 0 q 3 1 q 3 2 q 3 3 q 3 4 q 3 5 q 4 0 q 4 1 q 4 2 q 4 3 q 4 4 q 4 5 q 5 0 q 5 1 q 5 2 q 5 3 q 5 6 Conclusions and future work

In this paper we presented the framework of querying regular sets of XML documents. We considered the class of n-ary automata queries and introduced notions of universal and existential answers, i.e. answers present in every and some documents represented by a tree automata. We investigated computational properties of our framework and presented algorithms for computing universal and existential answers. Finally, we used our framework to compute consistent query answers in XML documents that do not satisfy the schema. This solution significantly extends our previous results in this area [START_REF] Staworko | Validity-Sensitive Querying of XML Databases[END_REF].

We envision several possible directions of further study. Firstly, we would like to investigate the problem of querying regular sets of trees with a query defined in a logical formalism which allow comparison of data-values. Such formalisms have been studied in [START_REF] Bojanczyk | Twovariable logic on data trees and xml reasoning[END_REF] where FO logic over data trees is considered. It is shown that FO is decidable for the two-variable fragment with a successor relation and a predicate to compare data-values. Another important direction of future study is to investigate if the setting of data exchange could be effectively captured by our framework. Finally, we would like to investigate using more expressive formalisms, for instance context-free tree grammars, to represent the sets of trees.

  transitions of one of the following types: opening transition p a :γ ---→ l q, and closing transition p /a :γ ----→q, where p, q ∈ Q M , a ∈ Σ, γ ∈ Γ M , and l ∈ Λ ∪ { * } ( * is a wildcard). The size of M is |M | = |Q M | + |∆ M | and by Dom(M ) ⊆ Λ ∪ { * } we denote the set of different attribute labels used in ∆ M .

Fig. 2 .

 2 Fig. 2. The STA M0 for the DTD D0

Figure 3 Fig. 3 .

 33 Fig. 3. An example of a binary STA query

Algorithm 1

 1 Computing existential answers to n-ary Φ in M function QA ∃ (Φ,M ) macros: Q :≡ QΦ × QM , I :≡ IΦ × IM , F :≡ FΦ × FM (p1, q1)x:(γ 1 ,γ 2 )

Theorem 5 .

 5 The combined complexity of consistent query answers is Π 2 p -complete if w I > 0 and EXPTIME-complete if w I = 0.

Fig. 4 .

 4 Fig. 4. A repair graph R(t1, M0)

⋆ Research supported by NSF Grants IIS-0119186 and IIS-0307434.


Bertrand Méda

Antoine Bellande

Gilles Dutin

Sylvain Busnot

Karine Germain

Influence of organic chicken dejections on the soils of two contrasting outdoor-runs of AlterAviBio experimental facility: Ex-ante assessment

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Results

Introduction

⇒

  Figures 1a & 1b: Nutrients stocks for G and T outdoor-runs for 0 -5 and 5 -15 cm horizons