Patent ID: 12254417

DETAILED DESCRIPTION

Decision tables are commonly used in a variety of industries, for example to describe decision logic for a computer program or an organization. Such decision tables are typically drafted by experts to comply with certain rules and best practices that reduce redundancy, improve flexibility, improve integrity, and improve logical consistency. In particular, experts may manually apply normalization concepts to decision tables in an effort to structure the decision tables in accordance with a series of “normal forms,” which originated in the context of relational databases. Examples of these normal forms are the first normal form (1NF), the second normal form (2NF), and the third normal form (3NF). A decision table can be in the first normal form if each entry in the table is atomic and unique. A decision table can be in the second normal form if it is in the first normal form, and if the decision table only includes input conditions that are relevant to the outcome. A decision table can be in a third normal form if it is in the second normal form, and if the decision table lacks dependencies among the input conditions such that all of the input conditions are independent of one another. Decision tables that are in third normal form can avoid duplicate entries, reduce the chance of input errors, and avoid logical inconsistencies. As a result, it may be desirable for experts to structure a decision table in third normal form. This may involve decomposing the single decision table into several decision tables that make the input dependencies explicit.

Although experts may wish to ensure their decision tables are in third normal form, it can be challenging for them to do so. For example, an expert may manually and subjectively analyze a decision table to determine if any dependencies exist among the input conditions therein. If so, the expert can determine that the decision table violates the third normal form requirements and make appropriate adjustments. But, such input dependencies are often not readily apparent (e.g., they are “hidden”) and may be transitive in nature, making them easy for an expert to accidentally miss. As a result, an expert may mistakenly think that a decision table is in a third normal form when it actually is not. And if the decision table is then used, for example to drive the decision logic of a computer program, numerous problems may arise. For example, the decision table may have logical inconsistencies that can cause the computer program to malfunction. Additionally, the decision table may take up more space in computer memory or may be stored in computer memory in a less flexible (e.g., suboptimal) way than would otherwise be required if the decision table was further decomposed into several decision tables that comply with third normal form constraints.

Some examples of the present disclosure can overcome one or more of the abovementioned problems by automatically validating a decision table to ensure that it complies with third normal form constraints. For example, a computer can execute a decision table validation (DTV) tool configured to automatically analyze a decision table to determine whether the decision table violates a third normal form constraint. The DTV tool can determine if the decision table violates the third normal form constraint by executing an iterative process that includes multiple iterations. Each iteration can involve selecting a pair of columns (e.g., input conditions) from the decision table and analyzing the values in the pair of columns to determine if they have a dependency relationship. This analysis can be performed according to a predefined set of rules, which are described in greater detail later on. If the values in the pair of columns have a dependency relationship, the DTV tool can generate a notification indicating that the pair of columns violate the third normal form constraint. Additionally or alternatively, the processor can automatically separate the pairs of columns into separate decision tables that comply with third normal form constraints. This process can be repeated for every pair of columns in the decision table, so that the decision table can be refactored into third normal form. In this way, the DTV tool can automatically assist a user with identifying decision tables that are not compliant with third normal form and restructuring those decision tables to be compliant with third normal form. This, in turn, can significantly reduce errors associated with computer programs and other entities that rely on such decision tables for decision logic.

As one specific example, a computer program may control the functionality of a wind turbine based on the following decision table:

TABLE 1Example Decision TableTurbine AgeTurbine SpeedBreakdownComputer(years)(RPM)RiskFunction>=21<15“Medium”Function_1>=21>=15“High”Function_2<21<15“Medium”Function_1
Since the computer program will determine a decision output (e.g., a computer function to execute) based on the values in the first three columns, the first three columns can be referred to as input columns and the fourth column can be referred to as an output column. There is a hidden dependency between the second and third columns, in that the speed of the turbine determines the breakdown risk independently of the age of the turbine. That is, no matter the age of the turbine, the risk will always be “Medium” if the speed is less than 15 RPM and the risk will always be “High” if the speed is greater than 15 RPM. This may be a somewhat counterintuitive dependency, since one would naturally think that turbine age would play a larger role in breakdown risk than turbine speed. As a result, this hidden dependency may be missed upon manual inspection of the decision table by an expert.

