Didier Dubois

Henri Prade

Agnès Rico

The cube of opposition and the complete appraisal of situations by means of Sugeno integrals

The cube of opposition is a logical structure that underlies many information representation settings. When applied to multiple criteria decision, it displays various possible aggregation attitudes. Situations are usually assessed by combinations of properties they satisfy, but also by combinations of properties they do not satisfy. The cube of opposition applies to qualitative evaluation when criteria are weighted as well as in the general case where any subset of criteria may be weighted for expressing synergies between them, as for Sugeno integrals. Sugeno integrals are well-known as a powerful qualitative aggregation tool which takes into account positive synergies between properties. When there are negative synergies between properties we can use the so-called desintegral associated to the Sugeno integral. The paper investigates the use of the cube of opposition and of the if-then rules extracted from these integrals and desintegrals in order to better describe acceptable situations.

Introduction

The description of situations (or objects, or items) is usually based on the degrees to which they satisfy properties (or criteria). Sugeno integrals [START_REF] Sugeno | Theory of Fuzzy Integrals and its Applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals: a survey[END_REF] are qualitative integrals first used as aggregation operators in multiple criteria decision. They deliver a global evaluation between the minimum and the maximum of the partial evaluations. The definition of the Sugeno integral is based on a monotonic set function, called capacity or fuzzy measure, which represents the importance of the subsets of criteria.

More recently Sugeno integrals have been used as a representation tool for describing more or less acceptable objects [START_REF] Prade | Decribing acceptable objects by means of Sugeno integrals[END_REF] under a bipolar view. In such a context the properties are supposed to be positive, i.e, the global evaluation increases with the partial ratings. But some objects can be accepted because they don't satisfy some properties. So we also need to consider negative properties, i.e., the global evaluation increases when the partial ratings decreases. Hence a pair of evaluations made of a Sugeno integral and a reversed Sugeno integral are used to describe acceptable objects in terms of properties they must have and of properties they must avoid. This reversed integral is a variant of Sugeno integral, called a desintegral. Their definition is based on a decreasing set function called anti-capacity.

Moreover, it was proved that the Sugeno integrals and the associated desintegrals can be encoded as a possibilistic logic base [START_REF] Dubois | The logical encoding of Sugeno integrals[END_REF][START_REF] Dubois | Qualitative integrals and desintegrals -Towards a logical[END_REF]. These results have been used for extracting decision rules from qualitative data evaluated on the basis of Sugeno integrals [START_REF] Dubois | Extracting decision rules from qualitative data using Sugeno integral: a case study[END_REF]. This paper extends these results to the extraction of decision rules from qualitative data using qualitative desintegrals. These decision rules should help completing the results presented in [START_REF] Prade | Decribing acceptable objects by means of Sugeno integrals[END_REF].

Besides, we can distinguish the optimistic part and the pessimistic part of any capacity [START_REF] Dubois | On the informational comparison of qualitative fuzzy measures[END_REF]. It has been recently indicated that Sugeno integrals associated to these capacities and their associated desintegrals form a cube of opposition [START_REF] Dubois | The cube of opposition. A structure underlying many knowledge representation formalisms[END_REF], the integrals being present on the front facet and the desintegrals on the back facet of the cube (each of these two facets fit with the traditional views of squares of opposition). As this cube summarizes all the evaluation options, we may consider the different Sugeno integrals and desintegrals present on the cube in the selection process of acceptable situations.

The paper is organized as follows. Section 2 introduces the cube of opposition and discusses its relevance for multiple criteria aggregation. Section 3 restates the main results on Sugeno integrals, desintegrals, and their logical rule counterparts, before presenting the cube of opposition for Sugeno integrals and desintegrals in section 4. Section 5 takes advantage of the cube for discussing the different aggregation attitudes and their relations.

Square and cube of opposition in multiple criteria evaluation

The traditional square of opposition [START_REF] Parsons | The traditional square of opposition[END_REF] is built with universally and existentially quantified statements in the following way. Consider a statement (A) of the form "all P 's are Q's", which is negated by the statement (O) "at least one P is not a Q", together with the statement (E) "no P is a Q", which is clearly in even stronger opposition to the first statement (A). These three statements, together with the negation of the last statement, namely (I) "at least one P is a Q" can be displayed on a square whose vertices are traditionally denoted by the letters A, I (affirmative half) and E, O (negative half), as pictured in Figure 1 (where Q stands for "not Q"). Changing P into ¬P , and Q in ¬Q leads to another similar square of opposition aeoi, where we also assume that the set of "not-P 's" is non-empty. Then the 8 statements, A, I, E, O, a, i, e, o may be organized in what may be called a cube of opposition [START_REF] Dubois | From Blanché's hexagonal organization of concepts to formal concept analysis and possibility theory[END_REF] as in Figure 2.

i: ∃x, ¬P (x) ∧ ¬Q(x)

I: ∃x, P (x) ∧ Q(x) O: ∃x, P (x) ∧ ¬Q(x) o: ∃x, ¬P (x) ∧ Q(x)
a: ∀x, ¬P (x) → ¬Q(x) The front facet and the back facet of the cube are traditional squares of opposition. In the cube, if we also assume that the sets of "Q's" and "not-Q's" are non-empty, then the thick non-directed segments relate contraries, the double thin non-directed segments sub-contraries, the diagonal dotted non-directed lines contradictories, and the vertical uni-directed segments point to subalterns, and express entailments. Stated in set vocabulary, A, I, E, O, a, i, e, o, respectively means

A: ∀x, P (x) → Q(x) E: ∀x, P (x) → ¬Q(x) e: ∀x, ¬P (x) → Q(x)
P ⊆ Q, P ∩ Q = ∅, P ⊆ Q, P ∩ Q = ∅, P ⊆ Q, P ∩ Q = ∅, P ⊆ Q, P ∩ Q = ∅.
In order to satisfy the four conditions of a square of opposition for the front and the back facets, we need P = ∅ and P = ∅. In order to have the inclusions indicated by the diagonal arrows in the side facets, we need Q = ∅ and Q = ∅ as further normalization conditions. Suppose P denotes a set of important properties, Q a set of satisfied properties (for a considered object). Vertices A, I, a, i correspond respectively to 4 different cases: i) all important properties are satisfied, ii) at least one important property is satisfied, iii) all satisfied properties are important, iv) at least one non satisfied property is not important.

Note also the cube is compatible with an understanding having a bipolar flavor [START_REF] Dubois | An introduction to bipolar representations of information and preference[END_REF]. Suppose that among possible properties for the considered objects, some are desirable (or requested) and form a subset R and some others are excluded (or undesirable) and form a subset E. Clearly, one should have E ⊆ R. For a considered object the set of properties is partitioned into the subset of satisfied properties S and the subset S of properties not satisfied. Then vertex A corresponds to R ⊆ S and a to R ⊆ S. Then a also corresponds to E ⊆ S.

