Markus Aschinger

Conrad Drescher

Georg Gottlob

Peter Jeavons

Evgenij Thorstensen

© M Aschinger

Structural Decomposition Methods and What They are Good For

Keywords: Digital Object Identifier 10, 4230/LIPIcs, STACS, 2011, 12

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

edge {v, w} of G. Undirected graphs are thus represented as special cases of arbitrary (possibly directed) graphs. The Gaifman graph of a structure A, is the undirected graph G(A) whose set of vertices is the domain A of A and where there is an edge {a, b} iff a, b ∈ A and a = b, and there exists a tuple in one of the relations of A in which a and b occur jointly. A tree decomposition of the structure A is a tree decomposition for the Gaifman graph, G(A). The treewidth tw(A) of a structure A is defined accordingly, i.e., tw(A) = tw(G(A)). Similarly, the pathwidth pw(A) is defined as pw(G(A). The treewidth tw(C) (pathwidth pw(C)) of a class C of finite structures is the maximum over all tw(A) ( pw(A)) for A ∈ C. A tree decomposition of a hypergraph H is a tree decomposition of the primal graph G(H) of H, which has the same vertices as H and an edge between each pair of vertices that jointly occur in a hyperedge of H.

It is NP hard to determine the treewidth of a structure A. However, for each fixed k, checking whether tw(A) ≤ k, and if so, computing a tree decomposition for A of optimal width, is achievable in linear time [START_REF] Hans | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF], and was recently shown to be achievable in logarithmic space [START_REF] Elberfeld | Logspace versions of the theorems of Bodlaender and Courcelle[END_REF]. Even though the multiplicative constant factor of Bodlander's linear algorithm [START_REF] Hans | A linear time algorithm for finding tree-decompositions of small treewidth[END_REF] is exponential in k, there are algorithms that find exact tree decompositions in reasonable time or good upper approximations in many cases of practical relevance, see for example [START_REF] Hans | On exact algorithms for treewidth[END_REF][START_REF] Hans | Treewidth computations i. upper bounds[END_REF] and the references therein.

The treewidth of a graph or relational structure is an invariant that can be used as a parameter to define infinite classes of graphs (or structures) related to problem instances. Many NP hard problems of practical relevance can be solved in polynomial time on instances of bounded treewidth and some are actually fixed-parameter tractable with respect to treewidth. Given that bounded pathwidth implies bounded treewidth, these results hold a fortiori for bounded pathwidth. The notion of treewidth is at the base of strong meta-theorems such as Courcelle's Theorem [START_REF] Courcelle | The monadic second-order logic of graphs. i. recognizable sets of finite graphs[END_REF], which states that any problem expressible in monadic second-order logic (MSO) over structures of bounded treewidth can be solved in linear time (or, by a recent result, in logarithmic space [START_REF] Elberfeld | Logspace versions of the theorems of Bodlaender and Courcelle[END_REF]). Many problems, e.g. the 3-colorability of graphs, are very easily expressed in terms of MSO, and thus Courcelle's theorem turns out to be a very effective tool for obtaining tractability results.

Hypergraph Decompositions

The structure of a computational problem is sometimes better described by a hypergraph than by a graph. Therefore, various width-notions for hypergraphs have been defined and studied, and often these are more effective than simply considering the associated primal graph. In particular, the notion of hypertree width, which is based on hypertree decompositions [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF][START_REF] Gottlob | Hypertree decompositions: A survey[END_REF][START_REF] Adler | Hypertree width and related hypergraph invariants[END_REF], is an appropriate measure for the degree of acyclicity of a hypergraph. Bounded hypertree width generalizes the concept of α-acyclic hypergraphs developed by Fagin [START_REF] Fagin | Degrees of acyclicity for hypergraphs and relational database schemes[END_REF]. In essence, a hypertree decomposition of width k for a hypergraph H can be obtained from a suitable tree decomposition of G(H) by covering each bag with at most k hyperedges of H. However, under this definition, which actually defines the concept of generalized hypertree width, ghw(H), of a hypergraph H, it is unfortunately NP-hard to determine whether a hypergraph has width ≤ k for k = 3 [START_REF] Gottlob | Generalized hypertree decompositions: NP-hardness and tractable variants[END_REF]. Therefore, to define the actual concept of hypertree width, an additional condition is imposed that ensures the tractability of computing hypertree decompositions of low width (for details, see [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF]). Bounded hypertree width is strictly more general than bounded treewidth because there exist families of hypergraphs with bounded hypertree width whose treewidth is unbounded.

A number of practically relevant problems become tractable for instances whose associated hypergraphs have low hypertree width. Examples are constraint satisfaction problems (CSPs) [START_REF] Dechter | Constraint Processing[END_REF][START_REF] Gottlob | A comparison of structural CSP decomposition methods[END_REF], see Section 3.1 for a definition, and combinatorial auctions [START_REF] Gottlob | On the complexity of combinatorial auctions: structured item graphs and hypertree decomposition[END_REF]. Very roughly, CSPs of bounded hypertree-width are loosely constrained and therefore tractable. CSPs may also become tractable because their associated hypergraphs are -in a precise sense-tightly constrained. Formally this was captured by the entropy-based measure of fractional edge cover [START_REF] Grohe | Constraint solving via fractional edge covers[END_REF].

S TA C S ' 1 1

CSPs whose associated hypergraphs are of bounded fractional edge cover number are tightly constrained and can be solved in polynomial time. Combining hypertree decomposition with fractional edge covers yields fractional hypertree decompositions [START_REF] Grohe | Constraint solving via fractional edge covers[END_REF], a decomposition method that is more general than both hypertree decompositions and fractional edge covers. While hypertree decompositions will be considered again in Section 3.1, this paper mainly deals with tree and path decompositions.

Structure of the Paper. The rest of the paper is structured as follows. In the next section, we present a taxonomy of the main uses of tree decomposition in Computer Science. We will distinguish between two main categories (categories 1 and 2) and four sub-categories (1.a, 1.b, 2.a, and 2.b) of applications of tree decompositions. In Section 3, we give examples of problems that fall into the categories 1.a, 1.b, and 2.a, respectively. In section 4, we describe a relevant version of the Partner Unit Problem (Pup) and report about our recent result [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF] showing that the problem falls in category 2.b and is therefore tractable.

Taxonomy of Main Uses of Tree Decompositions

One may distinguish between two main usages of tree decompositions, each of which can be subdivided in turn into two sub-cases. The following taxonomy will be illustrated with concrete examples in the next sections. When we speak about the treewidth of a problem instance, we mean the treewidth of some graph associated with the instance. Obviously, for each concrete problem, one has to indicate what this graph is, and, whenever necessary, how it can be obtained from the instance.

1.

Proving a problem tractable for instances of bounded treewidth. This is probably the main use of treewidth. The idea is that many practically relevant classes of inputs actually have bounded treewidth, and that for such classes, a polynomial algorithm can be designed. We distinguish between general tractability results and fixed-parameter tractability (FPT) results:

1.a General tractability results. We are able to show that the problem becomes tractable, but the best known polynomial algorithms are of complexity Ω(n f (k) ), where lim k→∞ f (k) = ∞. In many such cases it can actually be proven that the problem is fixed-parameter intractable with respect to the treewidth parameter k. A typical problem in this category, is the CSP problem, which we will discuss in more detail in the next section. 1.b Fixed-parameter tractability results. This is the case if there exists a function f such that the problem is solvable in time f (k) × n O (1) on instances of treewidth ≤ k. If the problem is actually solvable in time f (k) × O(n), then we speak about fixed-parameter linearity. In particular, fixed-parameter linearity results can be obtained whenever Courcelle's Theorem can be applied. To illustrate this, we will discus the Multicut problem in the next section.

Using treewidth as a tool for proving a problem to be generally tractable (on all instances).

There are a number of cases where treewidth is used as a tool in general tractability proofs. Again, we may distinguish between two sub-cases:

2.a

Proving that a problem is tractable both for small and large treewidth. For some problems having some associated implicit or explicit parameter c, it can be shown that there exists a function f such that the problem is tractable both for instances having treewidth ≤ f (c) and also for instances having treewidth > f (c). The tractability proof for low treewidth is usually completely different from the tractability proof for high treewidth. As an example for this category, we will review the problem of checking whether a loop-free undirected graph has a cycle of length 0 mod c, where c is a fixed constant. This problem was shown to be tractable by Thomassen [START_REF] Thomassen | On the presence of disjoint subgraphs of a certain type[END_REF].

2.b

Proving that all yes-instances of a problem have bounded treewidth and that the problem is tractable for this reason. Here, for some explicit or implicit constant parameter c associated with the problem, one is able to find a function t, such that all yes-instances of the problem must have treewidth ≤ t(c). Moreover, one shows that for instances of bounded treewidth the problem is polynomially solvable. Note that this is actually a very special case of Case 2.a. In fact, this means that the high-treewidth case is trivially tractable, because all instances of high treewidth are no-instances. As an example for this category, we will report in Section 4 about a new result related to the Partner Unit Problem (Pup), a problem of industrial relevance [START_REF] Falkner | Modeling Technical Product Configuration Problems[END_REF].

Examples for Tractability Results Based on Bounded Treewidth

As announced, this section contains examples for the usages of bounded treewidth as described under categories 1.a, 1.b, and 2.a. We start with a very brief review of the Constraint Satisfaction Problem (CSP) in Section 3.1. We then describe the Multicut problem and illustrate how a nice generalization of Courcelle's Theorem can be used to show that Multicut is FPT on instances of bounded treewidth. Finally, in Section 3.3 we review Thomassen's famous result stating that it can be determined in polynomial time whether a graph has an even cycle, and more generally, whether a graph has a cycle of length 0 mod c where c is a fixed constant. Our presentation of all these problems and results is necessarily very brief, but we include references to literature containing a full treatment and many more results.

The Constraint Satisfaction Problem

