Patent Publication Number: US-8543558-B2

Title: Support for user defined functions in a data stream management system

Description:
CROSS-REFERENCE TO PARENT APPLICATION 
     This application is a continuation application of and claims the benefit of and priority to U.S. patent application Ser. No. 11/874,896, filed on Oct. 18, 2007, by Anand Srinivasan, Namit Jain and Shailendra Kumar Mishra as the inventors, entitled “SUPPORT FOR USER DEFINED FUNCTIONS IN A DATA STREAM MANAGEMENT SYSTEM” which is incorporated by reference herein in its entirety. 
    
    
     BACKGROUND 
     It is well known in the art to process queries over continuous streams of data using one or more computer(s) that may be called a data stream management system (DSMS). Such a system may also be called an event processing system (EPS) or a continuous query (CQ) system, although in the following description of the current patent application, the term “data stream management system” or its abbreviation “DSMS” is used. DSMS systems typically receive from a user a textual representation of a query (called “continuous query”) that is to be applied to a stream of data. Data in the stream changes over time, in contrast to static data that is typically found stored in a database. Examples of data streams are: real time stock quotes, real time traffic monitoring on highways, and real time packet monitoring on a computer network such as the Internet. 
       FIG. 1A  illustrates a prior art DSMS built at the Stanford University, in which data streams from network monitoring can be processed, to detect intrusions and generate online performance metrics, in response to queries (called “continuous queries”) on the data streams. Note that in such data stream management systems (DSMS), each stream can be infinitely long and the data can keep arriving indefinitely and hence the amount of data is too large to be persisted by a database management system (DBMS) into a database. 
     As shown in  FIG. 1B  a prior art DSMS may include a continuous query compiler that receives a continuous query and builds a physical plan which consists of a tree of natively supported operators. Any number of such physical plans (one plan per query) may be combined together, before DSMS starts normal operation, into a global plan that is to be executed. When the DSMS starts execution, the global plan is used by a query execution engine (also called “runtime engine”) to identify data from one or more incoming stream(s) that matches a query and based on such identified data the engine generates output data, in a streaming fashion. 
     As noted above, one such system was built at Stanford University, in a project called the Stanford Stream Data Management (STREAM) Project which is documented at the URL obtained by replacing the ? character with “/” and the % character with “.” in the following: http:??www-db%stanford%edu?stream. For an overview description of such a system, see the article entitled “STREAM: The Stanford Data Stream Management System” by Arvind Arasu, Brian Babcock, Shivnath Babu, John Cieslewicz, Mayur Datar, Keith Ito, Rajeev Motwani, Utkarsh Srivastava, and Jennifer Widom which is to appear in a book on data stream management edited by Garofalakis, Gehrke, and Rastogi. The just-described article is available at the URL obtained by making the above described changes to the following string: http:??dbpubs%stanford%edu?pub?2004-20. This article is incorporated by reference herein in its entirety as background. 
     For more information on other such systems, see the following articles each of which is incorporated by reference herein in its entirety as background:
     [a] S. Chandrasekaran, O. Cooper, A. Deshpande, M. J. Franklin, J. M. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Ramna, F. Reiss, M. Shah, “TelegraphCQ: Continuous Dataflow Processing for an Uncertain World”, Proceedings of CIDR 2003;   [b] J. Chen, D. Dewitt, F. Tian, Y. Wang, “NiagaraCQ: A Scalable Continuous Query System for Internet Databases”, PROCEEDINGS OF 2000 ACM SIGMOD, p 379-390; and   [c] D. B. Terry, D. Goldberg, D. Nichols, B. Oki, “Continuous queries over append-only databases”, PROCEEDINGS OF 1992 ACM SIGMOD, pages 321-330.   

     Continuous queries (also called “persistent” queries) are typically registered in a data stream management system (DSMS) prior to its operation on data streams. The continuous queries are typically expressed in a declarative language that can be parsed by the DSMS. One such language called “continuous query language” or CQL has been developed at Stanford University primarily based on the database query language SQL, by adding support for real-time features, e.g. adding data stream S as a new data type based on a series of (possibly infinite) time-stamped tuples. Each tuple s belongs to a common schema for entire data stream S and the time t is a non-decreasing sequence. Note that such a data stream can contain 0, 1 or more pairs each having the same (i.e. common) time stamp. 
     Stanford&#39;s CQL supports windows on streams (derived from SQL-99) based on another new data type called “relation”, defined as follows. A relation R is an unordered group of tuples at any time instant t which is denoted as R(t). The CQL relation differs from a relation of a standard relational database accessed using SQL, because traditional SQL&#39;s relation is simply a set (or bag) of tuples with no notion of time, whereas the CQL relation (or simply “relation”) is a time-varying group of tuples (e.g. the current number of vehicles in a given stretch of a particular highway). All stream-to-relation operators in Stanford&#39;s CQL are based on the concept of a sliding window over a stream: a window that at any point of time contains a historical snapshot of a finite portion of the stream. Syntactically, sliding window operators are specified in CQL using a window specification language, based on SQL-99. 
     For more information on Stanford University&#39;s CQL, see a paper by A. Arasu, S. Babu, and J. Widom entitled “The CQL Continuous Query Language: Semantic Foundation and Query Execution”, published as Technical Report 2003-67 by Stanford University, 2003 (also published in VLDB Journal, Volume 15, Issue 2, June 2006, at Pages 121-142). See also, another paper by A. Arasu, S. Babu, J. Widom, entitled “An Abstract Semantics and Concrete Language for Continuous Queries over Streams and Relations” in 9th Intl Workshop on Database programming languages, pages 1-11, September 2003. The two papers described in this paragraph are incorporated by reference herein in their entirety as background. 
     An example to illustrate continuous queries is shown in  FIGS. 1C-1E  which are reproduced from the VLDB Journal paper described in the previous paragraph. Specifically,  FIG. 1E  illustrates a merged STREAM query plan for two continuous queries, Q 1  and Q 2  over input streams S 1  and S 2 . Query Q 1  of  FIG. 1E  is shown in detail in  FIG. 1C  expressed in CQL as a windowed-aggregate query: it maintains the maximum value of S 1 :A for each distinct value of S 1 :B over a 50,000-tuple sliding window on stream S 1 . Query Q 2  shown in  FIG. 1D  is expressed in CQL and used to stream the result of a sliding-window join over streams S 1  and S 2 . The window on S 1  is a tuple-based window containing the last 40,000 tuples, while the window on S 2  is a 10-minutes time-based window. 
     Several DSMS of prior art, such as Stanford University&#39;s DSMS treat queries as fixed entities and treat event data as an unbounded collection of data elements. This approach has delivered results as they are computed in near real time. However, once queries have registered and such a prior art DSMS begins to process event data, the query plan cannot be changed, in prior art systems known to the current inventors. In one prior art DSMS, even after it begins normal operation by executing a continuous query Q 1 , it is possible for a human (e.g. network operator) to register an “ad-hoc continuous query” Q 2 , for example to check on congestion in a network, as described in an article by Shivnath Babu and Jennifer Widom entitled “Continuous Queries over Data Streams” published as SIGMOD Record, September 2001. The just-described paper is incorporated by reference herein in its entirety as background. Such a query Q 2  may be written to find a fraction of traffic on a backbone link that is coming from a customer network. 
     Unlike research DSMS of the type described above, a DSMS for use in processing real world time-varying data streams is limited if it only allows queries to use built-in (i.e. native) functions, such as square-root function SQRT. There appears to be a long felt and unsolved need for support of functions that may be defined by the user depending on the application. 
     SUMMARY 
     A computer is programmed in accordance with the invention to implement a data stream management system (DSMS) to accept a command for creation of a new function defined by a user during normal operation of the DSMS, and thereafter accept and process new continuous queries using the new function with data from each tuple in a manner similar to built-in functions. The user typically starts with a pre-existing set of instructions to perform the new function (e.g. from a vendor-supplied library of statistical functions), and identifies in the command, a function name and a path for the location of the set of instructions. In response to such a command, the computer creates an instance of the set of instructions to execute the new function, and also creates a structure in a metadata repository to hold a mapping between the function&#39;s name (directly or indirectly via a system-generated identifier for the function) to the newly-created instance. 
     The structure in metadata repository (also called metadata entry) is used in certain embodiments, to process every new continuous query that uses the new function. Specifically, on receipt of a new continuous query that uses the new function, the computer creates an operator tree to execute the new continuous query, which operator tree includes an operator to automatically invoke the new function using a generic opcode in the DSMS which is designed to invoke any user defined function. This newly-created operator includes a second structure (also called “operator specific data structure”) in which the computer automatically stores a path to the newly-created instance (looked up from the metadata entry by use of the function name). Alternative embodiments do not perform the look up at this stage (query compilation), and instead store in the second structure the function name and perform the look up during query execution. 
     Thereafter, in the certain embodiments, additional second structures are created on receipt of additional continuous queries which use the new function, but all second structures are initialized to hold the same path, which is automatically looked up from the metadata entry for that function. Accordingly, in the certain embodiments all queries use the same instance when invoking the new function. Repeated use of a single instance (identified from the metadata entry) to execute multiple queries eliminates repeated instantiation of the same function and related usage of additional memory. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIGS. 1A and 1B  illustrate, in a high level diagram and an intermediate level diagram respectively, a data stream management system of the prior art. 
         FIGS. 1C and 1D  illustrate two queries expressed in a continuous query language (CQL) of the prior art. 
         FIG. 1E  illustrates a query plan of the prior art for the two continuous queries of  FIGS. 1C and 1D . 
         FIG. 2A  illustrates, in an intermediate level diagram, a data stream management system (DSMS) that has been extended in accordance with the invention to support user defined functions (UDFs). 
         FIG. 2B  illustrates a command to define a UDF that is accepted by the extended DSMS of  FIG. 2A . 
         FIGS. 2C and 2D  illustrate, in a high level block diagram and an intermediate level block diagram respectively, a tree of operators including an operator that uses a user-defined function “foo” to execute a continuous query Q 1 , in accordance with the invention. 
         FIGS. 2E and 2F  illustrate, in a high level block diagram and an intermediate level block diagram respectively, a tree of operators including two operators that use the user-defined functions “foo” and “bar” to execute another continuous query Q 2 , in accordance with the invention. 
         FIG. 3A  illustrates, in flow charts, methods that are executed by the extended DSMS of  FIG. 2A , in some embodiments of the invention to obtain (and use) a modified plan by addition of new continuous queries that use UDFs. 
         FIG. 3B  illustrates, in a block diagram, a metadata structure created by the method of  FIG. 2A  to map a function name to an instance of a set of instructions for the function. 
         FIG. 4  illustrates, in a block diagram, an opcode-specific structure created by some embodiments of the method of  FIG. 3A  for use in executing the continuous query based on a user defined function. 
         FIG. 5  illustrates, in another flow chart, a method performed by the extended DSMS of  FIG. 2A , in some embodiments of the invention, to execute the continuous query compiled as per the method of  FIG. 3A . 
         FIG. 6  illustrates, in a high level block diagram, hardware included in a computer that may be used to perform the methods of  FIGS. 3A and 5  in some embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     Many embodiments of the invention use a DSMS whose continuous query language (CQL) natively supports certain standard SQL keywords, such as a SELECT command having a FROM clause and in addition also supports windowing functions required for stream and/or relation operations. Note that even though several keywords and/or syntax may be used identically in both SQL and CQL, the semantics are different for these two languages because SQL may be used to define queries on stored data in a database whereas CQL is used to define queries on transient data in a data stream. 
     A computer which implements a DSMS in accordance with the invention is programmed with certain software in several embodiments called a function definition module and a continuous query compiler, as discussed below in reference to  FIG. 2A . Any aspects of the computer which are not described below are similar or identical to a computer described in the published literature about the Standford Stream Data Management (STREAM) Project, as discussed in the Background section above. 
     A function definition module is implemented in accordance with the invention to receive and dynamically act on a command to create a new function which is to be recognized in new continuous queries that are received thereafter, and executed in a manner similar or identical to built-in functions for data streams such as SQRT. For example, the user may define ROUNDUP as their user defined function to round up a real number and return an integer, assuming this is not a built-in function of the DSMS. 
     Of note, the function definition module is designed to accept such creation command(s) on the fly, i.e. during normal operation of the DSMS on existing queries. Moreover, a continuous query compiler is implemented in accordance with the invention to receive and act on a new continuous query q that uses a user defined function f, also on the fly during normal operation of the DSMS on existing queries. Accordingly, such a DSMS in accordance with the invention is hereinafter referred to as an extended DSMS. 
     Extended DSMS  200  ( FIG. 2A ) includes a compiler or interpreter for a predetermined non-database language, also called procedural language, in which the user writes a set of instructions to be performed by extended DSMS  200  in response to a user defined function f. Specifically, a user writes a set of instructions  201  for function f in the predetermined language, such as Java and having a predetermined name, such as “execute”. An example of a public interface supported by extended DSMS  200  of some embodiments is illustrated in Subsection A below. 
     The user stores the set of instructions  201  in store  280  within extended DSMS  200  (via line  242 ) during normal operation of DSMS  200 , i.e. while a number of queries (also called existing queries) are being currently processed. Additionally the user also issues a command  202  to extended DSMS  200  (via line  242 ), to create user defined function f. In response to command  202 , extended DSMS  200  dynamically stores command  202  (while continuing to process queries in the normal manner), for use in validating new queries. 
     An illustration of command  202  is shown in  FIG. 2B . Command  202  is typically typed by a user as a string of characters which starts with one or more reserved word(s)  261  ( FIG. 2B ) such as CREATE FUNCTION. Alternative embodiments may use other words or use more than two words. In many embodiments, the syntax for the CREATE FUNCTION statement in CQL as described herein conforms to the syntax of SQL (as used in prior art DBMS, such as Oracle 10gR1). 
     The command  202  also has a number of arguments which follow keyword(s)  261 , such as function name  262  and argument list  263 . Function name  262  is illustrated in  FIG. 2B  to have the value “foo.” This value is chosen by the user as the function name to be used in continuous queries, to invoke the set of instructions  201 . Argument list  263  is a listing of the function&#39;s arguments surrounded by brackets. Argument list  263  is illustrated in  FIG. 2B  to consist of two arguments, namely varchar2 and integer, which are data types of inputs to the set of instructions  201 . 
     Depending on the embodiment, the command  202  may have one or more clauses, introduced by reserved words which may be optionally followed by arguments. Command  202  has two reserved words  264  and  266  each of which is followed by a single argument  265  and  267  respectively. The value of reserved word  264  is shown in  FIG. 2B  as RETURN and its argument  265  identifies the data type of the value to be returned by function “foo”. The value of reserved word  266  is shown in  FIG. 2B  as NAME and its argument  267  identifies a user-written Java class named “foo” that is implemented in the package “myPackage”. The Java class contains a method “execute” to be used as the set of instructions  201  as illustrated below in Subsection A. 
     Also, as will be apparent to the skilled artisan, other embodiments may have other clauses, reserved words, arguments and values thereof. Moreover, the order of various portions of command  202 , relative to one another, can be different depending on the embodiment. However, note that in order for extended DSMS  200  to find a Java class when instantiating function foo, the user must place the package “myPackage” in an appropriate location in the file system that is reachable via a path normally used by extended DSMS  200  to load and execute Java classes. Accordingly, if a path is appropriately set up and known to the user, extended DSMS  200  can receive the user&#39;s software (set of instructions  201 ) via such a path at any time relative to normal operations (i.e. the extended DSMS can be up and running and processing existing continuous queries). 
     Note that in embodiments that repeatedly use the same instance of a function foo, the user must write their software (for function foo) in a manner that permits the same software instance to be used repeatedly for different evaluation contexts (different data in a tuple). Hence, as noted elsewhere, in such embodiments the user cannot use instance-specific variables, when writing their software to perform the function “foo.” Two examples of queries that use user-defined functions are as follows. In a first example, the user has registered the following query (after defining “foo” as a user-defined function):
         Q 1 : Select * from R where foo(A)&gt;10
 
