Marco Console

Paolo Guagliardo

Leonid Libkin

Propositional and predicate logics of incomplete information

One of the most common scenarios of handling incomplete information occurs in relational databases. They describe incomplete knowledge with three truth values, using Kleene's logic for propositional formulae and a rather peculiar extension to predicate calculus. This design by a committee from several decades ago is now part of the standard adopted by vendors of database management systems. But is it really the right way to handle incompleteness in propositional and predicate logics? Our goal is to answer this question. Using an epistemic approach, we first characterize possible levels of partial knowledge about propositions, which leads to six truth values. We impose rationality conditions on the semantics of the connectives of the propositional logic, and prove that Kleene's logic is the maximal sublogic to which the standard optimization rules apply, thereby justifying this design choice. For extensions to predicate logic, however, we show that the additional truth values are not necessary: every many-valued extension of first-order logic over databases with incomplete information represented by null values is no more powerful than the usual two-valued logic with the standard Boolean interpretation of the connectives. We use this observation to analyze the logic underlying SQL query evaluation, and conclude that the many-valued extension for handling incompleteness does not add any expressiveness to it.

Introduction

Incomplete information is ubiquitous in applications that involve querying and reasoning about data. It is one of the oldest topics in database research [START_REF] Codd | Understanding relations (installment #7)[END_REF], and is essential in many applications such as data integration [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF], data exchange [START_REF] Arenas | Foundations of Data Exchange[END_REF], inconsistent databases [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF], and ontology-based data access [START_REF] Bienvenu | Ontology-mediated query answering with data-tractable description logics[END_REF].

When it comes to querying incomplete data, practical solutions, such as relational databases, rely on many-valued logics to properly account for the lack of certainty. In fact, every database management system (DBMS) uses a threevalued logic for handling incomplete information, namely Kleene's logic [START_REF] Bolc | Many-Valued Logics: Theoretical Foundations[END_REF]. This was the design choice of SQL, the language of relational DBMSs, Copyright c 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

which is now written into the SQL Standard (ISO/IEC 2016), presented in all database textbooks, and implemented in all database products. However, this is far from the only logic to have been considered for representing incomplete information. The use of Kleene's logic was first proposed by [START_REF] Codd | Understanding relations (installment #7)[END_REF], but many other variants appeared afterward. [START_REF] Codd | More commentary on missing information in relational databases[END_REF] looked at a four-valued logic, but in the end argued against it due to the additional complexity. Nonetheless, well-documented problems with incomplete information [START_REF] Date | A Guide to the SQL Standard[END_REF][START_REF] Date | Database in Depth -Relational Theory for Practitioners[END_REF]) led to the search of more appropriate logics for handling incompleteness. For example, [START_REF] Gessert | Four valued logic for relational database systems[END_REF] revisited four-valued logics, while [START_REF] Yue | A more general model for handling missing information in relational databases using a 3-valued logic[END_REF] considered logics with four, five, and seven values, and showed how to encode them with three. A different kind of four-valued logics for missing data was studied by [START_REF] Console | Approximations and refinements of certain answers via many-valued logics[END_REF], while [START_REF] Darwen | The third manifesto[END_REF] suggested dropping nulls altogether and go back to the usual Boolean two-valued logic.

There is also no shortage of many-valued logics that have been proposed in closely related contexts. For example, a variety of many-valued logics were used in the study of default reasoning [START_REF] Reiter | A logic for default reasoning[END_REF] or in reasoning about inconsistency [START_REF] Zamansky | Non-deterministic semantics for first-order paraconsistent logics[END_REF]. Those are typically based on the notion of bilattices, providing truth and knowledge orderings on the truth values [START_REF] Arieli | Reasoning with logical bilattices[END_REF][START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF]. A common one is Belnap's bilattice with four truth values [START_REF] Belnap | A useful four-valued logic[END_REF][START_REF] Arieli | The logical role of the fourvalued bilattice[END_REF], which also found database applications [START_REF] Grahne | Intuitionistic data exchange[END_REF]; but others exist as well, e.g., many generalizations of Kleene's logic based on numerical intervals describing the degree of being true (Fitting 1991). A manyvalued propositional logic must also provide an interpretation of propositional connectives. To make the general picture even muddier, for different sets of truth values, different semantics of propositional connectives exist, sometimes even non-deterministic ones [START_REF] Arieli | Maximally paraconsistent three-valued logics[END_REF].

Thus, we are far from having a clear picture of what to use as a logic of incomplete information in data management applications. Choices are numerous, and there is no final argument as to why the approach of DBMSs that use Kleene's logic is the right one. Hence, the first question we address is:

1) What is the right many-valued propositional logic for handling incomplete information?

Now suppose we have a propositional logic that correctly accounts for truth values of statements about incomplete information, and for operations on them. In querying data, however, we use predicate logics. Indeed, the core of SQL is essentially a programming syntax for relational calculus, which is another name for first-order (FO) predicate logic.

Of course we know how to lift the semantics of propositional logic to the full predicate calculus by treating existential and universal quantifiers as disjunctions and conjunctions over all elements of the universe. What we do not know is how different choices of propositional logic for incomplete information affect the power of predicate calculus. As one example, consider the version of FO that underlies SQL and is based on Kleene's logic. What extra power does it possess over FO under the usual two-valued Boolean interpretation of the connectives? It was recently argued, by means of rewriting SQL queries, that FO based on Kleene's logic can be encoded in the usual Boolean FO [START_REF] Guagliardo | A formal semantics of SQL queries, its validation, and applications[END_REF]. But is there a general result in logic that underlies such a translation, and what is so special about Kleene's logic that makes it work?

Even more generally, the second question we would like to address is:

2) How does the choice of a propositional logic for incomplete information affect predicate logic?

Finally, we would like to understand how these theoretical considerations relate to the practice of incomplete data in relational databases. A rough approximation of the core of SQL -the way it is presented in many database textbooks -is first-order logic. But as soon as incomplete information enters the picture, this becomes a many-valued FO. And yet there is even more to it: in SQL queries, answer tuples are split into true ones that need to be returned, and others that are not returned, thus collapsing a three-valued logic to twovalued. This leads to our last question:

3) What is the logic that underlies real-life handling of incomplete information in relational databases (i.e., SQL's logic), and how much more power than the usual twovalued FO does it possess?

The goal of this paper is to address these three questions. Below we outline our main contributions.

Propositional logic

To understand what a proper propositional logic for reasoning about incomplete information is, we need to define its truth values, and truth tables for its connectives (we shall concentrate on the standard ones, i.e., ∧, ∨, and ¬, although we shall see others as well). We follow the approach of [START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF] to turn partial knowledge about the truth of a proposition into truth values. If we have a set W of worlds, and two of its subsets T and F in which a proposition is true and false, respectively, this produces a description (T, F, W ). It is possible that T ∪ F = W , i.e., we may have partial knowledge about the truth or falsity of a proposition. We require however that T ∩ F = ∅, as here we do not consider inconsistent descriptions.

Taking those descriptions (T, F, W ) directly as truth values, however, is not satisfactory: we shall have too many of them. Instead, we want to take as truth values what we know about such descriptions.

We abstract this knowledge as epistemic theories of such descriptions: they say what is known about a proposition being possibly or certainly true or false. Then, as truth values we take maximally consistent epistemic theories. We show that there are only six such theories, resulting in a six-valued logic L 6v . Its truth tables are again very naturally derived from epistemic theories of partial knowledge about truth of propositions.

As a final step, we then look at what makes a many-valued logic database friendly. It needs to be a sublogic of L 6v and yet satisfy some basic equivalences we expect to hold to be able to perform query evaluation and optimization. We then show that the maximal sublogic of L 6v that satisfies those equivalences is L 3v , the three-valued logic of Kleene used in all commercial DBMSs. Thus, we justify the choice that was made by SQL designers and standards committees in choosing L 3v as the logic to be implemented in all database products.

Predicate logic

We have justified Kleene's logic L 3v as the right choice for handling incompleteness in database contexts. But database languages are not propositional: they are based on FO instead. Thus, we next look at variants of FO based on propositional many-valued logics such as L 3v and L 6v , and compare their power with that of the usual Boolean FO (denoted by BFO from now on), based on just two values t and f. Our main result is that when added to FO, these many-valued propositional logics add no power: FO based on L 3v , or on L 6v , or on any other many-valued logic (under some mild restrictions on the connectives) has no more power than BFO.

The logic of SQL We finally apply the above observation to SQL's logic. We explain that it corresponds to a L 3v -based FO with an extra connectives that allows one to collapse truth values f and u into one, but it still has no more power than BFO. Thus, even though SQL designers were justified in choosing Kleene's logic as the propositional logic for reasoning about incomplete information, they overlooked the fact that, when considered within FO, such a logic does not add any expressive power.

To sum up, our investigation validates the choice of Kleene's logic by the designers of SQL, but at the same time asks whether it was really necessary and opens up a possibility for future languages that handle incomplete information to avoid the recourse to many-valued logics. Notice that much of the criticism of SQL concentrated on its propositional logic. However we showed that it was very reasonable: a sixvalued logic would have been better justified but the threevalued logic is better at handling computational aspects. For predicate logics, our results say that these many-valued logics could have been avoided altogether. However, the price for this is a different way of expressing logical queries, and thus this result is of more interest for future language design rather than changing the current choices.

Organization The paper is structured around three main themes: propositional logics, predicate logics, and the logic of SQL, followed by conclusions and future work.

Propositional Logics

Our study of logics for incomplete information starts at the propositional level. The goal of this section is to define a propositional logic for handling incompleteness, with a special regard to applications that deal with incomplete data, including relational databases query languages.

To this end, we first need to formally define propositional formulae. We assume a countably infinite set of symbols, referred to as propositional atoms. For a set Ω of connectives with associated (positive) arities, the propositional language L over Ω is defined inductively as follows: every propositional atom is a formula of L; if ω is an n-ary connective in Ω and α 1 , . . . , α n are formulae of L, then so is ω(α 1 , . . . , α n ); nothing else is in L. We assume that the binary connectives ∧ and ∨, for which we use the infix notation, and the unary connective ¬ are always present. As will be relevant in the next section, this general definition allows for the inclusion of additional connectives in the language.

The standard way of evaluating propositional formulae is to associate atoms with truth values, which are then propagated through the connectives by means of truth tables. We define a (propositional) logic L as a pair (T, Ω), where T is the set of truth values and Ω is the set of truth tables, which are functions ω : T n → T, of appropriate arities, associated with the connectives. We say that L is a logic for a language L if L defines truth tables for every connective of L. With a deliberate abuse of notation, we denoted by Ω both the connectives of L and the truth tables associated with them in L. When it is not clear from the context, we use ω L to explicitly denote the truth table of L for the connective ω.

Given a logic L = (T, Ω) for a language L, and a mapping µ from propositional atoms to the truth values in T, the evaluation of a formula α ∈ L under µ in L is the truth value tv L (α, µ) in T defined inductively as follows:

tv L (α, µ) = µ(α) if α is a propositional atom, tv L ω(α 1 , . . . , α n ), µ = ω L tv L (α 1 , µ), . . . , tv L (α n , µ) ,
for every α, α 1 , . . . , α n ∈ L and every n-ary connective ω.

For Ω = {∧, ∨, ¬}, the standard Boolean logic L Bool has truth values {t, f} and truth tables as in Figure 1, while SQL uses Kleene's three-valued logic, denoted by L 3v , with truth values {t, f, u} and truth tables as in Figure 2. But is L 3v the right propositional logic to deal with incomplete information in relational databases? To answer this question, we first need an appropriate model of incompleteness; then, we must define what kind of information truth values represent in this model, and how many of them are needed; finally, we need to define truth tables for ∧, ∨ and ¬ that propagate information in a consistent way.

Model of Incompleteness

In many data management applications, especially those involving knowledge representation and reasoning, the veracity of data is a common problem. This results in dealing with

∧ t f t t f f f f ∨ t f t t t f t f ¬ t f f t Figure 1: The truth tables of L Bool . ∧ t f u t t f u f f f f u u f u ∨ t f u t t t t f t f u u t u u ¬ t f f t u u Figure 2: The truth tables of L 3v .
two main sources of incomplete information: first, queries must be answered over sets of possible worlds and, second, the answer to a query may not be well defined, or known, in some of them. In the literature on many-valued logics, the approach of [START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF]) accounts for both these sources of incomplete information, and we follow it here as a basis for our model. However, as we shall discuss later on in this section, we deviate from Ginsberg's approach with respect to what truth values are and represent.

A propositional interpretation I is a triple (t, f, W ), where W is a non-empty set of worlds, and t and f are functions from L to the powerset of W such that, for every α, β ∈ L, all of the following hold:

t(α) ∩ f (α) = ∅ ; f (¬α) = t(α) ; t(¬α) = f (α) ; t(α ∧ β) = t(α) ∩ t(β) ; t(α ∨ β) = t(α) ∪ t(β) ; f (α ∧ β) = f (α) ∪ f (β) ; f (α ∨ β) = f (α) ∩ f (β) .
Intuitively, t tells us on which worlds a given formula is true, while f indicates where it is false. When a world w is neither in f (α) nor in t(α), the formula α is said to be undefined in w.

In [START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF], objects similar to propositional interpretations defined above are used as truth values for formulae. This is incompatible with the standard evaluation of formulae we defined earlier. Instead, we want to collate the information provided by propositional interpretations and abstract it as truth values. In a sense, a truth value should represent what we know about formulae with respect to interpretations. To formalize this intuition, it is natural to make use of some form of epistemic logic.

