Ph.D. Student supervised Katerina Tzompanaki
email: tzompana@lri.fr

Nicole Bidoit

Melanie Herschel

Semi-automatic SQL Debugging and Fixing to solve the Missing-Answers Problem

Asking questions is the driving force for scientific progress. But as important as it is to ask questions, so important is to be able to understand the obtained answers. In this way, we are able to verify the sanity of the question itself and if necessary refine it. In the same spirit, in this PhD we focus on SQL queries over relational databases with the aim to (1) pinpoint the reasons on the SQL query that led to missing-answers (tuples that were expected but not obtained in the query result), (2) fix the SQL query so that it best fits the user's expectations, and (3) do both efficiently so as to be of practical use.

CONTEXT AND MOTIVATION

One frequent task that developers perform when processing large amounts of data is to define complex data transformations, commonly in the form of queries. However, unexpected data in the output of a query can trigger a whole new series of tedious and error-prone query debugging and query rewriting tasks. Take for example a developer, who may miss some tuples from the result of an SQL query and/or receive undesired ones. Consequently, she might ask the following questions: "Why did this happen?" and "How can this unexpected and undesired behavior be fixed?". To answer them, the developer traditionally first traces the origins of the expected and unexpected result in the source database to then further analyze how the query manipulates these data. This allows to obtain a better understanding of the reasons that prevented the correct answers to appear in the result. She then continues by altering the query or even the data acquisition process before testing again in the new setting. If the result is not yet satisfactory, this whole manual process has to be iterated, possibly many times.

The procedure described above reminds us of 'classical' debuggers and development tools put at programmers disposal for procedural programming languages. However, there is yet no system that can act as debugger for declarative queries and data transformations. First steps towards debugging include [START_REF] Alexe | Spider: a schema mapping debugger[END_REF][START_REF] Grust | True language-level sql debugging[END_REF]. However, especially as queries become more complex, the developer still has to face the challenge of manually searching and identifying the prob-Proceedings of the VLDB 2014 PhD Workshop. lematic parts, and no alternatives are proposed to fix the query once the erroneous clauses have been identified.

The overall goal of the Nautilus project [START_REF] Herschel | Transformation lifecycle management with nautilus[END_REF] is to provide semiautomatic algorithms and tools for data transformation analysis, fixing, and testing. The PhD thesis presented in this paper is set in this context and aims at devising algorithms to support SQL debugging and fixing when facing one particular type of problem, i.e., the lack of some expected data in the query result. We refer to this problem as the missing-answers problem.

In presenting our work, firstly Sec. 2 reviews related work. Sec. 3 summarizes the research questions we address and highlights our scientific contributions. In Sec. 4 and Sec. 5, we describe our contributions so far and outline future work, respectively. Finally, we conclude in Sec. 6.

RELATED WORK

In this section we are surveying the works that are relevant to the developer questions introduced in Sec. 1: why are there (or not) certain tuples in some transformation result (Sec. 2.1) and how can we alter the transformation to obtain the desired results (Sec. 2.2).

Provenance & Transformation Debugging

General discussion. The data provenance field, which started with the introduction of data lineage in relational databases, counts more than one decade of study [START_REF] Woodruff | Supporting fine-grained data lineage in a database visualization environment[END_REF]. As surveyed in [START_REF] Cheney | Provenance in databases: Why, how, and where[END_REF], data provenance research focuses on explaining data present in a query result and may be categorized in three forms based on where [START_REF] Buneman | Why and where: A characterization of data provenance[END_REF] the data were copied from, why [START_REF] Buneman | Why and where: A characterization of data provenance[END_REF][START_REF] Cui | Tracing the lineage of view data in a warehousing environment[END_REF] a query answer was produced (i.e., based on what source data), and how [START_REF] Green | Provenance semirings[END_REF] data were manipulated by the query to produce the result data in question. As discussed in [START_REF] Herschel | Wondering why data are missing from query results?: ask conseil why-not[END_REF], approaches explaining missing-answers may focus on the query and point out how source data were lost [START_REF] Chapman | Why not? In SIGMOD[END_REF], or they focus on the source data and explain why these data cannot yield the desired output [START_REF] Huang | On the provenance of non-answers to queries over extracted data[END_REF]. We discuss these approaches in more detail below, as these are the most relevant w.r.t. this thesis. Note that our work is interested in fine-grained provenance at the level of individual data items (e.g., tuples) as opposed to coarse-grained provenance that remains at schema or manipulation type signature level, as is commonly the case in workflow provenance.

Further approaches useful for query debugging include methods for weighting and ranking the possibly large provenance, e.g., based on causality and responsibility [START_REF] Meliou | The complexity of causality and responsibility for query answers and non-answers[END_REF] or methods to automatically generate test data given a query and a desired output [START_REF] Binnig | Reverse query processing[END_REF][START_REF] Olston | Generating example data for dataflow programs[END_REF]. The latter are particularly valuable for instance when the source data are not accessible or incomplete. Further support in verifying transformation behavior and semantics can be obtained through sub-query result inspection [START_REF] Grust | True language-level sql debugging[END_REF], visualization [START_REF] Danaparamita | QueryViz: helping users understand SQL queries and their patterns[END_REF], or tools that simplify the specification of complex data transformations [START_REF] Khoussainova | SnipSuggest: Context-aware autocompletion for SQL[END_REF][START_REF] Nandi | Guided interaction: Rethinking the query-result paradigm[END_REF].

Whereas the methods mentioned above focus on relational data and queries, other approaches have considered more complex data transformations where in the worst case, individual manipulations use black-box functions. Clearly, data transformation debugging and fixing is essential in this context, and first solutions to incorporate data provenance in scientific workflows [START_REF] Amsterdamer | Putting lipstick on pig: Enabling database-style workflow provenance[END_REF] or Map-Reduce workflows [START_REF] Park | Ramp: A system for capturing and tracing provenance in mapreduce workflows[END_REF] have been proposed. We further observe that fundamental ideas underlying data provenance techniques are not limited to relational data, as it has also been considered for Datalog [START_REF] Green | Provenance semirings[END_REF], logic programming [START_REF] Damásio | Justifications for logic programming[END_REF], XML [START_REF] Foster | Annotated xml: queries and provenance[END_REF], and SPARQL [START_REF] Damásio | Provenance for sparql queries[END_REF]. Explaining Missing-Answers. Related algorithms can be divided into returning instance-based, query-based, or hybrid explanations.

Algorithms returning instance-based explanations [START_REF] Herschel | Explaining missing answers to SPJUA queries[END_REF][START_REF] Huang | On the provenance of non-answers to queries over extracted data[END_REF] look for problems in the data and output sets of tuples that, if added to the database would produce the missing-answers in the query result. Their main difference lies in the class of missing-answers and SQL queries they can handle. [START_REF] Roy | A formal approach to finding explanations for database queries[END_REF] approaches the problem of explaining numerical queries by returning the top-k tuples that are more responsible for the observed result, in a more formal way.

Query-based explanations place the responsibility of the missing-answers not on the source data, but on the transformation (or query). As such, query-based explanation algorithms return a set of transformation operators that have pruned the desired answers. Initially, this solution was proposed for general workflows represented as DAGs of manipulations [START_REF] Chapman | Why not? In SIGMOD[END_REF], while it can further be specialized to relational queries. In this case, the DAG representation of a query is an algebraic tree. This method has several shortcomings that we addressed in [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF], to propose a more effective and efficient algorithm. While both these approaches consider one particular instance of an algebraic query tree, their result may differ for equivalent algebraic query trees, an issue that we recently addressed in [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF]. We summarize both our contributions in Sec. 3.

There are cases where pure query-based or instance-based explanations cannot provide a helpful indication, as they require a combination of both kinds of reasons for the missing-answers. In such cases, hybrid explanations [START_REF] Herschel | Wondering why data are missing from query results?: ask conseil why-not[END_REF] suggest both the tuples to add to the source database and the operators of the algebraic query tree that pruned the desired answer, after applying the suggested hypothetical source database changes.

Query Modification and Fixing

Once the reasons for unexpected transformation results have been identified, a developer wonders how to leverage this knowledge to obtain the needed results. Often, this requires changing the data transformation, in which case the developer has to manipulate the culprit operators returned as query-based explanations. This task becomes time-consuming when we consider the number of different options of changing a transformation. For instance, given that a particular join is returned as query-based explanation, should she change the join condition, replace it with some outer join, or should it actually be a union? In this section, we review some work where transformations are automatically adjusted to changing requirements in general before we focus on modifying queries that make missing-answers appear in the result.

General discussion. A number of works about query rewriting concern schema mappings adaptation. For example, [START_REF] Curino | Graceful database schema evolution: the prism workbench[END_REF] proposes a solution in cases where the source schema evolves but the target schema and result are invariant. Similarly, [START_REF] Yu | Semantic adaptation of schema mappings when schemas evolve[END_REF] describes an approach to adapt schema mappings when the both source and target schemas evolve. To check the correctness of a transformation, [START_REF] Shah | Generating test data for killing sql mutants: A constraint-based approach[END_REF] generates test databases that kill mutants of a specific query and can be further used to identify inequivalent query rewritings. [START_REF] Glavic | Perm: Processing provenance and data on the same data model through query rewriting[END_REF] rewrites the query in order to annotate the result tuples with provenance information, in the form of extra attributes.

Unlike the aforementioned rewriting requirements, our goal is to rewrite a query keeping the schemas the same but not the target (result) data. This requirement derives from the fact that the desired result should be the original one plus the missing-answers. Query Modification for Missing-Answers. [START_REF] Tran | How to conquer why-not questions[END_REF] considers a select-project-join-aggregation (SPJA) query and a complex combination of missing tuples and returns a query similar to the original that is capable of including the missing-answer to the result set with minimal side effects, i.e., by adding to the result set as few extra tuples as possible (ideally only the missing-answers). Given a reverse skyline query and a missing data point, [START_REF] Islam | On answering why-not questions in reverse skyline queries[END_REF] proposes modifications both on the query and the missing data point. [START_REF] He | Answering why-not questions on top-k queries[END_REF] addresses the same problem but for top-k queries by adapting either k and/or the coefficients of a preference query so as to make the missing-answer appear in the result of the re-written top-k query.

THESIS CONTRIBUTIONS

Given the research context and the discussion of related work, we now clearly state the problems, scope, and contributions that we envision for this PhD thesis. The problem statements include some restrictions on the scope and some deliberate imprecisions, which we further clarify in the rest of the discussion. PROBLEM STATEMENT 3.1 (QUERY ANALYSIS.). Given an SQL query Q, a database instance I, and a set of tuples T disjoint from the result Q(I), how can we effectively and efficiently generate useful query-based explanations for the missing-answers defined by T ?

PROBLEM STATEMENT 3.2 (QUERY FIXING.).