More generally, satisfaction of properties may be graded, and importance (both with respect to desirability and undesiraribility) is also a matter of degree. It is the case in multiple criteria aggregation where objects are evaluated by means of a set C of criteria i (where 1 ≤ i ≤ n). Let us denote by x i the evaluation of a given object for criterion i, and

x = (x 1 , • • • , x i , • • • , x n ).
We assume here that ∀i, x i ∈ [0, 1]. x i = 1 means that the object fully satisfies criterion i, while x i = 0 expresses a total absence of satisfaction. Let π i ∈ [0, 1] represent the level of importance of criterion i. The larger π i the more important the criterion.

Simple qualitative aggregation operators are the weighted min and the weighted max [START_REF] Dubois | Weighted minimum and maximum operations. An addendum to 'A review of fuzzy set aggregation connectives[END_REF]. The first one measures the extent to which all important criteria are satisfied; it corresponds to the expression n i=1 (1π i ) ∨ x i , while the second one, n i=1 π i ∧ x i , is optimistic and only requires that at least one important criterion be highly satisfied. Under the hypothesis of the double normalization (∃i, π i = 1 and ∃j, π j = 0) and the hypothesis ∃r, x r = 1 and ∃s, x s = 0 , weighted min and weighted max correspond to vertices A and I of the cube on Fig. 3.

i: n i=1 (1 -πi) ∧ (1 -xi) I: n i=1 πi ∧ xi O: n i=1 πi ∧ (1 -xi) o: n i=1 (1 -πi)∧xi a: n i=1 πi ∨ (1 -xi) A: n i=1 (1 -πi) ∨ xi E: n i=1 (1 -πi) ∨ (1 -xi) e: n i=1 πi ∨xi Fig. 3

. Cube of weighted qualitative aggregations

There is a correspondance between the aggregation functions on the right facet and those on the left facet, replacing x with 1x.

Suppose that a fully satisfied object x is an object with an global rating equal to 1. Vertices A, I, a and i correspond respectively to 4 different cases: x is such that i) A: all properties having some importance are fully satisfied (if π i > 0 then x i = 1 for all i).

ii) I: there exists at least one important property fully satisfied (π i = 1 and x i = 1), iii) a: all somewhat satisfied properties are fully important (if x i > 0 then π i = 1 for all i) iv) i: there exists at least one unimportant property that is not satisfied (π i = 0 and x i = 0). These cases are similar to those presented in the cube on Fig. 2.

Example 1. We consider C = {1, 2, 3} and π 1 = 0, π 2 = 0.5 and π 3 = 1; see Fig. 4.

-on vertex A (resp. I) a fully satisfied object is such that x 2 = x 3 = 1 (resp. x 3 = 1).

-on vertex a (resp. i) a fully satisfied object is such that

x 1 = x 2 = 0 (resp. x 1 = 0),
The operations of the front facet of the cube of Fig. 3 merge positive evaluations that focus on the high satisfaction of important criteria, while the local ratings x i on the back could be interpreted as negative ones (measuring the intensity of faults). Then aggregations yield global ratings evaluating the lack of presence of important fault. In this case, weights are tolerance levels forbidding a fault to be too strongly present Then the vertices a and i in the back facet are interpreted differently: a is true if all somewhat intolerable faults are fully absent; i is true if there exists at least one intolerable fault that is absent. This framework this involves two complementary points of view, recently discussed in a multiple criteria aggregation perspective [START_REF] Dubois | Qualitative integrals and desintegrals: How to handle positive and negative scales in evaluation[END_REF]. In order to translate a Sugeno integral into rules we also need the notions of conjugate capacity, qualitative Moebius transform and focal sets: The conjugate capacity of µ is defined by µ c (A) = 1µ(A) where A is the complementary of A.

In this paper, the capacities are supposed to be normalized in a special way, i.e. ∃A = C such that µ(A) = 1 and ∃B such that µ c (B) = 1. It is worth noticing that in such a context there exists a non-empty set, namely B, such that µ(B) = 0.

The inner qualitative Moebius transform of a capacity µ is a mapping µ