In the above example, the DTV tool can automatically analyze the decision table and identify the hidden dependency between the second and third columns. Based on the presence of the hidden tendency, the DTV tool can notify the user that the decision table does not comply with a third normal form constraint. The DTV tool can also notify the user of the hidden dependency between the second and third columns. This may allow for the decision table to be broken down into multiple separate decision tables that comply with third normal form. For example, the user may manually refactor the decision table into two separate decision tables that comply with third normal form. Alternatively, the DTV tool can automatically refactor the decision table into two separate decision tables that comply with third normal form. Either way, by restructuring the original decision table as multiple separate decision tables that comply with third normal form, the resulting decision tables can have fewer redundancies and can be more flexibly stored in computer memory (e.g., across two or more memory devices or memory sectors). Additionally, logical inconsistencies may be avoided that could otherwise cause the computer program to call the wrong function or otherwise operate improperly.

These illustrative examples are given to introduce the reader to the general subject matter discussed here and are not intended to limit the scope of the disclosed concepts. The following sections describe various additional features and examples with reference to the drawings in which like numerals indicate like elements but, like the illustrative examples, should not be used to limit the present disclosure.

FIG.1is a block diagram of an example of a system100for automatically validating decision tables according to some aspects of the present disclosure. In this example, the system100includes a computing device102, such as a laptop computer, desktop computer, server, tablet, or mobile phone. The computing device102includes drafting software104for drafting a decision table106that contains decision logic110(e.g., for a DMN model or computer program). Examples of the drafting software104can include word processing software such as Microsoft Word®, DMN editor by Red Hat®, or a web-based editor included in a website. A user112can draft the decision table106using the drafting software104.

One example of the decision table106is shown in a dashed box inFIG.1. This decision table106is similar to Table1described above. The decision table106includes four columns122a-d. The first three columns122a-care input columns that include input conditions. The fourth column122dis an output column that indicates an action to take in response to a set of input conditions. The decision table106also includes three entries120a-c(e.g., records). Each of the entries120a-ccorresponds to a unique row of the decision table106. The entries define the decision logic110that, for example, may be used by a computer program or organization to perform certain functions in response to certain input conditions. The points where rows and columns intersect in the decision table106are referred to as cells. Cells in an input column can be referred to as input cells, and cells in an output column can be referred to as output cells. Each cell of the decision table106can have a value. Values can include numbers, letters, symbols, or any combination thereof. For example, cell124includes the value “<21”. While the decision table106only includes four columns122a-dand three entries120a-cfor simplicity, decision tables can include any number and combination of columns and entries.

The system100can also include a decision table validation (DTV) tool108. The DTV tool108is software that is executable for analyzing the decision table106to determine whether it complies with third normal form constraints. If the decision table106does not comply with third normal form constraints, the DTV tool108can generate one or more notifications114indicating third normal form violations to the user112. Additionally or alternatively, the DTV tool108can rearrange the decision table106into separate decision tables that conform to third normal form requirements.

In some examples, the DTV tool108may be standalone software that is located on the computing device102and configured to operate independently of the drafting software104. In other examples, the DTV tool108can be a plugin or extension for the drafting software104. In still other examples, the DTV tool108can be located on a server118that is remote from the computing device102. The computing device102can transmit (e.g., upload) the decision table106to the server118over a network116, such as a local area network or the Internet. The server118can receive the decision table106and responsively execute the DTV tool108to analyze the decision table106. If the server118determines that the decision table106does violate third normal form constraints, the server118can output a corresponding notification114to the user112via the network116and/or automatically rearrange the decision table106into two or more separate decision tables that do not violate the third normal form constraints.

Regardless of the location of the DTV tool108, in some examples the DTV tool108can determine whether the decision table106violates a third normal form constraint by executing the process200shown inFIG.2. Of course, the process200shown inFIG.2is intended to be exemplary and non-limiting. Other examples may involve more steps, fewer steps, different steps, or a different order of the steps shown inFIG.2. The steps ofFIG.2are described below with reference to the components ofFIG.1described above.

In block202, the DTV tool108receives a decision table106. The DTV tool108can receive the decision table106from any suitable source. For example, the DTV tool108can receive the decision table106from memory, where it may be stored by the drafting software104. Additionally or alternatively, the DTV tool108can receive the decision table106from the computing device102over the network116.