With the same hypothesis as above, given the query-based explanations X , how can we efficiently compute a set of useful queries

Q ′ such that ∀Q ′ ∈Q ′ , Q ′ (I) ≈ Q(I) ∪ T ?
SQL queries. SQL has been accepted for a long time as the standard language to manipulate relational data, and thus is one of the most popular query languages [START_REF] Groff | SQL: the complete reference[END_REF]. So, studying query debugging and fixing for SQL queries appears to us as a very natural and practically relevant choice. Query-based explanations. We consider that the content of the database is trusted and not subject to change, so reasons for the missing-answers can only be placed on the constraints imposed by query operators. This information guides a developer to subsequently fix the query. But even if the source data were modifiable, existing work [START_REF] Chapman | Why not? In SIGMOD[END_REF][START_REF] Herschel | Wondering why data are missing from query results?: ask conseil why-not[END_REF] indicate that the numerous instance-based explanations alone are overwhelming and quite costly to compute.

Furthermore, it remains an open question how to 'package' the query operators that are part of query-based explanations to make them most useful to the developer. Is it better to return only one candidate and if so, which one ( [START_REF] Chapman | Why not? In SIGMOD[END_REF] opted for this approach) or is it better to return a (ranked) list of all potential responsible operators? Moreover, should data examples be returned along with the operators? This thesis defines and analyzes some alternative solutions, devise algorithms computing these and also evaluates them experimentally. First results are published in [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF][START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF]. Query fixing. The numerous options for fixing a query may be frustrating for a developer, even if she knows in what query conditions the problem lies. (Semi-)automatically generating appropriate query modifications can relieve the developer from this effort. An interesting and fundamental preliminary question is which query modifications can be considered as appropriate. Ideally, each rewritten query Q ′ ∈Q ′ will return the result of the original query Q plus the missing-answers T , i.e., Q ′ (I)=Q(I)∪T , and thus avoid side-effects. However, finding such a solution is not always possible or the problem may be too complex to be solved efficiently. Therefore, this thesis aims at devising approximate solutions (hence the use of ≈ in the problem statement). Further pruning and ranking of the refined queries can be used to provide only useful solutions, useful meaning relevant to the initial intentions. Formalization. Even though explaining and recovering missinganswers have recently been considered, there is surprisingly little formalization of the problem and the principles underlying algorithms. In this thesis, we put a special emphasis on clearly formalizing the general problem and our solutions, as showcased in our publications so far [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF][START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF]. Efficient Solutions. Calculating explanations of missing-answers and providing query modifications can be very complex depending on the size of the database and the query complexity. To be of any use to a developer especially in an interactive setting, we ought to produce useful explanations and fixes in an efficient manner. In this thesis, we will investigate efficiency of our algorithms both through classical complexity analysis and experimental evaluation. So far, no existing solution addressing the missing-answers problem in SQL query results has explicitly considered efficiency.

Implementation. An integral part of this thesis is to implement and evaluate the designed algorithms, with a special focus on making the algorithms output easily consumable by developers. This implementation will extend the Nautilus Analyzer that was previously developed in our team [START_REF] Herschel | Transformation lifecycle management with nautilus[END_REF].

QUERY-BASED EXPLANATIONS

So far, we have addressed some of the aforementioned research questions in two works proposing the NedExplain [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF] and the Ted [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF] algorithms. The cornerstones of both algorithms are the same; they both compute query-based explanations for missing-answers to address Problem Statement 3.1. However, there are subtle differences w.r.t. their application scope and principles. The discussion first highlights the main concepts underlying both algorithms before we delve into selected details for each one. To illustrate the presentation, we use the sample data and query shown in Fig. 1. We show both an SQL and a query tree representation of the query, the latter providing labels for the individual query operators. Similarly, the tuples in the sample instance are labelled for future reference. The obtained answer is (11, Athens, 4).

Common Concepts

Both algorithms allow to specify the set of missing-answers in form of a Why-Not question, as illustrated in Example 4.1: EXAMPLE 4.1. Considering the data and query of Fig. 1, let us assume that a developer wonders why she did not get the city named Hangzhou in some country with a population (ppl) greater or equal to 1000.

This Why-Not question can be formally described by a conditional tuple tc=((Co.ppl:x1, Ci.CiID:x2), x1≥1000 ∧ x2=Hangzhou), or more briefly tc=((Co.ppl:x1, Ci.CiID:Hangzhou), x1≥1000). Assume now that the developer wonders why she did not get any result tuple having the country population lower than the city population. This Why-Not question is expressed by t ′ c =((Co.ppl:x1, Ci.ppl:x2), (x1<x2)).

Having an intuition on how the Why-Not question is expressed, we can now proceed to the formal definition: Both algorithms rely on this definition. NedExplain considers Q to be a SPJA query or a union thereof, and relies on a logical query tree representation of the query for further processing. Additionally, a conditional tuple may only compare attributes with constant values or with attributes of the same relation. On the other hand, Ted considers a conjunctive query and relies on its tableau representation [START_REF] Abiteboul | Foundations of Databases[END_REF]. Furthermore, in Ted, conditional tuples may also compare attributes of different relations. As a result, in the Example 4.1 the first conditional tuple tc can be treated by both algorithms, while t ′ c that compares attributes from different relations, can be handled only by Ted.

Having the missing-answers modelled by the Why-Not question, we gather all the source tuples that are relevant to produce these missing-answers. To identify the relevant source tuples, we use the notion of compatibility w.r.t. a conditional tuple tc. As the two algorithms differ in the expressiveness of the conditional tuple, they consequently differ in their respective notions of compatibility. NedExplain does not allow individual constraints to span over more than one relation thus, it is sufficient to identify compatible tuples per relation. On the contrary, Ted allows for constraints involving more than one relation and thus, identifies combinations of tuples from different source relations. Each such tuple combination forms what we call a concatenated compatible tuple (cc-tuple). Indeed, a compatible tuple is a special case of a cc-tuple. EXAMPLE 4.2. For the conditional tuple tc, we obtain the compatible tuples t1 and t5. Indeed, t5 satisfies the constraint on City (as it has CiID=Hangzhou) whereas t1 satisfies the constraints on Country (Co.ppl≥1000). Concerning t ′ c , we have to concatenate tuples from the different relations to check whether the condition is satisfied. For example, the tuple t3 can be considered compatible w.r.t. t ′ c only in association with tuple t6 (Paris has a greater population than Greece). We denote the resulting cc-tuple as τ =(t3t6).

The fundamental concept that comes next is pickyness, a property that defines those query parts that pruned the compatible source data. As already mentioned, the query Q considered in the two algorithms is not represented in the same way as the one uses a query tree and the other a minimal tableau. As a consequence, NedExplain identifies picky subqueries, whereas Ted more generally returns picky query conditions. EXAMPLE 4.3. For the Why-Not question involving tc, NedExplain identifies two picky subqueries. Referring to Fig. 1, these correspond to the subqueries rooted at op2 and op3. Indeed, the valuation for ppl in the compatible tuple t5 does not satisfy the selection condition of op3. Similarly, the attribute values of t1 contradict the condition of the selection op2.

Note that NedExplain does not return culprit subqueries rooted higher up in the query tree as all compatible tuples have been lost once tracing them all the way up to op2 and op3. This is a consequence of NedExplain considering one particular instance of a query tree and that the result is w.r.t. this query tree. Consequently, equivalent query trees may yield different sets of picky operators when using NedExplain. For example, if all selections are pushed above the join, only the join would be identified as picky, as it will be responsible for pruning both compatible tuples t1 and t5. Contrary to that, Ted returns all conditions (that are linked to query operators) that prune compatible data (cc-tuples in general) independently of a query tree representation. EXAMPLE 4.4. For the Why-Not question tc defines, Ted identifies as picky the conditions Co.CoID ='China ′ , Ci.ppl < 8, and Co.CoID=Ci.CoID as the values of the cc-tuple (t1t5) do not satisfy any of these conditions. Thus, Ted identifies the picky operators op2, op3, op4.

As a final step, both algorithms return query-based explanations, later called Why-Not answers, for the missing-answers captured by the Why-Not question. NedExplain models its Why-Not answer as a set of picky subqueries linked to the compatible tuples that were excluded at that point. So, not only is the user informed about the subqueries that are to blame but also gets a guidance on how to fix them, by knowing the values of the attributes that do not agree with the picky subqueries' constraints. Ted models the Why-Not answer as a polynomial of picky operators. Essentially, an addend k * op1 * • • • * opn provides a query-based explanation (the operators op1, . . . , opn). Moreover, the coefficient k gives an estimation of the amount of different ways in which the missing-answer could be generated if the given picky operator combination was passing. EXAMPLE 4.5. Continuing our example using tc, NedExplain returns the Why-Not answer {(t1, op2), (t5, op3)} while Ted returns op2 * op3 * op4. Assuming that table City did contain another tuple t ′ 5 =(Hangzhou, China, 9), NedExplain would return {(t1, op2), (t5, op3), (t ′ 5 , op3)} whereas Ted would return op2 * op3 * op4 + op2 * op3, i.e., there is one addend for the cc-tuple (t1t5) and another one for the cc-tuple (t1t ′ 5 ). Overall, comparing the two algorithms, NedExplain can handle a wider class of queries and is more efficient than Ted. On the other side, Ted's main strengths are that it can handle a wider class of Why-Not questions and that it provides a complete set of querybased explanations w.r.t. different query tree re-orderings as opposed to NedExplain. However, as we will see below, this comes at the price of a high worst-case complexity.

We now discuss the specificities of both algorithms in more detail. Due to space limitations most formal definitions are omitted and interested readers can refer to the detailed papers [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF][START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF].

NedExplain

Given an algebraic query tree and after identifying compatible tuples as described in the previous section, the core of the Ned-Explain algorithm [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF] traverses the query tree in a bottom-up way. When at some node (i.e., query operator at the root of a subquery) it loses track of compatible tuples, meaning they can be found in the operator input but not in the output, it marks the subquery rooted at the operator as a picky subquery. Example 4.6 illustrates this process by executing the algorithm on the running example and therefore describes in detail how we obtained the result in Example 4.3. EXAMPLE 4.6. We are going to trace the compatible tuples t1 from Country and t5 from City on the query tree in Fig. 1(c). Let us start with the subquery rooted at op1. After executing it on the Country instance (that contains the compatible tuple t1), we observe that there is a tuple that is generated using only compatible tuples (i.e., the tuple t1). We say that t1 has a valid successor in the output of op1. Then we move to op2. In the output of op2 we do not find any valid successors of t1, so we mark op2 as a picky subquery for t1. Similarly, in the input of op3 we have the compatible tuple t5, however we do not obtain a valid successor of it in the output. Thus, op3 is picky for t5. Now, in the input of op4 there are not any successors of compatible tuples and so we stop the procedure of searching for picky subqueries.

