Reasoning with rules in a multiple inheritance semantic network with exceptions

• US 5,802,508 A
• Filed: 08/21/1996
• Issued: 09/01/1998
• Est. Priority Date: 08/21/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morgenstern, Leora
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Smith, Jeffrey S.
• Application Number:
  US08/700,973
• Time in Patent Office: 741 Days
• Field of Search: 395/63, 395/64, 706/55, 706/48
• US Class Current: 706/55
• CPC Class Codes: G06N 5/027 Frames

Abstract

A new data structure describes an inheritance network with exceptions, augmented with rules attached to nodes in the network, a background context of rules and information, and an optional prioritization of links in the network. A process that determines which rules apply to classes (nodes) in the taxonomy exploits the structure of the network, in particular specificity and path prioritization, to get preferred maximally consistent subsets of rules that apply at specified nodes.

Claims

1. A computer system with one or more memories and one or more central processing units comprising:

a. a data structure, stored in one or more of the memories, representing a semantic network with three or more nodes connected by two or more links, each of the nodes representing an object, the semantic network describing the way the objects relate to one another, each of the nodes being one of a root node, internal node, and leaf node, the internal nodes and leaf nodes having one or more parent fields pointing to one or more other nodes in the network being parent nodes, the root and internal nodes having one or more child fields pointing to one or more other nodes in the network being child nodes, one or more ancestor nodes being either a parent node or recursively an ancestor of one of the parent nodes, a set of one or more rules attached to one or more of the nodes, a rule being a statement that at least partially regulates the object represented by the respective node and all the rules in the set being consistent;

b. a background data structure, stored in one or more of the memories containing one or more information items, each of the information items being attached to every node in the semantic network and at least partially regulating the objects represented by all the nodes in the semantic network; and

c. a process that proceeds node by node up one or more paths of the links to each ancestor node in the path, creating an interim set of rules by iteratively adding rules attached to each of the ancestors nodes processed only if the added rules are consistent with the rules in the interim set and the background information items, after all the ancestors of the node are processed the interim set being a superset of rules that are all the rules in the semantic network that regulate the node, the superset being a maximally consistent subset of all the rules attached to all of the ancestor nodes.

2. A computer system, as in claim 1, where the parent fields are ordered in a partial order, the partial order arranging the parent fields by dividing a set of parent fields into a sequence of subsets of parent fields, each parent field in any subset being of higher value than any parent field in any succeeding subset but all parent fields in any one of the subsets being of equal value to one another.

3. A computer system, as in claim 2, where the parent fields are ordered in a total order and where the total order is the partial order in which each subset of parent fields has exactly one element.

4. A computer system, as in claim 1, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

5. A computer system, as in claim 4, where the preference criterion is specificity in the semantic network, where specificity is understood as specificity in the semantic network, that is, a first node is more specific than a second node if the first node is a descendant of the second node.

6. A computer system, as in claim 2, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

7. A computer system, as in claim 6, where the preference criterion is a partial order of the parent nodes.

8. A computer system, as in claim 1, where one or more of the links between nodes is a cancel link and the ancestor node connected to the node by the cancel link is not processed by step c.

9. A computer system, as in claim 8, where the parent fields are in a partial order, the partial order arranging the parent fields by dividing a set of parent fields into a sequence of subsets of parent fields, each parent field in any subset being of higher value than any parent field in any succeeding subset but all parent fields in any one of the subsets being of equal value to one another.

20. A system, as in claim 1, where the object includes any one or more of the following:

a thing and an activity.

21. A system, as in claim 20, where the thing includes any one or more of the following:

a drug, a medication, a class of drugs, a price, one or more symptoms, a person, a business application, a brand, an animal, real-world application, a cost, a product, and a life threatening condition.

22. A system, as in claim 20, where the activity includes any one or more of the following:

a therapy, a service, a professional service, a medical service, a doctor'"'"'s visit, a family planning service, a preventive care service, a prescription service, and a diagnostic procedure.

23. A system, as in claim 1, where the information items includes any one or more of the following:

a set of background facts, a list of drugs, a set of background rules, an eligibility criteria, a description of personnel, and a table of pricing.

24. A system, as in claim 1, where the rules that regulate the objects include any one or more of the following:

a regulation about dispensing a drug, a logical formula, a criteria for payment, a method of payment, a criteria for qualification, a criteria for receipt of services, a criteria for discharge, one or more business rules, a cost sharing criteria, an access criteria, an administrative regulation, and a medical regulation.

25. A system, as in claim 9, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

26. A system, as in claim 8, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

27. A system, as in claim 26, where the preference criterion is specificity in the semantic network.

28. A system, as in claim 27, where the preference criteria further includes selecting a preempting path over an associated challenged path.

10. A computer system with one or more memories and one or more central processing units comprising:

a. a data structure, stored in one or more of the memories, representing a semantic network with three or more nodes connected by two or more links, each of the nodes representing an object, the semantic network describing the way the objects relate to one another, each of the nodes being one of a root node, internal node, and leaf node, the internal nodes and leaf nodes having one or more parent fields pointing to one or more other nodes in the network being parent nodes, the root and internal nodes having one or more child fields pointing to one or more other nodes in the network being child nodes, one or more ancestor nodes being either a parent node or recursively an ancestor of one of the parent nodes, a set of one or more rules attached to one or more of the nodes, a rule being a statement that at least partially regulates the object represented by the respective node and all the rules in the set being consistent, the rules being divided into one or more rule categories, the rules in each category being statements partially regulating the objects represented by the respective node and all the rules in the category and in the set being consistent;

