2.1. Frames and parts

In

each frame C represents a class ∥C∥ of objects (either atomic or complex) and it has a set of member slots associated with it (as usual, if x is a language element, we denote its semantics with ∥x∥).

Because of the relevance of the whole–part relation between a complex component and a part of it in the configuration task, a special status has been assigned to such relations, which are modeled via partonomic slots, whereas other properties and features of both complex and atomic objects are modeled via descriptive slots. In particular, partonomic slots in

capture the complex–component relation described in Gerstl and Pribbenow (1995). This relation is assumed to be asymmetric and transitive. Formally, any partonomic slot p of a frame C is interpreted as a relation ∥p∥ from ∥C∥ to the class ∥D∥ denoted by its value restriction D (for partonomic slots, the value restriction is always a frame) such that (∀c ∈ ∥C∥)(m ≤ card(∥p∥(c)) ≤ n), being [m, n] , its number restriction, and card(X) denotes the cardinality of the set X. The meaning is straightforward: any complex component of type C has from a minimum of m up to a maximum of n parts of type D via a whole–part relation named p.

The value restriction D of any descriptive slot q of a frame C always denotes a nonempty set of values of a predefined kind (i.e., integers, reals, strings, etc.). As in the case of partonomic slots, a descriptive slot is interpreted as a relation ∥q∥ from ∥C∥ to ∥D∥ such that m ≤ card(∥q∥(c)) ≤ n.

In

taxonomies, each class has a single superclass (i.e., taxonomies are trees); it inherits the slots (both partonomic and descriptive) of its superclass and can refine the description of the superclass by specifying additional (w.r.t. those inherited) slots or by restricting the number restriction and/or the value restriction of any inherited slot (according to the rules of strict inheritance typical of KL-One languages). The subclasses of any class are exhaustive (i.e., any instance of a class must be an instance of one of its subclasses) and disjoint (i.e., there is no instance of a class that belongs to two different subclasses of this class).

Figure 1 represents a fragment of the partonomic and taxonomic knowledge of a conceptual model relevant to PCs. Each rectangle represents a class of complex components, each oval represents a class of atomic components, each solid arrow corresponds to a partonomic slot, and each dashed arrow corresponds to a descriptive slot. The conceptual model sketched in the figure states that a PC is a complex object containing, among other things, a keyboard, from one to seven hard disks, an optional CD writer, a motherboard, and so on. The keyboard, the hard disks, and the CD writer are all atomic components whereas the motherboard is a complex component. The motherboard contains a main printed circuit board (described by its model, price, and type), an optional SCSI controller and other components. In the restricted world we are modeling, the PCs can be of two different types only: advanced application PCs or low cost PCs. Any advanced application PC always has a CD writer and a CD reader (i.e., in the advanced application PC class, the number restriction intervals of the inherited slots has_cdw and has_cdr have been restricted from [0,1] to [1,1]). Moreover, in any advanced application PC, the CD writer, the CD reader, and the hard disks must be the SCSI type. (In fact, the value restriction of the inherited slot has_hd has been restricted from the more general type Hard_Disk to the more specific type HD_SCSI). Analogous restrictions hold for the slots has_cdw and has_cdr). All the other partonomic slots of the PC class are inherited as they are. Unlike low cost PCs, an advanced application PC can have a CD tower (which is a complex component).

A sample (portion of a) conceptual model: the partotaxonomic knowledge.

Given a

conceptual model CM and a class C₁ of complex components in the CM, a slot chain starting in C₁ and ending in D is a sequence γ = 〈p₁, p₂,…, p_h〉 (h ≥ 1) of member slots such that in the CM there are the classes C₂,…,C_h−1 of complex components and the class C_h (either of atomic or complex components) such that C_i (1 ≤ i ≤ h − 1) has a partonomic slot named p_i (possibly inherited) whose value restriction is C_i+1 and C_h has a slot (either descriptive or partonomic and possibly inherited) named p_h whose value restriction is D, which can be either a class of (complex or atomic) objects of the CM (if p_n is a partonomic slot) or a set of

predefined values (if p_n is a descriptive slot). The semantics of such a slot chain is a natural generalization of the semantics of a single slot, because it is interpreted as the relation composition ∥〈p₁, p₂,…, p_h〉∥ ≡ ∥p_h∥ ∘ ∥p_h−1∥ ∘ ··· ∘ ∥p₁∥ from ∥C₁∥ to ∥D∥. That is, if h = 1, ∥〈p₁〉∥ is a relation from ∥C₁∥ to ∥D∥, such that (∀c₁ ∈ ∥C₁∥)∥〈p₁〉∥(c₁) = ∥p₁∥(c₁); if i ≥ 1 and h = i + 1, ∥〈p₁,…, p_i+1〉∥ is a relation from ∥C₁∥ to ∥D∥, such that (∀c₁ ∈ ∥C₁∥)(∥〈p₁,…, p_i+1〉∥(c₁) ≡ ∪_{ci+1∈∥〈p1,…, pi〉∥(c1)}∥p_i+1∥(c_i+1)), where the operator ∪ maintains repeated values of