The Why-Not answer returned by NedExplain includes the picky subqueries identified in Q and can take three forms. For brevity, here, we focus on the most informative one, i.e., the detailed Why-Not answer, previously illustrated in Example 4.5. Assuming a Why-Not question with a single conditional tuple, we define this Why-Not answer as formalized in Definition 4.2 below. When the Why-Not question contains more than one conditional tuple, the Why-Not answer is the union of the Why-Not answer obtained for each conditional tuple. Note that this definition distinguishes between direct and indirect compatible tuples (sets Dir tc and InDir tc , respectively). Intuitively, the direct compatible tuples are those that have attributes constrained in the Why-Not question. Thus they are of direct interest for the user and they can be used in conjunction with the picky subqueries for query re-writing purposes. The indirect compatible tuples are not linked to the Why-Not question and correspond to necessary data for the query. The algorithm producing the detailed Why-Not answer is discussed in detail in [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF]. Its worst case time complexity is in O(|Q|(L + Out)).|Q| denotes the size of Q, Out is the worst case size (in terms of number of tuples) of a subquery's output, and L is the height of the query tree.

As previously highlighted in Sec. 4.1, the picky subqueries returned may vary for different equivalent query trees of the same query Q. Avoiding this behavior was our main motivation when designing the Ted algorithm.

The Ted Algorithm

Ted algorithm [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF] is divided in two main phases: (1) computing the set of all cc-tuples and (2) determining the Why-Not answer.

Computing the set of all cc-tuples. As seen in Sec. 4.1, Ted allows a more general class of Why-Not questions with comparisons between attributes from different relations, which entails the necessity of defining cc-tuples. To compute the set of cc-tuples, we use a compatibility tableau Tt c that is built using the input query schema SQ (in this case Country and City) and the condition of tc. Even though in Example 4.2, we only show one cc-tuple, in general, we obtain a set of cc-tuples w.r.t. Tt c , which we denote CCT (Tt c , I). Each τ ∈CCT (Tt c , I) would have contributed the missing-answer, if it succeeded to satisfy all query conditions.

To efficiently compute CCT (Tt c , I), we create a valid partitioning of Tt c that groups together those rows of the tableau that share some variables in their conditions. Then, for each partition, we first join the involved relations (one row in the tableau stands for a relation) based on their join conditions (conditions with variables from two rows) and apply the remaining selection conditions. Thus, we obtain a set of cc-tuples for each partition.

We then use the following lemma [START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF] to compute the full set CCT (Tt c , I), by performing the cross product on the sets of cctuples of each partition. Computing the Why-Not answer. Essentially, the Why-Not answer includes, for each τ ∈CCT (Tt c , I), all query conditions that 'picked' τ out of the result. To compute the picky conditions and thus the picky operators for each τ ∈CCT (Tt c , I) we use another tableau Tτ , as illustrated in Tab. 2. This tableau has two columns that are used for conditions: (1) in condτ we keep the conditions on the attributes of each row induced by a given τ (here (t3t6)) and (2) in condQ we keep the conditions on the attributes of each row imposed by Q (here the selection and join conditions of op1, op2, op3, and op4). When some condition condp ∈ condQ contradicts some constraint in condτ , then condp is picky for τ . EXAMPLE 4.8. In the Country row of Tab. 2, the conditions on the variables x1 and x2 in the two condition columns, agree. However, the query condition x1=x4 is not satisfied by the valuation of τ , as Greece =F rance. So, x1=x4 and hence its associated query operator op4 is picky for τ . Similarly, we identify that op3 (associated with the query condition x5<8) is picky for τ and thus the set containing the picky operators w.r.t. τ is P Oτ ={op3, op4}. To model that both operators are problematic w.r.t. τ , we introduce the product op3 * op4 associated to τ .

As each cc-tuple represents one alternative to obtain the missinganswers, we determine one product for each τ in CCT (Tt c , I) . We then sum up these products and obtain a polynomial that explains how the operators in the query are picky w.r.t. tc. "How" here means in which combination and in how many ways, and also acknowledges the fact that this representation is similar in spirit to the provenance polynomials used for how-provenance [START_REF] Green | Provenance semirings[END_REF]. Formally, we define the Why-Not answer that Ted returns as follows: case complexity of Ted is in O(N k ), where k is the number of relations and N the maximum size of a relation instance. Clearly, the complexity of the algorithm is prohibitive for large databases and so our first priority is to address efficiency.

Implementation and Evaluation

We implemented both NedExplain and Ted using Java and evaluated their performance in terms of effectiveness and efficiency on several benchmark scenarios. We also implemented the algorithm presented in [START_REF] Chapman | Why not? In SIGMOD[END_REF], the only other algorithm returning query-based explanations for SQL queries (our implementation did benefit from source code kindly provided by the authors of [START_REF] Chapman | Why not? In SIGMOD[END_REF]). A detailed discussion of the experimental setup and results can be found in [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF][START_REF] Bidoit | Immutably answering why-not questions for equivalent conjunctive queries[END_REF]. Briefly, NedExplain produces better quality answers than [START_REF] Chapman | Why not? In SIGMOD[END_REF], by quality meaning that it captures also picky subqueries that [START_REF] Chapman | Why not? In SIGMOD[END_REF] is not able to capture. Additionally, NedExplain outperforms [START_REF] Chapman | Why not? In SIGMOD[END_REF] in terms of execution time (even though worst-case complexities are comparable) [START_REF] Bidoit | Query-based why-not provenance with nedexplain[END_REF]. However, even though the picky operators calculated by NedExplain and [START_REF] Chapman | Why not? In SIGMOD[END_REF] vary for different choices of query trees, they are always included in the Why-Not answer by Ted.

FUTURE DIRECTIONS

Based on our work so far, we now briefly discuss the future research directions that we envision to explore. Efficiency. Clearly, given its complexity, Ted requires further improvements on efficiency. Taking a closer look, we observe that as the Why-Not question becomes more general, the complexity increases, because the conditions that help reduce the number of cctuples to generate and process, are getting fewer. The worst case occurs when the Why-Not question asks "Why-Not any tuple?" in the case of an empty query result. Indeed, in this case, we have no choice but to first compute the cross product of all relations referenced in the query schema SQ as the set of cc-tuples, to then identify the picky query operators for each such cc-tuple. To tackle the efficiency problem, we think of:

(1) Why-Not question restriction: We can start by proposing alternative Why-Not questions to the developer in order to narrow down the set of missing-answers. This translates into adding more constraints in the Why-Not question. Which questions to present (and in which order) depends on the one hand on statistics on data distribution in the source database that allow to estimate the benefit of adding a particular constraint to the Why-Not question in terms of estimated complexity. On the other hand, the suggested Why-Not question should not be too different from the original one. In a sense, we suggest modifications to the Why-Not question, similar in spirit to the adaptation of the Why-Not question of reverse skyline of queries in [START_REF] Islam | On answering why-not questions in reverse skyline queries[END_REF]. However, our optimization focus significantly differs as it is solely motivated by efficiency.

(2) Sampling-based Why-Not answer approximation: Data statistics as those mentioned above may also be used to determine a representative sample of the database to reduce the cc-tuple computations. Ideally, the representative sample still allows to detect all operator combinations OCi of Ted's Why-Not answer, but with a number of occurrences reduced by a factor f . More specifically, if the exact Why-Not answer were N1 * Πop i ∈OC 1 opi + N2 * Πop i ∈OC 2 + . . ., we aim for a sampling that will generate the approximate N1/f * Πop i ∈OC 1 opi + N2/f * Πop i ∈OC 2 + . . .. (3) Execution environment: Ted can benefit from parallel computation capabilities of distributed platforms and MapReduce techniques to run concurrently the independent computation parts, e.g., processing partitions during cc-tuple computation or processing individual cc-tuples when identifying picky operators. Furthermore, given the types of queries that Ted generates, a column-store database system may be beneficial for runtime [START_REF] Kanade | Choosing right database system: Row or column-store[END_REF]. Query refinement. To avoid generating an overwhelmingly large number of alternative query rewritings, we plan to prune and rank solutions based on a cost model for possible query modifications that reflects the similarity to the original query. We will then generate query fixes that minimize this cost, which relates to work on edit distance. In this way, we favor rewritings most similar to the original query. Proposed algorithms will either return the top-k results w.r.t. the cost model or all rewritings up to a given cost threshold.

The Why-Not answers returned by our algorithms can serve as the starting point for the query rewriting process. Indeed, knowing the picky operators significantly narrows the search for a rewritten query, as we can first focus on finding "good" solutions that only affect this fragment of the query. Furthermore, TedExplain's Why-Not answer polynomial indicates what is the shortest picky operator combination and thus can be used to reduce the number of changes performed to achieve our goal.

CONCLUSIONS AND OUTLOOK

This thesis addresses the problem of explaining missing-answers for SQL queries and suggesting fixes to them to obtain the desired results. The current contributions consist in two algorithms computing query-based explanations, necessary formalizations, implementation and experimental evaluation. Currently, we are working on the efficiency aspects. Next, we will address the problem of proposing appropriate query rewritings. All methods will be implemented and evaluated, in order to properly validate our theoretical contribution and to provide relevant results in practice.

In the long term, our work could be extended to fit not only query but wider data transformations, including more complex manipulations. In this way, whole systems unexpected behaviour can be explained, which has also the benefit of reinforcing user trust, satisfaction, and acceptance of the system [START_REF] Lim | Why and why not explanations improve the intelligibility of context-aware intelligent systems[END_REF]. In a world where information and important decisions are derived and made upon processing Big Data, these properties seem to be more important than ever before.

Figure 1 :

 1 Figure 1: Sample query (a), instance (b), and query tree (c)

DEFINITION 4 . 1 (

 41 WHY-NOT QUESTION). A Why-Not question w.r.t. a query Q is a predicate P over Q's target type TQ, where P= n i=1 t i c , with t i c being a conditional tuple [26] s.t. type(t i c )⊆TQ.

DEFINITION 4 . 2 (

 42 DETAILED WHY-NOT ANSWER). The detailed Why-Not answer of tc w.r.t. Q and I, is defined ast I ∈Dir tc {(tI, Q ′ ) | Q ′ subqueryof Q and Q ′ picky w.r.t. Dir tc ∪ InDir tc and tI} where Dir tc ∪ InDir tc is the set of all compatible tuples in I.

EXAMPLE 4 . 7 .

 47 Tab.1 illustrates the compatibility tableau for the query of Fig. 1 and the conditional tuple t ′ c =((Co.ppl:x1, Ci.ppl:x2), (x1<x2)) introduced in Ex. 4.1 (the tableau omits the summary for brevity). There is a straightforward mapping from variables in the conditional tuple to variables in Tt c , e.g., x1 and x2 in t ′ c map to x2 and x5 in the tableau, respectively.

