Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-26
2001-11-13
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06317738
ABSTRACT:
The present invention relates generally to a system and method for executing database queries on an ordered sequence of rows, and particularly to a system and method for efficiently handling sequence functions that require evaluation of values stored in multiple rows of a database table.
BACKGROUND OF THE INVENTION
Sequence functions are functions that operate on ordered sets of rows and that require knowledge of or access to past values. An example of a sequence function is the running maximum function, which returns the maximum value up to the current point in an ordered sequence. Sequence functions are similar to scalar functions in that a single output value is produced for each input value. Sequence functions are different from scalar functions in that the result of a sequence function may depend on some or all of the previous values processed and the processing order.
Standard SQL (structured query language) does not provide for the direct expression or efficient computation of sequence functions. Computing sequence functions is very distinct from grouping rows or joining rows from different tables to produce a result. In the case of grouping rows, the source rows are combined with an aggregate function into a set of result rows, where each source row participates in at most a single result row. This amounts to a partitioning of the input rows into groups and then applying an aggregate to reduce each group to a single result row. In the case of joining tables, data for a result row depends on data from multiple source tables. Each source row may appear zero or more times in the result, depending on the join.
Standard SQL requires the user to construct an N-way self-join in order to compute a sequence function depending on N different rows. For example, consider a table with one row per day that records the day number and the low and high temperatures for the day. The change in low temperatures from day to day could be computed using a join query like the following:
SELECT (T
1
.LOWTEMP-T
2
.LOWTEMP)
FROM TEMP T
1
, TEMP T
2
WHERE T
1
.DAY=T
2
.DAY−1
ORDER BY DAY;
or
SELECT (T
1
.LOWTEMP-(SELECT T
2
.LOWTEMP FROM TEMP T
2
WHERE T
1
.DAY=T
2
.DAY−1))
FROM TEMP T
1
ORDER BY DAY;
This approach has several drawbacks. First, the number of joined tables increases with the number of rows referred to in the scalar expression, making the syntax neither manageable nor intuitive. Furthermore, there is an assumption that the value of DAY always increments by one in the sequence; that is, there is no generic notion of “previous.” Moreover, the execution performance of such queries is likely to be very poor because of the multiple joins.
In addition to the basic sequence functions mentioned above, various running and moving sequence functions would be useful to users of database systems. A running function is one that is applied to all rows starting with a defined beginning row and continuing through the current row. For each successive row, the running function is updated to include data from all prior rows and the current row. A moving function is one that is applied to a moving range or “window” of rows. Generally, each time a moving function is evaluated for a new row, one row is dropped from the back end of the window and the current row is added to the front end of the window. For instance, such functions would include functions for determining the running minimum, maximum, sum, average or variance of field in a table, or the moving sum, average or variance of a moving window of rows.
SUMMARY OF THE INVENTION
In summary, the present invention is a database query compiler and compilation method that has special facilities for compiling a query that includes one or more of a predefined set of running and moving sequence functions. The compiler converts the query into a predefined normalized form suitable for compilation using a running and moving function normalizer. The running and moving function normalizer converts each running and moving sequence function in the set into a corresponding ordered set of one or more executable statements, which include at least one Offset sequence function that accesses data in one or more auxiliary fields of a row of a table.
Each Offset sequence function in the normalized database query is compiled by parsing the argument of the Offset sequence function to determine a set of auxiliary fields for each row of the table. Each auxiliary field of a row contains information that may be accessed during execution of the Offset sequence function while the cursor for that table is pointing to a subsequent row.
During compilation, the Offset sequence function is converted into a compiled set of instructions, including instructions for storing and reading the auxiliary fields to and from a buffer that is separate from the table. The buffer is preferably stored in volatile, main memory. As a result, when the Offset sequence function is executed, information from a previous row is accessed without having to change the cursor position for the table.
REFERENCES:
patent: 5717911 (1998-02-01), Madrid et al.
patent: 5822749 (1998-10-01), Agarwal
patent: 5875334 (1999-02-01), Chow et al.
patent: 5930795 (1999-07-01), Chen et al.
Red Brick Systems, Inc. “Red Brick Systems White Paper; Decision-Makers, Business Data and RISQL®” ©Copyright 1996-1998, PN 660010 2/97.
Lohman Peter N.
Melton Mark E
Wehrmeister Robert M.
Alam Hosain T.
Compaq Computer Corporation
Kindred Alford W.
Pennie & Edmonds LLP
LandOfFree
System and method for computing running and moving sequence... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for computing running and moving sequence..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computing running and moving sequence... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2581874