Introduction

Feature models (FMs) are an intuitive way of representing commonality and variability properties of complex systems [1,2,3]. Specifically, in scenarios where companies are operating on a global basis, integration scenarios can arise where country or region-specific feature models have to be integrated to support a more globalized variability management. Think about a scenario where a car producer operating in the European and the US market decides to centralize variability management activities. On the technical (feature model) level, formerly region-or country-specific models have to be integrated in a systematic fashion in one centralized variability model. In this paper, we present an algorithmic approach to integrate (merge) two different ("old") feature models (e.g., the feature model 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 could denote a local feature model of a US car provider) in a semanticspreserving way where the solution (configuration) spaces of the local feature models are "transferred" to an integrated feature model which reflects exactly the same set of solutions: solutions(𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 ) ∪ solutions(𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 ) equals solutions(𝐹 𝑀 𝑛𝑒𝑤 ). In this context, we assume that 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 and 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 represent the local feature models of a globally operating car manufacturer and 𝐹 𝑀 𝑛𝑒𝑤 is the result of merging the local feature models (and related knowledge bases).

Knowledge base merging has been approached in various ways. For example, the alignment of knowledge bases is based on the idea of knowledge base integration by identifying concepts in different knowledge bases that represent the same underlying concept but are represented by different names. Knowledge base alignment is specifically performed in situations where numerous knowledge bases have to be integrated [4]. Knowledge base merging is based on a set of predefined merging operations [5,6], for example, consistency-based merging follows the goal of deriving a maximally consistent set of logical formulae that represent the union of the formulae of the original knowledge bases. Such integrations basically follow the idea of generating maximally satisfiable subsets (of rules) [7], i.e., sets that cannot be further extended (with original rules) without making the resulting knowledge base inconsistent.

Feature model merging [8,9,10,11,12,13] is also in the line of the ideas of the previously mentioned approaches. Feature models can become quite large and complex [14], which makes the development and maintenance of single models a challenging task. Following the idea of separation of concerns [15], Aydin et al. [16] propose an approach to construct stakeholder-individual feature models which are then merged for the purpose of providing a unified view on the feature space. In the context Figure 1: Example basic feature model from the automotive domain where type refers to the car type which can be (lim)ousine, (com)bi, (cit)y, and suv. Furthermore, the car color can be (b)lack or (w)hite, the engine can be 1l, 1.5l, and 2l. Fuel can be (d)iesel, (e)lectric, (g)asoline, and (h)ybrid, representing the supported types of fuel. Finally, a coupling unit is regarded as an optional feature.

of such a merging process, different "issues" have to be resolved, for example, some stakeholders regard a feature as optional while others think it should be mandatory. Furthermore, depending on the given scenario, feature naming can also become an issue if no "maximum feature set" has been specified ahead of the merging process. For such scenarios, Aydin et al. [16] propose a standard merging procedure that is able to generate a reference feature model, which then serves as a basis for further discussions and decision-making.

With a similar motivation, i.e., making large feature model development easier, Acher et al. [8], propose a set of integration operations for "local" feature models which basically support the goal of integrating local models into a global one. In this context, the authors also specify feature model relationships on a logical basis, for example, one feature model 𝐹 𝑀1 is the specialization of a feature model 𝐹 𝑀2 if the configuration space of 𝐹 𝑀1 is a subset of the configuration space of 𝐹 𝑀2 -see also Thüm et al. [17,3]. The authors also introduce a merge operation where the introduced semantics does not support semantics preservation but requires that the result of the merging operation is equivalent or a superset of the solution (configuration) spaces of the two original feature models, i.e., solutions(𝐹 𝑀1) ∪ solutions(𝐹 𝑀2) ⊆ solutions(merge(𝐹 𝑀1, 𝐹 𝑀2)). Such a semantics of a merge operation is also considered in the contributions of Broek et al. [10], Carbonell et al. [11], and She et al. [18].

Following the union merge semantics introduced in Schobbens et al. [12], the feature model merging approach presented in this paper focuses on the preservation of the semantics of the source feature models used as an input for the merging procedure. In other words, it supports a semantics-preserving merging where the configuration space of the feature model resulting from a merging operation is exactly the union of the configuration spaces of the original feature models: solutions(𝐹 𝑀1) ∪ solutions(𝐹 𝑀2) = solutions(merge(𝐹 𝑀1, 𝐹 𝑀2)) which is more restrictive compared to the union semantics introduced by Acher et al. [8].