LEMMA 4 . 1 .

 41 Let P art={P art1, . . . , P art k } be the valid partitioning of Tt c and I be a well-typed database instance. Then, CCT (Tt c , I)= × P art i ∈P art CCT (TP art i , I |P art i ).

DEFINITION 4 . 3 .

 43 (Why-Not answer w.r.t. tc) Given a query Q over a database schema SQ, the instance I over SQ, and the compatibility tableau Tt c associated with the Why-Not question tc, we define the Why-Not answer w.r.t. tc as τ ∈CCT (T tc ,I) op∈P Oτ op.Assuming that the number of tuples |I |R | of a relation R is typically much larger than the size of the schema or query, the worst

Table 1 :

 1 Tableau Tt c for sample Why-Not question t ′

	c

Table 2 :

 2 Tableau Tτ for cc-tuple τ = (t3t6)

		Co.CID Co.ppl Ci.CiID Ci.CoID Ci.ppl	condτ	cond Q
	Country	x1	x2			x1=Greece∧ x1 =China∧
	Co					x2=11	x2>10 ∧ x1=x4
	City		x3	x4	x5	x3=P aris∧	x5<8∧
	Ci					x4= F rance∧	x1=x4
						x5= 12


Nicole Bidoit

Melanie Herschel

Katerina Tzompanaki

Immutably Answering Why-Not Questions for Equivalent Conjunctive Queries Répondre à des requêtes Why-Not indépendamment de la représentation des requêtes

Keywords:

Answering Why-Not questions consists in explaining to developers of complex data transformations or manipulations why their data transformation did not produce some specific results, although they expected them to do so. Different types of explanations that serve as Why-Not answers have been proposed in the past and are either based on the available data, the query tree, or both. Solutions (partially) based on the query tree are generally more efficient and easier to interpret by developers than solutions solely based on data. However, algorithms producing such query-based explanations so far may return different results for reordered conjunctive query trees, and even worse, these results may be incomplete. Clearly, this represents a significant usability problem, as the explanations developers get may be partial and developers have to worry about the query tree representation of their query, losing the advantage of using a declarative query language.

As remedy to this problem, we propose the Ted algorithm that produces the same complete query-based explanations for reordered conjunctive query trees.

Dans le contexte de développement de transformations complexes, les réponses à une question de type 'Why-Not' ont pour objectif d'expliquer au développeur les raisons de l'absence de certaines réponses dans le résultat d'une transformation.

Plusieurs types d'explications ont été proposées et étudiées : des explications basées sur les données, des explications basées sur l'arbre de la requête, des explications hybrides. Les explications qui s'appuient sur l'arbre de la requête, appelées explications 'query-based' (query-based explanations) peuvent être calculées plus efficacement et sont aussi plus faciles à interpréter par le développeur.

Cependant, les algorithmes connus produisant des explications 'query-based' donnent des résultats (1) qui sont dépendants des arbres de requêtes considérés, (2) qui ne sont pas toujours complets. À l'évidence, cela pose un problème d'utilisation important, parce que le développeur doit interpréter les explications en fonction d'un arbre de requête perdant ainsi le bénéfice de l'utilisation d'un langage de requêtes déclaratif et savoir que ces explications sont insuffisantes pour expliquer l'absence de réponse.

1

Cet article propose de remédier à ce problème avec un algorithme appelé Ted, qui produit des explications 'query-based' complètes et équivalentes pour des arbres de requêtes conjonctives réordonnés.

Introduction

The increasing load of data produced nowadays is coupled with an increasing need for complex data transformations that developers design to process these data in every-day tasks, such as data cleaning or data enrichment. These transformations, commonly specified declaratively, may result in unexpected outcomes. For instance, given the query and data of Fig. 1, a developer (or scientist) may wonder why planet Kepler78b is missing from the result, even though he expected or intended it to be part of it. Traditionally, he would repeatedly manually analyze the query to identify a possible reason, fix it, and test it to check whether the missing answer is now present or if other problems need to be fixed.

To help developers during query analysis and debugging, and in particular for answering why-not questions as the one used in the above example that asks why some data are not part of a result, different algorithms have recently been proposed for relational and SQL queries [START_REF] Huang | On the provenance of non-answers to queries over extracted data[END_REF][START_REF] Herschel | Explaining missing answers to SPJUA queries[END_REF][START_REF] Chapman | Why not? In International Conference on the Management of Data[END_REF][START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF][START_REF] Herschel | Wondering why data are missing from query results? ask conseil why-not[END_REF] as well as other types of queries (top-k [START_REF] He | Answering why-not questions on top-k queries[END_REF], reverse skyline queries [START_REF] Md | On answering why-not questions in reverse skyline queries[END_REF]). In this paper, we focus on relational queries, for which existing algorithms explain a missing-answer either based on the data (instance-based explanations), the query (query-based explanations), or both (hybrid explanations). Moreover, we focus on solutions producing query-based explanations, as these are generally more efficient while providing sufficient information for query analysis and debugging. Taking a closer look at existing methods, we notice that these return different explanations for reordered query trees. This is due to the fact that these algorithms reason at the level of query tree operators and trace data relevant to the missing-answer, i.e., compatible data, through one particular instance of a query tree. On this particular query tree, they identify at which picky operators compatible data are lost, and output these.

Example 1.1. Consider the SQL query Q and data D of Fig. 1 and assume that a developer wants an explanation for the absence of planet Kepler78b in the query result Q(D), knowing that this planet does not revolve around the Sun. So here, the whynot question is "Why is tuple ((Planet:Kepler78b, Star:x), x =Sun) not in Q(D)?". Fig. 2 shows two possible query trees for Q. It also shows the picky operators that Why-Not [START_REF] Chapman | Why not? In International Conference on the Management of Data[END_REF] To more accurately answer Why-Not questions, we propose the Ted algorithm that identifies all the picky operators of a relational query and explains how they prevent the generation of the desired answer. The proposed explanations take the form of a polynomial, similarly to provenance semi-rings for how-provenance [START_REF] Green | Provenance semirings[END_REF] that explain data that exists in a query result. The main asset of this algorithm is that the computed set of query-based explanations (i.e., the Why-Not answer) is independent from the query tree representation and is thus not only correct, but also complete w.r.t. the provided definitions. This paper sets the theoretical foundation for computing query-based explanations that are invariant for reordered query trees for conjunctive queries (Sec. 2). We then present Ted, a first algorithm computing such explanations and discuss preliminary experiments (Sec. 3). Sec. 4 concludes and discusses future work.

(•) and NedExplain [2] (⋆) return as query-based explanations as well as query operators returned as part of hybrid explanations by Conseil [6] (•). It is easy to see that each algorithm returns a different result for each of the two query trees, and in most cases, it is only a partial result as the true explanation of the missing answer is

Polynomial-Based Why-Not answers

We assume that the reader is familiar with the relational model and tableaux theory [START_REF] Abiteboul | Foundations of Databases[END_REF]. Here, we briefly revisit necessary notions of previously defined Why-Not questions in Sec. 2.1. Sec. 2.2 reviews and extends what has been called compatible data in previous works. Finally, we define the Why-Not answer in Sec. 2.3.

To better illustrate the different aspects of our solution, we resort to a more complex example than the one introduced earlier.

Example 2.1. Assume a database schema S Q consisting of the relations R, S and T and the database instance I in Fig. 3(a). We use a unique annotation Id to identify a tuple of I. Further consider the relational query in Fig. 3(b). The query result includes the tuple {R.B:5, S.C:9, T.D:4}.

The Why-Not Question

Given a query Q over a database schema S Q1 and an input instance I, a developer formulates a Why-Not question as a predicate P that is a disjunction of conditional tuples (c-tuples) [START_REF] Imieliński | Incomplete information in relational databases[END_REF]. A full definition is available in [START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF]. Next, we will concentrate on conjunctive queries only and predicates composed of a single c-tuple. The proposed method trivially extends to unions of conjunctive queries and a general predicate P, but we omit a discussion for space constraints. A c-tuple t c has the form (t v , cond), where t v is a tuple with attribute values being variables and cond= n i=1 pred i is a conjunction of atomic conditions s.t. each pred i is a comparison between a variable and a constant, or a comparison between two variables. In the following, we will denote the condition associated with a c-tuple t c as t c .cond and the set of variables referred to in t v as var(t v )2 . Special attention has to be given to the condition associated with the c-tuple t c . More specifically, we distinguish here between simple and complex conditions. Notation 2.1. (Simple/Complex condition/c-tuple) An atomic condition pred i in a condition cond is simple if it compares (a) a variable with a constant or (b) two variables referring to source attributes of the same relation. Otherwise, it is a complex atomic condition. We qualify cond as complex if it includes at least one complex atomic condition, and simple otherwise. Finally, a c-tuple is simple if its condition cond is simple, and complex otherwise.

Example 2.2. Given the scenario of Ex. 2.1, we wonder why there is not a result tuple, s.t. the value of R.B is smaller than the one of T.D and on the same time the value of S.C smaller or equal to 9. This Why-Not question is expressed by t c =((R.B:x, T.D:y, S.C:z), (x<y ∧ z≤9)). In t c .cond, z≤9 is a simple condition whereas x < y is a complex condition, because the variables x and y refer to different relations (R and T , respectively). Consequently, t c is a complex c-tuple.

Compatible Data

Intuitively, compatible data designates any source tuples that could have provided data to form the missing answer modelled by t c . The first step towards answering the Why-Not question consists in identifying these source tuples and more specifically their combinations that form the missing answer in the absence of restrictions in Q. In a second step, discussed in the next section, we will identify query conditions (query operators) that prune these tuple combinations.

Example 2.3. Continuing Ex. 2.2, t c .cond implies that the missing-answer is based on a source tuple t x ∈I |R , a source tuple t y ∈I |T and a source tuple t z ∈I |S for which t x (R.B)<t y (T.D) and t z (S.C)≤9 holds3 . Due to the complex condition, t x and t y need to be chosen in correlation with one another, whereas t z is independent from all others. We obtain (Id 1 Id 9 ), (Id 1 Id 10 ) and (Id 2 Id 10 ) as compatible tuple concatenation for correlated (t x t y ), while for t z each one of the tuples in S, i.e., Id 5 , . . . , Id 8 comprises a compatible tuple concatenation.

Previous approaches [START_REF] Chapman | Why not? In International Conference on the Management of Data[END_REF][START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF] consider all compatible tuples independently from each other, e.g., they consider both Id 1 and Id 2 as compatible for t x . However, Id 2 should lose this property when Id 9 is chosen for t y , a fact previously ignored. Therefore, in this paper, we introduce the compatibility of a tuple concatenation rather than compatibility on isolated tuples. According to our definition, each concatenated compatible tuple (cc-tuple) would have resulted in the missing-answer if it was not pruned by some query operators.

