{'fraction_non_alphanumeric': 0.04673933123960835, 'fraction_numerical': 0.005736190652133752, 'mean_word_length': 4.1821837154755634, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tree Projections and Constraint Optimization Problems: Fixed-Parameter Tractability and Parallel Algorithms

Tree projections provide a unifying framework to deal with most structural decomposition methods of constraint satisfaction problems (CSPs). Within this framework, a CSP instance is decomposed into a number of sub-problems, called views, whose solutions are either already available or can be computed efficiently. The goal is to arrange portions of these views in a tree-like structure, called tree projection, which determines an efficiently solvable CSP instance equivalent to the original one. Deciding whether a tree projection exists is NP-hard. Solution methods have therefore been proposed in the literature that do not require a tree projection to be given, and that either correctly decide whether the given CSP instance is satisfiable, or return that a tree projection actually does not exist. These approaches had not been generalized so far on CSP extensions for optimization problems, where the goal is to compute a solution of maximum value/minimum cost. The paper fills the gap, by exhibiting a fixed-parameter polynomial-time algorithm that either disproves the existence of tree projections or computes an optimal solution, with the parameter being the size of the expression of the objective function to be optimized over all possible solutions (and not the size of the whole constraint formula, used in related works). Tractability results are also established for the problem of returning the best K solutions. Finally, parallel algorithms for such optimization problems are proposed and analyzed. Given that the classes of acyclic hypergraphs, hypergraphs of bounded treewidth, and hypergraphs of bounded generalized hypertree width are all covered as special cases of the tree projection framework, the results in this paper directly apply to these classes. These classes are extensively considered in the CSP setting, as well as in conjunctive database query evaluation and optimization.


Optimization in Constraint Satisfaction Problems
Constraint satisfaction is a central topic of research in Artificial Intelligence, and has a wide spectrum of concrete applications ranging from configuration to scheduling, plan design, temporal reasoning, and machine learning, just to name a few.
Formally, a constraint satisfaction problem (for short: CSP) instance 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 (see, e.g., [16]). Each constraint C v , with v ∈ {1, ..., q}, is a pair (S v , r v ), where S v ⊆ Var is a set of variables called the constraint scope, and r v is a set of assignments from variables in S v to values in U indicating the allowed combinations of values for the variables in S v . A (partial) assignment from a set of variables W ⊆ Var to U is explicitly represented by the set of pairs of the form X/u, where u ∈ U is the value to which X ∈ W is mapped. An assignment θ satisfies a constraint C v if its restriction to S v , i.e., the set of pairs X/u ∈ θ such that X ∈ S v , occurs in r v . A solution to I is a (total) assignment θ : Var → U for which q satisfying assignments θ 1 ∈ r 1 , ..., θ q ∈ r q exist such that θ = θ 1 ∪ ... ∪ θ q . Therefore, a solution is a total assignment that satisfies all the constraints in I.
By solving a CSP instance we usually just mean finding any arbitrary solution. However, when assignments are associated with weights because of the semantics of the underlying application domain, we might instead be interested in the corresponding optimization problem of finding the solution of maximum or minimum weight (short: Max and Min problems), whose modeling is possible in several variants of the basic CSP framework, such as the valued and semiring-based CSPs [6]. Moreover, we might be interested in the Top-K problem of enumerating the best (w.r.t. Max or Min) K solutions in form of a ranked list (see, e.g., [25,10]), 1 or even in the Next problem of computing the next solution (w.r.t. such an ordering) following one that is at hand [9].
CSP instances, as well as their extensions tailored to model optimization problems, are computationally intractable. Indeed, even just deciding whether a given instance admits a solution is a well-known NP-hard problem, which calls for practically effective algorithms and heuristics, and for the identification of specific subclasses, called "islands of tractability", over which the problem can be solved efficiently. In this paper, we consider the latter perspective to attack CSP instances, by looking at structural properties of constraint scopes.

Structural Decomposition Methods and Tree Projections
The avenue of research looking for islands of tractability based on structural properties originated from the observation that constraint satisfaction is tractable on acyclic instances (cf. [62,70]), i.e., on instances whose associated hypergraph (whose hyperedges correspond one-to-one to the sets of variables in the given constraints) is acyclic. 2 Motivated by this result, structural decomposition methods have been proposed in the literature as approaches to transform any given cyclic CSP into an equivalent acyclic one by organizing its constraints or variables into a polynomial number of clusters and by arranging these clusters as a tree, called decomposition tree. The satisfiability of the original instance can be then checked by exploiting this tree, with a cost that is exponential in the cardinality of the largest cluster, also called width of the decomposition, and polynomial if the width is bounded by a constant (see [36] and the references therein). Similarly, by exploiting this tree, solutions can be computed even to CSP extensions tailored for optimization problems, again with a cost that is polynomial over bounded-width instances. For instance, we know that (in certain natural optimization settings) Max is feasible in polynomial time over instances whose underlying hypergraphs are acyclic [54], have bounded treewidth [25], or have bounded hypertree width [37,40].
Despite their different technical definitions, there is a simple framework encompassing all structural decomposition methods, 3 which is the framework of the tree projections [29]. The basic idea of these methods is indeed to "cover" all the given constraints via a polynomial number of clusters of variables and to arrange these clusters as a tree, in such a way that the connectedness condition holds, i.e., for each variable X ∈ Var , the subgraph induced by the clusters containing X is a tree. In particular, any cluster identifies a subproblem of the original instance, and it is required that all solutions to this subproblem can either be computed efficiently, or are already available (e.g., from previous computations). A tree built from the available clusters and covering all constraints is called a tree projection [29,64,35,44]. In particular, whenever such clusters are required to satisfy additional conditions, tree projections reduce to specific decomposition methods. For instance, if we consider candidate clusters given by all subproblems over k + 1 variables at most (resp., over any set of variables contained in the union of k constraints at most), then tree projections correspond to tree decompositions [63,16] (resp., generalized hypertree decompositions [34,35]), and k is their associated width.
Deciding whether a tree projection exists is NP-hard in general, that is, when a set of arbitrary clusters/subproblems is given [35]. Moreover, the problem remains intractable is some specific settings, such as (bounded width) generalized hypertree decompositions [35]. Therefore, designing tractable algorithms within the framework of tree projections is not an easy task. Ideally we would like to efficiently solve the instances without requiring that a tree projection be explicitly computed (or provided as part of the input). For standard CSP instances, algorithms of this kind have already been exhibited [64,29,11,42]. These algorithms are based on enforcing pairwise-consistency [4], also known in the CSP community as relational arc consistency (or arc consistency on the dual graph) [16], 2-wise consistency [47], and R( * , 2)C [50]. Note that these algorithms are mostly used in heuristics for constraint solving algorithms. The idea is to repeatedly take-until a fixpoint is reached-any two constraints C i = (S i , r i ) and C j = (S j , r j ) and to remove from r i all assignments θ i that cannot be extended over the variables in S j , i.e., for which there is no assignment θ j ∈ r j such that the restrictions of θ i and θ j over the variables in S i ∩ S j coincide. Here, the crucial observation is that the order according to which pairs of constraints are processed is immaterial, so that this procedure is equivalent to Yannakakis' algorithm [70], which identifies a correct processing order based on the knowledge of a tree projection. 4 Actually, it is even unnecessary to know that a tree projection exists at all, because any candidate solution can be certified in polynomial time. Indeed, these algorithms are designed in a way that, whenever some assignment is computed that is subsequently found not to be a solution, then the (promised) existence of a tree projection is disproved. We define these algorithms computing certified solutions as promise-free, with respect to the existence of a tree projection (cf. [11,42]). We note that, so far, this kind of solution approach has not been generalized in the literature to deal with CSP extensions tailored for optimization problems.

Contributions
All previous algorithms proposed in the literature for computing the best CSP solutions in polynomial time [25,37,53,8,67,30,40,49,1] (or, more generally, for optimizing functions in different application domains-see, e.g., [58]) require the knowledge of some suitable tree projection, which provides at each node a list of potentially good partial evaluations with their associated values to be propagated within a dynamic programming scheme. The main conceptual contribution of the present paper is to show that this knowledge is not necessary, since promise-free algorithms can be exhibited in the tree projection framework even when dealing with optimization problems.
More formally, we consider a setting where the given CSP instance I is equipped with a valuation function F to be maximized over the feasible solutions. The function is built from basic weight functions defined on subsets of variables occurring in constraint scopes, combined via some binary operator ⊕. 5 Moreover, we assume that a set of subproblems V is given together with their respective solutions. Then, within this setting, ⊲ We provide a fixed-parameter polynomial-time algorithm [18] for Max that either computes a solution (if one exists) having the best weight according to F , or says that no tree projection can be built by using the available subproblems in V. In any case, the algorithm does not output any wrong answer, because the computed solutions are certified. More precisely, the algorithm runs in time f (κ) × n c , where the parameter κ is the number of basic functions occurring in F , n is the size of the input, and c is a fixed natural number. Thus, the running time has no exponential dependency on the input, but possibly on the fixed parameter κ.
⊲ We show that the Top-K problem of returning the best K solutions over all possible solutions is fixed-parameter tractable, too. As we may have an exponential number of solutions (w.r.t. n), tractability means here having a promise-free algorithm that computes the desired output with fixed-parameter polynomial delay: The first solution is computed in fixedparameter polynomial-time, and any other solution is computed within fixed-parameter polynomial-time after the previous one.
⊲ Moreover, we complement the above research results, by studying the setting where a tree projection is given at hand. In this case, we show that the task of computing the best solutions over a set of output variables is not only feasible in polynomial time (as we already know from the literature pointed out above), but it is even possible to define parallel algorithms that can exploit the availability of machines with multiple processors.
Concerning our main technical contributions, we stress here that different kinds of fixed-parameter polynomial-time algorithms can be defined for the problems of interests when varying the underlying parameter of interest. For instance, a trivial choice would be to consider the overall number of constraints involved in the CSP at hand. In fact, our parameter is very often much smaller, so that our algorithms can be useful in all those applications where the optimization function consists of few basic functions, while the number of constraints is large (which makes infeasible computing any tree projection).
Organization The rest of the paper is organized as follows. Section 2 illustrates some basic notions about CSPs and their structural properties. The formal framework for equipping CSP instances with optimization functions is introduced in Section 3. Our fixed-parameter tractability results are illustrated in Section 4. Parallel algorithms are presented in Section 5. Relevant related works are discussed in Section 6, and concluding remarks are drawn in Section 7. the (standard) valued and semiring-based CSP settings.

Preliminaries
Logic-Based Modeling of Constraint Satisfaction Let I = Var , U, C be a CSP instance, with C = {(S 1 , r 1 ), (S 2 , r 2 ), ..., (S q , r q )}. Following [55], we shall exploit throughout the paper the logic-based characterization of I as a pair (Φ, DB), which simplifies the illustration of structural tractability results. In particular, Φ is the constraint formula (associated with I), i.e., a conjunction of atoms of the form r 1 (u 1 ) ∧ · · · ∧ r q (u q ) where u v , for each v ∈ {1, ..., q}, is obtained by listing all the variables in the scope S v . The set of variables in Φ is denoted by vars(Φ), while the set of atoms occurring in Φ is denoted by atoms(Φ). Moreover, DB is the constraint database, i.e., a set of ground atoms encoding the allowed tuples of values for each constraint, built as follows. For each constraint index v ∈ {1, ..., q} and for each assignment θ v ∈ r v , DB contains the ground atom r v (a 1 , ..., a |Sv| ) where if X i is the i-th variable in the list u v , then a i = θ v (X i ) holds for each i ∈ {1, ..., |S v |}. No further ground atom is in DB.
In the following, for any set W of variables and any assignment θ, θ[W] denotes the partial assignment obtained by restricting θ to the variables in W. Therefore, a (total) substitution θ is a solution to Structural Properties of CSP Instances The structure of a constraint formula Φ is best represented by its associated hypergraph H Φ = (N, H), where N = vars(Φ), i.e., variables are viewed as nodes, and where H = {S 1 , ..., S v }, i.e., for each atom in Φ, H contains a hyperedge including all its variables. For any hypergraph H, we denote the sets of its nodes and of its hyperedges by nodes(H) and edges(H), respectively.
A hypergraph H is acyclic if it has a join tree [5]. A join tree JT of H is a labeled tree (V, E, χ), where for each vertex v ∈ V , it holds that χ(v) ∈ edges(H), and where the following conditions are satisfied: holds; and v 2 are connected in JT (via edges from E) and W ⊆ χ(v), for every vertex v in the unique path linking v 1 and v 2 in JT .
Note that this definition is apparently more liberal than the traditional one (in [5]), where there is a one-to-one correspondence between hyperedges and vertices of the join tree. We find it convenient to allow multiple occurrences of the same hyperedge in the χ labels of different vertices of JT , but it is straightforward to show that a standard join tree may be obtained from JT by  repeatedly contracting edges of the form {v 1 , v 2 }, where χ(v 1 ) ⊆ χ(v 2 ) (until such a one-to-one correspondence is met).
Decomposition Methods Structural decomposition methods have been proposed in the literature in order to provide a measure of the degree of acyclicity of hypergraphs, and in order to generalize positive computational results from acyclic hypergraphs to nearly-acyclic ones. Despite their different technical definitions, there is a simple framework encompassing all known (purely structural) decomposition methods. The framework is based on the concept of tree projection [29], which is recalled below.  Figure 1, and the hypergraph H 2 whose hyperedges are listed on the right of the same figure. Note that H 1 is (just) a graph and it contains a cycle over the nodes A, B, and C. The acyclic hypergraph H a shown in the middle is a tree projection of H 1 w.r.t. H 2 . For instance, note that the cycle is "absorbed" by the hyperedge {A, B, C}, which is in its turn trivially contained in a hyperedge of H 2 . ⊳ Following [42], tree projections can be used to solve any CSP instance (Φ, DB) whenever we have (or we can build) an additional pair (V, DB') such that: • V is a set of atoms (hence, corresponding to a set of constraint scopes).
Each atom in V clusters together the variables of a subproblem whose solutions are assumed to be available in the constraint database DB' and that can be exploited in order to answer the original CSP instance (Φ, DB). Atoms in V will be called views, and V will be called view set. It is required that, for each atom q ∈ atoms(Φ), V contains a base view w q with the same list of variables as q.
• DB' is a constraint database that satisfies the following conditions: q ⊆ q DB holds for each base view w q ∈ V; that is, base views should be at least as restrictive as atoms in the constraint formula; (ii) w DB' ⊇ Φ DB [w] holds for each w ∈ V; that is, any view cannot be more restrictive than the constraint formula, otherwise correct solutions may be deleted by performing operations involving such views.
Such a database DB' is said legal for V w.r.t. Φ and DB.
The pair (V, DB') is used as follows. Let H V denote the view hypergraph precisely containing, for each view w in V, one hyperedge over the variables in w. We look for a sandwich formula of Φ w.r.t. V, that is, a constraint formula Φ a such that atoms(Φ a ) includes all base views and H Φa is a tree projection of H Φ w.r.t. H V . By exploiting the sandwich formula Φ a , solving Φ can be reduced to answering an acyclic instance, hence to a task which is feasible in polynomial time. Indeed, by projecting the assignments of any legal database DB' over the (portions of the) views used in Φ a , a novel database DB' a can be obtained such that Φ DB'a a = Φ DB [29]. Most structural decomposition methods of constraint satisfaction problems can be viewed as special instances of this approach, where the peculiarities of each method lead to different ways of building the additional view set V, with its associated database DB'. For instance, the methods based on generalized hypertree decompositions [34,35] and tree decompositions [63], for a constant width k, fit into the framework as follows: k-width generalized hypertree decompositions: The method uses a set h-V k of views including, for each subformula Φ ′ of Φ with atoms(Φ ′ ) ⊆ atoms(Φ) and |atoms(Φ ′ )| ≤ k, a view that is built over the set of all variables on which these atoms are defined (hence, base views are obtained for k=1) and whose assignments in the corresponding constraint database h-DB' k are all solutions to (Φ ′ , DB).
k-width tree decompositions: The method uses the set V k of views consisting of the base views plus all the views that can be built over all possible sets of at most k + 1 variables. In the associated constraint relations in DB' k , base views consist of the assignments in the corresponding atoms in DB, whereas each of the remaining views contains all possible assignments that can be built over them, hence |U | k+1 assignments at most, where U is the size of the largest domain over the selected k + 1 variables.
and where r i (0, 0) and r i (1, 1) are the only two ground atoms in DB, for each i ∈ {1, 2, 3, 4}. The constraint hypergraph associated with Φ is precisely the hypergraph H 1 illustrated in Figure 1. Since H Φ = H 1 is not acyclic, our goal is to apply a structural decomposition method for transforming the original instance Φ into a novel acyclic one Φ a that "covers" all constraints in Φ and is equivalent to it. To this end, let us consider the application on (Φ, DB) of the tree decomposition method with k being the associated width, resulting in the pair (V k , DB' k ). For instance, the base view w r4(C,D) (C, D) is in V k and its associated tuples in DB' k are w r4(C,D) (0, 0) and w r4(C,D) (1, 1). Moreover, for each natural number k > 1, a view having the form w A,B,C (A, B, C) is in V k and the associated tuples in DB' k are w A,B,C (α, β, γ), with α, β, γ ∈ {0, 1}. In particular, for k = 2, the hypergraph H V2 precisely coincides with the hypergraph H 2 (whose hyperedges are) illustrated in Figure 1.
Consider then the constraint formula and note that H Φa coincides with the acyclic hypergraph H a , which is a tree where DB' a is just the restriction of DB' 2 over the atoms in atoms(Φ a ). ⊳

Valuation Functions and Basic Results
In this section, we illustrate a formal framework for equipping constraint formulas with valuation functions suited to express a variety of optimization problems. Moreover, we introduce and analyze a notion of embedding as a way to represent and study the interactions between constraint scopes and valuation functions. In the following we assume that a domain U of values, a constraint formula Φ, and a set D of weights totally ordered by a relation ≥ are given. Moreover, on the set D, we define max and min as the operations returning any ≥-maximum and the ≥-minimum weight, respectively, over a given set of weights.

Formal Framework
Let W ⊆ vars(Φ) be a set of variables. Then, a function f associating each assignment θ : W → U with a weight f (θ) ∈ D is called a weight function (for Φ), and we denote by vars(f ) the set W on which it is defined. If an assignment θ ′ : W ′ → U with W ′ ⊇ vars(f ) is given, then we write f (θ ′ ) as a shorthand for Definition 3.1. Let ⊕ be a closed, commutative, and associative binary operator over D being, moreover, distributive over max. A valuation function F (for Φ over ⊕) is an expression of the form f 1 u1 ⊕ · · · ⊕ f m um , with m ≥ 1. The set of all weight functions occurring in F is denoted by wfs(F ). For an assignment θ : vars(Q) → U, F (θ) is the weight f 1 u1 (θ) ⊕ · · · ⊕ f m um (θ).
As an example, note that valuation functions built for ⊕ = ' + ' basically 7 correspond to those arising in the classical setting of weighted CSPs, where combination of values in the constraints come associated with a cost and the goal is to find a solution minimizing the sum of the costs over the constraints.
A constraint formula Φ equipped with a valuation function F is called a (constraint) optimization formula, and is denoted by Φ F . For an optimization formula Φ F and a constraint database DB, we define the total order F over the assignments in Φ DB such that for each pair θ 1 and For a set O ⊆ vars(Φ), we also define F ,O as the total order over the assignments in Φ DB [O] as follows. For each pair θ 1 and θ 2 of assignments in Two problems that naturally arise with constraint optimization formulas are stated next. The two problems receive as input an optimization formula Φ F , a set O ⊆ vars(Φ) of distinguished variables, and a constraint database DB: Note that the parameter K is an additional input of the problem Top-K and, as usual, is assumed to be given in binary notation. This means, in particular, that the answers to this problem can be exponentially many when compared to the input size.

Structured Valuation Functions
Our results are actually given in the more general setting of the structured valuation functions, where different binary operators can be used in the same constraint formula, and the order according to which the basic weight functions have to be processed is syntactically guided by the use of parentheses (in this case the evaluation order of operators does matter, in general).
Formally, a structured valuation function F is either a weight function or an expression of the form (F ℓ ⊕ b F r ), where F ℓ and F r are in turn structured valuation functions, and ⊕ b is a binary operator with the same properties as the operator in Definition 3.1.
7 For more information on weighted CSPs, see Section 6. 8 As usual, the fact that θ 1 θ 2 and θ 2 θ 1 hold is denoted by θ 1 ≻ θ 2 . Clearly enough, any structured valuation function built with one binary operator can be transparently viewed as a standard valuation function by just omitting the parenthesis. On the other hand, given a valuation function F , we can easily built the set svf (F ) of all possible equivalent structured valuation functions, by just considering all possible legal ways of adding parenthesis to F .
Working on the elements of svf (F ) appears to be easier in the algorithms we shall illustrate in the following sections and, accordingly, our presentation will be focused on structured valuation functions. We will discuss in Section 4.4 how to move from structured valuation functions to equivalent standard valuation functions. and where the atoms in DB are those shown in Figure 2 using an intuitive graphical notation. Note that the instance is trivially satisfiable.
In fact, we are usually not interested in finding just any solution in this setting, but would rather like to single out one that matches as much as possible our preferences over the possible configurations. For instance, we might be interested in computing (the solution corresponding to) a car minimizing the sum of its price plus the cost that is expected to be paid, for the given quotation of the fuel, to cover 100.000 kilometers. Moreover, for cars that are equally ranked w.r.t. this first criterion, we might want to give preference to cars minimizing the emission of CO 2 . For a sufficiently large constant B (which can be treated in a symbolic way), this requirement can be modeled via the function F = ((B × F 1 ) + F 2 ) such that where f (X) (θ) = θ[X] is the identity weight function on each variable X and where any real number is viewed as a constant weight function. ⊳

Structured Valuation Functions and Embeddings
It is easily seen that structured valuation functions introduce further dependencies among the variables, which are not reflected in the basic hypergraphbased representation of the underlying CSP instances. Therefore, when looking at islands of tractability for constraint optimization formulas, this observation motivates the definition of a novel form of structural representation where the interplay between functions and constraint scopes is made explicit. In order to formalize this structural representation, we introduce the concept of parse tree of a structured valuation function.
Definition 3.3. Let F be a structured valuation function. Then, the parse tree of F is a labeled rooted tree P T (F ) = (V, E, τ ), where τ maps vertices either to variables or to binary operators, defined inductively as follows: That is, P T (F ) has no edges and a unique (root) node f , labeled by the variables occurring in f .
, and with p ℓ and p r being the root nodes of P T (F ℓ ) and P T (F r ), respectively. Then, P T (F ) = (V ℓ ∪V r ∪{p}, E ℓ ∪E r ∪{{p, p ℓ }, {p, p r }}, τ p ) is rooted at a fresh node p, with the labeling function τ p such that τ p (p) = ⊕ and its restrictions over V ℓ and V r coincide with τ ℓ and τ r , respectively.
Let O be a set of variables, and let p be the root of P T (F ). Then, the output-aware parse tree of  We say that the pair (F , O) can be embedded in H a if there is a join tree JT = (V, E, χ) of H a and an injective mapping ξ : V O → V , such that every vertex p ∈ V O is associated with a vertex ξ(p) of JT , called p-separator, which satisfies the following conditions: (1) τ O (p) ∩ nodes(H a ) ⊆ χ(ξ(p)), i.e., the variables occurring in p occur in the labeling of ξ(p), too; and (2) there is no pair q, q ′ of vertices adjacent to p in tree(F , O) such that their images ξ(q) and ξ(q ′ ) are not separated by ξ(p), i.e., such that they occur together in some connected component of the forest The mapping ξ is called an embedding of (F , O) in H a , and JT is its witness.
Intuitively, condition (1) states that any leaf node p of the parse tree (i.e., with τ O (p) ∩ nodes(H a ) = ∅) is mapped into a p-separator whose χ-labeling covers the variables involved in the domain of the underlying weight function. Moreover, it requires that the root node is mapped into a node whose χ-labeling covers the output variables in O. On the other hand, condition (2) guarantees that the structure of the parse tree is "preserved" by the embedding. This is explained by the example below.  Figure 3. Observe that H Φ is acyclic, as it is witnessed by the join tree depicted on the right. Moreover, note that the figure actually shows that there is an embedding of (F , {MODEL}) in H Φ that maps each node to (the hyperedge containing the variables of) the atom Cars, except for the leaf f (quote) which is mapped to FuelQuotes. Note also that the root is mapped to Cars, which indeed covers the output variable MODEL, and that mapping constant functions is immaterial. ⊳

Properties of Embeddings for Structured Valuation Functions
We shall now analyze some relevant properties of embeddings, which are useful for providing further intuitions on this notion and will be used in our subsequent explanations. Let F be a structured valuation function for a constraint formula Φ, let H a be an acyclic hypergraph with vars(Φ) ⊆ nodes(H a ), and let O ⊆ vars(Φ) be a set of variables. Let ξ : V O → V be any injective mapping and denote by V ξ ⊆ V its image. Thus, for each vertex v ∈ V ξ , its inverse ξ −1 (v) is the vertex in the parse tree whose image under ξ is precisely v. In the following, let us view JT as a tree rooted at the vertex Proof. We prove the property by structural induction, from the root to the leaves of JT . In the base case, v ′ is the root of JT and thus ξ −1 (v ′ ) is the root of tree(F , O). In this case, the result is trivially seen to hold. Now assume that the property holds on any vertex v ′′ ∈ V ξ in the path connecting the root and . We show that the property holds on v ′ , too. To this end, we first claim the following.
Proof. We prove the property by induction. Consider first the case where i = 2. The fact that ξ(q 2 ) is a descendant of ξ(q 1 ) is immediate by (ii). Then, assume that the property holds up to an index i, with i ∈ {2, ..., m − 1}. We show that it holds on i + 1, too. Indeed, by inductive hypothesis, we know that ξ(q i ) is a descendant of ξ(q i−1 ), which is in turn a descendant of ξ(q 1 ) by (ii). Consider the vertex q i , and recall that since ξ is an embedding, ξ(q i ) disconnects ξ(q i+1 ) from ξ(q i−1 ). This means that ξ(q i+1 ) is a descendant of ξ(q i ). ⋄ We now resume the main proof.
(only-if ) Assume that v is a descendant of v ′ . Hence, v is a descendant of some vertex v ′′ ∈ V ξ and we can apply the inductive hypothesis to derive that We distinguish two cases.
In the first case . Note that on this path we can apply the inductive hypothesis in order to conclude that ξ(q i ) is a descendant of ξ(q 1 ), for each i ∈ {2, ..., m}. Therefore, we are in the position to apply Claim 3.7, and we conclude that ξ(q i ) is a descendant of ξ(q i−1 ), for each i ∈ {2, ..., m}. In particular, by transitivity, we get The only remaining possibility is that there are two distinct vertices q and q ′ that are children of a vertexq, which is a descendant of Similarly to the case discussed above, note that on each of them we can apply Claim 3.7. Thus, we get that ξ(q) and Finally, recall that ξ is an embedding, and hence ξ(q) must disconnect ξ(q) and ξ(q ′ ). Therefore, it disconnects v and v ′ , too. Contradiction with the fact that v is a descendant of v ′ .
. Assume, for the sake of contradiction, that v is not a descendant of v ′ . Because of the only-if part, we are guaranteed that v ′ is in any case not a descendant of v. Therefore, there is a vertexv disconnecting v and v ′ and such that v and v ′ are both descendant ofv. We can now apply the inductive hypothesis on the vertex v ′′ ∈ V ξ in the path connectingv and the root, and that is the closest tov (possibly coinciding with it). Therefore, we know that ξ −1 (v) and Because of the inductive hypothesis, we know that ξ(q i ) is a descendant of ξ(q 1 ), for each i ∈ {2, ..., m}. Therefore, we are in the position of applying Claim 3.7 and, by transitivity, we derive In words, the above result tells us that embeddings preserve the descendant relationship. In fact, preserving this relationship suffices for an embedding to exist.
, if x is an internal node with children y and z, then we first observe that, by hypothesis, ξ(y) and ξ(z) are both descendant of ξ(x). Moreover, ξ(y) (resp., ξ(z)) is not a descendant of ξ(z) (resp., ξ(y)), and therefore there is a vertexv in V possibly coinciding with ξ(x) such that ξ(y) and ξ(z) occur in different components of (V \v, {e ∈ E | e ∩v = ∅}) as descendants ofv-in particular, wheneverv = ξ(x), we have thatv is a descendant of ξ(x). For the node x, we now define ξ ′ (x) =v.
Note that ξ ′ trivially satisfies condition (1) in Definition 3.4, as ξ ′ differs from ξ only over non-leaf nodes different from the root. We claim that ξ ′ satisfies condition (2), too.
Recall that, by Definition 3.3, the output-aware parse tree is binary, and its root is the only vertex having one child. Consider next any vertex p ∈ V O with parent s and children q and q ′ . Indeed, if p is the root or a leaf, then condition (2) in Definition 3.4 trivially holds. By the above construction (setting x = p), we know that ξ(q) and ξ(q ′ ) occur in different components of (V \ ξ ′ (p), {e ∈ E | e ∩ ξ ′ (p) = ∅}) as descendants of ξ ′ (p). Moreover, whenever ξ ′ (q) = ξ(q), we are guaranteed that ξ ′ (q) is a descendant of ξ(q) (again by the above construction, this time setting Consider now the parent s and the child q-the same line of reasoning applies to the child q ′ . By hypothesis, we know that ξ(p) occurs in the path connecting ξ(s) and ξ(q), with ξ(q) being a descendant of ξ(s). Moreover, by construction of ξ ′ (over s, p, and q), we have that: either ξ ′ (s) occurs in the path connecting ξ(s) and ξ(p), or ξ ′ (s) = ξ(s); either ξ ′ (p) occurs in the path connecting ξ(p) and ξ(q), or ξ ′ (p) = ξ(p); and ξ ′ (q) is either a descendant of ξ(q), or coincides with ξ(q). Therefore, ξ ′ (p) occurs in the path connecting ξ ′ (s) and ξ ′ (q). That is, By putting all together, we have shown that condition (2) in Definition 3.4 holds on any vertex p ∈ V O .

Structural Tractability in the Tree Projection Setting
The concept of embedding has been introduced in Section 3 as a way to analyze the interactions of valuation functions with acyclic instances. However, the concept can be easily coupled with the tree projections framework in order to be applied to instances that are not precisely acyclic. This coupling is formalized below.
Definition 4.1. Let F be a structured valuation function for a constraint formula Φ, let O ⊆ vars(Φ) be a set of variables, and let V be a view set for Φ. We can be embedded in the acyclic hypergraph H Φa .
If O = ∅, then we just say that F can be embedded in (Φ, V).

Example 4.2. Recall the setting of Example 2.3 and the valuation function
. Indeed, consider the sandwich formula Φ a depicted in Figure 1, and note that (F , ∅) can be embedded in H Φa . In fact, as F consists of a weight function only, this is witnessed by any join tree JT of H Φa because we can always build an embedding that maps f a to a vertex q of JT such that χ(q) ⊇ {A}. Note that, for this kind of valuation functions, checking the existence of an embedding always reduces to checking the existence of a tree projection. ⊳ Recall that deciding whether a pair of hypergraphs has a tree projection is an NP-complete problem [35], so that the notion of embedding can hardly be exploited in a constructive way when combined with tree projections. However, we show in this section that the knowledge of an embedding (and of a tree projection) is not necessary to compute the desired answers. Indeed, a promisefree algorithm can be exhibited that is capable of returning a solution to Max (and Top-K ) or to check that the given instance is not embeddable. The algorithm is in fact rather elaborated, and we start by illustrating some useful properties that can help the intuition.
Hereinafter, let Φ be a constraint formula, DB a constraint database, O a set of variables, and F a structured valuation function, all of them being provided as input to our reasoning problems. Moreover, to deal with the setting of tree projections, we assume that a view set V for Φ plus a constraint database DB' that is legal for V w.r.t. Φ and DB are provided. Accordingly, to emphasize the role played by these structures, the problems of interest will be denoted as

Useful Properties of Embeddings
For a constraint database DB and an atom a, the set a DB will be also denoted by rel(a, DB). Substitutions in rel (a, DB) will be also viewed as the ground atoms in DB to which they are unambiguously associated. If q is an atom, Without loss of generality, assume that, for each weight function f i ∈ wfs(F ), V contains a function view w fi over the variables in vars(f i ). Indeed, if w fi ∈ V, then we can just define w fi as the projection over vars(f i ) of any view w ∈ V such that vars(w) ⊇ vars(f i ). In particular, if such a view w does not exist, then we can immediately conclude that F cannot be embedded in (Φ, V).
Let us define DB as the constraint database obtained (in polynomial time) by enforcing pairwise consistency on DB' w.r.t. V [4]. The method consists of repeatedly applying, till a fixpoint is reached, the following constraint propagation procedure: Take any pair w and w ′ of views in V, and delete from DB any (ground atom associated with an) assignment θ in rel (w, DB) for which no assignment In words, the procedure removes, for each view w, all its associated assignments θ that cannot be extended to some assignment in each of the remaining views. In the database terminology, this is called a semijoin operation over w and w ′ .
The crucial property enjoyed by the database DB, which we shall intensively use in our elaborations, is recalled below.
For any partial assignment θ : W → U, where W ⊆ vars(Φ), and for any constraint optimization formula Φ F , denote by max F (θ) the maximum weight that any assignment where ⊥ denotes the minimum weight in the codomain of the valuation function.
Let p be any vertex of tree(F , O) occurring in the parse tree P T (F ). Let F p denote the subexpression of F whose parse tree is the subtree rooted at p. Note that if F p = f i holds for some weight function f i , then ∀θ ∈ w DB fi , f i (θ) = max Fp (θ) holds by construction. Assume now that p is a (non-leaf) vertex labeled by ⊕, and let ℓ and r be its children. Then, the maximum weight of F p = (F ℓ ⊕ F r ) is bounded by the aggregation via ⊕ of the maximum weights that can be achieved over its F ℓ and F r .
Proof. Letθ be an assignment such that max F ℓ ⊕Fr (θ) = F ℓ (θ) ⊕ F r (θ). Then, the result follows by the properties of ⊕ and since F ℓ (θ) ≤ max F ℓ (θ) and Assume now that there exists a tree projection H a of H Φ with respect to H V , and that the pair (F , O) can be embedded in H a . Let JT = (V, E, χ) be the join tree of H a and ξ : V O → V be the injective mapping of Definition 3.4. Then, we show that the inequality in Lemma 4.4 is tight on separators, thus the operation of choosing the best sets of partial assignments computed in the subtrees distributes over ⊕.
where q a is a p-separator for some p ∈ V O and w ∈ V is a view with vars(w) ⊇ vars(q a ).
Proof. Recall that ξ(p) separates its children ℓ and r in the join tree JT of H Φa . Observe that, by Lemma 3.6, the images of all vertices of the subtree rooted at ℓ (resp., r) belong to the same connected component C ℓ (resp., C r ) of JT \ ξ(p). In particular, C ℓ = C r . Thus, from the connectedness condition of join trees, every variable that C ℓ and C r have in common must be included in χ(ξ(p)). In fact, any partial assignment θ ∈ w DB [q a ] provides a value for all these variables. Thus, all possible extensions of θ to C ℓ are independent of their extensions to C r , so that they can be freely combined. Hence, we can safely obtain max F ℓ ⊕Fr (θ) by computing ⊕ over the maximum weights obtained for θ looking at F ℓ and F r in a separate way.
In the light of Lemma 4.4 and Lemma 4.5, it is not difficult to define a bottom-up algorithm that, given the tree projection H a and the embedding ξ, processes from the leaves to the root each vertex p of (F , O) computing the maximum weights that can be achieved by combining the results coming from its children, and using some view covering the p-separator.
However, because deciding whether there is a tree projection (and compute one, if one exists) is NP-hard [35], such a naïve approach to solve Max and Top-K is impractical for large constraint formulas. We need a method that is able to perform the computation even when an embedding is not given.

Algorithm Compute-Max
Our approach to solve Max and Top-K even without the knowledge of (a sandwich formula and of) an embedding is based on the Algorithm Compute-Max shown in Figure 4.
Assume that the vertices p 1 , . . . , p s of tree(F , O) are numbered according to some topological ordering of this tree (from leaves to root). As no tree projection and no embedding are known, we miss the relevant information about which views behave as separators. This is dealt with in Compute-Max by maintaining, for each vertex p i , a set sep i of views that are candidates to be p i -separators in some tree projections and w.r.t. to some embedding. These sets are managed as follows.
Initialization. Define DB 1 as the database obtained by enforcing pairwiseconsistency on DB' w.r.t. V. Let p i be a vertex of tree(F , O), and consider three cases: ] over a fresh relation symbol, and over all variables in vars(w fi ) plus the fresh variable X . Accordingly, DB 1 is enlarged to contain the relation: Thus, the auxiliary variable X is meant to store the weight of the function f i = F pi for each assignment of the view w fi . Note that the sample set  sep i includes just one (augmented) function view, as w fi can always be used as a p i -separator.
Internal node: p i is a non-leaf vertex having two children named p r and p t in the given ordering. Then, for each w ∈ V, w ′ ∈ sep r , and w ′′ ∈ sep t , the set sep i includes the augmented view [wX ], over the variables in vars(w) plus the fresh variables X (w ′ ) r and X (w ′′ ) t . Accordingly, DB 1 is enlarged to contain the relation: Intuitively, augmented views store the weights derived during the computation for functions F pr and F pt . Initially, we consider the constant noval , meaning that no weight is currently available. Note that for internal nodes we need to keep all the possible views in V as candidates for being p i -separators.
Root: p i = p s is the root whose only child is p s−1 . Then, let us chose any view During the initialization, DB 1 is modified so as to include augmented views. However, the projection of each augmented view over the variables occurring in Φ gives precisely the original underlying view. Thus, Lemma 4.4 and Lemma 4.5 hold over (the modified) DB 1 and the augmented views. During the computation, a sequence of such constraint databases DB 2 , ..., DB s is constructed. For each of them, the equivalence with DB 1 when considering projections over the variables in the original views is guaranteed.
Main Loop. After their initialization, views in sep i are incrementally processed, from i = 1 to i = s, via the functions evaluate and propagate. Both functions receive as input a candidate separator and a current constraint database, and produce as output a novel constraint database. The functions Step The goal of this step is to evaluate functions over the candidates in sep i and to filter out those that cannot be p i -separators. When invoked according to the topological ordering, it will be guaranteed that the active domain in DB i of any variable of any augmented view in sep i does not include noval , because functions associated with the children have been previously evaluated. We distinguish three cases: Leaf node: In this case, no operation is required, as sep i contains one good augmented view, by initialization.
Internal node: For every w ∈ V, recall that sep i contains the view [wX ], for each pair w ′ ∈ sep r and w ′′ ∈ sep t . Let ⊕ be the label of p i , and for any assignmentθ ∈ w DB1 , let marg(θ, w, w ′ , w ′′ ) be the maximum of θ[X ] taken over all the assignments θ ∈ [wX . This is often called marginalization of [wX . Let best (θ, w) denote the minimum weight of marg(θ, w, w ′ , w ′′ ) over all the possible pairs of views w ′ and w ′′ , and define for w the augmented view [wX (w) i ], whose associated relation in DB i is: Then, sep i is modified by including only all augmented views of the form [wX The rationale of this step can be understood by first recalling that every assignment in a p i -separator is associated with the largest weight over its possible extensions to full answers according to F pi (cf. Lemma 4.4 and Lemma 4.5). In fact, when analyzing the algorithm, we shall show that good candidates to act as p i -separators are those having the minimum marginalized weights for each one of their assignments, which therefore motivates the definition of the term best(θ, w). Based on this fact, we actually delete from sep i every view whose maximum weight over all its assignments is not the minimum over the maximum weights of all other views. This way |sep i | ≤ |V|, and the maximum weight stored somewhere in the constraint database is bounded by its real maximum over the answers of the given constraint formula. Therefore, no space explosion may occur, neither in terms of number of samples nor in terms of size of the weights stored in the views.

Root:
We drop all views from sep s , but one view (if any) of the form [w O X (w) Step DB i+1 := propagate(sep i , DB ′ i ). Let p j be the parent of p i . In this step, we propagate the information of the views in sep i into sep j . For any variable X, let dom(X) denote its active domain in DB ′ i . Then, for each view [wX ] ∈ sep i , propagation is implemented via the following steps (1)- (6): ); that is, these views are not restrictive w.r.t. X i because all its possible weights are considered; Repeat the step for the symmetrical case of those views having the form (4) update DB ′ i+1 with the result of EnforcePairWiseConsistency(V i , DB ′ i ); (5) remove from DB ′ i+1 the relations added at step (2).
Note that the goal of steps (1)-(4) above is to filter views of the form ] that are stored in sep j , by keeping the assignments that agree with the weights stored in the view [wX   In particular, as their role is just to propagate the information from sample [wX ], they are eventually removed in step (5) from the constraint database. Finally, note that the same assignment can be propagated with different associated weights. The final ingredient (used at the end of each "evaluate step") is to retain the assignment with the minimum associated weight.

Concluding
Step. If after the last invocation of the evaluation step sep s contains one view, then output any of its assignments having the maximum associated weight.

"Depromisization" and Analysis Overview
The analysis of Compute-Max is rather technical, and its details are deferred to the Appendix. Observe that algorithm Compute-Max is a promise algorithm, in that it is guaranteed to correctly return a solution to Max under the hypothesis that some embedding exists (the "promise"). Actually, we can show that its correctness does not require that the constraint optimization formula can be embedded in a tree projection of the entire CSP instance. Indeed, we can show that it suffices that an embedding exists for some homomorphically equivalent subformula.
Remark 4.6. We consider the usual computational setting where each mathematical operation costs 1 time unit. However, all the algorithms described in the following are such that the total size of the weights computed during their execution is polynomially bounded w.r.t. the combined size of the input and the size of the value of any optimal solution (assuming that the promise holds). This is a sensitive issue because, in the adopted computational setting, one may compute in polynomial-time weights of size exponential w.r.t. the input size.
To state our main result, recall first that, whenever Φ ′ is a subformula of Φ, i.e., atoms(Φ ′ ) ⊆ atoms(Φ), we say that Φ ′ is homomorphically equivalent to Φ, denoted by Φ ′ ≡ h Φ, if there is a homomorphism from Φ to Φ ′ , i.e., mapping h : vars(Q) → vars(Q ′ ) such that for each r i (u i ) ∈ atoms(Q), it holds that r i (h(u i )) ∈ atoms(Q ′ ). For any set O of variables, denote by atom(O) a fresh atom over the variables in O.

O). It outputs FAIL, only if this condition does not hold.
Interestingly, Compute-Max can be used as a subroutine for an algorithm that incrementally builds a solution in Φ DB , hence yielding a promise-free algorithm, i.e., an algorithm that either computes a correct solution or disproves some given promise (which is NP-hard to be checked), in our case the existence of an embedding. The full proof of the following result is given in the Appendix, but a proof idea is discussed below.  , FAIL), then we can terminate the computation, by returning that there is no solution, i.e., Φ DB = ∅ (resp., the promise that F can be embedded in (Φ, V) is disprovedobserve that the equivalent promise that (F , {X}) can be embedded in (Φ, V X ) is indeed more stringent than the one in Theorem 4.7 for V X and O = {X}). Therefore, let us assume that we get an assignment θ X with an associated weight z. The variable X is then deleted from the constraint formula and from the views, and the original constraint database is modified so as to keep only assignments where X is fixed to θ X .
The process is then iterated over all the variables. It can be shown that the promise is disproved if in some subsequent step Compute-Max does not return the same weight z, or if at the end of the computation the assignment we have computed, say θ, is not a solution or F (θ) = z. Otherwise, θ can be returned as a certified solution to Max.
The above is the basis for getting the corresponding tractability result for Top-K . Note that, since Φ DB may have an exponential number of assignments, tractability of enumerating such assignments means here having algorithms that list them with polynomial delay (WPD): An algorithm M solves WPD a computation problem P if there is a polynomial p(·) such that, for every instance of P of size n, M discovers whether there are no solutions in time O(p(n)); otherwise, it outputs all desired solutions in such a way that a new solution is computed within O(p(n)) time after the previous one. Note that, in general, an algorithm running WPD may well use exponential time and space.
Note, moreover, that in the result below, when the algorithm discovers that the promise does not hold, i.e., when F cannot be embedded in (Φ, V), then it stops the computation but we are still guaranteed that all solutions returned so far (which might be even exponentially many) constitute a solution to Top-K ′ , for some K ′ ≤ K. That is, the algorithm computes a (possibly empty) certified prefix of a solution to Top-K . Again, the proof of the following result is elaborated in the Appendix. Proof Idea. The result can be established by exploiting a method proposed by Lawler [59] for ranking solutions to discrete optimization problems. In fact, the method has been already discussed in the context of inference in graphical models [25] and in conjunctive query evaluation [54]. Reformulated in the CSP context, for a CSP instance over n variables, the idea is to first compute the optimal solution (w.r.t. the functions specified by the user), and then recursively process n constraint databases, obtained as suitable variations of the database at hand where the current optimal solution is no longer a solution (and no relevant solution is missed). By computing the optimal solution over each of these new constraint databases, we get n candidate solutions that are progressively accumulated in a priority queue over which operations (e.g., retrieving any minimal element) take logarithmic time w.r.t. its size. Therefore, even when this structure stores data up to exponential space (so that its construction required overall exponential time), basic operations on it are still feasible in polynomial time. The procedure is repeated until K (or all) solutions are returned. Thus, whenever the Max problem of computing the optimal solution is feasible in polynomial time (over the instances generated via this process), we can solve with polynomial delay the Top-K problem of returning the best K-ranked ones. In fact, we can show that the constraint database can always be updated according to the approach by Lawler [59], while being still in the position of applying Theorem 4.8, and hence by iteratively solving Top-K .

Results for Evaluation Functions
Our analysis has been conducted so far over structured valuation functions, whose syntactic form plays a crucial role with respect to the existence of an embedding in some tree projection. However, when we focus instead on valuation functions only (built over a single binary operator ⊕) the specific form of the constraint formula should not matter because ⊕ is by definition a commutative and associative operator. Therefore, to deal properly with this setting, we adopt a more semantic approach in which the only sensitive issue is the existence of a tree projection. To formalize the result, recall that, for a valuation function F , svf (F ) denotes the set of all equivalent structured valuation functions.   (1) can be built in polynomial time.

Moreover whenever (2) holds and the tree projection H a is given, then a function F ′ as in
Proof. The fact that (1) ⇒ (2) is immediate by the definition of embedding. Therefore, let us focus on showing that (2) ⇒ (1) holds, too. Assume that H a is a tree projection of H Φ w.r.t. H V satisfying the conditions stated in (2). Consider a join tree JT = (V, E, χ) of H a and let p O be a vertex in V such that χ(p O ) ⊇ h, which exists by (2).(a). Let us root (to simplify the exposition below) the tree JT at p O . Recall that wfs(F ) is the set of all weight functions occurring in F , and for each f ∈ wfs(F ), let p f ∈ V be any vertex such that χ(p f ) = h f , which exists by (2).(b). Based on JT , we build a novel join tree JT = (V ,Ē,χ) as follows: for each function f ∈ wfs(F ), we create a new nodep f such thatχ(p f ) = χ(p f ) and we add this node in JT as a child of p f . Moreover, we create a new nodep O whose only child is p O and such thatχ(p O ) = χ(p O ). This new node will act as the root of JT . All the other nodes, edges, and labeling remain the same as in JT . Finally, we process JT in order to make it binary. To this end, if a vertex p in JT has children c 1 , ..., c n with n > 2, then we modify JT by removing the edges connecting p and c i , for each i ∈ {2, ..., n}, by adding a novel vertex p ′ as a child of p and by appending c 2 , ..., c n as children of p ′ . The label of p ′ is defined as the label of p, so that the connectedness condition still holds on the modified join tree. The transformation is repeated till JT is made binary. Given the join tree JT , consider the following algorithm that recursively builds F (JT ). Let p be the vertex that is the closest to the root of JT and such that p has two children c 1 and c 2 and the subtrees rooted at them each contains a vertex of the formp f , for some weight function f ∈ wfs(F ). Note that, since JT is binary, either the vertex p is univocally determined or it does not exist at all. In particular, in this latter case, let f be the only weight function such that p f occurs in JT (w.l.o.g., the function contains at least one weight function, and this will be recursively guaranteed) and define F (J T ) := f . In the former case, define F (JT ) := F (JT 1 ) ⊕ F (JT 2 ), where JT 1 and JT 2 are the trees rooted at c 1 and c 2 , respectively. Note that F (JT ) clearly belongs to svf (F ). Moreover, consider the function ξ such that ξ(O) =p O ; ξ(f ) =p f , for each f ∈ wfs(F ); and, for each internal node v of the parse tree, ξ(v) is mapped to the node p selected in the above algorithm when processing the subexpression corresponding to the subtree rooted at v. Note that ξ is injective, and by the recursive construction, for each pair O). Then, we can apply Theorem 3.8 and conclude that an embedding ξ ′ of (F (JT ), O) in (Φ, V) can be built in polynomial time from ξ.
Note that, since the "(2) ⇒ (1)" of the above result is constructive, we immediately get the following by Theorem 4.8 and Theorem 4.9. Proof. Assume that |vars(f )| = 1, for each f ∈ wfs(F ). By Theorem 4.10, we can use the given tree projection to build in polynomial time a function F ′ ∈ ef (F ) such that (F ′ , ∅) can be embedded in (Φ, V). The result follows by Theorem 4.8 and Theorem 4.9.
Interestingly, if a tree projection is not given, then we are still able to end up with a useful result. Indeed, we can provide a fixed-parameter polynomial-time algorithm, where the parameter is the size of the valuation function, measured as the number of occurrences of weight functions. This algorithm may be useful in those applications where the number of weight functions is small, while the number of constraints is large (as it is often the case in CSPs). Note that this fixed-parameter tractability result should not be confused with tractability results where the parameter is the size of the whole constraint formula (equivalently, the size of the hypergraph to be decomposed), which may be useful only when the instance consists of a few constraints only. In such cases, however, the results presented in this paper are not needed, because if the parameter is the size of the constraint formula, then one can compute in fixed-parameter polynomial-time a tree projection [42], and then use known techniques for computing optimal solutions on acyclic instances. Proof. Consider the following algorithm: For any F ′ ∈ svf (F ), call the algorithm of Theorem 4.8. As soon as some invocation does not disprove the promise that F ′ can be embedded in (Φ, V), then we can return the answer we have obtained. To conclude, observe that we perform at most |svf (F )| iterations, and that |svf (F )| depends only on the number of weight functions occurring in F .
From the above theorem, we obtain the corresponding tractability result for Top-K , as in the proof of Theorem 4.9. In particular, because we may ask for an exponential number of solutions, fixed-parameter tractability means here having a promise-free algorithm that computes the desired output with fixedparameter polynomial-delay: The first solution is computed in fixed-parameter polynomial-time, and any other solution is computed within fixed-parameter polynomial-time from the previous one.

Parallel Algorithms
In the previous sections we have seen that the desired best solutions can be computed by just enforcing local consistency, without any explicit computation of the equivalent sandwich acyclic instance associated with some tree projection of the given CSP. However, in most practical applications, in particular when constraint relations contain a large number of tuples of allowed values (with respect to the number of constraints), having such an acyclic instance allows us to solve the given instance much more efficiently.
In particular, without using acyclicity, we need a quadratic number of operations for enforcing local consistency between each pair of constraints, contrasted with a linear number of such operations if the procedure is guided by any join tree of the given instance. From a computational complexity point of view, [52] proved that even establishing arc-consistency is P-complete and hence not parallelizable, while [32] showed that evaluating Boolean acyclic instances is LOGCFL-complete, hence inside P. Combining the latter result with the techniques of [33], it can be seen easily that even establishing global consistency in acyclic instances is in (functional) LOGCFL. It is known that all problems in this class are highly parallelizable. Indeed, any problem in LOGCFL is solvable in logarithmic time by a concurrent-read concurrent-write parallel random access machine (CRCW PRAM) with a polynomial number of processors, or in log 2 -time by an exclusive-read exclusive-write (EREW) PRAM with a polynomial number of processors.
In this section we provide parallel algorithms for the computation of the best solutions over a set of output variables O of a given constraint optimization formula Φ ′ F over a constraint database DB ′ , where F is a valuation function. These algorithms are significant extensions of a parallel algorithm originally given in [38].
We assume that a tree projection H a of (Φ ′ , V) (for some set of subproblems V) is given in input, too. By the results in [43], we assume w.l.o.g. that the number of hyperedges of H a is at most the number of variables occurring in Φ ′ , so that H a cannot be much larger than the original hypergraph of Φ ′ . Because the valuation function is built with a single operator, say ⊕, the embedding problem is trivial and any tree projection, in particular H a , can be used to solve the optimization problem. Therefore, a sequential algorithm can be obtained easily by using Lemma 4.5 and a dynamic programming algorithm as in [37]. However, it is not a-priori clear how to compute such solutions in parallel with a guaranteed performance that is independent of the shape of the tree projection at hand, and this is precisely the goal of this section. The algorithms proposed in this section generalize the DB-SHUNT parallel algorithm for evaluating Boolean conjunctive queries to relational databases presented in [32], which is in its turn based on a tree contraction technique which closely resembles the method of Karp and Ramachandran for the expression evaluation problem [51].
We refer the interested reader to [28], for a nice review of the literature on parallel approaches to solving CSPs. In particular, the importance of enforcing consistency (at different levels) in CSP solvers is pointed out. There are differ-ent models of parallelism, some more suited to distributed computations (useful when nodes are associated with difficult subproblems), and others to specialized parallel machines (see, e.g., Valiant's bulk synchronous parallel (BSP) and multi-BSP computational models [68], which can simulate the PRAM model, or the Immediate Concurrent Execution (ICE) abstraction, described in [69] for a general-purpose many-core explicit multi-threaded (XMT) computer architecture).
In this paper, we abstract from low-level details of the model and, following [32], we assume a shared-memory parallel EREW DB-machine, where relational algebra operations are machine primitives. In one parallel step of the DB-machine, each machine's processor can perform a constant number of relational algebra operations on the database relations at hand. Transformations of constraint scopes and input different from constraint relations are considered costless as long as they are polynomial. 9 The efficiency of a computation of the machine will be measured according to the following cost parameters: (a) the number of parallel steps; (b) the number of relational processors employed in each step, i.e., processors able to perform operations of relational algebra and related operations such as relational assignment statements (e.g., r := s where r and s are relation variables); (c) the size of the working constraint database. We refer the interested reader to [2] for a connection of our approach (called ACQ there) with Valiant's BSP and in particular to Map-Reduce models.

Enforcing Global Consistency in Parallel Given a Tree Projection
We first focus on the problem, of independent interest, of computing the (maximal) globally consistent sub-instance of the given constraint optimization formula. Recall that a CSP instance I with m constraints is said globally consistent, or equivalently m-wise consistent, or R( * , m)C-consistent, if, for every constraint C occurring in I, every tuple t of values in its constraint relation can be extended to a full solution of I. More formally, there exists a satisfying assignment θ for I such that t is given by θ applied (or restricted) to the variables in the scope of C. First observe that, by using the given tree projection H a and the DB-SHUNT algorithm described in [32], we can compute easily with a logarithmic number of parallel steps an equivalent acyclic instance having the same solutions of the original one. Just consider every hyperedge h of H a and the constraints having scopes s ⊆ h as a single acyclic instance (think of a join tree with h as its root label and all such constraints as direct children). We thus assume in the following that such an acyclic instance I = (Φ, O, DB) equivalent to the original instance has been already computed from Φ ′ , with Φ being an acyclic constraint formula, and DB its constraint database. We will omit the specification of the output variables O if it is understood that we are interested in solutions over Moreover, for an instance I as above, the algorithms use an additional tree T , called an e-Join Tree for I, defined as follows: each vertex p of T is a constraint occurring in I, whose scope and constraint relation are denoted, respectively, by Scope T (p) and rel (p); each constraint in Φ occurs as some vertex in T ; for each pair of vertices p, p ′ in T , the variables in Scope T (p) ∩ Scope T (p ′ ) occur in the scopes of all vertices in the path connecting p and p ′ in T . Moreover, the variables of Scope T (p) are partitioned in two distinguished sets R T (p) and I T (p).
Note that the above tree is essentially a join tree of the given acyclic instance. By using known results on join trees [32], it easily follows that, given I, we can compute in linear time or in logspace (and hence in parallel) an e-Join Tree T for I, whose number of vertices is linear in the number of constraints occurring in I, such that: T is a strictly-binary tree, i.e., every non-leaf vertex has precisely two children; and for every vertex p, I T (p) = ∅ (hence, R T (p) is equal to the original constraint scope occurring in I).
We assume that such a computation has already been done and we next focus on the evaluation of the CSP instance I with such an e-Join Tree T at hands. We remark that, from the resulting e-Join Tree T , we can immediately get, with at most one additional parallel step, the desired globally consistent constraint occurring in the original (possibly non acyclic) instance (Φ ′ , DB ′ ).
We next describe an algorithm that computes with (at most) a logarithmic number of parallel relational operations the (unique) maximal sub-instance of I that is globally consistent, which is hereafter called the globally-consistent reduct of I. Note that the naive parallel algorithm uses a linear number of parallel operations that depends on the tree-shape and that, in general, there is no guarantee that any balanced or similar good-shaped join tree exists for the given instance. Think, e.g., of a given CSP instance whose associated hypergraph is just a line.
Our algorithm transforms the e-join tree in stages, in such a way that the n-vertices tree T is contracted into a 3-vertices one in ⌈log n⌉−1 stages. At each stage, a local operation, called shunt, is applied in parallel to half of the leaves of T . Let l be a leaf of an e-join tree T , p the parent of l, s the other child of p, T ′ T Figure 6: Shunt operation applied to leaves 1,3 and 7 in parallel and q the parent of p (see Figure 5). The shunt operation applied to l results in a new contracted tree T ′ in which l and p are deleted, s is suitably transformed into a fresh constraint and takes the place of vertex p (i.e., it becomes child of q). Intuitively, as p is deleted, the variables occurring in both p and q must be kept in the new e-join tree, in order to guarantee the soundness of the procedure. To this end, whenever such variables do not occur in s, they are added to the scope of s (precisely, in I T' (s)). This way, after the application of shunt, by means of I T' (s), the new constraint at s stores the "witnesses" of the constraint tuples from p that are consistent with both s and l, and that are relevant to extend solutions to q (and up in the tree).
The leaves of T are numbered from left to right. At each iteration, the shunt operation is applied to the odd numbered leaves of T in a parallel fashion; to avoid concurrent changes on the same constraint, left and right leaves are processed in two distinct steps ( Figure 6). Thus, after each iteration the number of leaves is halved, and the tree-contraction ends within the desired bound.
To compute the globally-consistent reduct in parallel, we employ a two-phase technique. In the ascending phase, a shunt based procedure contracts the e-join tree; in the descending phase, the original tree shape is rebuilt by applying a sort of reverse shunt operation.
In the ascending phase, unlike the classical tree-contraction algorithm [32], no vertex is deleted but all processed vertices are modified and marked, for a subsequent use in the descending phase. A marked vertex is logically deleted for the ascending procedure and no shunt operation can be applied on it any more (during this phase). The mark is just a natural number encoding the step of the procedure that marked that vertex.
In our algorithm, a shunt operation performed at step w on the (current) e-join tree T , denoted shunt(w), proceeds as follows. We say that a leaf of T is unmarked (at step w) if it is an unmarked vertex having no unmarked child (hence, such a vertex it is not an actual leaf of the current tree, though it is a leaf of the sub-tree of T induced by its unmarked vertices). Let l be an unmarked leaf of T , p the parent of l, s the other unmarked child of p, and q the parent of p (as in Figure 7). The shunt operation applied to l results in a new e-join tree T ′ in which l and p are marked with w, s takes the place of vertex p (i.e., it becomes a child of q in T ′ ), and p becomes a child of s. The scopes of p and The constraint relations of p, s, and l in T ′ are just the projections over their scopes of the solutions of the subproblem comprising the constraints l, p, and s, i.e., in the relational framework, the projection of the relation C = rel (l) ⊲⊳ (rel (p) ⋉ rel(q)) ⊲⊳ rel(s). Additionally, the shunt operation produces and stores an updated version of vertex s of T , named s w , that will be used in the descending phase to rebuild possible p-s relationships coming from attributes in I T (s). This new constraint s w is stored into an additional storage (it is not in the e-join tree), its scope is Scope T (s w ) = Scope T (s) (the same as the old s) and its constraint relation rel(s w ) is the projection over this scope of the same relation C.
As soon as the ascending phase is terminated and the tree is contracted to a tree of depth 1, a descending phase gets started which re-expands the e-join tree by applying in parallel a reverse shunt operation.
The reverse shunt (r-shunt) operation unmarks (and updates) the vertices having the highest mark, say, w in the e-join tree. Let l and p be two vertices with mark w of an e-join tree T , such that p is the parent of l in T (note that l and p have been necessarily marked at the same step of the ascending procedure). Moreover, let s be the (unmarked) parent of p, and q, in turn, the (unmarked) parent of s (see Figure 8). The r-shunt(w) operation applied on l and p results in a new e-join tree T ′ in which the marks of l and p have been removed, p takes the place of s as a child of q, and s becomes a child of p. The scopes and the constraint relations associated to the vertices p and l in T ′ are the following: Intuitively, the new constraint for p is computed from its "frozen" version (which was marked at step w of the ascending phase) by enforcing consistency with both q and s. Actually, concerning s, p is made consistent with the constraint relation rel(s w ) ⋉ rel(s), because s w stores the variables shared by p and s in the ascending phase that were in I T (s) and are not present in the current scope of s. The relation for l is then obtained by enforcing consistency with the new p relation (note that the scope of p contains all variables that l shares with other unmarked vertices of the e-join tree).
The GLOBAL-CONSISTENCY algorithm is shown in Figure 9. The algorithm consists of two main phases. The ascending phase is similar to DB-SHUNT [32]: at each stage of the while loop performed in this phase, a shunt operation is applied to half of the unmarked leaves which get marked. After ⌈log n⌉ − 1 while iterations only three vertices remain unmarked. Then, instruction (5) computes the relation associated to the root of the tree, which is the final relation for this vertex and will be returned in the output database. Instruction (6) begins the descending phase, by fixing the values for the relations associated to the two children of the root. The descending phase "propagates" the correct relation values from the unmarked vertices to the marked vertices. The for loop unmarks the vertices marked during the ascending phase. In particular, an execution of instruction (7.a) unmarks all vertices marked by an execution of either instruction (4.b) or (4.d) of the ascending phase. Once a vertex is unmarked, its relation is fixed to the final value. Upon unmarking, the vertex is located exactly in the same tree position it had in the ascending phase (at the time when it was marked). Unmarking is performed by the r-shunt operations; each of them applies to a vertex l and to its parent p, both having the highest mark w in the current e-join tree. The relation for p is computed by eliminating from its old value all tuples which do not agree to its (unmarked) adjacent vertices. The relation for l is then obtained by a semi-join to its parent p. At the end of the for loop all vertices are unmarked and the associated constraints are returned.
Given an e-join tree T , we denote by verts(T ) the set of the vertices of Input: An acyclic CSP instance (Φ, DB) and an e-Join Tree T . Output: The globally-consistent reduct of (Φ, DB). begin (1) Let λ be the number of leaves in T ; (2) Label the leaves of T in order from left to right as 1, . . . , λ; for w := mark downto 1 do (a) in parallel apply r-shunt(w) to all pairs of adjacent vertices with mark w end (* for *) (8) output all constraints stored in the vertices of T . end. T , and by verts(T, s) the subtree rooted at vertex s of T . Moreover, define Mverts(T, s) as the set of vertices in the subtrees of T rooted at the marked children of s. Given a subproblem of the given CSP instance encoded as a set of vertices/constraints V of the e-join tree T , we will denote by ⊲⊳ V (or just V , if no confusion arises) the set of all its satisfying assignments, obtained as the (natural) join of all the constraint relations occurring in V . Proof. Given an acyclic CSP instance I, we denote by cr(I) the globallyconsistent reduct of I. Moreover, given a constraint p, cr(p, I) is the constraint occurring in the globally-consistent reduct, also called the consistent reduct of p w.r.t. I. Importantly, note that, by construction, the e-join trees keep the peculiar connectedness property of ordinary join trees during the computation. By the same arguments used for proving the soundness of DB-shunt [32], it turns out that at the end of the ascending phase the constraint associated with the root r of the e-join tree T is precisely cr(r, I).
Observe that, at each step of the computation, cr(p, I) is equal to the projection on R T (p) of the join of the constraint relations of all (marked and unmarked) vertices of the e-join tree at hand, i.e. ⊲⊳ verts(T ). Indeed, this property clearly holds at the beginning of the computation by definition of globally-consistent reduct, and it is easy to verify that the join of all constraint relations corresponding to the nodes of the e-join trees is an invariant of the algorithm. In fact, a tuple is discarded from a constraint relation at some step only if it is inconsistent with some other constraint.
By using an inductive argument we prove that, at any step of the descending phase, for each unmarked vertex p of the current e-join tree T , its constraint relation is equal to cr(p, I). (Basis.) We already pointed out that, at the end of the ascending phase, the root r holds cr(r, I). Moreover, it can be shown that, after the execution of instruction (6), rel (p) = cr(p, I) holds for each child p of the root. That is, after the execution of instruction (6) (the basis step of the descending phase), the root and its two children, which are the only unmarked vertices in the current e-join tree, contain precisely their respective consistent reducts for I.
(Induction step.) Assume the property holds for the e-join tree T computed after some executions of the loop at step 7. Consider one of the parallel steps executed on T by instruction (7.a), say, the execution of r-shunt(w) on vertices l and p, where p is the parent of l, and both vertices have the highest mark w of T . Let s be the parent of p, and q the parent of s, as shown in Figure 8. By the induction hypothesis, for the unmarked vertices s and q, rel(s) = cr(s, I) and rel (q) = cr(q, I). By applying r-shunt(w) on l, we get a new e-join tree T ′ where p replaces s as a child of q and s becomes a child of p (the other one is l). First, it can be shown that Rel T' (p) = cr(p, I). To this end, note that the consistent reduct of p can be obtained as cr(p, I) = RT(p) (U T q ⊲⊳ rel(q) ⊲⊳ T s ), where U T q = verts(T ) \ verts(T s ). Moreover, we use the fact that all variables occurring in both U T q and T s belong to Scope T (q), and that rel(q) is the consistent reduct of q and hence it is clearly consistent with ⊲⊳ U T q . It follows that cr(p, I) = RT(p) (rel (q) ⊲⊳ T s ). By means of a further elaboration on this expression, using a similar (though more involved) argument, we get cr(p, I) = RT(p) (rel (q) ⊲⊳ rel (p) ⊲⊳ SP ⊲⊳ rel(s)), where SP = verts(M T s ) \ verts(T p ). Recall that, at the execution of the shunt(w), we stored a relation Rel(s w ), which can be shown to be consistent with the full subproblem encoded by SP . Moreover, Sch(s w ) ⊆ (Scope T (p) ∪ Scope T (s)) by construction, so that we can prove cr(p, I) = RT(p) (rel (q) ⊲⊳ rel (p) ⊲⊳ rel (s) ⊲⊳ rel(s w )). Because Scope T (s) ⊆ Sch(s w ) and (Scope T (q) ∩ Sch(s w )) ⊆ Scope T (p), this constraint relation is equal to the result of the semi-join based computation in r-shunt(w). By similar arguments, we get that r-shunt(w) gives to us the constraint reduct for node l, too. Proof. Assume first that the number of processors c is half the number of leaves of the e-join tree, which is known to be ⌈n/2⌉, because it is a strictly-binary tree. Then each parallel operation can be executed by a different processor, and the ascending phase of GLOBAL-CONSISTENCY performs 2⌈log n/4⌉ shunt operations, because after each run of instructions 4a and 4b the number of leaves is reduced by half.
For the general case with c < ⌈n/4⌉: at the first iteration of the loop, we can equally divide the parallel shunt operations among the c processors, which means 2⌈n/4c⌉ operations. In the subsequent steps, the number of leaves (hence of needed processors) halves at each step. Then, to complete the loop, we need 2(2⌈n/4c⌉ − 1) operations until c = ⌈n/4⌉, followed by further 2⌈log c⌉ operations, as above.
Moreover, we note that this phase uses O(n) intermediate relations stored in the e-join tree, and we claim that the size of each such relation requires at most O(d 2 ) space.
The claim is proven by induction, assuming that for each vertex v, at each step, both RT(v) The claim trivially holds when the ascending phase starts. Consider the generic step depicted in Figure 5 where, after the shunt operation, the vertex s, which is a child of vertex p in the current tree T , becomes a child of vertex q in the new tree T ′ . Recall that, by definition, I T' (s) ⊆ R T (q). Because of the semijoin operation in the computation of the relation C and the fact that, by induction, RT(q) rel (q) ≤ d, we get d ≥ RT(q) C ≥ I T' (s) C . Moreover, RT(s) rel (s) is monotonically decreasing during the procedure. Then, the size of the relation rel (s) in the e-join tree T ′ is at most d 2 , as it is at most the cartesian product Note that all other vertices in T ′ have the same schema they have in T , and thus their stored relations, after the additional join operations computed in C, may only lose tuples with respect to T . For the sake of completeness, we note that the computation of the whole relation C is in fact not necessary to obtain the new relations in T ′ . Indeed, note that T encodes an acyclic query, so that the new relations for the vertices l, p, and s w can be computed easily in linear space by using the classical semijoin algorithm for enforcing global consistency over the acyclic subquery induced by vertices l, p, q, and s. After this procedure, the new relation for vertex s in T ′ can be computed by evaluating Scope T ′ (s) rel (p) ⊲⊳ rel (s) . The descending phase is even more efficient than the ascending phase. Indeed, the relation sizes decrease monotonically in the descending phase (only  semi-joins and projections are applied). With respect to the constraints appearing in the given e-join tree, the algorithm uses additional intermediate relations to store the s w vertices; however, since there is only one additional relation for each shunt operation performed in the ascending phase, the total number of intermediate relations is still linear in the size of the e-join tree (and hence in the number of constraints of the given instance). Moreover, the number of (parallel) steps performed in the descending phase is exactly the same as in the ascending phase. The same number of processors used in the ascending phase is clearly sufficient to perform the descending phase, and also the number of relational operations is the same (apart from a constant factor). Figure 10 shows the parallel algorithm ACSP for computing the best solutions of a given (already made) acyclic instance (Φ F , O, DB), given an e-join tree T of a tree projection for the given instance, and where F is a valuation function for Φ over ⊕. The e-join tree T is assumed to hold a global consistent instance, possibly computed by using the algorithm described in the previous section. Algorithm ACSP outputs a relation with the solutions θ over O, each one annotated with a value val (θ) ∈ D, which is the best possible value that can be obtained by extending the partial substitution θ to a full solution of the given instance. All tuples leading to the maximum value can thus be obtained immediately from this output relation. Clearly enough, such best solutions will be also the best solutions (w.r.t. F ) of the original (possibly non-acyclic) constraint formula (Φ ′ , DB ′ , O).

Computing Max
Algorithm ACSP proceeds similarly to the ascending phase of the previous algorithm, but the output variables are suitably preserved during all the computation, by propagating them towards the root of T . To this end, the scope Scope T (p) of any vertex p is now partitioned in three (instead of two) distinguished set of variables R T (p), I T (p), and O T (p), where the new set O T (p) contains output variables. For each vertex p of T , O T (p) is initialized to ∅.
The major novelty is due to the necessity of dealing with the optimization problem, which requires an extension of the classical relational operators so to manage the values provided by the weighting functions in wfs(F ). Every tuple θ of every vertex of the e-join tree T is associated with a value val (θ) ∈ D. Without loss of generality, we assume that D contains a neutral value for ⊕, denoted by 0, such that a ⊕ 0 = 0 ⊕ a = a, for all a ∈ D. 10 The e-join tree T is initialized as follows: Every vertex s whose associated constraint occurs in the constraint formula with some weigh function f , is such that every tuple θ ∈ rel (s) has value val (θ) = f (θ); for every other relation in the e-join tree, all tuples have value 0.
Given two vertices R 1 and R 2 , define the extended join operation R 1 ⊲⊳ ⊕ R 2 as the set of tuples Then, the shunt operation is redefined as follows. Let l be a leaf of an e-join tree T , p the parent of l, s the other child of p, and q the parent of p. The shunt operation applied to l results in a new contracted e-join tree T ′ in which l and p are deleted, s is transformed (as specified below) and takes the place of vertex p (i.e., it becomes child of q). The scope and the constraint relation of the transformed version of s in T ′ are specified below.
Thus, each output variable occurring in a deleted constraint (p or l) is kept in s (if it does not belong to R T' (s) ∪ I T' (s), then it is added to O T' (s)).
Theorem 5.3. The algorithm ACSP is correct.
Proof. The proof can be derived by a similar line of reasoning as for the previous algorithm; only a few remarks are needed. By the new definition of shunt, no output variable disappears from the e-join tree during the computation: whenever the last constraint containing an output variable X is deleted, X is stored in an O T attribute of another vertex. Thus, when the last iteration of instruction (3) is executed, all variables in O are still present in the tree (i.e., it holds that O ⊆ Scope T (p) ∪ Scope T (p ′ ) ∪ Scope T (p ′′ )). Moreover, if a variable X occurs in O T (p) for some vertex p of an e-join tree T generated during the computation of Algorithm ACSP, then X does not appear in the scope Scope T (q) of any other vertex q of T . Thus, O T variables are not playing as join attributes in any shunt operation performed in the algorithm. They are used only for storing and preserving, during the computation, the assignments over output variables that will eventually be output as solutions.
Finally, at the end of the algorithm, the root holds a relation where the value val (θ) ∈ D of each tuple θ is the best possible value that can be obtained by extending it to a full solution of the given instance. Indeed recall that F is a valuation function for Φ over a single operator ⊕ so that there is always a natural embedding for any tree projection, with every vertex that can play the role of a separator. Then, the statement easily follows by the definition of the extended operators ⊲⊳ ⊕ and ⊕ , and by Lemma 4.5. Proof. Use Algorithm ACSP on (Φ, O, DB) and its e-join tree: the while loop of instruction 2 is very similar to the ascending phase of the previous algorithm, so that it is easy to see that property (a) of the theorem stems from the proof of Theorem 5.2. Concerning property (b), compare the algorithm for enforcing global consistency in Figure 9 with ACSP, where the extra output variables that are kept in the e-join tree T may increase the size of the intermediate relations. If the cardinality of the set O is bounded by a fixed constant, such a size is bounded by a polynomial of the input size. However, in general the set O is arbitrary, possibly the whole set of variables occurring in the CSP instance. Therefore, to get the desired output-polynomial bound (property b), we use the crucial property that the given instance is global consistent, so that each tuple of values which is stored in the output variables during the while loop of ACSP will eventually be part of the solutions (no tuple can be deleted during the while loop). It follows that the size of the (partial) assignments over the output variables in the intermediate relations cannot exceed the size v of the result.
Because the number of solutions over the output variables O can be exponential with respect to the size of the input, if we are interested in computing just one best solution, the complexity can be made smaller by using O = ∅ in ACSP and then building the desired solution backward with a final top-down step.

Further Related Work
In this section, in addition to the references already given, we discuss further literature that is closely related to our research, by emphasizing our specific modeling choices.
Soft Constraints Soft constraints are classical constraints [16] enriched with the ability of associating either with the entire constraint or with each assignment of its variables a weight (meant to encode, for instance, a level of preference or a cost). The use of soft constraints leads to generalizations of the basic CSP setting, such as fuzzy [19], probabilistic [22], possibilistic [65], partial [27], and lexicographic [23] CSPs. These extensions can be viewed as special instances of the general setting of semiring-based CSPs [8], where each assignment in a constraint is associated with a value taken from a domain D over which a constraint-semiring D, ⊕, ⊗, 0, 1 is defined 11 . Intuitively, ⊗ is a binary operator combining the values associated with the various constraints, while ⊕ is a binary operator inducing a partial order ⊕ over D such that a ⊕ b if and only if a = a ⊕ b holds. The goal is to find an assignment whose total value is minimal w.r.t. this order. In many cases of practical interest, the domain D is already associated with a total order and, therefore, the semiring-based model can be reduced to the setting of valued CSPs [66]-see [6], for a formal comparison of the two settings. In a valued CSP, the domain is part of a valuation structure D, ⊛, ≥ , where ≥ is a total order over D and where ⊛ is a commutative, associative, and monotonic binary operator used (as usual) to combine the values. For instance, let k ∈ N∪{∞} be an element taken from the set of the natural numbers extended with the positive infinity 12 and consider the valuation structure {0, 1, ..., k}, ⊕, ≥ where a⊕b = min{k, a+b}. This structure gives rise to the well-known weighted CSP setting: For each constraint (S v , r v ) and for each assignment θ v over the variables in S v , if θ v is not in r v , then its value is k, which basically means that the given partial assignment is forbidden. Instead, if θ v is in r v , then its value is a non-negative cost. The goal is to check whether there is any ≥-minimal assignment whose associated value is different from ∞, and to compute one if any. Despite their simplicity, weighted CSPs are expressive enough to model all valued CSPs over discrete valuation structures, provided that ⊛ has a partial inverse [14].
Encodings From the above discussion, it is easily seen that hard and soft constraints do not need to be explicitly distinguished in the formalization, since hard constraints can be enforced by just associating an infinite cost to the assignments that are not admissible (and then looking for solutions with minimum cost). However, algorithms exploited to process hard constraints often assume a relational representation where only the allowed tuples of values for each hard constraint are listed, while soft constraints algorithms assume a tabular representation where all possible assignments are listed together with their values. Therefore, encoding a hard constraint in terms of a soft one might lead to an exponential blow-up of the size of its representation. For an extreme example, consider a constraint (S v , r v ) such that r v does not contain any assignment. To encode this (hard) constraint in terms of a weighted CSP, we have to associate with all possible assignments over S v the value ∞. The number of these assignments is clearly exponential in the arity of S v , i.e., |S v |, and hence representing them in tabular form might quickly become unfeasible.
In fact, most of the works in the literature on soft CSPs do not care about the issue, because a bounded-arity setting is (implicitly) considered, i.e., the size of the largest constraint scope is assumed to be bounded by a fixed constantwhen this constant is 2, then we get the classical setting of binary CSPs [3]. In the present paper, instead, we have not posed any arity bound on the given constraints, so that it was natural to avoid listing all possible assignments (cf. [56,53]). Accordingly, we assumed that the input to our reasoning problems is given by a standard CSP instance I, where only the assignments that are allowed are explicitly represented, plus an optimization function built on top of a valuation structure (over a set of binary operators) associating a value only with the assignments that are contained in some of the constraint relations of I.
Decomposition Methods One of the most important and deeply studied island of tractability for standard CSPs is the class of instances whose associated hypergraphs are acyclic [70,21,20]. Structural decomposition methods are approaches for extending the good results about this class to relevant classes of nearly acyclic structures (see, e.g., [31,12,39] and the references therein). On CSP instances having bounded arity, the tree decomposition [63,17,26] emerged to be the most powerful decomposition method [45]. Its natural counterpart over arbitrary instances is the (generalized) hypertree decomposition method [34,35], but it has been observed that this method does not chart the frontier of tractability-for instance, further classes of tractable instances can be identified via the fractional hypertree method [46,60] (see also the more recent results in [24]). All these methods (including fractional hypertree decompositions) fit into the framework of the tree projections [29,64,35], within which the results derived in the paper have been positioned.
Structural decomposition methods have been shown to play a crucial role even in presence of soft constraints, as introduced above. Indeed, the tractability of semiring-based and valued CSPs over structures having bounded treewidth has been shown in the literature [8,67], and the effectiveness of the solution approaches has been practically validated, too (see, e.g., [48]). Actually, in a variety of automated reasoning areas, similar solution algorithms over structures having bounded treewidth have been proposed over the years. A unifying perspective of all of them has been provided by [53], where the concept of graphical model is introduced (essentially capturing a valuation structure) and where the bucket-tree elimination algorithm has been introduced to solve instances of this model having a tree-like structure. In [53] it has been also shown how these results can be extended if the notion of hypertree decomposition is used in place of the notion of tree decomposition. However, for this extension, the given valuation structure has to satisfy certain technical conditions 13 , which reduces its range of applicability.
Efficient solution algorithms that work on instances having bounded hypertree width and with arbitrary valuation structures have been more recently proposed by [40,30]. In the present paper, we further generalized these algorithms to deal with complex optimization functions where more than just one aggregation operator is allowed. Moreover, unlike all the references reported above, we have not assumed that a decomposition is given (except for Section 5), which is a useful assumption when computing a decomposition is an NP-hard problem [35]. This has been obtained by designing promise-free algorithms that either compute correct certified solutions, or disprove the (promised) existence of a decomposition, in the spirit of [11]. Both generalizations are non trivial, and novel technical machineries have been required.
Constraint Propagation From a technical viewpoint, our algorithms are based on procedures enforcing pairwise consistency [4], also known in the CSP community as relational arc consistency (or arc consistency on the dual graph) [16], 2-wise consistency [47], and R( * , 2)C [50], which are suitably adapted to deal with the propagation of the weights (in addition to the propagation of the information in the allowed assignments).
Constraint propagation is a fundamental technique in the context of CSPs (see, e.g., [16]), and a number of different propagation strategies have been proposed over the years for standard CSPs. Moreover, it is known since the very introduction of the setting of valued and semiring-based CSPs that suitable notions of consistency can be used for propagation in the constraint optimization framework, too. It has been observed in [8] that when the aggregation operator is idempotent, then soft local consistency terminates by producing an instance equivalent to the original one and in a way that the result does not depend on the order of application of the propagation rules-see also [7], for a general environment supporting different forms of soft propagations founded on these properties. The result excludes non-idempotent operators, such as the very basic summation, and hence it has a limited scope of applicability. However, for operators that are not necessarily idempotent but admit a partial inverse, a notion of soft arc consistency can be defined whose enforcement preserves at least the equivalence with the original instance [13]. The goal of soft arc consistency is to transform a problem into an equivalent one, by providing incrementally maintainable bounds which are crucial for branch and bound search [57]. Motivated by the fact that the fixpoint of the computation is not unique and may lead to different lower bounds, the problem of finding optimal sequences of soft arc consistency operations has been recently addressed by [15].
While our algorithms might be abstractly viewed as methods enforcing (suitable kinds) of soft consistency, it must be pointed out that they are completely orthogonal to the research illustrated above. The correctness of our propagation strategies (except for Section 5) only requires that the instance has a tree-like structure (without any further knowledge about it, but its existence) to find the optimal sequence of consistency operations leading not only to a bound, but in fact to the exact solution. There is no obvious way to extend our results to design algorithms for efficiently solving (or just enforcing bounds in) arbitrary instances.

Conclusion
A formal framework for constraint optimization has been proposed and analyzed. The computational complexity of reasoning problems related to computing the best solutions have been studied. In particular, structural tractability results have been derived within the general setting of tree projections. Transferring our theoretical findings into the design of a practical platform for constraint optimization is a natural avenue of further research. With respect to foundational analysis and theoretical contributions, instead, efforts might be spent to study extensions of the framework supporting, for instance, forms of multi-criteria optimization.
A Proof of Theorem 4.8 In this section, we analyze the correctness of Compute-Max. The proof is rather involved and is discussed incrementally.
Hereinafter, recall that Φ is a constraint formula, DB a constraint database, O ⊆ vars(Φ) a set of variables, F a valuation function, V a view set for Φ, and DB' a legal database instance for V w.r.t. Φ and DB. Moreover, recall the following.

A.1 Promise Tractability
For any set of variables O, define atom(O) to be a fresh atom (with a fresh relation symbol) over these variables, i.e., such that O = vars(atom(O)). We start the analysis of Compute-Max by considering the following promise: Note that after local consistency, from Proposition A.1, for every q ∈ Φ a , and DB ′′ , where Φ ′′ = q∈Φ ′ [qX the atom w pi in the sandwich formula covering the p i -separator, as in the statement of Lemma 4.5. Therefore, if ⊕ i is the operator labeling p i in the parse tree, from this lemma get max ]. It follows that the desired combined maximum is achieved, for any projected assignment θ[h i ], on some assignment θ ′ ∈ [w i X and t ′ [w i ] ∈ Φ DB , that gets maximum weights according to both F p b and F p b . Of course such a correct assignment is preserved under any step of the algorithm, and we know that the weights are correctly propagated via the tree-projection. Then, the marginalization step correctly selects the right maximal weights for every assignment according to F pi .
Finally, observe that, from the inductive property proved for the two variables X in the discussion about propagate and from Lemma 4.4, it follows that the inductive statements hold for sep i , too. Now consider the step where the selection of a "minimum view" (if any) is executed. Observe that, by the inductive hypothesis, wrong views may only get better maxima for their assignments. Therefore, for any set of augmented views V w ⊆ sep i with the same "base" view w, we may safely select for each assignment θ ∈ w DB , its version with the lowest marginalized weight X (w ′ ) i among all views in V w . More precisely, observe that such a selection does not alter the validity of the two inductive statements. Moreover, as far as augmented views over different base views are concerned, we may safely consider the absolute maximum. Clearly, the right one (if any) should be the smallest one, from the inductive statements. Therefore, looking at this maximum, we are able to discard augmented views that cannot contain the variables of an actual sep i separator, and more importantly we enforce the actual maximum to be an upper bound for all weights computed in the algorithm for F pi and, at the end, for F .
We can now show the correctness of Compute-Max under P1. Proof. Note first that, whenever the algorithm outputs NO SOLUTION, then the constraint database obtained by enforcing local pairwise-consistency is empty. Hence, we are guaranteed that there is no solution at all in Φ DB .
Consider then the case where the algorithm does not output NO SOLUTION. In this case, correctness follows from Lemma A.2 applied to the root p s , which contains a unique augmented view, after the selection of the "minimum" view in function evaluate. Such a view contains only corrected weights if (F , O) can be embedded in (Φ ′ , V) for some subformula Φ ′ of Φ ∧ atom(O) such that Φ ′ ≡ h Φ ∧ atom(O). On the other hand, the algorithm outputs FAIL only when it recognizes that this condition does not hold, because there are no feasible separators at some step, or when it turns out that the formula has no answers at all. Observe that Algorithm Compute-Max performs s − 1 iterations of the for loop plus some further operations, each one feasible in polynomial time (where the mathematical operations cost 1). In particular, local consistency requires polynomial time w.r.t. the given set of views and the given constraint database, and note that we deal with at most O(|V| 2 F ) views in the algorithm, where F denotes the size of F , which is an upper bound to the total number of vertices of its parse trees.
Finally, note that the the size of the weights computed during the execution of the algorithm is polynomially bounded w.r.t. the size of the input. Indeed, recall from Lemma A.2 that we avoid the computation of wrong weights larger than the actual maximum, if the promise is true. Otherwise, we cannot guarantee anything: just think that the formula may be empty if there are no tree-projections at all (no matter of formula embeddings).

A.2 Larger Islands of Tractability
We now show how to solve Max under a less stringent promise than P1, by using Compute-Max as an oracle. For any variable X, define atom X ({X}) to be a fresh atom (with a fresh relation symbol) such that {X} = vars(atom X ({X})).
Consider the following promise: values obtained this way for variables in O form an assignment that is returned as output as a solution to Max. Note that, at each step, Compute-Max can disprove the promise P1 (and, hence P2), by returning FAIL. Moreover, our procedure may additionally disprove the property P2, whenever there is a pair of values θX and θX′ associated with different maximum weights by Compute-Max. Finally, if some subsequent invocation returns NO SOLUTION (after that the first invocation did not return NO SOLUTION or FAIL), then we can conclude that there is no sandwich formula of Φ w.r.t. V (by the results in [42,41]), and hence the promise is again disproved.
By the above result and the approach by Lawler [59], we obtain the corresponding tractability result for Top-K . Proof. LetΦ = Φ ∧ X∈O atom X ({X}). Update V by adding the base views associated with such novel atoms. Moreover, update DB and DB' by adding the relations associated with these views, each one containing the whole active domain dom(X) of any variable X ∈ O. Note that Φ DB =Φ DB and that DB' is legal. By P2, F can be embedded in (Φ ′ , V) for some subformula Φ ′ of Φ with Φ ′ ≡ hΦ . Then, P2 clearly holds forΦ, too. From Theorem A.3, Max(Φ F , O, DB) can be computed in polynomial time. Therefore, we can apply Lawler's procedure [59] onΦ, by using Compute-Max as an oracle. In particular, at any step, the oracle will be called with a different constraint database obtained by changing the atom X relations (as in [54]), and with the base views in the constraint database DB' changed accordingly. Note that, at each step, Max is still feasible in polynomial time, as we just change the database instance over which it has to be solved, without affecting the structural promise.

A.3 Putting It All Together: Computing Certified Solutions
We can now complete the picture, by showing that the above results may be exploited to design an algorithm that always output reliable answers. Indeed, if it is not possible to compute a correct solution, the promise is disproved. In particular, the price of having certified solutions is now to consider the following more stringent promise: (P0) F can be embedded in (Φ, V). Proof. Assume that P0 holds. Then, we derive that F can be embedded in (Φ ∧ X∈vars(Φ) atom X ({X}), V), because any tree projection of Φ w.r.t. V clearly covers every single variable in vars(Φ). Then, the promise P2 holds on Φ ∧ X∈vars(Φ) atom X ({X}) and, thus, we can exploit Theorem A.3 to compute a solution to Max(Φ F , vars(Φ), DB). Assume that the procedure in the proof of Theorem A.3 succeeds (otherwise P2 and thus P0 are disproved). If the result is NO SOLUTION, then we are in fact guaranteed that there is no solution at all. Otherwise, let θ be its output. Let v max be the one weight associated with all partial solutions at any invocation of Compute-Max. Then, in polynomial time we check that θ is in fact an answer in Φ DB , and that F (t) = v max . If the former check fails, then we conclude that no tree projections exist (and thus no embedding may exist, as well). Otherwise, from the proof of Lemma A.2, max F (θ[X]) ≤ v max , for each variable X ∈ vars(Φ). Therefore, if F (θ) = v max we are sure that the result is correct, and else that the promise does not hold.
By following the same line of reasoning as in the proof of Theorem A.4, we get the corresponding result for Top-K .