In block204, the DTV tool108selects a pair of input columns from the decision table106. The pair of input columns includes a first column and a second column. As used herein, the terms “first” and “second” are used to distinguish columns from one another for clarity, and not necessarily to identify specific column numbers. The pair of input columns can be any suitable pair of input columns, such as any unique pair of input columns that have not been previously selected by the DTV tool108during prior iterations of the process200.

In block205, the DTV tool108determines a first set of values associated with the first column and a second set of values associated with the second column. The first set of values may include some or all of the values in the cells of the first column. For example, the DTV tool108may select, as the first set of values, all of the values in the first column except an everything operator (e.g., “−”) value. The second set of values may also include some or all of the values in the cells of the second column. For example, the DTV tool108may select, as the second set of values, all of the values in the second column except for an everything operator value.

In some examples, the DTV tool108can generate the first set of values by transforming some or all of the values in the first column into value ranges. For example, a value of “>=0” can be transformed into an equivalent range with an endpoint defined, such as [0 . . . +inf]. A simple value such as “47” can be transformed into an equivalent range representing a single point, such as “[47 . . . 47]”. An everything operator (“−”) can be transformed into an equivalent range spanning infinity or the boundary of the column domain, such as [−Inf . . . +Inf]. Values that are already ranges, such as [1 . . . 2], may remain in their original state. String values such as “Medium” can be transformed into an equivalent range such as [“Medium” . . . “Medium”]. Any suitable approach can be used to transform the values in the first column into value ranges. Additionally, the DTV tool108can generate the second set of values by transforming some or all of the values in the second column into value ranges. This may be accomplished by using similar techniques as described above. Converting the values in the decision table106into value ranges can make the values easier to compare to one another in subsequent steps of the process200.

In block206, the DTV tool108selects a value from the first set of values associated with the first column. For example, the DTV tool108can select the first column122aand the second column122bfrom the decision table106as the pair of input columns. The first column122ahas a first set of cells with a first set of values (“>=21”, “>=21”, and “<21”) and the second column122bhas a second set of cells with a second set of values (e.g., “<10”, “>=10”, “<10”). The DTV tool108can select the value “>=21” from the first set of values associated with the first column122a. As another example, the DTV tool108may have previously transformed the value of “>=21” into the value range [21 . . . +inf], so the DTV tool108can select that value range.

In block208, the DTV tool108determines whether there is a one-to-one relationship between (i) the value selected from the first set of values associated with the first column and (ii) a corresponding value in the second set of values associated with the second column. A one-to-one relationship exists when a value in the first set of values always has the same corresponding value in the second set of values. In contrast, a one-to-many relationship exists when a value in the first set of values has multiple corresponding values in the second set of values. To make this determination, the DTV tool108may use any suitable technique. For example, the DTV tool108can identify one or more entries (e.g., rows) in the decision table106that include cells associated with the selected value in the first column. The DTV tool108can then determine whether the one or more entries have the corresponding value in the second set of values associated with the second column. If so, the DTV tool108may determine that the selected value has a one-to-one relationship with the corresponding value.

As one specific example, the DTV tool108can determine that the value “>=21” in the first entry120aof the decision table106has a corresponding value of “<10” in the second column122b. The DTV tool108can also determine that the value “>=21” in the second entry120bof the decision table106has a corresponding value of “>=10” in the second column122b. Since the value “>=21” sometimes corresponds to “<10” in the second column122band other times corresponds to “>=10” in the second column122b, the DTV tool108may determine that the value “>=21” has a one-to-many relationship.

As another example, the DTV tool108may have previously transformed the value “>=21” in the first column122aof the decision table106into the value range “[21 . . . +inf]”. The DTV tool108may have also previously transformed the value “<10” in the second column122bof the decision table106into the value range “[−inf . . . 10)”. The DTV tool108may have further previously transformed the value “>=10” in the second column122bof the decision table106into the value range “[10 . . . +inf]”. The DTV tool108may then determine that the value range “[21 . . . +inf]” sometimes corresponds to “[−inf . . . 10)” and other times corresponds to “[10 . . . +inf]”. So, the DTV tool108may determine that the value “[21 . . . +inf]” has a one-to-many relationship.

