Method and apparatus for evaluating expressions including time-scoped operands

• US 6,466,930 B1
• Filed: 06/02/1999
• Issued: 10/15/2002
• Est. Priority Date: 07/28/1998
• Status: Expired due to Term

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: International Computers Limited (Fujitsu Limited)
• Inventors: Gardner, Paul Anton Richardson
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US09/324,214
• Time in Patent Office: 1,231 Days
• Field of Search: 706/45-47, 707/2-5, 707/7, 707/201--, 707/510, 709/100-103, 709/228-234, 709/223, 712/25, 712/48-219, 712/210-220, 345/440-443, 345/117-118, 717/131, 717/114-116, 717/152, 717/139
• US Class Current: 1/1
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A data processing method evaluates expressions, including temporally-scoped operands, to produce temporally-scoped results. Each of the temporally-scoped operands and results includes a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span in which the data item is valid. An expression involving a binary operator is evaluated by scanning each of the operands of the binary operator and generating a value instance in the result, in respect of each time span in which each operand has a constant value.

Claims

1. A data processing method comprising:

(a) providing a plurality of expressions, each expression including a number of temporally-scoped operands; and

(b) evaluating the expressions to produce temporally-scoped results;

(c) wherein each of the temporally-scoped operands and results comprises a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span in which the data item is valid.

2. A method according to claim 1, wherein an expression involving a binary operator is evaluated by scanning each of the operands of the binary operator and generating a value instance in the result, in respect of each time span in which each operand has a constant value.

3. A method according to claim 1 wherein the value instances within an operand or result are time-ordered such that the most recent value instances come first.

4. A method according to claim 1 wherein the step of evaluating the expressions includes converting each expression into a data flow graph, including a root node representing the result of the evaluation, leaf nodes representing the operands, and intermediate nodes representing operators, and wherein evaluation of an expression is initiated by the root node propagating a Require message through the data flow graph towards the leaf nodes, the Require message including a parameter indicating a time span for which an operand is required.

5. A method according to claim 4 wherein, when a leaf node receives a Require message, the leaf node acquires the operand as indicated by the Require message, and then propagates a Data message through the data flow graph towards the root node, the Data message including the operand value.

6. A method according to claim 5 wherein, when the intermediate nodes receive Data messages, they perform predetermined operations on the operands in the Data messages, and then propagate result Data messages through the data flow graph towards the root node, the result Data messages containing the results of the operations.

7. A method according to claim 6 wherein, if one of said intermediate nodes determines that an operand is no longer required for a particular time span, that intermediate node propagates a Cancel message towards the leaf nodes, the Cancel message including a parameter indicating the time span for which the operand is not required.

8. Data processing apparatus comprising:

(a) means for storing a plurality of expressions, each expression including a number of temporally-scoped operands;

(b) an evaluation mechanism for evaluating said expressions to produce temporally scoped results; and

(c) means for storing said temporally-scoped results;

(d) each of the temporally-scoped operands and results comprising a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span in which the data item is valid.

9. Data processing apparatus according to claim 8 wherein the evaluation mechanism comprises:

(a) means for scanning each of the operands of an expression to identify time periods in which the operands of said expression overlap each other; and

(c) means for evaluating said expression in respect of each of said time periods.

10. Data processing apparatus according to claim 8 wherein the value instances within an operand or result are time-ordered such that the most recent value instances come first.

11. Data processing apparatus according to claim 8 wherein the evaluation mechanism comprises means for converting an expression into a data flow graph, including a root node representing the result of the evaluation, leaf nodes representing the operands, and intermediate nodes representing operators, and wherein the root node comprises means for propagating Require messages through the data flow graph towards the leaf nodes, the Require messages including parameters indicating time spans for which operands are required.

12. Data processing apparatus according to claim 11 wherein the leaf nodes comprise means for acquiring operands in response to the Require messages, and means for propagating Data messages through the data flow graph towards the root node, the Data messages including operand values acquired by the leaf nodes.

13. Data processing apparatus according to claim 12 wherein the intermediate nodes comprise means for performing predetermined operations on the operands in the Data messages, and means for propagating result Data messages through the data flow graph towards the root node, the result Data messages containing the results of the operations.

14. Data processing apparatus according to claim 13 wherein said intermediate nodes include means for propagating Cancel messages through the data flow graph towards the leaf nodes, a Cancel message including a parameter indicating the time span for which an operand is not required.

15. A data carrier incorporating a computer program for performing a method comprising:

providing a plurality of expressions, each expression including a number of temporally-scoped operands; and

evaluating the expressions to produce temporally-scoped results;

wherein each of the temporally-scoped operands and results comprises a sequence of one or more value instances, each value instance including a data item, a start time, and an end time, the start time and end time defining a time span in which the data item is valid.

16. A data processing method comprising:

(a) defining at least one expression, including a plurality of operands and an operator specifying an operation between said operands, each of said operands comprising a sequence of data values, and each of said data values having an associated time span;

(b) identifying a plurality of overlap periods, in which the time spans of said data values of said operands overlap each other; and

(c) for each of said overlap periods, performing said-operation between said operands, to produce a sequence of result data values, each of said result data values having an associated time span equal to one of said overlap periods.

17. Data processing apparatus comprising:

(a) means for storing at least one expression, including a plurality of operands and an operator specifying an operation between said operands, each of said operands comprising a sequence of data values, and each of said data values having an associated time span;

(b) means for identifying a plurality of overlap periods, in which the time spans of said data values of said operands overlap each other; and

(c) means for performing, for each of said overlap periods, said operation between said operands, to produce a sequence of result data values, each of said result data values having an associated time span equal to one of said overlap periods.