Given a propositional language L, the language L KP of epistemic formulae is defined inductively as follows:

• every propositional formula in L is in L KP ; • if ϕ and ψ are in L KP , then so are ϕ ∧ ψ, ϕ ∨ ψ, and ¬ϕ; • if ϕ is in L KP , then so are Kϕ and Pϕ; • nothing else is in L KP . An epistemic formula is said to be subjective if every propositional atom appears in the scope of K or P.

The semantics of epistemic formulae is given with respect to a propositional interpretation I = (t, f, W ) and an appointed world w ∈ W . Whether I and w satisfy ϕ ∈ L KP , written I, w |= ϕ, is inductively defined as follows:

• I, w |= α if w ∈ t(α), for α ∈ L ; • I, w |= Kϕ if I, w |= ϕ for every w ∈ W ; • I, w |= Pϕ if I, w |= ϕ for some w ∈ W ; • I, w |= ¬ϕ if I, w |= ϕ ; • I, w |= ϕ ∧ ψ if I, w |= ϕ and I, w |= ψ ; • I, w |= ϕ ∨ ψ if I, w |= ϕ or I, w |= ψ.
Observe that whether a subjective formula ϕ is satisfied in a propositional interpretation I does not depend on the choice of the appointed world, hence we simply say that I satisfies ϕ, and write I |= ϕ. Moreover, we denote by Mod(ϕ) the set of all models of ϕ, i.e., propositional interpretations that satisfy ϕ. We say that ϕ is satisfiable whenever Mod(ϕ) is non-empty.

We also remark that, unlike the standard operators and ♦ in classical modal logic, K and P here are not dual: while Kϕ implies ¬P¬ϕ, the converse is not necessarily true. To see this, consider a propositional formula α and the interpretation I = (t, f, {w 1 , w 2 }) such that t(α) = {w 1 } and f (α) = ∅; then, it is easy to verify that I satisfies ¬P¬α but not Kα, because w 2 ∈ t(α).

Truth Values

We need to understand what it means for a propositional formula to be true or false in a propositional interpretation. To do that, we resort to the notion of modalities.

Given a propositional formula α, the modalities of α are the modal formulae Kα, Pα, and their negation. Intuitively, the modalities of α describe the way α is true on a given propositional interpretation. To define truth values, then, we will look at the modalities of propositional formulae and their negations.

More formally, for a propositional formula α, we denote by M(α) the set consisting of all modalities of α and ¬α. A subset M of M(α) is called consistent if there exists at least one propositional interpretation I for which every formula in M is satisfied. A subset of M(α) is maximally consistent if, in addition, none of its proper supersets is a consistent subset of M(α).

Intuitively, every maximally consistent subset of M(α) defines a possible way in which a propositional formula can be evaluated on a propositional interpretation. Thus, to capture all possibilities, we need as many truth values as there are maximally consistent subsets of M(α). The following shows that our propositional logic must be six-valued.

Theorem 1. For every propositional formula α, there are at most 6 maximally consistent subsets of M(α). These are:

Kα, Pα,¬K¬α,¬P¬α (1
Proof. Let I = (t, f, W ) be a propositional interpretation. If I satisfies Kα, then by the assumption that W = ∅ it also satisfies Pα, ¬K¬α and ¬P¬α. Thus, we get (1). Otherwise, when I |= Kα, I may or may not satisfy Pα. If it does, then I |= K¬α. Under this assumption, we have two possibilities: either I satisfies P¬α, in which case we get the set (3), or not, and we get (4).

Suppose now I |= Kα and I |= Pα. If I satisfies K¬α, then by the assumption that W = ∅ it also satisfies P¬α. Thus, we get the set (2).

Finally, if I |= K¬α, then I may or may not satisfy P¬α. Thus, we get the sets ( 5) and ( 6), respectively.

We now analyze the information each of the above sets gives us for an arbitrary propositional formula α, and abstract it as a truth value, referring to the six maximally consistent sets in Theorem 1.

(1) We know that α is true in all worlds (Kα). We abstract this as the truth value t (always true).

(2) We know that ¬α is true in all worlds (K¬α), hence α is false in all worlds. We abstract this as the truth value f (always false).

(3) We know that there exists a world w in which α is true (Pα) and there exists a world w in which its negation is true (P¬α). Since α cannot be both true and false in the same world, we have w = w . We abstract this as the truth value s (sometimes true and sometimes false). (4) We know that there is a world in which α is true (Pα) but we do not know whether there is a (distinct) world in which its negation is true (¬P¬α). Thus, α could be true in all worlds, but we do not know that (¬Kα). We abstract this as the truth value st (sometimes true). (5) We know that there is a world in which the negation of α is true (P¬α) and where α is then false, but we do not know whether there is a (distinct) world in which α is true (¬Pα). Thus, α could be false in all worlds, but we do not know that (¬K¬α). We abstract this as the truth value sf (sometimes false). (6) We do not know whether there exists a world in which α is true (¬Pα) nor whether there is one where its negation is true (¬P¬α). That is, we have no information at all, and we abstract this as the truth value u (unknown). Thus, our set of truth values is T 6v = {t, f, s, st, sf, u}.

With each truth value τ and each propositional formula α, we associate the (subjective) epistemic formula χ τ α given by the conjunction of all formulae in the maximally consistent subset of M(α) corresponding to τ . So, for example, χ s α is the conjunction of all formulae in (3), that is, ¬Kα ∧ Pα ∧ ¬K¬α ∧ P¬α. Intuitively, the satisfiability of χ τ α tells us whether it is possible for α to evaluate to the truth value τ .

Truth Tables

With the set of truth values in place, we now look at how the truth tables for the connectives are defined. Starting from the fact that truth values correspond to maximally consistent sets of modalities, we will argue that the truth tables must satisfy two reasonable requirements: consistency and generality.

Consistency Let us first consider the unary connective ¬; given a truth value τ , which truth value should ¬τ denote? If τ is t, intuition tells us that ¬τ should not be t. Indeed, such a situation cannot occur, in the sense that for every propositional formula α there exists no interpretation I that satisfies both χ t α and χ t ¬α . For binary connectives, the situation is similar; for example, t∧t should not be f, as it cannot happen that for propositional formulae α and β there exists an interpretation I that satisfies χ t α , χ t β and χ f α∧β . Thus, we require that each entry in a truth table be consistent in the following sense. Definition 1. Let τ 1 , τ 2 , and τ be truth values in T 6v , and let ω be a binary connective. We say that τ is consistent with ω on τ 1 and τ 2 if there exist propositional formulae α and

β such that χ τ1 α ∧ χ τ2 β ∧ χ τ ω(α,β) is satisfiable.
Similarly, τ is consistent with ¬ on τ 1 if there exists a propositional formula α such that χ τ1 α ∧ χ τ ¬α is satisfiable. The notion of consistency directly yields the truth table of ¬ shown in Figure 3c, due to the following: Proposition 1. For every τ ∈ T 6v there exists one and only one truth value in T 6v that is consistent with ¬ on τ .

However, this is not the case for binary connectives: there are combinations of truth values that admit more than one consistent truth value, so consistency alone does not suffice to univocally define the truth tables for ∧ and ∨. For example, both f and sf are consistent with sf ∧ sf, and both t and st are consistent with st ∨ st. In such cases, how do we choose a suitable truth value? This is what we answer next.

Generality When there is more than one truth value that is consistent with a binary connective, we should pick the most general among them. To illustrate this point, let us consider the case of sf ∧ sf, which admits two consistent truth values: sf and f. Choosing f would preclude the existence of interpretations where the formula is true in some world. On the other hand, sf allows for this possibility without precluding the existence of interpretations where the formula is false in all worlds. We will make this intuition more precise in what follows.

For propositional interpretations I = (t, f, W ) and I = (t , f , W ), we say that I is more general than I (and write I I), if there exists a surjective mapping h : W → W such that, for every propositional formula α and every w ∈ W , all of the following hold:

• w ∈ t(α) implies h(w) ∈ t (α), and

• w ∈ f (α) implies h(w) ∈ f (α).
Intuitively, I is more general than I if, for every propositional formula α, it has more worlds where α is not known to be true or false -that is, worlds that do not belong to either t(α) nor f (α) -but I agrees with I on all the worlds for which this information is present.

Using this notion, we can define a partial ordering on subjective epistemic formulae as follows: we say that ϕ is more general than ψ (and write ψ ϕ) if for every model I of ψ there exists a model I of ϕ such that I I .

Finally, we can use generality to define a preference criterion for choosing a truth value over another when more than one are consistent with a connective. Definition 2. Let τ and τ be truth values that are consistent with ω on τ 1 and τ 2 . Then, τ is preferable to τ with respect to ω(τ 1 , τ 2 ) if

χ τ1 α ∧ χ τ2 β ∧ χ τ ω(α,β) χ τ1 α ∧ χ τ2 β ∧ χ τ ω(α,β)
for all propositional formulae α and β.

Of course, the above still leaves open the possibility that, among the truth values that are consistent with a binary connective, there might not be one that is preferable to all others. Below, we show that this is not the case. Theorem 2. Let ω ∈ {∧, ∨}, let τ 1 , τ 2 ∈ T 6v , and let C be the subset of truth values in T 6v that are consistent with ω on τ 1 and τ 2 . Then, there exists a unique τ ∈ C such that, for every τ ∈ C, τ is preferable to τ with respect to ω(τ 1 , τ 2 ).

Thus, to define the truth table of a binary connective ω, for each combination of truth values τ 1 and τ 2 in T 6v we assign to ω(τ 1 , τ 2 ) the most preferable truth value that is consistent with ω on τ 1 and τ 2 . This yields the truth tables for ∧ and ∨ shown in Figure 3a and 3b, respectively. Finally, we call L 6v the propositional logic consisting of the truth values in T 6v and the truth tables in Figure 3. Coming back to the example of sf ∧ sf mentioned earlier, we now illustrate intuitively why the requirement of generality is indeed reasonable. Suppose that two non-equivalent propositional formulae α and β are both assigned the truth value sf. If the evaluation is correct, then for every propositional interpretation there exists a world in which α is false and a world (not necessarily the same) in which β is false. Both sf and f are consistent with sf ∧ sf, so what truth value should α ∧ β evaluate to? The truth value f would indicate that α ∧ β is false in all worlds of every interpretation for which both α and β result in sf. Clearly, there are interpretations for which this happens, for example (t, f, {w 1 , w 2 }) with f (α) = {w 1 }, f (β) = {w 2 } and t(α) = t(β) = ∅. However, there are also interpretations where this is not the case, for instance (t , f , {w 1 , w 2 ) with t (α) = t (β) = ∅ and f (α) = f (β) = {w 1 }. The truth value sf is general enough to correctly capture the outcome of sf ∧ sf in all situations, including those mentioned above, while f may be incorrect in some cases.

SQL's Propositional Logic

The propositional logic L 6v = T 6v , {∧, ∨, ¬} can express many nuances of the truth value of a propositional formula in the case of incomplete information. But can this logic be used in practice?

The query optimization engines of modern relational database management systems are based on decades of research that relies on a well established set of assumptions on the logic underlying the evaluation. Among these assumptions, there are two crucial properties of the binary connectives: idempotency and distributivity, see [START_REF] Jarke | Query optimization in database systems[END_REF][START_REF] Graefe | Query evaluation techniques for large databases[END_REF]). These are used to transform redundant expressions into equivalent non-redundant ones, in order to reduce the number of superfluous operations to be executed during query evaluation.

∧ t f s st sf u t t f s st sf u f f f f f f f s s f sf sf sf sf st st f sf u sf u sf sf f sf sf sf sf u u f sf u sf u (a) ∨ t f s st sf u t t
The binary connectives in L 6v are weakly idempotent, i.e., for every truth value τ ∈ T 6v we have τ ∧ τ ∧ τ = τ ∧ τ , and likewise for ∨. However, they are not idempotent: s ∧ s and s ∨ s give sf and st, respectively, rather than s. Moreover, ∧ does not distribute over ∨:

s ∧ st (s ∨ s) sf = sf (s ∧ s) ∨ sf (s ∧ s) u and ∨ does not distribute over ∧: s ∨ sf (s ∧ s) st = st (s ∨ s) ∧ st (s ∨ s) u
Due to the lack of idempotency and distributivity, L 6v is unlikely to be implemented in real systems for query evaluation. However, we can look for sublogics of L 6v with the desired properties.

To this end, we say that L = (T, Ω) is a sublogic of L = (T , Ω ) if T ⊆ T and for every ω ∈ Ω there exists ω ∈ Ω such that ω(τ ) = ω (τ ) for every tuple of truth values in T. A sublogic L of L is maximal with respect to a property P if it has P and there is no sublogic L of L with property P such that L is a sublogic of L .

For practical purposes, we want a sublogic of L 6v that has the truth value t and it is maximal with respect to distributivity and idempotency. Theorem 3. L 3v is the only sublogic of L 6v that includes the truth value t and that is maximal with respect to distributivity and idempotency of the binary connectives (∧ and ∨).

Therefore, when it comes to balancing expressiveness and practicality, the much criticized three-valued logic used by SQL is in fact a good choice for dealing with incomplete information in relational databases, at least for the propositional case.

We next examine extensions of propositional logics such as L 6v and L 3v to predicate logics.

Predicate Logics

As already explained, the need to consider predicate logics of incomplete information arises most commonly in querying incomplete databases, where special values -commonly referred to as nulls -indicate incompleteness of some sort.

When atomic formulae may involve nulls -e.g., comparing a null with another value, or checking whether a tuple with nulls belongs to a relation -the standard approach is not to follow the Boolean semantics of FO, but instead to look for a many-valued semantics that will properly lift a propositional logic to all of FO. Such a semantics is by no means unique; we shall see three common versions later in this section.

We now define incomplete relational databases (which are in fact two-sorted relational structures), and consider manyvalued FO logics on them, based on particular propositional logic. While propagating truth values through connectives and quantifiers is completely standard, assigning them to atoms is not unique. We consider three commonly occurring ways:

• one uses the Boolean semantics [START_REF] Bolc | Many-Valued Logics: Theoretical Foundations[END_REF],

• one adopts the approach of SQL [START_REF] Date | A Guide to the SQL Standard[END_REF],

• and yet another is based on tuple unification, to achieve query answers with certainty guarantees [START_REF] Libkin | SQL's three-valued logic and certain answers[END_REF].

As our main result, we show that in the context of manyvalued FO, the exact choice of semantics of atoms, or truth values, or propositional connectives, does not matter: whatever combination of these one chooses, the resulting logic can be encoded in Boolean FO.

Incomplete Relational Structures (Databases)

As is standard in the database field and many applications of incomplete information, elements of relational structures (or relational databases; these terms are used interchangeably) come from two disjoint sets. One is the set Const of constants, i.e., known values that are stored in databases. The other is the set Null of nulls that represent unknown values. We always assume that Const is countably infinite. For the set Null, some options exist, of which the most common are the following.

• Null too is a countably infinite set. This corresponds to the model of marked nulls used both in relational databases and their many applications, such data exchange [START_REF] Arenas | Foundations of Data Exchange[END_REF], data integration [START_REF] Lenzerini | Data integration: a theoretical perspective[END_REF] and OBDA [START_REF] Bienvenu | Ontology-mediated query answering with data-tractable description logics[END_REF]. • Null is a singleton set containing one element denoted by N N N. This is the approach of SQL and implementations of relational DBMSs, where there is just one single null value.

A relational vocabulary σ (which is usually called schema in the database context) is a set {R 1 , . . . , R n , =} consisting of relation names R 1 , . . . , R n , each with an associated arity, plus a binary relation symbol "=" for equality. A structure A of this vocabulary is a tuple A, R A 1 , . . . , R A n , = A , where:

• A is a finite subset of Const ∪ Null, • R A i ⊆ A k
for every i ∈ {1, . . . , n}, and • = A is the binary relation defined as {(a, a) | a ∈ A}.

Many-valued Predicate Logics

A many-valued predicate logic is based on a many-valued propositional logic L with a set T of truth values and Ω of propositional connectives. Such a logic is a pair FO(L), of FO formulae based on the propositional logic (to be defined shortly) and the semantics of its formulae. We assume throughout that L has connectives ∨, ∧ which are commutative and associative. This is necessary to define quantifiers. Other connectives are arbitrary. We assume that truth values t and f are always included in T.

Syntax and semantics of FO(L) Given a propositional logic L with truth values T and connectives Ω, formulae of FO(L) are defined by the following rules.

• Atomic formulae:

if R is a k-ary vocabulary symbol, and x 1 , . . . , x k are variables, then R(x 1 , . . . , x k ) is an atomic formula; we shall also write the more common x 1 = x 2 in place of =(x 1 , x 2 ); -const(x) and null(x) are atomic formulae.

• If ω ∈ Ω is a k-ary connective, and ϕ 1 , . . . , ϕ k are formulae, then ω(ϕ 1 , . . . , ϕ k ) is a formula. • If ϕ is a formula and x is a variable, then ∃x ϕ and ∀x ϕ are formulae.

The notion of free variables is defined in the usual way.

The semantics of a formula ϕ is given with respect to a structure A with universe A and an assignment ν of values in A to free variables of ϕ (i.e., ν is a partial function that is defined on all free variables of ϕ and takes values in A). This semantics will be denoted by ϕ A,ν , and it is a value in T. In other words, assigns a truth value in T to ϕ in a structure A under assignment ν.

The semantics of atoms const and null is as follows:

const(x) A,ν = t if ν(x) ∈ Const, f if ν(x) ∈ Null. null(x) A,ν = t if ν(x) ∈ Null, f if ν(x) ∈ Const.
For propositional connectives and quantifiers, the semantics is defined with the standard lifting rules:

ω(ϕ 1 , . . . , ϕ k ) A,ν = ω( ϕ 1 A,ν , . . . , ϕ k A,ν ) , ∃x ϕ A,ν = a∈A ϕ A,ν[a/x] , ∀x ϕ A,ν = a∈A ϕ A,ν[a/x] ,
where ν[a/x] is the same as ν except that it assigns a to x. The last two rules rely on the fact that ∨ and ∧ are commutative and associative.

For atomic formulae R(x), with R ∈ σ, there are several options, which we now consider, when the underlying logic is either L bool or L 3v .

Boolean semantics This is the standard two-valued FO semantics, with only t and f as truth values, and it is given by

R(x) bool A,ν = t if ν(x) ∈ R A , f if ν(x) ∈ R A ,
for every R in the vocabulary σ (which, recall, includes =).

It is then extended to all of FO with the above rules, resulting in the semantics bool defined for all FO formulae. When ϕ bool A,ν = t we also write the more customary A, ν |= ϕ.

The logic BFO, or Boolean FO, is now formally defined as FO(L bool ) interpreted under bool ; it is the standard FO with only t and f as truth values.

Null-free semantics A tuple ā is null-free if all of its values are from Const. The null-free semantics of FO(L 3v ) is the same as the Boolean semantics for tuples of constants; if any nulls are present, it produces the truth value u:

R(x) nf A,ν =    t if ν(x) ∈ R A and ν(x) is null-free, f if ν(x) ∈ R A and ν(x) is null-free, u if ν(x) contains a null,
for every R in the vocabulary σ (which, recall, includes =).

In particular, for the equality predicate =, this is exactly the semantics used by SQL [START_REF] Date | A Guide to the SQL Standard[END_REF].

Unification semantics A semantics based on the notion of tuple unification was proposed by [START_REF] Libkin | SQL's three-valued logic and certain answers[END_REF] to enforce certainty guarantees for query answers. We say that two tuples ā and b unify if there is a map h : Const ∪ Null → Const that is the identity on constants and such that h(ā) = h( b).

Then, for every relation symbol R in the vocabulary σ, the unification semantics is defined by

R(x) ⇑ A,ν =    t if ν(x) ∈ R A , f if ā ∈ R A s.t. ν(x) and ā unify, u otherwise.
The semantics ⇑ is then lifted to all of FO by the standard lifting rules. The reason this semantics was introduced is that it ensures certainty of answers to FO queries: if ϕ(x) ⇑ A,ν = t, then the tuple ū = ν(x) is what is known as a certain answer to ϕ, i.e., h(A) |= ϕ h(ū) for every map h : Const ∪ Null → Const that is the identity on constants.

Mixed semantics There is a priori no reason to apply the same semantics on each relation symbol R ∈ σ; instead we can freely mix them. A mixed semantics s is then given by a function s : σ → {bool, ⇑, nf} so that R(x) s A,ν = R(x) s(R) A,ν . This generalizes Boolean, unification, and nullfree semantics.

Boolean FO Captures Many-valued FO

We now show that in most cases, many-valued predicate logics do not give any extra power compared to BFO, i.e., the usual FO under the standard Boolean interpretation of connectives and the Boolean semantics of atomic formulae. The notion of capturing a many-valued FO logic by BFO is defined as follows. Definition 3. A formula ϕ of FO(L) over a many-valued propositional logic L with truth values T is captured by BFO under semantics if there exist BFO formulae ϕ τ for each τ ∈ T such that for every structure A and assignment ν of free variables of ϕ we have

ϕ A,ν = τ ⇔ A, ν |= ϕ τ .
FO(L) is captured by BFO if each of its formulae is.

Usually we are interested in formulae that are true in a given structure, i.e., ϕ A,ν = t. If a formula is captured by BFO, this tells us that we do not need many-valued semantics, and instead can simply check whether A, ν |= ϕ t under the usual Boolean semantics.

To capture a many-valued FO by BFO we need very few assumptions. Recall that L = T, Ω is given by a set of truth values and truth tables for connectives in Ω, which we assume to contain at least ∨, ∧ to define quantifiers. In logics such as L bool and L 3v , these connectives are idempotent, i.e., τ ∧ τ = τ ∨ τ = τ for every τ ∈ T. In L 6v , they are weakly idempotent: τ ∧ τ ∧ τ = τ ∧ τ and likewise for ∨. Notice that idempotency implies weak idempotency. This is the only condition we need to impose to be able to lift capturing formulae by Boolean FO from atoms to arbitrary formulae. Theorem 4. Let L be a propositional many-valued logic in which connectives ∧ and ∨ are weakly idempotent. Assume that every relational atom R(x), for R ∈ σ, is captured by BFO under . Then every FO(L) formula over vocabulary σ is captured by BFO under .

To apply this result to the previously considered semantics, we need to capture atomic formulae, under different semantics, in BFO. This is possible for all of them. Proposition 2. Relational atoms are captured by BFO under Boolean, unification, and null-free semantics.

Finally, this tells us that any mixed semantics (including its pure versions, i.e., Boolean, unification, null-free) coupled with any propositional many-valued logic like L 3v or L 6v (as long as it has weakly idempotent conjunction and disjunction) is no more powerful than the standard semantics over two truth values t and f. Corollary 1. Let L be a propositional many-valued logic whose truth values include {t, f, u}, with an arbitrary set of connectives where ∨ and ∧ are (weakly) idempotent. Then for every vocabulary σ, every function s defining a mixed semantics, and every formula ϕ of FO(L) there is a formula ϕ of BFO such that ϕ s A,ν = t iff A, ν |= ϕ . Using this result, we can clarify, in the next section, the question of the power of the logic that underlies real-life database applications that use incomplete information.

The Logic of SQL

Most database texts will claim that the core of SQL, the main relational database query language, is first-order logic FO. This was certainly true in the early stages of SQL design, as it grew out of relational calculus, which is just another name for FO. But then the language gained many features, in particular null values, leading to more complex underlying logics.

These logics are still not well understood, as the formalization of SQL mainly took a different route via relational algebra, which is the procedural counterpart of FO. Several attempts to provide a theoretical language behind SQL looked at relational algebra translations of the language [START_REF] Ceri | Translating SQL into relational algebra: Optimization, semantics, and equivalence of SQL queries[END_REF][START_REF] Van Den Bussche | Translating SQL into the relational algebra[END_REF] or presented semantics of various fragments of the language, often under the simplifying assumption that no nulls are present and no three-valued logic is used [START_REF] Chu | HoTTSQL: Proving query rewrites with univalent SQL semantics[END_REF][START_REF] Negri | Formal semantics of SQL queries[END_REF]. An attempt to find a logic underlying SQL concentrated on its features that go beyond FO (i.e., aggregation) rather than nulls [START_REF] Hella | Logics with aggregate operators[END_REF]. More recent work [START_REF] Guagliardo | A formal semantics of SQL queries, its validation, and applications[END_REF], while providing a direct semantics of SQL, accounted for null values and three-valued logic, and even gave a translation of SQL queries that, similarly in spirit to the results in the previous section, showed how to evaluate them without ever producing the unknown truth value u. This was done, however, at the level of SQL queries. We now analyze the power of SQL and the need for three truth values at a purely logical level.

We start with the basic fragment of relational languages that has the power of FO, or -equivalently -the basic operations of relational algebra, or SQL's select-from-where queries without aggregation. These operate on databases whose values come from Const. Recall that SQL uses a single null denoted here by N N N. Now we add it; how should the logic change to capture this extension? It depends on who is asked to produce such an extension. A logician's approach If the domain is extended by a single constant, we simply consider FO over Const ∪ {N N N} with a unary predicate null( ) that is only true in N N N (to keep the vocabulary relational; alternatively a constant symbol could be added). The interpretation of = is simply {(c, c) | c ∈ Const} ∪ {(N N N, N N N)}, i.e., syntactic equality: N N N is equal to itself, and not equal to any element of Const. In other words, the logic is the usual BFO, with all the atoms interpreted under the Boolean semantics bool .

It would thus be seen, by a logician, as an overkill to introduce a many-valued logic to deal with just one extra element of the domain. Nonetheless, this is what SQL did.

SQL approach: a textbook version The usual explanation of the logic behind SQL is that it adds a new truth value u to account for any comparisons involving nulls. In other words, the logic is FO(L 3v ), and the semantics sql is mixed, combining Boolean and null-free semantics:

• for relational atoms, R(x) sql A,ν = R(x) bool A,ν ;

• for equality, x = y sql A,ν = x = y nf A,ν .

SQL approach: what really happens While the textbook approach comes close to describing the logic of SQL, it misses one important feature of such logic. In essence, we can think of SQL queries as expressions select x from Q 1 , . . . , Q n where θ(x 1 , . . . , xn ) where Q 1 , . . . , Q n are either queries or relations, xi is a tuple of variables returned by Q i , and θ is a condition composed of equalities of variables and constants, or statements Q (ȳ), where Q is another query, or statements Q = ∅, combined using ∧, ∨, and ¬.

Note that in SQL query evaluation, it is the conditions θ that are evaluated in L 3v ; once the evaluation of the where θ clause is finished, only tuples that evaluated to t are kept. To capture this in logic, we need a propositional operator that collapses f and u into f. Such an operator does exist in propositional many-valued logics [START_REF] Bochvar | On a three-valued logical calculus and its application to the analysis of the paradoxes of the classical extended functional calculus[END_REF] and is known as an assertion operator: ↑p for a proposition p evaluates to t if p evaluates to t, and to f otherwise. Let L ↑ 3v be the extension of L 3v with this operator.

The basic SQL query can then be expressed in FO(L ↑ 3v ):

Q(x) = ∃ȳ n i=1 Q i (x i ) ∧ ↑θ(x 1 , . . . , xn ) ,
where ȳ lists the variables present in x1 , . . . , xn but not in x. Thus, the many-valued predicate logic capturing SQL's behavior is FO(L ↑ 3v ) under sql .

To sum up, there are three choices of a logic capturing SQL's behavior: 1) Boolean predicate logic BFO; 2) FO based on Kleene's logic under the sql semantics; 3) FO based on Kleene's logic with the assertion operator under the sql semantics. These logics use different sets of truth values. However, it only matters when formulae evaluate to true, as this determines the output of queries. Thus, to compare logics with different sets of truth values, we say that two logics, FO(L 1 ) under 1 , and FO(L 2 ) under 2 , are true-equivalent if the models of t are the same in both. That is, for every formula ϕ 1 of FO(L 1 ) there is a formula ϕ 2 of FO(L 2 ) such that