As still another example, the selected pair of input columns can include the second column122band the third column122c. The selected value can be “<10” in the second column122b. The DTV tool108can determine that the value “<10” in the first entry120aof the decision table106has a corresponding value of “Medium” in the third column122c. The DTV tool108can also determine that the value “<10” in the third entry120cof the decision table106has a corresponding value of “Medium” in the third column122c. Because the selected value of “<10” corresponds to “Medium” in both entries, the DTV tool108may determine that the selected value of “<10” has a one-to-one relationship.

If the DTV tool108determines that the value selected from the first set of values does not have a one-to-one relationship with a corresponding value in the second set of values, the process200can proceed to block212. In block212, the DTV tool108determines that there is not a third normal form violation with respect to the selected pair of input columns. This is because there is likely not a dependency relationship between the pair of input columns (e.g., the first column is independent of the second column).

If the DTV tool108determines that the value selected from the first set of values does have a one-to-one relationship with a corresponding value in the second set of values, the process200can proceed to block210. In block210, the DTV tool108flags the selected value as having the one-to-one relationship.

The process200can next continue to block214, where the DTV tool108determines whether there are any more values in the first set of values associated with the first column that should be analyzed. If so, the process can return to block206, where another value can be selected from the first set of values and blocks208-214can iterate. Once there are no more values in the first set of values to analyze, the process can continue to block216.

In block216, the DTV tool108determines whether all of the analyzed values (from the first set of values) have a one-to-one relationship with corresponding values in the second set of values. For example, the DTV tool108can determine if each analyzed value was flagged as having a one-to-one relationship. If not, the process can continue to block212, where the DTV tool108can determine that there is not a third normal form violation with respect to the selected pair of input columns. Otherwise, the process can continue to block218. In block218, the DTV tool108determines that a third normal form violation exists with respect to the selected pair of input columns. This is because there is likely a dependency relationship between the pair of input columns.

In block220, the DTV tool108generates a notification114(e.g., for the user112) about the selected pair of input columns. For example, the notification114can indicate that there is a third normal form violation with respect to the pair of input columns. As another example, the notification114can indicate that there is not a third normal form violation with respect to the pair of input columns. Alternatively, if there is not a third normal form violation, the DTV tool108may forgo emitting a notification and this step may be skipped (e.g., the process200can proceed directly to block222).

In some examples, the DTV tool108can automatically break the pair of input columns into separate decision tables in response to determining that they violate third normal form constraints. For example, the DTV tool108can extract the values from the first column122aand incorporate the values into a new decision table. The DTV tool108may also include keys in the new decision table, where the keys can be used in the original decision table106to link to the values in the new decision table. The DTV tool108can then update the original decision table106with the appropriate keys, for example to create explicit dependencies among the columns. As a result of this process, the original decision table106may comply with third normal form constraints.

In block222, the DTV tool108determines if a stopping condition is satisfied. An example of the stopping condition may be that every pair of input columns in the decision table106has been analyzed. If the stopping condition has not been satisfied, the process200can return to block204, where another pair of input columns can be selected from the decision table106and the process can repeat. In this way, the process200can iterate multiple times. If the stopping condition has been satisfied, the process200may end.

FIG.3is a block diagram of another example of a system300for automatically validating decision tables according to some aspects of the present disclosure. The system300includes a processor302communicatively coupled to a memory304. In some examples, the processor302and the memory304can be part of the same computing device, such as the computing device102ofFIG.1. In other examples, the processor302and the memory304can be distributed from (e.g., remote to) one another.

The processor302can include one processor or multiple processors. Non-limiting examples of the processor302include a Field-Programmable Gate Array (FPGA), an application-specific integrated circuit (ASIC), a microprocessor, etc. The processor302can execute instructions306stored in the memory304to perform operations. The instructions306may include processor-specific instructions generated by a compiler or an interpreter from code written in any suitable computer-programming language, such as C, C++, C#, etc. In some examples, the instructions306can include the decision table validation tool108ofFIG.1.

The memory304can include one memory or multiple memories. The memory304can be non-volatile and may include any type of memory that retains stored information when powered off. Non-limiting examples of the memory304include electrically erasable and programmable read-only memory (EEPROM), flash memory, or any other type of non-volatile memory. At least some of the memory304can include a non-transitory computer-readable medium from which the processor302can read instructions306. A computer-readable medium can include electronic, optical, magnetic, or other storage devices capable of providing the processor302with computer-readable instructions or other program code. Non-limiting examples of a computer-readable medium include magnetic disk(s), memory chip(s), ROM, random-access memory (RAM), an ASIC, a configured processor, optical storage, or any other medium from which a computer processor can read the instructions306.

