In this paper we propose to relax finiteness in relational tables and tabular constraints in a controlled way. We preserve the syntactic representation of a row in a table as a tuple of symbols. Some of these symbols refer to an atomic value as usual. Others, which we call quasi-finite symbols (QF-symbols), refer to infinite subsets of an underlying infinite domain. Practical examples for QFsymbols are references to (uncountable) real-valued intervals and wildcards representing countably infinite sets. Our goal is to provide a simple and smooth extension of the tabular paradigm, predominant in business, that is compatible with compression of the table to c-tuples [14] or to a variant decomposition diagram [11], and is amenable to constraint processing, such as local propagation. The approach is based on organizing the QF-symbols pertaining to each product property in a specialization relation [8, 9]. A specialization relation is a partial ordering that expresses specificity of meaning. A QF-symbol can be ignored in the presence of a more special one. To ensure that the sets represented by two distinct QF-symbols pertaining to the same domain are disjoint, we further require that it must be possible to represent the intersection and set-differences of QF-symbols. In order to be able to remove duplicates implicated by a disjunction of QF-symbols from result sets of queries, we require that it is possible to represent their normalized set-union. QF-symbols may refer to any objects as long as the above requirements are met, e.g. regular expressions (unary predicates), rectangles (geometric shapes), etc.
This work expands on a common theme: that data in tabular form is a
natural, non-proprietary medium for communicating between
interrelated business processes within an enterprise, as well as between
enterprises. We focus on mass customization (MC), which we take to
be mass production with a lot size of one. A non-configurable
product, amenable to mass production, can have product variants2. For
example, mass produced ballpoint pens come in several colors, but
are otherwise identical. The offered colors are in a one-to-one
correspondence with the manufactured ballpoint variants. The business
attributes are maintained once for the generic ballpoint pen. Only one
generic bill of materials that covers all possibilities needs to be
maintained. For each variant the value of an additional product property,
color, is needed to determine which ink filling and matching cap is
1 Product Management GmbH, Germany, email:
albert@productmanagement-haag.de
2 We use SAP terminology pertaining to the handling of products and product
variants, citing [
MC adds customization to this setting by placing the emphasis
on individualization, i.e. there will be many variants of a product
and the business is prepared to produce only a single unit of each
one on demand (lot size one). Accordingly, the product properties
that distinguish the variants are central and potentially numerous4.
In other work [
If the domains of all descriptive properties are finite, then the number of variants is finite as well. Leaving the reference to the underlying generic MC product aside, each variant is defined by a value assignment to the properties, which we represent as a relational tuple (r-tuple). If the number of offered variants is not large, these r-tuples can be maintained as rows in a database table or spreadsheet, which then acts as a product model comprised of a single tabular constraint. If desired or needed, this overall variant table can conceptually be split into smaller tables that together form a constraint satisfaction problem (CSP). Each CSP variable corresponds to a product property and each CSP solution to an offered product variant5. We refer to any tabular constraint on product properties as a variant table.
Variant tables are a form of modeling that is very acceptable to
a business. Their downside is that they may not scale with a
growing number of choices for individualization. However, we show in
[
However, infinite domains occur in MC practice, and neither
tables of r-tuples nor classic CSP approaches allow infinite sets. In
this paper we propose to relax finiteness in variant tables, and by
extension in the associated constraint processing, in a controlled way.
3 The SAP tables relevant for configuration are listed in [
However, the reasoning here shows that product variants could be
exclusively expressed in tables in the finite case. The single overall table listing
all variants can be seen the the result of compiling the product model, e.g.
to a decision diagram [
Our goal is to provide a simple and smooth extension of the tabular paradigm that retains its acceptance in business, and, particularly, allows compression to a VDD and c-tuples. We preserve the syntactic representation of a row in a table as a tuple of symbols, while allowing some of these, which we call quasi-finite symbols (QF-symbols), to refer to infinite sets. A symbol for a real-valued interval, which is uncountably infinite by definition, is an example of a QF-symbol. A wildcard symbol that refers to an infinite domain is also a QFsymbol. In contrast, a wildcard for a finite domain is just an alias for the finite set of values. We treat this as “syntactic sugar” and equivalent to the expanded set of values.
The approach we take here is illustrated by example in Section 4 and based on the following ideas6:
Each property domain is defined by a finite set of symbols:
– a finite domain by its values, which we refer to as r-symbols,
– an infinite domain by one or more (disjoint) QF-symbols.
We represent a value assignment to the product properties as a
tuple of symbols. If the tuple contains only r-symbols, it is an
rtuple. If it also contains QF-symbols, we call it a QF-tuple. Both
r-tuples and QF-tuples are interpreted a special cases of a c-tuple,
where an r-symbol in the tuple is treated as a singleton set.
We adapt the concept of a specialization relation from [
Only a finite number of QF-symbols is needed, which can be derived in advance from the product model (e.g. the property domains and the variant tables)7.
Compression to a VDD, and through that to c-tuples, can be done as in the finite case, if we can ensure certain requirements are met.
One difference between a QF-symbol and an r-symbol is that the former still allows choice, i.e. it can be specialized or restricted further when required. The consequence is that some constraints may need to be formulated in non-tabular form, e.g. to express that for two real-valued properties length and width it should hold that: length width. These constraints can be seen as inter-property predicates. Whereas we discuss unary intra-property predicates as QF-symbols, we will not deal with other inter-property predicates in this paper, except to note in passing that restricting real-valued intervals with numeric linear (in)equalities is an established technique (see Section 8.2) that can be smoothly integrated with our intended processing.
We show how configuration queries over variant tables with
QFsymbols can be meaningfully supported. We also believe that the
concept of specialization relations is an important bridge to
constraint processing in general. The idea of defining a specialization
relation via the subset-relation can be inverted: given a set of
symbols from the column of a table that correspond to elements of a
partial order, such that a unique greatest successor and a unique least
common predecessor exists for any two elements, these symbols can
be treated in a like manner to QF-symbols for purposes of queries
and constraint processing, if we are willing to interpret the partial
order as a specialization relation.
6 This extends the simple processing of real-valued intervals and wildcards
proposed in [
As stated, the goal of this work is to smoothly extend the tabular paradigm, not to compete with other dedicated problem solving approaches, and we do not make any such comparisons here. The quasi-finite (QF) approach has not yet been tried in the field. Therefore, we cannot present results. Given that the VDD processing remains syntactically alike to the finite case, and given our positive experiences with specialization relations in other endeavors, we are confident that performance is not the issue. Instead, it will be a primary concern to establish usefulness in practice and evaluate acceptance by the business community.
We summarize a database approach to configuration in Section 2 and the topic of compression to VDDs and c-tuples in Section 3. We illustrate all ideas using an extensive example based on an MC T-shirt in Section 4.
Constructing VDDs from QF-tuples is akin to constructing them from c-tuples. This topic is beyond the scope of this paper. However, we summarize the basic problem of ensuring disjoint c-tuples (QF-tuples) in Section 5.
We look at the motivating examples of QF-symbols and how they meet our requirements in Section 6 in some detail.
We discuss queries to variant tables with QF-symbols in Section 7.
We present our ideas on specialization relations and their relation to constraint processing in Section 8. In particular we show that local propagation works seamlessly.
We also believe that using QF-symbols (and perhaps c-tuples in general) directly in the definition of a product variant has business benefits, which we discuss in Section 9.
We provide a summary and an outlook in Section 10. 2
The easiest MC business setting is when the business offering is a small finite set of product variants actually represented in extensional form in a relational database table or spreadsheet. Even when this is not possible, due to the size such a table would have, tabular constraints can be used to define the valid variants.
The extensional form of a tabular constraint naturally supports
various data queries such as (1) and (2), here formulated in SQL, which
are the most relevant for configuration as discussed in [
The query in (1) returns a result set of all variants matching the user’s criteria9. The k product properties are denoted by v1; : : : ; vk. The variant table is denoted as hvtabi. hRj i denotes a subset of the domain Dj for product property vj . The values of interest to a user when configuring can be communicated in the WHERE clause.
The query in (2) returns the domain restriction for property vj under the WHERE clause.
WHERE hv1i IN hR1i AND : : : hvki IN hRki; (2) 8 While the approach here may be extended to cover further SQL queries, this is beyond the scope of this paper. 9 In the SQL syntax, an IN term in the WHERE clause need not be specified where no restriction is intended. However, for purposes of representing a query condition as a c-tuple (see Section 3), we will substitute Rj = Dj for an omitted IN term
These queries can also be done to further filter the result sets of
previous queries (see [
To sum up: tabular constraints in extensional form can be
evaluated using database queries. In [
The discussion of compression in this section is illustrated with examples using a simple T-shirt in Section 4.
In the finite case a variant can be represented as an r-tuple. If we substitute sets for values in this tuple, the tuple is no longer relational, but represents the Cartesian set of all r-tuples that can be formed as combinations using values from the sets. We call such a Cartesian tuple a c-tuple10. As a tuple we denote it by C = hC1; C2; : : : ; Cki, where Cj Dj and Dj is the domain of the product property vj 2 fv1; : : : ; vkg. As a Cartesian set it would be written as C = C1 C2 : : : Ck.
In the context of the above definition, we don’t care whether an element Cj of a c-tuple is finite or infinite. Note that the set of rtuples represented by a c-tuple is uncountable if one of the sets in the c-tuple refers to a real-valued interval.
The WHERE clause with the k IN operators in (1) and (2) itself describes a c-tuple hR1; : : : ; Rki, which expresses the set of values the user (the problem solving agent) believes in. We will refer to this c-tuple as the query condition. We will allow a query condition to be any c-tuple from our variant domain.
C-tuples offer a way to compress tables. For example, if the set of
all variants is totally unconstrained, this can be represented by a
single c-tuple, which is the Cartesian product of the product domains.
With constraints, there will be more c-tuples, but often a c-tuple
representation is much more compact than the extensional form [
In the case of finite domains, a set of c-tuples can be further
compressed to a decision diagram (DD). We use the form of a Variant
Decomposition Diagram (VDD). As introduced in [
We will call a chain of nodes linked via LO-links an l-chain. If
more than one QF-symbol appears in an l-chain, the QF-symbols
10 We adapt the term from [
Nodes in an l-chain that all have a common HI-link represent the
disjunction of their value assignments and could be merged into one
set-labeled node. In [
A VDD is functionally equivalent to the extensional form of the
table it represents from the perspective of the queries (1) and (2)
relevant for configuration, see [
In [
The simple T-shirt has the three properties Imprint (v1), Size (v2), and Color (v3) with the finite domains: fM IB(Men in Black); ST W (Save the Whales)g fL(Large); M (Medium); S(Small)g fBlack; Blue; Red; W hiteg
Only 11 variants are valid due to constraints that state that M IB implies Black and ST W implies :S(Small). Table 1 is the extensional form of the variant table, which is small enough to be used as the only and definitive representation of the variants for the purposes of both business and configuration. It encodes the underlying CSP as a single tabular constraint.
The query (1) can be used to filter the variants to the set matching any given selection criteria (query condition) hR!; : : : ; Rki. For example, if the user needs a small (S) sized T-shirt, there is only one solution (the first row in Table 1). Alternatively, if a Red T-shirt is desired, there are two variants that satisfy this (eighth and ninth rows), and the domains are restricted as follows: Imprint 2 fST W g, Size 2 fM edium; Largeg, and Color 2 fRedg by applying the query (2) for each property in turn. To illustrate the use of infinite sets, we modify the example to allow an arbitrary user-provided image as an imprint on a white T-shirt. An image is identified at runtime via a file name. The file name must refer to a processable graphic, which is taken to mean that only a jpg or a tiff format can be accepted. Hence, the domain is the infinite set of all legal file names that match the regular expression himg-filenamei = :jpgj :tiff.
We also add a property Scale to capture a factor to be used to scale the image printed on the T-shirt. For the vintage prints MIB and STW we require Scale = 1. For the user-provided images, the scale can be arbitrarily chosen by the user as a floating point number in the range 0:5 to 1 (the interval [0:5; 1:0]).
Table 3 lists the c-tuples needed to describe this setting. The product property Scale has here been placed as the first property v1. The other properties are now v2 (Imprint), v3 (Size), and v4 (Color). 1. We construct a root node 1 labeled hv1; [1:0]i starting with the first c-tuple. This node will be used for both the first and second c-tuples in Table 3. 2. We construct the l-chain (chain of LO-links) for the root node: We pointed out in Section 3 that nodes linked in an l-chain need to have disjoint set labels. This is illustrated here. It will be a problem if we label 2 with [0:5; 1:0] (third c-tuple), because then the value Scale = 1:0 does not allow deciding uniquely for either 1 or 2. So we split [0:5; 1:0] into the two disjoint c-tuples.
[1:0] 3, the target for the HI-link of 1, labeled with hv2; M IBi 4, the target for the LO-link of 3, labeled with hv2; ST W i 5, the target for the LO-link of hv2; himg-filenameii
with 4. It is straightforward to handle the third column for the above three c-tuples: nodes 3, 4, and 5 have their HI-links pointing to nodes 6, 7, and 8, respectively with the labels depicted in Figure 2:
The first of the c-tuples allows only the color Black (node 9).
the third allows only the color White (node 11).
5. It is now trivial to finish the VDD. Node 2 still needs to be processed with respect to the last (fourth) c-tuple. But the columns two to four are identical to those in the third c-tuple. Node 5 was already constructed for this.
We note that we skirted the issue that the product property
Imprint (v2) allows both values from a finite list, e.g. fM IB; ST W g,
as well as arbitrary “additional” values (himg-filenamei). This is not
12 To reduce the size needed to display the graph, the terminal sink ? has
been omitted. Conceptually, it terminates all chains of LO-links. Also, the
nodes 1; 2; : : : n are identified by “n1”, “n2”, : : : “nn”
uncommon in practice where a “standard” solution is modeled with
a predefined finite domain, but additional values are allowed (see
[
Lastly, we informally discuss some exemplary queries. QF queries are the subject of Section 7. The query to Table 1 for small (S) TShirts yielded a result set consisting of one r-tuple (the first row). The domains for the three product properties were restricted to fM IBg, fSg, and fBlackg. The same query condition against Table 4 yields three c-tuples (the first, third and fourth c-tuple). Each of these ctuples in the result set must be intersected with the query condition to eliminate the sizes medium (M) and large (L) that are in the c-tuples but excluded by the query condition. Consequently, the domains for the four product properties are restricted to [0:5; 1:0] fM IB; himg-filenameig, fSg, and fBlack; W hiteg13.
Similarly, the query to Table 1 for Red T-Shirts yielded a result set consisting of two r-tuples (the eighth and ninth row). Against Table 4 the result set consists of one (the second) c-tuple. After intersection with the query condition the four product properties are restricted to [1:0] fST W g, fM; Lg, and fRedg.
Instead, if the query condition simply specifies a file name for a particular image, my-img.jpg, then the last two c-tuples would be the result set. They agree completely except in the first column. As there is no need for the split here (as there was when constructing the original VDD), the two tuples could be combined into one14: h[0:5; 1:0]; himg-filenamei; fS; M; Lg; W hitei 13 Formed by collecting all symbols occurring for each column and calculating the the union. The result of the union of the two intervals is normalized (see Section 6) 14 This reduction is actually required where we want the tuples in a result set to be distinct, i.e. to have been normalized.
The result set intersected with the external condition is then: h[0:5; 1:0]; fmy-img.jpgg; fS; M; Lg; W hitei
If the query formulates the additional restriction Scale 2 [0:25; 0:75], then the result set intersected with the external condition is:
h[0:5; 0:75]; fmy-img.jpgg; fS; M; Lg; W hitei 5
A c-tuple C can be decomposed into its head (the first element C1) and its tail T, which is also a c-tuple. We denote this by C := C1jT: C := hC1; : : : ; Cki = C1jhC2; : : : ; Cki = C1jT (3)
When constructing a (partial) VDD from a list of c-tuples C1; : : : Cm an l-chain for the head (root) node is constructed using the first elements C11; C21; : : : ; Cm1. As discussed in Section 3 and evident from the example in Section 4.2 these elements must be disjoint.
If there are two c-tuples Ci; Ci0 with the same tail, i.e.
Ci = Ci1jT and
Ci01 = Ci01jT then their first elements must be merged to yield one c-tuple
C0 = (Ci1 [ Ci01)jT
We can ensure disjointness of any other pair of c-tuples Ci; Ci0 with differing tails
Ci = Ci1jTi and
Ci01 = Ci01jTi0 by replacing them with the three c-tuples Ca; Cb; Cc in (4) (a c-tuple with an empty element is considered empty and can be disregarded): Ca = (Ci1 n Ci01)jTi Cb = (Ci01 n Ci1)jTi0 Cc = (Ci1 \ Ci01)j(Ti [ Ti0 ) (4)
As the example in Section 4.2 shows, the c-tuple heads show up directly as labels of set-labeled nodes. We already stated that a setlabeled node labeled with a finite set of symbols (r-symbols or QFsymbols) can be expanded to an l-chain of regular VDD nodes. 6
As the discussion in Section 5 and the example in Section 4 make clear, it will be necessary to both split and combine c-tuples when constructing a VDD and result sets. Therefore, we need the following operations on c-tuple elements Cij ; Ci0j pertaining to the same product property vj : set intersection: Cij \ Ci0j set union: Cij [ Ci0j negation with respect to the overall domain: :Cij := Dj n Cij set difference: Cij n Ci0j = Cij \ :Ci0j
For finite sets this is a given. For QF-symbols that are used in the labels of VDD nodes, we must ensure that these operations are well defined and fit in our QF framework.
In the following subsections we look at this in detail for the infinite elements we propose to add:
Unconstrained countably infinite sets Sets of exclusions, particularly finite exclusion sets.
Where the domain underlying negation needs to be made clear we will denote negation as:
:C := CD = D n C We denote a real-valued interval using conventional mathematical notation, e.g. [a; b) for a half-open interval with a closed lower bound a and an open upper bound b. This is the set of all real numbers x such that x >= a ^ x < b. We allow lower and upper infinity, denoted by inf and + inf, with open bounds. A single real number x can be encoded as a singleton interval [x]. All other interval bounds can be open or closed
We define an xnumeric to be a finite list of real-valued intervals representing the union of its elements in a normalized form. Normalized means that the intervals in the list are disjoint, separable, and in ascending order, e.g. the set of intervals f[0:5; 1:0); [1:0]g is disjoint and ascending, but it is not separable. In normalized form it is just [0:5; 1:0]. (Remark: The interval f[0:5; 1:0); (1:0; 2:0]g is separable and thus normalized, because its two intervals are separated by the “gap” of the singleton interval [1:0].)
For xnumerics it is straightforward to ensure normalization. First, any intervals that are non-disjoint or not separable can be merged into one interval. Since the remaining intervals are disjoint, they can be ordered. Hence the union of two xnumeric is just the set union followed by normalization. The intersection is just the list of pairwise intersections. Because the xnumeric is ordered due to normalization, this operation is efficient in the sense that it is not necessary to actually intersect all pairs.
The set union of two intervals is not necessarily again an interval, hence we need the concept of an xnumeric.
The unconstrained xnumeric is the interval ( inf; + inf). The negation of an xnumeric is the set difference to this unconstrained set. It is formed by inverting the finite number of “gaps” between the intervals in the xnumeric. For example :f[0:5; 1:0); (1:0; 2:0]g = f( inf; 0:5); [1:0]; (2:0; + inf)g Remark: a finite set of real number values can be represented as an xnumeric using singleton intervals. All interaction with finite sets is covered by the above operations defined for xnumerics.
An xnumeric is a list of QF-symbols (intervals) representing their set union. A set-labeled node for an xnumeric can be expanded to an l-chain of nodes with interval labels. 6.2
Examples of countably infinite domains are the list of all integers or all strings. This requires that each product property is associated with an immutable datatype. We consider a domain D or any C D to be qualified by a unary predicate (condition) that filters out disallowed values at run-time (e.g. a regular expression for a string). Any value fulfilling the predicate (e.g. any string matching the regular expression) is an acceptable value. Examples for qualifying predicates for an integer datatype are: positive p, even p or odd p.15 15 In the absence of more specialized predicates, htruei is taken as the default predicate.
A unary predicate can be represented by its name (a symbol), which serves as the QF-symbol identifying it. In the example in Section 4.2, we used the notation himg-filenamei to refer to a regular expression for legal file names.
The set operations translate into logical operations for predicates. The union of two infinite sets qualified by predicates 1 and 2 is just a set qualified with the disjunction 1 _ 2. Similarly, intersection translates to 1 ^ 2, and negation to : 1.
Again, we require normalization to reduce a complex logical expression by removing any redundant elements. It has yet to be determined what works best in practice here. From a theoretical view, we might require a disjunctive normal form (DNF). The overall predicate could then be represented as a list (finite set) of conjunctions. A set-labeled node for such a list can be expanded to an l-chain of nodes, as for xnumerics. Each such node would be labeled by a conjunction of predicates, which would be treated as an indivisible QF-symbol.
We must also deal with set unions between finite sets and countably infinite sets. In the example in Section 4, the standard imprints for the T-shirt formed a finite set fM IB; ST W g, but “additional values” were then allowed, which were specified by the QF-symbol himg-filenamei. The domain of the property imprint is just the union of these sets. Generally, the domain D for a product property with a non-xnumeric datatype is D = fF; g := F [ , where F is a finite set of values, a predicate representing an countable infinite set, and both F and respect the datatype assigned to the product property.16 The set-operations then become: set intersection: fF; h ig \ fF 0; h 0ig = fF \ F 0; h ^ 0ig set union: fF; h ig [ fF 0; h 0ig = fF [ F 0; h _ 0ig negation: :fF; h ig := F h i \ :h i set difference: fF; h ig n fF 0; h 0ig = fF 00; :F 0; h i n h 0ig – where F 00 is the finite set F n F 0 [ F n h 0i, and – the finite set :F 0 = F 0h i is an exclusion set of all values in
F 0 that lie in h i (see Section 6.3). 6.3
An exclusion of a value x from a property domain D is a way of stating Dnfxg. It means that x is considered to be invalid, which we will denote by :x. For real-valued domains, exclusions can be directly formulated as xnumerics, e.g., f( inf; x)(x; + inf)g would exclude the real number x. For a finite domain or an xnumeric domain, we can simply positively represent the set D n fxg. For a countably infinite domain, we need further expressiveness. Given a countably infinite domain D for a product property and a finite set of values E D, we introduce an exclusion set :E := ED := D n E. An exclusion set :E can be merged with a unary predicate by removing any values from E that do not satisfy the predicate , i.e. :E \ h i :E is a reduced exclusion set. In order to keep the exposition simple, we will ignore this reduction and denote :E \ h i also by :E.
For two exclusion sets :E; :E0, the required set operations are inverted: set intersection: :E \ :E0 = :(E [ E0) set union: :E [ :E0 = :(E \ E0) negation: ::E = D n (D n :E) = E 16 Ideally, F and will be disjoint. Either F or can be empty. We define the predicate hfalsei to represent the empty set. set difference: :E n :E0 = E0 n E
Finite exclusion sets are needed in order to meet our requirements of negation of finite sets against infinite domains. The concept can also be extended to infinite exclusion sets. Indeed, a negated unary predicate corresponds to such a set. For example, if the set of all prime numbers is represented by the unary predicate hprime pi, the :hprime pi represents exclusion of all prime integers.
In either case, a reference to an exclusion set is treated as a QFsymbol. For example, for a predicate , : is the symbol representing the exclusion of all values in . 7
In the classic finite case, the result set R of the query (1) is a finite set of r-tuples. In the QF framework, it is a finite set of QF-tuples that may contain both value symbols and QF-symbols. A QF-symbol in the result set must be specialized to conform to the the query condition, e.g. by set intersection with the query condition. Problem solving (PS) must expect the remaining degree of non-determinism.
The query (2) contains the keyword DISTINCT. This means any duplicates must be removed from the result set for the particular column (property). We see replacing QF-symbols by their normalized union akin to removing duplicates. Therefore, the symbols in the result set, both QF-symbols and r-symbols, must be replaced by their normalized union, which ensures also that remaining symbols are pairwise disjoint. 8 8.1
Given two QF-symbols 1; 2 for the same CSP variable, we regard
2 to be more special than 1 if 2 denotes a subset of 1. This
leads to a partial ordering (PO) of the symbols that occur in the
variant tables, which we call a specialization relation, introduced and
motivated for another context in [
Problem solving (PS) need not consider an otherwise valid fact in the presence of a more special one (procedural-subsumption property). This property requires the acquiescence of PS. A fact is logically implied by any of its specializations (semanticcompatibility property).
Negation inverts specialization (symmetry-under-negation property).
The facts we deal with in this paper are assignments of r-symbols and QF-symbols to a CSP variable. The PS we consider consists of queries to the table and constraint processing, particularly local propagation of constraints. From the perspective of queries we additionally need to be able to aggregate the result sets into a normalized form, e.g. delete duplicate r-symbols, replace two QF-symbols by a more general one representing their union, etc. We have shown in Section 6 that the QF-symbols we primarily envision meet these requirements.
We can also turn the reasoning around and define a PO of symbols pertaining to the same property domain as a specialization relation if we can show that it has the above properties and if we also guarantee the following: There is a unique symbol ? (false) that is a special of all other symbols. This is a QF-symbol for the empty set.
For any two symbols in the PO, there exists a unique symbol for a greatest common successor/special (the “intersection”). For any two symbols in the PO, there exists a unique symbol for a least common predecessor/general (the “normalized union”)17. There is a unique top-level symbol that represents the entire domain. For any symbol in the PO, there exists a symbol : in the PO, such that the least common predecessor of and : is and the greatest common successor is ?. : denotes the negation of .18 For example, we could arrange images in a PO and declare it a specialization relation, paying some attention to fulfill the requirements in the spirit of the intended PS.
Specialization relations provide some conceptual and practical benefits:
They can be pre-calculated and stored in a graph. This may be more performant than calculating intersections and unions on the fly.
They provide a general concept to adapt PS to QF-symbols: PS must simply be prepared to specialize the assignment of a QFsymbol to a CSP variable.
They generalize to other objects, e.g. shapes, images, taxonomies, etc. 8.2
If a product model contains multiple constraints, local propagation
[
The QF framework fits nicely in this scheme. A c-tuple comprised of finite sets of symbols that may include the normalized union of QF-symbols may be used as a query condition. The domain restrictions that result from the query (2) with this query condition may again contain the normalized union of QF-symbols. The c-tuple formed from the resulting domain restriction for each column can be smoothly propagated to other constraints.
If the product model is entirely made-up of tabular constraints, the local propagation of QF-symbols is covered by our approach. It is also straightforward to include constraints representing numeric linear (in)equalities when propagating real-valued intervals.19 Extending the propagation of QF-symbols yet further is a topic of future work. 8.3
Extending existing problem solvers to deal with QF-symbols, will
require an analysis of the particular methods employed. However, a
17 We had noted that the union of two QF-symbols need not itself be a
QFsymbol. Here, however, it is an advantage to be able to have a least
common predecessor/general representing the union as part of the PO. A more
detailed treatment of specialization relations is deferred to a discussion
using practical examples when they arise.
18 We need “negation” primarily to ensure a “set-difference” operation to
be able to split two symbols into a disjoint triple of symbols as in (4) in
Section 5.
19 This is implemented in the SAP product configurators ([
A product variant is classically defined as an r-tuple, a value assignment to each of its product properties, but this is neither ideal nor sufficient in practice. Some degree of indeterminism in a variant is needed when a variant is to be further specialized in a later business process (e.g., at the customer’s site). For example, a pump may be sold with a connection that fits several different sizes of hoses. The end customer may have to make a manual adjustment for the particular hose they want to attach by cutting off a part of the provided connector. The pump being sold to the customer by the business is a variant of their MC “pump” product that allows further individualization at the customer’s site.
The number of sub-variants can be infinite, e.g. for the frequency a radio receiver may be tuned to. As built, the property Frequency would be described by a list of real-valued intervals for possible reception bands, e.g. f[7:2; 7:45]; [9:4; 9:9]; [11:6; 12:1]g (MHz).
Allowing a variant to be defined by a c-tuple solves the above problem. However, c-tuples that define variants must be distinguished from those that are merely the by-product of compression. This would be an open MC business topic. 10
This work extends a common theme: that data in tabular form is not
only natural for modeling variants, but also a natural, non-proprietary
medium for communicating between interrelated business processes
within an enterprise, as well as between enterprises. Compression of
tables is essential in MC for letting variant tables scale with a
growing number of choices, which production technology now enables
[
We believe the QF framework presented here meets these expectations. The main idea is that problem solving will deal with the QF-symbols representing infinite sets via specialization relations. Instead of exploring the validity of a value assignment of a value (feature) to a variable (product property), the assignment to a QF-symbol can be specialized. A forced specialization to the empty set would invalidate an assignment.
The discussed techniques involving c-tuples and VDDs using QFsymbols has not yet been deployed in practice. The individual ingredients: c-tuples, VDDs, and the management of partial orders (POs) for specialization relations have all been applied with positive results. As already mentioned, the question of how to define practical normalization of predicates is open. However, we believe that the primary open issue is to verify that it actually meets the expectations of MC business. This also includes evaluating the need of integrating with other types of constraints, such as linear (in)equality constraints, and the business value of indeterminism in product variants.
I would like to thank my daughter Laura and the reviewers for their comments, which helped improve this paper considerably.