Accordingly, this query is automatically compiled as shown in  FIG. 2C , and it includes a filter operator  251  (which is one example of a DSMS operator) that uses the function foo. The filter operator is internally implemented by an expression tree shown in  FIG. 2D , wherein a result of the Boolean expression operator “&gt;” is supplied as the output of the filter operator, and it is in turn based on an operator for function “foo” which is automatically invoked to evaluate the expression in filter operator  251 . When Q 1 &#39;s execution is started at time  100 , an output stream (e.g. included in stream  231  of  FIG. 2A ) for values of O 1  at each of several time instants,  100 ,  101 , . . .  500  gets generated (assuming current time is  500 ). The user may also register another query Q 2  that uses two such user-defined functions, “foo” and “bar” as follows:
   Q 2 : Select * from R where bar (foo(A+5, B))&gt;20
 
This query is automatically compiled as shown in  FIG. 2E  and executed as shown in  FIG. 2F .
       

     As shown in  FIG. 3A , a function definition module in extended DSMS  200  receives a command to create a user defined function (UDF) in act  311  and proceeds to act  312 . In act  312 , the command is parsed and validated (e.g. the syntax is validated as per a predetermined grammar, and the data types of the arguments are validated). One embodiment validates the arguments using a Java API. In act  313 , extended DSMS  200  stores one or more pieces of information about function foo (called “metadata”) that were received in command  202 , for later use when a query  203  is received. Function foo&#39;s metadata may include one or more of pieces of information  263 ,  265  and  267  illustrated in  FIG. 2B  and described above. 
     Such metadata on function foo is stored in store  280  in an arrangement similar or identical to storage of the corresponding information for a built-in function. On performance of act  313 , an expression evaluator in DSMS  200  is automatically reconfigured to use the function foo&#39;s metadata to henceforth recognize the user defined function foo as valid, and to invoke the set of instructions  201  for function foo. Extended DSMS  200  performs one or more acts depending on the embodiment, to store metadata of function foo in store  280 . Function foo&#39;s metadata forms a single entry among a number of metadata entries for UDFs in store  280  that are accessible to query compiler  210  in DSMS  200 . Thereafter, a query compiler  210  performs acts  321 - 326  to start execution of the new query as discussed below. 
     An illustration of a user-defined function f&#39;s metadata entry in store  280  in some embodiments is shown in  FIG. 3B . The metadata entry typically includes a name  381  of the function and a reference  382  to the set of instructions for the function. In some embodiments, a function&#39;s metadata entry also holds information useful in type checking a query&#39;s usage of function f during query compilation, such as the number of arguments and the data type of each argument. This is illustrated in  FIG. 3B  by the number  383  of arguments that are input to the function, a list  384  of argument names, a list  385  of data types of these arguments, and a data type  386  of the return value for this function. 
     The embodiment of metadata entry illustrated in  FIG. 3B  can have any number N of argument names  384 A- 384 N, with a corresponding number N of data types, and the number N is stored in field  383  of the metadata entry. As will be apparent to the skilled artisan, other embodiments may maintain the information in such a metadata entry in a different order, or even maintain other information that is useful in compilation of a new continuous query based on user defined function f. Note that alternative embodiments may maintain type checking information in a location other than the metadata entry, e.g. adjacent to the function&#39;s instance in memory. 
     After command  202  is processed and a corresponding metadata entry is stored in store  280 , the user may now issue a new continuous query  203  which uses the user defined function f. In some embodiments, continuous query  203  is expressed in the continuous query language CQL of the type described in the background section above. Query  203  may include a reference to the new user defined function f anywhere therein, e.g. in the select list of the query, or in the wherein clause of the query or both. The function f may be included within any expression. Also, the function f may be invoked with arguments which are themselves expressions of any data from a tuple currently being processed. Moreover such a query may use any number of user defined functions and/or built-in functions and if necessary they may be nested in any manner, relative to one another. 
     Extended DSMS  200  receives continuous query  203  as per act  321  and parses the query ( FIG. 3A ) and thereafter semantically validates the query as per act  322 . Next, a logical plan is created in act  323 , followed by a physical plan in act  324 , followed by an execution plan in act  325 , followed by act  326  which modifies a query execution plan that is currently in use. In act  324  ( FIG. 3A ), a continuous query compiler  210  within DSMS  200  uses the function f&#39;s metadata on encountering the use of function f in a physical operator of the physical plan, to invoke the function. Continuous query compiler  210  ( FIG. 2A ) typically includes logic (such as a parser) to identify use of functions in continuous queries. Specifically, continuous query compiler  210  checks whether or not the function used in the query is a built-in function and if not checks if it has an entry in the metadata repository (indicating it&#39;s a user defined function). If so, continuous query compiler  210  assembles input data for function f as follows. 
     The continuous query compiler  210  uses fields  454 A- 454 N in the opcode-specific data structure ( FIG. 4 ) to identify queues which contain the respective data, and then creates an array of operands for function f. Accordingly, query compiler  210  creates a tree  220  for the new query, including an operator containing a predetermined opcode (such as UDF-INT) to invoke user defined functions with an integer input, and an opcode-specific data structure to hold information specific to function f. Then, query compiler  210  uses the tree to modify the currently executing plan, which concludes act  325 . 
     After act  325 , an act  326  ( FIG. 3A ) is performed wherein query compiler  210  alters the processing of queries, by invoking a scheduler to allocate time slots for all operators including the newly added operator, thereby to cause the new continuous query q to be automatically executed by query execution engine  230 . 
     As shown in  FIG. 3A , at an appropriate time, query execution engine  230  awakens the newly added operator in act  331  and then goes to act  332 . In act  332 , engine  230  checks if a new tuple of data has been received. If not, then engine  230  goes to sleep as per act  336 , to be eventually awakened in the next time slot (as shown by act  337 ). In act  332 , if a new tuple has been received, engine  230  checks if the current operator needs to evaluate an expression as per act  333  and if so goes to act  334  to invoke an expression evaluator to evaluate the user defined function f with user-specified argument(s) from the new tuple. In act  334 , the engine  230  executes the set of instructions  201 , which are identified from information in the opcode-specific data structure. After act  334 , engine  230  goes to act  335  to perform one or more operator-specific functions, such as Join. 
     Note that the opcode-specific data structure is used to transfer data from a tuple that is currently being processed, in the form of input arguments of the user defined function (i.e. set of instructions  201 ). The arguments are normally passed in as an array of objects (such as an array of integers, real numbers etc). Such transfer uses a mapping of data types between (1) data types in a predetermined language in which user&#39;s function f is expressed (e.g. Java), and (2) data types in extended DSMS  200 , as illustrated in Subsection A below. Also, note that query receipt, compilation and execution are performed by some embodiments of extended DSMS  200  ( FIG. 2A ) while processing incoming streams of data  250  by executing thereon one or more continuous queries that were already being executed (“existing queries”) prior to receipt of the new continuous query q. 
     In some embodiments, a reference  382  in metadata entry ( FIG. 3B ) is a copy of information piece  267  which is extracted from command  202 . In such embodiments, compiler  210  repeatedly instantiates the set of instructions  201  based on name argument  267  for each new continuous query that uses function f. However, certain embodiments are optimized to repeatedly use a single instance of function f for multiple queries. In the certain embodiments function definition module  310  instantiates the set of instructions  201  for the user defined function f just once, in act  312 , and stores an identifier of (e.g. a pointer to) the in-memory instance in function f&#39;s metadata, in reference  382 . 
     Note that a developer who prepares the set of instructions  201  cannot assume that the same the instance of the execute method will be invoked each time that a query references this function f. Specifically, depending on the embodiment, successive invocations may or may not be invoked on the same instance. Hence, the user can neither store nor make use of any state information, through instance variables. 
     In several embodiments, the same identifier (e.g. from reference  382 ) is repeatedly used, in compiling multiple queries which use function f. The identifier is obtained in some embodiments by looking up the function&#39;s metadata entry in store  280 , using the function&#39;s name as an index. Such an identifier may be copied into an opcode-specific data structure by compiler  210  and thereafter used by engine  230  in expression evaluator  333 . In such optimized embodiments, the user&#39;s set of instructions must be deterministic, i.e. must generate the same results if the inputs are the same. Therefore, the user cannot use any instance-specific variables in writing the set of instructions  201 . Instead, in some embodiments, the user may use local function variables (e.g. as per Java). The user cannot also use in implementing the function any non-deterministic information, such as the current date or a random number. 
     Some embodiments of extended DSMS  200  use an opcode-specific data structure of the type illustrated in  FIG. 4 . Specifically, such a data structure includes the following fields: a first field  451  holds a pointer to the set of instructions, a second field  452  holds the number of arguments, a third field  453  holds the data type of the value to be returned by the user defined function. The data structure also includes a number of fourth fields  454 A- 454 N, which are equal in number to the value in second field  452 . The above-described opcode-specific data structure is used in some embodiments by an expression evaluator of the type illustrated in  FIG. 5 . Specifically, in act  504 , the expression evaluator invokes the function f, by beginning execution of the in-memory instance of the set of instructions  201 . After the set of instructions  201  have been executed, act  504  completes and the expression evaluator goes to act  505 . In act  505 , the expression evaluator copies a single result which is returned by the set of instructions into a local variable, in order to continue with processing of the expression in the continuous query, in the normal manner. 
     Extending the DSMS to provide support for UDFs has the following advantages: (1) it allows users to integrate with their own or third-party CEP processors; and (2) gives the users a lot of flexility in designing their application. Furthermore, an extended DSMS in accordance with the invention provides support for error-handling for a user-defined function. Specifically, in some embodiments, the user-defined function is enabled to throw any exceptions, and the DSMS is extended to handle them correctly as follows. The error is not simply returned to a user, and instead the extended DSMS automatically logs the error, and all the queries that directly or indirectly depend on that operator are automatically identified and automatically disabled. Even if an error in the user-defined function is fatal, other queries which do not depend on that operator continue to execute. It is the responsibility of a human with administrator privileges in the DSMS to rectify any problems with the user-defined function and start execution of the disabled queries again. 
     Note that the extended data stream management system  200  may be implemented in some embodiments by use of a computer (e.g. an IBM PC) or workstation (e.g. Sun Ultra  20 ) that is programmed with an application server, of the type available from Oracle Corporation of Redwood Shores, Calif. Such a computer can be implemented by use of hardware that forms a computer system  600  as illustrated in  FIG. 6 . Specifically, computer system  600  includes a bus  602  ( FIG. 6 ) or other communication mechanism for communicating information, and a processor  604  coupled with bus  602  for processing information. 
     Computer system  600  also includes a main memory  606 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus  602  for storing information and instructions to be executed by processor  604 . Main memory  606  also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor  604 . Computer system  600  further includes a read only memory (ROM)  608  or other static storage device coupled to bus  602  for storing static information and instructions for processor  604 . A storage device  610 , such as a magnetic disk or optical disk, is provided and coupled to bus  602  for storing information and instructions. 
     Computer system  600  may be coupled via bus  602  to a display  612 , such as a cathode ray tube (CRT), for displaying to a computer user, any information related to DSMS  200  such as a data stream  231  including results from execution of a user-defined function that is being output by computer system  600 . An example of data stream  231  is a continuous display of stock quotes, e.g. in a horizontal stripe at the bottom of display  612 . An input device  614 , including alphanumeric and other keys, is coupled to bus  602  for communicating information and command selections to processor  604 . Another type of user input device is cursor control  616 , such as a mouse, a trackball, or cursor direction keys for communicating direction information and command selections to processor  604  and for controlling cursor movement on display  612 . This input device typically has two degrees of freedom in two axes, a first axis (e.g., x) and a second axis (e.g., y), that allows the device to specify positions in a plane. 
     As described elsewhere herein, incrementing of multi-session counters, shared compilation for multiple sessions, and execution of compiled code from shared memory are performed by computer system  600  in response to processor  604  executing instructions programmed to perform the above-described acts and contained in main memory  606 . Such instructions may be read into main memory  606  from another computer-readable medium, such as storage device  610 . Execution of instructions contained in main memory  606  causes processor  604  to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement an embodiment of the type illustrated in  FIGS. 3A and 5 . Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software. 
     The term “computer-readable storage medium” as used herein refers to any non-transitory medium that participates in providing instructions to processor  604  for execution. Such a non-transitory medium may take many forms, including but not limited to, non-volatile media and volatile media. Non-volatile media includes, for example, optical or magnetic disks, such as storage device  610 . Volatile media includes dynamic memory, such as main memory  606 . 
     Common forms of computer-readable media include, for example, a floppy disk, a flexible disk, hard disk, magnetic tape, or any other magnetic medium, a CD-ROM, any other optical medium, punch cards, paper tape, any other physical medium with patterns of holes, a RAM, a PROM, and EPROM, a FLASH-EPROM, any other memory chip or cartridge as described hereinafter, or any other non-transitory medium from which a computer can read. 
     Various forms of computer readable media may be involved in carrying the above-described instructions to processor  604  to implement an embodiment of the type illustrated in  FIGS. 5A-5C . For example, such instructions may initially be carried on a magnetic disk of a remote computer. The remote computer can load such instructions into its dynamic memory and send the instructions over a telephone line using a modem. A modem local to computer system  600  can receive such instructions on the telephone line and use an infra-red transmitter to convert the received instructions to an infra-red signal. An infra-red detector can receive the instructions carried in the infra-red signal and appropriate circuitry can place the instructions on bus  602 . Bus  602  carries the instructions to main memory  606 , in which processor  604  executes the instructions contained therein. The instructions held in main memory  606  may optionally be stored on storage device  610  either before or after execution by processor  604 . 
     Computer system  600  also includes a communication interface  618  coupled to bus  602 . Communication interface  618  provides a two-way data communication coupling to a network link  620  that is connected to a local network  622 . Local network  622  may interconnect multiple computers (as described above). For example, communication interface  618  may be an integrated services digital network (ISDN) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface  618  may be a local area network (LAN) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface  618  sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information. 
     Network link  620  typically provides data communication through one or more networks to other data devices. For example, network link  620  may provide a connection through local network  622  to a host computer  624  or to data equipment operated by an Internet Service Provider (ISP)  626 . ISP  626  in turn provides data communication services through the world wide packet data communication network  628  now commonly referred to as the “Internet”. Local network  622  and network  628  both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link  620  and through communication interface  618 , which carry the digital data to and from computer system  600 , are exemplary forms of carrier waves transporting the information. 
     Computer system  600  can send messages and receive data, including program code, through the network(s), network link  620  and communication interface  618 . In the Internet example, a server  530  might transmit a code bundle through Internet  628 , ISP  626 , local network  622  and communication interface  618 . In accordance with the invention, one such downloaded software implements an embodiment of the type illustrated in  FIGS. 3A and 5 . The received software may be executed by processor  604  as received, and/or stored in storage device  610 , or other non-volatile storage for later execution. In this manner, computer system  600  may obtain the software in the form of a carrier wave. 
     Other than changes of the type described above, the data stream management system (DSMS) of several embodiments of the current invention operates in a manner similar or identical to Stanford University&#39;s DSMS. Hence, the relation operator in such a computer propagates any new tuples that have a new time stamp to all query operators coupled thereto, including the newly coupled query operator. In this manner, a computer that is programmed in accordance with the invention to receive and execute new continuous queries while continuing to operate on existing continuous queries, without prior art issues that otherwise arise from updating relation operators during modification of an executing plan. 
     In some embodiments, the extended DSMS invokes an underlying implementation of a user-defined function specified in Java, after passing all the arguments (both input/output) correctly. 
     Numerous modifications and adaptations of the embodiments described herein will be apparent to the skilled artisan in view of this current disclosure. Accordingly numerous such modifications and adaptations are encompassed by the attached claims. 
     Following Subsection A is an integral portion of the current patent application and is incorporated by reference herein in their entirety. Subsection A describes one illustrative embodiment in accordance with the invention. 
     Subsection A 
     In some embodiments, the user implements the following generic interface. 
     
       
         
           
               
             
               
                   
               
             
            
               
                 public interface SingleElementFunction { 
               
               
                  /** 
               
               
                   * Generic execute method 
               
               
                   * &lt;p&gt; 
               
               
                   * This method is called by the DSMS to invoke the function 
               
               
                   * @param args array of function arguments. This will always be non- 
               
               
                   null. 
               
               
                   *   The length of this array is equal to the number of arguments 
               
               
                   *   of this function. The ith element of this array is the ith 
               
               
                   *   argument of the function. 
               
               
                   *   The datatype of this element is the java equivalent of 
               
               
                   *   the corresponding DSMS datatype i.e. 
               
               
                   *    Integer for int 
               
               
                   *    Float for float 
               
               
                   *    String for char 
               
               
                   *    byte[ ] for byte 
               
               
                   * @return function result. Datatype is the java equivalent of the DSMS 
               
               
                   *  datatype for the return result. 
               
               
                   *  Function return should be non null 
               
               
                   */ 
               
               
                  public Object execute(Object[ ] args); 
               
               
                 } 
               
               
                 An example of a user-defined function is the following function TkUsrFib, 
               
               
                 which is used to compute Fibonnaci numbers based on data streams 
               
               
                 after it is added to the DSMS. 
               
               
                 public class TkUsrFib implements SingleElementFunction { 
               
               
                  public Object execute(Object[ ] args) throws UDFException{ 
               
               
                   int arg = 0; 
               
               
                   int res = 0; 
               
               
                   try { 
               
               
                    arg = ((Integer)args[0]).intValue( ); 
               
               
                    res = getFib(arg); 
               
               
                   } 
               
               
                   catch (Exception e) { 
               
               
                    throw new 
               
               
                 UDFException(UDFError.- 
               
               
                 USERDEFINED_FUNCTION_RUNTIME_ERROR); 
               
               
                   } 
               
               
                   return new Integer(res); 
               
               
                  } 
               
               
                  private int getFib(int n) { 
               
               
                   if (n &lt; 0) return 0; 
               
               
                   if (n == 0) return 1; 
               
               
                   if (n == 1) return 1; 
               
               
                   return getFib(n−1) + getFib(n−2); 
               
               
                  } 
               
               
                 }