b. a background data structure, stored in one or more of the memories containing one or more information items, each of the information items being attached to every node in the semantic network; and

c. a process that transforms the set of rules attached for each category to one or more of the nodes to a superset of rules for each category by proceeding up one or more paths of the links in an order, the paths connecting the node with all the ancestors of the node on each of the paths, the process iteratively adding rules attached for each of the categories to each of the ancestors to form an interim set for each category only if the added rules are consistent with the rules in the interim set for each category and the background information items, the superset of rules for each category being the rules in the interim set for the category after all the ancestors of the node are processed, the superset of rules for each category being all the rules for that category in the semantic network that regulate the node, the superset being a maximally consistent subset of all the rules for that category attached to all of the ancestor nodes.

11. A computer system, as in claim 10, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

12. A computer system, as in claim 10, where one or more of the links between nodes are cancel links and the ancestor node connected to the node by the cancel link is not processed in step c.

13. A computer system, as in claim 10, where the parent fields are ordered in a partial order for each category.

14. A computer system, as in claim 10, where the parent fields are ordered in a total order for each category.

29. A system, as in claim 12, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

30. A system, as in claim 29, where the preference criterion is specificity in the semantic network.

31. A system, as in claim 12, where the parent fields are ordered in a partial order, where a partial order is a method of arranging elements in a set by dividing the set into a sequence of subsets, each member of any subset being of higher value than any member of a directly succeeding subset, but all members of a particular subset being of equal value to one another.

32. A system, as in claim 31, where one or more of the maximally consistent subsets is selected as a preferred maximally consistent subset based on a preference criterion.

33. A system, as in claim 32, where the preference criterion is specificity in the semantic network.

34. A system, as in claim 33, where the preference criteria further includes an order of the parent nodes.

35. A system, as in claim 34, where the preference criteria further includes selecting a preempting path over an associated challenged path, where a preempting path is a unique member of a set of two or more paths from a first node to a second node, such that all paths in the set not equal to the preempting path are preempted by the preempting path.

36. A computer system, as in claim 13, where the preference criterion is specificity in the semantic network.

37. A computer system, as in claim 36, where the preference criteria further includes an order of the parent nodes.

15. A computer system with one or more memories and one or more central processing units comprising:

a. a data structure, stored in one or more of the memories, representing a semantic network with three or more nodes connected by two or more links, each of the nodes representing an object, the semantic network describing the way the objects relate to one another, each of the nodes being one of a root node, internal node, and leaf node, the internal nodes and leaf nodes having one or more parent fields pointing to one or more other nodes in the network being parent nodes, the root and internal nodes having one or more child fields pointing to one or more other nodes in the network being child nodes, one or more ancestor nodes being either a parent node or recursively an ancestor of one of the parent nodes, a set of one or more rules attached to one or more of the nodes, a rule being a statement that at least partially regulates the object represented by the respective node and all the rules in the set being consistent;

b. a background data structure, stored in one or more of the memories containing one or more information items, each of the information items being attached to every node in the semantic network and at least partially regulating the objects represented by all the nodes in the semantic network; and

c. a process that proceeds node by node up one or more paths of the links in an order to each ancestor node in the path, creating an interim set of rules by iteratively adding rules attached to each of the ancestors nodes processed only if the added rules are consistent with the rules in the interim set and the background information items, after all the ancestors of the node are processed the interim set being a superset of rules that are all the rules in the semantic network that regulate the node, the superset being a maximally consistent subset of all the rules attached to all of the ancestor nodes.

16. A method of selecting a set of rules that apply to a focus node of a semantic network of nodes having multiple inheritance, the focus node representing a class of physical objects, comprising the steps of:

a. setting a collected rule set of one or more rules equal to a set of rules attached to a focus node in the semantic network of three or more nodes;

b. determining all of the one or more ancestral nodes in the semantic network that are most distant from the focus node and that have a positive undefeated path between the focus node and the respective ancestral nodes, the ancestral nodes being prime nodes;

c. identifying all of the positive undefeated paths between the focus node and the prime nodes;

d. topologically sorting the positive undefeated paths to determine an order;

e. in the order determined by the topological sort, traversing each of the positive undefeated paths by visiting each of one or more nodes on the positive undefeated path in an upward direction from the focus node to the respective prime node, and at each of the nodes visited, being a visited node, taking the preferred maximally consistent subset of the collected rule set and the rules attached to the visited node to create a new collected rule set; and

f. after traversing all of the positive undefeated paths, taking the new collected rule set as a final set of rules that apply to the focus node.

17. A method, as in claim 16, where each of the nodes are marked once the node is visited and there is no preferred maximally consistent subset determined at the marked nodes.

18. A method, as in claim 17, where the positive undefeated paths are grouped into independent groups of one independent positive undefeated path per independent group and preempting groups that contain one preempting path and one or more challenged paths that are preempted by their associated preempting path and where a preempting path is a unique member of a set of two or more paths from one node to a second node, such that all paths in the set not equal to the preempting path are preempted by the preempting path.

19. A method, as in claim 17, where the topological sorting is done for each of one or more rule types, there is a separate order for each of the rule types, and the marking during traversal is done for each of the orders.