Tableau skeleton. We first define a tableau skeleton T S Q , which is a set of variable tuples, one for each relation schema in S Q , such that a variable is not used twice in T S Q . The relations in S Q are also used to identify the rows of T S Q , as shown in Tab. 1.

R.A R.B T.C T.D T.E S.B S.C S.D R x 1 x 2 T x 3 x 4 x 5 S x 6 x 7 x 8
T S Q . h A (R.A)=x 1 h -1 A (x 1 ) = R.A h var(tc) : vat(t c ) → var(T S Q )
Map variables of t c to variables of T S Q associated to the same relation attribute. Practically, T tc models the pattern that a cc-tuple must match. For our example this pattern is: (R.A:x 1 , R.B:x 2 , T.C:x 3 , T.D:x 4 , T.E:x 5 , S.B:x 6 , S.C:x 7 , S.D:x 8 , x 2 < x 4 ∧ x 7 ≤ 9). This leads to the following definition of a compatible concatenated tuple w.r.t. T tc .

h var(tc) (x)=x 2 h var(tc) (y) = x 4 h var(tc) (z) = x 7 f : ID → I Maps a tuple annota- tion to the actual tuple. f (Id 1 ) = (R.A : 1, R.B : 4)

Definition 2.1. (Compatible concatenated tuple w.r.t. T tc ) Let I be an instance of S

Q ={R 1 , . . . , R n } and assume T tc =(T S Q , cond). Let τ =(Id 1 . . . Id n ) be s.t. f (Id i )∈I | R i , ∀i∈[1, n]. Then τ is a compatible concatenated tuple (cc-tuple) w.r.t. T tc if f (τ ) |= h -1
A (cond). We denote the set of cc-tuples w.r.t. T tc given I as CCT (T tc , I). Example 2.4. For T tc in Tab. A (cond) and so τ is a cc-tuple w.r.t. T tc . Totally, we find 12 cc-tuples for our running example.

The Why-Not answer

Given the set of cc-tuples CCT (T tc , I), we define the Why-Not answer using again the tableau skeleton T S Q , this time to create the tableau T τ =(S τ , T S Q , cond τ , cond Q ). S τ =h A (f (τ )) is the summary while cond τ and cond Q denote rewritten conditions induced by the cc-tuple τ and the query Q, respectively. Due to space limitation we do not provide a formal definition of T τ . Roughly, cond τ embeds τ in the tableau and cond Q follows from the classical tableau built from Q [START_REF] Abiteboul | Foundations of Databases[END_REF]. We denote cond τ,R and cond Q,R the restriction of the conditions to the row R. Let us now illustrate how T τ is used to identify picky atomic conditions and associated query operators from the query (and thus included in cond Q ) that are considered responsible for pruning a cc-tuple τ from the query result.

Example 2.6. First, focus on τ 1 and the first row R of Tab. 4. The atomic condition x 1 =1 in cond τ,R contradicts the atomic condition x 1 >3 of cond Q,R . Thus, we say that x 1 >3 is a picky condition. The atomic conditions on x 2 in cond τ,R and cond Q,R are simultaneously satisfied, as x 2 =3 ∧ x 6 =3 ∧ x 2 =x 6 is true.

In the same way, we identify in the rest of the rows the picky atomic conditions and eventually obtain the set of picky atomic conditions w.r.t.

τ 1 : {x 1 >3, x 7 ≥8, x 4 =x 8 }. cond τ cond Q R x 1 x 2 x 1 = 1 ∧ x 2 = 3 x 1 > 3 ∧ x 2 = x 6 T x 3 x 4 x 5 x 3 = 1 ∧ x 4 = 4 ∧ x 5 = 8 x 4 = x 8 ∧ x 5 ≥ 3 S x 6 x 7 x 8 x 6 = 3 ∧ x 7 = 4 ∧ x 8 = 5 x 2 = x 6 ∧ x 4 = x 8 ∧ x 7 ≥ 8 S τ x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 Table 4: Tableau T τ1
Associating these conditions to their respective query operators (see Fig. 3), we obtain the set of picky operators {op 2 , op 4 , op 5 }. The complete Why-Not answer includes an explanation for the pruning of each cc-tuple τ ∈CCT (T tc , I) and takes the form of a polynomial of query operators. We justify modeling each P O τ with a product by the fact that in order for τ to 'survive' up to the query result, every single picky operator w.r.t. τ must be 'repaired'. The sum of the products of each τ ∈ CCT (T tc , I) stems from the fact that, if any addend is 'correctly repaired', the associated τ will return the missing answer.

The Ted Algorithm

Alg. 1 presents the Ted algorithm that computes the Why-Not answer defined in Sec. 2 for a conjunctive query Q. Ted trivially extends to unions of conjunctive queries and a Why-Not question in form of a disjunction of c-tuples (see Sec. 2.1), however, details are omitted due to space constraints.

Ted starts by a preprocessing phase, that consists in creating the tableau skeleton T S Q and the tableau T tc (lines 2 and 3). Then, it determines the set of cc-tuples CCT (T tc , I) in line 5 before it computes the Why-Not answer (lines 6 -8). As the computation of the Why-Not answer directly follows from the definitions of Sec. 2.3, we focus our discussion computing CCT (T tc , I).

To compute the set of all cc-tuples, we could form the cross product of all relations of T tc (e.g., R × T × S) and then verify whether each resulting concatenated tuple (Id R Id S Id T ) satisfies the condition t c .cond. However, this will result in checking the same conditions numerous times, e.g., the condition x 7 ≤ 9 will not be checked once for every tuple in relation S, but as many times as there are tuples in the cross product. To improve efficiency, we divide the problem into independent subproblems based on a partitioning of the rows in T tc . It is easy to prove that the valid partitioning of T tc is unique and that the following lemma holds. Using the above lemma, Ted first determines the set of concatenated tuples for each partition and then forms the cross product of the tuples of each partition in order to obtain CCT (T tc , I).

Complexity analysis. The three main phases of Ted are the partitioning phase, the computation of concatenated compatible tuples, and the computation of the Why-Not answer. The respective worst case complexities add up to O

(|S Q | + R∈S Q |I |R | + R∈S Q (|I |R |) * |S Q | * |Q|).
|I |R |) or O(N k ),
where k is the number of relations and N the maximum size of a relation instance.

Implementation and evaluation. We implemented Ted in Java 1.6 and ran it over several benchmark queries we defined over three different datasets (the same as in [START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF]). Due to space constraints and the obvious efficiency issue entailed by Ted's complexity, we only very briefly show one case for each dataset. Tab. 5 reports Ted's Why-Not answer polynomial and the picky operators identified by NedExplain [START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF] and Why-Not [START_REF] Chapman | Why not? In International Conference on the Management of Data[END_REF]. These use cases clearly demonstrate that Ted returns complete Why-Not answer as opposed to NedExplain and Why-Not, that both in general return subsets of the operators referred to in the polynomial Ted returns. This comes at no surprise, as NedExplain and Why-Not base their procedures on a specific query plan in which they trace compatible data until up to the point (query operator) where they disappear. Being query plan independent, T ed produces the complete set of picky operators for all reordered query plans.

Concentrating on the Why-Not answer polynomials, we see that they bear more information than what previous algorithms return. Indeed, they not only tell us why t c is missing, but also all the different ways it was pruned from the result. For example, in Crime7, we conclude that the majority of cc-tuples do not satisfy the conditions of the op 7 , op 9 , and op 8 , but we also see 9 cc-tuples that are only pruned by op 9 . This information is interesting for subsequent processing (manual or automatic), e.g., we can deduce that the least "invasive" repair of the query touches op 9 .

Outlook and Future Work

Ted is an algorithm that returns query based-explanations for a Why-Not question over a conjunctive query. Opposed to previous work, it is the first algorithm that is guaranteed to return the same explanations, no matter the considered query plan representation. Another novelty is to represent the Why-Not answer as a polynomial. This polynomial has the benefit of being an elegant formalism that can subsequently be used for further processing, e.g., for ranking the importance of "misbehaving" query operators in the query, for actually computing query rewritings that automatically fix the problem, estimating the minimum number of side-effects of a rewriting, etc. These are interesting problems we plan to address in the future. However, before developing solutions to these interesting problems, we will tackle the problem of efficiency. Besides parallel computations, we may for instance reduce the overall complexity by only selecting a "representative" sample of cc-tuples and compute an approximate result (within certain error bounds).

Figure 3 :

 3 Figure 3: Sample instance (a) and query (b)

  3 and τ =(Id 1 Id 5 Id 9 ), it holds that f (τ )=(R.A:1, R.B:3, S.B:3, S.C:4, S.D:5, T.C:1, T.D:4, T.E:8) and h -1 A (cond)=(R.B<T.D ∧ S.C≤9). Since 3<4 and 4≤9, we get f (τ )|=h -1

Example 2 . 5 .

 25 For τ 1 =(Id 1 Id 9 Id 5 ) we obtain T τ1 of Tab. 4.

Notation 2 . 2 .

 22 (Picky operators w.r.t. τ ). We define the set of picky conditions w.r.t. τ as P C τ ={c|c∈cond Q and cond τ |= c}. Each atomic condition c is associated with a query operator op in Q, and we define the set of picky operators w.r.t. τ as P O τ = {op|op associated with some c ∈ P C τ }.

Definition 2 . 2 .

 22 (Why-Not answer w.r.t. t c ) Given query Q over a database schema S Q , the instance I over S Q , and the compatibility tableau T tc associated with the Why-Not question t c , we define the Why-Not answer w.r.t. t c as τ ∈CCT (Tt c ,I) op∈P Oτ op.

Example 2 . 7 .

 27 In Ex. 2.6 we found that {op 2 , op 4 , op 5 } are the picky operators for τ 1 , which results in the addend op 2 * op 4 * op 5 . Applying the same for all 12 cc-tuples in our example, we obtain the final result op 2 * op 4 * op 5 + 3 * op 2 * op 5 + 3 * op 2 * op 3 * op 4 * op 5 + op 2 * op 3 + 2 * op 2 * op 4 + 2 * op 2 * op 3 * op 5 .

Lemma 3 . 1 .

 31 Let P art={P art 1 , . . . , P art k } be the valid partitioning of T tc and I be a well-typed database instance. Then, CCT (T tc , I)= × P arti∈P art CCT (T P arti , I |P arti ).

  that both the selection is too strict for the compatible tuple (Kepler, 1.7, NULL) from table P lanet and this tuple does not find any join partner in table Star.

	Π planet,star	Π planet,star
	σ p.mass≤1 •	✶SID ⋆
	✶SID • ⋆ •	σ p.mass≤1 • ⋆ •	Star
	Planet	Star	Planet
	Figure 2: Reordered query trees for the SQL of Fig. 1 and identified algorithms' results
	(Why-Not •, NedExplain ⋆, Conseil •)
	SELECT planet, star FROM Planets P, Stars S WHERE P.SID = S.SID AND P.mass <= 1	Planet Mass SID 1 1 317.8 1 Kepler78b Planet Earth Jupiter 1.7 NULL Kepler37b 0.01 2	SID 1 2	Star Star Sun Kepler37
	Figure 1: Example query and data
		2

