Consistency-based Merging of Variability Models

Abstract

Globally operating enterprises selling large and complex products and services often have to deal with situations where variability models are locally developed to take into account the requirements of local markets. For example, cars sold on the U.S. market are represented by variability models in some or many aspects different from European ones. In order to support global variability management processes, variability models and the underlying knowledge bases often need to be integrated. This is a challenging task since an integrated knowledge base should not produce results which are different from those produced by the individual knowledge bases. In this paper, we introduce an approach to variability model integration that is based on the concepts of contextual modeling and conflict detection. We present the underlying concepts and the results of a corresponding performance analysis.

-

Configuration [ 7, 14 ] is one of the most successful applications of Artificial Intelligence technologies applied in domains such as telecommunication switches, financial services, furniture, and software components. In many cases, configuration knowledge bases are represented in terms of variability models such as feature models that provide an intuitive way of representing variability properties of complex systems [ 10, 4 ]. Starting with rule-based approaches, formalizations of variability models have been transformed into model-based knowledge representations which are more applicable for the handling of large and complex knowledge bases, for example, in terms of knowledge base maintainability and expressivity of complex constraints [ 2, 7 ]. Examples of model-based knowledge representations are constraint-based representations [ 15 ], description logic and answer set programming (ASP) [ 7 ]. Besides variability reasoning for single users, latest research also shows how to deal with scenarios where groups of users are completing a configuration task [ 6 ]. In this paper, we focus on single user scenarios where variability models are represented as a constraint satisfaction problem (CSP) [ 3, 15 ].

There exist a couple of approaches dealing with the issue of integrating knowledge bases. First, knowledge base alignment is the process of identifying relationships between concepts in different knowledge bases, for example, classes describe the same concept but have different class names (and/or attribute names). Approaches supporting the alignment of knowledge bases are relevant in scenarios where numerous and large knowledge bases have to be integrated (see, for example, [ 9 ]). Ardissono et al. [ 1 ] introduce an approach to distributed configuration where individual knowledge bases are integrated into a distributed configuration process in which individual configurators are responsible for configuring individual parts of a complex product or service. The underlying assumption is that individual knowledge bases are consistent and that there are no (or only a low number of) dependencies between the given knowledge bases.

The merging of knowledge bases is related to the task of exploiting various merging operators to different belief sets [ 5, 11 ]. For example, Delgrande and Schaub [ 5 ] introduce a consistency-based merging approach where the result of a merging process is a maximum consistent set of logical formulas representing the union of the individual knowledge bases. In the line of existing consistency-based analysis approaches, the resulting knowledge bases represent a logical union of the original knowledge bases that omits minimal sets of logical sentences inducing an inconsistency [ 12 ]. Contextual modeling [ 8 ] is related to the task of decentralizing variability knowledge related development and maintenance tasks.

Approaches to merging feature models represented on a graphical level on the basis of merging rules have been introduced, for example, in [ 16, 13 ]. In this context, feature models including specific constraint types such as requires and excludes, are merged in a semantics-preserving fashion. Compared to our approach, the merging of variability models introduced in [ 16, 13 ] is restricted to specific constraint types and does not take into account redundancy.

Our approach provides a generalization to existing approaches especially due to the generalization to arbitrary constraint types and redundancy-free knowledge bases as a result of the merge operation. We propose an approach to the merging of variability models (represented as constraint satisfaction problems) which guarantees semantics preservation, i.e., the union of the solutions determined by individual constraint solvers (configurators) is equivalent to the solution space of the integrated variability model (knowledge base). In this context, we assume that the knowledge bases to be integrated (1) are consistent and (2) use the same variable names for representing individual item properties (knowledge base alignment issues are beyond the scope of this paper).

The contributions of this paper are the following. (1) We provide a short analysis of existing approaches to knowledge base integration and point out specific properties of variability model integration scenarios that require alternative approaches. (2) We introduce a new approach to variability knowledge integration which is based on the concepts of contextualization and conflict detection. (3) We show the applicability of a our approach on the basis of a performance analysis.