Compared to related work on feature model semantics preservation [10,13], our approach provides a generalization in terms of (1) supporting arbitrary constraint types (in contrast to specific feature model related constraints such as requires and incompatible) and ( 2) taking into account redundancy-freeness in terms of assuring that redundant constraints as a result of a merging procedure can be detected and eliminated from the feature model. In our approach, the original feature models and the resulting feature model (result of the merging operation) are represented as constraint satisfaction problems (CSPs) [19]. To demonstrate the applicability of our approach, we present the results of a corresponding performance analysis.

The remainder of this paper is structured as follows. In Section 2, we introduce a working example consisting of simplified feature models from the automotive domain.

Using this example, we discuss our algorithmic approach to semantics-preserving feature model merging in Section 3. To show the performance of our approach, we report the results of a corresponding performance evaluation (see Section 4). Finally, we conclude the paper with a discussion of existing threats to validity (Section 5) and a corresponding summary of the contributions of this paper (Section 6).

Example Scenario

We now introduce a simplified example of a feature model merging scenario. Our basic underlying assumption is that the original feature models are consistent, i.e., it is possible that at least one solution can be identified and also that the feature set of the original models are the same, i.e., the differences are primarily observable in terms of the constraints defined in the individual models. In our example from the automotive domain, the original feature models are denoted as 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 (the original US feature model) and 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 which denotes the original European Union feature model. In this context, we assume that these feature models are consistent, i.e., non-void [20], meaning that at least one configuration can be identified for each of those models. Finally, we denote the resulting model (the merging result) as 𝐹 𝑀 𝑛𝑒𝑤 .

Figure 1 represents the basic feature model (i.e., configuration model [21]) that in the following will be used as a working example. This feature model represents all relevant features that can be used to define variability knowledge, i.e., we assume that the same set of features is used to represent variability knowledge in 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 and 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 . Differences in the two variability models can exist in terms of constraints representing individual configuration spaces. In the following, we specify constraints that define the properties of the two original feature models 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 and 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 represented in terms of individual constraint satisfaction problems (CSPs) representing the European and the US feature model [19]. 1These CSPs are defined in terms of variables with corresponding domain definitions (e.g., type(lim,com,sit,suv) denotes the variable type with the allowed values) and a corresponding set of constraints [22].

Note that region is an additional variable representing a contextual information, i.e., to which region a generated configuration belongs to. Contexts follow the idea of separation of concerns [15] which supports a kind of decentralized modeling [23]. For example, using the context variable region, the constraint 𝑐 1𝑢𝑠 ∶ 𝑓 𝑢𝑒𝑙 ≠ ℎ would be expressed as 𝑐 1𝑢𝑠 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝑈 𝑆 → 𝑓 𝑢𝑒𝑙 ≠ ℎ explicitly indicating that this constraint has to hold for configurations generated on the basis of the 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 CSP.

∶ 𝑓 𝑢𝑒𝑙 ≠ 𝑔, 𝑐 2𝑒𝑢 ∶ 𝑓 𝑢𝑒𝑙 = 𝑒 → 𝑐𝑜𝑢𝑝𝑙𝑖𝑛𝑔 = 𝑛𝑜, 𝑐 3𝑒𝑢 ∶ 𝑓 𝑢𝑒𝑙 = 𝑑 → 𝑡𝑦𝑝𝑒 ≠ 𝑐𝑖𝑡}

To show the differences between the feature models 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 and 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 , Table 1 provides an overview of the number of solutions supported by the original (regionspecific) feature models.

Merging Feature Models

In order to be able to merge the two original feature models (𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 and 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 ) in a semantics-preserving are the same as those of the original ones (assuming a corresponding context setting, e.g., 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝐸𝑈). Following this argumentation, solutions(𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 ) ∪ solutions(𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 ) = solutions(𝐹 𝑀𝐸𝑈 ′ 𝑜𝑙𝑑 ∪ 𝐹 𝑀𝑈 𝑆 ′ 𝑜𝑙𝑑 ) which supports our goal of achieving a semanticspreserving merging of the original knowledge bases (see Table 1).

∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝑈 𝑆 → (𝑓 𝑢𝑒𝑙 ≠ ℎ), 𝑐 ′ 2𝑢𝑠 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝑈 𝑆 → (𝑓 𝑢𝑒𝑙 = 𝑒 → 𝑐𝑜𝑢𝑝𝑙𝑖𝑛𝑔 = 𝑛𝑜), 𝑐 ′ 3𝑢𝑠 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝑈 𝑆 → (𝑓 𝑢𝑒𝑙 = 𝑑 → 𝑐𝑜𝑙𝑜𝑟 = 𝑏)} • 𝐹 𝑀𝐸𝑈

The algorithmic approach to support such a semanticspreserving merging is shown in Algorithm 1 (MergeFM) which itself is a Flama [24] prototype implementation. In a first step (starting with line 6 of MergeFM), those constraints in the contextualized original knowledge bases (in Algorithm 1 denoted as 𝐹 𝑀 ′ 1 and 𝐹 𝑀 ′ 2 ) can be decontextualized where such a contextualization is not needed (𝑐 is a decontextualized version of 𝑐 ′ ): if ¬𝑐 is consistent with 𝐹 𝑀 ′ 1 ∪ 𝐹 𝑀 ′ 2 , there (obviously) exist solutions supporting ¬𝑐. In such a case, the constraint 𝑐 must be added in a contextualized fashion to the resulting knowledge base 𝐹 𝑀, since some feature model configuration (in the other knowledge base) supports ¬𝑐. If ¬𝑐 is inconsistent with 𝐹 𝑀 ′ 1 ∪ 𝐹 𝑀 ′ 2 , 𝑐 can be added in decontextualized fashion to the resulting knowledge base 𝐹 𝑀. In a second step (starting with line 14 of Algorithm 1), each constraint of the resulting knowledge base has to be checked for redundancy: in a logical sense, a constraint 𝑐 can be regarded as redundant if 𝐹 𝑀 −{𝑐} is inconsistent with ¬𝑐 which means that the constraint does not reduce the solution space of FM and thus logically follows from the constraints in FM (and can be deleted from the constraints in FM). When applying Algorithm 1 to 𝐹 𝑀𝑈 𝑆 𝑜𝑙𝑑 and 𝐹 𝑀𝐸𝑈 𝑜𝑙𝑑 , the resulting knowledge base 𝐹 𝑀 𝑛𝑒𝑤 looks like as follows.