The efficient solution of Constraint Satisfaction Problems (CSPs) has for many years been an important goal of AI research and of related disciplines, in particular, Operations Research and Database Theory. An instance of a constraint satisfaction problem (CSP) (also constraint network) is a triple I = (Var, U, C), where Var is a finite set of variables, U is a finite domain of values, and C = {C 1 , C 2 , . . . , C q } is a finite set of constraints. Each constraint C i is a pair (S i , r i ), where S i is a list of variables of length m i called the constraint scope, and r i is an m i -ary relation over U , called the constraint relation. (The tuples of r i indicate the allowed combinations of simultaneous values for the variables S i ). A solution to a CSP instance is a substitution θ : Var -→ U , such that for each 1 ≤ i ≤ q, S i θ ∈ r i . The problem of deciding whether a CSP instance has any solution is called constraint satisfiability (CS). Many well-known problems in Computer Science and Mathematics can be formulated as CSPs. For example, the famous problem of graph threecolorability (3COL), i.e., deciding whether the vertices of a graph G = Vertices, Edges can be colored by three colors (say: red, green, blue) such that no edge links two vertices having the same color, can be formulated as a CSP as follows. The set Var contains a variable X v for each vertex v ∈ Vertices. For each edge e = v, w ∈ Edges, the set C contains a constraint C e = (S e , r e ), where S e = X v , X w and r e is the relation r = consisting of all pairs of different colors, i.e., r = = { red, green , red, blue , green, red , green, blue , blue, red , blue, green }.

It is well-known, and easy to see, that Constraint Satisfiability is an NP-complete problem. Membership in NP is obvious. NP-hardness follows immediately, e.g. from the NP hardness of 3COL. It is also well-known [START_REF] Bibel | Constraint satisfaction from a deductive viewpoint[END_REF][START_REF] Gyssens | Decomposing constraint satisfaction problems using database techniques[END_REF][START_REF] Dechter | From local to global consistency[END_REF] that the CSP is equivalent to various database problems, e.g., to the problem of evaluating Boolean conjunctive queries over a relational database.

To any CSP instance I = (V ar, U, C), we associate a hypergraph H(I) = (V, H), where V = V ar, and H = {var(S) | C = (S, r) ∈ C}, where var(S) denotes the set of variables in the scope S of the constraint C. The graph G(I) associated with a CSP is the primal graph G(H(I)) of the hypergraph H(I). Note that if all constraints of a CSP instance I are binary, then its associated hypergraph H(I) is identical to its graph G(I).

S TA C S ' 1 1

The following result (for treewidth) was implicit in work of Dechter and Pearl [START_REF] Dechter | Tree-clustering schemes for constraint-processing[END_REF] based on Freuder (see [START_REF] Gottlob | A comparison of structural CSP decomposition methods[END_REF] for clarifications). It was explicitly stated by Kolaitis and Vardi (Theorem 5.4 in [START_REF] Phokion | Conjunctive-query containment and constraint satisfaction[END_REF]) and, by Chekuri and Rajaraman [START_REF] Chekuri | Conjunctive query containment revisited[END_REF], who considered a slightly different graph associated to a CSP-instance I. The more general version for bounded hypertree width was proven in [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF].

Theorem 1. CSPs of bounded treewidth and CSPs of bounded hypertree width are tractable.

Since bounded treewidth implies bounded hypertree width [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF][START_REF] Gottlob | A comparison of structural CSP decomposition methods[END_REF], it is sufficient to consider the proof for bounded hypertree width. A detailed exposition is given in the proof of Theorem 21 of [START_REF] Phokion | Conjunctive-query containment and constraint satisfaction[END_REF]. Essentially it is shown that a CSP instance I of hypertree width k can be transformed in time O(n k ) into an instance I * of size n k , where n is the size of I, whose associated hypergraph is acyclic. I * can then be solved by using Yannakakis' well-known method for answering acyclic queries [START_REF] Yannakakis | Algorithms for acyclic database schemes[END_REF]. The total time for solving I is shown to be n k+1 log n.

It is natural to ask whether we could achieve fixed-parameter tractability (FPT) by finding a better algorithm which would allow us to get rid of the constant k in the exponent of n, and thus to replace the runtime bound by some expression f (k) × n c for a function f and a constant c independent of k. Unfortunately, this appears to be very unlikely. In fact, the problem of evaluating Boolean conjunctive queries, which is identical to the CSP problem, is easily shown to be fixed-parameter intractable (more precisely, W [1]-hard) with respect to either parameter, the query size or the number of variables [START_REF] Papadimitriou | On the complexity of database queries[END_REF], see also [START_REF] Grohe | The parameterized complexity of database queries[END_REF][START_REF] Downey | The parameterized complexity of relational database queries and an improved characterization of W[1]. Complexity, and Logic[END_REF]. It is therefore a fortiori FP-intractable with respect to the treewidth parameter, given that any k-variable CSP has treewidth at most k -1. This makes the CSP a prime example for a problem in category 1.a of our classification.

The precise complexity of solving CSPs (or answering conjunctive queries) of bounded treewidth, or hypertree width, is as follows [START_REF] Gottlob | The complexity of acyclic conjunctive queries[END_REF][START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF]: Theorem 2. Deciding satisfiability for CSP instances of bounded treewidth or bounded hypertree width is LOGCFL-complete.

Given that LOGCFL is a class of highly parallelizable problems included in the well-known very low classes AC 1 and NC 2 , this shows that even though FP-intractable in case of bounded treewidth, the problem is efficiently parallelizable. A concrete parallel algorithm can be obtained by combining the transformation of the original CSP instance of bounded treewidth, I, into an acyclic CSP instance I (see [START_REF] Gottlob | A comparison of structural CSP decomposition methods[END_REF]) (which is an AC 0 -reduction) with the Db-Shunt algorithm described in [START_REF] Gottlob | The complexity of acyclic conjunctive queries[END_REF].

By results of Grohe, Schwentick, and Segoufin [START_REF] Grohe | When is the evaluation of conjunctive queries tractable?[END_REF], for CSPs of bounded arity (i.e., whose constraint scopes and relations are of bounded arity, but otherwise unrestricted), it was shown that bounded treewidth is actually the best possible tractability criterion: a class of CSP instances of bounded arity is tractable if and only if it has bounded treewidth. However, when the constraints can have unbounded arity, bounded treewidth is a sub-optimal tractability criterion and is dramatically outperformed by bounded hypertree width. But, as already alluded to in the introduction, there are yet more powerful decomposition methods, such as fractional hypertree decompositions [START_REF] Grohe | Constraint solving via fractional edge covers[END_REF]. Even bounded fractional hypertree width does not seem to be an optimal structural tractability criterion. An optimal criterion was very recently established by Marx in [START_REF] Marx | Tractable hypergraph properties for constraint satisfaction and conjunctive queries[END_REF], however, this criterion imposes conditions not only on the constraint scopes, but also on the constraint relations, and is thus of a different, less "structural" type. Finally, let us observe that it may be useful to consider hypertree decompositions or their generalizations, rather than just tree decompositions, even in the case of bounded arities. In fact, in Theorem 16 of [START_REF] Gottlob | Efficient core computation in data exchange[END_REF] it was shown that each CSP instance I having n variables is of hypertree width ≤ n/2 + 1, while its treewidth may actually be n -1.

Network Multicut Problems

We now illustrate category 1.b of our taxonomy by a number of variants of the well-known Multicut problem. Multicut problems and their complexity. Multicut problems are highly relevant to the field of network design. The smallest size of a multicut reveals the robustness and stability of a network with multicommodity flows. Given a set H ⊆ V 2 of pairs of terminal vertices of a graph G = (V, E), several forms of Multicut have been considered and have given rise to complexity studies [START_REF] Calinescu | Multicuts in unweighted graphs with bounded degree and bounded tree-width[END_REF][START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF][START_REF] Garg | Primal-dual approximation algorithms for integral flow and multicut in trees[END_REF][START_REF] Guo | Fixed-parameter tractability and data reduction for multicut in trees[END_REF][START_REF] Guo | Complexity and exact algorithms for multicut[END_REF][START_REF] Marx | Parameterized graph separation algorithms[END_REF][START_REF] Marx | Fixed-parameter tractability of multicut parameterized by the size of the cutset[END_REF].

A large part of the literature deals with the Edge Multicut variant in which the solution is a set of edges E ⊆ E that, if removed, separate every terminal pair. Variants in which sets of vertices are removed, such as Unrestricted Vertex Multicut, wherein any vertices can appear in the solution set V , and Restricted Vertex Multicut, wherein no terminal vertices can appear in the solution set, have also been studied [START_REF] Calinescu | Multicuts in unweighted graphs with bounded degree and bounded tree-width[END_REF]. Formal definitions of these versions of Multicut are given below.

In 2006, Guo et al. [START_REF] Guo | Complexity and exact algorithms for multicut[END_REF] present an algorithm which solves all three of the variants of the problem in polynomial time given two constant parameters, the cardinality of the set of terminal pairs, |H|, and the treewidth ω of G.

In [START_REF] Gottlob | A logical approach to multicut problems[END_REF], Gottlob and Tien Lee introduced a new single parameter for which all variants of Multicut are FPT. This unique parameter is the treewidth ω * of the input structure A = (V, E, H), which is equal to the treewidth of the graph (V, E ∪ H). These more recent FPTresults are proved by using a powerful extended version of Courcelle's theorem due to Arnborg, Lagergren, and Seese [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]. By formulating Multicut in such an extended MSO, the considered Multicut problems are shown to be FPT with respect to ω * . Note that if the input graph has bounded treewidth, and if H has bounded cardinality, then, obviously, the entire input structure A = (V, E, H) also has bounded treewidth ω * . However, ω * can be bounded even in cases where G has bounded treewidth but H has unbounded cardinality. The FPT results for bounded ω * are thus a strict generalization of the results by Guo et al. [START_REF] Guo | Complexity and exact algorithms for multicut[END_REF]. These findings demonstrate that powerful logical tools such as the extended version of Courcelle's master theorem by Arnborg, Lagergren, and Seese [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF] can be applied to advance the state of the art in network multicut theory and can help identify parameters of interest in complexity analysis.

Formal definitions of multicut problems. We now define the various different versions of the MULTICUT problem mentioned earlier. The Edge Multicut problem is formally defined as follows:

Definition 3. Edge Multicut (EMC)