The remainder of this paper is organized as follows. First, we introduce a working example from the automotive domain (see Section 2). On the basis of this example, we introduce our approach to variability model integration (merging) in Section 3. In Section 4, we present a performance evaluation. Section 5 includes a discussion of threats to validity of the presented merging approach. The paper is concluded in Section 6 with a discussion of issues for future work. 2

Example Variability Models

In the following, we introduce a working example which will serve as a basis for the discussion of our approach to knowledge integration (Section 3). Let us assume the existence of two different variability models. For the purpose of our example, we introduce two car configuration knowledge bases represented as a constraint satisfaction problem. One car configuration knowledge base is assumed to be defined for the U.S. market and one for the German market. For simplicity, we assume that (1) both knowledge bases are represented as a constraint satisfaction problem (CSP) [ 15 ] and (2) that both knowledge bases operate on the same set of variables and corresponding domain definitions.4 Our two knowledge bases consisting of variable definitions and corresponding constraints fCKBus, CKBgerg are the following.

CKBus: fcountry(US), type(combi, limo, city, suv), color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c1us : f uel 6= hybrid, c2us : f uel = electro ! coupling dev = no, c3us : f uel = diesel ! color = blackg CKBger: fcountry(GER), type(combi, limo, city, suv), color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c1ger : f uel 6= gas, c2ger : f uel = electro ! couplingdev = no, c3ger : f uel = diesel ! type 6= cityg

In these knowledge bases, we denote the variable country as contextual variable since it is used to specify the country a configuration belongs to but is not directly associated with a specific component of the car. Table 1 shows a summary of the solution spaces (in terms of the number of potential solutions) that are associated with the country-specific knowledge bases CKBus and CKBger. For simplicity, we kept the number of constraints the same in both knowledge bases, however, the integration concepts introduced in Section 3 are also applicable to knowledge bases with differing numbers of constraints.

Merging Variability Models