Algorithm 1 MergeFM(𝐹 𝑀 ′ 1 , 𝐹 𝑀 ′ 2 )∶ 𝐹 𝑀 1: {𝐹 𝑀 ′ 1 , 𝐹 𝑀

In the resulting knowledge base, the constraint 𝑐 ′ 2𝑢𝑠 has been decontextualized. Also, as a result of applying Algorithm 1, constraint 𝑐 ′ 2𝑒𝑢 can be regarded as redundant and thus can be deleted from 𝐹 𝑀 𝑛𝑒𝑤 . 3 • 𝐹 𝑀 𝑛𝑒𝑤 : {region(US,EU), type (lim,com,cit,suv), color(b,w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes,no),

𝑐 ′ 1𝑢𝑠 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝑈 𝑆 → (𝑓 𝑢𝑒𝑙 ≠ ℎ), 𝑐 ′ 2𝑢𝑠 ∶ 𝑓 𝑢𝑒𝑙 = 𝑒 → 𝑐𝑜𝑢𝑝𝑙𝑖𝑛𝑔 = 𝑛𝑜, 𝑐 ′ 3𝑢𝑠 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 =

3 Alternatively, 𝑐 ′ 2𝑢𝑠 could be deleted as a redundant constraint (instead of 𝑐 ′ 2𝑒𝑢 ).

𝑈 𝑆 → (𝑓 𝑢𝑒𝑙 = 𝑑→ 𝑐𝑜𝑙𝑜𝑟 = 𝑏), 𝑐 ′ 1𝑒𝑢 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝐸𝑈 → (𝑓 𝑢𝑒𝑙 ≠ 𝑔), 𝑐 ′ 3𝑒𝑢 ∶ 𝑟𝑒𝑔𝑖𝑜𝑛 = 𝐸𝑈 → (𝑓 𝑢𝑒𝑙 = 𝑑 → 𝑡𝑦𝑝𝑒 ≠ 𝑐𝑖𝑡)}

On the algorithmic level, the resulting knowledge base 𝐹 𝑀 𝑛𝑒𝑤 is represented in terms of a constraint satisfaction problem. One possibility of representing the integrated knowledge base as the resulting integrated feature model is depicted in Figure 2.

Performance Evaluation

In this section, we discuss the results of an initial performance analysis we have conducted to evaluate MergeFM (Algorithm 1) 4 . For this analysis, we applied 8 real-world variability models with varying sizes collected from the S.P.L.O.T. feature model repository [25] and the Diverso Lab's benchmark5 [26]. Table 4 shows the characteristics of these models (denoted as 𝜙). In order to generate "tobe-merged" feature models (𝐹 𝑀 ′ 1 and 𝐹 𝑀 ′ 2 ) with different shares of contextualized constraints from individual 𝜙s, we determined the needed number of relationships or cross-tree constraints. We then modified these selected relationships/cross-tree constraints by changing their type, for example, changing mandatory to optional, changing alternative to or, or changing requires to excludes. The resulting models (𝐹 𝑀 ′ 1 ∪ 𝐹 𝑀 ′ 2 = 𝐹 𝑀 ′ ) are represented as constraint satisfaction problems [19] that differ individually in terms of the number of constraints (#constraints) and the degree of contextualization (expressed as percentages in Tables 2 and 3). In order to take into account deviations in time measurements, we repeated each experimental setting 10 times where in each repetition cycle the constraints in the individual (contextualized) knowledge bases 𝐹 𝑀 ′ were ordered randomly. All analyses have been conducted with an Apple M1 Pro (8 cores) computer with 16-GB RAM. For evaluation purposes, we used the Choco solver 6 to perform the needed consistency checks.

The number of consistency checks needed for decontextualization is linear in terms of the number of constraints in 𝐹 𝑀 ′ . A performance evaluation of MergeFM with different knowledge base sizes and degrees of contextualized constraints in 𝐹 𝑀 is depicted in Table 2. In MergeFM, the runtime (measured in terms of milliseconds needed by the constraint solver 7 to find a solution) increases with the number of constraints in 𝐹 𝑀 ′ and decreases with the number of contextualized constraints in 𝐹 𝑀. The increase in efficiency can be explained by the fact that a higher degree of contextualization includes more situations where the inconsistency check in Line 7 (Algorithm 1) terminates earlier (a solution has been found) compared to situations where no solution could be found. In addition, Table 3 indicates that the performance of solution search does not differ depending on the degree of contextualization in the resulting knowledge base 𝐹 𝑀. Consequently, integrating individual variability models can trigger the following improvements. (1) Decontextualization in 𝐹 𝑀 can lead to less cognitive efforts when adapting / extending knowledge bases (due to a potentially lower number of constraints [27] and a lower degree of contextualization). ( 2) Reducing the overall number of constraints in 𝐹 𝑀 can also improve runtime performance of the resulting integrated knowledge base.

Threats to Validity

We are aware that our evaluation is in fact based on real-world feature models, however, synthesized variants thereof have been used for MergeFM evaluation purposes. Furthermore, our approach is based on the assumption that the "to-be-merged" feature models have the same set of features, i.e., we assume feature equivalence. In this context, we assume that in real-world scenarios further streamlining tasks (e.g., feature name alignment) have to be completed before MergeFM can be activated. Our basic assumption behind redundancy elimination and de-contextualization in MergeFM is that the understandability and maintainability of feature models can be improved -although already confirmed by related work [27], further research is needed to better understand major impact factors that make feature models (and underlying knowledge bases) easier to understand and maintainable.

Conclusions and Future Work

In this paper, we have introduced an approach to the consistency-based merging of variability models represented as constraint satisfaction problems. The approach helps to build semantics-preserving feature models in the sense that the solution spaces of the resulting knowledge bases (result of the merging process) correspond to the union of the solution spaces of the original knowledge bases. Such an approach can be useful in the mentioned integration scenario but as well in situations where different parts (representing different contexts) of a knowledge are developed in a de-centralized fashion and integrated thereafter. Besides the preservation of the original semantics, our approach also helps to make the resulting knowledge base compact in the sense of deleting redundant constraints and not needed contextual information. The runtime performance of our approach is shown on the basis of a first performance analysis with real-world feature models. Future work will include the evaluation of our concepts with further knowledge bases and the development of alternative merging algorithms with the goal to further improve runtime performance. Furthermore, we will evaluate different alternative feature model representations that help to represent contextualized constraints -one such representation has been discussed in this paper.