Methods and systems for determining circular dependency
Patent 7188093 Issued on March 6, 2007. Estimated Expiration Date: 
October 1, 2021. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
October 1, 2021. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.Patent ReferencesMethod and apparatus for testing an object management system Software redevelopment system Non-recursive method for parameter evaluation within an information management system System of relational entities for object-oriented computer-aided geometric design Apparatus and method for controlling delivery of unsolicited electronic mail Systems and methods for facilitating the exchange of information between separate business entities Patent #: 6115642 InventorAssigneeApplicationNo. 09968194 filed on 10/01/2001US Classes:706/55, Semantic network (e.g., conceptual dependency, fact based structure)707/1, DATABASE OR FILE ACCESSING345/420, Solid modelling709/202, Processing agent700/104Knowledge based (e.g., expert system)ExaminersPrimary: Knight, AnthonyAssistant: Holmes, Michael B. Attorney, Agent or FirmInternational ClassG06F 17/00DescriptionTECHNICAL FIELD This invention relates generally to dependencies. More particularly, the present invention relates to methods and systems for determining circular dependency in a plurality of dependency rules. BACKGROUND OF THE INVENTION A concern in the design and verification of systems is dependencies. Dependencies may be static, remaining the same over the life of the system, or they may change over time. A dependency is a relationship between two items within which a change to one item, the independent object(s) may affect the meaning of the other item, the dependent object. For example, the dependency rule that object A depends on object B,object C, and object D may be illustrated as follows: A→B C D A dependent object in one dependency rule may be an independent object in another dependency rule. In addition, it is often not desirable to have circular dependencies in a system. The following three dependency rules, for example, result in acircular dependency: A→B B→C C→A In particular, if A, B, and C, in the above example, are vehicles in different locations of a road and the dependency refers to the right of way, circular dependency cannot be allowed in order to avoid an accident. One approach for determining the existence of circular dependency is to manually review the dependency rules. This process is typically time consuming and labor intensive. In addition, as the number of dependency rules increases, it isdifficult, if not impossible, to manually check for circular dependency. Therefore, there is a need for further methods for determining the existence of circular dependency in a plurality of dependency rules. SUMMARY OF THE INVENTION The above need is met by the present invention which in one aspect provides a method for use in determining whether circular dependency exists in a plurality of dependency rules. The method includes generating for at least some of the pluralityof dependency rules a plurality of exclusion lists. Each exclusion list is associated with at least one independent object of a dependency rule and lists as an item a dependent object of the dependency rule. Where an item listed in one of the generatedexclusion lists corresponds to an independent object having its own exclusion list with at least one item, the at least one item is incorporated into the generated exclusion list. A determination is made whether at least one of the generated exclusionlists for an independent object includes an item corresponding to the independent object. Where at least one of the generated exclusion lists for an independent object includes an item corresponding to the independent object, circular dependency isfound, if not and if all the dependency rules have been read, circular dependency is not found. Systems and computer program products corresponding to the above-summarized method is also described and claimed herein. BRIEF DESCRIPTION OF THE DRAWINGS The present invention will now be described, by way of example only, with reference to preferred embodiments thereof, as illustrated in the drawings in which: FIG. 1 is a flowchart of one example of a process for determining whether circular object dependency exists in a plurality of dependency rules in accordance with an aspect of the present invention; FIG. 2 is an illustration of the results for determining whether circular object dependency exists in a plurality of dependency rules using the process of FIG. 1 in accordance with an aspect of the present invention; and FIG. 3 depicts one example of an overview computing system which can be used to implement an intellectual property management facility in accordance with an aspect of the present invention. BEST MODE FOR CARRYING OUT THE INVENTION The present invention is directed to methods and systems for systematically determining whether circular dependency exists in a plurality of dependency rules. For example, the method may be implemented to determine whether circular dependencyexists in a computer program so that steps may be taken to prevent undesirable consequences. As explained in greater detail below, by providing one or more exclusion lists for one or more of the dependent objects in the dependency rules, it is possible to identify whether circular dependency exists in the dependency rules. FIG. 1 illustrates a flowchart of one example of a process 10 for determining whether circular dependency exists in a plurality of dependency rules. Initially, the various steps of FIG. 1 are described, and thereafter the steps are applied toseveral examples. Initially, a first one of a plurality of dependency rules is read or analyzed at 20. At 30, one or more exclusion lists are generated. As described in greater detail below, the generated exclusion lists for each independent object identifies orlists as an item the dependent object. As used herein, the term "generating" is meant to include the creating of separate exclusion lists for each dependency rule and/or extending, expanding, or adding to existing exclusion lists. At 40, a determination is made whether the listed item(s), e.g., dependent object(s), have their own exclusion lists. If the listed item(s) have their own exclusion list(s), the listed items in those exclusion lists are incorporated in thegenerated exclusion list(s) at 50. Thereafter, for each generated exclusion list for an independent object, a determination is made as to whether a listed item corresponds to the independent object at 60. If an item corresponds to an independentobject, circular dependency is found at 70. If circular dependency is not found, it is next determined whether there are any unread or unanalyzed dependency rules at 80. If there are one or more unread dependency rules, a next dependency rule is read, at 20, and the process is repeated. That is, further exclusion list(s) are generated (e.g., created or extended) at 30, if the listed item(s) have their own exclusion list(s), the listed items in those exclusion lists are incorporated at 50. Again, at 60, a determination is made as towhether for each generated exclusion list for an independent object a listed item corresponds to the independent object. If an item corresponds to the independent object, circular dependency is found at 70. If circular dependency is not found, it is determined whether there are any further unread dependency rules at 80. If there are no further unread dependency rules, then at 90, no circular dependency exists for the plurality of dependency rules. The above-described illustrated process is further understood in connection with the following examples. EXAMPLE 1 In this example, two dependency rules include, first, object A being dependent on object B, and second, object B being dependent on object A. These two dependency rules may be represented as follows: A→B B→A With reference again to FIG. 1, the first step is to read the first dependency rule, A→B, (at 20) and to create a first exclusion list for independent object B by listing as an item dependent object A (at 30) which may be represented asfollows: B:A At this point, there is no exclusion list for item A (at 40), nor is independent object B found in the exclusion list for independent object B (at 60). Since a second dependency rule exists and has not been read (at 80), the second dependencyrule, B→A, is read (at 20). A second exclusion list for independent object A is generated by listing as an item dependent object B (at 30), as follows: A:B At this point, there is an exclusion list for item B (i.e., B:A above) and item A in the first exclusion list is incorporated into the second exclusion list (at 50), as follows: A:B A Item A is found in the exclusion list for independent object A (at 60), and thus, circular dependency is found (at 70). EXAMPLE 2 In this example, two dependency rules include, first, object A being dependent on object B, and second, object B being dependent on object C, which may be represented as follows: A→B B→C The first dependency rule, A→B is read (at 20), and a first exclusion list for independent object B is generated listing as an item dependent object A (at 30), as follows: B:A At this point, there is no exclusion list for item A (at 40), nor is item B found in the exclusion list for independent object B (at 60). Since a second dependency rule exists and has not been read (at 80), second dependency rule, B→C, isread (at 20). A second exclusion list for independent object C is generated by listing as an item independent object B (at 30), as follows: C:B At this point, there is an exclusion list for item B (i.e., B:A above) and item A in the first exclusion list is incorporated into the second exclusion list (at 50), as follows: C:B A Item C is not found in the exclusion list for independent object C (at 60). All of the dependency rules have been read (at 80), and thus, circular dependency is not found (at 90). EXAMPLE 3 In this example, four dependency rules include the following: A→B C B→C D D→E E→C A A first exclusion list and second exclusion list for independent objects B and C are generated listing as an item dependent object A as follows: B:A C:A There are no exclusion lists for item A, nor is item B found in the exclusion list for independent object B or item C found in the exclusion list for independent object C. Thus the next dependency rule (B→C D) is read resulting in thefollowing exclusion lists: C:B D:B Since item B has it own exclusion list (i.e., B:A, above), item A is incorporated into the exclusion lists for independent objects C and D as follows: C:B A D:B A Since item C is not found in the exclusion list for independent object C and item D is not found in the exclusion list for independent object D, the next dependency rule (D→E) is read resulting in the following exclusion list: E:D The items for the exclusion list for independent object D (i.e., D:B A) are incorporated into the exclusion list for independent object E as follows: E:D B A Since item E is not found in the exclusion list for independent object E, the next dependency rule (E→C A) is read resulting in the following exclusion lists: C:E A:E The items for the exclusion list for independent object E (i.e., E:D B A) are incorporated into the exclusion list for object C and A resulting in the following: C:E D B A A:E D B A Since item A is found in the exclusion list for independent object A, circular dependency is found. EXAMPLE 4 In this example, three dependency rules include the following: Solomon→David (Solomon is a son of David) David→Jesse (David is a son of Jesse) Jesse→Solomon (Jesse is a son of Solomon) A first exclusion list for the first dependency rule is generated as follows (which means that David cannot be a son of Solomon): David:Solomon A second exclusion list for the second dependency rule is generated as follows (which means that Jesse cannot be a son of David): Jesse:David At this point, there is an exclusion list for David, and Solomon is incorporated into the second exclusion list as follows (which means that Jesse cannot be a son of David or Solomon): Jesse:David Solomon The next dependency rule is read and an exclusion list is generated as follows (which means that Solomon cannot be a son of Jesse): Solomon:Jesse Incorporating the items in the exclusion list for Jesse above into the third exclusion list results in the following: Solomon:Jesse David Solomon Circular dependency is detected as Solomon is on both sides of the exclusion list. In other words, Solomon cannot be a son of Solomon himself. EXAMPLE 5 In this example, two dependency rules include the following A→B Program A will preempt program B (stop program B from running) B→A Program B will preempt program A (stop program A from running) A first exclusion list for the first dependency rule is generated as follows: B:A A second exclusion list for the second dependency rule is generated as follows: A:B There is an exclusion list for independent object B and item A in the first exclusion list is incorporated into the second exclusion list resulting in the following: A:B A Item A is found in the exclusion list for independent object A, and thus, circular dependency is found. In particular, this set of dependency rules can stop both programs A and B from running, and if applied, may prevent a computer fromoperating properly. FIG. 2 illustrates the results for representing and determining whether circular dependency exists in a plurality of dependency rules using the process of FIG. 1. FIG. 2 is illustrated in connection with Example 3 above. In particular, in thisembodiment, a plurality of exclusion lists for the various independent objects are generated and added to (e.g., extended) upon the review of a subsequent one of a plurality of dependency rules. For example, from reading the first dependency rule (A→B C), two exclusion lists are generated and listed at (1). Reading the second dependency rule (B→C D), dependent object B is added as an item to the exclusion list for C and anexclusion list for independent object D is generated at (2a). Thereafter, since item B has its own exclusion list (B:A), item A is added to the exclusion list for independent object B at (2b). None of the exclusion lists includes a respectivecorresponding item. Reading the third dependency rule (D→E), an exclusion list for E is generated at (3a), and since item D has its own exclusion list (D:B A), items B and A are added to the exclusion list for independent object E at (3b). None of theexclusion lists includes a respective corresponding item. At (4a), the fourth dependency rule (E→C A) is read. Dependent object E is added as an item to the exclusion list for independent object C and an exclusion list for A is generated at(4a). Since item E has its own exclusion list (E:D B A), items D, B, and A are added to the exclusion lists for A and C at (4b). The exclusion list for independent object A includes item A. Thus, circular dependency is found for this group of four dependency rules. From the present description, it will be appreciated to those skilled in the art that other ways of illustrating and/or generating exclusion lists or listing the items according the present invention may be equally suitable, e.g., lists, tables,charts, database entries, etc. Accordingly, the term exclusion lists refers to the association of independent objects to various items or dependent objects and is not to be limited to any specific form. From the present description, it will also be appreciated by those skilled in the art that the present invention may be used to detect circular dependency in a plurality of existing dependency rules, as well as detecting circular dependency whensetting up or creating dependency rules. While the present invention may be implemented manually, the present invention may also be suitably implemented in software, hardware, microcode or any combination thereof to operably review a plurality of dependency rules and determine whethercircular dependency is present or review dependency rules as they are created. For a large number of dependency rules, desirably, the processing is automated. Any computing unit, processor, hardware, software, operating system may be suitably employedfor carrying out the aspects of the present invention. One example of a computing environment incorporating and using an intellectual property management facility in accordance with the present invention is depicted in FIG. 3 and described below. Referring to FIG. 3, a computer environment 100 includes, for instance, a computing unit 101 having at least one central processing unit 102, a main storage 104 and one or more input/output devices 106, each of which is described below. As is known, central processing unit 102 is the controlling center of computing unit 101 and provides the sequencing and processing facilities for instruction execution, interruption action, timing functions, initial program loading and othermachine related functions. The central processing unit executes at least one operating system, which as known, is used to control the operation of the computing unit by controlling the execution of other programs, controlling communication withperipheral devices and controlling use of the computer resources. Central processing unit 102 is coupled to main storage 104, which is directly addressable and provides for high speed processing of data by the central processing unit. Main storage may be either physically integrated with the CPU or constructedin stand alone units. The intellectual property database described herein may, in one embodiment, reside within main storage 104. Main storage 104 is also coupled to one or more local or remote input/output devices 106. These devices include, for instance, keyboards, communications controllers, teleprocessing devices, printers, magnetic storage media (e.g., tape, disks),direct access storage devices, and sensor based equipment. Data is transferred from main storage 104 to input/output devices 106, and from the input/output devices back to main storage. In one example, computer environment 100 can be a single system environment, which includes an RS/6000 computer system running an AIX operating system. (RS/6000 and AIX are offered by International Business Machines Corporation). The inventionis not limited to such an environment, however. The capabilities of the present invention can be incorporated and used within many types of computer environments and many types of computer systems. For instance, computer environment 100 can include aUNIX workstation running a UNIX-based operating system. Other variations are also possible and are considered a part of the claimed invention. The present invention can be included, for example, in an article of manufacture (e.g., one or more computer program products) having, for instance, computer usable media. This media has embodied therein, for instance, computer readable programcode means for providing and facilitating the capabilities of the present invention. The articles of manufacture can be included as part of the computer system or sold separately. Additionally, at least one program storage device readable by machine, tangibly embodying at least one program of instructions executable by the machine, to perform the capabilities of the present invention, can be provided. The flow diagrams depicted herein are provided by way of example. There may be variations to these diagrams or the steps (or operations) described herein without departing from the spirit of the invention. For instance, in certain cases, thesteps may be performed in differing order, or steps may be added, deleted or modified. All of these variations are considered to comprise part of the present invention as recited in the appended claims. While the invention has been described in detail herein in accordance with certain preferred embodiments thereof, many modifications and changes therein may be effected by those skilled in the art. Accordingly, it is intended by the appendedclaims to cover all such modifications and changes as fall within the true spirit and scope of the invention. * * * * * |
