Knowledge-based configuration tasks are often solved on the basis of constraint programming. Using constraint programming requires technical expertise regarding problem specification and - to some extent - also solution search, for example, in terms of being confronted with the definition of search heuristics. In this paper, we show how to apply database queries to solve knowledge-based configuration tasks. Using this approach, configuration tasks can be defined and solved without the need of integrating a potentially new technology, but rather stick with technical infrastructures (i.e., relational databases) already existing in the company.
Constraint programming (CP) [1] is based on the idea of defining a set of problem variables, variable domains, and related restrictions (constraints) and solving the problem using on a constraint solver. As such, this technology is often used for solving configuration tasks [ 2, 3]. There are further approaches used for configuration knowledge representation. For example, SAT solving [4] is based on the idea of representing a configuration task by set of Boolean variables where each variable represents a variable domain value in the general constraint satisfaction problem, for example, car color red is a domain value of the variable color. In the SAT context, red would be regarded as variable with the domain { , } addition, answer set programming (ASP) is based on a more object-oriented view on configuration knowledge representation [5] where on the reasoning level, ASP . In programs are solved using SAT solvers. ditional expertise in at least one of the areas of constraint programming or SAT solving. Furthermore, additional investments are needed to increase CP-related knowledge of employees which is a major precondition for making underlying technologies applicable for configuration knowledge representation and reasoning. On the other hand, relational database technologies and related
Following the concepts of constraint programming [1], a configuration task can be defined in terms of (1) finite domain variables ∈ = { 1.. } (including the correuct properties and user preferences and (2) constraints )) describing prod0000-0002-1388-4904 (A. Haag); 0000-0002-5024-3786 (S. Lubos) © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License sponding domain definitions ( = ∪ straints and customer requirements
[2].
A simplified example of a car configuration task is the following where type represents the car type, fuel represents the average fuel consumption, skibag indicates the availability of a skibag, and pdc represents a parc distance control feature. In this example, the product domain specific constraints are = { customer requirements are = { 1.. 5} and the 6.. 9} which can be specified in a complete (all variables in have a value) or incomplete fashion.
Representing a configuration task on the basis of a database query allows for the application of relational {( ), (), (), ( )} • • • = { , , , 4 ℎ , } • ( ) = { , , , }. ( ) =
{4, 6, 10}. () (4 ℎ ) = { , }. () = { , }. = → ≠ , = , = → ≠ 10} = ,
9 ∶ = } = { 1 ∶ 4 ℎ = → = ,
4 ∶ = 6 → ≠ , = { 6 ∶ 4 ℎ = ,
7 ∶ = 6, = { , }. 3 ∶ = 4 → 2 ∶ 5 ∶ 8 ∶
database technologies for determining corresponding configurations (solutions). We now introduce a definition of a configuration task on the basis of a database query setting [] (see Definition 1). In this context, can be (1) a set of tables where each table represents one ∈ (“one table per variable” representation), (2) one those variables ∈ representing the projection criteria Implicit configuration space description where each (CSP) variable ∈ is represented by a single table with one attribute and the table entries derived from (
), for example, variable type is represented by the corresponding table type. The corresponding database query has to take into account all constraints in . of the query, i.e., those variable values that should be shown as result of the configuration task.
A configuration task can be defined as database query [] . In this context, represents all possible configurations in tabular form (explicitly or implicitly) and [] represents the selection criteria of the query in conjunctive form, i.e., tributes (variables). In this context, = ∪ ⋀( ∈) . Furthermore, represents the projection at with representing the given customer requirements and representing product domain-specific constraints.
A configuration for the projection attributes (variables) in . configuration task is one tuple of a result of executing a database query [] using the selection criteria in and
Based on Definitions 1–2, we now discuss diferent ways of representing configuration knowledge in a tabular fashion. The chosen type of knowledge representation has an impact on the way the corresponding database query has to be formulated – for demonstration purposes, we will include related examples. (1) “One Table per Variable”.
tation, configuration knowledge is expressed in terms of tables (representing individual CSP variables) – see 2 shows one configuration returned by Query 1. The .1 Table 1We want to assure that at most one tuple is returned by a query – to support this, we assume a query setting such as LIMIT=1 (this is database-specific). configuration includes the pdc feature, i.e., . = (this attribute has not been specified by the user). represents a table that includes all (pre-generated) possible configurations.
values, the query projection has to specify those attributes, for example, since 4wheel, fuel, type, and skibag have already been specified as customer requirements, only pdc needs to be included (see Query 2). 3. S E L E C T * F R O M P
W H E R E ( 4 - w h e e l = y e s ) a n d . . a n d ( s k i b a g = y e s ) . Example Query Optimization. A basic approach to in2. S E L E C T D I S T I N C T p d c . v a l crease query eficiency is to reduce the number of table F R O M t y p e , f u e l , s k i b a g , 4 w h e e l , p d c entries in . For example, instead of having one cenW H E R E ( n o t 4 - w h e e l . v a l = y e s o r t y p e . v a l = x d r i v e ) tralized table, we could introduce one table per car type a n d . . a n d ( s k i b a g . v a l = y e s ) . which is reasonable if the user is sure about the car type selection and just wants to configure the remaining pa
Example Query Optimization. Possibilities of improv- rameters. If we want to generate a table just for the car ing the performance of such queries are (1) to reduce type city, this could be performed on the basis of the variable domains in terms of assuring node consistency query [ ∪{=}] . (e.g., each value of the domain of the variable type must be consistent with each unary constraint referring to (3) “Local Consistency”. An alternative to the prethis variable). (2) queries can be “enriched” by including viously discussed knowledge representations is to use so-called no-goods (conflict sets) [ 6] in negated form – tables that represent local consistency properties. For exthe determination of possible conflicts must also be per- ample, the constraint 1 ∶ 4 ℎ = → = formed in a pre-calculation step. (3) It is also possible to can be represented by a corresponding consistency table further restrict variable (attribute) domains by establish- (variant table [7]) c1 expressing all possible combinations ing arc consistency within a pre-calculation step. of variable values of 4wheel and type as specified by the corresponding constraint 1 (see Table 5). (2) “All Possible Configurations”. Specifically for small configuration problems with a limited configura- Table 5 tion space size there is also the possibility of just enu- Implicit configuration space description representing locally merating all possible configurations and storing those consistent variable value combinations (Table c1) – in this case, configurations in a corresponding table (see, e.g., Table combinations specified by 1 ∶ 4 ℎ = → = . 3). Such an enumeration can be performed on the basis 4wheel type of a database query [ ] where is a table that includes all possible configurations and represents the set of domain-specific constraints.
fuel
2 expressing the possible variable value combinations as defined by constraint 2 (see Table 6). This procedure needs to be performed for each constraint ∈ .
This way, we are able to specify tables fulfilling the property of arc consistency since only variable values are included which are part of at least one tuple included in the corresponding consistency table. Following this knowledge representation, the database query in our car configuration task is the following (see Query 4). type xdrive xdrive .. city
Following this knowledge representation, the database query in the context of our car configuration task is the following (see Query 3). In this example, we again as- 4. S E L E C T * F R O M c 1 , c 2 , . . . sume that includes all CSP variables. Furthermore, W H E R E c 1 . t y p e = c 2 . t y p e A N D . . xdrive xdrive xdrive xdrive city limo limo combi combi yes no yes no no yes no yes no
4. Initial Performance Analysis yes xdrive We compared the performance of the three discussed apyes limo proaches for representing configuration tasks as database yes combi query with constraint solving on the basis of five realno xdrive world feature models [9, 10] selected from the S.P.L.O.T. no limo feature model repository [11]. Table 8 provides an no combi overview of selected feature models. Due to space comno city plexity, not all configurations could be determined for
TTax and FQAs within reasonable time limits.
In this setting, we again assume that includes all For each feature model, we randomly synthesized2 and variables. Furthermore, can be regarded as the table collected 25,000 user requirements that cover 40% of the related to the equi-join of all generated consistency ta- leaf features in the feature model. We applied the systembles, i.e., 1 ⋈ 2 ⋈ 3 ⋈ 4 ⋈ 5 in our case where table atic sampling technique [12] to select 10 no-solution user represents the corresponding constraint ∈ . In requirements and 10 user requirements with at least one this context, join conditions have to be integrated in the solution. In Table 9, each setting shows the average runquery for every combination of consistency tables where time of the corresponding approach after executing the there is an overlap in terms of the included attributes. For queries on the basis of these 20 user requirements. We example, consistency tables 1 and 2 both include the used Choco Solver3 and HSQLDB4 as an in-memory retype attribute. Consequently, 4 ℎ . = . lational database management system. All experiments has to be included as join condition into the query. Table were run with an Apple M1 Pro (8 cores) with 16-GB 7 shows the complete set of (partial) configurations re- RAM, and an HSQLDB maximum cache size of 4GB. turned by Query 4 if we assume that only Tables 1 and Table 9 shows the results of this evaluation of selected 2 have been defined and included into the query. feature models represented as (1) an explicit enumeration of all possible configurations , (2) an implicit representation Table 7 of the feature model configuration space ( one table per Partial configurations determined by Query 4. variable), (3) an implicit representation where individual 4wheel type skibag tables represent local consistency, and (4) constraint satisfaction problem (CSP). Corresponding evaluation results show similar runtimes for small models and significantly longer runtimes for more complex models. Basically, the results of our performance evaluation show the applicability of database query based configuration approaches. yes yes no no no no no no no edge compression can be used and combined to increase database query eficiency. FM IDE DVS DELL MTT FQAs [1] F. Rossi, P. van Beek, T. Walsh, Handbook of Constraint Programming, Elsevier, 2006.
ALLC 0.05 3.66 1.44 - - [2] A. Felfernig, L. Hotz, C. Bagley, J. Tiihonen, OTV 0.49 0.45 2.53 1,448 301,541 Knowledge-based Configuration - From Research COSTPC 00..5713 00..7788 13..0392 17.0149 2220.4,9322 to Business Cases, Elsevier, 2014. [3] U. Junker, Configuration, in: F. Rossi, P. van Beek,
T. Walsh (Eds.), Handbook of Constraint Program5. Threats to Validity ming, Elsevier, 2006, pp. 837–873. [4] J. Gu, P. W. Purdom, J. Franco, B. W. Wah, AlWe have shown how to apply database queries to the gorithms for the Satisfiability (SAT) Problem: A identification of configurations. In a performance analy- Survey, in: DIMACS Series in Discrete Mathematsis, we compared the runtimes of database queries with ics and Theoretical Computer Science, American the Choco constraint solver. Related results show the Mathematical Society, 1996, pp. 19–152. basic applicability of our approach, however, further eval- [5] V. Myllärniemi, J. Tiihonen, M. Raatikainen, uations and optimizations are needed – specifically with A. Felfernig, Using Answer Set Programming for industrial datasets. Our focus in this paper is a discussion Feature Model Representation and Configuration, of basic alternative knowledge representation approaches in: Conf WS’14, Novi Sad, Serbia, 2014, pp. 1–8. that can be used as a basis for defining database queries. [6] U. Junker, QuickXPlain: Preferred Explanations We are aware of related work focusing on compression as- and Relaxations for Over-constrained Problems, in: pects when supporting configuration with variant tables AAAI 2004, 2004, pp. 167–172. – see, for example, Haag [7]. A major issue for our future [7] A. Haag, Managing Variants of a Personalized Prodwork will be to understand the possibilities of knowledge uct, JIIS 49 (2017) 59–86. compression depending on the used knowledge repre- [8] A. Haag, Arc Consistency with Negative Variant sentation. Finally, integrating machine learning with Tables, in: Conf WS’15, Vienna, Austria, 1015, pp. constraint solving is a relevant topic [13] – a major goal 81–87. for future work is to analyze related application poten- [9] D. Benavides, S. Segura, A. Ruiz-Cortes, Automated tials in the context of database queries [14]. Analysis of Feature Models 20 Years Later: A Literature Review, Inf. Sys. 35 (2010) 615–636. 6. Conclusions and Future Work [10] K. Kang, S. Cohen, J. Hess, W. Novak, S. Peterson, Feature-oriented Domain Analysis (FODA) – FeasiWe have introduced a database query based approach to bility Study, Technical Report SEI-90-TR-21 (1990). constraint-based configuration. With this, we provide [11] M. Mendonca, M. Branco, D. Cowan, S.P.L.O.T.: an alternative to approaches such as SAT solving and Software Product Lines Online Tools, in: OOPSLA constraint solving. For sure, further evaluations need to ’09, ACM, New York, NY, USA, 2009, pp. 761–762. be performed and the proposed queries have to be further [12] S. A. Mostafa, I. A. Ahmad, Recent Developments optimized for more complex industrial scenarios. in Systematic Sampling: A Review, Journal of Sta
Open issues for future related work are the following: tistical Theory and Practice 12 (2018) 290–310. (1) further evaluations on the basis of industrial configu- [13] A. Popescu, S. Polat-Erdeniz, A. Felfernig, M. Uta, ration benchmarks, (2) comparison with other knowledge M. Atas, V. Le, K. Pilsl, M. Enzelsberger, T. Tran, representation and reasoning approaches such as answer An Overview of Machine Learning Techniques in set programming (ASP) and SAT solving, (3) performance Constraint Solving, JIIS 58 (2022) 91–118. improvements through parallelization approaches (e.g., [14] R. Guo, K. Daudjee, Research Challenges in Deep [15]), (4) understanding in more detail how constraint- Reinforcement Learning-Based Join Query Optibased reasoning and database queries can profit from mization, in: aiDM’20, ACM, New York, USA, 2020. each other, for example, in which way could forward [15] V. Le and C. Vidal Silva and A. Felfernig and D. Bechecking be applied in database queries and in which navides and J. Galindo and T.N.T. Tran, FastDiagP: way can techniques from relational databases be useful An Algorithm for Parallelized Direct Diagnosis, in: in the context of SAT and constraint solving, and (5) we AAAI-23, 2023, pp. 6442–6449. are interested in which way machine learning and knowl