Large and globally operating enterprises can be confronted with situations where local variability models representing the constraints of individual countries and markets have to be integrated to support a centralized variability management. For example, a car producer operating in the U.S. as well as the European market, could be interested in having a centralized variability (feature) model representing the variability spaces of all supported markets. To achieve this goal, existing local feature models and the corresponding knowledge bases have to be integrated in such a way that the configuration spaces remain the same, for example, for the European market, we would request to support exactly the same set of car configurations that are supported by the corresponding local feature model. In this paper, we introduce an algorithmic approach that supports the merging of feature models in such a way that the semantics of the original feature models is preserved. We present our algorithm and the results of a solver performance analysis which has been conducted on the basis of real-world feature models.
CEUR
ceur-ws.org ). In this context, we assume that represent the local feature models
systems [1, 2, 3]. Specifically, in scenarios where com- knowledge bases).
Feature models (FMs) are an intuitive way of represento-f a globally operating car manufacturer and ing commonality and variability properties of complexresult of merging the local feature models (and related is the panies are operating on a global basis, integration sce-Knowledge base merging has been approached in varnarios can arise where country or region-specific featurieous ways. For example, thealignment of knowledge models have to be integrated to support a more globb-ases is based on the idea of knowledge base integraalized variability management. Think about a scenariotion by identifying concepts in diferent knowledge bases where a car producer operating in the European anthdat represent the same underlying concept but are repthe US market decides to centralize variability manager-esented by diferent names. Knowledge base alignment ment activities. On the technical (feature model) levelis, specifically performed in situations where numerous formerly region- or country-specific models have to beknowledge bases have to be integrated4][. Knowledge integrated in a systematic fashion in one centralized varbi-ase merging is based on a set of predefined merging ability model. In this paper, we present an algorithmiocperations 5[, 6], for example, consistency-based mergapproach to integrate (merge) two diferent (“old”) featureing follows the goal of deriving a maximally consistent models (e.g., the feature mode l
could denote a set of logical formulae that represent the union of the local feature model of a US car provider) in a semanticfos-rmulae of the original knowledge bases. Such integrapreserving way where the solution (configuration) spacestions basically follow the idea of generating maximally of the local feature models are “transferred” to an sina-tisfiable subsets (of rules) [7], i.e., sets that cannot be tegrated feature model which reflects exactly the samefurther extended (with original rules) without making set of solutions:solutions( ) ∪ solutions(
) the resulting knowledge base inconsistent. ConfWS’24: 26th International Workshop on Configuration, Sep 2–3, (T. N. T. Tran) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
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 comple1x4][, gle 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 of such a merging process, diferent “issues” have to be compared to the union semantics introduced by Acher resolved, for example, some stakeholders regard a featuerteal. [8]. as optional while others think it should be mandatory. Compared to related work on feature model semantics Furthermore, depending on the given scenario, featurepreservation1[0, 13], our approach provides a generalizanaming can also become an issue if no “maximum fea- tion in terms of (1) supporting arbitrary constraint types ture set” has been specified ahead of the merging process.(in contrast to specific feature model related constraints For such scenarios, Aydin et al1.6[] propose a standard such asrequires and incompatible) and (2) taking into merging procedure that is able to generate a referencaeccount redundancy-freeness in terms of assuring that feature model, which then serves as a basis for furtherredundant constraints as a result of a merging procedure discussions and decision-making. can be detected and eliminated from the feature model. In
With a similar motivation, i.e., making large featureour approach, the original feature models and the resultmodel development easier, Acher et al8.],[ propose a ing feature model (result of the merging operation) are set of integration operations for “local” feature moderlespresented as constraint satisfaction problems (CSPs) which basically support the goal of integrating local mo[1d9-]. To demonstrate the applicability of our approach, els into a global one. In this context, the authors alswoe present the results of a corresponding performance specify feature model relationships on a logical basaisn, alysis. for example, one feature mode l1 is the specializa- The remainder of this paper is structured as follows. tion of a feature mode l2 if the configuration space In Section 2, we introduce a working example consisting of 1 is a subset of the configuration space of 2 of simplified feature models from the automotive domain. – see also Thüm et al. 1[7, 3]. The authors also intro-Using this example, we discuss our algorithmic approach duce amerge operation where the introduced semanticsto semantics-preserving feature model merging in Secdoes not support semantics preservation but requirestion 3. To show the performance of our approach, we that the result of the merging operation is equivalenrteport the results of a corresponding performance evaluor a superset of the solution (configuration) spaces ofation (see Section4). Finally, we conclude the paper with the two original feature models, i.es.o,lutions( 1) ∪ a discussion of existing threats to validity (Sectio5n)and solutions( 2) ⊆ solutions(merge( 1, 2)) . Such a a corresponding summary of the contributions of this semantics of a merge operation is also considered in thepaper (Section6). contributions of Broek et al.10[], Carbonell et al1.1[], and She et al. 1[8].
Following theunion merge semantics introduced 2. Example Scenario in Schobbens et al. 1[2], the feature model merging approach presented in this paper focuses on theWe now introduce a simplified example of a feature model preservation of the semantics of the source featuremerging scenario. Our basic underlying assumption is models used as an input for the merging proceduret.hat the original feature models are consistent, i.e., it In other words, it supports a semantics-preservingis possible that at least one solution can be identified merging where the configuration space of the featureand also that the feature set of the original models are the same, i.e., the diferences are primarily observable in model resulting from a merging operation is exactly the union of the configuration spaces of the originalterms of the constraints defined in the individual modfseolauttuiornes(mmoedrgeel(s :1,s o2l)u)tions( 1)wh∪ich sioslumtoiornes( r2e)str=ictive ieonlrasig.liUInnaSlofefuearattueuxrraeemmmpoolddeeelflr)soaamnr dethdeenaoutetodw mahositcihv eddeon(tomhteaeiosnrt,hitghe-e original European Union feature model. In this contexTt,able 1 we assume that these feature models are consistent, i.e.N,umber of consistent solutions (configurations) related to the non-void [20], meaning that at least one configuration original and contextualized feature models. Feature model
#configurations ′ = ′ ′ ∩ ∪ ′ ′ 108 96 204 84 can be identified for each of those models. Finally, we denote the resulting model (the merging result) as can exist in terms of constraints representing individualthe context variablreegion.2 Assuming the two regions configuration spaces. In the following, we specify con-European Union and US, our context variable could be . Diferences in the two variability models els (represented as CSPs) has to be contextualized using
fashion, each constraint of the two original feature modture models and
represented in terms straints that define the properties of the two original fea-defined as region( resenting the European and the US feature mode1l9][.1 of individual constraint satisfaction problems (CSPs) repc-onstraint [] from the
, ) denoting the variableregion ( [] ) of the “EU” (“US”) CSP (derived (
) feature model) has to be with the allowed value{s, } . More precisely, each ated configuration belongs to. Contexts follow the idea a contextual information, i.e., to which region a genera-re denoted a s sponding domain definitions (e.g., type(lim,com,sit,suv) These CSPs are defined in terms of variables with corre-translated into a contextualized representation – see the following example :1 ∶ ≠ would be translated
Note thatregion is an additional variable representingof the original knowledge bas e s corresponding set of constraints22[]. denotes the variablteype with the allowed values) and ainto a corresponding contextualized fo r1m ′ ∶ = → ( ≠ ) . The resulting contextualized variants
and ′ and ′ .
and specific) feature models.
To show the diferences between the feature models ). Following this argumentationso,lutions( , Table1 provides an overview of solutions( ) = solutions( the number of solutions supported by the original (regionw- hich supports our goal of achieving a semantics ) ∪
′ ) preserving merging of the original knowledge bases (see Table1).
The algorithmic approach to support such a semanticspreserving merging is shown in Algorith1m(MergeFM) which itself is aFlama [24] prototype implementation. In
In order to be able to merge the two original feature moad-first step (starting with line6 of MergeFM), those conels ( and
) in a semantics-preserving straints in the contextualized original knowledge bases 1The feature name abbreviations o f
2In general, contexts can be represented by a set of variables (i.e., of separation of concerns [15] which supports a kind of decentralized modeling2[3]. For example, using the conbe expressed as 1
∶ = → ≠ ℎ text variableregion, the constrain t 1 ∶ ≠ ℎ
would explicitly indicating that this constraint has to hold for configurations generated on the basis of th e
CSP. • • 2 3 2 3 : ∶ : ∶ ∶ = → = ∶ = → ≠ = = → → {region(US), type(lim,com,cit,suv), color(b,w), engine(1l, 1.5l, 2l),
fuel(d, g, h), coupling(yes,no), 1
∶ ≠ ℎ {region(EU), type(lim,com,cit,suv), color(b,w), engine(1l,
1.5l, g, h), coupling(yes,no), 1 2l), ∶ fuel(d, ≠ } } = = e, e, , , , • ′ 2 ) ) } • ′ : ′ :
{region(US), type(lim,com,cit,suv), color(b,w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), coupling(yes,no), 1′
∶ = → ( ≠ ℎ) , 3′ ∶ = → ( = → = ∶ = → ( = → =
{region(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′ ∶ = → ( = → = ∶ = → ( = → ≠
∶ = → ( ≠ )
Note that the solution (configuration) spaces of the contextualized feature model s are the same as those of the original ones (assuming a corresponding context setting, e.g., = ′
and ′ ∪ ′ , (in Algorithm1 denoted as 1′ and 2′) can be decon- → ( = → = ) , 1′ ∶ = textualized where such a contextualization is not needed → ( ≠ ) , 3′ ∶ = → ( = ( is a decontextualized version of′): if ¬ is consistent → ≠ ) } with 1′ ∪ 2′, there (obviously) exist solutions supporting¬ . In such a case, the constrai ntmust be added On the algorithmic level, the resulting knowledge base in a contextualized fashion to the resulting knowledg e is represented in terms of a constraint satisfaction base , since some feature model configuration (in the problem. One possibility of representing the integrated other knowledge base) support¬s . If ¬ is inconsistent knowledge base as the resulting integrated feature model with 1′ ∪ 2′, can be added in decontextualized fash-is depicted in Figure2. ion to the resulting knowledge ba se . In a second step (starting with line14 of Algorithm1), each constraint of 4. Performance Evaluation the resulting knowledge base has to be checked for redundancy: in a logical sense, a constrainctan be regarded as In this section, we discuss the results of an initial perforredundant if −{} is inconsistent with¬ which means mance analysis we have conducted to evaluaMteergeFM that the constraint does not reduce the solution space o(Aflgorithm 1)4. For this analysis, we applied 8 real-world FM and thus logically follows from the constraints in FMvariability models with varying sizes collected from the (and can be deleted from the constraints in FM). S.P.L.O.T. feature model repository25[] and the Diverso
Lab’s benchmark5 [26]. Table4 shows the characteristics A1l:go{ rith1′, m 12′M:etwrgoeFcMon( text1′u, aliz2′e)∶d and consistent fea-ebonef-ttmhsheersaegreemdso”odffeeclasotnu(dtreeenxtmoutoaedldeizaless d)(.cIon1′naostnrrddaeirntts2o′)frgwoeinmtheirndaditfeievri“-dtuoa-l ture models} s, we determined the needed number of relationships 2: { ′: constraint c in contextualized form} or cross-tree constraints. We then modified these se3: { : feature model as a result oMfergeFM} lected relationships/cross-tree constraints by changing 54:: ←′{}← ; 1′ ∪ 2′; tchheairngtyinpge,afoltreerxnaamtipvlee,tochoarn,goirngchmaanngdiantgorryeqtouiorpetsiotnoaelx,6: for all ′ ∈ ′ do cludes. The resulting model s ( 1′ ∪ 2′ = ′) are 7: if ({¬} ∪ ′ ∪ ) then represented as constraint satisfaction problem1s9][ that 8: ← ∪ {}; difer individually in terms of the number of constraints 9: else (#constraints) and the degree of contextualization (ex10: ← ∪ { ′}; pressed as percentages in Table2sand 3). In order to 11: end if take into account deviations in time measurements, we 12: ′ ← ′ − { ′}; repeated each experimental setting 10 times where in 13: end for each repetition cycle the constraints in the individual 14: for all ∈ do (contextualized) knowledge bas e s ′ were ordered ran15: if (( − {}) ∪ {¬}) then domly. All analyses have been conducted with an Apple 16: ← − {}; M1 Pro (8 cores) computer with 16-GB RAM. For evalu17: end if ation purposes, we used theChoco solver6 to perform 18: end for the needed consistency checks. 19: ; The number of consistency checks needed for decontextualization is linear in terms of the number of constraints in ′. A performance evaluation oMf ergeFM
When applying Algorithm1 to and , with diferent knowledge base sizes and degrees of conthe resulting knowledge ba s e looks like as follows.textualized constraints i n is depicted in Table2. In In the resulting knowledge base, the constrain2′ t has MergeFM, the runtime (measured in terms of millisecbeen decontextualized. Also, as a result of applying Aoln-ds needed by the constraint solv7erto find a solution) gaondritthhums1c,aconnbsetrdaeilnette2′d fcraonm be reg.3arded as redundanticnrceraesaessews iwthiththtehneunmubmebreorfocfocnotenxstturaaliniztes dinco′nsatnrdaidnet-s in • : {region(US,EU), type(lim,com,cit,suv), 4The dataset, the implementation of algorithms, and evaluation procolor(b,w), engine(1l, 1.5l, 2l), fuel(d, e, g, h), cou- grams can be found athttps://github.com/AIG-ist-tugraz/FMMerging. pling(yes,no), 1′ ∶ = → ( ≠ ℎ) , 5https://github.com/flamapy/benchmarking 2′ ∶ = → = , 3′ ∶ = 67Fcohrocthoe-spoulrvpero.soersgof our evaluation we generated variability models 3Alternativel y,2′ could be deleted as a redundant constraint (instead represented as constraint satisfaction problems formulated using of 2′ ). the Choco constraint solver – www.choco-solver.org. . The increase in eficiency can be explained by the knowledge base compact in the sense of deleting redunfact that a higher degree of contextualization includedsant constraints and not needed contextual information. more situations where the inconsistency check in LineThe runtime performance of our approach is shown on 7 (Algorithm 1) terminates earlier (a solution has beetnhe basis of a first performance analysis with real-world found) compared to situations where no solution couldfeature models. Future work will include the evaluation be found. In addition, Table3 indicates that the perfor-of our concepts with further knowledge bases and the mance of solution search does not difer depending on the development of alternative merging algorithms with the degree of contextualization in the resulting knowledggeoal to further improve runtime performance. Furtherbase . more, we will evaluate diferent alternative feature model
Consequently, integrating individual variability modr-epresentations that help to represent contextualized conels can trigger the following improvements. (1) Des-traints – one such representation has been discussed in contextualization i n can lead to less cognitive eforts this paper. when adapting / extending knowledge bases (due to a potentially lower number of constrain2ts7][ and a lower degree of contextualization). (2) Reducing the overalRl eferences number of constraints in can also improve runtime performance of the resulting integrated knowledge base[.1] K. Kang, S. Cohen, J. Hess, W. Novak, S. Peterson, Feature-oriented domain analysis feasibility study (foda), Technical Report, CMU/SEI-90-TR-021 5. Threats to Validity (1990). [2] K. Czarnecki, S. Helsen, U. Eisenecker, FormalWe are aware that our evaluation is in fact based on izing cardinality-based feature models and their real-world feature models, however, synthesized vari- specialization, SoftwareProcess: Improvement and ants thereof have been used foMrergeFM evaluation Practice 10 (2005) 7–29. purposes. Furthermore, our approach is based on the[3] A. Felfernig, A. Falkner, D. Benavides, Feature assumption that the “to-be-merged” feature models have Models: AI-Driven Design, Analysis and Applicathe same set of features, i.e., we assume feature equiv- tions, SpringerBriefs in Computer Science, Springer, alence. In this context, we assume that in real-world Cham, 2024. doi:10.1007/978-3-031-61874-1. scenarios further streamlining tasks (e.g., feature name[4] L. Galarraga, N. Preda, F. Suchanek, Mining rules alignment) have to be completed beforMeergeFM can be to align knowledge bases, in: Proceedings of the activated. Our basic assumption behind redundancy elim- 2013 Workshop on Automated Knowledge Base ination and de-contextualization iMnergeFM is that the Construction, San Francisco, CA, 2013, pp. 43–48. understandability and maintainability of feature mod- [5] J. Delgrande, T. Schaub, A consistency-based frameels can be improved – although already confirmed by work for merging knowledge bases, Journal of Aprelated work2[7], further research is needed to better un- plied Logic 5 (2007) 459–477. derstand major impact factors that make feature models [6] P. Liberatore, M. Schaerf, Arbitraton (or how to (and underlying knowledge bases) easier to understand merge knowledge bases), IEEE Transactions on and maintainable. Knowledge and Data Engineering 10 (1998) 76–90. [7] R. Reiter, A theory of diagnosis from first principles,
AI Journal 23 (1987) 57–95. 6. Conclusions and Future Work [8] M. Acher, P. Collet, P. Lahire, R. France, Composing feature models, in: M. van den Brand, D. GašeIn this paper, we have introduced an approach to the vić, J. Gray (Eds.), Software Language Engineering, consistency-based merging of variability models repre- Springer, Berlin, Heidelberg, 2010, pp. 62–81. sented as constraint satisfaction problems. The approach[9] V. Bischof, K. Farias, L. Gonçales, J. Vichelps to build semantics-preserving feature models in the tória Barbosa, Integration of feature modsense that the solution spaces of the resulting knowledge els: A systematic mapping study, Inforbases (result of the merging process) correspond to the mation and Software Technology 105 (2019) union of the solution spaces of the original knowledge 209–225. URL: https://www.sciencedirect.com/ bases. Such an approach can be useful in the mentioned science/article/pii/S095058491630217.8doi:https: integration scenario but as well in situations where difer//doi.org/10.1016/j.infsof.2018.08.016. ent parts (representing diferent contexts) of a knowledge [10] P. van den Broek, I. Galvao, J. Noppen, Merging 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