In this section, we introduce our approach to merge variability models represented as constraint satisfaction problems (CSPs) [ 15 ]. Our approach is based on the assumption that the constraints of the two original knowledge bases CKB1 and CKB2 are contextualized, i.e., each constraint of knowledge base CKB1 gets contextualized 4 We are aware of the fact that this assumption does not hold for real-world scenarios in general. However, we consider tasks of concept matching as an upstream task we do not take into account when integrating knowledge bases on a formal level. on the basis of predefined contextualization variables. For example: assuming a context variable country(US,GER), each constraint c[i]us of the US knowledge base is contextualized with (transformed into) country = U S ! (c[i]us). Constraint c1us : f uel 6= hybrid would be translated into c1us0 : country = U S ! (f uel 6= hybrid). CKBus and CKBger have been transformed into their contextualized variants CKBu0s and CKBg0er where CKBu0s [ CKBg0er = CKB0.

CKBu0s: fcountry(US), type(combi, limo, city, suv), color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c01us : country = U S ! (f uel 6= hybrid), c02us : country = U S ! (f uel = electro ! couplingdev = no), c3us : country = U S ! (f uel = diesel ! color = black)g CKBg0er: fcountry(GER), type(combi, limo, city, suv), color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c01ger : country = GER ! (f uel 6= gas), c02ger : country = GER ! (f uel = electro ! couplingdev = no), c03ger : country = GER ! (f uel = diesel ! type 6= city)g The solution spaces of the contextualized knowledge bases CKBu0s and CKBg0er are shown in Table 2. They have the same solution spaces as CKBus and CKBger. [!ht]

On the basis of such a contextualization, we are able to preserve the consistency and semantics of the two original knowledge bases in the sense that (1) the solution space (CKB1) is equivalent to the solution space (CKB10), (2) the solution space (CKB2) is equivalent to the solution space (CKB20), and (3) the solution space (CKB1) [ solution space (CKB2) is equivalent to the solution space (CKB10 [ CKB20 = CKB0).

Based on this representation, we are able to (1) get rid of contextualizations (see line 7 of Algorithm 1) that are not needed in the integrated version of the two original configuration knowledge bases and (2) delete redundant constraints (see line 15 of Algorithm 1). In Line 7 it is checked whether a contextualization is needed for the constraint c (c is the decontextualized version of c0). If the negation of c is consistent with the union of the contextualized knowledge bases, solutions exist that support :c. Consequently, c must remain contextualized. Otherwise, the contextualization is not needed and c is added to the resulting knowledge base – with this, it replaces c0, i.e., the corresponding contextualized constraint.

Each constraint in the resulting knowledge base CKB (the decontextualized knowledge base) is thereafter checked with regard to redundancy (see Line 15). A constraint c is regarded as redundant if CKB fcg is inconsistent with :c. In this case, c does not reduce the search space and thus can be deleted from CKB – it is redundant with regard to CKB.

Algorithm 1 CKB-MERGE(CKB10; CKB20): CKB 1: fCKB10;20 : two contextualized and consistent configuration knowledge basesg 2: fc0: a contextualized version of constraint cg 3: fCKB: knowledge base resulting from merge operationg 4: CKB ;; 5: CKB0 CKB10 [ CKB20 ; 6: for all c0 2 CKB0 do 7: if inconsistent(f:cg [ CKB0 [ CKB) then 8: CKB CKB [ fcg; 9: else 10: CKB CKB [ fc0g; 11: end if 12: CKB0 CKB0 fc0g; 13: end for 14: for all c 2 CKB do 15: if inconsistent((CKB fcg) [ f:cg) then 16: CKB CKB fcg; 17: end if 18: end for 19: return CKB;

The knowledge base CKB resulting from applying Algorithm 1 to the individual knowledge bases CKBu0s and CKBg0er looks like as follows. In CKB, constraint c02us is represented in a decontextualized fashion since the context information is not needed. Furthermore, constraint c02ger has been deleted since it is redundant.

CKB: fcountry(US, GER), type(combi, limo, city, suv), color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c01us : country = U S ! (f uel 6= hybrid), c2us : f uel = electro ! couplingdev = no, c03us : country = U S ! (f uel = diesel ! color = black), c01ger : country = GER ! (f uel 6= gas), c03ger : country = GER ! (f uel = diesel ! type 6= city)g 4

Performance Evaluation

In this section, we discuss the results of an initial analysis we have conducted to evaluate CKB-MERGE (Algorithm 1). For this analysis, we applied 10 different synthesized variability models CKB0 (CKB0 = CKB10 [ CKB20) represented as constraint satisfaction problems [ 15 ]) that differ individually in terms of the number of constraints (#constraints) and the degree of contextualization (expressed as percentages in Tables 3 and 4). 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 CKB0 were ordered randomly.

The number of consistency checks needed for decontextualization is linear in terms of the number of constraints in CKB0. A performance evaluation of CKB-MERGE with different knowledge base sizes and degrees of contextualized constraints in CKB is depicted in Table 3. In CKB-MERGE, the runtime (measured in terms of milliseconds needed by the constraint solver5 to find a solution) increases with the number of constraints in CKB0 and decreases with the number of contextualized constraints in CKB. The increase in 5 For the purposes of our evaluation we generated variability models represented as constraint satisfaction problems formulated using the CHOCO constraint solver – www.choco-solver.org. 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 4 indicates that the performance of solution search does not differ depending on the degree of contextualization in the resulting knowledge base CKB.

Consequently, integrating individual variability models can trigger the following improvements. (1) De-contextualization in CKB can lead to less cognitive efforts when adapting / extending knowledge bases (due to a potentially lower number of constraints and a lower degree of contextualization). (2) Reducing the overall number of constraints in CKB can also improve runtime performance of the resulting integrated knowledge base. The main threat to (external) validity is the overall representativeness of the knowledge bases used for evaluating the performance of CKBMERGE. The current evaluation is based on a set of synthesized knowledge bases which do not directly reflect real-world variability models. We want to point out that the major focus of our work is to provide an algorithmic solution that allows semantics-preserving knowledge integration which is a new approach and regarded as the major contribution of our work. The application of CKB-MERGE to real-world variability models, i.e., not synthesized ones, is in the focus of our future work. In this paper, we have introduced an approach to the consistencybased merging of variability models represented as constraint satisfaction problems. The approach helps to build semantics-preserving knowledge bases in the sense that the solution space of the resulting knowledge base (result of the merging process) corresponds to the union of the solution spaces of the original knowledge bases. 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 performance of our approach is shown on the basis of a first performance analysis with synthesized configuration knowledge bases. Future work will include the evaluation of our concepts with more complex knowledge bases and the development of alternative merge algorithms with the goal to further improve runtime performance.

References

[1] L. Ardissono , A. Felfernig , G. Friedrich , A. Goy , D. Jannach , G. Petrone, R. Schaefer , and M. Zanker , ' A framework for the development of personalized, distributed web-based configuration systems' , AI Magazine , 24 ( 3 ), 93 - 110 , ( 2003 ).

[2] D. Benavides , S. Segura , and A. Ruiz-Cortes , ' Automated analysis of feature models 20 years later: A literature review' , Information Systems , 35 ( 6 ), 615 - 636 , ( 2010 ).

[3] D. Benavides , P. Trinidad , and A. Ruiz-Cortes , 'Using constraint programming to reason on feature models' , in 17th International Conference on Software Engineering and Knowledge Engineering (SEKE' 2005 ), pp. 677 - 682 , Taipei, Taiwan, ( 2005 ).

[4] K. Czarnecki , S. Helsen , and U. Eisenecker, ' Formalizing cardinalitybased feature models and their specialization' , SoftwareProcess: Improvement and Practice , 10 ( 1 ), 7 - 29 , ( 2005 ).

[5] J. Delgrande and T. Schaub , ' A consistency-based framework for merging knowledge bases' , Journal of Applied Logic , 5 ( 3 ), 459 - 477 , ( 2007 ).

[6] A. Felfernig , L. Boratto , M. Stettinger , and M. Tkalcic , Group Recommender Systems - An Introduction , Springer, 2018 .

[7] A. Felfernig , L. Hotz , C. Bagley , and J. Tiihonen , Knowledge-based Configuration: From Research to Business Cases , Morgan Kaufmann Publishers, 1st edn., 2014 .

[8] A. Felfernig , D. Jannach , and M. Zanker , ' Contextual diagrams as structuring mechanisms for designing configuration knowledge bases in uml' , in 3rd International Conference on the Unified Modeling Language (UML2000) , volume 1939 of Lecture Notes in Computer Science , pp. 240 - 254 , York, UK, ( 2000 ). Springer.

[9] L. Galarraga , N. Preda , and F. Suchanek , ' Mining rules to align knowledge bases' , in Proceedings of the 2013 Workshop on Automated Knowledge Base Construction , pp. 43 - 48 , San Francisco, CA, ( 2013 ).

[10] K. Kang , S. Cohen , J. Hess , W. Novak , and S. Peterson , ' Featureoriented domain analysis feasibility study (foda)' , Technical Report , CMU/SEI-90 - TR- 021 , ( 1990 ).

[11] P. Liberatore and M. Schaerf , ' Arbitraton (or how to merge knowledge bases)' , IEEE Transactions on Knowledge and Data Engineering , 10 ( 1 ), 76 - 90 , ( 1998 ).

[12] R. Reiter , ' A theory of diagnosis from first principles' , AI Journal , 23 ( 1 ), 57 - 95 , ( 1987 ).

[13] S. Segura , D. Benavides , A. Ruiz-Cortes , and P. Trinidad , ' Automated merging of feature models using graph transformations' , in Generative and Transformational Techniques in Software Engineering, number 5235 in Springer Lecture Notes in Computer Science , pp. 489 - 505 , ( 2007 ).

[14] M. Stumptner , ' An overview of knowledge-based configuration' , AI Communications , 10 ( 2 ), 111 - 125 , ( 1997 ).

[15] E. Tsang , Foundations of Constraint Satisfaction, Academic Press, London, 1993 .

[16] P. van den Broek , I. Galvao, and J. Noppen , ' Merging feature models' , in 15th International Software Product Line Conference , pp. 83 - 90 , Jeju Island , South Korea, ( 2010 ).