In some examples, the processor302can execute the instructions306to perform an iterative process, such as the process200ofFIG.2described above. For example, the processor302can determine a first plurality of values308associated with a first column in a decision table106and a second plurality of values310associated with a second column in the decision table106. The processor302can select the first column and the second column for use during a current iteration of an iterative process, such as the iterative process described above. An example of the first column can be column122aand an example of the second column can be column1122b, as shown using bold boxes inFIG.3.

In some examples, the first plurality of values308can be the values expressly included in the first column, and the second plurality of values310can be the values expressly included in the second column. In other examples, the first plurality of values308can be value ranges derived from the values expressly included in the first column, and the second plurality of values310can be value ranges derived from the values expressly included in the second column.

Next, the processor302can determine that each respective value in the first plurality of values308has a one-to-one relationship with a corresponding value in the second plurality of values310. Based on determining that each respective value in the first plurality of values308has the one-to-one relationship, the processor302can determine that the first column and second column violate a third normal form constraint. Based on determining that the first column and second column violate the third normal form constraint, the processor302can reorganize the first column and the second column into separate decision tables312that comply with the third normal form constraint. This automated reorganization is represented inFIG.3by an arrow from the original decision table106to the separate decision tables312. But, in some examples the separate decision tables312may include a modified version of the original decision table106and one or more additional decision tables.

In some examples, the processor302can implement some or all of the steps shown inFIG.4. Other examples can include more steps, fewer steps, different steps, or a different order of the steps than is shown inFIG.4. The steps ofFIG.4are discussed below with reference to the components discussed above in relation toFIG.3.

In block402, the processor302determines a first plurality of values308associated with the first column of a decision table106and a second plurality of values310associated with a second column of the decision table106. The first column and the second column may be selected from the decision table106by the processor302for use during a current iteration of an iterative process.

In some examples, the first plurality of values308can be the values expressly included in the first column. Additionally or alternatively, the second plurality of values310can be the values expressly included in the second column. In other examples, the first plurality of values308can be value ranges generated based on the values included in the first column. Additionally or alternatively, the second plurality of values310can be value ranges generated based on the values included in the second column.

In block404, the processor302determines that each respective value in the first plurality of values308has a one-to-one relationship with a corresponding value in the second plurality of values310. For example, the selected pair of input columns can include the second column122band the third column122cof the decision table106. The first plurality of values308can include the value range “[−inf . . . 10],” which the processor302may have derived from the value “<10” in the second column122b. The processor302can select the value range “[−inf . . . 10]” from the first plurality of values308and determine that it always corresponds to the value range of “[Medium . . . Medium]” in second plurality of values310. This is because, even though the value range “[−inf . . . 10]” may be present twice in the first plurality of values308since the value “<10” is present twice in the decision table106, in both instances it is correlated to the same value range of “[Medium . . . Medium]” in second plurality of values310. As a result, the processor302can determine that the selected value of “[−inf . . . 10]” has a one-to-one relationship. The processor302can repeat this process for each respective value in the first plurality of values308, to determine that each respective value in the first plurality of values308has a one-to-one relationship with a corresponding value in the second plurality of values310.

In block406, the processor302determines that the first column and second column violate a third normal form constraint, based on determining that each respective value in the first plurality of values308has the one-to-one relationship.

In block408, the processor302automatically reorganizes the first column and the second column into separate decision tables312that comply with the third normal form constraint. For example, the processor302can extract the values from the first column and incorporate the values into a new decision table. The processor302may also include keys in the new decision table, where the keys can be used in the original decision table106to link to the values in the new decision table. The processor302can then update the original decision table106with the appropriate keys, for example to create explicit dependencies among the columns. As a result of this process, the original decision table106may comply with third normal form constraints.

The foregoing description of certain examples, including illustrated examples, has been presented only for the purpose of illustration and description and is not intended to be exhaustive or to limit the disclosure to the precise forms disclosed. Numerous modifications, adaptations, and uses thereof will be apparent to those skilled in the art without departing from the scope of the disclosure. For instance, examples described herein can be combined together to yield still further examples.