predefined types, in case p_i+1 is a descriptive slot.

More intuitively, if p_h is a partonomic slot, the chain represents the subcomponents of a complex component c₁ ∈ ∥C₁∥ via the has-part relationships named p₁,…, p_h. The subcomponents referred to by the slot chain form a set. (No subcomponent is repeated inside it.)

If p_h is a descriptive slot, this chain represents the values of the property p_h for the subcomponents of c₁ via the has-part relationships p₁,…, p_h−1. Because the property p_h may have the same values in different subcomponents, the slot chain denotes a multiset (i.e., there can be repeated property values).

Similarly, a set of slot chains R = {γ₁,…, γ_k}(k ≥ 1) [each one starting in C₁ and ending in D_i (i = 1,…, k)] is interpreted as the relation union ∥R∥ ≡ ∪_i=1^k∥γ_i∥ from C₁ to ∪_i=1^kD_i.

For example, in Figure 1, the slot chain 〈has_m,has_mpcb〉 starting in PC represents the main printed circuit board of a PC, while the price of that component in a PC is represented by the chain 〈has_m,has_mpcb,price〉. The set of slot chains starting in PC {〈has_hd〉〈has_cdr〉〈has_cdw〉} represents the set of hard disks, CD reader, and CD writer of a PC.

2.2. Constraints

In modeling the real-world domains the expressive power provided by the frame portion of

is not sufficient; in particular, number restrictions and value restrictions cannot capture complex interslot constraints relating the components and the subcomponents of the complex objects.

For this reason,

puts a constraint language at our disposal. However, each constraint is associated with a class of complex components in order to have a uniform structured approach to knowledge representation. In this way, constraints complement partonomic and descriptive slots in capturing the characteristics of a complex object.

Given the class C and a constraint co associated with it, co is of the form α ⇒ β, where α is a conjunction of

predicates or the Boolean constant true and β is a predicate or the Boolean constant false. The meaning is that for every complex object c ∈ ∥C∥, if c satisfies α then it must satisfy β. It should be clear that if α = true, then, for each c ∈ ∥C∥, β must always hold, while if β = false, then, for each c ∈ ∥C∥, α can never hold. The contradiction true ⇒ false is not a valid constraint.

Actually,

is a bit more general, because it allows a constraint to be a clause whose literals are positive or negative

predicates. However, here we restrict the attention to constraints having a Horn-clause form. This restriction does not affect the decomposition mechanisms that we describe.

Each class (but the root of the taxonomy) inherits all the constraints of its superclass.

In the following, only a subset of the predicates available in

is described. Let R = {γ₁,…, γ_k} be a set of slot chains starting in a class C. The last slots of the chains occurring in R can either be all descriptive or all partonomic. Therefore, in the former case, for each c ∈ ∥C∥, ∥R∥(c) can generally be a multiset of property values, whereas in the latter it is a set of components.

Four types of predicates are briefly described.

1. (R)(m; n), where the last slots in the chains occurring in R are partonomic and m, n are nonnegative integers with m ≤ n. Here c ∈ ∥C∥ satisfies the predicate iff m ≤ card(∥R∥(c)) ≤ n.
2. (R)(inI₁ ∪···∪ I_s), with (s ≥ 1). If the last slots in the chains occurring in R are partonomic, each I_j(j = 1,…, s) is a class of components and c ∈ ∥C∥ satisfies the predicate iff ∥R∥(c) ⊆ ∥I₁∥ ∪···∪ ∥I_s∥. Similarly, if the last slots in the chains occurring in R are descriptive, each I_j denotes a set of
   
   predefined values and c ∈ ∥C∥ satisfies the predicate iff each v ∈ ∥R∥(c) belongs to ∥I₁∥ ∪···∪ ∥I_s∥.
3. (R)(inI₁ ∪···∪ I_s(m; n)), where (s ≥ 1), the last slots in the chains occurring in R are partonomic, each I_j(j = 1,…, s) is a class of components and m, n are nonnegative integers with m ≤ n. Here c ∈ ∥C∥ satisfies the predicate iff m ≤ card(∥R∥(c) ∩ (∥I₁∥ ∪···∪ ∥I_s∥)) ≤ n.
4. (f (R)) RelOp (g(S)), where S = {δ₁,…, δ_t} is a set of slot chains starting in C and different from R, the last slots in the chains occurring in R or S are descriptive, and their value restrictions denote numeric sets. Here c ∈ ∥C∥ satisfies the predicate iff f (∥R∥(c)) RelOp g(∥S∥(c)), where RelOp ∈ {=, <, >, ≤, ≥} and f and g are two functions belonging to the set of built-in functions provided by the conceptual language. [These functions include the sum ([sum ]), the minimum (min), and the maximum (max).] For example, c ∈ ∥C∥ satisfies (max(R)) ≤ ([sum ](S)) iff max(∥R∥(c)) ≤ [sum ]_{v∈∥S∥(c)} v.

A (small) subset of the constraints holding in a real computer system domain is reported in Figure 2, where a short explanation in natural language is provided for each constraint.

A sample (portion of a) conceptual model: the constraints.

4.1. A motivating example

