Currently there is no single dominating technology for building product configurator systems. While research often focuses on a single technology/paradigm, building an industrial-scale product configurator system will almost always require the combination of various technologies for different aspects of the system (knowledge representation, reasoning, solving, user interface, etc.) This paper demonstrates how to build such a hybrid system and how to integrate various technologies and leverage their respective strengths. Due to the increasing popularity of the industrial knowledge graph we utilize Semantic Web technologies (RDF, OWL and the Shapes Constraint Language (SHACL)) for knowledge representation and integrate it with Answer Set Programming (ASP), a well-established solving paradigm for product configuration.
The way large organizations manage their data is subject to
trends. Currently the (industrial) knowledge graph is gaining
popularity [
Knowledge graphs rely heavily on methods and technologies developed by the Semantic Web community. Given the current acceptance in the industry for these technologies it is a good time for the product configuration community to revisit these technologies. In this paper we demonstrate how to use Semantic Web technologies for product configuration and how to integrate them with established solving technologies for product configuration like Answer Set Programming.
Why is the use of open standards and technologies like the
Semantic Web technology stack so important? In our
experience using a configurator with a vendor-specific language for
specifying product configuration problems is the equivalent of
a data silo in data management. It is very hard to switch from
one configurator vendor to another, if both systems use their
own proprietary specification language. Also in the product
configuration community there is currently no standard way
to specify product configuration problems although the topic
of ontologies and product configuration is over 20 years old
(cf. [
In Section 2 we describe the technologies used for this paper. In Section 3 we show how to define a product configurator knowledge base with RDF and SHACL, that allows checking of constraints and interactive solving.
For solving product configuration problems, RDF and SHACL are combined with Answer Set Programming in Section 4. In Section 5 we illustrate how reasoning with OWL can help to integrate the product configuration solutions into the knowledge graph and facilitate reuse of ontologies.
In Section 6 we give a brief overview of the systems used for the examples and in Section 7 we conclude. 2
The proposed approach builds heavily on Semantic Web
standards and technologies. Instance data is represented as RDF
triples, domain models are mapped to domain-dependent
ontologies/vocabularies and queries are formulated in SPARQL
[
The Resource Description Framework (RDF) [
The Shapes Constraint Language (SHACL) [
The OWL 2 Web Ontology Language (OWL) [
An ontology describes things (individuals), sets of individuals (classes), relations between individuals (object properties) and attributes of individuals (data properties). Based on these, OWL provides class and property constructors to define complex classes and properties, e.g., intersection or union of classes. Eventually, with OWL axioms, we can define how classes (and properties) are related to each other, e.g., subclasses, equivalent classes, or disjoint classes.
OWL ontologies can be serialized in one of several syntaxes.
In this paper we use Turtle [
In the Semantic Web, the tasks of (i) constraint validation
and (ii) reasoning are grounded on different semantics. While
the latter usually operates under the Open World
Assumption (OWA) (i.e., a statement cannot be assumed to be false
if it cannot be proven to be true [
Those differences are illustrated in Figure 1 where OWL is used for specifying a cardinality constraint for individuals of type :ElementA allowing them to refer to exactly one module of type :ModuleI only.
ex:elemA rdf:type
Class ex:ElementA is defined to be equal to an
anonymous class having exactly one ex:ModuleI associated
via ex:requiredModule, hence every individual of type
ex:ElementA is only allowed to refer to one specific
module. Even though ex:elemA is violating its cardinality
constraint (because it is associated to more than one module
via ex:requiredModule) an OWL reasoner would not be able
to detect a violation, but instead infers that ex:moduleA and
ex:moduleB are representing the same thing.
2.4
Answer Set Programming (ASP) is a declarative
programming paradigm. Instead of specifying how to find a solution
to a problem in terms of an imperative algorithm, in ASP the
problem itself is specified in the form of a logic program. We
restrict our introduction to ASP to core concepts needed to
understand this paper and refer to [
A program P is a finite set of rules of the form h : - b1 , : : :, bm , not bm+1 , : : :, not bn . where h and b1; : : : ; bm are positive literals (i.e. atoms) and not bm+1; : : : ; not bn are negative literals. An atom is either a classical atom or a cardinality atom. A classical atom is an expression p(t1; : : : ; tn) where p is an n-ary predicate and t1; : : : ; tn are terms. A term is either a variable (whose name starts with an upper-case character or an underscore) or a constant (which can be a number or a string). A literal is either an atom or its default negation not . Default negation refers to the absence of information, i.e. an atom is assumed to be false as long as it is not proven to be true. Thus, ASP makes the Closed World Assumption.
A cardinality atom is of the form l l { a1 : l 11 , : : : , l 1m ; : : : ; an : l n1 , : : : , l no } u u where each structure ai : li1 ; : : : ; lim is a conditional literal in which ai (the head of the conditional literal) and all lij are classical literals, and l and u are terms representing nonnegative integers indicating lower and upper bound. If one or both of the bounds are not given, their defaults are used, which are 0 for l (and for l) and 1 for u (and for u).
H (r) = fhg is called the head of the rule, and B (r) = fb1; : : : ; bm; not bm+1; : : : ; not bng is called the body of the rule. A rule with empty head is a constraint and is used to filter out invalid solutions. A rule with empty body is called fact, its head holds unconditionally in a satisfiable program.
There are several ways to define the semantics of an
answerset program, i.e. to define the set of answer sets AS (P ) of an
answer-set program P . An overview is provided by [
Most ASP systems split the solving process into grounding and solving. The former part produces the grounding of a program, i.e. its variable-free equivalent. Thereby, the variables in each rule of the program are substituted by constants. The latter part then solves this propositional encoding.
To briefly illustrate ASP by means of a small example, consider the following program: triple ("ex: ElementA ", " rdfs : subClassOf ", "ex: Element "). rdfs_subClassOf (Sub , Sup ) :triple (Sub , " rdfs : subClassOf ", Sup ). class ( Sub ) :- rdfs_subClassOf (Sub , Sup ). class ( Sup ) :- rdfs_subClassOf (Sub , Sup ). n_element_types (N) :N = { rdfs_subClassOf (Sub ,"ex: Element ") : class ( Sub ) }. { } 3
This program contains one fact representing an RDF triple3 and two rules that derive new atoms from it. The single answer set of this program is: triple ("ex: ElementA "," rdfs : subClassOf ","ex: Element "), rdfs_subClassOf ("ex: ElementA ","ex: Element "), class ("ex: ElementA "), class ("ex: Element "), n_element_types (1)
PRODUCT CONFIGURATION WITH
SHACL
The following describes the product configuration
terminology from [
Definition 1 (Configuration Model) The (SHACL) configuration model CONFMODEL = (SHAPEGRAPH, RDF) consists of a SHACL shapes graph and an ontology/RDFS schema defining all the used classes and properties in the configuration model.
Definition 2 (User requirements) The (SHACL) user requirements USERREQ = (SHACLCONSTRAINTS, SUBGRAPH) consists of additional SHACL constraints and an initial RDF subgraph.
Definition 3 (Configuration Task) The configuration task CONFIGTASK = (CONFMODEL, USERREQ) represents the input of one concrete configuration problem.
Definition 4 (Configuration) A configuration (solution) of a configuration task CONFIGTASK is an RDF graph, which satisfies the SHACL constraints of CONFMODEL and USERREQ and contains SUBGRAPH of USERREQ as a sub graph.
The configuration model defines the constraints that all configurations must satisfy. The ontology is used to identify the classes and properties relevant for the current configuration task. In a large knowledge graph (RDF store/graph database) there can be thousands of concepts and properties and typically only a small subset is relevant for product configuration. Even within the classes relevant for product configuration not all will be relevant in the current configuration task as the configuration task of large artefacts is typically split into smaller configuration tasks like hardware configuration and software configuration. Although the tasks are separated, the resulting configurations will reside in the same knowledge graph and will be linked, e.g., a hardware component will be related to the required software driver.
In the following we will illustrate the product configuration concepts by means of an example. 3.1
For ease of comparison we use the example of [
In our example domain there may be different types of elements, which are controlled by hardware modules. Each hardware module must be in a frame and a frame must be mounted on a rack. More specifically, the constraints of the domain are: There are four disjoint types of elements (ElementAElementD).
There are five disjoint types of modules (ModuleIModuleV).
There are two disjoint types of racks (RackSingle, RackDouble).
An ElementA/B/C/D requires exactly one/two/three/four ModuleI/II/III/IV respectively, i.e., an ElementB must have only and exactly two ModuleIIs associated via the requiredModule property.
A ModuleV cannot have an element, all other modules must be required by an element (via the requiredModule property).
A RackSingle must contain exactly four frames, a RackDouble must contain exactly eight frames.
A frame must be mounted on a rack.
A frame can contain up to six modules.
A module must be mounted on a frame.
Whenever a frame contains a module of type ModuleII, it must also contain one of type ModuleV.
The ontology of our running example is illustrated in Fig. 2. ex:requiredModule ex:Element ex:Module
The following shows an excerpt of the ontology in turtle format: ex: ElementA rdfs : subClassOf ex: Element . ex: ElementB rdfs : subClassOf ex: Element . ex: ElementC rdfs : subClassOf ex: Element . ex: ElementD rdfs : subClassOf ex: Element . ex: ModuleI rdfs : subClassOf ex: Module . ex: ModuleII rdfs : subClassOf ex: Module . ex: ModuleIII rdfs : subClassOf ex: Module . ex: ModuleIV rdfs : subClassOf ex: Module . ex: ModuleV rdfs : subClassOf ex: Module . # defines the objectproperty relating elements # to their required modules # the cardinality constraints for the objectproperty # are defined with SHACL constraints : requiredModule rdf : type owl : ObjectProperty ; rdfs : domain : Element ; rdfs : range : Module . 3.2
In the subsequent paragraphs, we illustrate some types of
constraints supported by SHACL that are relevant in the
configuration domain and refer to [
Cardinality constraints A typical class of constraints for industrial product configuration problems are cardinality constraints. Whereas in customer product configuration problems simple yes/no or mandatory/optional constraints between components/features are often sufficient, complex cardinality constraints are common in industrial configuration problems, e.g., in our example each element class requires a different number and type of attached module. In SHACL these restrictions can be expressed with qualified cardinality constraints. For example the constraint that each instance of ex:ElementB requires exactly 2 ex:ModuleII can be expressed like this: ex: ElementBRequiredModuleShape a sh: NodeShape ; sh: targetClass ex: ElementB ; sh: property [ sh: path ex: requiredModule ; sh: minCount 2 ; sh: maxCount 2 ; sh: class ex: ModuleII ; ] .
Cardinality constraints are a powerful mechanism of product configuration models. With them it is possible to express mandatory/optional, requires, and part/subpart relationships. Almost all the constraints of our running example can be expressed with cardinality constraints.
Completeness of Taxonomy Typically in a configuration model it is required that every object of a configuration must be an instance of a leaf class in the taxonomy, e.g., if a configuration contains a rack, it must be known whether it is a RackSingle or a RackDouble. In SHACL this constraint can be expressed as: # subclass inheritance disjoint and complete ex: RackSubclassShape a sh: NodeShape ; sh: targetClass ex: Rack ; sh: message "A Rack must be either of type ex: RackSingle or ex: RackDouble " ; sh: xone ( [ sh: class ex: RackSingle ] [ sh: class ex: RackDouble ] ) .
The reason for requiring completeness is that a configuration should be a complete description of all components the configured artefact contains. If the exact type of a component is not known, the solution may be underspecified.
There are some scenarios like ETO (engineer to order) where this restriction does not apply. In these cases some parts of the configured artefact are deliberately left unspecified because it is the task of the engineering department to come up with a solution, e.g., in our example we could add as a SHACL constraint that every rack needs a power supply but let the exact type of power supply unspecified. It is then the task of the engineering department to find a suitable power supply for the given configuration. 3.3
Once we have defined the SHACL configuration model we can use it to check if a given RDF graph is a valid configuration. For example checking the RDF graph consisting of the single triple ex:EB a ex:ElementB . against previously introduced SHACL constraints produces the following validation result:
The resulting configuration of this configuration task is shown in Fig. 3 .
Although that kind of interaction might be sufficient for a domain expert, it is clear that the interactive configuration task shown above can be improved. There are only two points in the configuration task where a decision by the user is required. The first decision is to create an ElementA and the second decision is to choose between an RackSingle and a RackDouble. All other statements could be automatically derived by a reasoner.
Some simple statements can be derived with an RDFS reasoner. For example, ex:F2 a ex:Frame . follows from the fact that ex:F2 is an object in an ex:frame property and this property is defined to have the range ex:Frame.
Other SHACL constraints cannot be repaired by a typical Semantic Web reasoner because they require the creation of new entities. For these cases SHACL rules can be applied. The following example illustrates how SHACL rules could be utilized to "repair" a SHACL constraint violation. This rule creates frames for a rack until the required number of frames was created. ex: RackRuleShape a sh: NodeShape ; sh: targetClass ex: RackSingle ; sh: rule [ a sh: SPARQLRule ; sh: prefixes ex: ; sh: construct """
PREFIX ex: <http :// example . org / confws2018 #> CONSTRUCT { this ex: frame _: new .
_: new a ex: Frame . }
WHERE { } """ ; sh: condition [ sh: not ex: RackSingleFrameShape ] ; ] . 4 SOLVING SHACL CONFIGURATIONS
WITH ASP Unfortunately, SHACL rules are a relatively new concept and there are no rule engines that support backtracking. Therefore one must revert to more established solving techniques for product configuration. For this paper we decided to use ASP.
As a basic proof of concept, we demonstrate the generic translation of SHACL constraints to ASP for concepts needed in the example illustrated in Section 3.1. As such, this demonstration includes only a subset of the SHACL Core Validators [9, Appendix D]. Most of the other validators can be expressed in ASP as well4. 4.1
We represent RDF triples in ASP as instances of the ternary predicate triple, whose arguments are Subject, Predicate, and Object. For convenience, triples of certain RDF predicates are mapped to smaller ASP atoms by a set of projection rules: rdfs_subClassOf (Sub , Sup ) :triple (Sub ," rdfs : subClassOf ",Sup ). a( Instance , Class ) :triple ( Instance ," rdf : type ",Class ). sh_target_class (S, C) :- triple (S, "sh: targetClass ", C). 4 Validators that rely on string operations or data types are difficult to encode in ASP. sh_node_property (NS , PS) :- triple (NS , "sh: property ", PS ). sh_property_shape (PS) :- triple (NS , "sh: property ", PS ). sh_property_shape (PS) :triple (PS , " rdf : type ", "sh: PropertyShape "). sh_property_minCount (PS , Min ) :triple (PS , "sh: minCount ", Min ). sh_property_maxCount (PS , Max ) :triple (PS , "sh: maxCount ", Max ). sh_xone (S, List ) :triple (S, "sh: xone ", List ).
To enable the reasoning component to not only rule out invalid solutions but also explain inconsistencies, we use shacl_constraint_violated atoms in the head of constraints together with SHACL messages to encode explanations in the form of shacl_constraint_violation_message atoms in answer sets: sh_message (S, Msg ) :
triple (S,"sh: message ",Msg ). shacl_constraint_violation_message (I,S, Msg ) :
shacl_constraint_violated (I,S), sh_message (S, Msg ). 4.2
Property shapes specify constraints that need to be fulfilled by nodes that are reached on a SHACL property path, which can be defined in various ways [9, Section 2.3]. These constraints and paths need to be mapped to ASP concepts to enable mapping of ASP constraints to the intended targets of a SHACL property. A subset of these paths is handled by the following encoding: sh_property_path (PS , P) :triple (PS , "sh: path ", P), not sh_path_is_inverse (P). sh_path_is_inverse (P) :- triple (P, "sh: inversePath ", _). sh_property_path_inv (PS , InvP ) :triple (PS , "sh: path ", P), triple (P, "sh: inversePath ", InvP ). shacl_property_target (PS , Trgt ) :sh_property_target_inst (PS , Inst , Trgt ). sh_property_target_inst (PS , Inst , Trgt ) :sh_property_shape (PS), sh_node_property (NS , PS), sh_property_path (PS , P), sh_targetClass (NS , Class ), a(Inst , Class ), triple (Inst , P, Trgt ). sh_property_target_inst (PS , Inst , Trgt ) :sh_property_shape (PS), sh_node_property (NS , PS), sh_property_path_inv (PS , InvP ), sh_targetClass (NS , Class ), a(Inst , Class ), triple (Trgt , InvP , Inst ). 4.3
As an example for a simple SHACL constraint, we provide an encoding for the condition that a value node must be a SHACL instance of a given type (cf. [9, Section 4.1.1]): shape_constraint (S, class , C) :triple (S, "sh: class ", C). shape_constraint_satisfied_inst (I, S, class , C) :shape_constraint (S, class , C), a(I, C). 4.4
Based on the encoding fragments presented so far we are now able to encode detection of cardinality constraint violations (cf. [9, Section 4.2]): shacl_constraint_violated (I,PS) :sh_property_shape (PS), sh_node_property (NS ,PS), sh_target_class (NS ,C), a(I,C), sh_property_minCount (PS , Min ), not Min { sh_property_target_inst (PS ,I,T) }. shacl_constraint_violated (I,PS) :sh_property_shape (PS), sh_node_property (NS ,PS), sh_target_class (NS ,C), a(I,C), sh_property_maxCount (PS , Max ), not { sh_property_target_inst (PS ,I,T) } Max . 4.5
Logic constraints like xone (cf. [9, Section 4.6]) can also be mapped to cardinality constraints: sh_xone_inst (Inst , List ) :- sh_xone (S, List ), sh_target_class (S, Class ), a(Inst , Class ). shacl_constraint_violated (Inst , S) :sh_xone (S, List ), sh_xone_inst (Inst , List ), not 1 { shape_constraint_satisfied_inst ( Inst , List , Constraint , Value ) : shape_constraint (List , Constraint , Value ) } 1. 4.6
Given a translation of the SHACL constraints into ASP we can check if the given RDF graph is a valid configuration, i.e., ASP acts as an implementation of the SHACL validator. To enable solving, an additional generative program is needed. This generative program must be capable of enumerating all possible solutions within a certain scope. The generative program together with the translated SHACL constraints enables us to find a valid configuration, if one exists within the given scope. The following listing shows a generative program capable of enumerating all configurations consisting of racks and frames. The scope is controlled by blank nodes (e.g., _:b1). Every blank node can become a new component within the configuration. bnode ("_:b1"). bnode ("_:b2"). bnode ("_:b3"). bnode ("_:b4"). bnode ("_:b5"). bnode ("_:b6"). configobj (O) :triple (O,"a",C), configclass (C). 0 { triple ( BNODE , "a", "ex: RackSingle ") } 1 :bnode ( BNODE ). 0 { triple ( BNODE , "a", "ex: RackDouble ") } 1 :bnode ( BNODE ). 0 { triple ( BNODE , "a", "ex: Frame ") } 1 :
bnode ( BNODE ). 0 { triple (O1 , "ex: frame ", O2 )} 1 :configobject (O1), configobject (O2 ). % answer set found triple ("_:b1","a","ex: Rack "). triple ("_:b1","a","ex: RackSingle "). triple ("_:b2","a","ex: Frame "). triple ("_:b3","a","ex: Frame "). triple ("_:b4","a","ex: Frame "). triple ("_:b5","a","ex: Frame "). triple ("_:b1","ex: frame ","ex:b2"). triple ("_:b1","ex: frame ","ex:b3"). triple ("_:b1","ex: frame ","ex:b4"). triple ("_:b1","ex: frame ","ex:b5").
After an answer set has been found due to the triple notation it can be directly translated back to an RDF graph. This RDF graph is a solution of the configuration task and satisfies all SHACL constraints. 5
COMBINING SHACL/RDF WITH OWL REASONING So far we have concentrated on closed world reasoning and the unique name assumption for checking and finding configurations. In practice there are applications for CWA/OWA HardwarePart
subpart weight xsd:int and UNA/nUNA. As a use case for open world reasoning we will demonstrate how to reuse an existing ontology for our running example. 5.1
Semantic differences of SHACL and
OWL reasoning Consider the constraint that a single rack has four frames. Due to closed world reasoning the SHACL constraint is violated in the example below. For a OWL reasoner the example is consistent, because OWL adheres to the open world assumption and thus an OWL reasoner would not be able to decide if there is another frame. ex:R1 a ex: RackSingle . ex:R1 ex: frame ex:F1 . ex:R1 ex: frame ex:F2 . ex:R1 ex: frame ex:F3 .
In the next example again a SHACL constraint will be violated, because there are 5 frames associated with a Rack and under the Unique Name Assumption they are all considered different entities. In OWL this example is consistent, because the unique name assumption is not applied and there is no statement indicating that, e.g., ex:F1 and ex:F2 are different entities. ex:R1 a ex: RackSingle . ex:R1 ex: frame ex:F1 . ex:R1 ex: frame ex:F2 . ex:R1 ex: frame ex:F3 . ex:R1 ex: frame ex:F4 . ex:R1 ex: frame other :FA . 5.2
Modeling subpart relations can be surprisingly complicated
(cf. [
hw:subpart
But before we can do that, we have to map the configuration created previously to this Hardware Part ontology. The mapping can be expressed by SHACL rules or a mapping ontology. Taking the latter approach we can hold off on the decision for a concrete implementation strategy. In our example we only have to define the object properties ex:frame and ex:module as subproperties of p:subpart in the mapping ontology. Taking all the ontologies (example, subpart, and mapping) and the racks configuration data into account, an OWL reasoner would (also) entail the subpart relationships depicted in Fig. 5. Depending on the OWL reasoner implementation these entailments are materialised or only inferred for relevant queries. Assuming the weights of the hardware parts themselves are also available (for example through a similar mapping to a product catalogue) we now have all the necessary parts to compute the total weight of all the hardware parts with the above SPARQL query.
Alternatively we could use a similar query to materialise the total weights in the RDF graph: INSERT { ? part p: totalweight ? totalweight } WHERE { {
SELECT ? part ( SUM (? weight ) as ? totalweight ) WHERE {
? part p: subpart */p: weight ? weight .
} GROUP BY ? part } }
Using this mapping approach we can transparently map our instance data with relevant data from other (legacy) information systems via a knowledge graph and thus create a more complete knowledge base. We therefore are able to reuse ontologies like the Hardware Part ontology and the associated SPARQL queries in a modular manner. 6
All the example RDF files, ontologies, ASP and Java programs are available in our open-source git repository5. For manipulating RDF the Apache Jena library version 3.5.06 was used. For checking SHACL constraints we relied on the TopBraid SHACL API version 1.1.07. The SHACL examples can also 5 https://github.com/siemens/ProductConfigurationWithSHACL 6 https://jena.apache.org/ 7 https://github.com/TopQuadrant/shacl ex:F2 ex:F3 a a a ex:F4 a a be checked online interactively by using the SHACL playground8. The SHACL rule example has been implemented in Java. The translation of the SHACL example to ASP is also implemented in Java. For running the ASP programs we used the ASP solver clingo version 5.2.09. The OWL ontologies were edited with the Protégé ontology editor10 version 5.2. The classification example of 5 was verified with the integrated HermiT reasoner. The example was also executed with StarDog version 5.3.011 by using a SPARQL query with activated OWL reasoning. StarDog is a knowledge graph platform for the enterprise. 7
We have used Semantic Web technologies in the past, but
only for specific purposes like data integration [
Because of the lack of backtracking SHACL rule engines, SHACL rules can currently not be used to solve configurations except for trivial examples. A solver for product configuration problems finds a model for the product configuration model. This is not a reasoning task supported by a typical Semantic Web reasoner. The main task for a Semantic Web reasoner is classification and determining consistency12.
Therefore we resorted to ASP for solving the configuration
problem. To demonstrate the feasibility of the approach we
translated the subset of SHACL required to solve our simple
example domain. We will continue to evaluate our approach
on more sophisticated domains e.g. by adding arithmetic
constraints. Because the semantic of SHACL can be defined by
SPARQL and the expressive power of SPARQL [
The main challenge will be the automatic translation of the
SHACL constraints into ASP. In the future we want to adopt
a more generic approach by building on the work already done
for SPARQL and ASP [
An important topic for the future will be how to identify the relevant information for product configuration in the knowledge graph. This includes how to (semi-)automatically identify the parts that are currently available for configuring a 8 http://shacl.org/playground/ 9 https://potassco.org/ 10 https://protege.stanford.edu/ 11 https://www.stardog.com/ 12 A Semantic Web reasoner might eventually produce a model internally for proving consistency, but this is normally not available to the caller of the reasoner. product, how to relate the product configuration ontologies to other relevant ontologies for product line management, enterprise resource planning etc.
This work was partially conducted within the scope of DynaCon (FFG-PNr.: 861263), which is funded by the Austrian Federal Ministry of Transport, Innovation and Technology (BMVIT) under the program “ICT of the Future” between November 2017 and April 2020. More information: https://iktderzukunft.at/en/