In this paper I discuss a fundamental difference between positive and negative variant tables (tables listing excluded combinations) from the viewpoint of a modeler. I provide an approach to achieving arc consistency with negative tables that can be integrated into an existing configurator that already implements methods for arc consistency. I also provide a simple necessary condition to test whether a further restriction of given domains is possible using a negative table. As a positive table is equivalent to a negative table representing the complement, this condition test also applies for positive tables that have a small complement. I refer to this process as double negation. A prototypical implementation in Java exists that covers the work described both here and in [6]. I present aggregated results of applying double negation to variant tables from real product test data in [6]. This also validates the overall functional correctness of the entire approach.
Tabular data are an important element of product configuration models. In the context of the SAP Variant Configurator - SAP VC [3] a table that lists valid combinations of product properties is referred to as a variant table. The number of columns of a variant table is called its arity. Each column of the table is mapped to a product property, e.g., Color.
The simplest form of a product model is just as one single variant table. The term variant table derives from this. Table 1, below is an example of a variant table that completely describes the model of a configurable t-shirt by listing all variants. The t-shirt has three properties Color, Size, and Print2. Given the values that appear in the table3 it is evident that 11 of possible 24 combinations have been selected as valid for configuration. I expand on this model in Section 3.
Now, SAP customers have long requested the ability to also maintain tables of disallowed (excluded) combinations of product properties. These would be called negative variant tables.
Whereas, a positive table implicitly defines a bound on the overall (global) domains of the associated properties4, this is different for a negative variant table. There are at least two interpretations of the motivation for maintaining a negative table: 1. The persons maintaining a negative table are aware of overall (global) domains for the affected product properties. The negative form of the table is merely chosen as shorthand for maintaining the complement of an otherwise very large positive table. 1 SAP SE, Germany, email: albert.haag@t-online.de 2 The example is taken from [1]. I use and extend it both here and in [6] 3 I have kept the shorthand codes of M IB (for “Men in Black”) and ST W (for “Save the Whales”) used in [1] 4 That is to say, for a positive table a value that does not occur in a particular table column can be removed from the domain of the property associated with that column
One obvious way of dealing with negative variant tables that pertains to the first case is to provide support for complementing the table with respect to global domains of the product properties at maintenance time5. Note that it is not possible to calculate the complement to the global domains if these are unconstrained6.
I shall focus on the second case as requests by SAP customers clearly indicate this setting. Then, it is not legal to complement a negative table at maintenance time with regard to the global domains even if these are finite, because they may change after the table was maintained. The table may have its own update cycle and should, therefore, not need to be touched each time a global domain changes.
In knowledge-based configuration variant tables function as table constraints. The extensional form of a table constraint (explicitly listing all tuples of values implied by the table) closely corresponds to the relational form of a variant table (directly storing the variant table transparently in a relational database7). Each value aij (where i is the index of the row, and j is the index of the column) that occurs in a table cell states a Boolean proposition pij that the corresponding mapped property vj is assigned to that value (pij j= (vj = aij )). In this case, a row ri in the variant table directly maps to a tuple of propositions i in the associated table constraint representing the 5 If the challenge lies in the large size of the positive variant table, offering maintenance of the table directly in a compressed format is another option. Compressions of Table 1 are depicted in [6]. For the SAP VC some support is provided for complementing tables at maintenance time and maintaining tables in non-extensional form, i.e., with cells containing non-atomic entities such as real-valued intervals or sets of values 6 Unconstrained domains are not that common in traditional business settings, but they do occur. For real-valued numeric properties the global domains may often be (bounded/unbounded) continuous intervals 7 In this case, the table cells will contain only atomic values (Strings or numbers) conjunction of its elements, i.e., for fixed row index i and arity k ri = (ai1; : : : ; aik) and i = (pi1; : : : ; pik) j= pi1 ^ : : : ^ pik.
A central form of constraint evaluation is propagation to achieve arc consistency, which removes any values from the current domains of the properties constrained by the variant table that are not supported in the intersection of the table with these domains. This is a proven way in practice to limit the choices available to the user in interactive configuration. I refer to this simply as constraint propagation in the sequel8.
In this paper, I do not propose an own algorithm for constraint propagation with negative tables9. Rather, I assume that a configurator will already implement constraint propagation for positive tables, but it may not implement a corresponding algorithm (such as [9]) for negative table constraints10.
A tuple representing a disallowed combination of propositions (p1; : : : ; pk) in a negative variant table of arity k allows k obvious inferences: pj1 ^ : : : ^ pjk 1 ! :pjk at run-time. It is important that run-time operations do not impede the overall performance of the configurator. Maintenance-time operations should be performant as well, but this is less critical.
In Section 2, I introduce the notation and some formalisms. Section 3 uses the product model of a t-shirt taken from [1] (Table 1) to illustrate the concepts. As already mentioned, Sections 4 and 5 deal with deriving the necessary condition test and with double negation, respectively. In Section 6, I comment on the status of the implementation. I conclude with some further observations in Section 7.
Finally, a disclaimer: While the motivation for this work lies in my
past at SAP and is based on insights and experiences with the
product configurators there [3, 5], all work on this paper was performed
privately during the last two years after transition into partial
retirement. The implementation is neither endorsed by SAP nor does it
reflect ongoing SAP development.
(
These could be applied at run-time if and where the configurator supports it, e.g., where it is possible to remove a value from a domain in a way that can be represented in the configurator11.
In this paper, I characterize what can be achieved using
preexisting means of constraint propagation beyond (
The condition test rests on the fact that the solution set of a negative variant table with arity k can be easily decomposed at run-time into k + 1 disjoint parts, of which k are in the form of Cartesian products (referred to as c-tuples in Section 2.2). This decomposition is one of the results presented in this paper and applies independently and on top of the methods implemented in the configurator for arc consistency.
A positive variant table can be transformed into a negative one by negating (complementing) it. When processing this negative table the table is logically negated again, yielding an identical solution set, but not an identical structure to the original table. I refer to this as double negation, and discuss it as one possible approach to compression in Section 5. Otherwise, compression of variant tables is a topic I deal with in [6].
I distinguish between information known to the modeler at the time the variant table is maintained (maintenance-time) from information known when configuring the product (run-time). Some calculations can already be performed at maintenance-time, others best 8 I am only concerned with the propagation on each table constraint individually. The question of how to achieve overall arc consistency and how to resolve inconsistencies is up to the methods pre-implemented in the configurator. The SAP VC, for example, does not backtrack, but performs constraint propagation via forward filtering 9 The implementation is part of a prototype for exploring the compression approach in [6]. This also handles negative variant tables, and thus an own approach is implicit in that context 10 If it does implement such an algorithm, then the algorithm itself implicitly involves calculating the complement to the domains known at run-time 11 This will not be the case when the run-time domain is unconstrained, but then all methods of dealing with negative tables referred to cannot be meaningfully applied My scope here is restricted to the problem of constraint propagation with negative tables. I construct a framework for this that is based on operations with sets. After an overview of the basic framework, I define the relevant sets in Section 2.1, and present the actual framework I use for negative variant tables in Section 2.2.
A variant table T is characterized as follows: its arity expresses how many columns it has. The columns are indexed with j : 1 j k, where k is the arity. Each column is mapped to a product property, vj . I assume T to be in relational form, i.e., each table cell contains an atomic value (a string or number). Variant tables that allow intervals or wild cards in cells are not directly representable in relational form. Many of the results here could be extended to cover this case, but I consider it out of scope here.
I view a variant table T in its role as a constraint only12. In the language of constraints the product properties mapped to the columns of the variant table are the constraint variables. I continue to refer to them as product properties. The assumed relational form of the variant table simplifies the correspondence between a table cell aij (where i is the index of the row, and j is the index of the column) and a value assignment vj = aij . Thus each row directly corresponds to a value assignment tuple (v1 = a1; : : : ; vk = ak). In its role as a constraint, each row in T expresses a k-tuple of valid value assignments.
Each product property, vj , has a domain. The domain known at maintenance-time for vj is called the global domain, j , which may be unconstrained (infinite) if unknown (or otherwise infinite as would be the case for a continuous interval). For negative variant tables, I treat global domains as unconstrained, as discussed in Section 1. I refer to a domain known at run-time for vj as a run-time restriction, Rj , even if it also unconstrained or infinite.
I assume that the configurator already implements constraint propagation methods for arc consistency, e.g., implements some form of a GAC algorithm [2, 8]. As a consequence, I do not delve into the details of any particular GAC algorithms here13.
The following example illustrates the concepts introduced so far, albeit for a positive variant table. Examples for negative variant tables are constructed in Section 3. 12 In the SAP VC configurator variant tables are also used in procedural fashion, e.g., in “rules” 13 If the configurator also already implements some form of arc consistency with negative table constraints such as [9], the basic approach will still apply. I shall indicate what differences must then be observed in the appropriate places, below Example 1 Table 1 is a positive variant table of t-shirt variants. Looking at this table, the global domains are fBlack; Blue; Red; W hiteg for the product property “Color”, denoted by v1 fLarge; M edium; Smallg for the product property “Size”, denoted by v2 fM IB; ST W g for the product property “P rint”, denoted by v3 If the customer wants a red t-shirt, but specifies nothing else, then the run-time restrictions are
R1 = fRedg for the product property “Color” R2 = fLarge; M edium; Smallg for the product property “Size” R3 = fM IB; ST W g for the product property “P rint” A GAC algorithm can then further restrict the domains of the property “Size” to fLarge; M ediumg and of the property “P rint” to fST W g. (There are only two rows in the table involving the color “Red”.) 2.1
Let T denote a variant table of arity k for product properties v1 : : : vk. These are the product properties that are related via T as a constraint, and the only properties to consider when looking at T in isolation, but their existence is not directly tied to T . Let 1 : : : k be known global domains of v1 : : : vk. I define the solution space, , as := 1 : : : k
Any subset of the solutions space consisting of valid tuples defines a constraint relation on v1 : : : vk. In particular, ST , the set of valid tuples defined by T , is a subset of . If T is in relational (extensive) form, then ST = T for a positive table, and ST = n T for a negative table. I refer to ST as the solution set of T . Generally, a solution set as defined above may not be finite.
Let = ( 1; : : : ; k) 2 denote a tuple in the solution space. Given any X , I define the j-th column domain of X as j (X) := [ 2X f j g I call j (X) the projection of X onto the j-th component, and define the projection or constraint propagation operator as: (X) := 1(X) : : : k(X)
The complement of a column domain j (X) with respect to a run-time restriction Rj plays a central role in the decomposition in Section 2.2. Hence, I find it convenient to abbreviate its notation as:
R j (X) := Rj n j (X)
For notational convenience I refer to any set C that is a
Cartesian product C = C1 : : : Ck as a c-tuple. All of the
following are c-tuples
itself
(X) the tuple of column domains for in (
R = R1 : : :
Rk
I refer to R as a whole as as a run-time restriction tuple
(
In Example 1 it can be seen that it is possible to eliminate fSmallg and fM IBg after deciding on a red t-shirt. This is the basic inference of arc consistency, which I refer to as constraint propagation: filtering out values that are no-longer part of any valid tuple.
Given a run-time restriction tuple R and a variant table T with solution set ST , then the set of remaining valid tuples is R \ ST .
R\ST by ST ;R = R n T .
I abbreviate the solution set S T ;R. If T is positive, then ST ;R = T \ R. If T is negative, then S
Constraint propagation restricts the run-time restrictions Rj to j (R \ ST ). 2.2
For clarity, I denote a negative variant table by U . I take U to be in relational form and have arity k. The complement of U with respect to (U ) is a positive table constraint that can be calculated at maintenance-time and depends only on U itself. I denote this complement by U
The first part (R n (U )) is just R with the c-tuple spanning all values that occur in U removed. The second part then re-adds all tuples in (U ) that occur both in U and R.
The second part (U \ R) is just the solution set of U ^ R. As U is a positive variant table, this can be processed by the means available to the configurator14.
The first part (R n (U )) can be decomposed into k disjoint
ctuples CU;R as follows (see Proposition 2):
j
Proposition 2 (Rn (U )) in (
j (U )
) xj 2= j (U ) ) x 2= (U ).
Proof Each CU;R is a subset of R by construction.
j The j-th component of CU;R is j (U )R. This is disjoint to j (U ).
j So CjU;R is disjoint to all CpU;R 8j < p k.
No tuple x 2 (U ) is in any CjU;R, because x 2 CjU;R ) xj 2
R
14 If the configurator implements an algorithm for negative GAC such as [9],
then U need not be explicitly calculated. Processing would not be affected
for this part
15 I exclusively use the term disjoint union to refer to a union of disjoint sets
[4]. I denote the disjoint union of two sets A and B by A [ B, which
implies that A \ B = ;
(
R yj 2 j (U ) , and 8p > j : yp 2 Rp.
The decomposition (
I base my examples on the t-shirt model I introduced in Table 1. The global domains are listed in Example 1. In a real application setting, Table 1 would be used as the product model as is. For purposes of exposition here, I assume that the model evolves over time and further colors, sizes, and prints might be added in later model updates along with associated constraints. The restriction to the initial 11 valid tuples in Table 1 implements constraints to the effect that M IB implies
In this section, I use U to denote a negative variant table, and T to denote a positive one. 3.1
The constraint ST W ! :Small in the t-shirt example can be formulated as a single exclusion, yielding a negative variant table U with one row, k = 2, v1 = P rint, and v2 = Size
U =
ST W small As noted, U = ;.
Assume that the restricted domains at run-time are just the global
domains, i.e., R1 = 1 (property P rint) and R2 = 2
(Property Size). Then, the solution set SU;R is directly given by the
decomposition (
C1U;Rr = fM IBg C2U;R = fST W g fLarge; M edium; Smallg 16 Constraint propagation on a solution set in the form of a c-tuple means intersecting the c-tuple with the given run-time restriction tuple R. In a product configuration context the values will most often be ordered. Hence, set operations can use binary search and are relatively efficient 17 The unaffected property Color could take any value. I take this up in Section 3.5 3.2
The constraint M IB ! Black in the t-shirt example could be formulated as three exclusions against the original global domain of the property Color yielding a negative variant table with three rows, k = 2, v1 = P rint, and v2 = Color:
Red 1
Using the global domains given in Example 1, this means that 1(U ) = fM IBg and 2(U ) = fRed; W hite; Blueg: C1U;R = fST W g C2U;R = fM IBg fBlack; Red; W hite; Blueg fBlackg (10)
It still holds that U = ;. So the solution set is still directly given
by the first component in (
If, instead, the domain restriction for v2 at run-time is R2 = fRed; Blueg (but still R1 = 1), then
C1U;R = fST W g C2U;R = ;
fRed; Blueg (= fM IBg
(fRed; Blueg n 2(U )))
The solution set SU;R is now two tuples (ST W; Red) and (ST W; Blue). Constraint propagation produces a domain reduction of R1 to fST W g 3.3
Table U In the sequel, the order of the complete set of constraint variables is v1 = Color, v2 = Size, v3 = P rint.
Let T be the variant table of the t-shirt in its original positive form given in Table 1. T has 11 solutions out of a possible 24. Thus complementing the table with respect to the global domains in Example 1 yields a negative table U with thirteen rows, k = 3, and 0 Black B Red B Red B B Red B BB Red
BBW hite U = BBW hite
BBW hite BBW hite BB Blue BB Blue B@ Blue
ST W 1 M IB C M IB CC M IB CC ST W CC M IB CC M IB CC M IB CC ST W CC M IB CC M IB CC M IB AC ST W Let R1 = 1 (Color), R2 = 2 (Size), and R3 = 3 (P rint). j (U ) = Rj for every j, therefore all j (U )R = ;, and all CjU;R = ;. In this case, T = U , and the tuples in Table 1 are just the solution set. 1 = fBlack; Red; W hite; Blue; Y ellow; DarkP urpleg In this situation 3.4 First, assume that after U in Section 3.3 has been maintained, the global domains of the properties are extended without adding any exclusions (U remains unchanged)18 as follows:
XL and XXL are added to
2 (Size) none is added to
3 (P rint) 2 = fLarge; M edium; Small; XL; XXLg
3 = fM IB; ST W; noneg
Let the run-time domain restrictions reflect the changed global domains R1 = 1, R2 = 2, and R3 = 3. Since U is not changed, (U ) does not change either. It still holds that Hence, U is not changed either (still equal to Table 1), and with 1(U ) = fBlack; Red; W hite; Blueg 2(U ) = fLarge; M edium; Smallg 3(U ) = fM IB; ST W g 1(U ) 2(U ) 3(U )
In this example, both components R n (U ) and U \ R in (
Note that jRj = 6 5 3 = 90, and (looking at (11)) the total number of solutions s for U is s = jC1U;Rj + jC2U;Rj + jC3U;Rj + jU j = 30 + 24 + 12 + 11 = 77 3.4.2
Extending the Constraints
If product management notices that Y ellow does not go with M IB,
then corresponding exclusions must be added to U . This can be done
in several ways. In this example, I assume that Y ellow and the
corresponding exclusions are added before any of the other changes to
the domains are made19. Then, the global domain given in Example 1
for the product property Color, denoted by 1, is augmented by the
18 Leaving U unchanged implicitly changes the underlying positive
constraints. It now no-longer holds that M IB ! black, This is taken to
be an intended consequence of using a negative variant table in a product
model
19 This assumption is made to keep the example simple. The general problem
of achieving a good compression directly from a positive table is addressed
in [6]
value Y ellow, and 2 (Size) and 3 (P rint) remain unchanged.
The following exclusions must be added to U in 3.3:
:(Y ellow; Small; M IB)
:(Y ellow; M edium; M IB)
:(Y ellow; Large; M IB)
:(Y ellow; Small; ST W )
1(U ) = fY ellow; Black; Red; W hite; Blueg
changes, and U changes accordingly. Two values are added to allow
the color of Y ellow in sizes Large and M edium with the print
ST W . So jU j = 13. (11) holds with the modified version of 1(U ).
Again, both components in (
R2 From Sections 3.1 and 3.2 it is clear that the t-shirt table can be expressed in much more compact form by looking at the two constraints in two individual negative variant tables than at the single table in Section 3.3. In both Sections 3.1 and 3.2, the solution set is defined only by the decomposition of (R n (U )) into c-tuples. An overall solution set can be obtained by expanding these solution sets to account for the respective unconstrained property, and then intersecting the resulting two expanded solution sets.
Let the properties be ordered as v1 = Color, v2 = Size, and
v3 = P rint, and the solution space given by the global
domains in Example 1. In Section 3.1 the property v1 = Color is
unconstrained. Set 1(U ) = 1 (which implies 1(U )R = ; for all
R ). Then, the decomposition of R n (U ) in (
R the intersection of the solution sets given by (13) and (14): ST =
C20(ST W ) \ C10(MIB) C20(ST W ) \ C30(MIB) C30(ST W ) \ C10(MIB) C30(ST W ) \ C30(MIB)
The 11 tuples of T are represented as 3 c-tuples. The complexity of this compares favorably with the MDD representation in [1] for the same example. The representation also compares favorably with the compression of the table to c-nodes introduced in [7] if a suitable heuristic is applied. Thus, it should be possible to recover this compact representation from the full table. This is a topic of [6]. 4
Let a negative table U of arity k and a finite run-time restriction tuple R be given. (I assume in the sequel that j (U )R is finite for all columns.)
One approach at arc consistency with U is to use (
Here, I propose an alternative approach based on (
This has a trivial but important consequence:
R Corollary 4 If j (U ) 6= ; for more than one column, then no reduction of domains is possible by constraint propagation using U .
Lemma 3 and Corollary 4 generalize (
R the range of (U ), i.e., j (U ) = ;.
Recall that (U ) is determined when maintaining the variant table, whereas R is only known at run-time.
The examples in Section 3 illustrate that either both or only one
of the components in (
Double Negation of a Positive Variant Table T
In the sequel, I take T to be a positive table. I denote the negation of
T as the negative table :T := (T ) n T . Trimming any run-time
restrictions to (T ), :T (as a negative table) and T have the same
solution space, and constraint propagation on T can be replaced by
constraint propagation on :T . The approach seems advantageous,
if :T has a decomposition of the solution set (
As an example, consider the extended model of the t-shirt as
specified in Section 3.4.2. A representation as a positive table T has 73
tuples (rows) as inidicated there. Negating T against the extended
global domains yields a table :T with 17 rows. :T is just the table
U of Section 3.4.2 (and thus U there corresponds to :T here). Thus,
as outlined there, :T has a decomposition as in (
Double negation is not only an approach at compression for a table with a small complement, but also allows applying Lemma 3 and Corollary 4 as a simple test, before actually evaluating the remaining doubly negated table :T . The process could be iterated, i.e., :T could be doubly negated in turn. A fixed point occurs if T = :T . 6
I have implemented the approach for treating negative tables I describe here, including double negation, within a Java prototype addressing the greater context of compressing and compiling variant tables [6].
As customers so far have not had the opportunity of maintaining negative tables directly in product configuration models, I have no real data to evaluate this approach. Experiences are currently limited to testing for functional correctness. Besides testing with exemplary tables such as variations of the t-shirt, I have applied the double negation approach to 238 SAP VC variant tables. These tables are also the basis for the evaluation of the approach at compression in [6].
Complementing a sparse table is not feasible if the solution space is large. The implementation performs complementation on a representation I term a Variant Decision Diagram VDD, and produces a result in a compressed form (see [6]). I have so far limited attempts at double negation to those of the 238 tables where the number of tuples of the complement is smaller than the number of rows (tuples) in the original (relational) table. The result is given in Table 2. All tables where this criterium does not apply are counted as Skipped. Of the remaining tables where double negation was attempted, those where a reduction was realized (i.e., the VDD of T was larger than that of :T ) are counted as Reduced. The total number of tables in the model and the number of those neither skipped nor reduced are given for completeness.
I give more detailed results of tests with the implementation in [6]. As pointed out there, it is not yet clear whether double negation yields a gain over the general compression approach. this process :T is negated again (:T ), which I refer to as double negation. The purpose of double negation is that it may yield a beneficial (partial) compression of the table, i.e., the table :T may be smaller than T , with the remaining part of the solution set being a set of k c-tuples that additionally allows testing whether constraint propagation is possible at all for a given run-time restriction R. 7
I presented an approach to handling configuration constraints defined by negative variant tables that can be integrated as an add-on to an existing configurator, such as the SAP VC, with little risk. The original mechanisms and architecture of the configurator are not touched.
SAP customers specifically request that a constraint for a negative table not be sensitive to subsequent changes to the global domains of the affected product properties. This approach meets that requirement. As the footnote to the example in Section 3.4.1 points out, this may mean that some implicit positive constraints, valid before a change to the global domains, may no-longer be valid afterwards.
This emphasizes a modeling aspect of the problem: Is it feasible and beneficial to offer the option of negative variant tables as part of the modeling environment in this fashion? This may be a tricky question. The implemented prototype offers a means for experimenting with the functionality, and thus a basis for discussing the merits and demerits of negative variant tables.
One main idea, implicit in the approach, is to make use of the distinction between information known at maintenance-time to the modeler (the table content) and information known at run-time to the configurator (the current domain restrictions). For a negative table U the finite column domains j (U ) can be determined at maintenance time. For a given run-time restriction of the domains R the complements of the column domains to R (denoted by j (U )R) must be calculated at run-time. This calculation is efficient, as the required set-operations can make use of the natural order imposed on the domain values by the business context.
If more than one j (U )R is non-empty at run-time, constraint propagation does not yield a further restriction of the run-time domains. If one j (U )R is non-empty, then only the run-time restriction for that column can be further restricted. When a restriction is possible by constraint propagation, the GAC algorithm only needs to be applied to the positive table U , the complement of U to (U ). The remaining part of the solution set of U is the set-difference between two c-tuples (Cartesian products). I showed in Proposition 2 that such a set-difference can be decomposed into k disjoint c-tuples, where k is the arity of U . Constraint propagation on c-tuples is again based on set operations that are assumed to be efficient, given the value ordering on the domains.
Of course, the approach also applies to the general case that negative tables are merely meant as a short-cut to maintaining an otherwise lengthy positive variant table.
The approach can also be applied to a positive variant table T by negating it, and treating its complement :T as a negative table. In
I would like to thank all that took the time to comment on previous versions of this paper, and have thus contributed to its current form. This includes the anonymous reviewers, but also colleagues at SAP, particularly Conrad Drescher and Andreas Kra¨mer. I tired to incorporate all their suggestions. Any remaining flaws and dis-improvements are solely my responsibility.