As stated in the Introduction, the automatic configuration task can be, in general, computationally expensive. In fact, the components and the subcomponents of a configurable object usually have to respect a set of constraints, both endogenous (i.e. specific to the modeled domain, such as technical or physical constraints) and exogenous (imposed as additional requirements by any agent requiring a customized product). Usually, these constraints link together many components and subcomponents. Thus, rarely can a configuration be computed by a process making only a set of local choices. In most cases the configuration task is performed by a search process. When a choice made for a component during the configuration activity prevents another (or even the same) component from being configured, the process (if possible) backtracks, revises a past choice, and explores a different path in the search space.

If we consider the conceptual model in Figures 1 and 2,³

In many cases, the search space is quite huge and many paths in it do not lead to any solution. Moreover, there is no guarantee that a solution always exists for any configuration problem.

Because we are interested in problem decomposition as a way of controlling complexity and for supporting interactive configuration, we explore two different decomposition strategies.

4.1.1. Requirements-based decomposition. A first kind of decomposition (requirements-based decomposition) requires the ability of recognizing which components and subcomponents might be critical for the satisfaction of the user's requirements. In this way, the problem of configuring a complex object can be decomposed into two subproblems: the subproblem of configuring those parts of the target object that are related in some way to the requirements (i.e., to the exogenous constraints) and the subproblem of completing such a partial configuration by considering the remaining components.

The consistency assumption on the conceptual model (Assumption 2) gives a good reason for considering first the components and subcomponents that might be critical for the satisfaction of the user's requirements and then the other ones. In fact, given this assumption, if a configuration problem has no solution, this is due to the exogenous constraints (which can be inconsistent either by themselves or w.r.t. the conceptual model). By first considering the components possibly involved in these constraints, we expect that the inconsistency of the requirements will be detected early (in average) in the configuration process (saving useless work).

Let us suppose, for instance, that a user states the set of inconsistent requirements consisting in those listed in Figure 3 plus the requirement that no Unix operating system should be installed ([req4]true ⇒ ({< has_os >})(inUnix(0;0))). It should be clear that the constraints req2, req4, and co4 cannot be satisfied in the same configuration. The components that can be critical for meeting the requirements from req1 to req4 are the main printed circuit board, the software applications, the operating systems, and the CD tower, because they are directly mentioned in the requirements. Besides these components, the SCSI controller must also be considered, because it is related to the main printed circuit board by the constraints co1, co2, co3, and co8; furthermore, all the other components referred to by these constraints have to be taken into consideration (hard disks, CD readers, and CD writers).⁴

The user's requirements for an advanced application PC.

The other components (such as the keyboard, video cards, RAM memory slots, and so on) do not have any influence on the requirements. In this case, introducing these last components into the configuration would be a waste of time, because no solution can be found, whatever choices are made for them.

Moreover, requirements-based decomposition allows the configurator to perform a more focused search (even when the requirements can be met). In fact, whenever the configuration process enters a failure path in the search space in which a requirement is violated, a revision of any choice made for a component that had been recognized a priori to be independent from the requirements would be useless and it can be easily avoided by considering such components in a second phase.

The ability to distinguish which parts of the configurable object might be critical for the requirements satisfaction also has other motivations. In fact, if the task is that of checking the consistency of the requirements, the configuration of the whole product would be a useless effort in many cases. In this case, the computation of a partial configuration, involving only the components that may prove critical for the requirements, is enough. Moreover, this ability is important in any system supporting an interactive configuration. In this task, we cannot assume that all the requirements are always known from the beginning because they can be incrementally added by the user. In this scenario, the system should not be too eager to complete the work (i.e., to configure the entire target object); it is important for it to recognize which components can be critical for the satisfaction of the current set of requirements and to limit its choices to them by leaving the user the possibility of adding some requirements for components not yet introduced into the configuration.

In the (consistent) set of requirements in Figure 3, req3 specifies that a CD tower must be present in the configuration. However, nothing else is stated about the CD tower. If, for example, we want to allow the user to express some requirements for it in a second phase, the configurator should only insert into a configuration a (generic) CD tower without configuring it. The user can specify at a later time how many and which kinds of CD readers and CD writers she/he wants. Furthermore, when a product needs to be reconfigured in order to meet a new set of requirements, it can be helpful to single out the subset of components that will be involved in the reconfiguration process.

4.1.2. Constraints-splitting decomposition. A second kind of decomposition (constraints-splitting decomposition) is based on a different observation. As we said, the constraints (both endogenous and exogenous) usually link together the components and the subcomponents. Moreover, the constraints themselves can be bound [through the (sub)components to which they are relevant] in a way that a choice made in order to satisfy one of them may restrict the choices available for satisfying another one.

