Decision modeling is a key aspect in modern BPM complementing and working alongside process models, such as BPMN. DMN is the main standard for decision modeling and in this work we aim to tackle a main drawback of DMNs, namely the lack of optimization techniques in terms of minimizing the execution time and execution cost. We address this limitation through mapping DMNs to PDMs. PDMs are declarative and emphasize on the data input requirements for performing operations to derive additional data elements, one of which is the final target of the process. Moreover, efective optimization heuristics have been proposed for PDMs. We also present two illustrative examples showing the benefits stemming from our approach.
a key and persistent challenge in query processing and data-intensive workflows [ 3, 4].
Organizations are interested in executing their pro- The Product Data Model is a data-centric approach,
taicesses eficiently, in an attempt to remain competitive. lored to information-intensive processes, which are used
To this end, they make use of Business Process Manage- by an array of industries, including insurance companies[5,
ment (BPM). BPM is defined as a body of methods, tech- 1], banking[
Decisions in DMN are usually based on a number of in- could be used to represent the decision logic of processes, put data, which can be the outcome of one or more other originally captured in DMN. Such a conversion would decisions upstream. As such, the decision inputs, espe- make DMN models compatible with the dynamic opticially of intermediate decision tables, are often not avail- mization techniques that have been developed for PDMs. able at the beginning of the process; moreover, there is To this end, we propose an approach to converting a some cost and/or time overhead associated with their ac- DMN model into a PDM one. Our approach produces quisition, e.g., a costly operation needs to be performed a PDM given the Decision Requirement Diagram (DRD) to obtain them. This gives rise to the problem of defining graph and decision table of a process; the resulting PDM the optimal order of acquiring input data and checking is then amenable to optimizations. the corresponding rules in terms of execution time and In summary, our contribution is twofold: (i) the introexecution cost. As explained later, this problem gener- duction of an approach to map DMN decisions and input alizes operator and task ordering optimization, which is data to a PDM and (ii) the provision of example cases to show the benefits that can stem from optimizing the order in which DMN decisions are taken leveraging the same techniques that optimize the operation ordering in PDMs.
The remainder of this paper is structured as follows.
BICOD 2021: The British International Conference on Databases 2021, December 09–10, 2021, London, UK £ kmvarvou@csd.auth.gr (K. Varvoutas); gounaria@csd.auth.gr (A. Gounaris); georkoug@csd.auth.gr (G. Kougka)
© 2021 Copyright for this paper by its authors. Use permitted under Creative CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmmUoRns LWiceonsrekAstthribouptionP4r.0oIncteerenadtiionnagl s(CC(CBYE4U.0)R.-WS.org) Section 2 provides the background and the motivating examples. Next, we introduce our approach followed by discussion of examples. We discuss the additional related work in Sec. 5 and we conclude in Sec. 6.
process models for selecting the best business strategies [9].
In Figure 2, we present the decision table of the claim assignment example. Without explaining the full details at this stage, the outcome of a decision is the rightmost column and depends upon a set of input values, which are represented in the blue-colored fields. Often, these decision inputs are not available upfront, while acquiring each one of them incurs a certain cost. Therefore, aside from finding the correct outcome for a specific set of values, a cost-eficiency issue is encountered. The research question that motivates this work is: what is the optimal order of acquiring the input values and executing the sub-decisions (i.e., rules) of a decision model?
Let us assume for the moment that the hit policy in
The DMN standard complements control flow-oriented initiatives, such as BPMN. It is a declarative approach that models decisions on two levels, the requirements level and the decision logic level. On the first level, the information requirements of the decisions are represented by a decision requirements diagram (DRD). These diagrams Figure 2 is “U”, which means that only one rule may consist of four types of elements: decisions, input data, match as the rule overlapping may lead to an error and business knowledge models and knowledge sources. The the costs of acquiring the four input fields are 3, 2, 2 and 5 decision logic is most commonly expressed with the help cost units, respectively. Given these costs, it seems that of decision tables. In a nutshell, the role of a DMN deci- acquiring the first input regarding the region of the emsion model is to contribute to the business process exe- ployee and the customer with cost 3 is the most eficient cution and provide the requirements that must be pre- choice. But what if, with probability 30%, when acquirserved taking into account the input data [9]. Figure ing the first input, its value is “no”, which implies that no 1 presents the DRD graph of an example claim assign- rule in the decision table can be triggered and additional ment DMN process, where the decisions nodes are Deter- rules need to be checked? To make the case even more mine Employee, Employee appropriateness score and Expe- complex, we also need to account for the fact that checkrience of people, while the input data are represented by ing each rule (i.e., each row in the table) comes with a the DRD nodes Region of customer and employee, Claims cost that potentially difers between rows. To complete expenditure, Number of open claims of employee and Ap- the example, if we assume that in most of the cases the proval authority. In this work, we focus on the case where experience of the employee is high, the open claims are the whole decision process is captured by the DMN model. always more than 10 and each rule has the same cost to As such, in our approach, it sufices to focus on decisions execute, then, in the average case, it is beneficial first and input data solely. to extract the number of the open cases and then define
On the second level, decision tables are used to rep- the final outcome (i.e., the score) based on the retrieved
resent decisions (nodes) that have been specified in the value. This is despite the fact that extracting the
numDRD in detail; an example is presented in Figure 2. Each ber of open cases comes with the highest cost of input
row of a decision table represents a rule, which specifies acquiring, i.e., 5 cost units.
how a decision is taken. The top-left cell specifies the In the example above, we essentially had to determine
hit policy. This policy defines whether one or all rules the most beneficial ordering of operations. However,
need to be triggered, whether rules need to be checked this problem has been investigated in depth in works
in a specified order and so on. such as [
In many cases, the execution of specific decisions can be optimized for a specific decision model. There are cases where the decision inputs can be available with a specific cost and the need arises to define the most cost eficient execution plan for specific input values. Additionally, there are multiple process models that can be generated based on a decision model, which implies the demanding need to introduce a method to “evaluate” the
According to [1], the Product Data Model (PDM) is the
key mechanism to define the process structure of an
informational product, where example informational
products include a decision as to whether to grant approval
to a specific admission request, approval of a mortgage
application, and so on. PDM is used to represent the
structure of a workflow product in a rooted graph-like
manner. One of the most important phases during the
PDM design is the analysis, where the information ele- given quantitative objectives of cost and time? To answer
ments, dependencies and production logic are identified this question, which relates to the execution of PDMs,
[1]. PDMs describe the required elements for generat- the PDM is accompanied by a set of decision strategies
ing the end product of a workflow and a PDM mainly in a method referred to as Product Based Workflow
Supconsists of connected data elements (nodes), which rep- port (PBWS) [
A PDM does not specify per se how the end product typically annotated with quantitative metadata regard(i.e., the root element) is produced, but allows multiple ing the cost and duration of their execution and the probsequences of operations to derive the root information ability of failure to produce a data element. product. In other words, there may be multiple paths Note that optimizing PDM execution is at least as difito the production of the root element. Usually, each of cult as detecting the optimal order of tasks in data-intensive these paths has a diferent cost of execution, giving rise workflows under arbitrary constraints; it is beyond the to the following optimization problem: which paths of scope of this work to provide more details, but this is operations to choose for a specific case in order to optimize due to the fact that task ordering in workflows can be mapped to a PDM, in which each element can be produced via a single operation. As explained in [3], based on the analysis of [11], the task ordering problem in workflows is not only NP-hard but it is unlikely any polynomial algorithm to manage to approximate the optimal solution within a polynomial factor.
ties with regards to their structure and use-cases. Both of them are used to represent information-intensive processes, centered around some type of decision making. Similarities are also apparent when it comes to their execution. Both of these standards feature models that can be directly executed. In such cases, the execution is approached in a dynamic step-by-step manner, which aims to produce the final outcome optimizing a particular objective, i.e. cost of execution. However, while, for PDMs, there is a set of decision strategies available to solve this problem, this is not the case for DMNs. Therefore, by providing an approach that converts DMN models into PDM, we also render the existing decision strategies that are available for PDMs applicable to DMNs.
Require: (1) DRD graph of the DMN as depicted in figure 1. (2) Decision tables of the DMN as depicted in figures 2 and 3. 1: for every element in DRD do 2: if is the top element of DRD then 3: make root element of PDM 4: else if is an input data element of DRD then 5: make leaf element of PDM 6: else 7: make regular element of PDM 8: end if 9: end for 10: for every decision node in DRD with a decision table do 11: convert decision logic of table into PDM operations. 12: end for 13: for every decision node in DRD without a decision table do 14: extract decision logic from DRD. 15: end for 16: for every input data element in DRD do 17: insert a corresponding leaf operation in the PDM. 18: end for 19: return
ing a DMN model into a PDM. Our approach takes as input both the DRD graph and the decision table of a DMN model. We present a high-level algorithmic outline of our approach in Algorithm 1, while also presenting a more detailed outline of each step below.
The first step relates to the graph structure of the model.
Each element of the DRD graph, either a decision or an input node, is mapped to a PDM node. The top element of the DRD is set as the root element of the PDM, while DMN input data elements are mapped to leaf data elements.
The next step is to extract the decision logic from the decision tables, when such tables are available, and the DRD, and convert this logic into the format of PDM operations. Each decision table corresponds to a diferent decision node, and therefore to a diferent PDM node based on the output variable in the table. Each row of a decision table corresponds to a PDM operation, but a single PDM operation may cover multiple decision table rows. Each of these operations produces as output the same output node as defined in the decision table. The 4. Examples input elements of each operation are determined based on the values of their respective column. For example, In this section, we present two DMN models that will we present the decision table of the Employee appropri- be used as examples to showcase our approach. The first ateness score decision node in Figure 2. The second row DMN model has already been introduced in Section 2.1 represents an operation that takes as input the nodes and its DRD graph is presented in Figure 1. It repreClaims Expenditure and Experience of employee (this is because empty columns signify that the respective input data do not play any role in this particular rule). In the corresponding PDM, there would be an operation connecting these two inputs to the output node, where the output node would correspond to the appropriateness score data element.
In addition, when a decision node does not have a corresponding decision table, the decision logic used for its production is captured by the DRD exclusively. In such a case, we take into account the incoming edges of the decision node. The decision logic then is transformed into an operation that produces the decision node as output and takes as input the nodes which are connected to it (via the DRD edges).
Finally, for each input data node in the DRD, a leaf operation (i.e operation with no input elements) is added to account for the production (acquisition) of its corresponding data element in the PDM.
This process is summarized in Algorithm 1 and is polynomial in the size of DRD and the entries of DMN decision tables.
DRD graph is presented in Figure 5 and it consists of eight decision nodes and a single input data node. Fig4.1.1. First example. ure 6 presents the decision table of the Income Tax deci
Figure 2 presents the decision table of the Employee sion node, which constitutes the outcome (top-decision) appropriateness score decision node as already explained. of the model. As previously we assume that it sufices In addition, Figure 3 presents the decision table of the a single rule to be triggered for the final decision to be Experience of Employee decision node. taken. The resulting PDM model is presented in Figure 7.
The resulting PDM model after applying our approach It contains nine data elements and thirteen operations. is presented in Figure 4. It contains eight data elements Op01 aims to produce i9, which, through Op02-Op04 and ten operations, presented in detail in the upper and and Op06,Op07 produces the data elements i6-i8 and i3,i4, lower tables of Figure 4. The operation costs in the bot- respectively. Op05 derives i2 through combining i6,i7. tom table in the figure are assumed to be either extracted Similarly, Op8 produces i5 through combining i8,i9. from logs or provided by a domain expert. The five remaining operations all produce data ele
Regarding the operations of the PDM, we take into ac- ment i1, which represents the decision node Income Tax.
count both the decision table and the DRD of the DMN. These operations are derived from the decision table in
The three operations Op05, Op06 and Op07 that produce Figure 6. More specifically, we group the rows that share
data element i5, which corresponds the decision of the the same attributes in the table into common operations.
Employee appropriateness score, are derived from the de- Therefore, the first two table rows yield Op13, which
cision table presented in Figure 2. The first row of the ta- takes i2 as inputs and produces i1. The third, fourth and
ble corresponds to an operation that takes as input data last row of the table correspond to three distinct
operelements i1 and i2. Rows 2 to 4 are bundled (i.e., knot- ations, namely, Op09, Op10 and Op11, respectively.
Fited) together into a single operation that takes as input nally, the fith and sixth table rows are mapped to Op12.
elements i3 and i7. Finally, rows 5 to 7 are bundled
together into a single operation that takes as input element 4.2. Optimization of the execution
i4. The operation Op08 that produces element i7, which
represents the decision node Experience of Employee, is The main motivation behind mapping DMNs to PDMs
derived from the corresponding decision table in Figure is to enable optimizations, which refer to the ordering in
3. The table’s three rows are reduced into a single oper- which operations are executed and thus data elements
ation that takes as input element i6. Decision node De- are produced. In this section, as a proof of concept, we
termine Employee, which is represented by data element execute the two example PDMs discussed above. The
i8, does not have a corresponding decision table. There- optimized execution is based on the heuristic decision
fore, the operation that produces this element is derived strategies discussed in PBWS [
From the example above, we see that making informed
decisions can yield cost reduction by a factor more than
is detailed in [8] and takes into account the full path from 2X even in simple cases. Mapping DMNs to PDMs
alan operation to the production of the root element with- lows us to benefit from the existing state-of-the-art
optiout performing an exhaustive search of alternatives. The mizations regarding operation ordering in PDMs. These
execution paths (i.e., operation orderings) of the three optimizations include more heuristics, but based on the
strategies are presented below: evidence in [8], on average, the rank-based ones are the
better performing ones.
1. Random: 02, 03, 04, 01, 07, 05, 09, We now go a step further and we conduct a bigger
ex 10. Total Cost: 45 periment, where we simulate 10,000 random cases, where
2. Lowest Cost: 02, 01, 03, 04, 05, 09, each operation is randomly assigned a cost value in the
10. Total Cost: 37 range of [0,10] following a uniform distribution. Figure 8
3. Ranked-Cost: 02, 01, 05, 10. Total Cost: presents the results of the execution in terms of average
21 cost of execution per case. The left chart corresponds to
the claim assignment example, while the right chart
corresponds to the tax management example. In the former
37.4
26.66
42.69
32.2
6. Summary
case, a random choice after each operation execution
incurs 2.4X higher cost compared to the rank-based
heuristic in the average case; the diference shrinks in the
second example but is still significant ( > 35%). It should be
noted that such a performance gain is in line with the
results of former optimization use cases of PDM found
in industry [
In this work, we discuss mapping DMN decisions and input data to a PDM model, the execution of which can be optimized in a cost-based manner. Apart from showing the connection between diferent decision models, we enable optimizations regarding the ordering in which data elements are produced and rules leading to the final decision are fired. Through illustrative examples, we show that the cost gains can be significant; thus map5. Related Work ping DMNs to PDMs amenable to optimizations aspires to open new directions in the manner business processes
In the area of decision modeling, a lot of attention are optimized. In the future, we aim to explore these
dihas been placed on the separation of (decision) logic from rections in more depth, covering also BPMN models.
business processes. The work in [14] presents a formal- Acknowledgments. The research work was supported
ization of decision requirements with the aim of achiev- by the Hellenic Foundation for Research and Innovation
ing integration between a decision and process model. (H.F.R.I.) under the “First Call for H.F.R.I. Research Projects
In [15], an approach that extracts the decision logic from to support Faculty members and Researchers and the
an existing BPMN process model and obtains the corre- procurement of high-cost research equipment grant”
sponding DMN model is presented. In a similar context, (Project Number:1052, Project Name: DataflowOpt). We
the work in [
Additionally, there is also research that focuses on decision making with the aim of achieving process improve- References ment. The work in [18] presents an approach that relies on data from past executions to make dynamic decisions related to resource assignment and process utilities. We difer in that we make dynamic decisions regarding the order of acquiring input data and execute rules. Finally, our work relates to the proposal in [19], which discusses an automated methodology that derives a BPMN/DMN model from an input PDM workflow. However, we focus on the reverse mapping from DMN to PDM. [1] M. Dumas, M. L. Rosa, J. Mendling, H. A. Reijers,
Fundamentals of Business Process Management,
Second Edition, Springer, 2018. [2] OMG: Decision model and notation (DMN), 2015.
URL: https://www.omg.org/dmn/. [3] G. Kougka, A. Gounaris, A. Simitsis, The many faces of data-centric workflow optimization: a survey, Int. J. Data Sci. Anal. 6 (2018) 81–107. [4] A. Rheinländer, U. Leser, G. Graefe, Optimization of complex dataflows with user-defined functions, ACM Comput. Surv. 50 (2017) 38:1–38:39. 177. tics for product data models, in: Business Process
ing and enacting enterprise decisions, in: Advanced Information Systems Engineering Work[10] B. Rücker, Decision model and notation (dmn) – the new business rules standard. an introduction by example, 2015. URL: http://www.bpm-guide.de
5 4 0 - 3 6 6 1 5 - 6 . 2015, pp. 405–417. A. PDM
mation about the heuristic decision strategies [
in [
An activity is traditionally classified as knockout when its execution leads directly to the completion of its process. This approach takes into account the probability that an activity (i.e., a PDM operation) produces the root element, either directly or indirectly. In the latter case, it is treated as a sequence of operations, starting from that particular operation. More specifically, it relies on a rank function to select the next operation for execution. The rank value of an operation Op is defined as (1) 2016, pp. 169–180. shops - CAiSE 2016 Int. Workshops, volume 249, first two strategies, Random and Lowest Cost are presented thienen, M. Denecker, Consistent integration of decision (DMN) and process (BPMN) models, in: where ( ) is the path from eration directly producing the root. It should be noted
Example: In the PDM in Figure 4, let us assume a state models, in: Advanced Information Systems Engi- where leaf elements i4 and i6 have already been proneering - 27th Int. Conf., CAiSE 2015, volume 9097, 2015, pp. 349–366.
duced. Therefore, operations 2019, pp. 176–188.
cost of: sponds to 07 is: 08, + 08 05, 10, which has els from process execution data, Knowl. Based Syst. (