Decision Model and Notation (DMN) is a formalism for the representation of knowledge about decision processes. It represents a set of decision rules in an easy-to-understand tabular format, called a decision table. In this paper, we argue that current formal semantics for DMN have certain limitations and we propose a novel formal semantics. Our semantics considers a decision table as a definition. The semantics consists of two components: the first component captures the meaning of one row (rule), and the second component aggregates the meaning of the rules into meaning for the whole table. By choosing the second component in diferent ways, the diferent “hit policies” of DMN (i.e., mechanisms for deciding what happens when multiple rows of the same table are applicable) can be represented. Our semantics can cope better with undefined and unknown values and provides a foundation for forms of reasoning diferent from deriving the output for a given set of inputs.
Decision Model and Notation (DMN) [
In the past, there have been multiple attempts to formalize the semantics of DMN [
In the current DMN formalism, there are two possible ways of going around this issue. Firstly, DMN has a special “null” value, which is used when no rule of a table fires [ 1, p.166]. However, it is also used in various other cases, such as for notANumber, negativeInfinity and positiveInfinity [1, p.104], which makes its meaning not perfectly clear. Moreover, many commercial DMN rule engines allow it in diferent places (e.g., as a value of an input attribute, as a constraint of a row) and implement its behavior diferently. An alternative solution is to simulate non-existing values by introducing a new value, such as “does_not_exist”. This approach brings room for all kinds of mistakes. This special value requires special treatment in each statement where the variable ranges over that value, in other words, it pollutes the domain. Furthermore, this special value should be introduced for each type, breaking the uniform way of treating undefinedness. In both cases, there is a semantic mismatch with FO. This stems from FO’s assumption that every logical constant is total, i.e., has a value. Hence, the introduction of partial attributes requires subtle changes in the current semantics and syntax.
In this paper, we present a general solution for these problems by proposing an alternative semantics for DMN that is declarative, yet, much closer to the intuitive operational understanding of DMN. We define the semantics in two steps: semantics of individual rules, and semantics of a decision table (i.e., a sequence of rules). Individual rules are defined as decision value derivation functions, and decision tables are defined as an aggregate function (corresponding to the hit policy) over values derived by the rows of the table. With this semantics we investigate the proper distinction between undefined (non-existing) values and unknown values in three diferent situations: (i) some attribute is known to be undefined, (ii) it is not known whether an attribute is defined or not, and (iii) it is known that an attribute is defined, but its value is unknown.
The remainder of the paper is structured as follows. First, an overview of the most important related work and issues with current approaches are provided. Next, we present the preliminary version of the novel semantics for DMN. Further, we discuss the benefits and practical applications of our semantics. We close the paper with notes on future work and a conclusion.
Although DMN is a relatively young formalism, quite some theoretical work has already been done. This section provides an overview of the most related ideas to this paper and points out the important diferences.
In [
Another approach is based on defining an input-output relation based on a DMN decision
table and its hit policy. The rule semantics described in [
Finally, the oficial DMN specification [
In this section, we briefly illustrate the three problems discussed in Section 1.
Let us consider the non-realistic simple1 example from Fig. 2 of two tables with unique hit
policy, one of which (2a) has a missing rule and the other one (2b) has overlapping rules for
input value 10. One can argue that these tables should not be considered since they are not
“correct”. But Table 2a will nevertheless provide a sound decision for any combination of input
values except for the missing one, which makes it usable. On the other hand, Table 2b has a
conflict in case = 10, resulting in a clear error. In this paper, we take the simple approach
1Note that our examples do not contain default values, which is allowed by the standard [1, p. 134].
to derive undefined ) for the decision attribute in this case2. We proceed to show that FO is not
well suited for capturing these cases. Following [
( < 10 ⇒ = ) ∧ ( > 10 ⇒ = )
( ≤ 10 ⇒ = ) ∧ ( ≥ 10 ⇒ = )
(1)
(2)
It is not hard to see that these translations do not match the basic intuition in the case when
= 10. Formula (1) is trivially satisfied as both antecedents are false and hence
can take any value. But according to the DMN specification, in this case, should
take the distinguished value null. On the other hand, the formula (2) will be unsatisfiable since
should be both and , which is not possible. This case is not well covered
by the DMN specification, but intuitively there is something wrong with this table due to its
inconsistency. This has to be distinguished from unsatisfiability which is representing impossible
situations (more in Section 5.3). The input-output relation [
Another major issue with the existing semantics of DMN is support for unknown values and
distinction between objective and epistemic relations. The greeting example [
DMN is recognizable for its simple and clean syntax. It supports certain data types described with object symbols, characteristic relations (e.g., the order relation), and characteristic functions (e.g., the addition of numbers). Since our intention is to define a general semantics, we will not focus on a particular data type in this paper, but rather focus on an abstract data type. Definition 4.1. A data type is a triple (, , ) where is a set of objects (object domain), is a set of predicate symbols and is a set of function symbols. Predicate and function symbols have arity denoted as / and /. Function symbols of arity 0 are called object symbols. A data type interprets all predicate and function symbols as: Per predicate symbol / it assigns a relation ⊆ and per function symbol / a function → denoted with . , , and respectively denote projections of , , and of a data type .
The set of all terms for a particular data type is defined as: Definition 4.2. Given a set of function symbols of a data type , the set of all terms over , denoted as (), is defined as: • An object symbol /0 ∈ is a term, • If 1, . . . , are terms and ∈ is a function of arity then (1, . . . , ) is a term.
Based on terms, a DMN expressions are defined as follows.
Definition 4.3. For a given data type we define a DMN value expression as := where is a term from () and constraint expression as: :=(1, . . . , − 1, _, +1, . . . , ) | not :=“ − ” | “ ” | “ ” := | | , (Atom and negation) (Expressions) (Compound) Where is a -ary predicate symbol from applied to − 1 values leaving -th argument unspecified, denoted with “_” (when obvious from the context, “_” is omitted). We call this language ℳ (for DMN constraints). Additionally, [] denotes an FO logic expression obtained by replacing all occurrences of “_” in with the attribute symbol , replacing “ not” with ¬ and “,” with ∨.
Note that only atomic constraints can be negated, negating other DMN constraints is not needed as not = and vice versa, while negating “ − ” would mean that nothing matches this constraint, which would be equivalent to omitting the rule. Following is the example of DMN constraints over the data type of natural numbers.
Example 4.1. Consider the data type of natural numbers equipped with comparison predicates and standard binary functions: = (N, {< /2, > /2, ≤ /2, ≥
/2}, {+/2, − /2, × /2, ÷ /2, 0/0, /1}) We use 1, 2, . . . to denote (0), ((0)), . . . The examples of terms are: 0, (0), 10 × atomic constraint expressions are defined as follows: 5, . . . The := (..) | [..] | (..] | [..) |< |> |≤ |≥ |= An example of an atomic constraint expression is (1..34). When this occurs in a cell below attribute , it expresses the constraint 1 < < 34, while (1..34] expresses 1 < ≤ 34, and similar for the others.
Section 3 demonstrates that current formal semantics are not aligned with the human intuition behind the decision tables. Hence, based on the informal operational understanding of DMN decision tables, we propose a two-step declarative semantics3. First defining the formal semantics of rules individually and then decision tables as the hit policy function applied on the sequence of values produced by all the rules. We start with definitions of rules and tables where a rule corresponds to a row in a DMN table, and a sequence of rules corresponds to the full table. Definition 4.4. For a given sequence ⃗ = ⟨1, . . . , ⟩ of input attributes and a decision attribute : A DMN rule is a pair (⃗, ) where ⃗ is a (finite) sequence of constraint expressions ⟨1, . . . , ⟩ and an value expression. The logical format of is the expression := ← 1[1] ∧ · · · ∧ [] where the left/right hand side of the ← is head/body denoted as ()/(). A DMN decision table is a pair (⃗, ℎ) where ⃗ is a (finite) sequence of rules (for ⃗ and ) and ℎ a hit policy expression.
We intend to define semantics that can cope with undefined input and decision attributes. In order to define a formal model semantics, we need a notion of an interpretation assigning values to the attributes and hit policy functions. But introducing partiality brings the issue of constraining the existence of a value. According to Kleene’s principle of regularity for threevalued logic [6, p.334] comparing an undefined object with anything results in undefinedness. For that reason we extend DMN syntax with two new constraints and (Definition 4.3) with semantics defined in 4.7.
Definition 4.5. Given a data type and set of attribute symbols, a DMN interpretation A over in consists of: • A domain D which is a non empty set [[D]]A = . • Per attribute symbol ∈ an element ∈ [[D]]A or distinguished value ⊥, denoted as [[]]A. • Per hit policy function symbol ℎ an aggregate function [[ℎ]]A that maps the sequence of contributions of the rules into a unique value for the output attribute, as in definition 4.6. 3To preserve simplicity, we restrict DMN decision tables to the simpler form without losing generality in which all attributes are of the same type, decision tables have only one decision attribute and there are only two hit policies. Each DMN constraint expression denotes the (obvious) set [[]]A ⊆ [[D]]A ∪ {⊥}, and each DMN value expression denotes an element from the domain [[]]A ∈ [[D]]A according to the predicate and function symbol interpretations in . Definition 4.7 demonstrates this with the data type of natural numbers .
Definition 4.6. Let ⃗ = ⟨1, . . . , ⟩ be a sequence of values, then: The unique (i.e., exactly one rule matches) hit policy is (⃗ ) = if ∃1 ∈ {1..} : ̸= ⊥ then ∈ ⃗ | ̸= ⊥ else ⊥ (where ∃1 means “exists exactly one”), and sum (i.e., summation of values of all matching rules) hit policy is +(⃗ ) = if (⃗ ⊥) ̸= ∅ then (⃗ ⊥) else ⊥. Where ⃗ ⊥ represents a sequence obtained by removing all values equal to ⊥ from ⃗ .
Definition 4.7. For a given structure A over data type of natural numbers , a DMN value expression denotes an element from domain [[D]]A (in this case N), which is denoted with [[]]A and defined as: if is a object symbol then [[]]A = , if it is a compound term = (1, . . . , ) then [[]]A = (1 , . . . , ). A DMN constraint expression (over ) denotes a subset of [[D]]A⊥ (the domain of A augmented with ⊥, in this case N⊥), denoted as [[]]A. We first define the value of atomic expression : [[[..]]]A ={ | ∈ N ∧ [[]]A ≤ ≤ [[]]A} [[(..]]]A ={ | ∈ N ∧ [[]]A < ≤ [[]]A} [[(..)]]A ={ | ∈ N ∧ [[]]A < < [[]]A} [[⊕ ]]A ={ | ∈ N ∧ ⊕ [[]]A} [[[..)]]A ={ | ∈ N ∧ [[]]A ≤ < [[]]A} [[not ]]A =N ∖ [[]]A where ⊕ ∈ { =, <, >, ≤ , ≥} , and and are value expressions. The value of other DMN expressions is defined as: [[ ]]A = N [[ ]]A = {⊥} [[− ]]A = N⊥ Compound constraint, constructed with “or” operator (in DMN “,”), is defined as: [[1, . . . , ]]A = [[1]]A ∪ · · · ∪ [[]]A
Note that atomic expressions are always specifying a subset of the domain, meaning that each of these constraints carries an assumption that the value exists.
If not stated diferently we assume that each interpretation is over data type of natural numbers . Henceforth data type is not mentioned explicitly in the following definitions.
The semantics of a rule is defined as a function that maps an interpretation of the input attributes to the contribution of the rule, the value for the decision attribute. Definition 4.8. For a given sequence of input attributes ⃗ = ⟨1, . . . , ⟩ and a decision attribute , let = (⃗, ) be a DMN rule with constraint expressions ⃗ = ⟨1, . . . , ⟩ and value expression , and let A be a DMN interpretation (over ⃗ and ), then C(A), the value contributed by in A, is [[]]A when each constraint is satisfied (in A) and ⊥ otherwise; formally:
C(A) = if ∀ ∈ {1..} : [[]]A ∈ [[]]A then [[]]A else ⊥ Finally, the function associated with the hit policy aggregates all contributions of rules into one value.
Definition 4.9. For a given input attributes ⃗ and a decision attribute , let = (⃗, ℎ) be a DMN table with rows and A be a DMN interpretation (over ⃗ and ) then A satisfies table , or A is a model of , (denoted as A |= ) if the value [[]]A equals to the value obtained by applying the hit policy function ([[ℎ]]A) on the sequence of values ⟨C1 (A), . . . , C (A)⟩ derived by rules ( ∈ ⃗) application; formally:
[[]]A = [[ℎ]]A(⟨C1 (A), . . . , C (A)⟩)
In this section, we discuss the results of the proposed model semantics, preliminary ideas,
and future work. The model semantics defined in the Section 4 distinguishes itself from other
approaches in the following aspects:
1. It is straightforward to extend the semantics with new hit policies. Also, it is possible to
define hit policies that are domain-specific (e.g., if rule 3 derives value ≥ 5 take the value
produced by the rule 4 and otherwise the value produced by the rule 5).
2. The distinction between undefined and unknown is made clear (more in Section 5.1).
3. Combining decision tables is straightforward, and tables with missing or overlapping rules
does not require any special treatment (more in Section 5.3).
4. Employing formal reasoning methods is possible and hence solving many diferent
problems without implementing new custom algorithms but rather using existing solvers.
This is the principle of knowledge representation and reasoning as explained in [
One of the main contributions of this paper is the disambiguation of unknown and undefined values of DMN attributes. This subsection provides a detailed discussion on this matter.
We start from the usual DMN task, which is computing the value of the decision attribute for given values of input attributes. Let 1, . . . , be input attributes and the decision attribute of the DMN table . The problem is then to compute the value of when values of 1, . . . , are given by value expressions 1, . . . , . To solve this problem using model semantics proposed in this paper it is necessary to find the interpretation A such that [[]]A = [[]]A for ∈ {1, . . . , } and A |= . Finding such an interpretation would require a solver capable of determining whether some constraint is satisfied in an interpretation or not; practically implementing definition 4.7 and building up to answer the question of whether some interpretation is a model of a DMN table. For the moment we assume the existence of such a solver and discuss it further in Section 5.2. Taking into account that values of input attributes are exact and that value of the decision is obtained with an aggregate function, it follows that there exists exactly one interpretation satisfying the above requirements, and hence the decision value is [[]]A.
Although solving this kind of problem is already very useful, in real-life scenarios it is often
the case that the user does not know exact values for all input attributes but rather a set of
possible values. For example, a user might know that input attribute 1 is between numerical
values 3 and 10. Hence we propose to allow users to specify constraints (using ℳ ) on
attributes rather than exact values. By combining diferent constraints users can express their
knowledge about an attribute value. This idea is not new, cDMN [
Definition 5.1. DMN model generation with attribute constraints is an inference method defined as: For a given input: (i) A set of input and decision attributes: = {1, . . . , , }, (ii) A DMN table: , (iii) Per attribute ∈ a set of ℳ constraints : , the output is the set of interpretations such that each interpretation satisfies all attribute constraints and is a model of the table, formally: {A | ∀ ∈ : ∀ ∈ : [[]]A ∈ [[]]A and A |= }.
Constraining attributes in this way allow users to distinguish between unknown and undeifned values. Following are constraints corresponding to the three situations from the introduction: 1. Constraint “ ” expresses that some attribute is known to be undefined. 2. Constraint “ ” expresses that some attribute is known to be defined, but its value is unknown. 3. The absence of constraints means that it is not known whether an attribute is defined or not (nor anything about its value).
Furthermore, by combining diferent constraints one can express much more. For example, “ , [3..10]” means: “if the attribute is defined then its value is between 3 and 10”. However this is not the most convenient way of expressing such constraints, hence extending the language of attribute constraints would be useful. We propose to use the language ℒ defined as the set of formulas consisting of ℳ constraints closed under the logical connectives ∧,∨,¬, ⇒, and ⇔. The constraint from above then becomes “ ⇒ [3..10]”. The semantics of this language is straightforward as it can be defined by a slight extension of standard
or negation of constraints connected with “or” (in DMN “,”) like “not ( , [3..10])”.
can be expressed in terms of these.
Definition 5.2. For a given DMN interpretation A, a ℒ attribute constraint expression denotes a set [[]] which is subset of the [[D]]A ∪ {⊥} (denoted as [[D]]A ), defined as: A ⊥ [[1 ∨ 2]]A =[[1]]A ∪ [[2]]A [[¬]]A =[[D]]A⊥ ∖ [[]]A [[]]A =[[]]A if ∈ ℳ
To make practical use of the semantics proposed in this paper, a solver implementing it is needed.
The solver should be able to answer whether an interpretation is a model of one or more DMN
tables. On top of that, the solver should be intuitive to extend with diferent functionalities,
such as generating all models of a table, extending partially specified interpretations, and more.
However, building such a solver is a dificult task and a bit redundant since there are existing
solvers for many languages, especially those based on FO. While this suggests that a translation
of DMN tables to some FO language is required, as we pointed out earlier, standard FO will
not sufice. Indeed, support for partial functions, definitions, and (optionally) aggregates is
required. At the moment of writing this paper, we are not aware of a solver that provides
all of these options. But, one solver, the IDP system [
specifying attribute constraints (i.e., ℒ constraint expressions). The second theory represents DMN table translation to a definition; a set of rules of the form := ← 1[1]∧· · ·∧ [] (Definition 4.4). However, this is not suficient as the sequence of rules is lost, hence translation has to include the numerical identifier ( ) assigned to the row in the DMN table. The most convenient way with IDP system is to replace the head of rule with relation: (, ) ← 1[1] ∧ · · · ∧ []. The third theory defines the hit policy as aggregate functions over the relation; for example unique hit policy: ∀ : = ←
(∃ : (, )) ∧ #{1, 1 : (1, 1)} = 1.
The IDP solver can generate all models satisfying these three theories. These models correspond to models defined in definition 5.1.
We demonstrate this approach in the greeting example from Fig. 2c. Presented are snippets of theories while the whole formalization is provided online4. First, the theory that expresses the user’s knowledge about the attributes of the table is declared (e.g., = ). theory T_attribute_constraints : V_salutation{
Gender = Male.
R_Salutations(1,Mr) ← R_Salutations(2,Mrs) ← R_Salutations(3,Ms) ←
Gender = Male.
Gender = Female ∧ MaritalStatus = Married.
Gender = Female ∧ MaritalStatus = Single.
Following is the theory expressing the contributions of the rules (with identities). theory T_rules_derivation : V_salutation_decision {
{ } }
} 4https://bitbucket.org/krr/dmn-to-idp-poc/src/main/
Finally, the theory defining unique hit policy is instantiated for this particular table. theory T_unique_hit_policy : V_salutation_decision { { ∀ t[Titles] : Salutation = t ← (∃r[Rule]:R_Salutations(r,t))
∧ #{r1[Rule], t1[Titles]:R_Salutations(r1,t1)}=1.
The model of theories above obtained by the use of the IDP solver would look like this: The IDP system is suficient for building this proof of concept example. Furthermore, it provides a variety of inference methods and hence is a good candidate to serve as a solver for DMN model semantics proposed in this paper.
So far in this paper, we focus on the semantics of DMN tables individually, while they are almost always used as a part of Decision Requirements Graphs (DRG) where tables can share inputs or be connected (the decision of one table is an input of another). The reason for this is that model semantics defined in this paper naturally scale up to multiple tables.
Definition 5.3. For a given sequence of attributes ⃗, let be a set of DMN tables {1, . . . , } where each table is over some subset of attributes, and let A be a DMN interpretation (over ⃗) then A satisfies set of DMN tables , or A is a model of , (denoted as A |= ) if A is a model of each table ∈ ; formally:
A |= ⇔ ∀ ∈ : A |=
In the introduction, it is mentioned that the current semantics based on the translation to FO would result in undefinedness in the case of tables with overlapping rules. This would prevent decision derivation for other tables that perhaps are deriving a decision. For examples, combining tables from Fig. 2b and 2c in case that user knows that = 10 for table 2b and = for table 2c. Translation of rules to material implications would result in a theory that is unsatisfiable because of the overlapping rules in table 2b. However, table 2c derives the decision = based on gender. Our semantics produces one model in such scenario, decisoin of table 2b is non-existing (i.e., undefined) and decision of table 2c is . As pointed out earlier, it is more natural to consider overlapping rules (with a unique hit policy) as an error. The model semantics defined in this paper can be refined with over-defined values which would correctly capture the value in these cases and allow diferent interpretations from undefinedness.
In Sections 5.1 and 5.2 it is demonstrated how to get models of a DMN table where user can
express the knowledge about input/output attributes. These ideas are briefly demonstrated in
the greeting challenge example [
Expressing such statements, about all possible models, is not possible in DMN. This forces
users to use encoding tricks which ultimately results in a bad knowledge representation. While
as a matter of fact, the nature of this knowledge is epistemic (e.g., If we know that salutation is
“ ”, taking into account what is known about gender and marital status, then use greeting
“Dear Mr.”). It is important to observe that there are two levels of knowledge in this statement.
The first is about values of gender and marital status. The second is about salutation message
with respect to all the possible salutations (according to what is known about the person). This
idea is known as ordered epistemic logic and it is worked out in detail in [
We propose to extend DMN with modal epistemic operator and in particular with ordered
epistemic logic. This extension comes naturally to DMN since tables are not allowed to have
cycles in dependency. Moreover, this extension would not require a new specialized solver as it
is possible to simulate it using the IDP system (as demonstrated in [
Salutation message U Salutation 1 ( ) 2 ( ) 3 ( ) 4 ( ∨ ) ∧ ¬( ) ∧ ¬( ) ∧ ¬( ) 5 ¬( ∨ ) ∧ ¬( ) ∧ ¬( ) ∧ ¬( ) Salutation message “Dear Mr.” “Dear Mrs.” “Dear Ms.” “Dear Madam” “Dear Customer”
The first three rows are simply stating that in cases when an exact salutation is known then it should be used in the message. The fourth row expresses that in cases when ∨ is known and no exact salutation is known message is “Dear Madam”. This rule is quite cumbersome because it is necessary to eliminate all the previous cases. Likewise, the last rule states that if non of the above is known “Dear Customer” message is appropriate.
The size of the epistemic formulas in the table from Fig. 3 is simply unmanageable. However, it is possible to optimize it by the use of diferent hit policies. For example, first hit policy derives the value of the first rule that produces a value where the order of the rules corresponds to the numbers in the table. The simplified table is presented in Fig. 4.
Salutation message F Salutation Salutation message 1 ( ) “Dear Mr.” 2 ( ) “Dear Mrs.” 3 ( ) “Dear Ms.” 4 ( ∨ ) “Dear Madam” 5 - “Dear Customer”
The informal interpretation of this table is slightly diferent from the previous one, but they have the same meaning. The first three rules are expressing that it is safe to use a message with the exact salutation only if that salutation is known. According to the fourth rule it is safe to use message “Dear Madam” if ∨ is known. The last rule specifies that message “Dear Customer” is always safe. The first hit policy then selects the most precise message where precision is following the order of rules. We provide a proof of concept for this example (using table from the Fig. 3) using the IDP system5.
The topics that are opened with this paper are the formalization of epistemic DMN with ordered
epistemic logic [
In this paper, we proposed and partially formalize the extension of DMN with undefinedness, uncertainty, and epistemic K-operator. This is an important problem in real-life, which is not yet addressed in current semantics. Our model semantics provides clear disambiguation between undefined and unknown values. Furthermore, extending it with ordered epistemic logic is straightforward. We discuss the importance and benefits of our approach and provide a proof of concept for implementing it. 5https://bitbucket.org/krr/dmn-to-idp-poc/src/main/
This research received funding from the Flemish Government under the “Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen” programma.
This paper benefited from reviews and constructive comments from Maurice Bruynooghe. Semantics, complexity and applications, in: Thirteenth International Conference on the Principles of Knowledge Representation and Reasoning, 2012.