Method and system for automatically assembling processing graphs in information processing systems

• US 8,370,812 B2
• Filed: 04/02/2007
• Issued: 02/05/2013
• Est. Priority Date: 04/02/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Feblowitz, Mark D., Liu, Zhen, Ranganathan, Anand, Riabov, Anton V.
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): Luu, Cuong V
• Application Number:
  US11/695,349
• Publication Number:
  US 20110004863A1
• Time in Patent Office: 2,136 Days
• Field of Search: None
• US Class Current: 717/126
• CPC Class Codes: G08G 1/04 using optical or ultrasonic detectors
• CPC Class Codes: G08G 1/09 Arrangements for giving variable traffic instructions railroad crossing signals B61L; reflectors E01F, G08B; indicating arrangements for variable information by selection or combination of individual elements G09F9/00

Abstract

A method for assembling processing graphs in an information processing system, includes: performing, in an offline manner, translating a plurality of component descriptions into a planning language and performing reasoning on the plurality of component descriptions during the translation; and performing, in an online manner, receiving a processing request that specifies a desired processing outcome; translating the processing request into a planning goal; and assembling a plurality of processing graphs, each of the processing graphs including a plurality of the translated and reasoned components that satisfy the desired processing outcome.

Claims

1. A method for assembling processing graphs in an information processing system, comprising:

performing, in an offline manner, translating a plurality of component descriptions into a planning language and performing reasoning on the plurality of component descriptions during the translation; and

performing, in an online manner, receiving a processing request that specifies a desired processing outcome;

translating the processing request into a planning goal; and

assembling a plurality of processing graphs, each of the processing graphs including a plurality of the translated and reasoned components that satisfy the desired processing outcome,

wherein each of the plurality of component descriptions includes;

an applicability condition that includes variables representing objects that must be included in a pre-inclusion state, wherein the pre-inclusion state is a state against which the applicability of the component for inclusion in a processing graph is evaluated; and

an inclusion effect that includes variables representing objects that must be included in a post-inclusion state, wherein the post-inclusion state is a state resulting from inclusion of the component in the processing graph,

wherein every one of the variables in the inclusion effect must be included in the applicability condition,

wherein each component creates at least one new object graph for each output.

2. The method of claim 1, wherein each of the plurality of component descriptions includes:

a graph pattern that semantically describes the objects that must be included in the pre-inclusion state; and

a graph pattern that semantically describes the objects that must be in the post-inclusion state.

3. The method of claim 2, wherein assembling each of the plurality of processing graphs comprises:

matching a post-inclusion state obtained after adding a first component to a processing graph to an applicability condition of a second component if the post-inclusion state obtained after adding the first component to the processing graph includes the objects that must be included in a pre-inclusion state applicable to the second component, and if the graph that semantically describes the objects in the post-inclusion state of the first component satisfies the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component.

4. The method of claim 3, wherein the post-inclusion state obtained after adding the first component to the processing graph is matched to the applicability condition of the second component by applying a pattern solution defined on all the variables in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component.

5. The method of claim 4, wherein when applying the pattern solution, variables that are substituted in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component become a subset of the data objects in the post-inclusion state obtained after adding the first component to the processing graph.

6. The method of claim 5, wherein a graph that is obtained after substituting the variables in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component is satisfied by the graph that semantically describes the objects in the post-inclusion state obtained after adding the first component to the processing graph based on a logical derivation framework.

7. The method of claim 3, further comprising:

connecting the first component to the second component when the post-inclusion state obtained after adding the first component to the processing graph and the applicability condition of the second component are matched to each other.

8. The method of claim 7, further comprising:

generating a new post-inclusion state by applying differences between the inclusion effect of the second component and the applicability condition of the second component to the pre-inclusion state matched to the applicability condition of the second component based on a graph transformation operation.

9. The method of claim 8, further comprising:

adding and removing subgraphs from the pre-inclusion state matched to the applicability condition of the second component based on differences between the applicability condition of the second component and the inclusion effect of the second component.

10. The method of claim 1, wherein when a first processing graph of the plurality of processing graphs includes first and second components that satisfy the desired processing outcome and a second processing graph of the plurality of processing graphs includes the first component and a third component that satisfies the desired processing outcome, the method further comprises:

selecting which of the first or second processing graphs is to be deployed in an information processing system.

11. The method of claim 10, wherein the processing graph to be deployed is selected based on Pareto optimality of the processing graph.

12. The method of claim 1, wherein when a first processing graph of the plurality of processing graphs includes first and second components that satisfy the desired processing outcome and a second processing graph of the plurality of processing graphs includes third and fourth components that satisfy the desired processing outcome, the method further comprises:

selecting which of the first or second processing graphs is to be deployed in an information processing system.

13. The method of claim 12, wherein the processing graph to be deployed is selected based on Pareto optimality of the processing graph.

14. The method of claim 1, wherein the reasoning is Description Logic (DL) reasoning.

15. A system for assembling processing graphs in an information processing system, comprising:

a memory device for storing a program;

a processor in communication with the memory device, the processor operative with the program to;

perform, in an offline manner, translating a plurality of component descriptions into a planning language and performing reasoning on the plurality of component descriptions during the translation; and

perform, in an online manner, receiving a processing request that specifies a desired processing outcome;

translating the processing request into a planning goal; and

assembling a plurality of processing graphs, each of the processing graphs including a plurality of the translated and reasoned components that satisfy the desired processing outcome,

wherein each of the plurality of component descriptions includes;

an applicability condition that includes variables representing objects that must be included in a pre-inclusion state, wherein the pre-inclusion state is a state against which the applicability of the component for inclusion in a processing graph is evaluated; and

an inclusion effect that includes variables representing objects that must be included in a post-inclusion state, wherein the post-inclusion state is a state resulting from inclusion of the component in the processing graph,

wherein every one of the variables in the inclusion effect must be included in the applicability condition,

wherein each component creates at least one new object graph for each output.

16. The system of claim 15, wherein each of the plurality of component descriptions includes:

a graph pattern that semantically describes the objects that must be included in the pre-inclusion state; and

a graph pattern that semantically describes the objects that must be in the post-inclusion state.

17. The system of claim 16, wherein when assembling each of the plurality of processing graphs the processor is further operative with the program to:

match a post-inclusion state obtained after adding a first component to a processing graph to an applicability condition of a second component if the post-inclusion state obtained after adding the first component to the processing graph includes the objects that must be included in a pre-inclusion state applicable to the second component, and if the graph that semantically describes the objects in the post-inclusion state of the first component satisfies the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component.

18. The system of claim 17, wherein the post-inclusion state obtained after adding the first component to the processing graph is matched to the applicability condition of the second component by applying a pattern solution defined on all the variables in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component.

19. The system of claim 18, wherein when applying the pattern solution, variables that are substituted in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component become a subset of the data objects in the post-inclusion state obtained after adding the first component to the processing graph.

20. The system of claim 18, wherein a graph that is obtained after substituting the variables in the graph pattern that semantically describes the objects that must be included in the pre-inclusion state applicable to the second component is satisfied by the graph that semantically describes the objects in the post-inclusion state obtained after adding the first component to the processing graph based on a logical derivation framework.

21. The system of claim 17, wherein the processor is further operative with the program to:

connect the first component to the second component when the post-inclusion state obtained after adding the first component to the processing graph and the applicability condition of the second component are matched to each other.

22. The system of claim 21, wherein the processor is further operative with the program to:

generate a new post-inclusion state by applying differences between the inclusion effect of the second component and the applicability condition of the second component to the pre-inclusion state matched to the applicability condition of the second component based on a graph transformation operation.

23. The system of claim 22, wherein the processor is further operative with the program to:

add and remove subgraphs from the pre-inclusion state matched to the applicability condition of the second component based on differences between the applicability condition of the second component and the inclusion effect of the second component.

24. The system of claim 15, wherein when a first processing graph of the plurality of processing graphs includes first and second components that satisfy the desired processing outcome and a second processing graph of the plurality of processing graphs includes the first component and a third component that satisfies the desired processing outcome, the processor is further operative with the program to:

select which of the first or second processing graphs is to be deployed in an information processing system.

25. The system of claim 24, wherein the processing graph to be deployed is selected based on Pareto optimality of the processing graph.

26. The system of claim 15, wherein when a first processing graph of the plurality of processing graphs includes first and second components that satisfy the desired processing outcome and a second processing graph of the plurality of processing graphs includes third and fourth components that satisfy the desired processing outcome, the processor is further operative with the program to:

select which of the first or second processing graphs is to be deployed in an information processing system.

27. The system of claim 26, wherein the processing graph to be deployed is selected based on Pareto optimality of the processing graph.

28. The system of claim 15, wherein the reasoning is Description Logic (DL) reasoning.

29. A computer program product comprising a non-transitory computer useable medium having computer program logic recorded thereon for assembling processing graphs in an information processing system, the computer program logic comprising:

program code for performing, in an offline manner, translating a plurality of component descriptions into a planning language and performing reasoning on the plurality of component descriptions during the translation; and

program code for performing, in an online manner, receiving a processing request that specifies a desired processing outcome;

translating the processing request into a planning goal; and

assembling a plurality of processing graphs, each of the processing graphs including a plurality of the translated and reasoned components that satisfy the desired processing outcome,

wherein each of the plurality of component descriptions includes;

an applicability condition that includes variables representing objects that must be included in a pre-inclusion state, wherein the pre-inclusion state is a state against which the applicability of the component for inclusion in a processing graph is evaluated; and

an inclusion effect that includes variables representing objects that must be included in a post-inclusion state, wherein the post-inclusion state is a state resulting from inclusion of the component in the processing graph,

wherein every one of the variables in the inclusion effect must be included in the applicability condition,

wherein each component creates at least one new object graph for each output.