Table 1 :

 1 Tableau skeleton T S

	Function	Purpose	Example
	h A : A → var(T S Q ) Notation for the map-ping between attribute
		names and variables in

Q

Mappings. Our subsequent definitions require the mapping functions described and illustrated in Tab. 2. Note that h var(tc) is used to rename the variables var(t c ) of t c into variables in T S Q . Both functions h A and h var(tc) are extended to apply on the tableau and the c-tuple conditions respectively. Finally, f naturally extends to concatenated tuples, e.g., f (Id 1 Id 5 )=(R.A:1, R.B:3, S.B:3, S.C:4, S.D:5).

Table 2 :

 2 Mapping functionsCompatible concatenated tuples. We are now ready to define cc-tuples. To this end, we enrich T S Q by the condition of cond=h var(tc) (t c .cond) and a summary S tc =h var(tc) (var(t c .t v )).We thus obtain the compatibility tableauT tc =(S tc , T S Q , cond).For brevity, we will also use the notation T tc =(T S Q , cond) (omitting the summary). A sub-condition R.cond can be associated with row R of T tc by restricting the conjunction cond to predicates pred i sharing variables with var(R).So, given T S Q in Tab. 1 and the condition cond=(x 2 <x 4 ∧ x 7 ≤9), we obtain T tc in Tab. 3 (ignore the grouping of the rows for now).

		R.A R.B T.C T.D T.E S.B S.C S.D	cond
	R T S	x 1 x 2	x 3 x 4 x 5	x 6 x 7 x 8	x 2 < x 4 x 2 < x 4 x 7 ≤ 9
	S tc	x 2	x 4	x 7

Table 3 :

 3 Tableau T tc for our running example

	P art 1
	P art 2

Algorithm 1 :

 1 Ted algorithm Input: S Q , Q, I, t c Output: Answer, the polynomial built of the picky operators 1 Polynomial Answer = 0 ; 2 Initialize tableau skeleton T S Q ; 3 Tableau T tc ← createT tc (T S Q , h var(tc) (t c )) ; 4 Set P art ←partitioning( T tc ); 5 Set CCT = CompatibleFinder(P art, I); 6 for (τ : cc-tuple in CCT ) do 7 P O τ = 1; initialization of the product of picky operators for τ Definition 3.1. (Valid partitioning of T tc ).Assume a partitioning of T S Q into k partitions P art 1 , . . . , P art k . This partitioning is valid for T tc if each P art i is minimal w.r.t. the property: ∀R∈T S Q , if R∈P art i and R ′ ∈T S Q s.t. var(R.cond)∩var(R ′ .cond) =∅ then R ′ ∈P art i . Each P art i generates a compatibility tableau (S i , P art i , cond i ), where S i is the restriction of S tc and cond i the restriction of cond over P art i .

	8 9	for (x:variable in T S Q ) do c τ ← single atomic condition on x imposed by τ ;
	10	C Q ← conditions on x imposed by Q;
	11	for (c: atomic condition in C Q ) do
	12	c ′ τ ← true;
	13	if c is a complex condition then
	14	x ′ ← variable compared to x in c τ ;
	15	c ′ τ ← single atomic condition on x ′ imposed by τ ;
	16	if c τ ∧ c ′ τ ∧ c then
	Example 3.1. Tab. 3 shows the two partitions of the valid partitioning that we obtain
	in our running example.

17 P O τ ← P O τ * getOperatorF orCond(c); 18 Answer ← Answer + P ol τ ; 19 return Answer;