Input: An undirected graph G = (V, E), and H ⊆ V × V a collection of pairs of vertices. Task: Find a minimal cardinality set E ⊆ E whose removal disconnects each pair in H.

The vertex variants of the problem were identified by Calinescu et al. [START_REF] Calinescu | Multicuts in unweighted graphs with bounded degree and bounded tree-width[END_REF] and they are defined as:

Definition 4. Unrestricted Vertex Multicut (UVMC) Input: An undirected graph G = (V, E), and H ⊆ V × V a collection of pairs of vertices. Task: Find a minimal cardinality set V ⊆ V whose removal disconnects each pair in H.
If H is a set of pairs of elements, we denote by H 0 the set of all elements occurring in some pair of H, i.e., H 0 = {x|∃y : (x, y) ∈ H ∨ (y, x) ∈ H}.

Definition 5. Restricted Vertex Multicut (RVMC)

Input: An undirected graph G = (V, E), and H ⊆ V × V , a collection of pairs of vertices. Task: Find a minimal cardinality subset V ⊆ V where V ∩ H 0 = ∅ and whose removal disconnects each pair of vertices in H.

S TA C S ' 1 1

It has been shown that all three forms of the problem are NP-complete for general graphs [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF][START_REF] Calinescu | Multicuts in unweighted graphs with bounded degree and bounded tree-width[END_REF] and remain hard even for graphs with bounded treewidth [START_REF] Garg | Primal-dual approximation algorithms for integral flow and multicut in trees[END_REF][START_REF] Calinescu | Multicuts in unweighted graphs with bounded degree and bounded tree-width[END_REF].

A strong master theorem by Arnborg, Lagergren, and Seese. Before showing that the problems become FPT for inputs of bounded treewidth ω * , we present a strong and most useful generalization of Courcelle's Theorem by Arnborg, Lagergren, and Seese [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]. Let us refer to the version of MSO where second-order quantification is restricted to sets of domain elements (e.g., sets of vertices of the input graph) as MSO 1 . Note that Courcelle [START_REF] Courcelle | The monadic second-order logic of graphs. i. recognizable sets of finite graphs[END_REF] and other authors considered an extended version of MSO called MSO 2 which extends MSO 1 by the possibility of quantifying over subsets of any relation of the input structure, e.g., sets of edges of an input graph. Thus, for example, if a relational symbol R is part of the problem signature, then a subformula (∃X ⊆ R)ϕ(X), expressing that there exists a subset X of the relation R such that ϕ(X) holds for some formula ϕ, could be part of an MSO 2 formula. Courcelle's Theorem is actually valid for MSO 2 (and thus, in particular, for MSO 1 ). Arnborg, Lagergren and Seese [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF] considered an important extension of MSO 2 , called extended MSO that can be used to formulate optimization and counting problems. They proved that solving problems expressible in this form over input structures is FPT with respect to the treewidth of these input structures.

While in the original setting in [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF], extended MSO properties were defined in a much more general context, it is sufficient for our purposes to state a drastically simplified definition and, accordingly, a simplified master theorem (Theorem 7). By optimization we here understand the search for a minimum or maximum solution according to some cardinality criteria. The solution itself is an "optimal" assignment of sets to second-order variables that freely occur in some MSO formula, such that the formula is satisfied over a given input structure. More precisely: Definition 6 (simplified version of a definition in [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]). An optimization problem is an extended MSO cardinality optimization problem if it can be expressed in the following form. The input of the problem is a a structure A = (V, E, H), where V is a set (the universe of A), and E and H are binary relations over elements of V . Let ϕ(X) be a fixed MSO 1 or MSO 2 formula over A, where X is either a free set variable ranging over subsets of V , or a binary relation variable ranging over subsets of E. The task is to find an assignment1 among all possible assignments z to the variable X such that:

|z(X)| = opt{|z (X)| : (A, z ) |= ϕ(X)}
where opt is either min or max. A suitable assignment z is called a solution to the extended MSO cardinality optimization problem.

Using this definition, Arnborg, Lagergren and Seese found the following important fixedparameter tractability result [START_REF] Arnborg | Easy problems for tree-decomposable graphs[END_REF]: Theorem 7. Solving extended MSO cardinality problems is fixed-parameter tractable w.r.t. the treewidth of the input structure. In particular, for a fixed extended MSO cardinality optimization problem P , and a class C of input structures whose treewidth is bounded by some constant, the following can be done in linear time:

Determine whether P has a solution for an input from C. Compute a solution for an input from C, if one exists.

Applying the master theorem to multicut problems. We first define a useful formula that states that two vertices x and y are connected by a path that lies entirely in a set S of vertices.

Definition 8. On structures A = (V, E, H) as above, let connects(S, x, y) be defined as follows:

S(x) ∧ S(y) ∧ ∀P ((P(x) ∧ ¬P (y)) → (∃v∃w (S(v) ∧ S(w) ∧ P (v) ∧ ¬P (w) ∧ E(v, w)))).

Lemma 9 ([28]). Over a structure A = (V, E, H) as above, the formula connects(S, x, y) states that there is a path in (V, E) that connects vertex x to vertex y, and this path lies entirely in S. In particular, this is also true for directed graphs.

Theorem 10 ( [START_REF] Gottlob | A logical approach to multicut problems[END_REF]). The problems UVMC, RVMC, and EMC are fixed parameter linear with respect to the treewidth ω * of the input structure (V, E, H).

Proof. (Sketch.) We outline the proof for UVMC. The problem UVMC can in fact be expressed as an extended MSO cardinality optimization problem in the following way: Find an assignment z ⊆ V to set variable X such that |z(X)| = min{|z (X)| : V, E, H, z |= uvmc(X)}, where uvmc(X) is an MSO 1 expression defined as: uvmc(X) ≡ ∀x ∀y (H(x,y) → ∀S(connects(S, x, y) → ∃v(X(v) ∧ S(v)))).

In words, the formula uvmc(X) defines X to be such that for each pair (x, y) ∈ H (i.e., for each pair (x, y) that must be disconnected), whenever there is a set S of vertices from V that contains a path from x to y, then X must intersect S, i.e. contain some vertex from S. In [START_REF] Gottlob | A logical approach to multicut problems[END_REF] it is formally proven that uvmc(X) is true iff the set X is an unrestricted vertex multicut of (V, E, H). The theorem then follows immediately from Theorem 7. Slight variants of this proof yield the corresponding FPT results for RVMC and EMC. For EM C, quantification over subsets of the edge relation is used. For details, see [START_REF] Gottlob | A logical approach to multicut problems[END_REF].

Master theorems such as Courcelle's and the one of Arnborg, Lagergren and Seese are constructive and can be used for the implementation of model-checking tools such as MONA [START_REF] Klarlund | Mona implementation secrets[END_REF] that directly interpret an MSO-formulation of a problem, or directly compile an MSO-formula into a solution algorithm. However, in order to obtain more efficient algorithms and better upper bounds it is currently still advisable to attempt a more detailed ad hoc analysis of the problem at hand, once the master theorems show us they are FPT. The above FPT-results, for example, were used by Pichler, Rümmele and Woltran [START_REF] Pichler | Multicut algorithms via tree decompositions[END_REF] as a starting point for the design of very effective algorithms and for the derivation of rather low complexity bounds for Multicut problems on inputs of low treewidth. In the future we may expect new tools that are able to automatically compile algorithms and bounds of a similar quality. As an intermediate step, we believe that it is rewarding to replace MSO by equally expressive but much simpler (and better optimizable) languages for expressing a problem. One such candidate is the monadic fragment of the wellknown Datalog language [START_REF] Ceri | Logic Programming and Databases[END_REF][START_REF] Ceri | What you always wanted to know about datalog (and never dared to ask)[END_REF]. It was recently shown in [35] that over structures of bounded treewidth, when a tree decomposition is provided, monadic Datalog is exactly as expressive as MSO. As illustrated in [START_REF] Gottlob | Bounded treewidth as a key to tractability of knowledge representation and reasoning[END_REF][START_REF] Gottlob | Tractable database design and datalog abduction through bounded treewidth[END_REF], many problems of practical relevance can be easily encoded in monadic Datalog, and special interpreters that execute monadic Datalog programs over structures of bounded treewidth turned out to be much more efficient than MONA fed with the MSO formulas that are logically equivalent to those Datalog programs. For a further discussion, see Section 5 of [START_REF] Gottlob | Bounded treewidth as a key to tractability of knowledge representation and reasoning[END_REF].

The Even Cycle Problem

The EVEN CYCLE PROBLEM (ECP) is the problem of determining whether a loop-free undirected graph has an even cycle. The tractability of ECP was open for a long time, until Carsten Thomassen proved it polynomial [START_REF] Thomassen | On the presence of disjoint subgraphs of a certain type[END_REF]. Actually, Thomassen proved the following more general result regarding the problems mCP of whether a loop-free undirected graph has a cycle of length 0 modulo m, where m is a fixed positive integer.

S TA C S ' 1 1

Theorem 11 ([53]). For each integer m > 0, mCP is decidable in polynomial time.

As the following proof outline shows, the proof is according to the pattern of Case 2.a in our taxonomy.

Proof. (Outline.) First it is shown that on graphs G = (V, E) of bounded treewidth, mCP is tractable. With Courcelle's theorem this is very easy; it is sufficient to note that mCP can be expressed in MSO. (Given that Courcelle's Theorem was not known, Thomassen gave a slightly more involved ad hoc proof.)

The second part deals with input graphs of "large" treewidth. It is proven that for each fixed m, a number t(m) can be determined, such that all graphs of treewidth > t(m) must actually have a cycle whose length is a multiple of m. Thus, for the specific problem mCP, all instances of "high" treewidth are actually yes-instances. In particular, it is shown by using Robertson's and Seymour's result [START_REF] Robertson | Graph minors. ii. algorithmic aspects of tree-width[END_REF] that t(m) can always be chosen large enough such that G must contain a subdivision of a grid H, which, in turn, must contain a cycle whose length is a multiple of m.

