=Paper=
{{Paper
|id=Vol-2467/paper-02
|storemode=property
|title=Consistency-based Merging of Variability Models
|pdfUrl=https://ceur-ws.org/Vol-2467/paper-02.pdf
|volume=Vol-2467
|authors=Alexander Felfernig,Mathias Uta,Gottfried Schenner,Johannes Spöcklberger
|dblpUrl=https://dblp.org/rec/conf/confws/FelfernigUSS19
}}
==Consistency-based Merging of Variability Models==
https://ceur-ws.org/Vol-2467/paper-02.pdf
Consistency-based Merging of Variability Models
Mathias Uta1 and Alexander Felfernig2
and Gottfried Schenner3 and Johannes Spöcklberger2
Abstract. Globally operating enterprises selling large and complex integrated into a distributed configuration process in which individ-
products and services often have to deal with situations where vari- ual configurators are responsible for configuring individual parts of a
ability models are locally developed to take into account the require- complex product or service. The underlying assumption is that indi-
ments of local markets. For example, cars sold on the U.S. market vidual knowledge bases are consistent and that there are no (or only
are represented by variability models in some or many aspects differ- a low number of) dependencies between the given knowledge bases.
ent from European ones. In order to support global variability man- The merging of knowledge bases is related to the task of exploiting
agement processes, variability models and the underlying knowledge various merging operators to different belief sets [5, 11]. For exam-
bases often need to be integrated. This is a challenging task since an ple, Delgrande and Schaub [5] introduce a consistency-based merg-
integrated knowledge base should not produce results which are dif- ing approach where the result of a merging process is a maximum
ferent from those produced by the individual knowledge bases. In consistent set of logical formulas representing the union of the in-
this paper, we introduce an approach to variability model integration dividual knowledge bases. In the line of existing consistency-based
that is based on the concepts of contextual modeling and conflict analysis approaches, the resulting knowledge bases represent a logi-
detection. We present the underlying concepts and the results of a cal union of the original knowledge bases that omits minimal sets of
corresponding performance analysis. logical sentences inducing an inconsistency [12]. Contextual model-
ing [8] is related to the task of decentralizing variability knowledge
related development and maintenance tasks.
1 Introduction Approaches to merging feature models represented on a graph-
Configuration [7, 14] is one of the most successful applications of Ar- ical level on the basis of merging rules have been introduced, for
tificial Intelligence technologies applied in domains such as telecom- example, in [16, 13]. In this context, feature models including spe-
munication switches, financial services, furniture, and software com- cific constraint types such as requires and excludes, are merged in a
ponents. In many cases, configuration knowledge bases are repre- semantics-preserving fashion. Compared to our approach, the merg-
sented in terms of variability models such as feature models that pro- ing of variability models introduced in [16, 13] is restricted to spe-
vide an intuitive way of representing variability properties of com- cific constraint types and does not take into account redundancy.
plex systems [10, 4]. Starting with rule-based approaches, formaliza- Our approach provides a generalization to existing approaches es-
tions of variability models have been transformed into model-based pecially due to the generalization to arbitrary constraint types and
knowledge representations which are more applicable for the han- redundancy-free knowledge bases as a result of the merge operation.
dling of large and complex knowledge bases, for example, in terms We propose an approach to the merging of variability models (repre-
of knowledge base maintainability and expressivity of complex con- sented as constraint satisfaction problems) which guarantees seman-
straints [2, 7]. Examples of model-based knowledge representations tics preservation, i.e., the union of the solutions determined by indi-
are constraint-based representations [15], description logic and an- vidual constraint solvers (configurators) is equivalent to the solution
swer set programming (ASP) [7]. Besides variability reasoning for space of the integrated variability model (knowledge base). In this
single users, latest research also shows how to deal with scenarios context, we assume that the knowledge bases to be integrated (1) are
where groups of users are completing a configuration task [6]. In this consistent and (2) use the same variable names for representing indi-
paper, we focus on single user scenarios where variability models are vidual item properties (knowledge base alignment issues are beyond
represented as a constraint satisfaction problem (CSP) [3, 15]. the scope of this paper).
There exist a couple of approaches dealing with the issue of in- The contributions of this paper are the following. (1) We provide
tegrating knowledge bases. First, knowledge base alignment is the a short analysis of existing approaches to knowledge base integra-
process of identifying relationships between concepts in different tion and point out specific properties of variability model integration
knowledge bases, for example, classes describe the same concept scenarios that require alternative approaches. (2) We introduce a new
but have different class names (and/or attribute names). Approaches approach to variability knowledge integration which is based on the
supporting the alignment of knowledge bases are relevant in scenar- concepts of contextualization and conflict detection. (3) We show the
ios where numerous and large knowledge bases have to be integrated applicability of a our approach on the basis of a performance analy-
(see, for example, [9]). Ardissono et al. [1] introduce an approach sis.
to distributed configuration where individual knowledge bases are The remainder of this paper is organized as follows. First, we in-
troduce a working example from the automotive domain (see Section
1 Siemens Erlangen, Germany, email: mathias.uta@siemens.com
2). On the basis of this example, we introduce our approach to vari-
2 Graz University of Technology, Austria, email: alexan- ability model integration (merging) in Section 3. In Section 4, we
der.felfernig@ist.tugraz.at, spoecklberger.johannes@student.tugraz.at
3 Siemens AG, Austria, email: gottfried.schenner@siemens.com present a performance evaluation. Section 5 includes a discussion of
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
threats to validity of the presented merging approach. The paper is on the basis of predefined contextualization variables. For example:
concluded in Section 6 with a discussion of issues for future work. 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
2 Example Variability Models would be translated into c1us0 : country = U S → (f uel 6=
In the following, we introduce a working example which will serve hybrid). CKBus and CKBger have been transformed into their
0 0 0
as a basis for the discussion of our approach to knowledge integration contextualized variants CKBus and CKBger where CKBus ∪
0 0
(Section 3). Let us assume the existence of two different variability CKBger = CKB .
models. For the purpose of our example, we introduce two car con- 0
figuration knowledge bases represented as a constraint satisfaction • CKBus : {country(US), type(combi, limo, city, suv), color(white,
problem. One car configuration knowledge base is assumed to be black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro,
defined for the U.S. market and one for the German market. For sim- diesel, gas, hybrid), service(15k, 20k, 25k), c01us : country =
plicity, we assume that (1) both knowledge bases are represented as U S → (f uel 6= hybrid), c02us : country = U S → (f uel =
a constraint satisfaction problem (CSP) [15] and (2) that both knowl- electro → couplingdev = no), c3us : country = U S →
edge bases operate on the same set of variables and corresponding (f uel = diesel → color = black)}
0
domain definitions.4 Our two knowledge bases consisting of variable • CKBger : {country(GER), type(combi, limo, city, suv),
definitions and corresponding constraints {CKBus , CKBger } are color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no),
the following. fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k),
c01ger : country = GER → (f uel 6= gas), c02ger :
• CKBus : {country(US), type(combi, limo, city, suv), color(white, country = GER → (f uel = electro → couplingdev = no),
black), engine(1l, 1.5l, 2l), couplingdev(yes,no), fuel(electro, c03ger : country = GER → (f uel = diesel → type 6= city)}
diesel, gas, hybrid), service(15k, 20k, 25k), c1us : f uel 6=
hybrid, c2us : f uel = electro → coupling− dev = no, The solution spaces of the contextualized knowledge bases
0 0
c3us : f uel = diesel → color = black} CKBus and CKBger are shown in Table 2. They have the same
• CKBger : {country(GER), type(combi, limo, city, suv), solution spaces as CKBus and CKBger .
color(white, black), engine(1l, 1.5l, 2l), couplingdev(yes,no), [!ht]
fuel(electro, diesel, gas, hybrid), service(15k, 20k, 25k), c1ger :
f uel 6= gas, c2ger : f uel = electro → couplingdev = no,
Table 2. Solution spaces when merging knowledge bases.
c3ger : f uel = diesel → type 6= city}
In these knowledge bases, we denote the variable country as con- Knowledge base #solutions
textual variable since it is used to specify the country a configuration CKBus 0 288
belongs to but is not directly associated with a specific component of CKBger0 324
the car. Table 1 shows a summary of the solution spaces (in terms CKB 0 = CKBus0 ∪ CKB 0
ger 612
0
CKBus ∩ CKBger 0 126
of the number of potential solutions) that are associated with the
country-specific knowledge bases CKBus and CKBger . For sim-
plicity, we kept the number of constraints the same in both knowl-
edge bases, however, the integration concepts introduced in Section On the basis of such a contextualization, we are able to preserve
3 are also applicable to knowledge bases with differing numbers of the consistency and semantics of the two original knowledge bases
constraints. in the sense that (1) the solution space (CKB1 ) is equivalent to the
solution space (CKB10 ), (2) the solution space (CKB2 ) is equivalent
[!ht]
to the solution space (CKB20 ), and (3) the solution space (CKB1 ) ∪
solution space (CKB2 ) is equivalent to the solution space (CKB10 ∪
Table 1. Solution spaces of individual knowledge bases. CKB20 = CKB 0 ).
Based on this representation, we are able to (1) get rid of contex-
Knowledge base #constraints #solutions
tualizations (see line 7 of Algorithm 1) that are not needed in the
CKBus 3 288
integrated version of the two original configuration knowledge bases
CKBger 3 324 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
3 Merging Variability Models bases, solutions exist that support ¬c. Consequently, c must remain
contextualized. Otherwise, the contextualization is not needed and c
In this section, we introduce our approach to merge variability mod- is added to the resulting knowledge base – with this, it replaces c0 ,
els represented as constraint satisfaction problems (CSPs) [15]. Our i.e., the corresponding contextualized constraint.
approach is based on the assumption that the constraints of the two Each constraint in the resulting knowledge base CKB (the de-
original knowledge bases CKB1 and CKB2 are contextualized, contextualized knowledge base) is thereafter checked with regard to
i.e., each constraint of knowledge base CKB1 gets contextualized redundancy (see Line 15). A constraint c is regarded as redundant if
4 We are aware of the fact that this assumption does not hold for real-world CKB − {c} is inconsistent with ¬c. In this case, c does not reduce
scenarios in general. However, we consider tasks of concept matching as the search space and thus can be deleted from CKB – it is redundant
an upstream task we do not take into account when integrating knowledge with regard to CKB.
bases on a formal level.
Algorithm 1 CKB-M ERGE(CKB10 , CKB20 ): CKB efficiency can be explained by the fact that a higher degree of contex-
tualization includes more situations where the inconsistency check in
1: {CKB10 ,20 : two contextualized and consistent configuration
Line 7 (Algorithm 1) terminates earlier (a solution has been found)
knowledge bases}
compared to situations where no solution could be found. In addi-
2: {c0 : a contextualized version of constraint c}
tion, Table 4 indicates that the performance of solution search does
3: {CKB: knowledge base resulting from merge operation}
not differ depending on the degree of contextualization in the result-
4: CKB ← ∅;
ing knowledge base CKB.
5: CKB 0 ← CKB10 ∪ CKB20 ;
Consequently, integrating individual variability models can trig-
6: for all c0 ∈ CKB 0 do
ger the following improvements. (1) De-contextualization in CKB
7: if inconsistent({¬c} ∪ CKB 0 ∪ CKB) then
can lead to less cognitive efforts when adapting / extending knowl-
8: CKB ← CKB ∪ {c};
edge bases (due to a potentially lower number of constraints and a
9: else
lower degree of contextualization). (2) Reducing the overall number
10: CKB ← CKB ∪ {c0 };
of constraints in CKB can also improve runtime performance of the
11: end if
resulting integrated knowledge base.
12: CKB 0 ← CKB 0 − {c0 };
13: end for
14: for all c ∈ CKB do Table 3. Avg. runtime (msec) of CKB-M ERGE measured with different
15: if inconsistent((CKB − {c}) ∪ {¬c}) then knowledge base sizes (CKB 0 ) and shares of contextualized constraints in
16: CKB ← CKB − {c}; CKB (10-50% contextualization).
17: end if
CKB 0 #constraints 10% 20% 30% 40% 50%
18: end for
1 10 749 219 195 118 97
19: return CKB; 2 20 559 653 666 679 487
3 30 1541 813 644 588 664
The knowledge base CKB resulting from applying Algorithm 1 4 40 1888 1541 1345 1177 1182
0 0 5 50 3773 3324 3027 3171 2643
to the individual knowledge bases CKBus and CKBger looks like
0
as follows. In CKB, constraint c2us is represented in a decontextu- 6 60 5376 4458 4425 3304 3056
7 70 7300 6912 7362 5619 4896
alized fashion since the context information is not needed. Further-
8 80 10795 8793 7580 6821 5909
more, constraint c02ger has been deleted since it is redundant. 9 90 13365 11770 10103 8916 7831
10 100 15992 14443 14679 12417 11066
• CKB: {country(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 →
Table 4. Avg. runtime (msec) of the merged configuration knowledge
couplingdev = no, c03us : country = U S → (f uel = bases (CKB) measured with different knowledge base sizes (CKB 0 ) and
diesel → color = black), c01ger : country = GER → shares of contextualized constraints in CKB (10-50% contextualization).
(f uel 6= gas), c03ger : country = GER → (f uel = diesel →
type 6= city)} CKB 0 #constraints 10% 20% 30% 40% 50%
1 10 244 159 203 167 274
2 20 305 230 250 362 271
4 Performance Evaluation 3 30 310 378 251 426 243
4 40 425 453 522 502 563
In this section, we discuss the results of an initial analysis we have 5 50 500 640 603 637 657
conducted to evaluate CKB-M ERGE (Algorithm 1). For this anal- 6 60 881 728 899 801 698
ysis, we applied 10 different synthesized variability models CKB 0 7 70 830 778 802 888 876
(CKB 0 = CKB10 ∪ CKB20 ) represented as constraint satisfaction 8 80 917 1054 1011 848 1030
problems [15]) that differ individually in terms of the number of con- 9 90 1017 1117 1042 960 667
straints (#constraints) and the degree of contextualization (expressed 10 100 1387 1363 1297 1297 1308
as percentages in Tables 3 and 4). In order to take into account devi-
ations in time measurements, we repeated each experimental setting
10 times where in each repetition cycle the constraints in the indi-
vidual (contextualized) knowledge bases CKB 0 were ordered ran-
domly. 5 Threats to Validity
The number of consistency checks needed for decontextualiza-
tion is linear in terms of the number of constraints in CKB 0 . A The main threat to (external) validity is the overall representativeness
performance evaluation of CKB-M ERGE with different knowledge of the knowledge bases used for evaluating the performance of CKB-
base sizes and degrees of contextualized constraints in CKB is de- M ERGE. The current evaluation is based on a set of synthesized
picted in Table 3. In CKB-M ERGE, the runtime (measured in terms knowledge bases which do not directly reflect real-world variabil-
of milliseconds needed by the constraint solver5 to find a solution) in- ity models. We want to point out that the major focus of our work is
creases with the number of constraints in CKB 0 and decreases with to provide an algorithmic solution that allows semantics-preserving
the number of contextualized constraints in CKB. The increase in knowledge integration which is a new approach and regarded as the
5 For the purposes of our evaluation we generated variability models rep- major contribution of our work. The application of CKB-M ERGE
resented as constraint satisfaction problems formulated using the C HOCO to real-world variability models, i.e., not synthesized ones, is in the
constraint solver – www.choco-solver.org. focus of our future work.
6 Conclusions and Future Work
In this paper, we have introduced an approach to the consistency-
based merging of variability models represented as constraint satis-
faction problems. The approach helps to build semantics-preserving
knowledge bases in the sense that the solution space of the result-
ing knowledge base (result of the merging process) corresponds to
the union of the solution spaces of the original knowledge bases. Be-
sides 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 informa-
tion. 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 perfor-
mance.
REFERENCES
[1] L. Ardissono, A. Felfernig, G. Friedrich, A. Goy, D. Jannach,
G. Petrone, R. Schaefer, and M. Zanker, ‘A framework for the devel-
opment 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 cardinality-
based feature models and their specialization’, SoftwareProcess: Im-
provement and Practice, 10(1), 7–29, (2005).
[5] J. Delgrande and T. Schaub, ‘A consistency-based framework for merg-
ing knowledge bases’, Journal of Applied Logic, 5(3), 459–477, (2007).
[6] A. Felfernig, L. Boratto, M. Stettinger, and M. Tkalcic, Group Recom-
mender 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 Lan-
guage (UML2000), volume 1939 of Lecture Notes in Computer Sci-
ence, pp. 240–254, York, UK, (2000). Springer.
[9] L. Galarraga, N. Preda, and F. Suchanek, ‘Mining rules to align knowl-
edge 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, ‘Feature-
oriented domain analysis feasibility study (foda)’, Technical Report,
CMU/SEI-90-TR-021, (1990).
[11] P. Liberatore and M. Schaerf, ‘Arbitraton (or how to merge knowl-
edge 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 Genera-
tive and Transformational Techniques in Software Engineering, num-
ber 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).