Laurent Bienvenu

Ludovic Patey

Diagonally non-computable functions and fireworks

A set C of reals is said to be negligible if there is no probabilistic algorithm which generates a member of C with positive probability. Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable real, the class of coherent completions of Peano Arithmetic or the class of reals of minimal degrees. One class of particular interest in the study of negligibility is the class of diagonally noncomputable (DNC) functions, proven by Kučera to be non-negligible in a strong sense: every Martin-Löf random real computes a DNC function. Ambos-Spies et al. showed that the converse does not hold: there are DNC functions which compute no Martin-Löf random real. In this paper, we show that the set of such DNC functions is in fact non-negligible. More precisely, we prove that for every sufficiently fast-growing computable h, every 2random real computes an h-bounded DNC function which computes no Martin-Löf random real. Further, we show that the same holds for the set of reals which compute a DNC function but no bounded DNC function. The proofs of these results use a combination of a technique due to Kautz (which, following a metaphor of Shen, we like to call a 'fireworks argument') and bushy tree forcing, which is the canonical forcing notion used in the study of DNC functions.

1 Background 1.1 Negligibility, Levin-V'yugin algebra and DNC functions Let C ⊆ 2 ω be a class of infinite binary sequences (a.k.a. reals) and, consider the set {X ∈ 2 ω : X Turing-computes some element of C} By Kolmogorov's 0-1 law theorem, its (Lebesgue) measure is either 0 or 1. If it is equal to 0, the class C is said to be negligible, a terminology due to Levin and V'yugin [START_REF] Levin | Invariant properties of informational bulks[END_REF]. Equivalently, this means that there is no (infinite) probabilistic algorithm which generates a member of C with positive probability.

Various classes have been proven to be negligible, for example the Turing upper-cone of a non-computable A [START_REF] De Leeuw | Computability by probabilistic machines[END_REF] (or a countable class of such A's), the class of coherent completions of Peano Arithmetic [START_REF] Jockusch | Π 0 1 classes and degrees of theories[END_REF], the class of minimal degrees [START_REF] Paris | Measure and minimal degrees[END_REF], the class of shift-complex sequences [START_REF] Yu | Everywhere complex sequences and the probabilistic method[END_REF][START_REF] Khan | Shift-complex sequences[END_REF], etc. Likewise, many classes have been showed to be non-negligible (or 'typical'). Obviously classes of positive measure, such as the class of Martin-Löf random reals, are all non-negligible. Much more interesting examples were given by Kautz [START_REF] Steven | Degrees of random sequences[END_REF] 1 . He showed that the following are non-negligible: the class of hyperimmune sets, the class of 1generic reals, and the class of sets of CEA degrees. All three results are variations of the same technique. However, the way Kautz presents his technique is quite abstract and in some sense hides its true spirit, namely that what is being used is a probabilistic algorithm. In the paper [START_REF] Rumyantsev | Probabilistic constructions of computable objects and a computable version of Lovász local lemma[END_REF], Rumyantsev and Shen give a more explicit and intuitive explanation of the underlying algorithm, using the metaphor of a fireworks shop in which a customer is trying to either buy a box of good fireworks, or expose the vendor by opening a flawed one, and uses a probabilistic algorithm to maximize his chances of success. Following the tradition of colourful terminology in computability theory (Lerman's pinball machine, Nies' decanter argument...), we propose to refer to this method as a fireworks argument, the precise template of which will be recalled in the next section.

The dichotomy between negligibility and non-negligibility has received quite a lot of attention in recent years. We refer the reader to [START_REF] Barmpalias | The typical Turing degree[END_REF][START_REF] Bienvenu | Deep Π 0 1 classes[END_REF][START_REF] Stephen | Mass problems associated with effectively closed sets[END_REF] for a panorama of the existing results in this direction.

One class of particular interest in the study of negligibility is the class of diagonally non-computable functions, or 'DNC functions' for short. It consists of the total functions f : N → N such that f (n) = ϕ n (n) for all n, where (ϕ n ) is a standard enumeration of partial computable functions from N to N. By definition, there is no computable DNC function. On the other hand, as showed by Kučera [START_REF] Kučera | Measure, Π 0 1 classes, and complete extensions of PA[END_REF], the class of DNC functions is non-negligible. If we take the point of view of probabilistic algorithms, this is clear: since for all n there is only one value for f (n) to avoid (namely, ϕ n (n) if it is defined), so by picking f (n) at random between 0 and some large integer (e.g. 2 n ), we ensure a positive probability of success. The situation becomes more interesting when one restricts the class DNC to the subclass

DNC h = {f : N → N | f is a DNC function and (∀n)f (n) < h(n)}
where h is a given function, typically a computable one. The faster h grows, the easier it is to obtain an element of DNC h . And indeed, depending on the growth rate of h the class DNC h can be negligible or non-negligible (an unpublished result due to J. Miller, see [START_REF] Bienvenu | Deep Π 0 1 classes[END_REF] for a proof). This notion relativizes to an arbitrary oracle X: a DNC X function is a function f such that f (n) = ϕ X n (n) for all n. Likewise, we set

DNC X h = {f : N → N | f is a DNC X function and (∀n)f (n) < h(n)}
Of course, the stronger the oracle X, the harder it is to compute a DNC X function.

In this paper, we study the role of DNC functions in the setting of the Levin-V'yugin algebra, which is the algebra of Turing invariant Borel sets 'modulo negligibility'. That is, for two Turing-invariant sets A and B we write A B if A B is negligible. We say that A and B are equivalent if A B and B A. We call an equivalence class for this equivalence relation a Levin-V'yugin degree. Despite having been introduced some time ago and being a very natural notion, little work has been done on the Levin-V'yugin degrees, except for the seminal papers [START_REF] Levin | Invariant properties of informational bulks[END_REF][START_REF] Vladimir V'yugin | On Turing invariant sets[END_REF][START_REF] Vladimir | Algebra of invariant properties of binary sequences[END_REF] and some ongoing work by Hölzl and Porter. It is during discussions with the authors of the latter that a question arose. Kučera's result discussed above shows that reals of Martin-Löf random degree are also of DNC degree, so mlr dnc, where mlr is the set of sequences Turingequivalent to a Martin-Löf random real, and dnc those equivalent to a DNC function. On the other hand, it is well-known that there are DNC functions which do not Turing-compute any Martin-Löf random real (see subsection 1.3 below). But does this result translate in the setting of V'yugin's algebra? More precisely, is it then the case that mlr dnc (i.e., that dnc mlr is non-negligible)? In this paper, we answer this question in the affirmative. Namely, we prove: Theorem 1 (Main theorem) For every sufficiently fast-growing computable h, every 2-random (i.e., Martin-Löf random relative to ∅ ) real Z computes some f ∈ DNC h which does not compute any Martin-Löf random real.

Not only is this result interesting in its own right, but its proof is particularly instructive. It combines fireworks arguments with bushy tree forcing, a forcing notion used in many recent papers to study the properties of DNC functions [START_REF] Ambos-Spies | Comparing DNR and WWKL[END_REF][START_REF] Cai | Elements of Classical Recursion Theory: Degree-Theoretic Properties and Combinatorial Properties[END_REF][START_REF] François | Comparing the strength of diagonally non-recursive functions in the absence of Σ 0 2 induction[END_REF][START_REF] Greenberg | Diagonally non-recursive functions and effective Hausdorff dimension[END_REF][START_REF] Khan | Forcing with bushy trees[END_REF]. To our knowledge, our proof is the most elaborate use of a fireworks argument to date. It illustrates quite convincingly the power of the technique, and is likely to yield further applications in the future. Also interesting is the fact that if we want to study functions which are DNC relative to some oracle X, we can state a stronger theorem than what we would get from a straightforward relativization of Theorem 1.

Theorem 2 (Main theorem, relativized) For any real X and a sufficiently fast-growing computable h, every real Z which is both X-random and 2-random computes a function f ∈ DNC X h which itself computes no Martin-Löf random real.

A straightforward relativization of Theorem 1 would require Z to be X -random, and would give a function f which does not compute any X-Martin-Löf random real, but it could still compute a Martin-Löf random real. Note that taking X = ∅ gives us a stronger result than Theorem 1: Every 2-random real Z computes some f ∈ DNC ∅ h which is does not compute any Martin-Löf random real.

We finally remark en passant that '2-random' in the hypothesis of Theorem 2 cannot be substituted for 'Martin-Löf random', as shown by the following easy proposition.

Proposition 3 There is a Martin-Löf random real which computes no member of dnc mlr.

Proof. Take any hyperimmune-free Martin-Löf random Z. Because of hyperimmune-freeness, everything Turing-computed by Z is in fact tt-computed by Z. Moreover, every non-computable real which is tt-computed by a Martin-Löf random real is also of Martin-Löf random degree [START_REF] Demuth | Remarks on the structure of tt-degrees based on constructive measure theory[END_REF]. In particular, every DNC function it computes is of Martin-Löf random degree.

Remark. Readers who are experts in algorithmic randomness may not fully be satisfied with this last proposition, and rightfully so. Indeed, there is a wealth of algorithmic randomness notions between Martin-Löf randomness and 2-randomness, and it would be interesting to know precisely which levels of randomness it is sufficient for a real to have in order to compute a member of dnc mlr. A more precise answer is the following: weak-2-randomness is not sufficiently strong, but Demuth randomness is. For the first part of this assertion, observe that in the proof of Proposition 3, one can take Z to be weak-2-random (indeed there are hyperimmune-free weak-2-randoms). The second part is more involved and requires a fine analysis of fireworks arguments which will be done in a forthcoming paper by Christopher Porter and the first author. However, the crude '2-randomness' bound we use in this paper is sufficient for our main goal, which is to prove the non-negligibility of dnc mlr.

Notation and terminology

Unless otherwise specified, a string is a finite sequence of integers. We denote the set of strings by ω <ω , by λ the empty string and by |σ| the length of a string σ. Unless specified otherwise, a sequence is an infinite list of integers. The set of sequences is denoted by ω ω . We will sometimes need to consider binary sequences (which we also call reals), the set of which we denote by 2 ω . The n-th element of a string or sequence Z is denoted by Z(n -1) and Z n denotes the finite sequence consisting of the first n values of Z. A string τ is a prefix of a string σ (we also say that

σ extends τ ), noted τ σ, if |σ| ≥ |τ | and σ |τ | = τ . A sequence Z ∈ ω ω is said to be a DNC function (resp. X-DNC function) if for all n, Z(n) = ϕ n (n) (resp. Z(n) = ϕ X n (n))
, where (ϕ n ) is a standard enumeration of partial computable functions from N to N with oracle.

A tree T ⊆ ω <ω is a set of strings closed downwards under the prefix relation, i.e., if σ ∈ T and τ σ then τ ∈ T . Members of a tree are often referred to as nodes. A node σ is a child (or immediate extension) of a node τ in a tree T if τ σ, τ and σ are nodes of T , and |σ| = |τ | + 1. A leaf of a tree T is a node with no immediate extension in T . A path in a tree T is a sequence f such that every initial segment of f is in T . The class of paths of a tree T forms a closed set denoted by T .

Bushy trees

In this section we present the notion of bushy tree and its main properties. Roughly speaking, bushiness is a purely combinatorial property, which states that a tree is 'sufficiently fast branching', in a way that guarantees the existence of a DNC path through the tree. The idea of bushy tree was invented by Kumabe, who used it to construct a DNC function of minimal Turing degree (see [START_REF] Kumabe | A fixed-point-free minimal degree[END_REF] for an exposition of this result), which in particular shows that there is a DNC function which computes no Martin-Löf random real (as no Martin-Löf random real can have minimal degree). Since then, bushy trees have been successfully applied to the study of DNC functions. We refer the reader to the excellent survey of Khan and Miller [13].

Definition 1 (Bushy tree) Fix a function h and a string σ ∈ ω <ω . A tree T is h-bushy (resp. exactly h-bushy) above σ if every τ ∈ T is comparable with σ and whenever τ σ is not a leaf of T , it has at least (resp. exactly) h(|τ |) immediate children. We call σ the stem of T . Definition 2 (Big set, small set) Fix a function h and some string σ ∈ ω <ω . A set B ⊆ ω <ω is h-big above σ if there exists a finite tree T which is h-bushy above σ and such that all leaves of T are in B. If no such tree exists, B is said to be h-small above σ.

Bushy tree forcing consists generally of building decreasing sequences of infinite bushy trees T 0 ⊇ T 1 ⊇ T 2 . . . where T i is h-bushy over σ i for some string σ i . Each stem σ i is an initial segment of the constructed sequence. During the construction we maintain a set B of "bad" extensions, i.e., of strings to avoid. This set must remain g-small above σ i at any stage for some function g. Bushy tree forcing is especially convenient for building DNC functions. Let B DNC be the set of strings which are not initial segments of any DNC function:

B DNC = σ ∈ ω <ω : (∃e < |σ|) ϕ e (e) ↓= σ(e)
One can easily see that B DNC is 2-small above λ.

The following three lemmas are at the core of every bushy tree argument. We state them without proof and refer the reader to [START_REF] Khan | Forcing with bushy trees[END_REF] for details.

Lemma 1 (Concatenation) Fix a function h. Suppose that A ⊆ ω <ω is h-big above a string σ. Let (S τ ) τ ∈A be a family of subsets of ω <ω . If S τ ⊆ ω <ω is h-big above τ for every τ ∈ A, then

τ ∈A S τ is h-big above σ.
The concatenation property is often used in the following contrapositive form: If we are given a finite tree T h-bushy above some string σ and a "bad" set B of extensions to avoid which is h-small above σ, then there exists a leaf τ of T such that B is still h-small above τ . In particular, if a set A is h-big above σ, there exists an extension τ of σ which is in A and such that B is still h-small above τ .

Lemma 2 (Smallness additivity) Suppose that B 1 , B 2 , . . . , B n are subsets of ω <ω , g 1 , g 2 , ..., g n are functions, and σ ∈ ω <ω . If B i is g i -small above σ for all i, then i B i is ( i g i )-small above σ. Lemma 3 (Small set closure) We say that B ⊆ ω <ω is g-closed if whenever B is g-big above a string ρ then ρ ∈ B. Accordingly, the g-closure of any set B ⊆ ω <ω is the set C = {τ ∈ ω <ω : B is g-big above τ }. If B is g-small above a string σ, then its closure is also g-small above σ.

As explained in [START_REF] Khan | Forcing with bushy trees[END_REF], Lemma 3 is very useful during our constructions. We are given a "bad" set B of nodes, which is g-small above σ where σ is a partial approximation of the object we are constructing. We want to extend σ still avoiding B and in particular preserving g-smallness of B. Lemma 3 enables us to consider w.l.o.g. that if ρ is an extension of σ which does not preserves g-smallness of B, then ρ is already on B.

The next lemma is very simple and yet central in this paper. It expresses the fact that if a set B is sufficiently small in an h-bushy tree T , then there is only a small probability that a random path of the tree meets B (has a member of B as prefix). By "random path", we mean the probability distribution over paths induced by a downward random walk where one starts at the root and at each step goes from a node to one of its children, all children being given the same probability of being picked.

Lemma 4 Fix two functions positive functions g and h with g ≤ h. If T is an infinite tree h-bushy above λ and B ⊆ T is a g-small above λ, then the probability that a random path of T avoids B is greater than

i∈ω 1 - g(i) h(i)
Note that this quantity is positive if and only if

g(i)/h(i) < ∞, due to the identity i∈ω (1 -e i ) = exp -i∈ω ln(1 -e i ) and the asymptotic estimate -ln(1 -x) = x + o(x).
Proof. Without loss of generality, we can assume that B is g-closed (otherwise, take its closure). We prove by induction over n that the probability of having avoided B by the time we reach depth n is at least n-1 i=0 1 -g(i)/h(i) (a quantity equal to 1 for n = 0, by convention). The lemma immediately follows from this fact.

The base case n = 0 is trivial as λ is the only such node and B is g-small above λ. Assume it is true for some depth n. Suppose we have reached a node ρ ∈ T of length n such that B is g-small above ρ. By h-bushiness of T , ρ has at least h(n) immediate extensions. If B were g-big above g(n)-many immediate extensions of ρ then B would be also g-big above ρ, by g-closedness. Hence B is g-small above at least h(n) -g(n) immediate extensions of ρ. It follows easily that, conditional to having reached ρ, the probability to avoid B at the next level is at least 1 -g(n)/h(n). This finishes the induction.

Remark. Lemma 4 makes no computability assumption on T and B. However, when T is computable, taking a path of T at random can be performed using a probabilistic algorithm, which will then produce a path avoiding B with probability at least n-1 i=0 1 -g(i)/h(i) (and this still makes no computability assumption about B). 2 will do) and take an h-bushy tree T . Now, take a path of T at random. Since, as we saw above, B DN C is 2-small in T , the previous lemma tells us that the probability to get a path of the tree which avoids B, and thus is a DNC function, is at least i (1 -2/h(i)), thus is positive.