In a similar fashion, while classifying the complexity of model checking for all prefix-classes of existential second-order logic (ESO) over graphs, it was shown in [START_REF] Gottlob | Existential second-order logic over graphs: Charting the tractability frontier[END_REF] that evaluating fixed closed formulas of type ∃R 1 , . . . R k ∀x ∃y φ(V, E, R 1 , . . . , R k , x, y) over a loop-free undirected input graph (V, E), where R 1 . . . , R k are existentially quantified relation symbols of arbitrary arity, and where φ(V, E, R 1 , . . . , R k , x, y) is a quantifier-free first order formula, is feasible in polynomial time. Note that this generalizes Thomassen's theorem, given that for each m, the problem mCP can be expressed by an ESO formula of this type.

4

The Partner Units Problem

In this section, we describe the Partner Units Problem (Pup). First, in Section 4.1, a general version of the problem is given, which is, however, intractable. In Section 4.2 we describe a special version of the Pup which is of particular industrial relevance. It is for this special case that we were able to establish tractability by exploiting the result that all yes-instances must necessarily have bounded pathwidth (and thus bounded treewidth). It is thus the special case which serves as a paradigmatic example of a problem in category 2.b of our taxonomy. In Section 4.2.4 we then report on a prototypical implementation for the special case that already could solve benchmark instances beyond the reach of the heuristic methods and "engineering approaches" previously used to solve this problem. This section gives only a short summary; the original work underlying this section, as well as detailed proofs can be found in [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF].

Definition of the Partner Units Problem and Basic Facts

The Partner Units Problem (Pup) has recently been proposed as a new benchmark configuration problem [START_REF] Falkner | Modeling Technical Product Configuration Problems[END_REF]. It captures the essence of a specific type of configuration problem that frequently occurs in industry. Informally it can be described as follows: Consider a set of sensors that are grouped into zones. A zone may contain many sensors, and a sensor may be attached to more than one zone. The Pup consists of connecting the sensors and zones to control units. These control units can be connected to the same fixed maximum number UnitCap of zones and sensors. 2 Moreover, if a sensor is attached to a zone, but the sensor and the zone are assigned to different control units, 2 For ease of presentation we assume that UnitCap is the same for zones and sensors.

then the two control units in question have to be (directly) connected. However, a control unit cannot be connected to more than InterUnitCap other control units (the partner units).

The Pup occurs e.g. in the following application domain: Consider a museum where we want to keep track of the number of visitors that populate certain parts (zones) of the museum. To this end the doors leading from one zone to another are equipped with sensors. To keep track of the visitors the zones and sensors are attached to control units; the adjacency constraints on the control units ensure that communication between control units can be kept simple. It is worth pointing out that the Pup is not limited to this application domain: It occurs whenever sensors that are grouped into zones have to be attached to control units, and communication between units should be kept simple.

Figure 1 shows a Pup instance and a solution for the case UnitCap = InterUnitCap = 2six sensors (left) and six zones (right) which are completely inter-connected are partitioned into units (shown as squares) respecting the adjacency constraints. Note that for the given parameters this is a maximal solvable instance; it is not possible to connect a new zone or sensor to any of the existing ones.

= (V 1 , V 2 , E)
into a set U of bags such that each bag contains at most UnitCap vertices from V 1 and at most UnitCap vertices from V 2 ; and has at most InterUnitCap adjacent bags where the bags U 1 and U 2 are adjacent whenever v i ∈ U 1 and v j ∈ U 2 and (v i , v j ) ∈ E. To every solution of the Pup we can associate a solution graph. For this we associate to every bag u ∈ U a vertex u ∈ U . Then the solution graph

G * has the vertex set V 1 ∪ V 2 ∪ U and the set of edges {(v, u ) | v ∈ u ∧ u ∈ U } ∪ {(u i , u j ) | u i
and u j are adjacent.}. In the following we will refer to the subgraph of the solution graph induced by the u as the unit graph.

The reasoning tasks for Pup instances that we consider in this paper are the following: Decide whether there is a solution (Pudp). Find a solution (Pusp). Find an optimal solution; i.e. one that uses the minimal number of control units (Puop). The rationale behind the optimization version is that (a) units are expensive, and (b) connections are cheap. Especially the case where the maximum number InterUnitCap of connections between units is limited to two is of great interest for our partners in industry.

S TA C S ' 1 1

By a reduction from BinPacking it can be shown that Puop is NP-complete [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF] when InterUnitCap = 0, and UnitCap is part of the input. We also observe [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF] that a Pup instance has no solution if it contains K 1,n or K n,1 as a subgraph, where n = ((InterUnitCap+1) * UnitCap)+1.

A Special Case: InterUnitCap = 2

We now turn to the announced special case, which consists of Pups where InterUnitCap = 2, i.e. the number of neighbors of any given unit in a solution is bounded by 2. This special version of the Pup, which is of high industrial relevance, can be directly tackled. We will do this by giving an algorithm that decides this version of the Pup in NLogSpace by exploiting the notion of a path decomposition of a given graph.

For ease of presentation in the sequel we make the simplifying assumption that the underlying bipartite graph is connected. This does not affect solutions of the Pudp and the Pusp, where the connected components can be tackled independently. For optimal solutions, however, the connected components of an underlying graph will have to be considered simultaneously; cf. the discussion in section 4.2.3.

Basic Properties of the Pup (Special Case)

We proceed by identifying basic properties of the Pup in the special case. The key observation is that the units and their interconnections form a special kind of unit graph in any solution: either a simple path, or a simple cycle. This holds because each unit is connected to at most two partner units. Moreover, cycles are more general unit graphs than paths: Every solution can be extended to a cyclic solution; hence in the sequel we only consider cyclic solutions.

Exploiting this observation we can transform the Pup into the problem of finding a suitable path decomposition P of the zones-and-sensors-graph G:

S 1 ⊆ V 1 , S 2 ⊆ V 2 with |S i | ≤ UnitCap such that S 1 ∪ S 2 are in every bag of P. (c) Apart from S 1 ∪ S 2 each bag contains at most 2 * UnitCap elements from V 1 (or V 2 , respec- tively). (d) For any vertex v ∈ V 1 ∪ V 2 all
neighbors of v appear in three consecutive bags of P (assuming the first and last bag to be connected). (e) For each bag χ(w i ) of P it holds χ(w

i ) = f -1 (U 1 ) ∪ f -1 (U i ) ∪ f -1 (U i+1 ) for 1 ≤ i ≤ n -1. (f) S 1 = f -1 (U 1 ) ∩ V 1 and S 2 = f -1 (U 1 ) ∩ V 2 .
Proof. If G is solvable then there is a solution G * whose unit graph is a cycle U 1 , . . . , U n , U 1 . Consider P = (P = w 1 , . . . , w n-1 , χ) where χ(w

i ) = f -1 (U 1 ) ∪ f -1 (U i ) ∪ f -1 (U i+1
). This P is indeed a path decomposition:

Every edge (v 1 , v 2 ) is in some bag. Assume Intuitively, the vertices in the sets S 1 and S 2 from condition (b) above are those that close the cycle (i.e. that are connected to unit U 1 ). These have to be in every bag as some of their neighbors might only appear on the last unit U n .

An Algorithm for the Special Case

By Theorem 12 we know that if a Pup instance is solvable then there is a path decomposition with specific properties. But we still need an algorithm for finding such suitable path decompositions. Many algorithms for finding path decompositions of bounded width have been proposed in the literature. But for the Pup we want to find path decompositions P with specific properties:

The paths should be short (the number of bags reflects the number of units); and hence, The bags should be rather full (in "good" solutions the units will be filled up).

The construction of the bags must be interleaved with checking the additional constraints.

Below we introduce a novel algorithm that fits the bill; it is inspired by the algorithm for finding hypertree decompositions from [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF]. This non-deterministic algorithm does the following: The bags on the path decomposition are guessed. The initial bag partitions the graph into a set of remaining components that are recursively processed simultaneously. A single bag suffices to remember which part of the graph has already been processed; the bag separates the processed part of the graph from the remaining components. Consequently, the current bag and the remaining components can be stored in in logarithmic space, and the algorithm runs in NLogSpace. In addition to the bags the unit function is guessed, too. According to condition (2d) of Theorem 12 all neighbors of any vertex in G occur in three consecutive bags in P. Hence, for checking locally that the unit function is correct it suffices to remember three bags at each step.

A closer look reveals that it actually is enough to remember only U 1 and two "first" and "second" units U i-1 and U i . At each step the current bag's content is then given by the union of U 1 with U i-1 ∪ U i . For the next step a third unit U i+1 is guessed. All neighbors of vertices assigned to the current second unit U i are guaranteed to appear in U i-1 ∪ U i ∪ U i+1 . For the current first unit U i-1 this will already have been established (if i > 2); hence, in the next step the new current first and second unit U i and U i+1 together with U 1 are again a proper separator. The neighbors of U 1 , however, are only guaranteed to appear somewhere on the first, second, or last unit. Upon termination the current "second" unit is the last unit in the cycle. But in addition to the first unit U 1 the second unit U 2 has to be stored throughout a run of the algorithm, too:

DecidePup(G) 1 Guess disjoint non-empty U 1 , U 2 ⊆ V (G) with |U i ∩ V 1 | ≤ UnitCap ≥ |U i ∩ V 2 | 2 C R ← G \ (U 1 ∪ U 2 ) 3 if DecidePup (C R , U 1 , U 2 , U 1 , U 2 ) 4 then ACCEPT 5 else REJECT S TA C S ' 1 1 DecidePup(C R , U 1 , U 2 , U i-1 , U i ) 1 if C R = ∅ 2 then 3 if ∀v ∈ U 1 nb(v) ⊆ U 1 ∪ U 2 ∪ U i and ∀v ∈ U i nb(v) ⊆ U i-1 ∪ U i ∪ U 1 4 then ACCEPT 5 else REJECT 6 else 7 Guess non-empty U i+1 ⊆ V ( C R ) with |U i+1 ∩ V 1 | ≤ UnitCap ≥ |U i+1 ∩ V 2 | 8 For v ∈ U i check nb(v) ⊆ (U i-1 ∪ U i ∪ U i+1 ) 9 C R ← (C R \ U i+1 ) 10 DecidePup (C R , U 1 , U 2 , U i , U i+1 )
Using this algorithm in [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF] we show the following:

Theorem 13 (Tractability of Pudp). The decision problem for the Pup is solvable by the algorithm DecidePup in NLogSpace for InterUnitCap = 2 and any given fixed value of UnitCap.

Answer Extraction

For actually obtaining a solution to a Pup instance we face the following problem: In general it is not possible to remember the contents of all the bags in logarithmic space. Theoretically this problem can be solved as follows: On a first accepting run of DecidePup we clearly can remember the first bag's contents in logarithmic space. We can then run DecidePup again with a fixed first bag, and so forth. Hence the following holds: Theorem 14 (Tractability of Pusp). The problem of finding a solution to the Pup is solvable in NLogSpace for InterUnitCap = 2 and any given fixed value of UnitCap.

Note that the problem of answer extraction disappears when actually implementing the nondeterministic algorithm on a deterministic computer; cf. section 4.2.4.

Towards an Efficient Algorithm

We next make a number of observations that can be exploited to turn DecidePup into a practically efficient algorithm. Guiding the Guessing Not all zones and sensors assigned to units have to be chosen randomly. At most UnitCap neighbors of sensors and zones on the first unit can be assigned to the last unit. Hence the following holds:

3 |nb s (U 1 ) \ (U 1 ∪ U 2 )| ≤ UnitCap ≥ |nb z (U 1 ) \ (U 1 ∪ U 2 )|.
Moreover, the neighbors of U 1 not assigned to U 1 or U 2 may only be guessed in the last step, where the number of unprocessed sensors (or zones) is at most UnitCap.

Starting from i ≥ 2 we have the stronger:

(nb s (U i ) \ (U i ∪ U i-1 )) ⊆ U i+1 ⊇ (nb z (U i ) \ (U i ∪ U i-1 )).
Finding Optimal Solutions First Next recall that "good" solutions correspond to short path decompositions with filled-up bags. Moreover, the number of units used in the solution of a

Pup instance G = (V 1 , V 2 , E) can always be bounded by lb = max (|V1|,|V2|)
UnitCap from below and ub = max (|V 1 |, |V 2 |) from above [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF]. Hence we can apply iterative deepening search: First, try to find a solution with lb units; if that fails increase lb by one. This has the effect that the first solution found will be optimal. This yields the following: Corollary 15 (Tractability of Puop). On connected input graphs the optimization problem for the Pup is solvable in NLogSpace.

In this context let us point out that branch-and-bound-search (on the number of units used) does not work: E.g. a K 6,6 graph does not admit solutions with more than three units. Symmetry Breaking We already observed that cycles are more general unit graphs than paths. But with cycles for unit graphs there is rotational symmetry: For a solution with unit graph U 1 , . . . , U n , U 1 there is a solution U 2 , . . . , U n , U 1 , U 2 , etc.. We can break this symmetry without additional computational cost by requiring that the first sensor is assigned to unit U 1 ; and the second sensor appears somewhere on the first half of the cycle.

Puop and Multiple Connected Components

Next let us discuss the problem of finding optimal solutions when the input graph consists of more than one connected component. Here, part of the problem is that any two connected components may either have to be assigned to the same, or to two distinct unit graph(s). A priori it is unclear which of the two choices leads to better results. E.g. if we assume that UnitCap = 2 then two K 3,3 should be placed on one cyclic unit graph, while two K 6,6 must stand alone. In [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF] we are able to show the following:

Theorem 16 (Tractability of Puop on Multiple Connected Components). For InterUnitCap = 2 and any given value of UnitCap the optimization problem for the Pup on multiple connected components is solvable in NLogSpace if there are only logarithmically many connected components in the input graph.

Implementation and Evaluation

We prototypically implemented the DecidePup algorithm in Java, replacing the non-determinism by a backtracking search mechanism. A detailed description of the procedure is beyond the scope of this paper. However, in [START_REF] Gottlob | A backtracking-based algorithm for hypertree decomposition[END_REF] a deterministic backtracking version of the non-deterministic hypertree decomposition algorithm from [START_REF] Gottlob | Hypertree Decomposition and Tractable Queries[END_REF] is described, and the issues we face when making DecidePup deterministic are very similar. Suffice it to say the following: To avoid repeated sub-computations we store those pairs of bags and remaining components (represented by unassigned neighbors) that could not be decomposed. We don't store successful pairs -the first such pair occurs when finding a solution. As there are only polynomially many such pairs the overall runtime of the algorithm is polynomial [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF]. Finally observe that for the backtracking search we have to store the choices made, and hence answer extraction is easy.

We have evaluated our algorithm on a set of benchmark instances that we received from our partners in industry. Using our prototypical implementation we could solve many instances that were beyond the reach of the previously used heuristic methods and engineering approaches [START_REF] Aschinger | Tackling the Partner Units Problem[END_REF].

Conclusion

In this work we have reviewed structural problem decomposition methods, such as path-, tree-, and hypertree decompositions. We have introduced a taxonomy of usages of treewidth for proving tractability results, and illustrated each category by an example. In particular, we have shown

S TA C S ' 1 1

that treewidth (or pathwidth) can be applied in two distinct main ways: Either to show that a problem is efficiently solvable when a width parameter is fixed, or to prove that the unrestricted (or some width-parameter free) version of a problem is tractable by using a width-notion as a mathematical tool for directly solving the problem at hand. As a show case for the latter usage we have reported on some recent results concerning the Partner Units Problem, a type of configuration problem that was proposed to us by an industrial partner. We have shown that, while the Pup is intractable in general, the notion of a path decomposition can be used to obtain a polynomial algorithm for a highly relevant special case. Our prototypical implementation of the respective DecidePup algorithm could solve many previously unsolvable problem instances.

There is still significant work to be done on the Pup:

We need to analyze the cases with InterUnitCap = k and UnitCap = m for fixed constants k > 2, m. We would like to find better algorithms for the NP-hard general case (when InterUnitCap and UnitCap are unbounded).

We have not yet exploited heuristics for the search.

Figure 1

 1 Figure 1 Solving a K6,6 Partner Units Instance -Partitioning Sensors and Zones into Units

Theorem 12 (

 12 Pup is Path-Decomposable). Assume a Pup instance given by a graph G = (V 1 , V 2 , E) is solvable with a solution graph G * with |U | = n. Let f be the unit function that associates vertices from G to U . Then there is a path decomposition P = (P, χ) of G of pathwidth ≤ (3 * 2 * UnitCap) -1, with the following special properties: (a) The length of P is n -1; P = w 1 , . . . w n-1 . (b) There are sets

v 1 and v 2

 2 are assigned to two different connected units U i and U i+1 . Then {v 1 , v 2 } ⊆ χ(w i ). The connectedness condition is satisfied: For the vertices connected to unit U 1 the induced subgraph is P . All other vertices occur in at most two consecutive bags. Every bag in P contains ≤ (3 * 2 * UnitCap) elements; hence pw(P) ≤ (3 * 2 * UnitCap) -1. An optimal path decomposition of the complete bipartite graph K n,n with n = 3 * UnitCap has width (3 * 2 * UnitCap) -1; cf. figure1. Hence the bound is tight. The conditions (a -f ) are easily seen to hold for the path decomposition P constructed above.

An assignment z to the variable X is an interpretation of X that maps X to a subset z(X) of V if X is unary and a subset of E if X is binary.

We denote by nbs(U ) the set of sensors adjacent to vertices in U .

Acknowledgment. Work funded by EPSRC Grant EP/G055114/1 "Constraint Satisfaction for Configuration: Logical Fundamentals, Algorithms and Complexity. G. Gottlob's work, in particular, with respect to specific topics arising in the context of the co-operation with Siemens Austria and the University of Klagenfurt, was also partially funded by the FFG Fit-IT project Reconcile. G. Gottlob would also like to acknowledge the Royal Society Wolfson Research Merit Award.


Dionysis Athanasopoulos

Apostolos V Zarras
email: zarras@cs.uoi.gr

Fine-grained Metrics of Cohesion Lack for Service Interfaces

A design issue that often appears in real-world services is that their interfaces are not cohesive, i.e., they consist of many and possibly unrelated operations. This issue may complicate the comprehension of the services functionalities and the maintenance of the applications that use them. Currently, the state of the art on cohesion metrics for service interfaces is limited. In particular, there exist coarse-grained metrics of cohesion lack, which consider that the operations of a service interface are related if the types of certain of their input/output data exactly match. The problem in this approach is that operations which operate on data characterized by similar, but not exactly matching, types are treated as being totaly unrelated. Consequently, the aforementioned metrics may overestimate the cohesion lack of service interfaces. In this paper, we undertake a more elaborate approach. Specifically, we propose two fine-grained metrics of cohesion lack, which are defined with respect to the structural similarity of the input/output data types of interface operations. The proposed metrics are formally defined and analytically assessed with respect to fundamental properties of software metrics. Moreover, the usefulness of the metrics in identifying cohesion problems is evaluated in real-world services.

I. INTRODUCTION

The service-oriented architecture (SOA) paradigm aims at facilitating the work of distributed application developers [START_REF] Thomas | Service-Oriented Architecture: Concepts, Technology, and Design[END_REF], [START_REF] Cardoso | Semantic Web Services, Processes and Applications[END_REF]; software reuse is promoted via services that are available to anyone who wishes to compose them towards constructing a novel customized application. Nevertheless, the rapid and low-cost aspects of the overall development process should not be taken for granted. These aspects depend on how well-designed are the services, used for building service-oriented applications. In this paper, we investigate the issue of cohesion. Cohesion was introduced in the early 70s [START_REF] Stevens | Structured design[END_REF] and refers to the degree to which the elements of a module belong together. The lack of cohesion leads to poorly designed systems that are hard to comprehend and maintain.

In general, cohesion can be regarded from different perspectives [START_REF] Stevens | Structured design[END_REF], [START_REF] Yourdon | Structured Design[END_REF]. According to [START_REF] Stevens | Structured design[END_REF], [START_REF] Yourdon | Structured Design[END_REF], the best possible types of cohesion are functional, sequential and communicational. In a functionally cohesive module, all the elements of the module contribute in a single well defined task. In a sequentially cohesive module, the outputs of one element are used as inputs for other elements. In a communicationally cohesive module, the elements operate on the same data.