ϕ 1 1 A,ν = t ⇔ ϕ 2 2
A,ν = t for every A, ν, and vice versa, for each ϕ 2 of FO(L 2 ) there is a formula ϕ 1 of FO(L 1 ) such that the above condition holds.

Then, with respect to the truth value t, there is no difference between the logics that attempt to model SQL's behavior. Theorem 5. The logics FO(L 3v ) and FO(L ↑ 3v ), both under sql , and BFO, are all true-equivalent.

Thus, the most natural logical approach to adding a null value to the language does not miss any expressiveness of the more complex solutions based on many-valued logics.

Conclusions

To conclude, let us revisit history. Handling incomplete information by logical languages is an important topic, especially in data management. All commercial database systems that speak SQL offer a solution based on a three-valued propositional logic that is lifted then to full predicate logic. This solution was heavily criticized in the literature, but at the level of the chosen propositional logic.

We proposed a principled approach to justifying a proper logic for handling incomplete information, which resulted in a six-valued logic L 6v . However, taking into account the needs of SQL query evaluation (e.g., distributivity laws), the largest fragment of L 6v that does not break traditional evaluation and optimization strategies is Kleene's logic L 3v , precisely the one chosen by SQL.

However, even though the SQL designers were justified in their choice of Kleene's logic, they neglected to consider the impact that lifting it to full predicate logic would have. We showed that it leads to no increase in expressive power; had this been known to the SQL designers, perhaps other choices would have been considered too.