Now we see how randomness helps us compute DNC functions: take a computable function

h such that i (1 -2/h(i)) > 0 (which is equivalent to i 1/h(i) < ∞; for example, h(n) = (n + 1)

Fireworks arguments

A fireworks argument can be seen as "probabilistic forcing" for Σ 1 properties. It is best illustrated by the following theorem, due to Kautz: there exists a probabilistic algorithm which with positive probability produces a 1-generic real (more precisely, every 2-random real computes a 1-generic real). Let us present the argument in a more abstract way so as to better fit the setting of the next section, where we will (implicitly) force with bushy trees. Let (P, ≤) be a computable partial order, and let W 1 , W 2 , ... be a list of uniformly c.e. subsets of P. We want to get a probabilistic algorithm to generate an infinite list p 0 ≥ p 1 ≥ p 2 ≥ ... such that for every set W i , the requirement R i holds, where R i says that there exists a j such that either p j ∈ W i holds or for every q ≤ p j , q / ∈ W i . (For example, to get Kautz's result, on takes for P the set of finite strings, where σ ≤ τ if σ extends τ and the W i are all c.e. sets of strings. In this paper, P will typically consist of a set of finitely represented bushy trees, and T ≤ T will mean that T is a subset of T ).

Suppose we have already built the sequence of p j up to some p k , and we want to satisfy the requirement R i . If we did not care about the effectivity of the construction, we could easily satisfy the requirement by distinguishing two cases: Case 1 (the Π 1 case): there is no p ≤ p k such that p ∈ W i . In this case nothing needs to be done, R i is already satisfied! Case 2 (the Σ 1 case): there is some p ≤ p k such that p ∈ W i . Here it suffices to search for such a p (which can be done effectively since W i is c.e.), and set p k+1 = p after which R i is satisfied.

Although both cases only require effective actions (do nothing or effectively search for a p , respectively), the problem is that one cannot computably distinguish between them, as being in Case 2 is only a c.e. event (hence the name 'Σ 1 case'). And indeed in general there is no deterministic algorithm to build a sequence of p j satisfying all requirements (otherwise one could, for example, computably build a 1-generic).

There is however, a probabilistic algorithm which builds such a sequence of p j 's with positive probability. It works as follows. We start with any p 0 ∈ P. Next, for each i, we pick an integer n i at random between 1 and N (i), where N is a fixed computable function (the faster N grows, the higher the probability of success of the algorithm will be). Moreover, for each i, we let c i be a counter, initialized at 0, which will count how many wrong passive guesses we have made for requirement R i .

By "passive guess", we mean that in the construction of the p j 's, we assume at some step k that we are in the Π 1 case, i.e., that no q ≤ p k is in W i . It is a passive guess because as we saw, if it is indeed true, requirement R i is already satisfied and no particular action is needed. Of course, this guess may be incorrect but since W i is c.e., if it is incorrect we will discover this at some later stage k of the algorithm. When this happens, we make a new assumption that there are no q ≤ p k in W i and so on. If at any point we make a correct passive guess, requirement R i is satisfied. There is however a danger that all the passive guesses we make for requirement R i turn out to be wrong. What we do is use the number n i as a cap on how many times we allow ourselves to make a wrong passive guess for R i . If for some i the cap n i is reached at stage k, we then make the opposite guess ("active guess"), i.e., that there is a q ≤ p k such that q ∈ W i holds, try to find such a q and take it as our p k+1 , thus satisfying requirement R i . This guess is "active" because we need to find such a q before doing anything else. But at least, as we said above, since W i is a c.e. set, such a q can be effectively found if it exists. Then we take p k+1 = q. This active/passive guessing strategy is still not guaranteed to work, as one bad case remains: if we make an incorrect active guess for some R i , we then get stuck while waiting for a q in W i which we will never find. However, this is the only bad case: if it does not happen for any R i , then the algorithm succeeds in producing a sequence p 0 ≥ p 1 ≥ p 2 ≥ ... as wanted. Indeed, for every i, either it makes a good passive guess for R i that never turns out to be wrong, meaning that for some p s , no q ≤ p s is in W i , or it makes a good active guess that some q ≤ p s is in W i , eventually finds such a q, and take it as an extension.

Why can the probability of success of the algorithm be made arbitrarily close to 1? The reason is the following key observation: For all i, if all {n j : j = i} are fixed, then there is at most one value of the random variable n i for which we get stuck in a loop while trying to satisfy requirement R i . Indeed, suppose we get stuck having chosen a value n i . This means that we made n i -1 incorrect passive guesses and then one incorrect active guess. Any other choice n i < n i would have been fine, because our n i -th guess would then have been a correct active guess and a q in W i . And any other choice n i > n i would also have been fine, as in this case our n i -th guess would have been a correct passive guess. Thus, the probability to get stuck because of requirement R i is at most 1/N (i), giving a total probability of success of the algorithm of at least 1i 1/N (i), which can be made arbitrarily close to 1 for a well chosen N . Now the last thing we need to check is how much randomness (in the sense of algorithmic randomness) is needed for this probabilistic algorithm to work. Let us explain what we mean. A probabilistic algorithm is nothing but a Turing functional Γ with access to a 'random' (in the classical sense) oracle R ∈ 2 ω . This is the R used by the algorithm to make its random decisions. What we have argued above is that the failure set of the algorithm U = {R | Γ R is either undefined or fails to satisfy some R i } has probability < 1 (by 'undefined' we mean that the algorithm does not produce an infinite sequence of p j 's).

In fact, this probability can be made arbitrarily small, therefore fireworks arguments do not give us one algorithm but a uniform family of algorithms: For any given integer m, one can design, uniformly in m, a probabilistic algorithm which fails with probability at most 2 -m (it suffices to choose the function N such that 1/N (i) < 2 -m ). Call Γ m the corresponding algorithm, and consider

U m = {R | Γ R
m is either undefined or fails to satisfy some R i } which is of measure at most 2 -m . The set m U m , which is the set of R's on which all the algorithms Γ m fail is a null set. This means that if R is 'sufficiently random', in the sense of effective randomness, it does not belong to all U m and thus some algorithm Γ m succeeds using R. Which level of algorithmic randomness is actually needed? One should observe that every U m is in fact an effectively closed set relatively to ∅ . Indeed, as we have seen, the only case the algorithm Γ m fails is when it waits in vain for a q extending some condition p and belonging to some W i . If such a situation happens, it does so at some finite stage, i.e., having used only a finite initial segment of R, hence U m is open. Moreover, testing whether the algorithm Γ m is stuck at a given stage can be done using ∅ : indeed, the predicate [(∀q ≤ p) q / ∈ W i ] is a Π 1 -predicate uniformly in p and i.

Thus, (U m ) m∈N is a ∅ -Martin-Löf test, which shows that every 2-random real computes, via some functional Γ m , an infinite sequence p 0 ≥ p 1 ≥ p 2 ≥ ... such that for every i there is a j such that either p j ∈ W i holds or for every q ≤ p j , q / ∈ W i , as wanted.

Main result

We shall now see how to combine fireworks arguments with bushy tree forcing to prove Theorem 2. We first provide an informal presentation of the proof. Full details will be given in the next section.

Proof overview

For this construction, we will need a hierarchy of very fast growing computable functions

g 0 g 1 g 2 . . .
(g g is an informal notation: it means that g grows 'much faster' than g) and another fast-growing function h (which is meant to grow faster that all the g i but with certain restrictions). At this point, we do not specify precisely what functions g i and h we take. We will see during the construction which properties they need to have to make the argument work.

Contrary to most bushy tree arguments, the whole construction will happen within a single tree T , which is exactly h-bushy:

T = {σ ∈ ω <ω : (∀i) σ(i) < h(i)}
Typically, a bushy tree forcing argument constructs a sequence T 0 ⊇ T 1 ⊇ . . . of bushy trees, and the path obtained by forcing is in the intersection of all of those. We will not need such a sequence in our argument. However, some steps of the construction can be understood as "locally" taking a subtree of T . What we keep from other bushy tree arguments is the idea of maintaining during the construction a small set of bad strings to be avoided. But again, there is a difference in our construction: to build a DNC X function by forcing, one usually starts with the initial small bad set

B DNC = σ ∈ ω <ω : (∃e < |σ|) Φ X e (e) ↓= σ(e)
We will not do this as we need our bad set of strings to be c.e. at all times. Our fireworks argument will (with high probability) build an A which does not compute any Martin-Löf random real. It is only an a posteriori analysis of the construction which will allow us to conclude that A is also DNC X with high probability. In the absence of any other requirement, we would just build A value by value, picking for each n the value of A(n) at random between 0 and h(n) -1. This would give us a probability of avoiding B DNC of at least n (1 -1/h(n)), which is positive for h fast-growing. But of course there are other requirements our construction needs to meet, namely all the requirements of the form:

R Γ,d : either Γ A is partial or there is an n such that K(Γ A n) < n -d
where d is an integer, Γ is a Turing functional from ω <ω to 2 ω , and K is the prefix-free Kolmogorov complexity function. (Here we use the Levin-Schnorr theorem that a real Y is Martin-Löf random if and only if for some constant d, and all n, K(Y n) ≥ n -d).

Let us see how we would ideally like to satisfy such a (single) requirement. Suppose we have already built some string σ ∈ T of length k and consider the set

S = {τ ∈ T : |Γ τ | ≥ h(k -1)}
where |Γ τ | ≥ h(k -1) means that the Turing reduction Γ produces at least h(k) bits of output on input τ , and distinguish two cases:

• Case 1: S is g k -small above σ. In this case there is essentially nothing to worry about.

We can just continue to build A by making random choices. The probability that we hit the set S at some point is small, namely it is at most 1 -i≥k+1 (1 -g k (i)/h(i)) (by Lemma 4), and recall that h(i) ≥ g k+1 (i) g k (i) for i ≥ k + 1. And if we do not hit S, then Γ A will end up being partial, therefore satisfying R Γ,d .

• Case 2: S is g k -big above σ. Each element τ ∈ S is such that |Γ τ | ≥ h(k -1), therefore
we can decompose S as

S = |ρ|=h(k-1)
S ρ where S ρ = {τ ∈ S | Γ τ ρ} There are 2 h(k-1) strings of length h(k -1), therefore by Lemma 2, there must be a ρ * such that S ρ * is g k /2 h(k-1) -big above σ (note that in this expression, g k is a function while h(k -1) is just an integer). Since being big is a Σ 1 -property, such a ρ * can be found effectively knowing σ and Γ, and thus the first such ρ * found with this effective search must satisfy

K(ρ * ) ≤ K(σ) + K(Γ) + c ≤ 2 i≤k-1 log h(i) + K(Γ) + c (1)
for some fixed constants c, c (the last term is due to the fact that σ is a list of k -1 integers such that the i-th integer is less than h(i), therefore has complexity less than 2 log h(i)). Since |ρ * | = h(k -1) we have

K(ρ * ) -|ρ * | ≤ 2 i≤k-1 log h(i) -h(k -1) + K(Γ) + c
If h grows fast enough, and k is sufficiently large then this last inequality implies K(ρ * ) ≤ |ρ * | -d. Thus, any A which passes through a node in S * ρ satisfies requirement R Γ,d . Moreover, since S ρ * is g k /2 h(k-1) -big above σ, this means by definition that there is a finite g k /2 h(k-1) -bushy tree T ⊆ T of stem σ all of whose leaves are in S ρ * . Then, what we can do is effectively find the tree T and temporarily restrict our random walk to T (picking at each step the next value at random among nodes of T ) until we reach a leaf of T . This guarantees the satisfaction of R Γ,d and the probability that we hit B DNC during this temporary restriction is less than 1 -i≥k (1 -2 h(k-1) /g k (i)), which can be made small if g k is well-chosen.

Of course, the problem is that, having built σ, we cannot effectively determine whether we are in Case 1 or in Case 2. This is where the fireworks argument comes into play. We are going to pick a number n = n(Γ, d) between 1 and some large N = N (Γ, d), and assume up to n times that we are in Case 1 (the Π 1 case), and if proven wrong n times, we will then wait until proven that we are in Case 2 (the Σ 1 case), and if so, implement the above strategy for Case 2. As with other fireworks arguments, the probability that we decide to wait at the wrong moment is at most 1/N , which we can thus make arbitrarily small. These considerations are enough to give us a strategy which ensures, with arbitrarily high probability, the satisfaction of a single requirement R Γ,d while avoiding the set B DNC with high probability. However, there is a subtle point to address when we try to satisfy several requirements in parallel. Indeed, what can happen is that the strategy for a first requirement has made the assumption that some set S is g k -small in T -and thus small probability of being hit -while a strategy for a second requirement needs to make a temporary restriction to a tree T . While the probability to hit S was small for a random walk within T , it could happen that the random walk restricted to T has a much greater probability to hit S. This is what the assumption g i g j for i < j takes care of: Whenever a strategy needs to make such a restriction to a g k /2 h(k-1) -bushy subtree, we will have that g k /2 h(k-1) grows much faster than the g j 's previously considered in the proof, and thus, if a set S is g j -small, it will still be unlikely that we hit S while choosing a path of a g k /2 h(k-1) -bushy tree at random for any k > j.

The full algorithm and formal proof of correctness

We now state the precise theorem regarding the probabilistic algorithm discussed above. The analysis of the level of effective randomness required will be done separately.

Theorem 4 Let X ∈ 2 ω and h be a sufficiently fast-growing computable function. For every rational ε > 0, one can effectively design a probabilistic algorithm (= Turing machine with random oracle) which, with probability at least 1 -ε, produces an A ∈ ω ω such that (1) A is DNC X h and (2) A computes no Martin-Löf random real.

Let m = m(ε) (we will argue at the end of the proof that choosing m large enough guarantees that the algorithm succeeds with probability at least 1 -ε). Let us first define the functions g k and h we alluded to above. Set g 0 to be the function defined by g 0 (n) = 2 n+m . Then, for all k > 1, inductively define

g k (i) = 1 if i < k g k-1 (i) • 2 g k-1 (k-1)+i+m otherwise Finally define for all k h(k) = g k (k)
Let us now give the details of the algorithm. First, number all the requirements R Γ,d and call R i the i-th requirement. As usual, we organize them in a way that all requirements receive attention infinitely often, and only one requirement receives attention at any given stage. We will see during the verification that a small extra assumption should be added, namely that every requirement should be considered for the first time at some 'late enough' stage.

Stage 0: Initialization. The first thing we do is pick for all i a number n i at random between 1 and 2 i+m . Then, we initialize σ to be the empty string. For all i, set a counter c i originally equal to 0.

Loop (to be repeated indefinitely). Suppose that the values σ(0), ..., σ(k -1) of σ are already defined (the last one being between 0 and h(k -1) -1). Assume some requirement R i = R Γ,d receives attention.

(a) If this requirement receives attention for the first time, we make for this requirement the assumption that the set

S = {τ ∈ T : |Γ τ | ≥ h(k -1)}
is g k -small above the current σ (again, note that this is a Σ 1 assumption so if it is false it will be discovered to be so at some finite stage).

(b) If it does not receive attention for the first time, we check whether the current assumption made for this requirement still appears to be true at stage k.

(1) If it does, we maintain this assumption and simply pick the value of σ(k) at random between 0 and h(k) -1.

(2) If the assumption is discovered to be false, we increase our 'error counter' c i by 1.

(i) If the new value of c i remains less than n i , we forget our previous assumption for requirement R i and make a new assumption: we now assume that the set

S = {τ ∈ T : |Γ τ | ≥ h(k -1)} is g k -small above (the current) σ. (ii)
If the new value of c i is equal to n i , we then wait until we find, for some ρ of length h(k -1), a set S ρ = {τ ∈ S | Γ τ ρ} which is g k /2 h(k-1) -big above σ. When this happens, i.e., when we find a finite subtree T of T of stem σ which is g k /2 h(k-1) -bushy above σ and all of whose leaves are in S ρ , we choose the next values of σ by a downward random walk restricted to T until we reach a leaf of T (note that we may never find such a tree in which case our algorithm gets stuck at this stage and thus fails to even return an infinite sequence). When a leaf is reached, we mark the i-th requirement as satisfied.

The sequence A returned by the algorithm is the minimal element of ω ≤ω extending all the values taken by σ throughout the algorithm. We now turn to the verification of our algorithm, which we have already done for the most part in Section 2.1. We do this via a series of claims.

Claim 1. The probability that the algorithm gets stuck at some substage of type (b.2.ii) (waiting to find a big tree T which does not exist) is at most 2 -m+1 .

Proof. This is standard fireworks calculation: all other randomly chosen values being fixed, there at most one value of n i which causes the algorithm to get stuck at (b.2.ii) because of requirement R i . And since n i is chosen randomly between 1 and 2 i+m , the probability that the algorithm gets stuck at (a.2.ii) because of requirement R i is at most 2 -i-m . Thus, over all requirements, this gives a probability of at most 2 -m+1 . Claim 2. Conditionally to our algorithm returning an infinite sequence, the probability that all requirements are met is at least 1 -2 -m+2 .

Proof. Let us look at a given requirement R i = R Γ,d . This requirement receives attention infinitely often until satisfied. This means that if the algorithm does not get stuck, one of the following happens

• at some point it makes for R i a correct assumption during substep (a) or (b.2.i) or,

• the i-th requirement causes the algorithm to enter some substep (b.2.ii) but a tree T is found thereafter.

These two cases are mutually exclusive. In the first case, for some k a set

S = {τ ∈ T : |Γ τ | ≥ h(k -1)}
is correctly assumed to be g k -small above the current σ. For any later stage of the algorithm (i.e., at stages i ≥ k), the value of σ(i) is chosen at random among h(i) values, where h(i) is either equal to h(i) or to g k (i)/2 h(k -1) for some k > k in case some other strategy has caused a temporary restriction of the tree. The latter quantity is the smaller of the two, and by definition of the g k 's, it follows that h(i) ≥ 2 i+m g k (i).

By the calculations of the proof of Lemma 4, it follows that in this case, the probability of hitting a node of S at some later stage is at most

1 - i≥k 1 - g k (i) h(i) ≤ 1 - i≥k 1 - g k (i) 2 i+m g k (i) ≤ i≥k 2 -i-m ≤ 2 -k-m+1
In the second case the requirement R i is always satisfied. Indeed, in this case, we find a string ρ * of length h(k -1) and finite tree T whose leaves are contained in S ρ * = {τ ∈ S | Γ τ ρ * } and then make a random walk within T until we reach a leaf. As explained in the previous section, we then have

K(ρ * ) ≤ K(σ) + K(Γ) + c ≤ 2 i≤k-1 log h(i) + c + K(Γ)
for some fixed constants c, c . But |ρ * | = h(k -1), so

K(ρ * ) -|ρ * | ≤ 2 i≤k-1 log h(i) + K(Γ) -h(k -1) + c (2)
for some fixed c . By construction of h, h(k -1) -2 i≤k-1 log h(i) tends to ∞, thus for k large enough (and this 'large enough' can be found computably), the value of above expression is less than -d, which means that the requirement R Γ,d is satisfied as soon as we reach a leaf of T . We thus add the technical extra assumption that requirement R Γ,d is only allowed to receive attention at stage k if in the above expression the right-hand side is smaller than -d. This essentially changes nothing since it only prevents every requirement to receive attention for finitely many stages.

Given a requirement R Γ,d , we say that stage k is good for R Γ,d when after having built σ k, in the next iteration of the loop, R Γ,d receives attention and either a true assumption is made at steps (a) or (b.2), or stage (b.2.ii) is reached and a tree T is found. To every requirement corresponds exactly one good stage (and no two requirements have a good stage in common). As we have just argued, if k is the good stage for a requirement, the probability that the requirement is satisfied, conditional to the algorithm returning an infinite sequence, is at least 1 -2 -k-m+1 . Over all requirements, this gives a probability of at least 1k 2 -k-m+1 = 1 -2 -m+2 . Claim 3. The probability that we hit a node of B DNC during the algorithm is at most 2 -m+1 .

Proof. There is at most one 'bad' value of σ(n) the algorithm can choose (namely, ϕ X n (n), if it is defined). Whenever a value σ(n) is chosen at random for some n, it is either chosen at random between 0 and h(n) -1 or, in case of a temporary restriction to a subtree, between 0 and g k (n)/2 h(k-1) -1 for some k ≤ n (in case of a temporary restriction of the tree). Both quantities are at least 2 n+m , by construction. This gives a total probability of at most

n 2 -n-m = 2 -m+1 of hitting B DNC .
The theorem immediately follows from the three claims: the probability that an infinite sequence A is returned and all requirement are satisfied is at least 1

-2 -m+1 -2 -m+2 -2 -m+1 = 1 -2 -m+3 .

How much randomness do we need?

It remains to conduct, like in Section 1.4, an analysis of the level of algorithmic randomness needed to make the algorithm work. The attentive reader will notice that there are two uses of randomness in the construction: the first one to choose the sequence (n i ) which will make the fireworks argument work (i.e., the algorithm won't get stuck), and the second one which helps choosing a node of the tree at random during the construction. For a given k, consider the algorithm Γ k with probability of success at least 1 -2 -k . There are three ways in which it can fail:

1. It could get stuck at some stage b.2.ii.

2. It could hit a node which belongs to B DNC .

3. It could make at some stage k a true assumption that a set S is g k -small, but nonetheless hit a node of S later on (when it hits a node of the set S corresponding to a wrong assumption, this is not a problem because the assumption will be discovered to be wrong later on and a new assumption will be made for the requirement).

Technically, the occurrence of the third case does not necessarily mean that the algorithm has failed, but if neither of these three cases occur the algorithm succeeds, as explained above. The total probability of such events is at most 2 -k . Moreover, if any event of the above three types happens, it does so at some finite stage, thus after having used only finitely many bits of the random oracle. The open set of oracles that cause events of type 1 and 3 to happen can be effectively enumerated relatively to ∅ . Indeed, for the first type this is exactly what is explained in Section 1.4, namely that ∅ can check at any given given stage whether the algorithm is stuck at stage b.2.ii. The third type can also be checked using ∅ : indeed, the sets we assume to be g k -small are c.e. sets and since g k is computable uniformly in k, the smallness can be checked using ∅ and checking whether a node chosen at some stage of the algorithm is in S can also be done effectively in ∅ (since S is c.e.). Thus we can design a ∅ -Martin-Löf test (U ∅ k ) k∈N such that U ∅ k covers the set of oracles which make the algorithm Γ k fail because of cases 1 or 3.

The second type of failure is even easier to analyse. The set B DNC is X-c.e., so the set of oracles which cause the algorithm to hit a node of B DNC is effectively open relative to X. Thus we can design a X-Martin-Löf test (V X k ) k∈N such that V X k covers the set of oracles which make the algorithm Γ k fail because of case 2. This finishes the proof of Theorem 2: if Z is X-random and 2-random, for k large enough it will be outside U ∅ k and outside V X k , hence the algorithm Γ k will succeed on input Z.

Further results

The proof of Theorem 2 can be adapted to prove more results on the class of DNC functions in V'Yugin's algebra. For example, in this proof, we construct a real of DNC X degree which computes no Martin-Löf random real, but we do so using Kolmogorov complexity in a rather liberal way. By being very slightly more precise we can get a stronger result.

Theorem 5 Let X ∈ 2 ω . For every fixed computable function h 0 , for every sufficiently fastgrowing h, every real Z which is both X-Martin-Löf random and 2-random computes a DNC X h function which computes no DNC h 0 function. This is a stronger theorem than Theorem 2 because, as we saw in Section 1.1, when h 0 is sufficiently fast-growing, every Martin-Löf random real computes a DNC h 0 function. Again, the fact that dnc h 0 is strictly contained in dnc h 1 when h 1 grows sufficiently faster than h 0 is known (see [START_REF] Khan | Forcing with bushy trees[END_REF]), but our theorem shows that this separation holds in V'Yugin's algebra as well.

The first thing to do to adapt our previous proof is to use the relationship between Kolmogorov complexity and DNC functions discovered by Kjos-Hanssen et al. [START_REF] Kjos-Hanssen | Kolmogorov complexity and the recursion theorem[END_REF]. For a function h : N → N, call h-complex a real A ∈ 2 ω such that K(X h(n)) ≥ n -O(1). Call a real complex if it is h-complex for some computable h. Kjos-Hanssen et al. proved that a real computes a DNC function with computable bound if and only if it computes a complex real. More precisely: for any computable h 0 , for any computable h 1 which grows sufficiently faster than h 0 , if a real A computes a DNC h 0 function, it computes an h 1 -complex real, and if A computes an h 0 -complex real, it computes a DNC h 1 function.

Proof of Theorem 5. By the correspondence between DNC functions and complex reals, it suffices to show the following: For every fixed computable function h 0 , for every sufficiently fast-growing h, every real Z which is both X-Martin-Löf random and 2-random computes a DNC X h function which computes no h 0 -complex function. We modify the proof of Theorem 2 as follows. The requirements now become: R Γ,d : either Γ A is partial or there is an n such that K(Γ A h 0 (n)) < n -d

The new functions g i 's are defined by

g k (i) = 1 if i < k g k-1 (i) • 2 h 0 (g k-1 (k-1)
)+i+m otherwise and again, h(k) = g k (k) for all k. The sets S considered in Step (a) of the algorithm are now

S = {τ ∈ T : |Γ τ | ≥ h 0 (h(k -1))}
The rest of the construction remains the same. The estimate (1) is left unchanged by this modification, but we now have |ρ * | ≥ h 0 (h(k -1)). Together with (1), for k large enough, this guarantees the satisfaction of R Γ,d (where Γ is the reduction with respect to which ρ * is defined).

Using another adaptation of the proof of Theorem 2, we can also transfer to V'Yugin's algebra the following result, due to Miller (see [13, section 3]): there exists a DNC function which computes no complex real. Namely, the following holds.

Theorem 6 Let X ∈ 2 ω . Every real Z which is both X-Martin-Löf random and 2-random computes a DNC X function which computes no DNC h function for any computable h.

Although the general structure is similar, this second adaptation is not straightforward and quite a number of important changes are needed. The first thing to notice is that there is obviously no hope to conduct the whole construction in an h-bushy tree for a computable h since we want A to compute no complex real, which is equivalent to computing no computably bounded DNC function. Thus we will need to work in the full tree ω ω and at each level k, choose dynamically the interval [0, h(k)] for the random choice of σ(k).

For this construction, the requirements are of the form:

R Γ,ϕ,d : Γ A is partial, or ϕ is partial, or there is an n such that K(Γ A ϕ(n)) ≤ n -d
where the Γ's are still Turing functionals from ω ω to 2 ω , and the ϕ's are partial computable functions from N to N. How can we satisfy a single requirement R Γ,ϕ,d ? Again, suppose some string σ of length k has already been built, and consider the set

S = τ ∈ 2 <ω : |Γ τ | ≥ ϕ(r + d)
where r is an upper bound for the Kolmogorov complexity of (Γ, d, ϕ, σ) (which can be found computably since there are computable upper bounds of prefix-free Kolmogorov complexity). By convention, this set is empty if ϕ(r + d) is undefined. Again, let us analyze the different cases and how to succeed in each of them.

• Case 1: ϕ(r + d) is undefined. Then the requirement is satisfied vacuously.

• Case 2: ϕ(r + d) is defined and S is 2 ϕ(r+d) • g 0 -small above σ, where g 0 is the function defined in previous constructions. In this case, it suffices to choose a function g 1 2 ϕ(r+d) • g 0 and for all k ≥ k pick the value of σ(k ) at random between 0 and g 1 (k ). By smallness of S, using Lemma 4 as usual, we will avoid the set S with high probability, thus satisfying requirement R Γ,ϕ,d .

• We want to use a fireworks argument to help us choose between these three cases, but some care is needed since we no longer have a Σ 1 /Π 1 dichotomy. Indeed Case 2 is neither Σ 1 nor Π 1 . The solution is to introduce a priority between passive guesses. We will first make a number of assumptions that ϕ(r+d) is undefined at different stages. If all of these assumptions turn out to be wrong (= the error counter reaches its cap), we will then make the assumption that ϕ(r + d) is defined at the current stage, wait for the value ϕ(r + d) to be defined, and only then make one assumption that the current S is 2 ϕ(r+d) • g 0 -small above the current σ. If proven wrong, we will begin another round of assumptions that ϕ(r + d) is undefined (using a new error counter with a new cap) before making a new 'Case 2' assumption. Finally, when many of these 'Case 2' assumptions are proven to be wrong, we make one last assumption, a 'Case 3' assumption, and if everything goes well we will satisfy the requirement R Γ,ϕ,d . Thus, for any given requirement, our sequence of assumptions will look like this: C1, C1, ..., C1, C2, C1, ..., C1, C2, C1, ..., C1, C2, ..........., C2, C1, C1, ..., C1, C3 (where Ci=Case i) unless one of the C1/C2 assumptions is never proven to be wrong, in which case we succeed. This time there are two possible ways for the algorithm to get stuck: either wrongly assume in Case 2 that ϕ(r + d) is defined, and then wait forever for it to converge, or like in the previous proofs, get stuck because of a wrong C3 assumption, waiting in vain to find a big subtree with leaves in a given c.e. set. The probability of either of these events happening can be made arbitrarily small by a fireworks argument.

The idea to handle several requirements at the same time is similar to what was done in our previous constructions, but this time is dynamic: Before making a C2/C3 assumption of type 'the following set S is small/big', we need to dynamically decide what 'big/small' should mean. What we do is first look at what other smallness assumptions are currently being made for other requirements. If there are l current assumptions of type 'S i is g i -small' for i ≤ l, then we first choose a function G much larger than g 1 +....+g l and evaluate the smallness of S in terms of this new function. In case S is then assumed to be small it is just added to the list of current assumptions. In case it is correctly assumed to be big, since G is much larger than the other g i 's, the probability that we hit one of the S i during the temporary restriction of the tree will be, as in the previous proofs, close to 0.

While we hope that the reader is already convinced at this point, we provide the formal details for completeness.

Theorem 7 Let X ∈ 2 ω and h be a sufficiently fast-growing computable function. For every rational ε > 0, one can effectively design a probabilistic algorithm which, with probability at least 1 -, produces an A ∈ ω ω such that (1) A is DNC X and (2) A computes no complex real.

The algorithm with parameter m = m( ) is the following.

Stage 0: Initialization. First, for each requirement R i , pick a number n(i, 1) at random between 1 and 2 i,1,0 +m . The number n(i, 1) is meant to be a cap for the number of wrong C2 assumptions for requirement R i . As well, for each integer b between 0 and n(i, 1), pick a number n(i, 2, b) at random between 1 and 2 i,2,b +m . Each time C2 makes a wrong assumption, C1 starts a new series of assumptions with n(i, 2, b) as a new cap, where b is the made or stage (b.3.ii) is reached and a tree T is found. To every requirement corresponds exactly one good stage (and no two requirements have a good stage in common). As before, if k is the good stage for a requirement, the probability that the requirement is satisfied, conditional to the algorithm returning an infinite sequence, is at least 1 -2 -k-m+1 and over all requirements, this gives a probability of at least 1k 2 -k-m+1 = 1 -2 -m+2 . Claim 6. The probability that we hit a node of B DNC is at most 2 -m+1 .

Proof. For every n the value of σ(n) is chosen at random among at least 2 n+m values, so the probability of picking ϕ X n (n), if defined, is at most 2 -n-m , thus a total bound of n 2 -n-m = 2 -m+1 .

Thus the probability of success of the algorithm is at least 1 -2 -m+3 . To get Theorem 6, it remains to evaluate the level of algorithmic randomness needed, but the situation is essentially the same as in previous proofs. Checking whether the algorithm gets stuck at a given stage can be tested effectively in ∅ (with ∅ we can check whether partial functions are defined or not, and we can check bigness/smalllness of c.e. sets of strings) and whether it hits B DNC can be tested using X as discussed before.

Conclusion

The above results provide a clear picture of the hierarchy of DNC notions in V'Yugin's algebra. Namely, for every computable function h 0 which grows fast enough, and computable h 1 which grows fast enough compared to h 0 , we have the strict inclusions: mlr dnc h 0 dnc h 1 complex dnc Moreover, every 2-random real computes a witness for each of the four separations. While this is an interesting result in and of itself, the techniques we employed to prove these results are without doubt the main contribution of this paper. They illustrate the power and flexibility of fireworks arguments and show that they interact well with complex forcing notions. What is also interesting is that 'true randomness' seems to be needed for our fireworks arguments. Other known fireworks arguments, such as the proof that every 2-random real computes a hyperimmune set or that every 2-random computes a 1-generic real require only a very weak form of randomness. Indeed, for both of these constructions, Barmpalias et al. [START_REF] Barmpalias | The typical Turing degree[END_REF] showed that it suffices to have a non-computable real which is Turing-below a 2-random, despite the fact that a real which is simply below a 2-random may have very little randomness content. Having a non-computable real which is below a 2-random real is not sufficient in our case: Indeed no 1-generic real computes a DNC function (see for example [START_REF] Downey | Algorithmic randomness and complexity[END_REF]), and as we just said, there are 1-generic reals which are below a 2-random real.

We believe that fireworks arguments will yield more applications in the future. In the constructions of this paper, the strategies for different requirements do interact, but there is no injury per se. It would be very interesting to find examples of situations where fireworks arguments can be mixed with finite/infinite injury constructions.

  Case 3: ϕ(r + d) is defined and S is 2 ϕ(r+d) • g 0 -big above σ. Each element τ ∈ S is such that |Γ τ | ≥ ϕ(r + d), therefore we can decompose S as S = |ρ|=ϕ(r+d) S ρ where S ρ = {τ ∈ S | Γ τ ρ} and since there are 2 ϕ(r+d) strings of length ϕ(r + d), there must be a ρ * such that S ρ * is g 0 -big above σ and such a ρ * can be found effectively knowing (Γ, d, ϕ, σ), hence by the choice of r, K(ρ * ) ≤ r We have |ρ * | = ϕ(r + d), so for m large enough, this guarantees K(ρ * ϕ(r + d)) ≤ r, thus satisfying requirement R Γ,ϕ,d with n = r + d.

Very similar ideas were used by V'Yugin in[22,

[START_REF] Vladimir | Algebra of invariant properties of binary sequences[END_REF]

Acknowledgements. We are thankful to Peter Gács and Alexander Shen for enlightening us on fireworks arguments, to Mushfeq Khan for having made early versions of his survey available to us, and to Chris Porter and Rupert Hölzl for having introduced us to the Levin-V'Yugin algebra and asked the question which ultimately led to this paper. We would also to thank two anonymous referees for their many useful comments and suggestions.

number of wrong C2 assumptions. Create two counters c i , c i , initialized at 0 (c i counts the number of wrong C2 assumptions for requirement R i and c i counts the number of wrong C1 assumption during the current run of such assumptions for requirement R i ). Let L be a list of assumptions (coded as integers, with at most one assumption per requirement), initially empty. Finally, initialize σ to be the empty string.

Loop (to be repeated indefinitely). Suppose that the values σ(0), ..., σ(k -1) of σ are already defined and some requirement R i = R Γ,ϕ,d receives attention. Let r be an upper bound of the Kolmogorov complexity of the current tuple (σ, Γ, ϕ, d, L). Let g 0 , ..., g l be the computable functions such that an assumption 'S is g i -small' is currently in L. We (locally) define a function G by G(u) = 2 u+m (g 0 (u) + . . . + g l (u)).

(a) If this requirement receives attention for the first time, we make for this requirement the assumption that ϕ(r + d) is undefined, and add this assumption to L.

(b) If it does not receive attention for the first time, we check whether the current assumption made for this requirement still appears to be true at stage k.

(1) If it does, we maintain this assumption and simply pick the value of σ(k) at random between 0 and G(k).

(2) If the assumption is discovered to be false, and it was a C1 assumption (ϕ undefined on some value), we remove this assumption from L and increase c i by 1.

(i) If the new value of c i remains less than n(i, 2, c i ), we make a new assumption: we now assume that ϕ(r + d) is undefined and add this assumption to L. (ii) If the new value of c i reaches n(i, 2, c i ), we wait for ϕ(r + d) to become defined.

We then make the assumption that the set

• G)-small above σ and add this assumption to L.

(3) If the assumption is discovered to be false, and it was a C2 assumption (smallness of some set S), we remove this assumption from L, and increase c i by 1.

(i) If the new value of c i remains less than n(i, 1), we make a new assumption: we now assume that ϕ(r + d) is undefined, add this assumption to L, and reset c i to 0. (ii) If the new value of c i is equal to n(i, 1), we then wait until we find, for some ρ of length ϕ(r + d), a set S ρ = {τ ∈ S | Γ τ ρ} which is G-big above σ. When this happens, i.e., when we find a finite tree T of stem σ which is Gbushy above σ, we choose the next values of σ by a downward random walk restricted to T until we reach a leaf of T . When a leaf is reached, we mark the i-th requirement as satisfied.

The sequence A returned by the algorithm is the minimal element of ω ≤ω extending all the values taken by σ throughout the algorithm.

The verification is similar to the previous proofs. Proof. Indeed, by the standard verification of fireworks arguments, the probability that the algorithm gets stuck at the end of the b-th run of C1 assumptions for requirement i (making a bad assumption that ϕ is defined on some value) is, by construction, 2 -i,2,b -m . Likewise, the probability that it gets stuck because of a bad C3 assumption for requirement i is 2 -i,1,0 -m . Since the sum of the terms 2 -i,a,b -m is 2 -m+1 , we have the desired result.

Claim 5. Conditionally to algorithm returning an infinite sequence, the probability that all requirements are met during the construction is at least 1 -2 -m+2 .

Proof. Fix a requirement R i = R Γ,ϕ,d . This requirement receives attention infinitely often until satisfied. This means that if the algorithm does not get stuck, one of the following happens

• At some point it makes for R i a correct assumption that ϕ is undefined on some value during substep (a) or (b.3.i).

• At some point it makes for R i a correct assumption that

• g)-small above σ for some computable g.

• the i-th requirement causes the algorithm to enter some substep (b.3.ii) but a tree T is found thereafter.

In the first case, the requirement is satisfied vacuously. In the second case, we have a set

which is correctly assumed to be (2 ϕ(r+d) • g)-small above σ for some computable g. For any i ≥ k, the value of σ(i) is chosen at later stages of the algorithm at random among at least G(i)-many values, where G is chosen to be greater than 2 i+m • h for any function h appearing in the list L, which in particular includes g (since the assumption featuring g is correct, it is never removed from the list). By Lemma 4, it follows that the probability of hitting a node of S at some later stage is at most

In third case, we find a string ρ * of length ϕ(r +d) and G-bushy finite tree T whose leaves are contained in S ρ * = {τ ∈ S | Γ τ ρ * }. The string ρ * can be effectively found knowing Γ, ϕ, d, the current value of σ and G. But G can be computed knowing the list L, and the integer r is precisely defined to bound the complexity of the tuple (σ, Γ, ϕ, d, L), thus

, so the requirement R Γ,ϕ,d is satisfied for n = r + d. Note that to be completely rigorous, when we say that 'r bounds the Kolmogorov complexity of (σ, Γ, ϕ, d, L)', we also need r to be large enough to overcome the additive constants that will arise in the calculation of the bound of K(ρ * ). This is done, as usual, by picking r 'large enough' (which can be achieved computably), or using a fixed-point argument. Now, given a requirement R Γ,ϕ,d , we say that stage k is good for R Γ,d when after having built σ k, the next iteration of the loop, R Γ,ϕ,d receives attention and a true assumption is


Pegdwendé N Sawadogo
email: pegdwende.sawadogo@univ-lyon2.fr

Jérôme Darmont
email: jerome.darmont@univ-lyon2.fr

Benchmarking Data Lakes Featuring Structured and Unstructured Data with DLBench

Keywords: Data lakes, Benchmarking, Textual Documents, Tabular data

In the last few years, the concept of data lake has become trendy for data storage and analysis. Thus, several approaches have been proposed to build data lake systems. However, these proposals are difficult to evaluate as there are no commonly shared criteria for comparing data lake systems. Thus, we introduce DLBench, a benchmark to evaluate and compare data lake implementations that support textual and/or tabular contents. More concretely, we propose a data model made of both textual and CSV documents, a workload model composed of a set of various tasks, as well as a set of performance-based metrics, all relevant to the context of data lakes. As a proof of concept, we use DLBench to evaluate an open source data lake system we previously developed.

Introduction

Over the last decade, the concept of data lake has emerged as a reference for data storage and exploitation. A data lake is a large repository for storing and analyzing data of any type and size, kept in their raw format [START_REF] Dixon | Pentaho, Hadoop, and Data Lakes[END_REF]. Data access and analyses from data lakes largely rely on metadata [START_REF] Maccioni | KAYAK: A Framework for Just-in-Time Data Preparation in a Data Lake[END_REF], making data lakes flexible enough to support a broader range of analyses than traditional data warehouses. Data lakes are thus handy for both data retrieval and data content analysis.

However, the concept of data lake still lacks standards [START_REF] Russom | Data Lakes Purposes, Practices, Patterns, and Platforms[END_REF]. Thus, there is no commonly shared approach to build, nor to evaluate a data lake. Moreover, existing data lake architectures are often evaluated in diverse and specific ways, and are hardly comparable with each other. Therefore, there is a need of benchmarks to allow objective and comparative evaluation of data lake implementations. There are several benchmarks for big data systems in the literature, but none of them considers the wide range of possible analyses in data lakes.

Hence, we propose in this paper the Data Lake Benchmark (DLBench) to evaluate data management performance in data lake systems. We particularly focus in this first instance on textual and tabular contents, which are often included in data lakes. DLBench is data-centric, i.e., it focuses on a data management objective, regardless of the underlying technologies [START_REF] Darmont | Data-centric benchmarking[END_REF]. We also designed it with Gray's criteria for a "good" benchmark in mind, namely relevance, portability, simplicity and scalability [START_REF] Gray | Database and transaction processing performance handbook[END_REF].

More concretely, DLBench features a data model that generates textual and tabular documents. By tabular documents, we mean spreadsheet or Comma Separated Value (CSV) files whose integration and querying is a common issue in data lakes. A scale factor parameter SF allows to vary data size in predetermined proportions. DLBench also features a workload model, i.e., a set of analytical operations relevant to the context of data lakes with textual and/or tabular content. Finally, we propose a set of performance-based metrics to evaluate such data lake implementations, as well as an execution protocol to execute the workload model on the data model and compute the metrics.

The remainder of this paper is organized as follows. In Section 2, we show how DLBench differs from existing benchmarks. In Section 3, we provide DL-Bench's full specifications. In Section 4, we exemplify how DLBench works and the insights it provides. Finally, in Section 5, we conclude this paper and present research perspectives.

Related Works

Benchmarking data lakes mainly relates to two benchmark categories, namely big data and text benchmarks. In this section, we present recent works in these categories and discuss their limitations with respect to our benchmarking objectives.

Big Data Benchmarks

Big data systems are so diverse that each of big data benchmarks in the literature only target a part of big data requirements [START_REF] Bajaber | Benchmarking big data systems: A survey[END_REF]. The de facto standard TPC-H [18] and TPC-DS [START_REF]Transaction Processing Performance Council: TPC Benchmark DS -Standard Specification[END_REF] issued by the Transaction Processing Performance Council are still widely used to benchmark traditional business intelligence systems. They provide data models that reflect a typical data warehouse, as well as a set of typical business queries, mostly in SQL. BigBench [START_REF] Ghazal | Bigbench: towards an industry standard benchmark for big data analytics[END_REF] is another reference benchmark that addresses SQL querying on data warehouses. In addition, BigBench adaptations [START_REF] Ghazal | Bigbench V2: the new and improved bigbench[END_REF][START_REF] Ivanov | Corebigbench: Benchmarking big data core operations[END_REF] include more complex big data analysis tasks, namely sentiment analysis over short texts.

TPCx-HS [START_REF]Transaction Processing Performance Council: TPC Express Benchmark HS -Standard Specification (version 2.0.3[END_REF] is a quite different benchmark that aims to evaluate systems running on Apache Hadoop1 or Spark2 . For this purpose, only a sorting workload helps measuring performances. HiBench [9] also evaluates Hadoop/Spark systems, but with a broader range of workloads, i.e., ten workloads including SQL aggregations and joins, classification, clustering and sorts [START_REF] Ivanov | Big Data Benchmark Compendium. In: Performance Evaluation and Benchmarking: Traditional to Big Data to Internet of Things -7th TPC Technology Conference[END_REF]. In the same line, TPCx-AI [START_REF]Transaction Processing Performance Council: TPC Express AI -Draft Specification (version 0.6[END_REF], which is still in development, includes more analysis tasks relevant to big data systems, such as advanced machine learning tasks for fraud detection and product rating.

Textual Benchmarks

In this category, we consider big data benchmarks with a consequent part of text on one hand, and purely textual benchmarks on the other hand. Big-DataBench [START_REF] Wang | Bigdatabench: A big data benchmark suite from internet services[END_REF] is a good representative of the first category. It indeed includes a textual dataset made of Wikipedia3 pages, as well as classical information retrieval workloads such as Sort, Grep and Wordcount operations.

One of the latest purely textual benchmarks is TextBenDS [START_REF] Truica | Textbends: a generic textual data benchmark for distributed systems[END_REF], which aims to evaluate performances of text analysis and processing systems. For this purpose, TextBenDS proposes a tweet-based data model and two types of workloads, namely Top-K keywords and Top-K documents operations. Other purely textual benchmarks focus on language analysis tasks, e.g., Chinese [START_REF] Zhu | SCUT-EPT: new dataset and benchmark for offline chinese text recognition in examination paper[END_REF] and Portuguese [START_REF] Fialho | Benchmarking natural language inference and semantic textual similarity for portuguese[END_REF] text recognition, respectively.

Discussion

None of the aforementioned benchmarks proposes a workload sufficiently extensive to reflect all relevant operations in data lakes. In the case of structured data, most benchmark workloads only consider SQL operations (TPC-H, TPC-DS, Hi-Bench). More sophisticated machine learning operations remain marginal, while they are common analyses in data lakes. Moreover, the task of finding related data (e.g., joinable tables) is purely missing, while it is a key feature of data lakes.

Existing textual workloads are also insufficient. Admittedly, BigDataBench's Grep and TextBenDS's Top-K documents operation are relevant for data search. Similarly, Top-K keywords and WordCount are relevant to assess documents aggregation [START_REF] Huang | The hibench benchmark suite: Characterization of the mapreduce-based data analysis[END_REF][START_REF] Truica | Textbends: a generic textual data benchmark for distributed systems[END_REF]. However, other operations such as finding most similar documents or clustering documents should also be considered.

Thus, our DLBench benchmark stands out, with a broader workload that features both data retrieval and data content analysis operations. DLBench's data model also differs from most big data benchmarks as it provides raw tabular files, inducing an additional data integration challenge. Moreover, DLBench includes a set of long textual documents that induces a different challenge than short texts such as tweets [START_REF] Truica | Textbends: a generic textual data benchmark for distributed systems[END_REF] and Wikipedia articles [START_REF] Wang | Bigdatabench: A big data benchmark suite from internet services[END_REF]. Finally, DLBench is data-centric, unlike big data benchmarks that focus on a particular technology, e.g., TPCx-HS and HiBench.

Specification of DLBench

In this section, we first provide a thorough description of DLBench's data and workload model. Then, we propose a set of metrics and introduce an assessment protocol to evaluate and/or compare systems using DLBench.

Data Model

Data Description DLBench includes two types of data to simulate a data lake: textual documents and tabular data. Textual documents are scientific articles that span from few to tens of pages. They are written in French and English and their number amounts to 50,000. Their overall volume is about 62 GB.

Tabular data are synthetically derived from a few CSV files containing Canadian government open data. Although such data are often considered as structured, they still need integration to be queried and analyzed effectively. DL-Bench features up to 5,000 tabular files amounting to about 1,4 GB of data.

The amount of data in the benchmark can be customised through scale factor parameter SF , which is particularly useful to measure a system's performance when data volume increases. SF ranges from 1 to 5. DLBench's data come with metadata catalogues that can serve in data integration. More concretely, we generate from textual documents catalogue information on year, language and domain (discipline) to which each document belongs. Similarly, we associate in the tabular file catalogue a year with each file. This way, we can separately query each type of data through its specific metadata. We can also jointly query textual documents and tabular files through the year field.

Eventually, textual documents are generated independently from tabular files. Therefore, each type of data can be used apart from the other. In other words, DLBench can be used to assess a system that contains either textual documents only, tabular files only, or both. When not using both types of data, the workload model must be limited to its relevant part.

Data Extraction

We extract textual data from HAL 4 , a French open data repository dedicated to scientific document diffusion. We opted for scientific documents as most are long enough to provide complexity and reflect most actual use cases in textual data integration systems, in contrast with shorter documents such as reviews and tweets.

Although HAL's access is open, we are not allowed to redistribute data extracted from HAL. Thus, we provide instead a script that extracts a user-defined amount of documents. This script and a usage guide are available online for reuse 5 . Amongst all available documents in HAL, we restrict to scientific articles whose length is homogeneous, which amounts to 50,000 documents. While extracting documents, the script also generates the metadata catalogue described above.

Tabular data are reused from an existing benchmark [START_REF] Nargesian | Table Union Search on Open Data[END_REF]. These are actually a set of 5,000 synthetic tabular data files generated from an open dataset stored inside a SQLite6 database. Many of the columns in the tables contain similar data and can therefore be linked, making this dataset suitable to assess structured data integration as performed in data lakes.

We apply on this original dataset7 a script to extract all (or a part) of the tables in the form of raw CSV files. As for textual documents, this second script also generates a metadata catalogue. The script as well as guidelines are available online 7 .

Workload Model

To assess and compare data lakes across different implementations and systems, some relevant tasks are needed. Thus we specify in this section instances of probable tasks in textual and tabular data integration systems. Furthermore, we translate each task into concrete, executable queries (Table 2).

Data Retrieval Tasks are operations that find data bearing given characteristics. Three main ways are usually exploited to retrieve data in a lake. They are relevant for both tabular data and textual documents. However, we mainly focus on data retrieval from textual documents, as they represent the largest amount of data.

1. Category filters consist in filtering data using tags or data properties from the metadata catalogue. In other words, it can be viewed as a navigation task. 2. Term-based search pertains to find data, with the help of an index, from all data files that contain a set of keywords. Keyword search is especially relevant for textual documents, but may also serve to retrieve tabular data. 3. Related data search aims to, from a specified data file, retrieve similar data.

It can be based on, e.g., column similarities in tabular data, or semantic similarity between textual documents.

Textual Document Analysis/Aggregation tasks work on data contents.

Although textual documents and tabular data can be explored with the same methods, they require more specific techniques to be jointly analyzed or aggregated in data lakes.

4. Document scoring is a classical information retrieval task that consists in providing a score for each document with respect to how it matches a set of terms. Such scores can be calculated by diverse ways, e.g., with the Elastic-Search [START_REF]Elasticsearch: Theory Behind Relevance Scoring[END_REF] scoring algorithm. In all cases, scores depend on the appearance frequency of query terms in the document to score and in the corpus, and also the document's length. This operation is actually very similar to computing top-k documents. 5. Document highlights extract a concordance from a corpus. A concordance is a of snippets where a set of terms appear. It is also a classical information retrieval task that provides a sort of summary of documents. 6. Document top keywords are another classical way to summarize and aggregate documents [START_REF] Ravat | Top-keyword: An Aggregation Function for Textual Document OLAP[END_REF]. Computing top keywords is thus a suitable task to assess systems handling textual documents. 7. Document text mining. In most data lake systems, data are organized in collections, using tags for example. Here, we propose a data mining task that consists either in representing each collection of documents with respect to the others, or in grouping together similar collections with respect to their intrinsic vocabularies. In the first case, we propose a Principal Component Analysis (PCA) [START_REF] Wold | Principal component analysis[END_REF] where statistical individuals are document collections. PCA could, for example, out put an average bag of words for each collection.

In the second case, we propose a KMeans [START_REF] Steinley | K-means clustering: a half-century synthesis[END_REF] clustering to detect groups of similar collections.

Tabular Data Analysis/Queries Finally, we propose specific tasks suitable for integrated tabular files.

Simple table queries.

We first propose to evaluate a data lake system's capacity to answer simple table queries through a query language such as SQL. As we are in a context of raw tabular data, language-based querying is indeed an important challenge to address. 9. Complex table queries. In line with the previous task, we propose to measure how the system supports advanced queries, namely join and grouping queries. 10. Tuple mining. An interesting way to analyze tabular data is either to represent each row with respect to the others or to group together very similar rows. We essentially propose here the same operation as Task #7 above, except that statistical individuals are table rows instead of textual documents.

To achieve such an analysis, we only consider numeric values.

Performance Metrics

In this section, we propose a set of three metrics to compare and assess data lake implementations.

1. Query execution time aims to measure the time necessary to run each of the 20 query instances from Table 2 on the tested data lake architecture. This metric actually reports how efficient the lake's metadata system is, as it serves to integrate raw data, and thus make analyses easier and faster. In the case where certain queries are not supported, measures are only computed on the supported tasks. 2. Metadata size measures the amount of metadata generated by the system.

It allows to balance the execution time with the resulting storage cost. 3. Metadata generation time encompasses the generation of all the lake's metadata. This also serves to balance query execution time.

We did not include other possible metrics such as actually used RAM and CPU because they are hard to measure. However, we recommend interpreting benchmark results while taking into account available RAM and CPU.

Assessment Protocol

The three metrics from Section 3.3 are measured through an iterative process for each scale factor SF ∈ {1, 2, 3, 4, 5}. Each iteration consists in four steps (Algorithm 1).

1. Data generation is achieved with the scripts specified in Section 3.1 7 . 2. Data integration. Raw data now need to be integrated in the data lake system through the generation and organization of metadata. This step is specific to each system, as there are plethora of ways to integrate data in a lake.

Overview of AUDAL

To demonstrate the use of DLBench, we evaluate AUDAL [START_REF] Scholly | Coining goldMEDAL: A New Contribution to Data Lake Generic Metadata Modeling[END_REF], a data lake system designed as part of a management science project, to allow automatic and advanced analyses on various textual documents (annual reports, press releases, websites, social media posts...) and spreadsheet files (information about companies, stock market quotations...). The AUDAL system uses an extensive metadata system stored inside MongoDB8 , Neo4J9 , SQLite 8 and ElasticSearch10 to support numerous analyses.

AUDAL provides ready-to-use analyses via a representational state transfer application programming interface (REST API) dedicated to data scientists, and also through a Web-based analysis platform designed for business users.

Setup and Results

AUDAL is implemented on a cluster of three VMware virtual machines (VMs). The first VM has a 7-core Intel-Xeon 2.20 GHz processor and 24 GB of RAM. It runs the API and also supports metadata extraction. Both other VMs have a mono-core Intel-Xeon 2.20 GHz processor and 24 GB of RAM. Each of the three VMs hosts a Neo4J instance, an ElasticSearch instance and a MongoDB instance to store AUDAL's metadata.

The results achieved with DLBench show that AUDAL scales quite well (Figures 123456). Almost all task response times are indeed either constant (Tasks #3, #7, #8, #9 and #10) or grow linearly with SF (Tasks #1, #2, and #4 to #6). In addition, we observe that except Task #6 (that takes up to 92 seconds), all execution times are reasonable considering the modest capabilities of our hardware setup. Eventually, metadata generation time and size scale linearly and almost-linearly, respectively (Figure 7). We can also see that metadata amount to about half the volume of raw data, which illustrates how extensive AUDAL's metadata are. We observe some fluctuations in the results, with sometimes negative slopes while SF increases. Such variations are due to external, random factors such as network load or the Java garbage collector starting running. However, the influence on the runtime is negligible (of the order of a tenth of a second) and is only visible on simple queries that run in half a second.

Conclusion

In this paper, we introduce DLBench, a benchmark for data lakes with textual and/or tabular contents. To the best of our knowledge, DLBench is the first data lake benchmark. DLBench features: 1) a data model made of a corpus of long, textual documents on one hand, and a set of raw tabular data on the other hand; 2) a query model of twenty query instances across ten different tasks; 3) three relevant metrics to assess and compare data lake implementations; and 4) an execution protocol. Finally, we demonstrate the use of DLBench by assessing the AUDAL data lake [START_REF] Scholly | Coining goldMEDAL: A New Contribution to Data Lake Generic Metadata Modeling[END_REF], highlighting that the AUDAL system scales quite well, especially for data retrieval and tabular data querying.

Fig. 1 :Fig. 6 :

 16 Fig. 1: Task #1 response times

Fig. 7 :

 7 Fig. 7: Metadata size and generation time

Table 1 :

 1 Table 1 describes the actual amount of data obtained with values of SF . Amount of data per SF value

	Scale factors	SF = 1 SF = 2 SF = 3 SF = 4 SF = 5
	Nb. of textual documents	10,000 20,000 30,000 40,000 50,000
	Nb. of tabular files	1,000 2,000 3,000 4,000 5,000
	Textual documents' size (GB)	8.0	24.9	37.2	49.6	62.7
	Tabular files' size (GB)	0.3	0.6	0.8	1.1	1.4

Table 2 :

 2 Query instances Q4a Calculate documents scores w.r.t. the terms university and science Q4b Calculate documents scores w.r.t. the terms university, research, new and solution #5 Q5a Retrieve documents concordance w.r.t. the terms university and science Q5b Retrieve documents concordance w.r.t. the terms university, science new and solution #6 Q6a Find top 10 keywords from all documents (stopwords excluded)

	Task Query
		Data retrieval
		Q1a Retrieve documents written in French
	#1	Q1b Retrieve documents written in English and edited in December
		Q1c Retrieve documents whose domains are math or info, written in English
		and edited in 2010, 2012 or 2014
	#2	Q2a Retrieve data files (documents or tables) containing the term university Q2b Retrieve data files containing the terms university, science or research
	#3	Q3a Retrieve the top 5 documents similar to any given document Q3b Retrieve 5 tables joinable to table t dc9442ed0b52d69c c11 1 1
		Textual Document Analysis/Aggregation
	#4
	#7	Q7a Run a PCA with documents merged by domains Q7b Run a 3-cluster KMeans clustering with documents merged by domains
		Tabular Data Analysis/Queries
	#8	Q8a Retrieve all tuples from table t e9ef d5cda78af 711 c11 1 1 Q8b Retrieve tuples from table t e9ef d5cda78af 711 c11 1 1
		whose column PROVINCE bears the value BC
	#9	Q9a Calculate the average of columns Unnamed: 12, 13, and 20 from table t 356f c1eaad97f 93b c15 1 1 grouped by Unnamed: 2
		Q9b Run a left join query between tables P ED SK DT L SN F	c7 0 1
		and t 285b3bcd52ec0c86 c13 1 1 w.r.t. columns named SOILTYPE
	#10	Q10a Run a PCA on the result of query Q9a Q10b Run a 3-cluster KMeans clustering on the result of query Q9a

  3. Metadata size and generation time computing consists in measuring metrics the total size of generated metadata and the time taken to generate all metadata, with respect to the current SF . 4. Query execution time computation involves computing the running time of each individual query. To mitigate any perturbation, we average the time of 10 runs for each query instance. Let us notice that all timed executions must be warm runs, i.e., each of the 20 query instances must first be executed once (a cold run not taken into account in the results).

	Algorithm 1: Assessment protocol
	Result: metric 1, metric 2, metric 3
	metric 1 ← [ ][ ]; metric 2 ← [ ]; metric 3 ← [ ];
	for SF ← 1 to 5 do
	generate benchmark data(SF);
	generate and organize metadata(SF);
	metric 2[SF] ← retrieve metadata generation time(SF);
	metric 3[SF] ← retrieve metadata size(SF);
	for i ← 1 to 20 do
	run query(i, SF);
	response times ← [ ];
	for j ← 1 to 10 do
	response times[j] ← run query(i, SF);
	end
	metric 1[SF][i] ← average(response times);
	end
	end
	4 Proof of Concept

https://hadoop.apache.org/

http://spark.apache.org/

https://en.wikipedia.org/

https://hal.archives-ouvertes.fr/

https://github.com/Pegdwende44/DLBench

https://www.sqlite.org/

https://storage.googleapis.com/table-union-benchmark/large/benchmark.sqlite

https://www.mongodb.com

https://neo4j.com

https://www.elastic.co

Acknowledgments P.N. Sawadogo's PhD is funded by the Auvergne-Rhône-Alpes Region through the AURA-PMI project.