Table 5 :

 5 Assuming that the number of tuples |I |R | of a relation R op 8 + 8op 9 + 56136op 7 op 9 op 8 + 792op 7 op 9 op 8 , op 9 Ted, NedExplain and Why-Not results is typically much larger than the size of the schema or query (i.e., |I |R | >> |S Q | and |I |R | >> |Q|), this simplifies to O( R∈S Q

	Use case	Ted	NedExplain Why-Not
	Crime7 952op 9 op 7 Imdb2 8op 3 op 1 op 3 Gov2 17400op 3 + 12op 1 + 19952op 3 op 1 op 1 op 3

Indeed S Q is the query schema of Q as defined in[START_REF] Bidoit | Query-based whynot provenance with Nedexplain[END_REF], which implies that each relation schema in S Q occurs only once in Q.

We also use var(•) to retrieve the set of variables from other structures, e.g., var(tc.cond) returns the variables for which constraints are specified.

I |R denotes the instance of relation R and t(A) denotes the attribute value of tuple t on the qualified attribute A.


domain: info.info-au math spi sdv

text:
Francis Mairet
email: francis.mairet@inria.fr

Jean-Luc Gouzé
email: jean-luc.gouze@inria.fr

Control of a bioreactor with quantized measurements

Keywords: bioreactor, Haldane model, hybrid systems, differential inclusions, quantized output, control

We consider the problem of global stabilization of an unstable bioreactor model (e.g. for anaerobic digestion), when the measurements are discrete and in finite number ("quantized"), with control of the dilution rate. The model is a differential system with two variables, and the output is the biomass growth. The measurements define regions in the state space, and they can be perfect or uncertain (i.e. without or with overlaps). We show that a quantized control may lead to global stabilization: trajectories have to follow some transitions between the regions, until the final region where they converge toward the reference equilibrium. On the boundary between regions, the solutions are defined as a Filippov differential inclusion.

Introduction

Classical control methods are often based on the complete knowledge of some outputs y(t) of the system [START_REF] Sontag | Mathematical control theory: deterministic finite dimensional systems[END_REF]. By complete, we mean that any output y i is a real number, possibly measured with some noise δ i . The control is then built with this (noisy) measurement. These tools have been successfully applied in many domains of science and engineering, e.g. in the domains of biosystems and bioreactors [START_REF] Dochain | Automatic control of bioprocesses[END_REF]. However, in these domains, detailed quantitative measurements are often difficult or impossible or too expensive. A striking example is the measurements of gene expression by DNA-chips, giving only a Boolean measure equal to on (gene expressed) or off (not expressed). In the domain of bioprocesses, it frequently happens that only a limited number or level of measurements are available (e.g. high, very high ...) because the devices only give a discretized semiquantitative or qualitative measurement [START_REF] Bernard | Non-linear qualitative signal processing for biological systems: application to the algal growth in bioreactors[END_REF]. The measure may also be quantized by some physical device (as the time given by an analogical clock), and give as a result some number among a finite collection.

For this case of quantized outputs, the problem of control has also to be considered in a non-classical way: the control cannot be a function of the full continuous state variables anymore, and most likely will change only when the quantized measurement changes. Moreover, the control itself could be quantized, due to physical device limitations.

The above framework has been considered by numerous works, having their own specificity: quantized output and control with adjustable "zoom" and different time protocols, [START_REF] Nesic | A unified framework for design and analysis of networked and quantized control systems[END_REF], hybrid systems abstracting continuous ones (cf. [START_REF] Lunze | Handbook of hybrid systems control: theory, tools, applications[END_REF] for many examples of theories and applications).

In this paper, we consider a classical problem in the field of bioprocesses: the stabilization of an unstable bioreactor model, this model being a simplified representation of anaerobic fermentation, towards its working set point. Anaerobic fermentation is one of the most employed process for (liquid) waste treatment [START_REF] Dochain | Automatic control of bioprocesses[END_REF]. The process (substrate and biomass are state variables) has two stable equilibria (and an unstable one, with a separatrix between the two basins of attractions of the respective stable equilibria), one being the (undesirable) washout of the culture ( [START_REF] Hess | Design and study of a risk management criterion for an unstable anaerobic wastewater treatment process[END_REF]). The goal is to globally stabilize the process toward the other locally stable reference equilibrium. The (classical) output is the biomass growth (through gaseous production), the control is the dilution rate (see [START_REF] Steyer | Lessons learnt from 15 years of ica in anaerobic digesters[END_REF] for a review of control strategies). For scalar continuous output, there exists many approaches based on well-accepted models ( [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]), using constant or adaptive yield [START_REF] Mailleret | Nonlinear adaptive control for bioreactors with unknown kinetics[END_REF][START_REF] Antonelli | Set-point regulation of an anaerobic digestion process with bounded output feedback[END_REF]. Some original approaches make use of a supplementary competitor biomass [START_REF] Rapaport | Biological control of the chemostat with nonmonotonic response and different removal rates[END_REF].

In this paper, we suppose that the outputs are discrete or quantized: there are available in the form of finite discrete measurements. The precise models are described later: roughly, the simplest one is "perfect", without noise, meaning that the true measure is supposed to be one of the discrete measurements, and that the transitions between two contiguous discrete measures are perfectly known. The next model is an uncertain model where the discrete measurements may overlap, and the true value is at the intersection between two quantized outputs. Remark that the model of uncertainty is different from the interval observers approaches ( [START_REF] Alcaraz-González | Software sensors for highly uncertain wwtps: a new approach based on interval observers[END_REF][START_REF] Gouzé | Interval observers for uncertain biological systems[END_REF]) for the estimation or regulation [START_REF] Alcaraz-Gonzalez | Robust interval-based regulation for anaerobic digestion processes[END_REF], where some outputs or kinetics are not well known, but upper or lower bounds are known. Moreover, in the interval observer case, the variables are classical continuous variables.

For this problem, the general approaches described above do not apply, and we have to turn to more tailored methods, often coming from the theory of hybrid systems, or quantized feedbacks (see above) ... We here develop our adapted "hybrid" approach. It has also some relations with the fuzzy modeling and control approach: see e.g. in a similar bioreactor process the paper [START_REF] Estaben | Fuzzy control for an anaerobic digester[END_REF]. We provide here a more analytic approach, and prove our results of stability with techniques coming from differential inclusions and hybrid systems theory [START_REF] Filippov | Differential Equations with Discontinuous Righthand Sides[END_REF]. Our work has some relations with theoretical qualitative control techniques used for piecewise linear systems in the field of genetic regulatory networks ( [START_REF] Chaves | Exact control of genetic networks in a qualitative framework: the bistable switch example[END_REF]). The approach is also similar to the domain approaches used in hybrid systems theory, where there are some (controlled) transitions between regions, forming a transition graph [START_REF] Belta | Controlling a class of nonlinear systems on rectangles. Automatic Control[END_REF][START_REF] Habets | A control problem for affine dynamical systems on a full-dimensional polytope[END_REF].

The paper is organized as follows: the first section describes the bioreactor model and the measurements models, and gives useful elements for the following.

In the second section, we explain what happen at the boundary between two discrete measurements, and define the control on this boundary, with the help of the Filippov definition of differential inclusion. We follow by giving the full solution of the problem in some cases and examples, with or without uncertainty.

Framework

Model presentation

In a perfectly mixed continuous reactor, the growth of biomass x limited by a substrate s can be described by the following system (see [START_REF] Bastin | On-line estimation and adaptive control of bioreactors[END_REF][START_REF] Dochain | Automatic control of bioprocesses[END_REF]):

ṡ = u(t)(s in -s) -kµ(s)x ẋ = (µ(s) -u(t))x (1)
where s in is the input substrate concentration, u(t) the dilution rate, k the pseudo yield coefficient, and µ(s) the specific growth rate. Given ξ = (s, x), let us rewrite System (1) as ξ = f (ξ, u(t)), where the dilution rate u(t) is the manipulated input.

The specific growth rate µ(s) is assumed to be a Haldane function (i.e. with substrate inhibition) [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]:

µ(s) = μ s k s + s + s 2 /k i (2)
Parameters μ, k s , k i describe the model and are positive. This function admits a maximum for a substrate concentration s = √ k s k i := s, and we will assume s < s in .

Lemma 1 The solutions of System (1) with initial conditions in the positive orthant are positive and bounded.

Proof. It is easy to check that the solutions stay positive. Now consider z = s+kx whose derivative writes ż = u(t)(s in -z).

It follows that z is upper bounded by max(z(0), s in ), and so is kx. Finally, if s(t) > s in , then ṡ(t) < 0, therefore s is upper bounded by max(s(0), s in ).

In the following, we will assume initial conditions within the interior of the positive orthant.

Quantized measurements

We consider that a growth proxy y(ξ) = αµ(s)x of biomass growth is monitored (e.g. through gas production), but in a quantized way, in the form of a more or less qualitative measure: it can be levels (high, medium, low...) or discrete measures. Finally, we only know that y(ξ) is in a given range, or equivalently that ξ is in a given region (parameter α is a positive yield coefficient):

Y i ={ξ ∈ R 2 + : y i ≤ y(ξ) ≤ y i }, i = 1, . . . n -1, Y n ={ξ ∈ R 2 + : y n ≤ y(ξ)}.
where 0 = y 1 < y 2 < . . . < y n and y 1 < y 2 < . . . < y n-1 . We will consider two cases:

-(A1). Perfect quantized measurements:

y i = y i+1 , ∀i = {1, . . . n -1}.
This corresponds to the case where there is no overlap between regions. The boundaries are perfectly defined and measured.

0 y i = y i-1 y i = y i+1 Yi-1 Yi Yi+1 y -(A2)
. Uncertain quantized measurements:

y i < y i-1 < y i+1 , ∀i = {2, . . . n -1}.
In this case, we have overlaps between the regions. In these overlaps, the measure is not deterministic, and may belong to two values.

0 y i y i-1 y i+1 y i Yi-1 Yi Yi+1 y
For both cases, we define (open) regular domains:

Ỹi := Y i \ (Y i-1 ∪ Y i+1 ),
and (closed) switching domains:

Y i|i+1 := Y i ∩ Y i+1 .
For perfect measurements (A1), we have Ỹi = intY i , and the switching domains Y i|i+1 correspond to the lines y(ξ) = y i = y i+1 . For uncertain measurements (A2), the switching domains Y i|i+1 become the regions {ξ ∈ R 2 + :

y i+1 ≤ y(ξ) ≤ y i }.
In a switching domain ξ ∈ Y i|i+1 , we consider that the measurement is undetermined, i.e. either ξ ∈ Y i or ξ ∈ Y i+1 .

Quantized control

Given the risk of washout, our objective is to design a feedback controller that globally stabilizes System (1) towards a set-point. Given that measurements are quantized, the controller should be defined with respect to each region:

ξ(t) ∈ Y i ⇔ u(t) = D i , i = 1, ..., n. (3)
Here D i is the positive dilution rate in region i. This control scheme leads to discontinuities in the vector fields. Moreover, in the switching domains, the control is undetermined. Thus, solutions of System (1) under Control law (3) are defined in the sense of Filippov, as the solutions of the differential inclusion [START_REF] Filippov | Differential Equations with Discontinuous Righthand Sides[END_REF]:

ξ ∈ H(ξ)
where H(ξ) is defined on regular domains Ỹi as the ordinary function H(ξ) = f (ξ, D i ), and on switching domains Y i|i+1 as the closed convex hull of the two vector fields in the two domains i and i + 1:

H(ξ) = co{f (ξ, D i ), f (ξ, D i+1 )}.
Following [START_REF] Casey | Piecewise-linear models of genetic regulatory networks: Equilibria and their stability[END_REF][START_REF] Chaves | Exact control of genetic networks in a qualitative framework: the bistable switch example[END_REF]

Model analysis with a constant dilution

For this case, the system is a classical ordinary differential equation in the whole space. When a constant dilution rate D is applied (i.e. u(t) = D, ∀t ≥ 0), System (1) can present bistability, with a risk of washout. Let us denote s a (D) and s b (D) the two solutions, for D ∈ (0, µ(s)), of the equation µ(s) = D, with 0 < s a (D) < s < s b (D). For the Haldane growth rate defined by (2), we have:

s a (D) = k i 2 μ D -1 - k i 2 μ D -1 2 -k s k i s b (D) = k i 2 μ D -1 + k i 2 μ D -1 2 -k s k i .
The asymptotic behavior of the system can be summarized as follows: Proof. See [START_REF] Hess | Design and study of a risk management criterion for an unstable anaerobic wastewater treatment process[END_REF].

For D ∈ (0, µ(s)), let us define:

y j (D) = αD k [s in -s j (D)], j = a, b.
y a (D) and y b (D) are the growth proxy obtained respectively at the equilibria ξ a (D) and ξ b (D) (if it exists) 1 .

In order to design our control law, we need to provide some further properties of the system dynamics. In particular, we need to characterize ẏ(ξ), the time derivative of y(ξ) along a trajectory of System (1) with a constant dilution rate u(t) = D:

ẏ(ξ) = α [D(s in -s) -kµ(s)x] µ ′ (s)x + αµ(s)(µ(s) -D)x.
Let us define the following functions: 4 Control with quantized measurements

g D : s -→ µ(s) -D kµ ′ (s) + D(s in -s) kµ(s) h j D : s -→ D(s in -s j (D)) kµ(s) , j = a, b.

Control design

Our goal is to globally stabilize the system towards the stable equilibrium corresponding to D n . Number n is the number of measurements (see section 2.2) and the control is such that D 1 < D 2 < . . . < D n . The last dilution rate D n is chosen because of its high productivity, it verifies the case (ii) of Prop. 1. We consider the following control law, based on the quantized measurements y(ξ):

∀t ≥ 0, ξ(t) ∈ Y i ⇔ u(ξ) = D i , (4)
given that the following conditions are fulfilled:

y b (D i ) < y i i = 1, . . . , n, (5)
y a (D i ) > y i i = 1, . . . , n -1, (6)
y a (D n ) > y n-1 . (7)
These conditions make the equilibrium ξ a (D n ) globally stable, as we will see below. In Section 5.1, we will precise how to choose the D i such that these conditions hold. In order to prove the asymptotic behavior of System (1) under Control law (4-7), the study will be divided into three steps:

the dynamics in one region, -the transition between two regions, -the global dynamics. This approach is similar to those deducing the global dynamics from a "transition graph" of possible transitions between regions.

Dynamics in one region with a given dilution: exit of domain

We first focus on a region Y i , i < n. A constant dilution D i -such that Conditions (5-6) for i hold -is applied. These conditions guarantee that the stable operating equilibrium for this dilution (see Proposition 1) is located in an upper region Y j , j > i, while the saddle point is located in a lower region Y k , k < i. This allows us to establish the following lemma: Lemma 4 For any i ∈ {1, ..., n -1}, consider System (1) under a constant control u(t) = D i , such that Conditions (5-6) for i hold. All solutions with initial conditions in Y i leaves this domain, crossing the boundary y(ξ) = y i .

Proof. Let us consider the function V (ξ) = y a (D n )-y(ξ) on Y i . Given Conditions (5-6), we get ∀ξ ∈ Y i :

y b (D i ) < y i < y(ξ) < y i < y a (D i ).
Since a constant dilution rate D i is applied, we can apply Lemma 3 to conclude that ẏ(ξ) > 0. Thus, V (ξ) is decreasing on Y i . Recalling that the trajectories are also bounded (Lemma 1), we can apply LaSalle invariance theorem [START_REF] Lasalle | The Stability of Dynamical Systems[END_REF] on the domain Ω 1 := {ξ ∈ Y i | x ≤ max(z(0), s in )/k, s ≤ max(s(0), s in )}. Given that the set of all the points in Ω 1 where V (ξ) = 0 is empty, any trajectory starting in Ω 1 will leave this region. The boundaries x = max(z(0), s in )/k and s = max(s(0), s in ) are repulsive (see Proof of Lemma 1). Finally, the boundary y(ξ) = y i corresponds to the maximum of V (ξ) on Ω 1 , so every trajectory will leaves this domain, crossing the boundary y(ξ) = y i .

Transition between two regions

Now we will characterize the transition between regions (as we have seen above, the intersection can be either a simple curve in the case of perfect measurements, or a region with non empty interior in the uncertain case):

Lemma 5 For any i ∈ {1, ..., n -1}, consider System (1) under Control law (4) with Conditions (5-6) for i, i + 12 . All trajectories with initial conditions in Ỹi ∪ Y i|i+1 enter the regular domain Ỹi+1 .

Proof. First, we consider i = n -1. We will follow the same reasoning as for the previous lemma, applying Lasalle theorem on a domain

Ω 2 := {ξ ∈ intR 2 + | x ≤ max(z(0), s in )/k, s ≤ max(s(0), s in ), y i-1 < y(ξ) < y † } with y i < y † < y i+2 . We can show that the functional V (ξ) = y a (D n ) -y(ξ) is decreasing on Y i whenever u = D i . Similarly, V (ξ)
is also decreasing on Y i+1 whenever u = D i+1 . Now under Control law (4), we have shown that V (ξ) is decreasing on the regular domains Ỹi and Ỹi+1 . V (ξ) is a regular C 1 function, and can be differentiated along the differential inclusion. On the switching domains Y i|i+1 , we have:

V (ξ) ∈ co ∂V ∂x f (ξ, D i ), ∂V ∂x f (ξ, D i+1 ) < 0.
Thus, V (ξ) is decreasing on Ω 2 . Following the proof of Lemma 4 concerning the boundaries, we can deduce that every trajectory will reach the boundary y(ξ) = y † , i.e. it will enter Ỹi+1 . For i = n -1, taking y n-1 < y † < y a (D n ), we can show similarly that V (ξ) is decreasing on Ω 2 so every trajectory will enter the region Ỹn .

Following the same proof, we can show that the reverse path is not possible, in particular for the last region: Lemma 6 Consider System (1) under Control law (4) with Conditions ( 5) for n -1, n, Condition [START_REF] Bernard | Non-linear qualitative signal processing for biological systems: application to the algal growth in bioreactors[END_REF] for n -1, and Condition [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]. The regular domain Ỹn is positively invariant.

Global dynamics

Proposition 2 Control law (4-7) globally stabilizes System (1) towards the point ξ a (D n ).

Proof. From Lemmas 5 and 6, we can deduce that every trajectory will enter the regular domain Ỹn , and that this domain is positively invariant.

System (1) under a constant control u(t) = D n has two non-trivial equilibria (see Proposition 1): ξ a (D n ), and ξ b (D n ). The growth proxy at these two points satisfy y a (D n ) > y n-1 and y b (D n ) < y n (Conditions (5,7)), so there is only one equilibrium in Ỹn : ξ a (D n ). Moreover, it is easy to check that Ỹn is in the basin of attraction of ξ a (D n ), therefore all trajectories will converge toward this equilibrium.

5 Implementation of the control law The global stability of the control law is based on Conditions (5-7). We consider the case where the regions are imposed (by technical constraints of the measurements) and we want to find the different dilution rates D i such that these conditions hold. The approach may be analytic or graphical, and will described elsewhere.

For example, for perfect measurements (A1) with equidistribution, it can be shown that it will always be possible to implement the desired control law, i.e. it is always possible to find a set of dilution rates D i such that Conditions (5-7) hold, whenever the measurement resolution is good enough (i.e. the number of regions is high enough). The result is illustrated by the simulations below.

Simulations

As an example, we consider the anaerobic digestion process, where the methane production rate is measured. Parameters, given in Table 1, are inspired from [START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF] (considering only the methanogenesis step). Our objective is to stabilize the equilibrium ξ a (D * ), with D * = 0.47 d -1 (which corresponds to a productivity of 92% of the maximal productivity).

For uncertain measurements, we use discrete time simulation. At each time step t k (with ∆t = 0.05d), when ξ(t k ) is in a switching region Y i|i+1 , we choose randomly the control u(t k ) between D i and D i+1 . In this case, we perform various simulations for a same initial condition.

Trajectories for various initial conditions are represented in the phase portrait for perfect and uncertain measurements, see Figure 2 and Figure 3. On top of both figures, the number of regions (three regions only) is too small in order to stabilize the given set-point ξ a (D * ): it is not possible to choose dilution rates such that Conditions (5-7) hold. In this case, some trajectories do not converge towards the set-point. Some regions have transitions towards the upper region, but also towards the lower one. There are sliding modes. This aspect will be further discussed in the next subsection.

On bottom of both figures, with one more region (four measurements), we can define a set of dilution rates such that Conditions (5-7) are fulfilled. The transition graph is deterministic (there is only one transition from a region to the upper one).

Actually, given the following perfect measurement set (considering equidistant region):

y i = y i+1 = i n -1 y n , i = 1, ..., n -1, with y n = 4 L CH 4 .L -1 .d -1 ,
we can choose the following dilution rates: For uncertain measurements, we increased each upper bound and decreased each lower bound by 10%. It appears that the same dilution rates can be chosen. Thus, all the trajectories converge towards the set-point (see Figure 3).

D 1 = 0.

When Conditions are not verified: risk of failure

We here detail what happens if Conditions (5-7) are not fulfilled, and in particular if there is a risk of washout. This point is illustrated by the top figures of Fig. 2 and Fig. 3.

First, given the previous analysis of the system, one can easily see that only the condition y b (D 1 ) < y 1 , i.e. D 1 < µ(s in ) is necessary to prevent a washout, so D 1 can be chosen with a safety margin in order to avoid such situation. Now, if Condition (6) does not hold for some i, the stable equilibrium ξ a (D i ) will be located in the region Y i , so some trajectories can converge towards this point instead of going to the next region. On the other hand, if Condition ( 5) is not are not fulfilled, some trajectories converge towards a singular equilibrium point (black diamond) with a sliding mode. Bottom: Conditions (5-7) are fulfilled, all the trajectories converge towards the set-point (dark circle). The frontiers are represented by the green dashed lines, switching regions are colored in gray. In these gray regions, the system is not deterministic. Open circle: washout.

fulfilled for some i > 1, the unstable equilibrium ξ b (D i ) will be located in the region Y i , and thus a trajectory can stay in a switching domain. Given that z converges towards s in , such trajectory will converge towards the intersection between the switching domain and the invariant manifold z = s in (see Figure 2, Figure 3 on top):

-For perfect measurements (A1), this gives rise to a sliding mode and the convergence towards a singular equilibrium point. -For uncertain measurements (A2), all the trajectories converge towards a line segment. In our simulation, they actually also converge towards a singular equilibrium point.

In all the cases, the trajectories converge towards a point or a line segment. Although it is not desired, this behavior is particularly safe (given that there is theoretically no risk of washout). Moreover, undesired equilibrium can easily be detected and the dilution rates can be changed accordingly (manually or through a supervision algorithm).

Conclusion

Given the quantized measurements, we were able to design (under some conditions) a control based on regions and transition between regions. These tools are similar to the ones of piecewise linear systems, and it is possible to draw a transition graph showing all the possible transitions. Moreover, we have seen that for some cases, singular behaviors (sliding modes) are possible on the boundaries between regions. We think that this kind of control on domains, and design of the resulting transition graph, is a promising approach, that we want to deepen in future works. This approach could be generalized to others classical systems, e.g. in mathematical ecology. First, we consider ϕ a D (s) on (0, s). Given that µ(s) is increasing and concave on this interval, we get ϕ a D ′ (s) < 0 on (0, s a (D)), and ϕ a D ′ (s) > 0 on (s a (D), s). Moreover, we have ϕ a D (s a (D)) = 0, so ϕ a D (s) ≥ 0 on (0, s), which proves (i).

Now we want to determine the sign of ϕ b D (s) on (s, +∞). For this purpose, we consider the equation ϕ b D (s) = 0. By replacing µ(s) and its derivative by their analytic expressions, this equation becomes: First, given that g D (s) represent the nullcline ẏ(ξ) = 0, we can check that we have (see Figure 1): ẏ(ξ) > 0 on {ξ ∈ intR 2 + | s < s, x < g D (s)} ∪ {ξ ∈ intR 2 + | s > s, x > g D (s)}.

Recalling that h a D (s) and h b D (s) are respectively the isolines y(ξ) = y a (D) and y(ξ) = y b (D), Lemma 2 allows to conclude that for ξ ∈ R 2 + such that y b (D) < y(ξ) < y a (D), we have ẏ(ξ) > 0.

⊓ ⊔

Proposition 1

 1 Consider System (1) with a constant dilution rate u(t) = D and initial conditions in the interior of the positive orthant. (i) If D < µ(s in ), the system admits a globally exponentially stable equilibrium ξ a (D) = s a (D), sin-sa(D) k . (ii) If µ(s in ) < D < µ(s), the system admits two locally exponentially stable equilibria, a working point ξ a (D) = s a (D), sin-sa(D) k and the washout ξ 0 = (s in , 0), and a saddle point ξ b (D) = s b (D), sin-s b (D) k , see Figure 1. (iii) If D > µ(s), the washout ξ 0 = (s in , 0) is globally exponentially stable.

1 .Lemma 3 Fig. 1 .

 131 Fig. 1. Phase portrait of System (1) with a constant dilution rate u(t) = D ∈ (µ(sin); µ(s)). Magenta lines: trajectories, cyan dashed lines: nullcline ẏ(ξ) = 0, green dash dotted lines: isolines y(ξ) = ya(D) and y(ξ) = y b (D), red dotted line: separatrix, black vertical line: s = s, dark circles: stable equilibria, open circle: unstable equilibrium.

5. 1

 1 How to fulfill Conditions[START_REF] Belta | Controlling a class of nonlinear systems on rectangles. Automatic Control[END_REF][START_REF] Bernard | Non-linear qualitative signal processing for biological systems: application to the algal growth in bioreactors[END_REF][START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF]

  19 d -1 , D 2 = 0.29 d -1 , D 3 = 0.4 d -1 , D 4 = 0.47 d -1 .

Fig. 2 .

 2 Fig.2. Trajectories (magenta lines) with Control law (4) for various initial conditions in the phase portrait, in the case of perfect measurements. Top: Conditions (5-7) are not fulfilled, some trajectories converge towards a singular equilibrium point (black diamond) with a sliding mode. Bottom: Conditions (5-7) are fulfilled, all the trajectories converge towards the set-point (dark circle). Open circle: washout. The frontiers are represented by the green dashed lines.

Fig. 3 .

 3 Fig.3. Trajectories (magenta lines) with Control law (4) for various initial conditions in the phase portrait, in the case of uncertain measurements. Top: Conditions (5-7) are not fulfilled, some trajectories converge towards a singular equilibrium point (black diamond) with a sliding mode. Bottom: Conditions (5-7) are fulfilled, all the trajectories converge towards the set-point (dark circle). The frontiers are represented by the green dashed lines, switching regions are colored in gray. In these gray regions, the system is not deterministic. Open circle: washout.

  Let us define ϕ j D (s) := g D (s) -h j D (s) for j = a, b. We have:µ ′ (s) 2 -D(s j (D) -s) µ ′ (s) kµ(s) 2 .

s a (D) k i s 2 -

 2 2k s s + k s s b (D) = 0. Given that s a (D)s b (D) = k s k i , the equation ϕ b D (s) = 0 has only one root s = s b (D). Moreover, we have: lim sցs ϕ b D (s) = -∞ and lim s→+∞ ϕ b D (s) = -∞. Given that ϕ b D (s) is continuous on (s, +∞), we finally conclude that on this interval, ϕ b D (s) ≤ 0 , i.e. g D (s) ≤ h b D (s). ⊓ ⊔ Proof of Lemma 3

Table 1 .

 1 Parameter values used for simulation.

	Parameter	Value
	μ	0.74 d -1
	ks	0.59 g.L -1
	ki	16.4 g.L -1
	k	30
	α	11 L CH4.g -1
	sin	30 g.L -1

if D < µ(sin), ξ b (D) does not exist and y b (D) < 0.

or if i = n -1, Conditions (5) for n -1, n, Condition (6) for n -1, and Condition[START_REF] Bernard | Dynamical model development and parameter identification for an anaerobic wastewater treatment process[END_REF].