But does this mean that we should abandon many-valued logics of incomplete information? Most likely not: while the theoretical complexity of formulae that result from eliminating many-valuedness is the same as that of original manyvalued formulae, their practical complexity (i.e., if implemented as real life database queries) is likely to be different. This is mainly due to the fact that 40 years of research on query evaluation and optimization had one particular model in mind, and that model used a many-valued logic. However, the observations we made here might have an impact on the design of new languages, since avoiding many-valued logics for handling incompleteness is now an option.

Regarding future directions, we would like to extend the propositional setup with bilattice orderings as is often done [START_REF] Arieli | Reasoning with logical bilattices[END_REF][START_REF] Ginsberg | Multivalued logics: a uniform approach to reasoning in artificial intelligence[END_REF], and understand the right orderings for logics like L 6v . Yet another direction is to drop the restriction t(α) ∩ f (α) = ∅ for every propositional formula α. Such restrictions have been lifted in the study of paraconsistent logics [START_REF] Arieli | Maximally paraconsistent three-valued logics[END_REF][START_REF] Zamansky | Non-deterministic semantics for first-order paraconsistent logics[END_REF], and in fact the question of looking for the right many-valued logic for reasoning about inconsistency has been raised [START_REF] Arieli | What is an ideal logic for reasoning with inconsistency[END_REF]. Our focus would be slightly different, as we want to extend the current study to handle the most common case of inconsistency in data management, namely inconsistency with respect to integrity constraints [START_REF] Arenas | Consistent query answers in inconsistent databases[END_REF][START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF]