# : 2 C → L defined by µ # (E) = µ(E) if µ(E) > max B⊂E µ(B) and 0 otherwise.
It contains the minimal information characterizing µ (µ(A) = max E⊆A µ # (E)). A set E for which µ # (E) > 0 is called a focal set. The set of the focal sets of µ is denoted by F(µ). The Sugeno integral of an object x with respect to a capacity µ is originally defined by [START_REF] Sugeno | Theory of Fuzzy Integrals and its Applications[END_REF][START_REF] Sugeno | Fuzzy measures and fuzzy integrals: a survey[END_REF]:

S µ (x) = max α∈L min(α, µ({i|x i ≥ α})). (1)
There are two equivalent expressions used in this article:

S µ (x) = max A∈F (µ)
[min(µ(A), min

i∈A x i )] = min A∈F (µ c ) [max(µ(A), max i∈A x i )]. (2)
The first expression in (2) is the generalisation of a normal disjunctive form from Boolean functions to lattice-valued ones. The second is the generalisation of a normal conjunctive form. Clearly using the first form, S µ (x) = 1 if and only if there is a focal set E of µ for which µ(E) = 1 and x i = 1 for all i in E. Likewise, using the second form S µ (x) = 0 if and only if there is a focal set F of µ c for which µ c (F ) = 1 and x i = 0 for all i in F . The Sugeno integral can then be expressed in terms of if-then rules that facilitate the interpretation of the integral, when it has been derived from dat a (see [START_REF] Dubois | Extracting decision rules from qualitative data using Sugeno integral: a case study[END_REF] for more details).

When we consider a capacity µ, its pessimistic part is µ * (A) = min(µ(A), µ c (A)) and its optimistic part is µ * (A) = max(µ(A), µ c (A)) [START_REF] Dubois | On the informational comparison of qualitative fuzzy measures[END_REF]. We have µ * ≤ µ * , µ * c = µ * and µ * c = µ * . We need these notions in order to respect the fact that, in the square of opposition, the vertices A, E express stronger properties than vertices I, O.

Proposition 2 A capacity µ induces the following square of opposition for the associated Sugeno integrals

A: Sµ * (x) E: Sµ * (1 -x) I: Sµ * (x) O: Sµ * (1 -x)
Proof. A entails I and E entails O since µ * ≤ µ * . A and O (resp. E and I) are the negation of each other since for all capacities µ we have the relation:

S µ (x) = 1 -S µ c (1 -x). (4)
Let us prove that expressions at vertices A and E cannot be both equal to 1. Consider x such that S µ * (x) = 1, hence using Equation ( 4),

1 = 1 -S µ * (1 -x). So S µ * (1 -x) ≤ S µ * (1 -x) = 0 which entails S µ * (1 -x) = 0.
Similarly we can prove that I and O cannot be false together.

Remark 1. In the above square of opposition, A and E can be false together and I and O can be true together. For instance, if µ is a non-fully informed necessity measure N (for instance F(N ) = {E}, with weight 1, where E is not a singleton), it comes down to the known fact that we can find a subset A such that N (A) = N (A) = 0, and for possibility measure

Π(A) = 1 -N (A) it holds that Π(A) = Π(A) = 1.
Note that S µ * (1x) = S 1-µ * (x) and S µ * (1x) = S 1-µ * (x) where 1µ * 1µ * are anti capacities. Hence a capacity µ defines a square of opposition where the decision rules on the vertices A and I (resp.E and O) are based on a Sugeno integral (resp. desintegral).

In order to present the cube associated to Sugeno integrals we need to introduce the negation of a capacity µ, namely the capacity µ defined as follows: µ # (E) = µ # (E) and µ(A) = max E⊆A µ # (E). A square of opposition aieo can be defined with the capacity µ. Hence we can construct a cube AIEO and aieo as follows: [START_REF] Dubois | The cube of opposition. A structure underlying many knowledge representation formalisms[END_REF]: Let us prove that S µ * (x) ≤ S µ * (1x) (the arrow A → i on the left side facet).

i: Sµ * (1 -x) I: Sµ * (x) O: Sµ * (1 -x) o: Sµ * (x) a: Sµ * (1 -x) A: Sµ * (x) E: Sµ * (1 -x) e: Sµ * (x)
S µ * (x) = min A [max(min(µ(A), 1 -µ(A)), max i∈A x i ] and S µ * (1 -x) = max A [min(max(µ(A), 1 -µ(A)), min i∈A (1 -x i )]
. So we just need to find sets E and F such that one term inside min A is less that one term inside max A . Let us consider A = {i} where i is such that

x i = 0. We have max(min(µ(A), 1 -µ(A)), max i∈A x i ) = min(µ(C\{i}), 1 -µ({i})) and min(max(µ(A), 1 -µ(A)), min i∈A (1 -x i )] = max(µ({i}), 1 -µ(C\{i})). Note that µ(C\{i}) = µ # (C\{i}), since C\{i} is focal for µ and µ({i}) = µ # ({i}) = µ # (C\{i}) by definition. So min(µ(C\{i}), 1 -µ({i})) ≤ µ(C\{i}) = µ # (C\{i}) ≤ max(µ({i}), 1 -µ(C\{i})).
The inequality S µ * (1x) ≤ S µ * (x) linking a with I, is obtained, under the condition ∃j ∈ C such that x j = 1, and C\{j} must be a focal set of µ, i.e., {j} is focal for µ using the equation ( 4). For arrow E → o and e → O, we need by symmetry to exchange i and j in the above requirements. This concludes the proof.

The cube of opposition is reduced to the facet AEIO if and only if µ = µ. So the cube is degenerated if and only if for each focal set T = C of µ, the complement T is also focal and µ # (T ) = µ # (T ), in other words, capacities expressing ignorance in the sense that µ(A) = µ(A) for all A = ∅, C. Likewise the cube is reduced to the top facet AEea, if µ is self-conjugate, that is, µ = µ c , i.e., µ(A) + µ(A) = 1.

Discussing aggregation attitudes with the cube

In this following, we characterize situations where objects get a global evaluation equal to 1 using aggregations on the top facet. According to the selection rules, we can restrict to focal sets of the capacity with weight 1.

i: S µ * (1 -x) = 1 iff ∃A such that µ * (A) = 1 and for all i in A, x i = 0. Since µ * (A) = max(µ(A), µ c (A)) = 1, either µ(A) = 1 or µ c (A) = 1, i.e., µ(A) = 0.
So, from the previous case we find that S µ * (1x) = 1 if and only if for all i in A, x i = 0, and A is contained in a focal set of µ with weight 1, or A contains no focal set of µ.

Example 2. Assume C = {p, q, r}. We want to select objects with properties p and q or p and r. Hence we have F µ = {{p, q}, {p, r}} with µ # ({p, q}) = µ # ({p, r}) = 1.

We can calculate the useful capacities: capacity {p} {q} {r} {p, q} {p, r} {q, r} {p, q, r} µ The aggregation functions on the vertices are: A : S µ (x) = max(min(x p , x q ), min(x p , x r )) I :S µ c (x) = max(x p , min(x q , x r )) a :S µ c (1x) = min(1x q , 1x r ) i :S µ (1x) = max(1x q , 1x r ). Note that for vertex A, the two focal sets overlap so that the first condition of Proposition 4 is met when S µ (x) = 1. For vertex I, one can see that S µ c (x) = 1 when x p = 1 and {p} does overlap all focal sets of µ; the same occurs when x q = x r = 1. For vertex a, S µ c (1x) = 1 when x q = x r = 0, and note that the complement of {q, r} is contained in a focal set of µ, while {q, r} contains no focal set of µ. For vertex i, S µ (1x) = 1 when, x q = 0 or x r = 0, and clearly, neither {q} not {r} contain any focal set of µ, but the complement of each of them is a focal set of µ.

# 0 0 0 1 1 0 0 µ 0 0 0 1 1 0 1 µ c 1 0 0 1 1 1 1 µ c # 1 0 0 0 0 1 0 µ # 0

Concluding remarks

This paper has shown how the structure of the cube of opposition extends from ordinary sets to weighted min-and max-based aggregations and more generally to Sugeno integrals, which constitute a very important family of qualitative aggregation operators, which moreover have a logical reading. The cube exhausts all the possible aggregation attitudes. Moreover, as mentioned in Section 2, it is compatible with a bipolar view where we distinguish between desirable properties and rejected properties. It thus provides a rich theoretical basis for multiple criteria aggregation.

Fig. 2 .

 2 Fig. 2. Cube of opposition of quantified statements

i: ∨( 1 -Fig. 4 .

 14 Fig. 4. Cube of weighted qualitative aggregations 3 Sugeno integrals, desintegrals and rules

Fig. 5 .Proposition 3

 53 Fig. 5. Cube of opposition associated to µ

Proposition 4

 4 The global evaluations at vertices AIai of a cube associated to a capacity µ are maximal respectively in the following situations pertaining to the focal sets of µ:A: The set of totally satisfied properties contain a focal set with weight 1 and overlaps all other focal sets.I: The set of satisfied properties contains a focal set with weight 1 or overlaps all other focal sets.a: The set of totally violated properties contains no focal set and its complement is contained in a focal set with weight 1.i: The set of totally violated properties contains no focal set or its complement is contained in a focal set with weight 1.Proof. A: S µ * (x) = 1 iff there exists a set A such that µ * (A) = 1 and for all i in A,x i = 1. µ * (A) = 1 is equivalent to µ(A) = 1 and µ c (A) = 1, that is µ(A) = 0. So Acontains a focal set of µ with weight 1 and overlaps all focal sets. I: S µ * (x) = 1 iff ∃A such that µ * (A) = 1 and for all i in A, x i = 1. Since µ * (A) = max(µ(A), µ c (A)) = 1, either µ(A) = 1 or µ c (A) = 1, i.e., µ(A) = 0. So A contains a focal set of µ with weight 1 or it overlaps all focal sets. a: S µ * (1x) = 1 if and only if there exists a set A such that µ * (A) = 1 and for all i in A, x i = 0. The condition µ * (A) = 1 reads µ(A) = 1 and µ c (A) = 1. The first condition says that µ # (B) = 1 for some subset B of A that is µ # (B) = 1, where B contains A. The second condition says that µ(A) = 0 = µ(A). It means that there is no focal set of µ contained in A. So S µ * (1x) = 1 if and only if there exists A such that for all i in A, x i = 0, and A is contained in a focal set of µ with weight 1, and A contains no focal set of µ.

µ

  c ≥ µ so µ * = µ and µ * = µ c µ ≥ µ c so µ * = µ and µ * = µ c Note that µ is a possibility measure.

Selection rules Each focal T of µ corresponds to the selection rule: If x i ≥ µ(T ) for all i ∈ T then S µ (x) ≥ µ(T ).

The objects selected by such rules are those satisfying to a sufficient extent all properties present in the focal set appearing in the rule. Elimination rules Each focal set of the conjugate µ c with level µ c (F ) corresponds to the following elimination rule:

The objects rejected by these rules are those that do not satisfy enough the properties in the focal set of µ c of some such rule.

When Sugeno integrals are used as aggregation functions for selecting acceptable objects, the properties are considered positive: the global evaluation increases with the partial ratings. But generally we have also negative properties: the global evaluation increases when the partial ratings decrease. In such a context we can use a desintegral associated to the Sugeno integral. We now presents this desintegral.

In the case of negative properties, weights are assigned to sets of properties by means of an anti-capacity (or anti-fuzzy measure) which is a set function ν :

Clearly, ν is an anticapacity if and only if 1ν is a capacity. The conjugate ν c of an anti-capacity ν is an anti-capacity defined by ν c (A) = 1ν(A), where A is the complementary of A. The desintegral is defined from the corresponding Sugeno integral, by reversing the direction of the local value scales (x becomes 1x), and by considering a capacity induced by the anti-capacity ν, as follows:

Based on this identity, we straightforwardly obtain the following rules associated to the desintegral S ↓ ν from those derived from the integral S 1-ν c :

Selection rules Each focal T of 1ν c corresponds to the selection rule:

The objects selected by these rules are those that do not possess, to a high extent (less than ν c (T )), faults present in the focal set of the capacity 1ν c . Elimination rules Each focal set of 1ν corresponds to the elimination rule:

The objects rejected by these rules are those possessing to a sufficiently large extent the faults in the focal sets of the capacity 1ν.

proof: The first result is obvious. For the second, notice that 1 -(1ν c ) c (A) = ν(A).


Deniz Çokuslu
email: deniz.cokuslu@izmir.edu.tr

Abdelkader Hameurlain
email: hameurlain@irit.fr

Kayhan Erciyes
email: kayhan.erciyes@izmir.edu.tr

Paul Sabatier

Fault-tolerant resource allocation for query processing in grid environments

Keywords: resource allocation, fault-tolerance, distributed query processing, grid systems, distributed databases

In this paper, we propose a new algorithm for fault-tolerant resource allocation for query processing in grid environments. For this, we propose an initial resource allocation algorithm followed by a fault-tolerance protocol. The proposed fault-tolerance protocol is based on the passive replication of stateful operators in queries. We provide theoretical analyses of the proposed algorithms and consolidate our analyses with the simulations.

Introduction

Grid systems are differentiated from distributed and parallel systems by their large-scale, dynamic and heterogeneous characteristics [START_REF] Foster | The Grid: Blueprint for a New Computing Infrastructure[END_REF]. These characteristics raise additional challenges to the distributed query processing domain such as resource discovery, resource selection, resource allocation, autonomous computing, monitoring, replication, caching, security issues and many others [START_REF] Gounaris | Adapting to changing resource performance in grid query processing[END_REF]. From those, resource allocation is one of the most important steps that directly affect the performance of query execution. However finding near optimal resource allocation alone may not be sufficient for efficiently processing queries in grid environments. Defining the policies in case of node failures during query execution is also very important and should be included in the resource allocation method. Since grid environments are dynamic, eventual node failures are likely during the execution of queries. These failures may be very costly if the queries are long running and if the system is not designed fault-tolerant. Therefore fault-tolerance must be considered in processing queries in grid environments.

In the current literature, there can be found many resource allocation algorithms with dynamicity support [START_REF] Gounaris | Adapting to changing resource performance in grid query processing[END_REF][START_REF] Silva | An adaptive parallel query processing middleware for the grid: research articles[END_REF][START_REF] Venugopal | A grid service broker for scheduling e-science applications on global data grids: research articles[END_REF][START_REF] Kotowski | Parallel query processing for OLAP in grids[END_REF][START_REF] Gounaris | Adaptive workload allocation in query processing in autonomous heterogeneous environments[END_REF][START_REF] Paton | Autonomic query parallelization using non-dedicated computers: an evaluation of adaptivity options[END_REF][START_REF] Quiane-Ruiz | A self-adaptable query allocation framework for distributed information systems[END_REF]. Although these studies provide resource allocation methods by considering dynamicity of resource properties, none of them consider failure of nodes during execution of stateful operators in queries. A query operator is considered to be stateful if its execution requires storage of any kind of state such as a hash table [START_REF] Bestehorn | Fault-tolerant query processing in structured P2P-systems[END_REF]. Since stateful operators like hash join require recovery of states of the nodes in case of node failures, dynamic resource allocation methods are not sufficient in such cases. We have found few studies for fault-tolerant query processing in the current literature [START_REF] Smith | Fault-tolerance in distributed query processing[END_REF][START_REF] Smith | Failure recovery alternatives in grid-based distributed query processing: a case study, knowledge and data management in grids[END_REF][START_REF] Taylor | Recovery from Node Failure in Distributed Query Processing[END_REF][START_REF] Bestehorn | Fault-tolerant query processing in structured P2P-systems[END_REF]. Although these studies provide fruitful algorithms, none of them is specialised on processing stateful query operators in grid environments.

In this paper, we propose a resource allocation algorithm for fault-tolerant query processing in grid environments based on passive replication of stateful operations in queries. For finding the Initial Resource Allocation (IRA) scheme, we first propose the IRA algorithm. After completion of the IRA we propose the Fault-Tolerant Resource Allocation (FTRA) algorithm in which each allocated node applies a replication policy by itself according to the type of the task that it executes.

The contribution of this section is therefore twofold. First, we propose the IRA algorithm by taking advantages of Single Join Operator Resource Allocation (SJORA) algorithm which is presented by Cokuslu et al. (2012b). Second, we propose the FTRA algorithm that presents fault-tolerance for stateful query operators in grid environments. With IRA, we struggle large-scale and heterogeneity characteristics, with FTRA we deal with the dynamicity characteristic of the grid environments taking hash join query requirements into consideration.

In this paper, we assume that the node that posts the query and the nodes in which base relations reside are fault-tolerant or stable by default during the execution of the query. We consider a query as consisting of hash join operators which are composed of atomic tasks, namely scan, build and probe. Scan tasks act as providers to both build and probe tasks by reading tuples from their storage units and sending them to their corresponding tasks. Build tasks receive tuples from their scan tasks and create hash tables for that operator. Probe tasks are blocked during the execution of their corresponding build tasks. After build tasks complete, probe tasks start receiving tuples from their corresponding scan tasks and check for matching tuples in the hash table. Probe tasks pipeline matched tuples through their successor tasks in the query tree. More detailed description of distributed hash join operator can be found in the work of [START_REF] Özsu | Principles of Distributed Database Systems[END_REF].

The structure of this paper is as follows; in Section 2 we present a brief literature survey about the current resource allocation studies. In Section 3, we propose the IRA algorithm followed by the FTRA algorithm for query processing in grid environments. We present detailed design, analyses and simulations for each algorithm. Finally in Section 4, we present our conclusions.

Related work

There can be found many studies in the literature, which examine resource allocation for query processing in grid environments (such as [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF][START_REF] Gounaris | Adapting to changing resource performance in grid query processing[END_REF][START_REF] Kant | Double auction protocols for resource allocation in grids[END_REF][START_REF] Mandal | Scheduling strategies for mapping application workflows onto the grid[END_REF][START_REF] Soe | Efficient scheduling of resources for parallel query processing on grid-based architecture[END_REF][START_REF] Gounaris | A novel approach to resource scheduling for parallel query processing on computational grids[END_REF][START_REF] Silva | An adaptive parallel query processing middleware for the grid: research articles[END_REF][START_REF] Venugopal | A grid service broker for scheduling e-science applications on global data grids: research articles[END_REF][START_REF] Bose | Allocating resources to parallel query plans in data grids[END_REF][START_REF] Kotowski | Parallel query processing for OLAP in grids[END_REF][START_REF] Liu | Grid query optimizer to improve query processing in grids[END_REF][START_REF] Gounaris | Adaptive workload allocation in query processing in autonomous heterogeneous environments[END_REF][START_REF] Paton | Autonomic query parallelization using non-dedicated computers: an evaluation of adaptivity options[END_REF][START_REF] Quiane-Ruiz | A self-adaptable query allocation framework for distributed information systems[END_REF]. A very detailed literature survey related to these studies is presented by Cokuslu et al. (2012a). These studies either present static resource allocation algorithms in which the resource allocation is performed once, and allocated nodes sustain execution until the tasks are completed, or they present dynamic resource allocation algorithms in which allocation is dynamically modified during the execution of the tasks according to the monitored status of the resources. Although dynamic resource allocation algorithms take dynamicity of the characteristics of the environment into account, none of these algorithms consider the case in which node failures occur. Still, there can be found many other studies in the current literature, which examine fault-tolerant distributed query processing in different environments [START_REF] Abadi | The design of the borealis stream processing engine[END_REF][START_REF] Balazinska | Fault-tolerance in the borealis distributed stream processing system[END_REF][START_REF] Bestehorn | Fault-tolerant query processing in structured P2P-systems[END_REF][START_REF] Chandrasekaran | TelegraphCQ: continuous dataflow processing[END_REF][START_REF] Hwang | High-availability algorithms for distributed stream processing[END_REF][START_REF] Hwang | A cooperative, self-configuring high-availability solution for stream processing[END_REF][START_REF] Kwon | Fault-tolerant stream processing using a distributed, replicated file system[END_REF][START_REF] Smith | Fault-tolerance in distributed query processing[END_REF][START_REF] Smith | Failure recovery alternatives in grid-based distributed query processing: a case study, knowledge and data management in grids[END_REF]. However, few of them are applicable in grid environments especially for processing stateful query operators such as hash joins [START_REF] Bestehorn | Fault-tolerant query processing in structured P2P-systems[END_REF].

More precisely, [START_REF] Smith | Fault-tolerance in distributed query processing[END_REF] presented a fault-tolerant query processing system for distributed query processing. Their study is an extension to their previous work OGSA-DQP [START_REF] Alpdemir | OGSA-DQP: a service for distributed querying on the grid[END_REF] with the addition of fault detector and fault handler modules. In their study, the queried node generates a query plan, performs an IRA and initiates the execution of the query. For the fault-tolerance, the algorithm performs a rollback recovery protocol. [START_REF] Smith | Failure recovery alternatives in grid-based distributed query processing: a case study, knowledge and data management in grids[END_REF] discuss failure recovery alternatives in query processing in grid environments. In their study, they examined three failure recovery alternatives, namely restart, reduce and replace. [START_REF] Bestehorn | Fault-tolerant query processing in structured P2P-systems[END_REF] presented a fault-tolerant query processing algorithm in structured P2P systems. In their study, they examined the query operations in two classes: namely stateless and stateful operations. The proposed method examines fault-tolerance over these operations with two different perspectives: fault-tolerant routing and replication. The study exploits the functionalities proposed by the CAN peer-to-peer system for selecting the backup peers. A very detailed survey study related to fault-tolerant distributed query processing can be found in the work of [START_REF] Taylor | Recovery from Node Failure in Distributed Query Processing[END_REF]. In his study, Taylor examines different fault-tolerant distributed query processing algorithms in three classes, namely: (a) upstream backup [START_REF] Smith | Failure recovery alternatives in grid-based distributed query processing: a case study, knowledge and data management in grids[END_REF][START_REF] Smith | Fault-tolerance in distributed query processing[END_REF], (b) active standby [START_REF] Abadi | The design of the borealis stream processing engine[END_REF][START_REF] Balazinska | Fault-tolerance in the borealis distributed stream processing system[END_REF][START_REF] Chandrasekaran | TelegraphCQ: continuous dataflow processing[END_REF] and (c) passive standby [START_REF] Hwang | High-availability algorithms for distributed stream processing[END_REF][START_REF] Hwang | A cooperative, self-configuring high-availability solution for stream processing[END_REF][START_REF] Kwon | Fault-tolerant stream processing using a distributed, replicated file system[END_REF].

Considering our analyses related to fault-tolerance in query processing, we have found many studies examining this problem. Although these studies present valuable algorithms, to the best of our knowledge, we cannot find studies designed especially for grid environments, which examine fault-tolerance in stateful query operators. Most of the examined studies are focused on stream processing which does not include stateful operators. Moreover most of these studies are designed for P2P systems. Although there are many similarities between grid systems and P2P systems, in many aspects they have distinct differences. Therefore, we believe that the characteristics of grid environments and requirements of query processing tasks should be focused in order to find suitable RA algorithms for fault-tolerant query processing in grid environments.

Algorithms

In this section, we propose an algorithm for FTRA for query processing in grid environments. To realise this, we first propose an IRA algorithm by extending the SJORA algorithm which is presented by Cokuslu et al. (2012b). Then, after setting the IRA, we propose FTRA algorithm by introducing a fault-tolerance module that realises passive replication of stateful operators in the queries.

Initial Resource Allocation (IRA) algorithm

In the IRA algorithm, we aim at finding suitable nodes for all tasks that compose the join operators in the entire query. However, since the residing nodes of the temporary relations cannot be determined beforehand, we design the IRA algorithm in bottom-up fashion starting from allocation of resources to the operators that use base relations. In this section, we examine hash join queries, which consist of one or more join operators, as a use case for query operators. We assume that the optimised query operator tree is provided explicitly. The relations that are involved in the query are assumed to be horizontally partitioned into the grid without replication. We consider a query as consisting of hash join operators which are composed of atomic tasks namely, scan, build and probe. A brief description of these tasks is given in the introduction section and detailed are presented in the work of [START_REF] Özsu | Principles of Distributed Database Systems[END_REF].

In SJORA algorithm, Cokuslu et al. (2012b) find and allocate suitable resources for queries consisting of a single join operator assuming scan tasks are already allocated in the nodes in which the base relations reside. Since queries may consist of more than one join operator, it is necessary to extend the SJORA algorithm by materialising the allocation of all tasks in the entire query. In this section, we propose the IRA algorithm, which allocates nodes for the queries that consist of multiple join operators. For the IRA algorithm, we use tree representation of queries. An example query with its tree representation is shown in Figure 1. Vertices in the query tree represent tasks and directed edges represent data flow between tasks. In IRA algorithm, we consider that queries consist of join operators, and join operators consist of scan, build and probe tasks. Each join operator in the query may be composed of more than one pair of build and probe tasks that execute concurrently over the different data partitions. The build and probe tasks in each pair are tightly coupled. Therefore, we decided to allocate each pair of build and probe tasks in the same resource. For simplicity, in the rest of this paper, these pairs of build and probe tasks are named as join tasks. In SJORA algorithm, Cokuslu et al. (2012b) assumed that the partitions of base relations are known at the end of the resource discovery stage. However, for the temporary relations, it is not possible to find out their physical locations before precedent join tasks are allocated. Therefore, in IRA algorithm, we execute multiple instances of SJORA algorithm starting from the join tasks that are located at the lowest level of the query tree.

These kinds of join tasks are marked as first-level join tasks as shown in Figure 1. Then, we allocate the join tasks that are located at the second level in the query tree. We repeat this process until all tasks are allocated in the query. To realise this, we apply post-order tree traversal on the query tree. The generation of the query tree involves query optimisation steps such as query reordering. Since this kind of optimisation is out of scope of this paper, we assume that the query tree is already provided exclusively. The IRA algorithm is executed by the queried node. A snapshot of the IRA is stored in the query tree that resides on the queried node. Each vertex in the query tree contains a data structure called treeElement, as shown in Figure 2. The treeElement contains four principal fields, namely type, list, left and right. Type field indicates the type of the task whether it is a scan or a join task. List field contains a list of allocated nodes for the task, which is initially empty. Left and right fields point to the left and right subtrees, respectively, in the query tree. The IRA algorithm is shown in Algorithm 1. The algorithm runs recursively a post-order tree traversal (lines 1-6). In line 7, the algorithm processes the visited vertex. If the visited vertex is a scan task, IRA algorithm fills list field of the treeElement with the list of nodes in which the partitions of the processed relation reside (line 8). Else, if the visited vertex is a join task, the list field is filled with the results of the SJORA algorithm. In this step, the list of partitions of base or temporary relations is provided by the child vertices (line 10). The estimated sizes of the temporary relations (sizes) are assumed to be known by external estimations. The ids of most distant nodes and the distance between them for the partitions of temporary relations (nodeA, nodeB and dist) are provided by the topology control module of the resource discovery algorithm, which is presented by [START_REF] Cokuslu | A maximum degree self-stabilizing spanning tree algorithm[END_REF]. At the end of execution of the IRA algorithm, all the vertices in the query tree contain the list of selected nodes for the corresponding task. At this stage, the queried node sends the query tree to all selected nodes in order to complete allocation of nodes and to start execution of the query.

Analysis

In this section, we provide time and message complexity analyses of the proposed algorithm, IRA.

Theorem 1: The IRA algorithm has O(jnN) time complexity, where j is the number of join operators in the query, n is the number of scan nodes and N is the number of nodes in the grid system.

Proof: The IRA algorithm uses the SJORA algorithm (Cokuslu et al., 2012b) for each join operator in the query tree. Since the time complexity of the SJORA algorithm is O(nN), the time complexity of the IRA algorithm is O(jnN) for a query that consists of j join operators.

Theorem 2: The IRA algorithm has O(jnN 2 ) message complexity, where j is the number of join operators in the query, n is the number of the scan nodes and N is the number of the nodes in the grid system.

Proof: The IRA algorithm uses the SJORA algorithm (Cokuslu et al., 2012b) for each join operator in the query tree. Since the message complexity of the SJORA algorithm is O(nN 2 ), the total message complexity of the IRA algorithm is O(jnN 2 ) for a query that consists j join operators.

Simulations

In this section, we present evaluation of the IRA algorithm by simulation. We compare our algorithm with a comparative algorithm (CA) that reflects the common properties of the recent resource allocation algorithms [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF][START_REF] Gounaris | A novel approach to resource scheduling for parallel query processing on computational grids[END_REF]. The main idea behind the comparative algorithm is similar to the algorithm proposed by [START_REF] Gounaris | Resource scheduling for parallel query processing on computational grids[END_REF][START_REF] Gounaris | A novel approach to resource scheduling for parallel query processing on computational grids[END_REF]. The algorithm ranks the nodes in the grid according to their properties. In our case, one of the most significant properties that influence the execution of queries is the connection speed of the nodes. Therefore, the CA algorithm ranks the nodes according to their connection speeds. Then the ranked nodes are sorted and the algorithm starts to allocate nodes starting from the top of the list. When addition of a new node does not lead to a performance increase, the algorithm terminates. The CA algorithm traverses the query tree and allocates resources for each join operator in the query. We have implemented IRA and CA algorithms in ns2 simulation environment and measured the cost of resource allocation process and duration of execution of a sample query.

We have generated grid simulation scenarios consisting of 100 through 800 nodes. Each node in the scenario represents a uniprocessor computer in the grid system that has arbitrary connections to other nodes in the environment. The bandwidths of duplex connections between nodes are randomly assigned between 1 and 10 Gbps. In our simulation scenarios, we have simulated resource allocation and execution of a sample query consisting of three join operators, which joins four relations in total. The formal representation of the sample query is shown in Figure 3 where R1, R2, R3 and R4 present relations and presents the join operator. We have collected test results for the cost of IRA and cost of query execution. Figure 4 shows the IRA process for the sample query. As it can be seen in Figure 4, the cost of the IRA algorithm is higher than the CA. This is because the IRA algorithm processes its entire candidate list to find the best possible resource allocation within its candidates and measures the communication speeds from each candidate node to all scan nodes while calculating the estimated query duration. This overhead results in a worse performance than the CA initially in return for a better selection of resources. However, it can be seen in Figure 4 that the IRA algorithm scales well with the number of nodes in the grid environment. The cost of resource allocation process remains nearly constant as the number of nodes increase. This is caused by the limitation of the candidate resource search space. In each scenario, the algorithm examines nearly the same number of candidate resource in the IRA. Like the IRA, the CA also remains nearly constant as the number of nodes increase. This is because in CA the algorithm stops adding new resources when the performance increase reaches to a threshold limit, instead of examining all resources in the candidate list. Otherwise, the CA would examine every resource in the grid environment. This approach may miss better resource allocation combinations with higher number of resources. However, it is conceptually impossible to evaluate all possible resource allocation combinations.

Figure 5 shows the execution cost of the sample query. It can be seen in Figure 5 that the resources allocated by the IRA algorithm execute the query faster than the resources that are allocated by the CA. This is because, although the resources that are allocated by the CA are the highest ranked nodes in the grid, they might be placed far from the scan nodes, which may result in slower data transfer rates. On the other hand, the resources that are allocated by the IRA algorithm are closer to the scan nodes in terms of connection speeds. For that reason, IRA algorithm ensures allocation of more effective resources in terms of the communication performances with the scan nodes. Regarding the simulation results, which are shown in Figures 4 and5, it can be considered that the IRA algorithm is more preferable if the cost of IRA does not exceed the estimated query execution durations. In our simulation scenarios, the durations of query executions are much higher than the costs of the resource allocation processes. Therefore, in such cases, the IRA algorithm might be considered as a better alternative to the existing resource allocation algorithms that are based on ranking functions.

Fault-Tolerant Resource Allocation (FTRA) algorithm

In this section, we propose the FTRA algorithm for query processing in grid environments based on the passive replication of stateful join operators in the queries. The FTRA algorithm works in succession with the IRA algorithm and is responsible for the fault-tolerance of the nodes that are allocated for the join tasks. The nodes that execute tasks are named as master nodes; and the nodes that are allocated for the faulttolerance purpose are named as backup nodes or replicas. It is assumed that a master node and its replica do not fail at the same time.

The FTRA algorithm is composed of four steps: (a) replica selection, (b) query execution & backing up, (c) failure detection and (d) failure recovery. These steps are defined as follow:

1 Replica selection: The replica selection step is realised before the master node starts its execution. When the IRA algorithm completes, each master node determines a backup node by choosing its closest available neighbour. The selection of the closest available neighbour as the replica aims at minimising the replication overhead that will be caused by the FTRA. In this step, we assume that a master node has always at least one available neighbour for replica selection.

2 Query execution & backing up: After the replica selection step, the master node starts executing the query while backing up its state for fault-tolerance. In order to avoid synchronisation issues between replicas and master nodes, the replication scheme in this step is chosen to be passive replication. In passive replication, the states of the master nodes are backed up to their replicas periodically. The states depend on the type of tasks that are being executed. More precisely, build tasks generate hash tables for the join operators. The failure of a node during the execution of build task results in the loss of the hash table that is generated so far. Therefore, during the execution of the build task the state is composed of the hash table and the sequence number of the last tuple that is received. On the other hand, probe tasks receive tuples from their predecessors, check the hash table for occurrences and send results to their successors in a pipelined fashion. Execution of a probe task means that the build task is already terminated and the hash table is already constructed. It also implies that the hash table is already backed up. Therefore, during the execution of the probe task the state is composed only of the sequence number of the last received tuple. The update interval of the replication period is determined heuristically. The states of master nodes are backed up incrementally. In other words, during the execution of build task, each time the state of the master node is backed up, only the additions to the hash table is transferred to the replica node since the last check point.

3 Failure detection: In FTRA, the failure detection is held by both master nodes and replicas. Failures of nodes are detected by exploiting the periodical backup messages. The replica nodes monitor failures of their master nodes and master nodes monitor failure of their replicas by examining delivery of backup and their acknowledgement messages.

4 Failure recovery: Whenever a replica node detects failure of its master node, it replaces itself with its master and notifies its predecessor and successor nodes for the change. Before it starts acting as a master node, it requests a replica node for itself by choosing its closest available neighbour. On the other hand, if a master node detects failure of its replica, it requests a new replica and backs up its last state entirely once and continues incremental backing up later.

The algorithm is executed successively to the IRA algorithm that is proposed in the Section 3.1. When the IRA algorithm is executed beforehand, the algorithm outputs a tree structure, namely query tree, which contains the tree representation of the query with the selected nodes included for the IRA. A sample query tree is shown in Figure 6.

Figure 6 Example query tree that is used for input of the FTRA algorithm Each vertex in the query tree is composed of the data structure treeElement that is shown in Figure 2. The FTRA algorithm inputs the query tree and starts processing it by using post-order tree traversal. Each time the algorithm visits a vertex in the query tree, it sends a request message to resources that are selected by the IRA algorithm in order to inform them about the initial allocation. This allows selected nodes to know their successor and predecessor nodes to communicate with. The formal presentation of the FTRA algorithm in the queried node is shown in Algorithm 2. After finishing the query tree traversal, the queried node waits for the resulting tuples of the query as a pipelined fashion. The other nodes in the grid environment, which receive request messages, involve in the query execution according to the algorithm that is suitable for their types. Basic algorithm steps in the nodes that are assigned for different types of tasks are shown in Algorithm 3. In Algorithm 3, the execution of FTRA algorithm in a node that executes a scan task is presented. A scan node will read tuples from its storage unit and sends them to its successor nodes. In order to start this operation, it first waits for all its successor nodes to become ready to receive tuples (line 2). When all its successor nodes become ready, it starts the scan operation (line 4). Upon finishing the data to be sent, the node indicates this by sending a specific message to its successor nodes (line 6). Notice that it is assumed that scan nodes are stable during the execution of the query therefore they do not require any fault-tolerance algorithm.

Algorithm 3

Basic steps of FTRA algorithm in a scan node Input: Received messages Output: Execution of the required steps 1: Upon reception of AllocScanReq message: 2: Wait StartScan message from all successor nodes 3: When all successor nodes send StartScan message 4: Start sending tuples to the corresponding successor nodes 5: When the data is completely consumed 6:

Send ScanEnd message to all successor nodes 7: end

The execution steps of the FTRA algorithm in a node that is assigned for a join task are shown in Algorithm 4. After being allocated for the task, a join node selects a replica for itself that is the nearest neighbour to it (line 2). Then it claims its readiness to its predecessor nodes (line 3). While receiving tuples from its scan nodes, the join node constructs the hash table (line 4). At the same time it backs up its state periodically in its replica node (line 5). If failure of the backup node is detected, the join node selects another backup node and backs up its entire state once (lines 6-8). When construction of the hash table is finished, the node wakes-up the scan nodes that hold relations for the probe phase and starts probe operation (lines 9 and 10). At this stage, the join node only backs up the sequence number of the scan messages (line 11). When the probe operation is finished, the node informs its successor by sending a specific message (line 12).

Algorithm 4

Basic steps of FTRA algorithm in a join node Input: Received messages Output: Execution of the required steps 1: Upon reception of AllocJoinReq message: 2: Send ReplicaReq message to the nearest neighbour 3: Upon receiving ReplicaResp, send StartScan message to all predecessor nodes 4: Build the hash table using the received tuples from the scan nodes 5: Periodically send hash table updates to the backup node 6: if the backup node is failed then 7:

Select another backup node 8:

end if 9: When build task is finished, send StartScan message to the scan nodes that hold partitions of the relation that is used in the probe task 10: Execute probe task using the received tuples 11: Periodically send last received tuple information to the backup node 12: When probe task is finished, send ScanEnd message to the successor node 13: end Finally in Algorithm 5, the algorithm steps for a node that is allocated for replication is presented. After agreeing with the master node (lines 1 and 2) the backup node periodically accepts backup messages and stores the state information of its master (line 3). If failure of the master node is detected, the backup node informs the predecessor nodes of its master about the failure to suspend data flow (lines 4 and 5). Then it selects a backup node for itself (line 6) and itself starts acting as a master node. It then makes its predecessor nodes to resume the communication and continue the execution of the query (lines 7and 8).

Algorithm 5

Basic steps of FTRA algorithm in a backup node Input: Received messages Output: Execution of the required steps 1: Upon reception of ReplicaReq message: 2: Send ReplicaResp message to the master node 3: Record periodical state updates 4: if master node is failed then 5:

Send AllocUpdate message to all predecessors of the master node in order to suspend communication 6:

Select a backup node by sending ReplicaReq message to the nearest neighbour 7:

Change type of task to join 8:

Send StartScan message to all predecessors to resume the query execution as a master node 9: end if 10: end

Analysis

In this section, we present time and message complexity analyses of the FTRA algorithm.

Theorem 3: The overhead of the FTRA algorithm to the standard query execution in terms of time complexity is O(j), where j is the number of join operators in the query.

Proof: The standard execution of a query in a grid environment consists of execution of scan, build and probe tasks. In FTRA algorithm, additionally to the standard execution, replica selection is required for each join operator before starting the execution. For each join operator, selection of a replica node involves four steps. Since there are j join operators in the query, the total time overhead of the FTRA algorithm is (4j) which is defined as O(j).

Theorem 4: The overhead of the FTRA algorithm to the standard query execution in terms of message complexity is O(jnm), where j is the number of join operators in the query, n is the number of scan nodes and m is the number of allocated nodes for the join tasks.

Proof: In FTRA algorithm, since allocated nodes become ready to receive tuples from their precedent nodes only after they set their backup nodes, beginning of scan tasks are subject to synchronisation with their successors. This synchronisation requires each allocated node to send a message to its scan nodes. Therefore, for each join operator, the FTRA algorithm requires nm message exchanges. Therefore, the total message overhead of the FTRA algorithm is O(jnm).

Simulations

In this section, we present quantitative evaluations and simulation results for the FTRA algorithm. We compare our algorithm to the IRA algorithm and examine the overhead that is caused by the replication.

For the simulation scenario, we used the same simulation setting that is used in the Section 3.1.2. We measured the cost of the resource allocation process.

Figure 7 shows the initial costs of IRA and FTRA algorithms. As it can be seen in Figure 7, there is a slight difference between the IRA and the FTRA. In all different simulation scenarios, the FTRA requires a constant amount of time in order to provide fault-tolerance. This overhead is caused by the selection of the replica nodes. In FTRA, after completion of the IRA, the algorithm executes the finite state machine steps which are shown in Figure 7. In our scenarios, since the number of join operators and number of scan nodes are constant, the overhead of the FTRA algorithm is bound by the number of allocated nodes in the IRA. During our simulations, we observed that the number of allocated nodes by the IRA algorithm does not alter significantly. Therefore, the overhead of the FTRA algorithm remains nearly constant as the number of nodes increase. Regarding the simulation results, it can be considered that the FTRA can be a strong alternative to the classical resource allocation algorithms in the case in which the queries are long running and fault-tolerance overhead is acceptable.

Conclusions

Resource allocation for query processing in grid systems is a very important step that directly affects the performance of query execution. Since grid environments are differentiated from other distributed environments by their large-scale, dynamic and heterogeneous nature, the resource allocation algorithm should address all problems that are caused by these characteristics. In this paper, we have first proposed an IRA algorithm, which allocates resources for a query consisting of multiple join operators by exploiting the SJORA algorithm which is presented by Cokuslu et al. (2012b), aiming at addressing scalability and heterogeneity problems. Then, aiming at addressing the dynamicity problems, we proposed an FTRA algorithm for query processing in grid environments that recovers from node failures during the execution of the query. Although there can be found many studies in the current literature, to the best of our knowledge, we cannot find any study which focuses on the dynamicity of nodes in the grid environment in terms of node failures. For that reason, we aimed at contributing the query-processing domain by proposing fault-tolerance in resource allocation.

We presented our algorithms in detail and proposed complex analyses. Then, we strengthened our perspectives by the use of quantitative analyses and simulations. We showed that the IRA algorithm outperforms the similar existing algorithms in the cases in which the query execution durations are much higher than the cost of the IRA. For the FTRA, the simulation results showed that the algorithm is a very favourable algorithm with slight overhead to the IRA algorithm. Since it provides fault-tolerance, it can be preferred in situations in which the queries are long running and in environments in which node failures are likely. It can be concluded that the proposed algorithms can be considered to be scalable and strong alternatives to the existing algorithms in the defined cases.

Figure 1

 1 Figure1An example query and its query tree

Figure 2

 2 Figure 2 Data structure for the treeElement

Figure 3

 3 Figure 3 Formal representation of the sample query {(R1 R2) (R3 R4)}

Figure 4 Figure 5

 45 Figure 4 Initial resource allocation costs

Figure 7

 7 Figure 7 Cost of the FTRA algorithm