Source: http://www.google.com/patents/US7565337?dq=6,208,537
Timestamp: 2014-11-26 22:00:28
Document Index: 53011487

Matched Legal Cases: ['art 1', 'art 2', 'art 3', 'art 4', 'art 1', 'art 2']

Patent US7565337 - Batch validation method, apparatus, and computer-readable medium for rule ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA computer-implemented method and apparatus thereof for validating combinations of product features that are compliant with existing business rules relative to a modified business rule, where the modification includes an include and/or an exclude ZDD rule component. The method comprises obtaining combinations...http://www.google.com/patents/US7565337?utm_source=gb-gplus-sharePatent US7565337 - Batch validation method, apparatus, and computer-readable medium for rule processingAdvanced Patent SearchPublication numberUS7565337 B2Publication typeGrantApplication numberUS 10/950,622Publication dateJul 21, 2009Filing dateSep 28, 2004Priority dateSep 29, 2003Fee statusPaidAlso published asUS20050080798Publication number10950622, 950622, US 7565337 B2, US 7565337B2, US-B2-7565337, US7565337 B2, US7565337B2InventorsDavid L. Huelsman, Sharon E. Love, Douglas M. MairOriginal AssigneeHuelsman David L, Love Sharon E, Mair Douglas MExport CitationBiBTeX, EndNote, RefManPatent Citations (57), Non-Patent Citations (26), Classifications (7), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetBatch validation method, apparatus, and computer-readable medium for rule processingUS 7565337 B2Abstract A computer-implemented method and apparatus thereof for validating combinations of product features that are compliant with existing business rules relative to a modified business rule, where the modification includes an include and/or an exclude ZDD rule component. The method comprises obtaining combinations of features compliant with the existing business rules, processing the combinations against a representation of the rule components to determine validity against the modified business rule, and providing to a user an indication of validity of the combinations relative to the modification. The processing optionally comprises forming a representation of a record-by-feature array having rows corresponding to the combinations, ordering columns of the array according to one of the rule components, and testing validity of the rows of the array against the rule component. The features or combinations arc optionally read from a database, and optionally include a service.
1. A method of validating an existing product configuration comprising:
storing one or more particular combinations of features associated with the existing product configuration that are compliant with an existing business rule in a memory for access by an application program executed on a processing system, where each feature is associated with one or more enumerations;
using the application program executed on the processing system to process each of the one or more particular combinations against a representation of at least one of a component indicating included combinations of features or a component indicating excluded combinations of features of a modification of the existing business rule by:
forming a record-by-enumeration array comprising one or more rows representing one or more features and one or more columns representing one or more enumerations associated with each of the one or more particular combinations of features;
ordering the one or more columns according to the at least one of the component indicating included combinations of features or the component indicating excluded combinations of features of the modification of the existing business rule;
sorting the one or more rows responsive to the ordering of the one or more columns;
testing each one of the one or more rows against the at least one of the components indicating included combinations of features or the component indicating excluded combinations of features to determine validity of the row, the validity of the row indicating the validity of the respective combination relative to the modification of the existing business rule; and
denoting the validity in a column of the record-by-enumeration array.
2. The method of claim 1 where the storing comprises reading the particular combinations from a database.
3. The method of claim 2 where the features include a service.
4. The method of claim 1, where each of the columns corresponds to one of the features.
5. The method of claim 1, where at least one of the columns corresponds to a plurality of the features.
6. The method of claim 1, where the component indicating included combinations of features is represented as an include Zero-suppress binary Decision Diagram (ZDD).
7. The method of claim 1, where the component indicating excluded combinations of features is represented as an exclude Zero-suppress binary Decision Diagram (ZDD).
8. A computer-implemented method, comprising:
accessing a database stored in a memory using an application program executed on a processing system to obtain a plurality of records each defining an existing product configuration compliant with an existing rule;
using the application program, representing a modification of one or more rules validating enumerations of the plurality of records as at least one Zero-suppress Decision Diagram (ZDD) component;
using the application program, representing the plurality of records as a record-by-enumeration array, each one of one or more rows of the array representing a respective one of the records, each one of one or more columns of the array representing one or more of enumerations associated with the records;
using the application program, ordering the columns according to the at least one ZDD component;
using the application program, sorting the rows according to the ordering of the columns; and
using the application program, determining validity of each of the sorted rows according to existence of a respective path in the at least one ZDD component corresponding to the enumerations of the respective record, the validity of the row indicating compliancy of the respective record; and
using the application program, denoting the compliancy of the respective records in a column of the record-by-enumeration array.
9. The improvement of claim 8, where the at least one ZDD component is an include ZDD component; and where the determining validates the row according to the existence of the respective path.
10. The improvement of claim 8, where the at least one ZDD component includes an exclude ZDD component; and where the determining is configured to invalidate the row according to the existence of the respective path.
11. The improvement of claim 10, where the respective path corresponds to an initial subset less than all of the enumerations of the respective record, the enumerations of the respective record considered according to the ordering of the columns.
12. An apparatus configured to validate plurality of product data records, the apparatus comprising:
a processor configured to execute instructions stored in the computer readable medium to:
obtain the plurality of product data records each comprising a particular combination of one or more features each having one or more enumerations defining an existing product configuration compliant with an existing business rule;
represent a modification of the existing rule as at least one Zero-suppress binary Decision Diagram (ZDD) component;
represent the plurality of product data records as a record-by-enumeration array, each one of one or more rows of the array representing a respective one of the product data records, each one of one or more columns of the array representing one or more of the enumerations associated with the plurality of records;
order the columns according to the at least one ZDD component; and
determine validity of each of the rows according to the at least one ZDD component, the validity of the row indicating the compliancy of the respective product data record to the modification of the existing business rule; and
denote the compliancy of the respective product data record in a column of the record-by-enumeration array.
13. The apparatus of claim 12, where the at least one ZDD component includes at least one of an include component and an exclude component.
14. The apparatus of claim 12, where the processor is further configured to retrieve the selected product data records as ones of the product data records indicative of the criteria.
15. The apparatus of claim 12, where the processor is further configured to sort the rows according to the ordering of the columns.
16. The apparatus of claim 15, where the validity of each of the rows is according to existence of a respective path in the at least one ZDD component corresponding to the enumerations of the respective product data record.
17. The apparatus of claim 16, where the processor is further configured to:
determine the validity of each of the rows in order according to the sorting of the rows, buffer nodes of at least some of the paths; and
determine existence of an initial portion of the respective path corresponding to an initial subset of the enumerations of the respective product data record of a particular one of the rows based, at least in part, on the buffered nodes, the enumerations of the respective product data record considered according to the order of the columns.
18. A computer-readable medium comprising program instructions stored thereon that when executed by a processor, result in:
accessing a plurality of data records each defining a combination of enumerations of an existing product compliant with an existing rule:
forming a record-by-enumeration array indicative of the plurality of data records, each one of one or more rows of the array representing a respective one of the data records, each one of one or more columns of the array representing one or more of the enumerations;
order the columns according to a ZDD component of a modified rules;
determine validity of each of the rows according to the ZDD component, the validity of the row indicating the compliancy of the respective data record to the modified rule; and
denote the compliancy of the respective data record in the record-by-enumeration array.
19. The computer-readable medium of claim 18, where the ZDD component comprises an include component or an exclude component or combinations thereof.
20. The computer-readable medium of claim 18, where the combinations comprises product configuration parameters.
21. The computer-readable medium of claim 18, where the product comprises a service.
22. The computer-readable medium of claim 18, where the product comprises a rule-based system.
23. The computer-readable medium of claim 18, further embodying program instructions to sort the rows according to the ordering of the columns.
24. The computer-readable medium of claim 18, where the validity of each of the rows is according to existence of a respective path in the ZDD component corresponding to the enumerations of the respective data record. Description
CROSS-REFERENCE TO RELATED PATENTS AND PATENT APPLICATIONS This invention claims the benefit of Provisional Application Ser. No. 60/506,156 filed on Sep. 29, 2003 in the names of Huelsman, et al., entitled Improved Method and Apparatus for Rule Processing, which is incorporated herein.
This invention is also related to U.S. patent application Ser. Nos. 10/101,151 and 10/101,154, each filed on Mar. 20, 2002 in the names of the same inventors hereof, which are incorporated herein.
BACKGROUND This invention concerns an improvement to a method or apparatus for rule processing utilizing binary decision diagrams to express and manipulate a business rule, but more specifically, to a method, an apparatus, and a computer-readable medium to validate multiple records indicative of compliancy of criteria, e.g., attributes and enumerations of such attributes expressed in a binary decision diagram, relative to a new or modified business rule.
Specialized applications use rule processing implemented one a computer to drive high volume transaction processing utilities. These applications typically involve separating a relatively large volume of transaction records into two groups based on whether the individual records thereof conform with, or conflicts with certain business rules. An example of a batch validation application includes validating a large number of previously sold product configurations, e.g., stored data records, against a new set of proposed configuration rules in order to determine the validity of the existing or previously sold product configurations under the new configuration rules. When configurations are complex or numerous, prior techniques proved inadequate or required validation on an individual basis.
SUMMARY According to an aspect of the present invention, one improvement comprises a computer-implemented method of validating combinations of product features (or specifications) that are compliant with an existing business rule relative to a modification thereof that includes at least one include Zero-suppressed binary Decision Diagram (ZDD) rule component and/or one exclude ZDD rule component. The method comprises identifying combinations of features compliant with the existing business rule, processing the combinations against a representation of the include ZDD rule component and/or exclude rule component of the modified rule to determine validity, and providing to a user, such as a product manager, an indication of validity of the combinations relative to the modification whereby to validate the existing set of user-selected criteria against a new or modified business rule. In a further embodiment, the processing step of the improvement comprises forming a representation of a record-by-feature array indicative of the combinations, re-ordering the features (or specifications) according to at least one include and/or exclude ZDD rule component, testing the validity of re-ordered features against each rule component; and providing an output indicating to a user or product manager whether the re-ordered product features are compliant. Product features or combinations may be read from a database and the product may include a service.
In accordance with another aspect of the invention, the improvement is utilized in a rule processing method utilizing binary decision diagrams or other representation thereof (e.g., zero-suppress binary decision diagrams) to determine compliancy relative to a business rule. In this case, the improvement comprises a computer-implemented method of validating multiple data records stored in a computer memory representing user-selected enumerations (e.g., product specifications) relative to a modification of the rule. The improved method comprises obtaining data records indicative of user-selected enumerations that are compliant with the rule; forming a record-by-enumeration array of the records and enumerations; re-ordering enumerations of the array according to any include rule components of a modified rule, sorting the data records according to the re-ordering, determining a validity of the record according to existence of a path in the include rule component of the modified rule embodying re-ordered enumerations of the data records, and forming a resulting array by removing records having an invalid determination; re-ordering enumerations of the resulting array according to any exclude rule component of the modified rule, sorting records of the resulting array according to any exclude rule component, determining validity of records of the resulting array according to existence of a path in the exclude rule component embodying the re-ordered enumerations, and forming a final array by removing records having an invalid determination; and communicating to an end user an indication of those records of the final array that are fully compliant with the include and exclude rules components of the modified rule.
In yet another embodiment of the invention, there is provided an apparatus that validates multiple data records indicative of user-selected criteria relative to a modified or updated rule to determine compliancy of the criteria relative to the modification where the apparatus comprises an input (e.g., a GUI interface, keyboard, and/or pointing device) that obtains the criteria from a stored database, a processor including routines to form a representation of a record-by-enumeration array indicative of the criteria, to re-order enumerations of the array according to a ZDD rule component of the modified or updated rule, to determine validity of records having combinations of re-ordered enumerations relative to the ZDD rule component, and an output to provide a list of products to an end-user having valid combinations of enumerations. The ZDD rule component may include one or more include rule and exclude rule components. The user-selected criteria may comprise configuration parameters representing valid combination of components of a product or service.
In yet a further embodiment of the invention, there is provided a computer-readable medium including instructions to effect acquisition of a set of data records stored in a memory including combinations of enumerations compliant with an existing rule, to form a representation of a record-by-enumeration array indicative of the set, to re-order enumerations of the array according to a ZDD rule component of a modified business rule, to determine the validity of data records having re-ordered combinations of enumerations relative to the ZDD rule component, and to provide a list of products to an end-user having valid combinations of enumerations (e.g., valid product specifications). The ZDD rule component may comprises and/or exclude rule components. The combinations may comprise product or service configuration parameters.
The invention may also be implemented via a network using client-server communication, including a local area network or an Internet.
Other aspects, features, and embodiments will become apparent upon review of the following description of the illustrative embodiment taken in connection with the accompanying drawings. The invention, though, is pointed out with particularity by the appended claims.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows a truth table representing set of valid combinations or product features relative to an exemplary business rule.
FIG. 2 is re-ordered, sorted representation of the table of FIG. 1 according to an include rule component of a modified or new rule.
FIG. 3 shows the results of excluding invalid combinations or records of the table of FIG. 2 relative to include rule components.
FIG. 4 shows the further results of excluding invalid combinations or records of the table of FIG. 3 relative to exclude rule components.
DESCRIPTION OF ILLUSTRATIVE EMBODIMENT According to one aspect of the present invention, the improved method and apparatus provides a indication of each transaction or data record that is valid against a new or modified business rule. In the illustrated embodiment, the method or apparatus begins by obtaining a set of user-selected attributes, usually stored in a database. The data records may be obtained remotely over a local or wide area network. Exemplary software routines to effect operation of the method is set forth in the Appendix, which may be stored or transferred using a computer-readable medium.
Each selection comprises a set of enumerations previously selected by a user in connection with an existing business rule, such as a product configuration rule. FIG. 1, for example, shows five user selections or attributes. The first selection, Row 1, has enumerations 100, 121 and 152 selected. The second selection has enumerations 101, 120 and 151 selected, and so on . . . . Thus, the five selections, which are individually stored in a data record, may be represented as follows: {{100, 121, 152}, {101, 120, 151}, {101, 121, 151}, {102, 122, 153}, {120, 153 }}. To validate these selections or product configuration records, the method and apparatus of the present invention separately processes updated include and exclude rule components of a modified or new rule and communicate the results of the analysis to an end user, e.g., a product or production manager of a product or service marketed to a consumer.
To perform Include rule processing, selections are formed into a two-dimensional record-by-enumeration array having vertical columns and horizontal rows, as shown in FIG. 2. Only those columns having selections are included in the array while the remaining columns may be omitted. The columns of the array represent the enumerations. Next, the columns are ordered the same order as enumerations in the Include ZDD component of the new or modified rule (if any) against which the selections are to be validated. In this example, the Include ZDD enumeration ordering is (151, 152, 153, 100, 101, 102, 120, 121, 122). The rows of the array are then sorted (preferably descending) according to this column ordering. Finally, a validity column is denoted or appended to the end.
Each row or record in the array of FIG. 2 represents a single user selected criteria. The first row, for example, indicates the combination of Enum151, Enum101 and Enum120 in the user-selected criteria. If this combination exists in the Include ZDD tree of the new or modified rule, the validity column for the first row becomes True and this value is stored or associated with the record in under examination.
If the new or modified rule model has no Include rules, the Validity column is set to true and any remaining Include processing is skipped. Processing then immediately proceeds to the Exclude rule processing.
If all enumerations for each group are grouped together, the above table may be represented in the following manner:
As seen, the second row or record is almost identical to the first row, except that implementation of the inventive method involves searching for Enum121 on the second pass through the Include ZDD. Multi-OR selections is handled this way in that the record must be split into individual rows and then searched. Preferably, no row may have more than one enumeration per group.
Viewing the re-characterized table, it is seen that rows 1 through 4 are fully specified meaning that there is an enumeration from each group. Row 5 is not specified. For row 5, Group 2 is treated as a DC (don't care) value.
Fully specified Processing:
The process for finding validity is quicker for fully specified rows, which is achieved by scanning down the ZDD tree of the new or modified rule model and comparing the index of the node encountered to the column index of the array.
Upon encountering a zero in the data, process travels down the �else� side of matching nodes. Upon encountering a one in the data, the process travels down the �then� side of the matching nodes. As long as the process continues to encounter nodes that are in this combination, it continues. Upon encountering a node whose ordering in the ZDD tree is smaller than the ordering of the index being searched for, the process travels down the �else� side of the node. Upon encountering a node whose ordering in the ZDD tree is larger than the ordering of the index being searched for, then the process need not continue the scanning; and it then knows that the combination is not valid. Upon encountering the �one� node, then the process has found a valid path and the validity for the row becomes True. To improve speed, the improved method and apparatus may include buffering of the nodes encountered while scanning down the ZDD tree. Once a determination of the validity for a row has been made, the process proceeds to the next row or record. For fully specified rows, the process skips columns that are the same as the previous row. In the illustrated example, upon encountering nodes 151, 101, and 120 for row one, the process starts with node 101 and scans for node 121 on row two.
Non-Fully Specified Processing:
As the method and apparatus analyzes or processes the user-selected combinations row by row relative to nodes in the Include ZDD, its switches back and forth between fully specified and non-fully specified rows, as needed. The main difference between the two involves what happens when encountering indexes in the ZDD tree lacking a column in the array. For non-fully specified rows, such nodes are skipped, that is, they are treated as a DC (don't care). This adds processing time due to the need to consider both the �then� and the �else� sides of these nodes.
Exclude Processing:
If the modified rule model has no exclude rules, exclude processing is skipped. If, on the other hand, the new or modified rule includes exclude rule components, the analysis continues. After completing the include scanning, the resulting array will be found to have some valid combinations and some invalid combinations, e.g., rows or records of the resulting array. At this point, the process or apparatus removes or suppresses invalid rows to form a new resulting array, as shown in FIG. 3. The columns are then reordered according to the order of indexes in the Exclude ZDD rule component of the modified or new rule against which the selections are to be validated. In the illustrated example, the enumeration ordering in the Exclude ZDD rule is (120, 121, 122, 151, 152, 153, 100, 101, 102). The rows are also sorted (preferably in descending order), which renders the array of FIG. 4.
The method and/or apparatus uses the resulting array to scan through the Exclude ZDD component in order to invalidate any excluded combinations. It is not necessary to find the entire combination in the Exclude ZDD rule component to determine or denote an invalidation. If a portion of a combination on a path in the Exclude ZDD is found, then the entire combination is excluded thus invalidating that row in the array.
The rows of the array of FIG. 4 that have validity indication of True are thus validated according to the invention. The resulting array is returned to the calling routine of the rule processing system or method and/or conveyed to an end user. The validation results may be displayed for visual observation on a computer monitor, fed to an I/O device for hard copy printing of results, or simply stored in a memory for subsequent use by an end user.
Based on the above teachings, the invention also embraces modifications not explicitly shown in the drawings or written description, or illustrated by the exemplary code found in the attached Appendix. In particular, the invention is preferably practiced utilizing zero-suppressed binary decision diagrams (ZDDs) but software emulations or other representations of ZDDs may be employed to achieve substantially the same results. A computer-readable medium embodying software routines may comprise a magnetically or optically medium, as known in the art. These routines may also be conveyed via a network, and temporarily stored in a communication or network processor before reaching a computer apparatus for execution. Typically, a keyboard and pointing device (e.g., a mouse) is used to supply inputs to a GUI (graphical user interface) of a processor. The GUI also is used to provide results to the user. A processor (desktop, handheld, or other portable computing device) typically implements the method. Access and transfer of data may occur locally or via a network, e.g. the Internet or a LAN. Also, the illustration was directed to a product configuration business rule, but may be extended to other scenarios to the same extent described in the incorporated and related patents and patent applications. Accordingly, the disclosure is not intended to limit the scope of the invention set forth by the appended claims.
Appendix Notation Used
The notation used for attributes in this document is �Attr� followed by a number. The first attribute in the examples is Attr1.
The notation for enumerations is �Enum� followed by two numbers. The first number is the attribute that it belongs to. The second number is its number within the attribute from 1 to 5.
The ellipses symbol �. . . � is used to show a range of enumerations.
For convenience and illustration, every attribute in the examples shown herein has five (5) enumerations.
The word �related� means that the attributes are in the same rule. The double arrow symbol �←→� also means that the attributes are related.
Batch Validation Routine
Description: Routine to quickly get validity for a large group of selections. Does not provide any advice information. Multi-OR is not supported. A work around is to split out the multiple enumerations in a selection, into separate selections. Handles fully specified selections and partially specified selections.
Exemplary Code
The batch validation routine must be called through an API interface, it is not executed during the engine advice run. The main entry point is FindValidPicksFromBatch.
Proc: SkipOverBlanks
Skip over blanks in the pick set.
\**********************************************************************************
int SkipOverBlanks(PickInfo &p, int nRow, int nCol, int findex)
while ( ((findex != p.aTrans[nCol]) &&
(p.aPicks[nRow][nCol] == 0) &&
(nCol < p.nTotPickCols)) ||
(p.aPickIncludeGroup[nCol] == UNINITIALIZED_VALUE) )
nCol++;
if (nCol >= p.nTotPickCols)
nCol = p.nTotPickCols−1;
return nCol;
Proc: FindValidPicksFromBatch
This routine will search a set of picks and fill in the validity column for
those that are valid. It is given a two dimensional array that has the picks
in it. This array must be sorted. The aTrans array translates columns in the
pick array to indexes in the tree.
\***************************************************************************************
RebsDD_API FindValidPicksFromBatch(PickInfo &p)
nCol, nRow;
BddErrorCode
retVal = ecSuccess;
if ((ecSuccess == (retVal = GetBddFromHandle(p.hBddX, &p.fX, &p.ddX))) &&
(ecSuccess == (retVal = GetBddFromHandle(p.hBddI, &p.fI, &p.ddI))) )
// Include finder
bPickFS, bPrevPickFS;
nNumGroups = g_ManagerTableArray[p.hBddI].nGroups;
&aEnumInGroup = GetVariableGroups(p.hManagerI);
&aGroupUsed = g_ManagerTableArray[p.hManagerI].aGroupUsed;
p.aPickForGroup = (int *)calloc(nNumGroups, sizeof(int));
p.aIndexUsed.assign(g_ManagerTableArray[p.hManagerI].aIndexUsed);
p.aPickIncludeGroup = (int *)calloc(p.nTotPickCols, sizeof(int));
p.aSNodes = (Dm_Node **)malloc(p.nTotPickCols* sizeof(Dm_Node *));
for (nCol=0; nCol<p.nTotPickCols; nCol++)
p.aSNodes[nCol] = NULL;
// Build the array to tell if a pick is specified in the include.
int nGroup = aEnumInGroup[p.aTrans[nCol]];
if (aGroupUsed[nGroup])
p.aPickIncludeGroup[nCol] = nGroup;
p.aPickIncludeGroup[nCol] = UNINITIALIZED_VALUE;
// Make the Picks order match the trees order.
The array is expected to be in the correct column order
and sorted row-wise. The array should also be sorted row-wise
in a descending fashion.
bPrevPickFS = false;
for (nRow=0; nRow<p.nTotPickRows; nRow++)
Dm_Node
*pZdd = p.fI;
nMatchCol = 0;
// Only do checks if validity hasn't already been determined.
bPickFS = true;
if (p.aPicks[nRow][p.nValidityCol] == UNINITIALIZED_VALUE)
// Determine if this row is FS.
for (int nGroup=0; nGroup<nNumGroups; nGroup++)
if ((p.aPickForGroup[nGroup] == UNINITIALIZED_VALUE) &&
aGroupUsed[nGroup])
bPickFS = false;
if (bPickFS)
// Find matching column between this row and previous row.
if (bPrevPickFS)
if (p.aPicks[nRow−1][nCol] != p.aPicks[nRow][nCol])
if ((p.aPicks[nRow][nCol] == 1) && (p.aSNodes[nCol]
!= NULL))
pZdd = p.aSNodes[nCol];
nMatchCol = nCol;
FindValidPicksIFS(p.ddI, pZdd, p, nRow, nMatchCol);
// Initialize the group array by filling it with the picks.
memset(p.aPickForGroup, UNINITIALIZED_VALUE, nNumGroups *
sizeof(int));
if (p.aPickIncludeGroup[nCol] != UNINITIALIZED_VALUE)
int nPickValue = p.aTrans[nCol];
if (p.apicks[nRow][nCol] == 1)
p.aPickForGroup[ p.aPickIncludeGroup[nCol] ] =
nPickValue;
nMatchCol = SkipOverBlanks(p,nRow, nMatchCol, pZdd->index);
FindValidPicksICover(p.ddI, pZdd, p, nRow, nMatchCol);
bPrevPickFS = bPickFS;
// Cleanup the include finder.
free(p.aSNodes);
free(p.aPickIncludeGroup);
free(p.aPickForGroup);
// Debug print the Picks array
sDebug[255];
OutputDebugString(�Picks:\n�);
DebugDump1dArray(� �, p.aTrans, p.nTotPickCols, �%3.3d �, �Val\n�);
sprintf(sDebug, �%d: �, nRow);
DebugDump1dArray(sDebug, p.aPicks[nRow], p.nTotPickCols+1, �[%d]
�, �\n�);
// Exclude finder
// Alloc the memory
p.aExCounts = (int *)calloc(p.ddX->sizeZ, sizeof(int *));
p.aExCurPath = (int *)calloc(p.ddX->sizeZ, sizeof(int *));
// Copy the include picks to the exclude picks.
p.aExPicks = (int **)malloc(p.nTotPickRows * sizeof(int *));
bFoundInInclude = false;
// Set the validity column.
p.aExPicks[nRow] = (int *)calloc((p.ddX->sizeZ+1), sizeof(int));
p.aExPicks[nRow][p.ddX->sizeZ] = p.aPicks[nRow][p.nValidityCol];
// Set the individual indexes.
p.aExPicks[nRow][nPickValue] = 1;
p.aExCounts[nPickValue]++;
bFoundInInclude = true;
if (!bFoundInInclude || (p.nTotPickCols == 0))
p.aExPicks[nRow][p.ddX->sizeZ] = 1;
DebugDump1dArray(sDebug, p.aExPicks[nRow], p.ddX->sizeZ+1, �.�,
�\n�);
DebugDump1dArray(�Cnts: �, p.aExCounts, p.ddX->sizeZ, �.�, �\n�);
// Exclude any picks that have all of the indexes from any path of
// the exclude tree.
p.aExPathLen = 0;
FindValidPicksX(p.ddX, p.fX, p, 0, 0);
// Move the validity column from the exclude picks to the include picks.
p.aPicks[nRow][p.nValidityCol] = p.aExPicks[nRow][p.ddX->sizeZ];
// Cleanup the exclude finder.
// Free the array elements
free(p.aExPicks[nRow]);
free(p.aExPicks);
free(p.aExCounts);
free(p.aExCurPath);
p.aIndexUsed.setSize(0);
// Debug print the results
OutputDebugString (�Picks:\n�);
Proc: FindValidPicksX
bool FindValidPicksX(Dm_Manager *ddX, Dm_Node *fX, PickInfo &p, int nPickRow, int
nPickCol)
nRow, nCol, nPickIndex;
if (fX == Dm_ONE(ddX))
// We are at the end of a complete path to 1.
// Now we will find any picks which have all of the current path on it.
bool bFoundAValid = false;
// Assume that we have found a row to exclude.
bFoundARowToExclude = true;
// Only check rows that are valid.
if (p.aExPicks[nRow][p.ddX->sizeZ] == 1)
for (nPickIndex=0; nPickIndex<p.aExPathLen; nPickIndex++)
if (p.aExPicks[nRow][ p.aExCurPath[nPickIndex] ] == 0)
bFoundARowToExclude = false;
// We found a row that needs to be excluded.
if (bFoundARowToExclude == true)
// Set the validity for this row to zero and decrease the
p.aExPicks[nRow][p.ddX->sizeZ] = 0;
// Update the counts for every index on the path.
for (nCol=0; nCol<p.ddX->sizeZ; nCol++)
if (p.aExPicks[nRow][nCol] == 1)
p.aExCounts[nCol]−−;
bFoundAValid = true;
bRet = ! bFoundAValid;
} else if (fX == Dm_ZERO(ddX)) {
// If the count is zero (or less) for this index, then there aren't
// any more valid rows with this index.
if (p.aExCounts[fX->index] > 0)
p.aExCurPath[p.aExPathLen++] = fX->index; // Add the current index
to the path.
// Move down the then branch for this subtree.
bRet = FindValidPicksX(ddX, Dm_T(fX), p, nPickRow, nPickCol+1);
p.aExPathLen−−; // Remove the topmost index from the path.
// Move down the else branch for this subtree.
bRet = FindValidPicksX(ddX, Dm_E(fX), p, nPickRow, nPickCol);
Proc: FindValidPicksIFS
Find out if the fully specified pick in row nPickRow is in the zdd.
Since the picks are fully specified, we can make the correct decision at
node of the tree. We don't have to search for parts of the pick
throughout the tree.
\********************************************************************************
int FindValidPicksIFS(Dm_Manager *dd, Dm_Node *f, PickInfo &p, int nPickRow, int
nRet = 0;
*pElse;
if (f == Dm_ONE(dd))
p.aPicks[nPickRow][p.nValidityCol] = 1;
return nPickCol;
if (f == Dm_ZERO(dd))
// Skip over blank columns
nPickCol = SkipOverBlanks(p, nPickRow, nPickCol, f->index);
// Put this node in the cache.
if (f->index == p.aTrans[nPickCol])
p.aSNodes[nPickCol] = f;
// Check if node matches the current pick column value.
if ((f->index == p.aTrans[nPickCol]) && (p.aPicks[nPickRow][nPickCol] == 1))
// Its a match, so try next node & pick column.
nRet = FindValidPicksIFS(dd, Dm_T(f), p, nPickRow, nPickCol+1);
pElse = Dm_E(f);
if (!Dm_IsConstant(pElse))
nRet = FindValidPicksIFS(dd, pElse, p, nPickRow, nPickCol);
p.aPicks[nPickRow][p.nValidityCol] = 0;
nRet = nPickCol;
Proc: FindValidPicksICover
Find out if the pick in row nPickRow is in the zdd. The specified pick may be
a cover. So this routine will skip over non-matching picks as if they are
DC's.
I may be able to use the path rule that �only 1 member of a group can be on a
path to one�. If I have hit any other member of the current picks group, then
I can ignore the whole �Then� subtree. We may need to add an array that is the
size of #groupsInModel. At the beginning of a path, we clear out this array.
As we go down the path, we fill in this array. If we hit a pick that already
an element in its group position, then we can stop processing that pick. This
would allow us to exit paths much earlier.
\****************************************************************************************
int FindValidPicksICover(Dm_Manager *dd, Dm_Node *f, PickInfo &p, int nPickRow, int
// Check if we are already valid.
if (p.aPicks[nPickRow][p.nValidityCol] == 1)
if ((f == Dm_ONE(dd)) && (nPickCol < p.nTotPickCols))
bAllUnused = true;
for (ix=nPickCol; ix<p.nTotPickCols; ix++)
if ((p.aPicks[nPickRow][nPickCol] == 1) &&
(p.aPickIncludeGroup[ix] != UNINITIALIZED_VALUE))
bAllUnused = false;
if (bAllUnused)
// Handle the case where an index isn't in the tree at all.
if (p.aIndexUsed[p.aTrans[nPickCol]] == false)
if (p.aPickIncludeGroup[nPickCol] == UNINITIALIZED_VALUE)
// This index is an Always.
if ((p.aPicks[nPickRow][nPickCol] == 0) && (nPickCol ==
p.nTotPickCols))
// We were at the last column, so this row is valid.
nPickCol++;
// This index is a Never.
if (p.aPicks[nPickRow][nPickCol] == 1)
// Column is unused by include, so skip this column.
return FindValidPicksICover(dd, f, p, nPickRow, ++nPickCol);
if (dd->permZ[f->index] < dd->permZ[p.aTrans[nPickCol]])
// We are at a node index in the tree that is higher than the next picks index.
// We can skip the entire then side of this node if it is a member of
// a group that we already have a pick for. So we only check the then side
// if the aPickForGroup is empty for its group.
if (p.aPickForGroup[ aEnumInGroup[f->index] ] == UNINITIALIZED_VALUE)
nRet = FindValidPicksICover(dd, Dm_T(f), p, nPickRow, nPickCol);
nRet = FindValidPicksICover(dd, Dm_E(f), p, nPickRow, nPickCol);
} else if (f->index == p.aTrans[nPickCol]) {
bool bFoundLastPick = true;
if (npickCol < p.nTotPickCols)
for (nCol=nPickCol+1; nCol<p.nTotPickCols; nCol++)
if (p.aPicks[nPickRow][nCol] == 1)
bFoundLastPick = false;
if (bFoundLastPick == true)
nRet = FindValidPicksICover(dd, Dm_T(f), p, nPickRow, nPickCol+1);
nRet = FindValidPicksICover(dd, Dm_E(f), p, nPickRow, nPickCol+1);
// We are at a node in the tree that is deeper than the next pick that we
// were looking for. So, we can skip the rest of this subtree.
if (p.aPicks[nPickRow][p.nValidityCol] != 1)
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5212771Apr 27, 1990May 18, 1993Bachman Information Systems, Inc.System for establishing concurrent high level and low level processes in a diagram window through process explosion and implosion subsystemsUS5301284Jan 16, 1991Apr 5, 1994Walker-Estes CorporationMixed-resolution, N-dimensional object space method and apparatusUS5311424 *Jun 28, 1991May 10, 1994International Business Machines CorporationMethod and system for product configuration definition and trackingUS5576965Apr 12, 1993Nov 19, 1996Hitachi, Ltd.Method and apparatus for aiding of designing processUS5630025Jul 13, 1994May 13, 1997Unisys CorporationGeneralized configurator using a declaratively constructed two-level bi-partite graph as a knowledge representationUS5701400 *Mar 8, 1995Dec 23, 1997Amado; Carlos ArmandoMethod and apparatus for applying if-then-else rules to data sets in a relational data base and generating from the results of application of said rules a database of diagnostics linked to said data sets to aid executive analysis of financial dataUS5745765Oct 23, 1995Apr 28, 1998Calico Technology, Inc.Method and apparatus for automatic and interactive configuration of custom productsUS5805462 *Aug 18, 1995Sep 8, 1998Vlsi Technology, Inc.Automatic synthesis of integrated circuits employing boolean decompositionUS5809212Dec 18, 1996Sep 15, 1998New York UniversityConditional transition networks and computational processes for use interactive computer-based systemsUS5844554Sep 17, 1996Dec 1, 1998Bt Squared Technologies, Inc.Computer implemented method to generate a user productUS5877966Mar 18, 1996Mar 2, 1999Pantheon Solutions, Inc.System and method for creating configurations using templatesUS5910898Dec 14, 1995Jun 8, 1999Viewlogic Systems, Inc.Method for verifying structural equivalenceUS5924077 *Dec 29, 1995Jul 13, 1999Sapient Solutions, LlcComputer based system for monitoring and processing data collected at the point of sale of goods and servicesUS5963953Mar 30, 1998Oct 5, 1999Siebel Systems, Inc.Method, and system for product configurationUS5987473Dec 29, 1997Nov 16, 1999Beologic A/SInteractive configuration via networkUS6002854Mar 10, 1997Dec 14, 1999Trilogy Developmetn Group, Inc.Method and apparatus for configuring systemsUS6016394Sep 17, 1997Jan 18, 2000Tenfold CorporationMethod and system for database application software creation requiring minimal programmingUS6031984Mar 9, 1998Feb 29, 2000I2 Technologies, Inc.Method and apparatus for optimizing constraint modelsUS6035305Aug 29, 1997Mar 7, 2000The Boeing CompanyComputer-based method of structuring product configuration information and configuring a productUS6064982Nov 12, 1997May 16, 2000Netscape Communication CorporationSmart configuratorUS6076080Nov 4, 1997Jun 13, 2000The Standard Register CompanyForms order entry systemUS6163876Nov 6, 1998Dec 19, 2000Nec Usa, Inc.Method for verification of RTL generated from scheduled behavior in a high-level synthesis flowUS6182275 *Jan 26, 1998Jan 30, 2001Dell Usa, L.P.Generation of a compatible order for a computer systemUS6256618Apr 23, 1998Jul 3, 2001Christopher SpoonerComputer architecture using self-manipulating treesUS6321186 *May 3, 1999Nov 20, 2001Motorola, Inc.Method and apparatus for integrated circuit design verificationUS6327581Apr 6, 1998Dec 4, 2001Microsoft CorporationMethods and apparatus for building a support vector machine classifierUS6349290Jun 30, 1999Feb 19, 2002Citibank, N.A.Automated system and method for customized and personalized presentation of products and services of a financial institutionUS6385617Oct 7, 1999May 7, 2002International Business Machines CorporationMethod and apparatus for creating and manipulating a compressed binary decision diagram in a data processing systemUS6389576Sep 2, 1999May 14, 2002Sun Microsystems, Inc.Method and apparatus for optimizing real functions in Boolean domainUS6396488Jan 4, 1999May 28, 2002Corel Inc.System and method for determining a path in a graphical diagramUS6424962Sep 19, 1997Jul 23, 2002Bull S.A.Method of automated proving for unrestricted first-order logicUS6442732Apr 21, 1999Aug 27, 2002Lucent Technologies, Inc.Virtual logic system for solving satisfiability problems using reconfigurable hardwareUS6519767 *Jun 7, 1995Feb 11, 2003Microsoft CorporationCompiler and method for automatically building version compatible object applicationsUS6529890Aug 19, 1998Mar 4, 2003Ensys, Inc.Method for representing synoptic climatology information in a class-object-attribute hierarchy and an expert system for obtaining synoptic climatology informationUS6535883 *Aug 4, 1999Mar 18, 2003Mdsi Software SrlSystem and method for creating validation rules used to confirm input dataUS6556978Mar 8, 2000Apr 29, 2003The State Of Oregon Acting By And Through The State Board Of Higher Education On Behalf Of The University Of OregonSatisfiability algorithms and finite quantificationUS6567814Aug 26, 1999May 20, 2003Thinkanalytics LtdMethod and apparatus for knowledge discovery in databasesUS6598035 *Oct 15, 2001Jul 22, 2003International Business Machines CorporationObject oriented rule-based expert system framework mechanismUS6651096 *Apr 20, 1999Nov 18, 2003Cisco Technology, Inc.Method and apparatus for organizing, storing and evaluating access control listsUS6658458Jun 22, 2000Dec 2, 2003Cisco Technology, Inc.Cascading associative memory arrangementUS6741975Aug 31, 2000May 25, 2004Ncr CorporationRule based expert system for consumer preferenceUS6795832 *Oct 9, 2001Sep 21, 2004Hewlett-Packard Development Company, L.P.Rule based compatibility moduleUS6874016Oct 14, 2003Mar 29, 2005Cisco Technology, Inc.Information searching deviceUS6952812Feb 13, 2001Oct 4, 2005Freescale Semiconductor, Inc.Design analysis tool for path extraction and false path identification and method thereofUS6961913 *Nov 8, 2000Nov 1, 2005Matsushita Electric Industrial Co., Ltd.IP base LSI designing system and designing methodUS6983187 *Aug 14, 2003Jan 3, 2006Sap AktiengesellschaftMethod and system for automatically generating selection conditions in a product configuration systemUS7130783Jan 12, 2001Oct 31, 2006Synopsys, Inc.Simulation-based functional verification of microcircuit designsUS7188333 *Jan 22, 2002Mar 6, 2007Sprint Communications Company L.P.Product incompatibility systemUS20010029499Dec 28, 2000Oct 11, 2001Tuatini Jeffrey TaihanaRules processing systemUS20020065701Nov 30, 2000May 30, 2002Kim Kyu DongSystem and method for automating a process of business decision and workflowUS20020078431Feb 2, 2001Jun 20, 2002Reps Thomas W.Method for representing information in a highly compressed fashionUS20020095645Jan 16, 2001Jul 18, 2002International Business Machines CorporationSearching for counter-examples intelligentlyUS20020108093Dec 11, 2000Aug 8, 2002Intel CorporationMethod and system for formal verification of a circuit modelUS20020112213Feb 13, 2001Aug 15, 2002Abadir Magdy S.Design analysis tool for path extraction and false path identification and method thereofUS20020165701 *Nov 30, 2001Nov 7, 2002Jakob LichtenbergMethod of configuring a productUS20020178432Aug 16, 2001Nov 28, 2002Hyungwon KimMethod and system for synthesizing a circuit representation into a new circuit representation having greater unatenessWO1999048031A1Mar 16, 1999Sep 23, 1999Array Technology ApsA database useful for configuring and/or optimizing a system and a method for generating the database* Cited by examinerNon-Patent CitationsReference1 *"Array". Microsoft Computer Dictionary, Fifth Edition. May 1, 2002. 5th ed.2Anderson, An Introduction to Binary Decision Diagrams, University of Denmark, Oct. 1997, pp. 8-11.3Beck, M., et al., Enabling Full Service Surrogates Using the Portable Channel Representation, Proceedings of the Tenth International Conference on World Wide Web, Apr. 2001, pp. 376-385.4Bryant, Binary Decision Diagrams and Beyond, Enabling Technologies for Formal Verification, IEEE, 1995, pp. 236-243.5Cabodi, et al., Symbolic Traversals of Data Paths with Auxilary Variables, IEEE, 1994, pp. 93-96.6Cosnard, et al., Automatic Task Graph Generation Techniques, Proceedings of the Twenty-Eighth Hawaii International Conference on System Sciences, Vo. 2, Jan. 3, 1995, pp. 113-122.7Cugola, G, et al., Exploiting an event-based infrastructure to develop complex distributed systems, Proceedings of the 20th International Conference on Software Engineering, Apr. 1998, pp. 261-270.8Ejnioui, et al., Design Partitioning on Single-chip Emulations Systems, Thirteenth International Conference on VLSI Design, Jan. 3, 2000, pp. 234-239.9F. Aloul, M. Mneimneh, and K. Sakallah "ZBDD-Based Backtrack Search SAT Solver" International Workshop on Logic Synthesis (IWLS), New Orleans, Louisiana, pp. 131-136, 2002. url=http://www.eecs.umich.edu/~faloul/.10Gottlob, et al., The complexity of acyclic conjuctive queries, 39th Annual Symposium on Foundations of Computer Science Proceedings, Nov. 8, 1998, pp. 706-715.11J Moller, HR Andersen, H Hulgaard, "Product Configuration over the Internet presented at", The 6th INFORMS Conference on Information Systems and Technology, Nov. 3-4, 2001, Miami Beach, Florida.12Jesper Moller "Configuration and E-commerce", IFORS Jul. 2002.13Kurihara, et al., BDD Encoding for Partial Order Constraints and its Application to Expert Systems in Software Verification Domains, 2000 IEEE International Conference on Systems, Man, Cybernetics, vol. 3, 8-11, Oct. 2000, pp. 2062-2067.14 *Mianto, Shin-ichi. "Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems" 1993, ACM, 30th ACM/IEEE Design Automation Conference. pp. 272-277.15 *Mianto, Shin-ichi. "Zero-Suppressed BDDs for Set Manipulations in Combinatorial Problems" 1993, ACM, 30th ACM/IEEE Design Automation Conference. pp. 272-277.16Minato, S., "Zero-Suppressed BDDs and Their Applications", International Journal on Software Tools for Technology Transfer, vol. 3, No. 2, pp. 156-170, Springer, May 2001.17Minato, S., Representations of Discrete Funtions, Chapter 1, Graph-Based Representations of Discrete Functions, Sasao and Fujia, ed.s, 1996, Kluwer Academic Publishing, pp. 1-23.18 *Mishchenko, Alan. "An Introduction to Zero-Suppressed Binary Decision Diagrams" 2001, Jun. 8, Department of Electrical Engineering Portalnd State University. pp. 1-15.19Panda, et al., Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams, Proceedings of the 1994 IEEE/ACM International Conference on Computer-Aided Design, Nov. 1994, pp. 628-631.20USPTO; File History U.S. Appl. No. 10/950,809 to Huelsman et al., filed Sep. 28, 2004; Part 1, Sep. 2004 through Dec. 2007.21USPTO; File History U.S. Appl. No. 10/950,809 to Huelsman et al., filed Sep. 28, 2004; Part 2, Mar. 2007 through May 2008.22USPTO; File History U.S. Appl. No. 10/950,809 to Huelsman et al., filed Sep. 28, 2004; Part 3, May 2008 through Aug. 2008.23USPTO; File History U.S. Appl. No. 10/950,809 to Huelsman et al., filed Sep. 28, 2004; Part 4, Aug. 2008 through Feb. 2009.24USPTO; File History U.S. Appl. No. 10/950,815 to Huelsman et al., filed Sep. 28, 2004; Part 1, Sep. 2004 through Feb. 2007.25USPTO; File History U.S. Appl. No. 10/950,815 to Huelsman et al., filed Sep. 28, 2004; Part 2, May 2007 through Feb. 2009.26Yang, Optimizing Model Checking Based on BDD Characterization,Thesis, Carnegie Melon U.,May 1999, pp. 9-11.* Cited by examinerClassifications U.S. Classification706/45, 706/47International ClassificationG06F17/30, G06N5/00, G06Q30/00Cooperative ClassificationG06Q30/06European ClassificationG06Q30/06Legal EventsDateCodeEventDescriptionJan 2, 2013FPAYFee paymentYear of fee payment: 4Mar 15, 2011CCCertificate of correctionAug 8, 2007ASAssignmentOwner name: RESOLUTIONEBS, INC., OHIOFree format text: PARTIAL RELEASE OF SECURITY INTEREST;ASSIGNOR:VENTURE LENDING & LEASING IV, INC.;REEL/FRAME:019658/0805Effective date: 20070611Owner name: VERDE SABOR ASSETS, L.L.C., DELAWAREFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:RESOLUTIONEBS, INC.;REEL/FRAME:019658/0827Effective date: 20070607Owner name: RESOLUTIONEBS, INC.,OHIOFree format text: PARTIAL RELEASE OF SECURITY INTEREST;ASSIGNOR:VENTURE LENDING & LEASING IV, INC.;REEL/FRAME:19658/805Owner name: VERDE SABOR ASSETS, L.L.C.,DELAWAREFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:RESOLUTIONEBS, INC.;REEL/FRAME:19658/827Aug 1, 2005ASAssignmentOwner name: VENTURE LENDING & LEASING IV, INC., CALIFORNIAFree format text: SECURITY INTEREST;ASSIGNOR:RESOLUTIN EBS, INC.;REEL/FRAME:016829/0435Effective date: 20050622Dec 20, 2004ASAssignmentOwner name: RESOLUTIONEBS, INC., OHIOFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:HUELSMAN, DAVID L.;LOVE, SHARON E.;MAIR, DOUGLAS M.;REEL/FRAME:016091/0216Effective date: 20041012RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google