Figure 3 :

 3 Figure 3: The truth tables of L 6v for ∧, ∨ and ¬.

Acknowledgments

The authors would like to thank the anonymous referees for their helpful comments. This work was partly supported by EPSRC grants M025268 and N023056.


Leila Amgoud
email: amgoud@irit.fr

Towards a Formal Model for Task Allocation via Coalition Formation

Keywords:

This paper focuses on the problem of generating coalition structures for task allocation via coalition formation. It provides a unified formal framework for constructing those coalitions structures. The framework takes as input a set of coalitions whose structures are abstract, a conflict relation between the coalitions, and a preference relation between the coalitions and returns the coalitions struc-tures. Three semantics for coalitions structures will be proposed: a basic semantics which will return a unique coalition structure, sta-ble semantics and preferred semantics. These two last may return several coalitions structures at the same time.

INTRODUCTION

Generally, to perform complex tasks in multi-agent environments, agents need to form coalitions which are temporary associations between agents in order to carry out joint tasks. As argued in [START_REF] Aknine | Coalition formation methods for multi-agent coordination problems[END_REF][START_REF] Klush | Dynamic coalition formation among rational agents[END_REF][START_REF] Sandholm | Coalition structure generation with worst case garantees[END_REF][START_REF] Shehory | Task allocation via coalition formation among autonomous agents[END_REF][START_REF] Shehory | Methods for coalition formation task allocation via coalition formation[END_REF], task allocation via coalition formation follows a three steps process: i) generating the coalition structures. The idea here is to form the coalitions such that agents within a coalition should coordinate to achieve a task (or a set of tasks), but those in different coalitions do not. ii) Discussing these structures between the agents in order to select the one which will be adopted. iii) Distributing the gain between the agents of each coalition in the coalitions structure. The way in which the coalitions structures are generated depend broadly on the studied problem. In some applications, for example, it may be required that the tasks are independent, or that a single agent should belong only to one coalition at the same time. Inspired from work on argumentation theory, particularly the system developed in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF], this paper provides a unified and general formal framework for generating the coalitions structures. That framework is defined in terms of a set of coalitions, a conflict relation between these coalitions and finally a preference relation between the coalitions. The framework returns three semantics of coalition structures: the basic semantics which returns a unique coalitions structure, stable semantics and preferred semantics which are two different refinements of the basic one and may return several coalitions structures at the same time.

