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

• US 7,834,875 B2
• Filed: 04/02/2007
• Issued: 11/16/2010
• Est. Priority Date: 04/02/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Riabov, Anton V., Liu, Zhen, Ranganathan, Anand
• Primary Examiner(s): Amini; Javid A
• Application Number:
  US11/695,487
• Publication Number:
  US 20080238923A1
• Time in Patent Office: 1,324 Days
• Field of Search: 345/440
• US Class Current: 345/440
• CPC Class Codes: G06F 8/00 Arrangements for software engineering testing or debugging G06F11/36; administrative, planning or organisation aspects of software project management G06Q10/06
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A method for assembling stream processing graphs in a stream processing system, includes: performing, in an offline manner, translating a plurality of processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome.

Claims

1. A method for assembling stream processing graphs in a stream processing system, comprising:

performing, in an offline manner, translating a plurality of processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome,

wherein a first processing element description includes;

an input message pattern that includes variables representing data objects that must be included in a message input to the first processing element, and a graph pattern that semantically describes the data objects that must be included in the message input to the first processing element.

2. The method of claim 1, wherein of the first processing element description includes:

an output message pattern that includes variables and new data objects, the variables and new data objects representing data objects that must be included in a message output from the first processing element, and a graph pattern that semantically describes the data objects in the message output from the first processing element.

3. The method of claim 2, wherein a first data source description includes:

an output message description that includes exemplar terms representing data objects that must be included in a message output from the first data source, and a graph that semantically describes the data objects in the message output from the first data source.

4. The method of claim 3, wherein assembling each of the stream processing graphs comprises:

matching a message output from the first processing element or the first data source to an input message pattern of a second processing element if the message includes the data objects that must be included in a message input to the second processing element and if a graph that semantically describes data objects in the message satisfies the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

5. The method of claim 4, wherein the message is matched to the input message pattern of the second processing element by applying a pattern solution defined on all the variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

6. The method of claim 5, wherein when applying the pattern solution, variables that are substituted in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element become a subset of the data objects in the output message pattern of the second processing element after matching the message to the second processing element.

7. The method of claim 6, wherein a graph that is obtained after substituting the variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element is satisfied by the graph that semantically describes the data objects in the output message pattern of the second processing element after matching the message to the second processing element based on a logical derivation framework.

8. The method of claim 7, further comprising:

substituting variables representing configuration parameters of the second processing element by terms that satisfy constraints on the variables in variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

9. The method of claim 4, further comprising:

connecting the first processing element or the first data source to the second processing element when the message is matched to the input message pattern of the second processing element.

10. The method of claim 9, further comprising:

generating an output message of the second processing element by applying differences between the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element and the graph pattern that semantically describes the data objects that must be in an output message pattern of the second processing element to the graph that semantically describes the data objects in the message.

11. The method of claim 10, further comprising:

adding and removing subgraphs from the message matched to the input message pattern of the second processing elements based on differences between the input message pattern of the second processing element and the output message pattern of the second processing element.

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

13. A method for assembling stream processing graphs in a stream processing system, comprising:

performing, in an offline manner, translating a plurality of processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome

wherein when a first stream processing graph of the plurality of stream processing graphs includes a first data source and a first processing element that satisfy the desired processing outcome and a second stream processing graph of the plurality of stream processing graphs includes the first data source and a second processing element that satisfies the desired processing outcome, the method further comprises;

selecting which of the first or second processing graphs is to be deployed in a stream processing system,

wherein the stream processing graph to be deployed is selected based on Pareto optimality of the stream processing graph.

14. A method for assembling stream processing graphs in a stream processing system, comprising:

performing, in an offline manner, translating a plurality of processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome

wherein when a first stream processing graph of the plurality of stream processing graphs includes a first data source and a first processing element that satisfy the desired processing outcome and a second stream processing graph of the plurality of stream processing graphs includes a second data source and the first processing element that satisfy the desired processing outcome, the method farther comprises;

selecting which of the first or second stream processing graphs is to be deployed in a stream processing system,

wherein the stream processing graph to be deployed is selected based on Pareto optimality of the stream processing graph.

15. A system for assembling stream processing graphs in a stream 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 processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome,

wherein a first processing element description includes;

an input message pattern that includes variables representing data objects that must be included in a message input to the first processing element, and a graph pattern that semantically describes the data objects that must be included in the message input to the first processing element.

16. The system of claim 15, wherein the first processing element description includes:

an output message pattern that includes variables and new data objects, the variables and new data objects representing data objects that must be included in a message output from the first processing element, and a graph pattern that semantically describes the data objects in the message output from the first processing element.

17. The system of claim 16, wherein a first data source descriptions includes:

an output message description that includes exemplar terms representing data objects that must be included in a message output from the first data source, and a graph that semantically describes the data objects in the message output from the first data source.

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

match a message output from the first processing element or the first data source to an input message pattern of a second processing element if the message includes the data objects that must be included in a message input to the second processing element and if a graph that semantically describes data objects in the message satisfies the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

19. The system of claim 18, wherein the message is matched to the input message pattern of the second processing element by applying a pattern solution defined on all the variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

20. The system of claim 19, wherein when applying the pattern solution, variables that are substituted in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element become a subset of the data objects in the output message pattern of the second processing element after matching the message to the second processing element.

21. The system of claim 20, wherein a graph that is obtained after substituting the variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element is satisfied by the graph that semantically describes the data objects in the output message pattern of the second processing element after matching the message to the second processing element based on a logical derivation framework.

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

substitute variables representing configuration parameters of the second processing element by terms that satisfy constraints on the variables in variables in the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element.

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

connect the first processing element or the first data source to the second processing element when the message is matched to the input message pattern of the second processing element.

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

generate an output message of the second processing element by applying differences between the graph pattern that semantically describes the data objects that must be included in the message input to the second processing element and the graph pattern that semantically describes the data objects that must be in an output message pattern of the second processing element to the graph that semantically describes the data objects in the message.

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

add and remove subgraphs from the message matched to the input message pattern of the second processing elements based on differences between the input message pattern of the second processing element and the output message pattern of the second processing element.

26. The system of claim 15, wherein when a first stream processing graph of the plurality of stream processing graphs includes a first data source and the first processing element that satisfy the desired processing outcome and a second stream processing graph of the plurality of stream processing graphs includes the first data source and a second processing element 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 a stream processing system.

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

28. The system of claim 15, wherein when a first stream processing graph of the plurality of stream processing graphs includes a first data source and the first processing element that satisfy the desired processing outcome and a second stream processing graph of the plurality of stream processing graphs includes a second data source and the first processing element that satisfy the desired processing outcome, the processor is further operative with the program to:

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

29. The system of claim 28, wherein the stream processing graph to be deployed is selected based on Pareto optimality of the stream processing graph.

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

31. A computer program product comprising a computer useable medium having computer program logic recorded thereon for assembling stream processing graphs in a stream processing system, the computer program logic comprising:

program code for performing, in an offline manner, translating a plurality of processing element and data source descriptions into a planning language and performing reasoning on the plurality of processing element and data source 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 stream processing graphs, each of the processing graphs including a plurality of the translated and reasoned processing elements or data sources that satisfy the desired processing outcome,

wherein a first processing element description includes;

an output message pattern that includes variables and new data objects, the variables and new data objects representing data objects that must be included in a message output from the first processing element, and a graph pattern that semantically describes the data objects in the message output from the first processing element.