We saw that in the considered conceptual model the software applications and the operating systems are linked together by the constraints co4 and co5. In other words, we can say that these two constraints are bound together. In fact, in order to satisfy co4, we could install in a PC two (different) Unix operating systems. This choice has an impact on the choices available for satisfying co5, since, given the previous choice, the only valid possibility is not to install any Microsoft application. (Note that the choice of adding both some Microsoft applications and a Windows operating system is not available any more, because the conceptual model states that at most two operating systems can be installed in a PC⁵

However, in many cases not every constraint interacts with each other and the ability of recognizing the sets of (possibly) interacting constraints offers the basis for a problem decomposition that considers each set of bound constraints separately.

Let us again consider the requirements in Figure 3. The constraints co4, co5, and req2 refer to the same components (i.e., software applications and operating systems), thus they interact among themselves. However, req3 interacts neither with the other requirements nor with the endogenous constraints. This means that if, for instance, the configuration process reaches a region in the search space where one or more constraints among co4, co5, and req2 are violated, revising a previous choice for the CD tower would not move the search away from the failure region. This suggests that the requirement req3 and the set of constraints co4, co5, and req2 could be considered separately (either in sequence or in parallel) in order to have a more focused search.

As we shall see, in the

framework, the partonomic knowledge is the basis for performing both kinds of decomposition.

4.2. The decomposition policies

Table 1 summarizes the decomposition policies that we are considering. Because the two kinds of decomposition (i.e., requirements-based decomposition and constraints-splitting decomposition) are two orthogonal dimensions, a decomposition policy is defined by selecting a value for each dimension.

Decomposition policies

In requirements-based decomposition, there are three distinct choices:

1. no_dist, if no distinction is performed between the (sub)components possibly critical for the requirements satisfaction and those that have no influence on it (thus, no requirements-based decomposition is actually performed);
2. after, if the (sub)components possibly critical for the requirements satisfaction are kept distinct from the other ones; both set of (sub)components are taken into consideration, but the noncritical (sub)components are considered after all the critical ones;
3. never, as in the previous case, but only the set of possibly critical (sub)components is considered; the other ones are never taken into consideration.

For the constraints-splitting decomposition there are only two possible values: no, meaning that no constraints-splitting decomposition is performed, and yes meaning the opposite. The latter type of decomposition works only on the set of constraints directly associated with the target object (i.e. the one that should be configured).⁶

In Table 1, each policy that we take into consideration is identified by a number. The policies for which Requirements_based ≠ never (i.e., policies 1, 2, and 3) configure the whole product. The other ones (i.e., 4 and 5) leave out of the configuration those components that are recognized to have no influence on the possibility of meeting the requirements.

The entry with the dash corresponds to a combination that we do not consider. In fact, whenever we do not make the “coarser” distinction between the components (possibly) related to the requirements and the other ones, it also seems reasonable to not perform the “more detailed” analysis on the interaction among constraints.

6.1. The configuration algorithm

The configuration mechanisms consist of the mainProc procedure (Fig. 4), the (recursive) configure procedure (Fig. 5), and the insertDirectComponents procedure (Fig. 6).

A configuration algorithm: mainProc procedure.

A configuration algorithm: configure procedure.

A configuration algorithm: insertDirectComponents procedure.

The search for a configuration progressively extends and modifies a tentative configuration. The tentative configuration that the configurator is working on is denoted by T = 〈COMPS_T,INST_SLOTS_T〉.

The mainProc procedure (Fig. 4) accepts as input a configuration problem CP = 〈CM,C,REQS〉 (Definition 1) and returns either a partial configuration T solving CP according to Definition 7 or the FAILURE message (in case the configuration problem does not admit any solution).

At the beginning, the tentative configuration T contains only a component c such that class(T, c) = C, representing the target object.

The set CONSTRS_REQS(c) of the constraints that are relevant to the target object and bound to the requirements is then computed. According to Definition 6, this set contains all the requirements plus those constrains stated in the conceptual model for the class C of the target object that may interact with the requirements during the configuration process. Because the requirements-based decomposition is adopted, all the other constraints (if any) associated with class C do not interact with the requirements and are therefore not taken into consideration.

The constraints-splitting decomposition is adopted, too; therefore, CONSTRS_REQS(c) is partitioned into a set of classes of bound constraints by means of the bound relation

(Definition 5).

is the quotient set (i.e., the set of the equivalence classes) induced in the set CONSTRS_REQS(c) by the relation

; thus, it contains all the above-mentioned classes of bound constraints. CLASSES_CON is initialized to this quotient set.

Every class of constraints in CLASSES_CON corresponds to a subproblem, and each subproblem can be solved independently of each other.

In the WHILE loop, the subproblems are solved sequentially. At each execution of the WHILE body, one class of constraints c_constrs(T, c) ∈ CLASSES_CON is activated for the target object c and the configure procedure is invoked to extend T by taking into consideration only the current active constraints in c_constrs(T, c) and the components and subcomponents of c possibly critical for the satisfaction of these constraints. [The other (sub)components do not play any role in the subproblem relevant to the current class of constraints c_constrs(T, c).] If any one of these subproblems fails to admit a solution, the whole problem has no solution and a global FAILURE message is returned. Otherwise, the configuration is progressively extended until all the subproblems are solved. The solution is then returned.

If CLASSES_CON contains more than one class, it means that the main problem has actually been split into a set of independent subproblems (in this case, the main problem is said to be constraints-splitting decomposable). In this version of the algorithm, the subproblems are sequentially solved. However, a parallel version of the algorithm could be implemented that sends these subproblems to a pool of configurators working in parallel. The experiments discussed in Section 7 were performed with the sequential version of the algorithm. Nevertheless, the constraints-splitting decomposition strategy proved to also be effective within such an algorithm.

Each call to configure(T,CM,c) (Fig. 5) corresponds to a request to extend the configuration of the complex component c ∈ COMPS_T by taking into consideration the tentative configuration T, the CM, and the the current active constraints in c_constrs(T, c). In response, configure(T,CM,c) returns either a tentative configuration in which T has been successfully extended or the FAILURE message, indicating that no configuration exists for component c that satisfies the constraints in c_constrs(T, c).

This procedure first extends T by inserting into the tentative configuration a set of new direct components of c. Each time a direct complex component of c is inserted into the configuration, it is added to the set dirComplComps(T, c). In a second phase, configure is recursively invoked one time for each component in this set.

At the beginning, no direct component of c exists yet, thus dirComplComps(T, c) is empty. No other components of c but those possibly critical for the satisfaction of the set c_constrs(T, c) of current active constraints have to be considered (in fact, the other components of c are not involved in the subproblem that is being solved). Therefore, the set PART_SLOTS of the partonomic slots that are going to be considered for (partially) configuring the component c contains only those partonomic slots of component c that are mentioned in the active constraints c_constrs(T, c).

The direct components of c are inserted into the configuration by insertDirectComponents procedure (Fig. 6).

Whenever insertDirectComponents procedure fails, a backtracking occurs that revises a previous choice. If no previous choice can be revised, configure fails.⁷

The WHILE loop in configure procedure extracts one of these components c′ at a time; the set of active constraints c_constrs(T, c′) for c′ is computed and the process is repeated to configure that portion of c′ possibly critical for the satisfaction of this new set of active constraints.

This set is computed as follows:

where I_Constrs(T,CM,c′) is the set of constraints that c′ “inherits” from the component c, which it is direct part of, namely,

(i.e., it is the set of constraints in c_constrs(T, c) containing some partonomic slot relevant to the component c′). L_Constrs(T,CM,c′) is the set of constraints associated with class(T, c′) that are bound in c′ to some constraint belonging to I_Constrs(T,CM), namely,

The other constraints possibly associated with class(c_comp(T)) are not involved in the subproblem that is being solved; thus, they are not considered.

When all the direct complex components of c contained in dirComplComps are successfully (partially) configured, configure returns the extended configuration. If any one of such complex components does not admit any configuration that satisfy the set of active constraints, the FAILURE message is returned.

In regard to the insertDirectComponents procedure (Fig. 6), it accepts as input a tentative configuration T, the CM, a complex component c ∈ COMPS_T, and a set PART_SLOTS of partonomic slots relevant to class(T, c). It returns either a tentative configuration in which the configuration of the component c has been extended by considering only partonomic slots in PART_SLOTS or the FAILURE message.

This procedure performs the two basic kinds of choices of the configuration process:

1. given a partonomic slot p ∈ PART_SLOTS, it chooses its cardinality, that is, it chooses the number n of direct components x₁,…, x_n of the component c, through the whole–part relation represented by p;
2. it chooses the type of each such component x_i (i.e., the value of class(T, x_i) (i = 1,…, n)).

In performing these choices, it must respect both the partotaxonomic description (i.e., the number and the value restrictions of p) and the active constraints in c_constrs(T, c). If either the cardinality of p or the type for any x_i cannot be chosen without violating any constraint in c_constrs(T, c), a FAILURE message is returned to configure procedure, which manages the backtracking. Otherwise, the tentative configuration T is extended by both adding the set X = {x₁,…, x_n} of new components to COMPS_T and adding the equality 〈p(c) = X〉 to INST_SLOTS_T. If x₁,…, x_n are complex components, they are inserted into dirComplComps(T, c). After the two above-mentioned choices have been successfully made for p, all the satisfied constraints are removed from the tentative configuration T. (In fact, any subsequent extension of T cannot change their truth value.) Whenever a constraint is removed from c_constrs(T, c), it can be that some slots in PART_SLOTS will no longer occur in any active constraint for the component c. These slots need to be removed from PART_SLOTS, because they are no longer critical for the satisfaction of the constraints in c_constrs(T, c).

It is worth noting that each component in X = {x₁,…, x_n} is a new one, that is, it is different from the other components in COMPS_T: this assures that the exclusiveness assumption on parts (Assumption 1) actually holds. Moreover, whenever an atomic component is inserted into a configuration, the values for its properties are also stated in the configuration.

6.2. A configuration example

In this section we briefly describe the behavior of the configuration algorithm by means of an example in which the configurator builds a partial configuration (according to Definition 7) by adopting decomposition policy 5 (Table 1). Because the backtracking mechanism is out of the scope of this paper, we discuss a simple example in which the configurator is able to go straight to the solution without entering any failure path in the search space.

Let us suppose that we want to configure an advanced application PC (described in the PC conceptual model PC_CM shown in Figs. 1 and 2) meeting the requirements REQS listed in Figure 3. The procedure mainProc(PC_CM,Advanced Appl. PC,REQS) is invoked. The process starts with a tentative configuration T₁ containing only the component aapc1 representing the target object (thus class(T,aapc1) = Advanced Appl. PC). The set of constraints relevant to aapc1 is CONSTRS(aapc1) = {co1,co2,co3,co4,co5,co6,co7,req1,req2,req3} (see Definition 4). All these constraints are bound to the requirements; thus, CONSTRS_REQS(aapc1) = {co1,co2,co3,co4,co5,co6,co7,req1,req2,req3} (see Definition 6). Because policy 5 is adopted, only the components and the subcomponents of aapc1 possibly critical for the satisfaction of these constraints will be considered during the configuration process (requirements-based decomposition). Moreover, constraints-splitting decomposition takes place and thus according to the bound relation (Definition 5), CONSTRS_REQS(aapc1) is partitioned into the set of equivalence classes

It is easy to see, for instance, that req1 is directly bound in aapc1 to co1, co2, co3, and co7, because all these constraints contain the partonomic slot has_m of class(T,aapc1) = Advanced Appl. PC; moreover, it is bound in aapc1 by transitivity to co6, in fact req1 is directly bound in aapc1 to co1, which is directly bound in aapc1 to co6 (because they both contain the partonomic slot has_hd of Advanced Appl. PC class). Moreover, req3 contains only the partonomic slot has_cdt, which does not occur in any other constraint; therefore, req3 is not bound to any constraint (except itself).

CLASSES_CON entails a set of independent subproblems (one subproblem for each equivalence class of constraints). The configurator solves them sequentially. Let us suppose that it starts with the subproblem corresponding to the set {req1,co1,co2,co3,co6,co7}.⁸

A configuration example: the first subproblem.

At the beginning the set of current active constraints for the target object is c_constrs(T₁,aapc1) = {req1,co1,co2,co3,co6,co7}. The set of partonomic slots that have to be considered are those ones in Advanced Appl. PC class that occur in some active constraints, namely, PART_SLOTS = {has_hd,has_m,has_cdr,has_cdw}. [See the tentative configuration T₁ in Fig. 7(a)].

After the direct components of aapc1 relevant to these slots have been inserted into the configuration, the situation is as depicted in Figure 7(b): no more direct parts of aapc1 need to be inserted for solving the current subproblem and the constraint co6 is satisfied in T₂, thus it is removed from the set of active constraints.

The motherboard mb1 is a direct complex component of aapc1 (i.e., dirComplComps(T₂,aapc1) = {mb1}), therefore it must be (partially) configured. mb1 inherits from aapc1 the set I_constrs(T₃,PC_CM,mb1) = {req1,co1,co2,co3,co7} of constraints (because all these constraints contain partonomic slots relevant to mb1). These constraints activate the set of local constraints L_constrs(T₃,PC_CM,mb1) = {co8} (in fact, req1

co8), thus c_constrs(T₃,mb1) = {req1,co1,co2,co3,co7,co8}. The set of partonomic slots of Motherboard class occurring in these constraints is {has_mpcb,has_cs,has_cpu} [see Fig. 7(c)].

It is worth noting that the initial set c_constrs(T₃,mb1) of active constraints corresponds to the set CONSTRS_REQS(mb1) (see Definition 6). This is true in general when requirements-based decomposition is adopted. In fact, in such a case, for the target object only the constraints bound to the requirements are activated, therefore, the set I_constrs(T,CM,c) for each direct component c of the target object contains only constraints bound to the requirements; each constraint in L_constrs(T,CM,c) is bound to a constraint in I_constrs(T,CM,c) by definition, thus it is bound to the requirements, too. This reasoning can be recursively repeated for each subcomponent.

After the main printed circuit board of type SCSI mpcb_scsi1 is inserted [Fig. 7(d)], the constraints req1, co1, co2, and co3 are satisfied in T₄; thus, they are deleted from the tentative configuration. The configuration process then considers has_cs and has_cpu slots: two CPUs (cpu1 and cpu2) and no SCSI controller are inserted into the configuration [Fig. 7(e)]. Configuration T₅ contains no active constraints (i.e., both the set {req1,co1,co2,co3,co6,co7} of the constraints initially active and constraint co8, activated by the first ones in the mb1 component, are satisfied in T₅); therefore, T₅ is a partial configuration solving the first subproblem.

The second subproblem corresponds to the set of constraints {req2,co4,co5}. These become the initial active constraints for the target object, as shown in Figure 8(a). The configurator solves the second subproblem by taking into consideration only the slots has_asw and has_os. Configuration T₇ is a partial configuration solving both the first and the second subproblems. Because there is no interaction between these two subproblems, the portion of the tentative configuration relevant to the first one (the one with dashed arcs and grey labels and nodes in T₆ and T₇) is not involved in any way in the resolution of the second one.

A configuration example: the second subproblem.

The third subproblem, corresponding to constraint req3 (Fig. 9), is solved by introducing a CD tower (the component cdt1 in T₉) into the configuration, where T₉ is a partial configuration solving the main problem according to Definition 7. Because decomposition policy 5 is adopted, the configuration process stops at this point. It is worth noting that some components and subcomponents of an advanced application PC have not been considered during the configuration process, because they are not critical for the satisfaction of the requirements (i.e., keyboard, case, video card, modem, etc.).

A configuration example: the third problem.

Figure 10 shows an example where the user incrementally specifies her/his requirements. In fact, after stating the requirements listed in Figure 3, she/he might put some additional requirements on the components and subcomponents relevant to partonomic slots not specified in the partial configuration T₉. In particular, requirements REQS′ in Figure 10 require that the CD tower cdt1 contains two CD readers and two CD writers. In order to satisfy the user's request, the configure procedure has to be invoked to configure component cdt1 given the set of constraints relevant to that component. The invocation of configure has the effect of extending T₉ by means of a solution to the configuration problem CP_cdt1 = 〈PC_CM,CD Tower,REQS′〉.

A configuration example: configuring the CD tower component.

The partial configuration T₁₀ reported in Figure 10 is a solution because it meets all the requirements REQS ∪ REQS′.

8.1. Configuration ontologies

The relevant concepts for the various configuration tasks have been described in several works (Mittal and Frayman, 1989; Mailharro, 1998; Soininen et al., 1998; Felfernig et al., 2000; Soininen, 2000). We have defined the decomposition mechanisms in the

framework in which many of these concepts can be expressed. Besides those concepts explicitly mentioned in Section 2, it is worth discussing four other concepts occurring in configuration ontologies.

8.1.1. Resources

In the

framework, both resource satisfaction and resource balancing can be expressed and actually have been exploited to model the computer system configuration domain that we used in experiments. For instance, the RAM memory slots produce a certain amount of memory capacity, and each software application needs a certain amount of memory. These properties are represented with the descriptive slots RAM_mem and Sw_mem associated with the RAM and Software_Application classes, respectively, and taking values in a set of positive numeric values. The constraint true → (max({〈has_asw,Sw_mem〉})) ≤ (Σ({〈has_m,has_ram,RAM_mem〉})), associated with the PC class, states that the memory capacity resource must be satisfied.

⁹

For brevity, here we do not consider the memory consumption relevant to the operating system.

For the sake of simplicity and in order to keep the example in Section 6.2 small enough, this constraint and the descriptive slots occurring in it are not represented in Figures 1 and 2.

In the

framework every constraint is always associated with a class of complex objects; moreover, in each constraint, the slot chains explicitly refer to a set of components of individuals of the class with which the constraint is associated. This allows the representation of contexts (i.e., sets of components) in which resources must be satisfied or balanced.

8.1.2 Shared components

Another issue that it is worth discussing is that of shared components. As stated in Section 3, in the present work we assume that partonomic relations are exclusive (Assumption 1). This assumption is quite natural in several configuration domains. However, in some cases shared components must be represented.

We use an example to briefly discuss some issues relevant to what can be retained and what should be modified in the framework in order to handle shared components.

Let us consider, for example, the conceptual model depicted in Figure 11, where a hydraulic system is composed of two subsystems having two tanks as their part. We suppose that the tanks can be shared by the two subsystems. If we require the first subsystem to have only TypeA tanks

and the second at least one one TypeB tank,

we may wonder if the decomposition strategies can be applied to this situation.

A portion of a hydraulic system conceptual model.

The conceptual model states only that the tanks can be shared by the two subsystems, but not that they must be shared. If a valid configuration exists in which (at least) one of the two tanks is shared, then a valid configuration in which each subsystem has its own tanks also exists and it can be constructed by separately configuring the two subsystems; conversely, if both the subsystems can be separately configured, a valid configuration of the whole system does exist. Therefore, the subproblems of configuring the two subsystems are independent to a certain extent, because the main problem admits a solution if and only if the two subproblems are solvable separately.

According to the bound relation (Definition 5), req1 and req2 (associated with the HydraulicSystem class) are not bound; therefore, this relation is still able to recognize such an independence.

However, if some components can be shared, it is often convenient to produce configurations in which they are actually shared. For example, a hydraulic system with three tanks (two TypeA and one TypeB tanks, in which one of the TypeA tanks is shared by the two subsytems) could be preferred to a system in which four tanks are present. To produce such configurations, the procedure in Figure 6 has to be slightly modified. This procedure always inserts a set of new components each time a cardinality greater than zero is chosen for a partonomic slot. To handle shared components, this procedure should be given the possibility of using components already present in the tentative configuration it is working on each time a shared partonomic relation is considered.

To express the situations in which the components must be shared,

has to be extended with a set of new predicates. For instance, we could model the fact that the tanks must be shared by the two subsystems by means of the constraint [shared]true → shared(〈has_sub1,has_tank1〉,〈has_sub2,has_tank2〉). In this case, the two requirements req1 and req2 cannot be considered separately. The bound relation still works, because it places req1, req2, and shared in a same class of bound constraints.

8.1.3. Functions

Mittal and Frayman (1989) present a model of configuration tasks in which functional architectures play a basic role. The configuration algorithms that we presented here does not rely on functional architectures. However,

provides the means of describing a set of functions in order to express some typical classes of requirements. The

models contain, for each function, a mapping into a set of

constraints. These mappings are used to automatically produce the requirements in a

constraint-based form. The user can further specify her requirements by directly adding a set of constraints to those derived by the functions that she selected (see Magro & Torasso, 2001b).

8.1.4. Connections

In some configuration tasks also the connections (either physical or logical) between components represent an important piece of knowledge. These connections are usually represented by means of ports. In our framework this knowledge cannot be explicitly expressed. To model the computer system domain we used in experiments, a set of

constraints has be derived from this knowledge. For instance, if, in each complex object of class C, the components of, say, type TypeA need to be connected to components of type TypeB, a set of

constraints is added to the conceptual description of C. These constraints state that in any individual of C, the number of TypeB components must be greater than or equal to the number of TypeA components.

To model and reason in those domains in which more complex constraints relevant to the connections have to be represented,

framework should be extended.

8.2. The open world semantics and the justification of configuration elements issues

As pointed out by some researchers, the classical open world semantics of description logics and of classical propositional or predicate logic is not suitable for configuration task (see, for example, Weida, 1996; Soininen, 2000).

For instance, given a consistent DL knowledge base Σ = 〈TBox,ABox〉, under open world semantics, a particular individual description d may be consistent with Σ (i.e. Σ′ = 〈TBox,ABox ∪ {d}〉 may be satisfiable), even if d contains some concept names that do not occur in Σ. However, in a configuration task, where Σ is a conceptual model and individuals are intended to represent configuration elements, such individual descriptions should be forbidden. In fact, it is assumed that all basic concepts needed to express configurations are explicitly mentioned in the conceptual model. Moreover, open world semantics would allow fully specified individuals to restrict more roles than any primitive or defined concept of Σ that they instantiate. This means that no basic concept in Σ is able to account for all the properties of such individuals. Again, in a configuration task, these situations should not occur. In fact, it is assumed that the conceptual model does explicitly contain the description of all the types of elements that can occur in configurations. In order to cope with these issues, Weida (1996) formalized the concept of the closed terminology assumption (CTA).

Similar problems also occur when formalizing a configuration conceptual model as a logic theory. In fact, let T be a first-order theory describing a configuration domain, in which all the objects that can appear in a configuration are explicitly represented (by means of constants). If we think of a configuration as a model for T,¹⁰

Our framework is close to description logic based approaches to configuration and basically follows the CTA stated in Weida (1996). In fact, the application does not add any new concept to the conceptual model during problem solving. Moreover, we distinguish between abstract classes (nonleaf classes in

taxonomies) and concrete classes (the leaves in

taxonomies). In each tentative configuration (thus, in both complete and partial configurations), each component (either complex or atomic) instantiates one (and only one) concrete class (Definition 2, item 1). Besides this, every component occurring in any complete configuration is “finished” in the sense specified in Weida (1996). In fact, if a configuration contains the equality 〈p(c) = X〉, p is a slot (possibly inherited) of the (concrete) class class(T,c) instantiated by the component c (Definition 2, item 3) and such an equality expresses a property respecting the restrictions for slot p stated in the conceptual description of class(c) (i.e., the equality is justified by the conceptual description of class(c), Definition 2, item 3). Moreover, each complete configuration specifies every slot p ∈ class(c), for each component c occurring in the configuration (Definition 3, item 1) and all the constraints (possibly inherited) associated with class(c) in the conceptual model are satisfied by c (Definition 3, item 2).

The case of partial configurations (Definition 7) is slightly different, because for them it is not requested that every component c specify all the slots relevant to the class that it instantiates (which is still a concrete class). However, each partial configuration can be extended to a set of complete configurations (Property 2). Thus, each partial configuration represents a common subconfiguration of a set of finished configurations.

Differently from Weida's approach, the framework discussed in this paper does not exploit CTA to progressively specify the type of components. In fact, configuration problem definition (Definition 1) assumes that the concrete class instantiated by the target object is known a priori. Furthermore, as soon as a component is inserted into a tentative configuration during problem solving, the application chooses the concrete class that such component instantiates. To make such choices the application makes use of a set of focusing mechanisms able to rule out a set of impossible classes (Magro & Torasso, 2001a). These choices may be retracted (by means of a backtracking mechanism) as soon as the configurator reaches a failure state in the search space.

Our framework does not require that the components that can be part of a configuration be explicitly listed in the conceptual model, because the application creates them dynamically. Thus, the approach does not commit to Herbrand models. However, each element occurring in a configuration is justified. Indeed, in each configuration there is exaclty one component representing the target object (Definition 2, item 2) and, as said above, each relation occurring in a complete configuration is justified by the description of the basic concepts in the conceptual model. A partonomic relation needs an additional justification for being stated in a partial configuration, because only the properties possibly critical for satisfying the requirements can be specified in such configurations (Definition 7). (It is worth noting that the requirements are expressed in the vocabulary of the conceptual model: see Definition 1, item 3.)

As in Soininen (2000) but different than Mittal and Falkenhainer (1990), no subset minimality condition is imposed on configurations.