FORMAL FRAMEWORK

Task allocation via coalition formation can be defined as a finite set N of agents who should achieve a finite set T of tasks. Each agent aims at maximizing its own satisfaction and also the satisfaction of the whole multi-agent system in which it is a member.

DEFINITION 1 (FORMAL FRAMEWORK).

A framework for generating coalition structures (FGS) is a triplet <C, R, > where C is a set of coalitions, R is a binary relation representing a defeat relationship between coalitions, R ⊆ C × C, and is a (partial or complete) preordering on C.

DEFINITION 2. Let C1, C2 ∈ C, and S ⊆ C. C1 attacks C2 iff C1 R C2 and not (C2 C1). S is conflict-free iff C1, C2 ∈ S s.t C1 attacks C2. S defends C1 iff for all C2 such that C2 attacks C1, then there is C3 ∈ S s.t C3 attacks C2.
Let's define the basic coalition structure. Intuitively, it is clear that a non-attacked coalitions will belong to the coalition structure. CAtt gathers all such coalitions. This notion is very restrictive since it discards coalitions which appear "good". DEFINITION 3 (COALITIONS STRUCTURE). Let <C, R, > be a finitary FGS. The basic coalitions structure is:

S R, = F i>0 (∅) = CAtt ∪ [ F i≥1 (CAtt)],
where

F (S) = {C ∈ C | C is defended by S}.
In some cases, the set S R, may be empty. This is not always desirable in multi-agents applications. In order to palliate this problem, we define the stable structures and the preferred ones. DEFINITION 4 (STABLE STRUCTURES). Let <C, R, > be a FGS, and S ⊆ C. S is a stable structure iff S is conflict-free and S defeats any coalition which is not in S.

A framework FGS may have several stable structures. These stable structures correspond to different ways of achieving the tasks. DEFINITION 5 (PREFERRED STRUCTURES). Let <C, R, > be a FGS, and S ⊆ C. S is a preferred extension iff S is conflictfree, S defends all its elements, and S is maximal (for ⊆) among the sets satisfying the 2 above conditions.

Note that each framework FGS has at least one preferred structure. PROPERTY 1. Each stable structure is also a preferred one. The reverse is not always true. Moreover, the coalition structure S R, is included in every stable (resp. preferred) structure.

ILLUSTRATION

Let's consider the problem of coalition formation described in [START_REF] Shehory | Task allocation via coalition formation among autonomous agents[END_REF]. In that work, a multi-agent system is supposed to perform a service that requires several criteria <c1, . . ., cr>. Each agent ai ∈ N is supposed to have non-negative capabilities

B i = <b i 1 , . . ., b i r >.
A capability b i j represents the capacity of the agent ai regarding the criterion cj. To each task t ∈ T a vector

B t = <b t 1 , . . ., b t r > of its capabilities is given. An element b t j
k represents the amount of c k necessary for its satisfaction. The function V alue returns the value of a given coalition. It is assumed that the tasks are independent, an agent cannot belong to more than one coalition at a time, and a coalition can work on a single task at a time. A coalition should be minimal since each coalition has a cost, and the more the coalition is large, the more costly it is. Moreover, an agent cannot be in a coalition if it is not useful and it cannot help in the achievement of the task. Before giving the formal definition of a coalition, let's first define formally when a task is achievable. DEFINITION 6. Let C ⊆ N and t ∈ T . C achieves the task t,

denoted by C t, iff ∀ 1 ≤ j ≤ r, a i ∈C b i j < b t j .
The above definition says that a task is achievable by a group of agents if the capabilities of the agents taken together, are sufficient to what is required by the task.

DEFINITION 7 (COALITION).

A coalition is a pair <C, t> s.t: C ⊆ N , t ∈ T , C t, C is minimal for (set ⊆) among the sets satisfying the above conditions. C is the support of the coalition, and t its task. C(AS) is the set of all the coalitions.

The value of a coalition may be equal to the benefit obtained from the coalition minus the cost of that coalition. For the sake of simplicity, we suppose that this value is given and it is a numerical value. The values of coalitions make it possible to compare them. DEFINITION 8. Let <C1, t1>, <C2, t2> ∈ C(AS). <C1, t1> is more beneficial than <C2, t2>, denoted <C1, t1> <C2, t2> iff Value(<C1, t1>) > Value(<C2, t2>).

The coalition structures should satisfy the hypothesis already fixed when defining the problem. The first requirement is that an agent cannot belong to more than one coalition at the same time. This kind of conflict will be called here "Interfere".

DEFINITION 9 (INTERFERING COALITIONS). Let <C1, t1>, <C2, t2> ∈ C(AS). <C1, t1> interferes with C2, t2 iff C1 ∩ C2 = ∅.
The second requirement is that the same task cannot be affected to more than one coalition at the same time. In the coalition structure, it cannot then be the case that two coalitions achieve the same task. This requirement gives raise to another kind of conflict between coalitions. In what follows, this conflict will be called "Competition".

DEFINITION 10 (COMPETING COALITIONS). Let <C1, t1>, <C2, t2> ∈ C(AS). <C1, t1> is in competition with <C2, t2> iff t1 = t2.

The two above relations are brought together in a unique definition of defeat as follows: DEFINITION 11. Let <C1, t1>, <C2, t2> ∈ C(AS). <C1, t1> R <C2, t2> iff: <C1, t1> interferes with <C2, t2> or <C1, t1> is in competition with <C2, t2>.

The basic coalition structure of this system is:

S R, = F i>0 (∅) = CR, ∪ [ F i≥1 (CR, )].
The following result can be shown: THEOREM 1. If the agents do not misrepresent the capabilities of the others, and if they have all the same values for the different coalitions, then their respective frameworks will all return the same coalition structure. Thus, there is no need to the negotiation step.

This result is of great importance since it shows that with such a framework, more work is done by the agents themselves, and consequently this may minimize greatly the communication which is very costly.

CONCLUSION

Inspired from works on argumentation theory, we have proposed a unified, general and abstract framework for generating coalition structures in an elegant way. The formal framework has three components: a set of coalitions, a defeasibility relation between the coalitions, and finally a preference relation between the coalitions. In this abstract framework, the notion of coalition remains an abstract entity and its exact definition depends on the studied application. Regarding the notion of defeasibility, it is induced and defined from the constraints of the application. Finally, the preference relation comes from the values that agents can assign to each coalition. We have proposed three semantics for the coalitions structures. This work is of great importance, since it allows agents to reason about the coalitions, and minimize the negotiation between agents in the second step of the coalition formation process. Moreover, this framework is general enough to capture different propositions made in the literature.