Generally, in service interfaces, cohesion concerns the degree to which the operations of a service interface belong together. However, since functional cohesion is a purely conceptual notion that can not be quantified, we specifically focus on the notions of sequential and communicational cohesion.

Taking a real-world case, Amazon is a major service provider that offers a variety of Web services. Among these services, the Amazon Simple Queue Service (SQS) enables communication via message queues, allocated on the Amazon infrastructure. Figure 1 shows one of the main interfaces of the SQS service, called MessageQueue1 . This interface provides a quite large number of operations, which enable deleting a queue, getting/setting certain queue attributes/timeouts, adding/removing/listing access permissions for a particular queue, sending messages to a queue, receiving messages from a queue and changing the visibility of messages. The MessageQueue interface is not cohesive, in the sense that it includes various functionalities that do not belong together (queue attributes management, access rights management, message exchange operations). Consequently, a developer who aims at building a queue client (QueueClientApplication in Figure 1) that communicates with other queue clients through an existing queue is supposed to study the specification of the MessageQueue interface (which consists of 838 lines of WSDL and XML schema definitions) and a 49 pages API reference guide. Nevertheless, amongst the various operations offered by the MessageQueue interface, only 4 are actually related to the exchange of messages. A more cohesive decomposition of the provided operations into separate interfaces that relate to the management of queue attributes, the management of access rights and the exchange of messages would simplify the comprehension of the functionalities that the developer actually needs. Regarding the queue client application, we may further consider maintenance scenarios that involve new releases of the MessageQueue interface. Such scenarios may be quite frequent. Specifically, since 2006 there have been various different releases of MessageQueue, which were not always backwards compatible. In the 2008 release, the access rights management operations (ListGrants(), AddGrant(), RemoveGrant()) were removed from the interface. Dealing with such situations, amounts to reasoning about whether the changes from one release to the other actually affect the queue client application. Again, a more cohesive decomposition of the provided operations that groups the message exchange operations into a separate interface would simplify the aforementioned reasoning.

Despite the widely recognized importance of cohesion as a general design property of software, the state of the art on cohesion metrics in the context of the SOA paradigm is quite limited. Specifically, for sequential and communicational cohesion, there exist coarse-grained metrics of cohesion lack, which consider that the operations of a service interface are related if the types of certain of their input/output data exactly match [START_REF] Perepletchikov | Cohesion Metrics for Predicting Maintainability of Service-Oriented Software (QSIC)[END_REF], [START_REF] Perepletchikov | Formalising service-oriented design[END_REF], [START_REF] Perepletchikov | The impact of service cohesion on the analyzability of service-oriented software[END_REF]. A limitation of these metrics is that operations which operate on data characterized by similar, but not exactly matching, types are treated as being totaly unrelated. Such cases of operations are frequent in real world services. For instance, in our example, several operations of the MessageQueue interface use similar but not exactly matching data types (e.g., see Figure 2 for the input/output data of the GetQueueAttributes() and the SetQueueAttributes() operations). Consequently, the state of the art metrics for sequential and communicational cohesion may overestimate the cohesion lack of service interfaces.

Based on the previous discussion, in this paper we propose two fine-grained metrics of cohesion lack, which are defined with respect to the structural similarity of the input/output data types of interface operations. The proposed metrics are formally defined and analytically assessed with respect to fundamental properties of software metrics. Moreover, the usefulness of the metrics in identifying cohesion problems is evaluated in real-world services.

The rest of the paper is structured as follows: Section 2 defines formally the proposed metrics and validates them with respect to fundamental software metrics properties. Section 3 details the methodology of the evaluation and analyzes the experimental results. Section 4 focuses on related work. Finally, Section 5, summarizes the contribution of the paper and discusses the future work.

II. COHESION OF SERVICE INTERFACES

Our overall approach for the definition of the proposed metrics is based on a generic conceptual model for services, derived from the W3C standard services architecture 2 . According to this model, a service is characterized by a name and provides a set of interfaces (Table I(1,2)). An interface is characterized by a name and a set of operations (Table I [START_REF] Bieman | Cohesion and Reuse in an Object-Oriented System[END_REF][START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF]). An operation corresponds to a particular functionality; its execution requires at most one input message and produces at most one output message (Table I(5)). A message is modeled as an unordered rooted tree (Table I(6-9)). The tree root represents the message. The non-leaf vertices correspond to complex elements, i.e., elements characterized by a name and a complex XML type, which consists of further constituent elements. The leaves of the tree represent primitive elements, i.e., elements characterized by a name and a XML build-in type.

E = {(v i , v j ) ∈ V × V |i = j} (8)

A. Communicational & Sequential Cohesion Metrics

The fundamental notions of communicational and sequential cohesion can be adapted in the case of services as follows.

Definition 1: Sequential cohesion: An interface si ∈ s.I of a service s is sequentially cohesive to some extent, if it includes pairs of operations, op i , op j , such that the input message of op j (resp. op i ) and the output message of op i (resp. op j ) comprise common (complex or primitive) elements. More specifically, for complex elements the term common refers to elements characterized by the same complex XML type, while for primitive elements the term common refers to elements, characterized by the same name and build-in type. In this case, the operations op i , op j are sequentially related, in the sense that certain output data produced by op i (resp. op j ) may be used as input for op j (resp. op i ).

Definition 2: Communicational cohesion: An interface si ∈ s.I of a service s is communicationally cohesive to some extent, if it includes pairs of operations op i , op j , such that their input messages and/or their output messages comprise common (complex or primitive) elements. In this case, the operations are communicationally related, in the sense that they may use similar input data and/or produce similar output data.

The common elements of messages play an important role in both of the previously defined types of cohesion. The following definition reflects the similarity of messages more formally.

Definition 3: Message similarity: Let S mi,mj be the set of the common elements of two messages m i , m j . According to our model, each t i ∈ S mi,mj is a common bottom-up subtree of m i and m j3 . In the trivial case, where |t i .V | = 1, t i corresponds to a common primitive element, otherwise t i corresponds to a common complex element. Then, the similarity M S(m i , m j ) of m i , m j is defined as the sum of the orders of the common bottom-up subtrees of S mi,mj , divided by the order of the message that results from the union of m i and m j (Table II(1)).

M S(m

i , m j ) = ∀t i ∈Sm i ,m j |t i .V | |m i .V ∪ m j .V | (1)
OpSseq(op i , op j ) = M S(op i .in, op j .out) 2 + (2)
M S(op i .out, op j .in) 2

OpScom(op i , op j ) = M S(op i .in, op j .in) 2 + (3)
M S(op i .out, op j .out) 2

C si = {(op i , op j ) ∈ si.O × si.O| (4) (op i = op j ) ∧ (op j , op i ) ∈ C si } LoC S (si) = 1 - ∀(op i ,op j )∈C si OpSseq(op i , op j ) |si.O| * (|si.O|-1) 2
(5)

LoC C (si) = 1 - ∀(op i ,op j )∈C si OpScom(op i , op j ) |si.O| * (|si.O|-1) 2 (6)
By definition, the values M S(m i , m j ) range from 0 to 1; M S(m i , m j ) = 1 if the messages exactly match, while M S(m i , m j ) = 0 if the messages are completely unrelated. The similarity between two messages increases with the number of the bottom-up subtrees that they have in common and the orders of these subtrees. Technically, the specification of every service includes references to XML schemas that contain the definitions of the complex XML data types used in the definitions of the interfaces provided by the service. These complex XML data types constitute the set of candidate bottom-up subtrees that may be common in two messages. In this way, constructing the set S mi,mj amounts to checking whether a complex XML data type is used in m i and m j .

Nevertheless, when constructing S mi,mj special attention must be paid to certain common elements. In practice, the operations of many service interfaces use input messages and/or produce output messages that have common bottom-up subtrees, which correspond to generic meta-data elements. These elements are not related to the particular functionality of the operations and may result in misleading values of cohesion lack for the service interfaces. Dealing with this issue, when measuring the value of M S(m i , m j ) amounts to filtering out from S mi,mj the common bottomup subtrees that correspond to generic meta-data elements. Apparently, excluding the aforementioned subtrees from M S(m i , m j ) requires user intervention so as to identify the generic meta-data elements. However, this task is quite simple; the generic meta-data elements can be easily identified, since they are included in all input, or in all output messages.

Based on message similarity, we can define the similarity of operations. In particular, OpS seq reflects the similarity of operations from the perspective of sequential cohesion, while OpS com reflects the similarity of operations from the perspective of communicational cohesion.

Definition 4: Sequential similarity: The sequential similarity between two operations op i , op j ∈ si.O of an interface si is defined as (Table II(2)) the average of: 1) the similarity of the input message of op i and the output message of op j and 2) the similarity of the output message of op i and the input message of op j . Definition 5: Communicational similarity: The communicational similarity between two operations op i , op j ∈ si.O of an interface si is defined as (Table II(3)) the average of:

1) the similarity of the input messages of op i and op j and 2) the similarity of the output messages of op i and op j . Based on the previous notions of similarity between operations, we define the proposed metrics of cohesion lack for service interfaces. In particular, LoC S evaluates sequential cohesion (i.e., whether interfaces consist of sequentially similar operations), while LoC C evaluates communicational cohesion (i.e., whether interfaces consist of communicationally similar operations). Definition 6: Lack of cohesion metrics: Let C si be the set of all pairs of operations of an interface si ∈ s.I of a service s, formed such that it contains either (op i , op j ), or (op j , op i ) (Table II(4)). The lack of sequential cohesion, LoC S (si) for si is defined as the complement of the average sequential similarity of the pairs of operations that belong to C si (Table II(5)). Similarly, the lack of communicational cohesion, LoC C (si) for si is defined as the complement of the average communicational similarity of the pairs of operations that belong to C si (Table II( 6)).

B. Analytic Validation

