=Paper=
{{Paper
|id=Vol-1453/07_ReinfrankNinausWotawaFelfernig_MaintainingConstraint-BasedSystems-_Confws-15_p39
|storemode=property
|title=Maintaining constraint-based systems: challenges ahead
|pdfUrl=https://ceur-ws.org/Vol-1453/07_ReinfrankNinausWotawaFelfernig_MaintainingConstraint-BasedSystems-_Confws-15_p39.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/ReinfrankNWF15a
}}
==Maintaining constraint-based systems: challenges ahead==
https://ceur-ws.org/Vol-1453/07_ReinfrankNinausWotawaFelfernig_MaintainingConstraint-BasedSystems-_Confws-15_p39.pdf
Maintaining Constraint-based Configuration
Systems: Challenges ahead
Florian Reinfrank, Gerald Ninaus, Franz Wotawa, Alexander Felfernig
Institute for Software Technology
Graz University of Technology
8020 Graz, Austria
firstname.lastname@ist.tugraz.at
Abstract. Constraint-based configuration systems like Such systems are used, for example in the notebook do-
knowledge-based recommendation and configuration are used main. Such product domains - like the notebook domain -
in many different product areas such as cars, bikes, mobile change over time because new product characteristics can fit
phones, and computers. The development and maintenance to new customer needs. For example, ten years ago the num-
of such systems is a time-consuming and error prone task be- ber of cpu cores for notebooks was not a configurable variable.
cause the content of such systems and the responsible knowl- Nowadays, users can choose between one, two, or four cpu
edge engineers are changing over time. cores. This example shows that constraint-based recommen-
Much research has been done to support knowledge engi- dation systems have to be updated over time. While adding
neers in their maintenance task. In this paper we give a short a variable to the product might be easy to handle, adding
overview of previous research in the context of intelligent tech- and editing constraints can be a time consuming and error
niques to support the maintenance task and give an overview prone task. This problem occurs in complex constraint-based
of future research aspects in this area. This paper focuses recommendation systems with many existing constraints.
on intelligent simulation techniques for generating metrics, A lot of research has been done in the last years to tackle
predicting boundary values for automated test case genera- this challenge. For example, recommendation techniques can
tion, assignment-based (instead of constraint-based) anomaly help to support knowledge engineers in their maintenance
management, and processes for the development of constraint- tasks, via reducing the sets of constraints so that the engi-
based configuration systems. neer can focus on the relevant constraints. Other examples
for the support of the maintenance tasks are anomaly de-
tection, dependency detection, and metrics measurement. An
1 Introduction example application for the maintenance of constraint-based
The number of e-commerce web sites and the quantity configuration systems is iCone (Intelligent Environment for
of offered products and services is increasing enormously the Development and Maintenance of configuration knowl-
[2]. This triggered the demand of intelligent techniques that edge bases) [21, 26].1
improve the accessibility of complex item assortments for Based on intelligent techniques to support knowledge engi-
users. Such techniques can be divided into configuration- neers in their maintenance tasks, this paper focuses on fur-
based systems and recommendation systems. When the e- ther aspects in the maintenance of constraint-based configu-
commerce system has highly configurable products (e.g. cars), ration systems and picks up four research aspects (see be-
configuration-based systems can help users to configure the low) for improving existing development and maintenance
product based on their needs. If, on the other hand, the e- environments for constraint-based configuration systems like
commerce system contains many different products, intelli- knowledge-based configuration and recommendation systems.
gent recommendation techniques can help to find the prod- The paper is organized as follows: Section 2 (preliminaries)
uct, which fits best to the user’s needs [16]. We can differen- gives an overview of constraint-based configuration systems
tiate between collaborative systems (e.g., www.amazon.com and a running example. Section 3 contains four aspects of the
[16]), content-based systems (e.g., www.youtube.com [16]), context of constraint-based configuration system development
critiquing-based systems (e.g., www.movielens.org [4]), and and maintenance. Section 3.1 is dealing with simulation tech-
constraint-based recommendation systems (e.g., www.my- niques for constraint-based configuration systems. Section 3.2
productadvisor.com [6]). The favored type of recommenda- shows principles of test case generation based on software en-
tion systems depends on the domain in which the recom- gineering for constraint-based systems. An introduction for
mendation system will be used. For example, in highly struc- assignment-based anomaly management is given in Section
tured domains where almost all information about a product 3.3. Section 3.4 goes beyond maintaining constraint-based
is available in a structured form, critiquing and constraint- configuration systems and takes a look into development pro-
based recommendation systems are often the most valuable
1 http://ase-projects-studies.ist.tugraz.at:8080/iCone
recommendation approach.
39 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
cesses for configuration systems. Section 4 summarizes this whereas for domains with strings we reduce the different types
paper. of relations to =, 6=.
To consider the selection strategy of variables within the
filters, we have to duplicate the variables. For example,
2 Preliminaries if a customer wants to have a notebook for gaming and
In this Section we will describe constraint-based configura- of f ice, we replace the variable usage scenario ∈ V with
tion systems, the terms assignment, consistency, and redun- usage scenario1 ∈ V and usage scenario2 ∈ V with the
dancy, and introduce a short knowledge-based recommenda- same domain in the knowledge base KB. We also have
tion system for notebooks as an example for a constraint- to extend the affected filters in F , such that we have
based configuration system. to replace the affected assignments in the example con-
We use the terminology of constraint satisfaction problems straint usage scenario = gaming → cpu cores > 2 ∈
(CSP) [25] to represent configuration systems. Constraint- FC with the assignments (usage scenario1 = Gaming ∨
based configuration systems are defined as a triple KB = usage scenario2 = Gaming) → cpu cores > 2 ∈ FC .
{V, D, F }. V is a set of product and customer variables. All To check if at least one product fits to the customer’s prefer-
variables have a selection strategy vsel which describes, if a ences, we do consistency checks, s.t. V ∪ D ∪ F 6= ∅. If at least
variable can have more than one value. vsel = singleselect one product in the constraint-based configuration system is
shows that the variable v can have zero or one assignment, e.g. presented to the customer, we can say, that the knowledge
each product has one price, e.g. price = 399. If a variable can base is consistent. Otherwise, the knowledge base contains
have more than one value, we differ between multipleAN D inconsistencies. For dealing with inconsistencies, we refer the
and multipleOR. vsel = multipleAN D points out that a vari- reader to [3, 5, 10, 11, 12, 15].
able can have more than one assignment. For example, a note- If the knowledge base is consistent, we can further evalu-
book can have two wireless connections like bluetooth AND ate whether the knowledge base contains redundancies. A
W LAN , s.t. wireless connectionsel = multipleAN D. On the redundancy is given, if the removal of a constraint from FC
other hand, a customer wants to have a notebook with two leads to the same semantics [15, 20].
OR four cpu cores. We denote such a selection strategy as In the following we describe a notebook domain. The
multipleOR, s.t. cpu coressel = multipleOR. simplified domain is represented as a knowledge-based
Each variable vi ∈ V has a domain dom(vi ) ∈ D that recommendation system.
contains the set of all possible values (not only the assigned
values). Each variable can have zero to n finite assignments. V = {price, cpu cores, usage scenario}
Products FP , customer requirements FR , and constraints pricesel = singleselect
which are defining the relationship between product variables cpu coressel = singleselect
and customer variables FC are in the filter set F . usage scenariossel = multipleAN D
Customer requirements represent the preferences of cus-
tomers in the recommendation / configuration process. The D={
set of customer preferences is denoted as FR . For example, dom(price) = {399, 599, 799, 999},
a customer can have the preference that a notebook should dom(cpu cores) = {2, 4},
be cheaper than 599 EUR, s.t. {price < 599} ∈ FR . Fur- dom(usage scenario) = {of f ice, multimedia,
thermore, customers can be asked for their usage scenarios, gaming}
which might can be multimedia, of f ice, gaming. If a user }
has more than one usage scenario, we duplicate the vari-
able usage scenario for this user, s.t. usage scenario1 = FC = {
multimedia ∧ usage scenario2 = of f ice. f1 := usage scenario = of f ice → (price < 599∧
Constraints which can also be denoted as filters in FC de- cpu cores = 2)
fine the relationship between customer preferences and prod- f2 := usage scenario = multimedia → ((price <
uct variables and are defined in the set FC ∈ F . For example, 999 ∧ cpu cores = 4) ∨ price < 799)
the relationship between the customer’s usage scenario and f3 := usage scenario = gaming → cpu cores = 4
the product attributes is f1 := usage scenario = gaming → }
cpu cores > 2. Additionally, constraint-based recommenda-
tion systems have a set of products. This set is denoted as FR = ∅
FP ∈ F and contains one disjunctive query with all products,
s.t. FP = {product0 ∨ product1 ∨ ... ∨ productn } and each FP = {
product is a conjunctive query of the product variables, s.t. (price = 399 ∧ cpu cores = 2)∨ (p0 )
product0 = {price = 399 ∧ cpu cores = 2}. The aggregation (price = 599 ∧ cpu cores = 4)∨ (p1 )
of customer requirements, constraints, and products represent (price = 799 ∧ cpu cores = 2)∨ (p2 )
the filters, s.t. FR ∪ FC ∪ FP = F . (price = 999 ∧ cpu cores = 4) (p3 )
Each filter can be divided into assignments. An assign- }
ment consists of a variable v, a relationship, and a value d
which is an element of the domain dom(v). The different types F = F C ∪ FR ∪ FP
of relationships depend on the values in the corresponding do-
main. If, for example, the domain consists only of numbers, KB = V ∪ D ∪ F
we can say that the types of relationships are <, ≤, =, 6=, ≥, >
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 40
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
3 Challenges in the Development and Algorithm 1 GibbsSampling
Maintenance of Constraint-based function Gibbs(KB, A): ∆
Configuration Systems CC = ∅ . set of consistency check results {0, 1}
In the following, we describe basic approaches to increase mincalls = 200 . constant
the maintainability, understandability, and functionality of threshold = 0.01 . constant
constraint-based configuration systems. Therefore we use sim- consistent = 0
ulation techniques (Section 3.1), automated test case gener- verif y = Double.M ax V alue
ation (Section 3.2), assignment-based anomaly management while n < mincalls ∨ verif y > threshold do
(Section 3.3), and the consideration of the development pro- randA = A ∪ generateRandAssign(KB)
cess (Section 3.4). F.addAll(randA) . F ∈ KB
if isConsistent(KB) then
consistent + +
3.1 Simulation CC.add(1)
In the context of constraint-based configuration systems else
we use simulation to approximate the number of consistent CC.add(0)
constraint sets compared to the number of all possible con- end if
straint sets. This technique can be used to calculate metrics F.removeAll(randA)
- like the number of valid configurations - or to approximate verif y = verifyChecks(CC)
the dependency between variables [21]. On the one hand we n++
loose minimal accuracy when calculating the possible number end while
of consistent constraint sets whereas, on the other hand, it is return consistent/n
possible to approximate metrics which can not be calculated end function
in an efficient manner. In the following, we describe the basic function generateRandAssign(KB):A
functionality of simulation for constraint-based configuration A=∅ . A: set of assignments
systems and give an example simulation in Figure 1. n = Random(F ∈ KB): . generate n assignments
for i = 0; i < n; i + + do
av = Random(V ∈ KB) . V ∈ KB
ar = Random(Rel)
ad = Random(dom(av ) ∈ D ∈ KB)
A.add(a)
end for
return A
end function
function verifyChecks(CC):∆
CC1 = CC.split(0, |CC|/2)
CC2 = CC.split((|CC|/2) + 1, |CC|)
mean1 = mean(CC1 )
mean2 = mean(CC2 )
if mean1 ≥ mean2 then
return mean1 − mean2
Figure 1. Example simulation for approximated consistency. We else
assume that a high number of consistency checks leads to a repre- return mean2 − mean1
sentative sample of the configuration knowledge base (Law of large end if
numbers). In this example the average number of consistent con- end function
figurations is approx. 50%.
Due to the huge complexity for calculating all possible in- A consistency check is either consistent (1) or inconsistent
stances for all possible assignments in constraint-based con- (0). The number of minimum calls is constant and given in
figuration systems, we use Gibbs’ simulation to estimate the variable mincalls. The total number of consistent checks is
consistency rate coverage for a specific set of assignments A given in the programming variable consistent. threshold is
[22]. An assignment is a filter constraint which contains one a constant and required to test if the current set of consis-
variable av , one domain element ad , and a relationship be- tency checks has a high accuracy. The variable verif y con-
tween variable and domain element ar (see Section 2). Algo- tains the result of the last verification returned by the function
rithm 1 is divided into three functions and shows the basic V ERIF Y CHECKS. If the variable verif y is greater than
algorithm for estimating the consistency rate for a set of as- the threshold, we can not guarantee that the current result
signments. is accurate. In that case we have to execute the loop again.
The function Gibbs(KB, A) is the main function of this In the while-loop we first have to generate a new set of ran-
algorithm. It has a knowledge base KB and a set of as- dom assignments. Since assignments are also special types of
signments A as input. The knowledge base contains sets of constraints, we add the set randA to the set FC ∈ KB and
variables V ∈ KB and filters C ∈ KB (see Section 2). The do a consistency check. If KB with the randomly generated
set CC (checks) contains all results from consistency checks. assignments is consistent, we add 1 to the set CC and incre-
41 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
ment the variable consistent. Otherwise, we add 0 to the set
CC. Finally, we verify all previous consistency checks. If the
variable verif y is lower than the variable threshold and we
have more consistency checks than mincalls, we can return
the number of consistent checks divided by the total number
of checks.
The function generateRandAssign(KB) is responsible for
the generation of new assignments. Random(F ) returns the
number of assignments which have to be generated ran-
domly. This number depends on the number of filters in the
knowledge base, the number of available variables and do-
main elements, since in small knowledge bases it can happen
that we can not generate more than mincalls assignments.
Random(V ) takes a variable from the knowledge base. If the
variable is already part of another assignment, the variable
won’t be used again except the selection strategy vsel is ei-
ther multipleAN D or multipleOR. Random(R) selects a re-
lation between the variable and the domain elements. In our
case, variables can have textual domain elements (e.g. the
brand of a notebook) or numeric domain elements (e.g. the
price of a notebook). While the set of relations for textual Figure 2. Example simulation for approximated consistency
domain elements is Rel = {=, 6=}, the set is extended to
Rel = {=, 6=, <, ≤, >, ≥} for numerical domain elements (see usage scenario = multimedia ∧ cpu cores = 2) and some are
Section 2). Finally, Random(dom(av )) selects a domain ele- consistent (e.g. usage scenario = gaming ∧ cpu cores = 2 =
ment from dom(av ) randomly. inconsistent). We can use the simulation technology (see Sec-
The function verif yChecks(CC) tests if the numbers of tion 3.1) to generate various sets of filter constraints to get
consistent and inconsistent checks are normally distributed. some boundaries. Table 1 shows a list of randomly generated
Therefore, we first divide the set with the consistency check test cases. Note that the number of assignments in the test
results CC into two parts. We evaluate the mean of both sets case can be different (see Algorithm 1).
CC1 and CC2 and test, if both mean values mean(CC1 ) and
mean(CC2 ) are pclose to each other. If they have nearly the tc f ilterconstraint coverage
same values, ( (mean(CC1 ) − mean(CC2 ))2 ≤ threshold), t0 cpu cores = 2∧ 0.50
we can say that the consistent checks are normally dis- usage scenario = of f ice
tributed and return the difference between mean(CC1 ) and t1 cpu cores = 2∧ 0.50
mean(CC2 ). usage scenario = multimedia
t2 price = 799∧ 0.00
In our iCone implementation we use the simulation tech- usage scenario = gaming
nique in three different ways. First, we evaluate the coverage t3 price = 599∧ 0.50
metric which defines the number of consistent configurations usage scenario = gaming
compared to the number of all possible configurations [22]. t4 cpu cores = 4∧ 0.50
Second, we use this technique to generate random assign- usage scenario = multimedia
t5 cpu cores = 4 ∼ 0.54
ments for test cases (see Section 3.2). Finally, we use this
technique to approximate the consistency rate coverage for at Table 1. An example for randomly generated test cases.
least two variables and their domain elements. Figure 2 shows
the probability that the combination of two assignments is The next step is to evaluate these randomly generated
consistent. For example, approximately 100% of the note- boundary test cases according to the domain experts’ knowl-
book configurations are consistent, if the usage scenario = edge. Our example test cases show, that between the test cases
multimedia ∧ cpu cores = 2. t2 and t3 is a boundary because the coverage is different.
After the randomly detected boundaries via simulation we
3.2 Test Case generation have to evaluate the boundary. Such evaluations have to be
done by stakeholders of the knowledge base and can be done
In this Section we want to describe a basic approach to gen- via micro tasks [7]. In this context, several stakeholders can
erate test cases for constraint-based configuration systems. be asked if the results of randomly generated test cases are
In software engineering, boundary value analysis are those valid or not. Such answers can be collected within a case base.
situations directly on, above, and beneath the edges of input Table 2 gives an example case base.
equivalence classes [19]. To use this type of software test- 87.5% of the stakeholders agree that t2 is correct, which
ing in the context of configuration systems, we can say that means that the test case should be inconsistent and the test
the edges are within variable assignments. For example, if case currently leads to an inconsistency. On the other hand,
price = 399 is consistent, price = 599 is consistent too, and 62.5% of the stakeholders think that t3 should not be consis-
price = 799 is inconsistent, the boundary would be between tent. This example represents a conflict between the knowl-
the domain elements 599 and 799. In Figure 2 we can see that, edge engineers’ opinions of the knowledge base. For such sce-
under circumstances, some combinations are inconsistent (e.g. narios we have to offer relevant information to the stakehold-
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 42
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
stakeholder testcase correct? Algorithm 2 AssignmentSequential
s0 t2 yes function AssignmentSequential(KB): R
s1 t2 yes
s2 t2 yes . KB: knowledge base
s3 t2 yes F¯C = ¬f1 ∨ ¬f2 ∨ ¬f3
s4 t2 yes R=∅
s5 t2 no for all f ∈ FC do
s6 t2 yes for all a ∈ A(f ) do
s7 t2 yes
A.remove(a)
s0 t3 no
s1 t3 no if (FC ∪ F¯C )isinconsistent then
s2 t3 yes R.add(a)
s3 t3 yes else
s4 t3 no A.add(a)
s5 t3 no end if
s6 t3 no
end for
s7 t3 yes
end for
Table 2. An example case base for evaluating randomly gener- return R
ated test cases. end function
ers such as mails, forum, and content-based recommendation
[16]. knowledge base (but not from the negation of the knowledge
Finally, a result of the discussion leads to a consistent base) and the combination is still inconsistent, we can say that
knowledge base (filter constraints f ∈ FC have to be updated the knowledge base has kept its semantics and the removed
or removed) which represents the real product domain. If the filter constraint is redundant.
knowledge base has to be maintained, intelligent techniques While the Sequential algorithm removes filter constraint
like the detection of minimal conflicts and diagnoses [21] help by filter constraint from FC , we divide the filter constraint
to detect the causes for the difference between the knowledge into its assignments and remove assignment by assignment.
base and the real world. Therefore, we introduce the set A(f ) which describes the set
of assignments of filter constraint f ∈ FC . When we remove
3.3 Assignment-based anomaly an assignment from A(f ), we next have to consider the rela-
management tions between the assignments. Figure 3 shows the graphical
representation of all filter constraints and their assignments
The anomaly management research describes different ap- in our example knowledge base in a conjunctive order. When
proaches to detect and explain anomalies [21, 26]. For ex- we remove an assignment a from A(f ) we will further replace
ample, QuickXplain can detect conflicts [17], FastDiag finds the upper relation. For example, the removal of the assign-
minimal diagnoses for these conflicts [13], Sequential [20] and ment usage scenario = of f ice of filter f1 replaces the upper
CoreDiag [15] can remove maximal sets of filter constraints implication → with the top node of those elements which will
without changing the semantics of the knowledge base (re- not be connected to the conjunctive constraint. In our case,
dundancy detection). Well-formedness violations can detect this is relation ’∧’.
domain elements which can never be selected (deadelements) Algorithm 2 introduces an approach to detect redundant as-
or have to be selected (f ullmandatories) or can only exit if signments within a knowledge base. The approach is straight
specific domain elements of other variables are selected as well forward: First, we have to generate the negation of F¯C . Then
(unnecessaryref inements) [21]. we select filter by filter. For each filter we remove assignment
While all of these algorithms focus on filters, little at- by assignment a. Finally, we check if the knowledge base with
tention has been paid to the context of assignment-based the changed filter f is still inconsistent with F¯C . If it is incon-
anomaly detection. Compared to constraint-based perspec- sistent, we can say that the removed assignment a is redun-
tives, an assignment-based view can a) find out which assign- dant.
ments within a filter lead to the anomaly and b) detect more Figure 4 shows the redundant assignments of our example
redundancies when one assignment within a filter constraint knowledge base. In the first row we see the original filters
with more than one assignment can not be detected with com- and the result for the usage scenario variable (green box).
mon algorithms. Then we remove assignment by assignment and see the re-
Alternatively, we can check the assignments within a filter sult of the filter constraints in the column result. The yellow
instead of the filter itself for anomalies. Algorithm 2 gives an boxes suggest that the adapted filter constraints lead to the
example for an assignment-based algorithm. This algorithm same semantics as the original knowledge base. We can re-
extends the Sequential algorithm introduced by Piette [20]. move cpu cores = 2 from filter constraint f1 and the assign-
First of all, we have to generate the negation of all filter ments price < 999 and cpu cores = 4 from filter constraint
constraints in the knowledge base. We denote the negation f2 without changing the semantics of the knowledge base.
F¯C and define a disjunctive query of the original knowledge Similar adaptations can also be done e.g., for QuickXPlain
base ¬f1 ∨ 6 f2 ∨ 6 f3 . If the negation of the knowledge base [17], FastDiag [14], and CoreDiag [15]. While these algorithms
in combination with the original knowledge base is inconsis- use a divide and conquer approach based on filters, future
tent, s.t. FC ∪ F¯C is inconsistent, the knowledge base has not research can also consider assignments instead of filters to
changed its semantics. If a filter will be removed from the calculate the anomalies.
43 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Figure 3. Conjunctive query of all filters f ∈ FC in our example knowledge base. In Algorithm 2 we remove assignment by assignment
from the knowledge base and check the consistency instead of the whole filter (f1 , f2 , f3 ).
Figure 4. Results for consistency checks. The columns f1 , f2 , and f3 show the filter constraints when one assignment will be removed.
The first row shows the results (green background) of the original filter constraints. The yellow background suggests, that the removal of
the assignments leads to the same results.
3.4 Constraint-based configuration system base development, a task which is crucial for an effective
development constraint-based configuration system. Next, we want to sum-
marize previous work in the context of knowledge base devel-
opment processes and try to give hints for transferring re-
A lot of research has been done in the maintenance of
search results from the software engineering discipline into
constraint-based systems. For example, we can evaluate the
the knowledge base development research area.
quality of knowledge bases [22] and check if the knowledge
base has anomalies [5, 21]. Therefore, we can evaluate if we
are doing the knowledge base maintenance efficiently.
Less work has been done in the context of knowledge
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 44
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
Development processes for constraint-based software could be done with design patterns. Such patterns
configuration systems can help to reduce the time effort for the realization of a re-
quirement in a knowledge engineering process. For example,
An overview of knowledge base engineering processes is a notebook recommendation system contains products, ques-
given in [9, 24]. tions to customers, and relationships between products and
Common-KADS focuses on different models (organiza- customers (filter constraints). In this domain, products have
tion, task, agent, communication, and expertise) of the knowl- different prices and customers will be asked for their max-
edge base. For example, the expertise model tries to describe imum price. While the product variable product price may
knowledge from a static, functional, and a dynamic view. have hundreds of different prices (domain elements), the cus-
While this system tries to consider all stakeholders, it does tomer will not choose e.g. between product price = 799.90 or
not prioritize the knowledge and does not try to solve con- product price = 799.99 but wants to have for example ten dif-
flicts in the knowledge before it will be transferred into a ferent prices (e.g. customer price ≤ 400 or product price ≤
constraint-based configuration system [23]. 600 or ... or product price ≤ 2200). The relationship between
The MIKE engineering process can be seen as an iterative those variables can be denoted as mapping which could be a
process and is divided into the activities elicitation, interpre- design pattern.
tation, formalization / operationalization, design, and imple-
mentation. The entire development process, i.e. the sequence
of knowledge acquisition, design, and implementation, is per- 4 Conclusion
formed in a cycle inspired by a spiral model as process model.
Every cycle produces a prototype as output which can be eval- In this paper we gave an overview of future research in
uated by tests in the real target environment. The evaluation the context of developing and maintaining constraint-based
of each activity will be done by domain experts. While the configuration systems. Such systems can be constraint-based
result of the implementation activity can be evaluated by do- configuration, knowledge-based recommendation systems, or
main experts, a deep understanding of modelling techniques is feature models. We introduced a simulation technique in the
required to evaluate the results of elicitation, interpretation, context of constraint-based configuration systems, show some
and formalization activities [1]. hints for automatic test case generation and gave an overview
Protege-II is used to model method and domain ontolo- of assignment-based anomaly detection instead of constraint-
gies. A method ontology defines the concepts and relation- based conflicts, redundancies, and well-formedness detection.
ships that are used by a problem solving method for provid- Finally, we showed how requirements engineering and design
ing its functionality. Domain ontologies define a shared con- patterns can be used for knowledge base engineering pro-
ceptualization of a domain. Both ontologies can be reused in cesses.
other domains which may reduce the effort to build-up a new
knowledge base with similar elements [18].
Acknowledgements
Development in the Software Engineering Discipline The work presented in this paper has been conducted within
the scope of the research project ICONE (Intelligent Assis-
Compared to development processes for constraint-based tance for Configuration Knowledge Base Development and
configuration systems we give an overview of actual trends Maintenance) funded by the Austrian Research Promotion
in the engineering of such systems and create a link to the Agency (827587).
currently existing development processes for constraint-based
configuration systems.
A relevant task in software engineering is requirements REFERENCES
engineering. Transferring this aspect into the context of de-
veloping constraint-based configuration systems we can say [1] J. Angele, D. Fensel, D. Landes, and R. Studer. Develop-
that products, product variables, questions to customers, ing knowledge-based systems with mike. Automated Software
Engineering, 5(4):389–418, 1998.
variable domains, and filters can be functional requirements [2] Ivan Arribas, Francisco Perez, and Emili Tortosa-Ausina.
whereas interface development (e.g. to an ERP-system), per- Measuring international economic integration: Theory and ev-
formance, and collaborative development are non-functional idence of globalization. World Development, 37(1):127 – 145,
requirements. When knowledge base engineering processes 2009.
have to be finalized with a given budget and time, we also have [3] David Benavides, Alexander Felfernig, Jos A. Galindo, and
Florian Reinfrank. Automated analysis in feature modelling
to prioritize such requirements. Therefore, we have to rank the and product configuration. ICSR, pages 160 – 175, 2013.
requirements based on their necessity and effort (time and [4] Li Chen and Pearl Pu. Evaluating critiquing-based recom-
budget) for a functional knowledge base. The prioritization mender agents. In Proceedings of the 21st national confer-
should be done by different stakeholders to include as many ence on Artificial intelligence - Volume 1, AAAI’06, pages
157–162. AAAI Press, 2006.
knowledge as possible into the prioritization process. [5] Alexander Felfernig, David Benavides, Jos A. Galindo, and
While many different constraint-based configuration sys- Florian Reinfrank. Towards anomaly explanation in feature
tems will be developed, each of them is developed from models. Workshop on Configuration, pages 117 – 124, 2013.
scratch. Similar to requirements engineering, most of the as- [6] Alexander Felfernig and Robin Burke. Constraint-based rec-
pects of a new knowledge base are new and reuse is not pos- ommender systems: technologies and research issues. In Pro-
ceedings of the 10th international conference on Electronic
sible. On the other hand, several requirements are domain commerce, ICEC ’08, pages 3:1–3:10, New York, NY, USA,
independent. For such requirements, the implementation in a 2008. ACM.
45 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria
[7] Alexander Felfernig, Sarah Haas, Gerald Ninaus, Michael
Schwarz, Thomas Ulz, and Martin Stettinger. Recturk:
Constraint-based recommendation based on human compu-
tation. CrowdRec, June 2014.
[8] Alexander Felfernig, Lothar Hotz, Claire Bagley, and Juha
Tiihonen, editors. Knowledge-based configuration. From re-
search to business cases, volume 1. Morgan Kaufmann, 2014.
[9] Alexander Felfernig, Lothar Hotz, Claire Bagley, and Juha
Tiihonen, editors. Knowledge Engineering for configuration
systems, pages 139 – 155. Volume 1 of Felfernig et al. [8],
2014.
[10] Alexander Felfernig, Florian Reinfrank, and Gerald Ninaus.
Resolving anomalies in configuration knowledge bases. IS-
MIS, 1(1):1 – 10, 2012.
[11] Alexander Felfernig, Florian Reinfrank, Gerald Ninaus, and
Paul Blazek. Conflict Detection and Diagnosis Techniques for
Anomaly Management, pages 73 – 87. Volume 1 of Felfernig
et al. [8], 2014.
[12] Alexander Felfernig, Florian Reinfrank, Gerald Ninaus, and
Paul Blazek. Redundancy Detection in Configuration Knowl-
edge, pages 157 – 166. Volume 1 of Felfernig et al. [8], 2014.
[13] Alexander Felfernig and Monika Schubert. Personalized
diagnoses for inconsistent user requirements. AI EDAM,
25(2):175–183, 2011.
[14] Alexander Felfernig, Monika Schubert, and Christoph Zehent-
ner. An efficient diagnosis algorithm for inconsistent con-
straint sets. AI EDAM, 26(1):53–62, 2012.
[15] Alexander Felfernig, Christoph Zehentner, and Paul Blazek.
Corediag: Eliminating redundancy in constraint sets. In Mar-
tin Sachenbacher, Oskar Dressler, and Michael Hofbaur, ed-
itors, DX 2011. 22nd International Workshop on Principles
of Diagnosis, pages 219 – 224, Murnau, GER, 2010.
[16] Dietmar Jannach, Markus Zanker, Alexander Felfernig, and
Gerhard Friedrich. Recommender Systems: An Introduction,
volume 1. University Press, Cambridge, 2010.
[17] Ulrich Junker. Quickxplain: preferred explanations and relax-
ations for over-constrained problems. In Proceedings of the
19th national conference on Artifical intelligence, AAAI’04,
pages 167–172. AAAI Press, 2004.
[18] Mark A Musen, Henrik Eriksson, John H Gennari, and Sam-
son W and Tu. Protg-ii: A suite of tools for development
of intelligent systems from reusable components. Proc Annu
Symp Comput Appl Med Care, 1994.
[19] Glenford J. Myers, Tom Badgett, and Corey Sandler. The art
of software testing. John Wiley & Sons, 3 edition, 2012.
[20] Cédric Piette. Let the solver deal with redundancy. In Pro-
ceedings of the 2008 20th IEEE International Conference on
Tools with Artificial Intelligence - Volume 01, pages 67–73,
Washington, DC, USA, 2008. IEEE Computer Society.
[21] Florian Reinfrank, Gerald Ninaus, and Alexander Felfernig.
Intelligent techniques for the maintenance of constraint-based
systems. Configuration Workshop, 2015.
[22] Florian Reinfrank, Gerald Ninaus, Bernhard Peischl, and
Franz Wotawa. A goal-question-metrics model for configu-
ration knowledge bases. Configuration Workshop, 2015.
[23] G. Schreiber, B. Wielinga, R. de Hoog, H. Akkermans, and
W. Van de Velde. Commonkads: a comprehensive methodol-
ogy for kbs development. IEEE Expert, 9(6):28–37, Dec 1994.
[24] Rudi Studer, V. Richard Benjamins, and Dieter Fensel.
Knowledge engineering: Principles and methods. Data &
Knowlege Engineering, 25:161 – 197, 1998.
[25] Edward Tsang. Foundations of Constraint Satisfaction. Aca-
demic Press, 1993.
[26] Franz Wotawa, Florian Reinfrank, Gerald Ninaus, and
Alexander Felfernig. icone: intelligent environment for the de-
velopment and maintenance of configuration knowledge bases.
IJCAI 2015 Joint Workshop on Constraints and Preferences
for Configuration and Recommendation, 2015.
Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 46
Proceedings of the 17th International Configuration Workshop
September 10-11, 2015, Vienna, Austria