To provide a first analytical assessment of the proposed metrics we follow the approach of Chidamber & Kemerer [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. Specifically, the goal is to examine the behavior of LoC S and LoC C with respect to the properties of software metrics that have been proposed by Weyunker [START_REF] Weyuker | Evaluating Software Complexity Measures[END_REF] (i.e. non-coarseness, non-uniqueness, design-details-importance, monotonicity, non-equivalence and increased-complexity). As discussed in detail in this subsection, the proposed metrics exhibit a similar behavior with the Lack of Cohesion of Methods (LCOM ) metric proposed by Chidamber & Kemerer [START_REF] Chidamber | A metrics suite for object oriented design[END_REF] in their object-oriented metrics suite. Moreover, the behavior of LoC S and LoC C with respect to the examined properties is the same. Therefore, hereafter we use the term LoC * to refer to either LoC S , or LoC C .

Briefly, non-coarseness states that the values of LoC * are not the same for all interfaces, whilst non-uniqueness states that the values of LoC * are not different for all interfaces. The design-details-importance property states that different interfaces that offer the same functionality, may have different LoC * values. As discussed below, proving that these properties are satisfied by LoC * can be done, by following similar steps as in [START_REF] Chidamber | A metrics suite for object oriented design[END_REF] for the case of LCOM . The remaining three properties considered in [START_REF] Chidamber | A metrics suite for object oriented design[END_REF], concern the behavior of LoC * when merging two interfaces si, sj; the merging of two interfaces si sj results in a service interface that provides the union of the operations of si and sj, i.e., (si sj).O = si.O sj.O. Following, we show that the monotonicity property is not satisfied, i.e., LoC * may not increase monotonically when merging si with sj. Moreover, we show that the non-equivalence property is satisfied, i.e., if si, sj are characterized by the same LoC * value and each one of them is merged with the same interface sk, the resulting two interfaces may be characterized by different LoC * values. Finally, we show that the increased-complexity property is not satisfied, i.e., the value of LoC * for the interface that results from merging si, sj may be less than the sum of the LoC * values of the merged interfaces.

Property 1: (Non-coarseness) Given an interface si, another interface sj can always be found such that LoC * (si) = LoC * (sj).

Proof: To prove this proposition we rely on the approach followed by Chidamber and Kemerer [START_REF] Chidamber | A metrics suite for object oriented design[END_REF]. Specifically, in [START_REF] Chidamber | A metrics suite for object oriented design[END_REF] the authors assume that the numbers of methods and attributes that characterize different classes are independent identically distributed random variables. Similarly, we can assume that the orders of the common bottomup subtrees of the messages that characterize operations which belong to different service interfaces are independent identically distributed random variables. Based on this assumption, for any interface si there is a nonzero probability that there exists an interface sj, such that LoC * (si) = LoC * (sj).

Property 2: (Nonuniqueness) There can exist interfaces si, si, such that LoC * (si) = LoC * (sj).

Proof: As in the proof of Property 1 we can rely on the assumption that the orders of the common bottom-up subtrees of the messages that characterize operations which belong to different service interfaces are independent identically distributed random variables. Thus, for any interface si, there is a nonzero probability that there exists an interface sj, such that LoC * (si) = LoC * (sj).

Property 3: (Design-details-importance) Given two interfaces si, sj, the fact that si and sj provide the same functionalities does not imply that LoC * (si) = LoC * (sj).

Proof: In general, the definition of an interface that provides certain functionalities is a design choice that is not restricted in any sense. For the same functionality it is possible, for instance, to define alternative operations whose input/output messages are structured differently. Property 4: (Monotonicity) There can exist service interfaces si, sj, such that LoC * is not monotonically increasing with respect to their merging, i.e. the following inequality may not hold: LoC * (si) ≤ LoC * (si sj).

Proof: Let si, sj be the two interfaces that are going to be merged. If due to design flaws the operations of si are not related (communicationally or sequentially) with each other, while certain of them are related with the operations of sj, then obviously after merging the two interfaces we shall have that LoC * (si) > LoC * (si sj).

Property 5: (Nonequivalence) There exist service interfaces si, sj, sk such that, LoC * (si) = LoC * (sj) does not imply that LoC * (si sk) = LoC * (sj sk).

Proof: Let si, sj, sk be three interfaces, such that LoC * (si) = LoC * (sj). However, sk may be such that its operations are related (communicationally or sequentially) with the operations of si, but unrelated with the operations of sj. Then, obviously LoC * (si sk) = LoC * (sj sk).

Property 6: (Increased-complexity) There can exist service interfaces si, sj, such that the following inequality does not hold: LoC * (si) + LoC * (sj) < LoC * (si sj).

Proof: Let si, sj be the two interfaces that are going to be merged. If due to design flaws the operations of si are not related (communicationally or sequentially) with each other, while certain of them are related with the operations of sj, and the same holds for sj, then obviously after merging the two interfaces we shall have that LoC * (si) + LoC * (sj) > LoC * (si sj).

As in the case of the LCOM metric [START_REF] Chidamber | A metrics suite for object oriented design[END_REF], the fact that the monotonicity and the increased-complexity properties are not satisfied is not a negative result. In general, merging and splitting interfaces are candidate solutions for improving the cohesion of interfaces and the non-satisfaction of the aforementioned properties shows that the benefits of applying any of these solutions are reflected by the values of the metric.

C. Example: Lack of cohesion of MessageQueue.

Returning to the case of the SQS service, Figure 2 gives examples of operations provided by the MessageQueue interface. An example that highlights the negative effect of generic meta-data elements involves the ResponseStatus element. ResponseStatus is a complex element that contains general purpose response meta-data; the element is included in all of the output messages that are used in SQS. Then, for the output messages of SetQueueAttributes and DeleteQueue, for instance, there exists a common bottom-up ResponseStatus subtree. In other words, the output messages of the two operations appear to be similar, despite the fact that their functionalities are completely unrelated. According to the SQS specification, the SetQueueAttributes operation manipulates certain queue attributes, while the DeleteQueue operation deletes a particular queue. Applying the filtering discussed earlier solves the problem. In particular, if we filter out the ResponseStatus elements, the output messages of SetQueueAttributes and DeleteQueue are no longer similar to each other.

In our example, we can further observe a common bottom-up subtree (solid-line) in the input message of the SetQueueAttributes operation and the output message of the GetQueueAttributes operation. This tree consists of 3 vertices, while the union of the two messages consists of 7 vertices. Hence, the similarity of the two messages is 3 7 . On the other hand, the similarity between the input message of GetQueueAttributes and the output message of SetQueueAttributes is 0 because these messages do not contain common bottom-up subtrees. Therefore, the value of the sequential similarity OpS seq for the operations is 2 . Finally, we can observe a trivial common bottomup subtree (dashed-line) in the input message of the SetQueueAttributes operation and the input message of the GetQueueAttributes operation. The subtree consists of a single vertex named Attribute. The union of these two messages comprises 7 vertices. Therefore, the similarity of the two messages is 1 7 . Since the output messages of these two operations are not similar, the overall communicational similarity OpS com for the operations is

1 7 2 .
Overall, for the MessageQueue interface there are 78 pairs of operations, that contribute to the values of the proposed lack of cohesion metrics. Specifically, we have: LoC S (M essageQueue) = 0.98 and LoC C (M essageQueue) = 0.98. As expected, in both cases, the values of the metrics are very close to 1, reflecting the cohesion lack of the MessageQueue interface.

III. EVALUATION

The purpose of the evaluation is to assess the usefulness of the proposed metrics in identifying potential cohesion problems for real-world services. To automatically calculate the value of the metrics, we implemented a prototype that consists of two core components as depicted in Figure 3. The ServiceParser component of the prototype takes as input the WSDL-based specifications of services, and populates a data structure that corresponds to the conceptual model of Table I. The CohesionLackCalculator component of the prototype can be customized so as to calculate the value of any of the metrics given in Table II [START_REF] Cardoso | Semantic Web Services, Processes and Applications[END_REF][START_REF] Chidamber | A metrics suite for object oriented design[END_REF].

In the rest of this section we describe the methodology of the evaluation, the case studies that were used, and the results that we obtained.

A. Methodology of the Evaluation

To assess the capability of the proposed metrics to determine cohesion problems, we experimented with services provided by Amazon4 . The issue is whether the values of the metrics are indicative of the existence of potential cohesion problems. To address the aforementioned issue, the strategy of our evaluation process comprises two steps. Firstly, for every interface the values of the communicational and the sequential cohesion metrics are calculated. Secondly, if the value of any of the two metrics is close to 1, we turn to a manual inspection of the interface. The purpose of the manual inspection is to check the relatedness of the operations within the interface based on its documentation.

B. Case Studies

Amazon provides 21 services that are available through the Web. Amongst these services, 16 were used for the purpose of our evaluation. The remaining 5 services were excluded due to a technical constraint of our current prototype. Our prototype accepts as input WSDL-based specifications of service interfaces, while for the 5 services that were excluded from the evaluation, Amazon does not provide specifications in the aforementioned format. The 16 Amazon services provide an overall number of 19 interfaces; 14 of the examined services provide a single interface, while the remaining 2 services (the Fulfilment Web Service (FWS) and the SQS service that served as an example in previous sections) provide 3 and 2 interfaces, respectively.

Hereafter, for reasons of simplicity we use identifiers A1-A19 to refer to the interfaces of the Amazon services. The mapping of identifiers to service interfaces and the sizes of the interfaces (i.e., the number of provided operations) are given in detail in Table III. In general, we can observe that Amazon provide interfaces that consist of large numbers of operations; more than 50% of the interfaces provide more than 10 operations, while the largest interface is A18 that comprises 87 operations.

C. Results

The results that we obtained are provided in detail in Table IV. Starting from the largest interface (A18) of our case studies, we observe that the values of LoC S and LoC C are 0.99 and 0.98 respectively, indicating the existence of a cohesion problem. Obviously, the problem was expectable because of the very large number of operations (A18 contains 87 operations). In this case, the interface contains lots of unrelated operations leading to metric values very close to 1.

Turning into the manual inspection of A18, its overall purpose is to give access to a virtual computing environment. The operations of A18 can be divided into 22 groups. The operations of each group are more similar to each other than to the operations of the other groups. Indicatively, we enumerate the operations of two groups. The first group consists of operations for the manipulation of IP addresses: AllocateAddress(), AssociateAddress(), DescribeAddresses(), DisassociateAddress(), and ReleaseAddress(). The second group concerns the manipulation of account keys, and comprises the operations: CreateKeyPair(), DeleteKeyPair(), and DescribeKeyPairs().

Continuing with the medium sized interfaces (A5, A7, A15-A17, and A19), whose number of operations is between 15 and 30, we observe that the values of the metrics range from 0.84 to 0.95. Even if the size of the interfaces is almost the 25% of the size of A18, the lack of cohesion values are still very high. Again, the manual inspection showed cohesion problems that justify the values of the metrics. For instance, the A16 interface provides a secure and seamless bridge between a company's existing information technology (IT) infrastructure and the cloud of Amazon. In this case, we identified 6 groups of closely related operations. Indicatively, we enumerate the operations of two groups.

The first group consists of operations for the manipulation of a connection between a company's infrastructure and the Amazon cloud: CreateVpc(), DeleteVpc(), and DescribeVpcs(). The second group concerns the manipulation of subnets within the Amazon cloud, and comprises the operations: CreateSubnet(), DeleteSubnet(), and DescribeSubnets().

Turning to the small sized interfaces (A1-A4, A6, A8-A14), we were intuitively expecting lower values of the metrics than the cases of the medium sized interfaces. However, we observe that this assumption does not hold because the values of the metrics range in nearly the same level as before (from 0.83 to 0.98). The inspection of the interfaces showed that although the size of the interfaces is small, their operations are not similar to each other.

As an example, we discuss the A13 interface, which also served as an example in previous sections. We observe that the value of both metrics is equal to 0.98 indicating a cohesion problem. Based on the documentation, we identified 4 groups of tightly related operations. The first group comprises operations for adding/removing/listing access permissions for a particular queue: AddGrant(), ListGrants(), and RemoveGrant(). The second group concerns getting/setting certain queue timeouts, and consists of the operations: GetVisibilityTimeout(), and SetVisibilityTimeout()). The third group consists of operations for sending messages to a queue, receiving/deleting messages from a queue and changing the visibility of messages:

SendMessage(), PeekMessage(), ReceiveMessage(), DeleteMessage(), and ChangeMessageVisibility(). The last group enables the deletion of a queue and consists of only one operation: DeleteQueue().

Overall, based on our results we can conclude in the following point: the proposed metrics succeed in indicating cohesion problems for real-world service interfaces. Moreover, in our services set, we observed that the definition of cohesive interfaces was not a primary priority of the designers. This does not necessarily mean that the design of the services is flawed. However, cohesion should not be neglected from the design of widely used services, given that the effects of cohesion lack may affect numerous applications all over the Web that depend on these services.

IV. RELATED WORK

The metrics proposed in this paper are inspired from various cohesion metrics that have been proposed in the context of OO software development. In particular, in [START_REF] Chidamber | A metrics suite for object oriented design[END_REF] the authors propose the well known LCOM metric (Lack of Cohesion of Methods), which is defined in terms of the number of pairs of class methods that use common class attributes and the number of pairs of class methods that do not use common class attributes. Moreover, in [START_REF] Henderson-Sellers | Coupling and cohesion (towards a valid metrics suite for object-oriented analysis and design)[END_REF] the authors propose metrics of cohesion lack defined in terms of the number of methods that use each one of the attributes of a given class. In [START_REF] Hitz | Measuring Coupling and Cohesion in Object-Oriented Systems[END_REF], [START_REF] Bieman | Cohesion and Reuse in an Object-Oriented System[END_REF] the authors propose metrics that further take into account class methods which use other class methods. In [START_REF] Bansiya | A class cohesion metric for object-oriented designs[END_REF] the authors propose a cohesion metric that is based on the parameter types of the methods that belong to a given class. Given the variety of OO metrics that have been proposed in the literature, certain approaches proposed unified frameworks for the quality analysis of software [START_REF] Bansiya | A hierarchical model for objectoriented design quality assessment[END_REF] and frameworks for the comparison of existing metrics [START_REF] Briand | A unified framework for cohesion measurement in object-oriented systems[END_REF], [START_REF] Counsell | The interpretation and utility of three cohesion metrics for object-oriented design[END_REF].

In the context of service-oriented development, the aforementioned OO metrics can be used to assess the internal implementation of services. However, they can not be used to reflect the relevance of the operations of service interfaces. Generally, in SOA the state of the art on cohesion metrics for service interfaces is limited to the work of Perepletchikov et al. [START_REF] Perepletchikov | Cohesion Metrics for Predicting Maintainability of Service-Oriented Software (QSIC)[END_REF], [START_REF] Perepletchikov | Formalising service-oriented design[END_REF], [START_REF] Perepletchikov | The impact of service cohesion on the analyzability of service-oriented software[END_REF]. In this line of research the authors consider various notions of cohesion and propose corresponding metrics. Specifically, certain metrics focus on measuring the cohesion between a service interface and the internal service implementation (SIIC). The values of these metrics are calculated as a function of the number of operations that use the same internal implementation elements. Certain other metrics concentrate on the cohesion between the users of a service and the service (SIUC). In this case, the values of the proposed metrics are calculated as a function of the number of service consumers that use all of the operations.

Regarding sequential and communication cohesion, which are amongst the most desirable fundamental notions of cohesion [START_REF] Stevens | Structured design[END_REF], [START_REF] Yourdon | Structured Design[END_REF], the authors proposed two metrics, namely SISC and SIDC. According to SIDC, a service interface is cohesive if its operations are characterized by common types of input parameters and common types of output parameters. Similarly, regarding SISC, a service interface is cohesive if its operations are sequentially dependent, in the sense that the types of certain output parameters of one operation match the types of certain input parameters of another operation. SISC and SIDC are quite coarse grained, compared to the metrics that we proposed in this paper. In particular, in the case of our metrics the relatedness between operations is measured with respect to the similarity of their input/output data types, while in SISC and SIDC the relatedness between operations is measured with respect to exactly matching input/output data types. As already discussed (Section 1), the latter requirement (i.e., exactly matching input/output data types) may lead to the overestimation of cohesion lack. Another problem that may also negatively affect the precision of SISC and SIDC is that the approach proposed in [START_REF] Perepletchikov | Cohesion Metrics for Predicting Maintainability of Service-Oriented Software (QSIC)[END_REF], [START_REF] Perepletchikov | Formalising service-oriented design[END_REF], [START_REF] Perepletchikov | The impact of service cohesion on the analyzability of service-oriented software[END_REF] for the calculation of the metrics values does not make any distinction between normal input/output data and meta-data that are common in all operations.

V. CONCLUSION AND FUTURE WORK

This paper investigated the notion of cohesion in service interfaces. We proposed two fine-grained metrics that measure the lack of communicational and sequential cohesion. The metrics were formally defined with respect to the structural similarity of the input/output data types of interface operations, and analytically validated with respect to fundamental properties of software metrics. Moreover, we evaluated the capability of the metrics to identify cohesion problems in real-world services.

An interesting issue that we currently work on is to provide automated support for improving the cohesion of a service interface. A possible way to do it is to develop a restructuring mechanism that makes use of the proposed metrics in order to divide the interface into groups of closely related operations. Each group corresponds to a separate interface which is more cohesive than the original one. To this end, we plan to investigate the use of hierarchical clustering algorithms along with the metrics that have been proposed in this paper.

Figure 1 .

 1 Figure 1. The Amazon MessageQueue interface.

2 )

 2 Service = (name : string, I) (1) I = {si : Interf ace} (Interf ace = (name : string, O) (3) O = {op : Operation} (4) Operation = (name : string, (5) in : M essage, out : M essage) M essage = (V, E) (6) V = {v : Element} (7) Element = (name : string, type : anyT ype)

Figure 2 .

 2 Figure 2. Examples of MessageQueue operations.

Figure 3 .

 3 Figure 3. The prototype implementation.

Table II DEFINITIONS

 II OF METRICS.

Table III AMAZON

 III SERVICE INTERFACES.

	Service Interface
	Name	Size	ID
	CloudWatchPortType	2	A1
	ElasticMapReducePortType	4	A2
	AmazonFBAOutboundPortType	7	A3
	AmazonSNSPortType	13	A4
	MechanicalTurkRequesterPortType	27	A5
	ElasticLoadBalancingPortType	13	A6
	AmazonFPSPortType	27	A7
	ImportExportPortType	5	A8
	QueueService	2	A9
	AmazonFWSInventoryPortType	4	A10
	AmazonLSPortType	6	A11
	AmazonSDBPortType	9	A12
	MessageQueue	13	A13
	AutoScalingPortType	13	A14
	AmazonFWSInboundPortType	18	A15
	AmazonVPCPortType	21	A16
	AmazonRDSv2PortType	23	A17
	AmazonEC2PortType	87	A18
	AmazonS3	16	A19

Table IV RESULTS

 IV FOR THE CASE STUDIES.

		Cohesion Type
	ID	LoC S	LoC C
	A1	0.86	1.00
	A2	0.94	0.97
	A3	0.94	0.94
	A4	0.97	0.96
	A5	0.84	0.91
	A6	0.97	0.93
	A7	0.97	0.91
	A8	0.96	0.93
	A9	1.00	0.90
	A10	0.99	0.83
	A11	0.97	0.95
	A12	0.97	0.94
	A13	0.98	0.98
	A14	0.98	0.96
	A15	0.96	0.93
	A16	0.98	0.95
	A17	0.96	0.91
	A18	0.99	0.98
	A19	0.97	0.88

http://docs.amazonwebservices.com/AWSSimpleQueueService/2007-05-01/SQSDeveloperGuide/

http://www.w3c.org/TR/ws-arch.

In general, a tree t is a bottom-up subtree of t if the root v of t is a vertex of t and the rest of the vertices of t are the descendants of v in t[START_REF] Valiente | Simple and efficient subtree isomorphism[END_REF]

Amazon services -http://aws.amazon.com/