Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-26
2001-09-11
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C705S007380
Reexamination Certificate
active
06289336
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 (T1.LOWTEMP-2.LOWTEMP)
FROM TEMP T1, TEMP T2
WHERE T1.DAY=T2.DAY−1
ORDER BY DAY;
or
SELECT (T1.LOWTEMP-(SELECT T2.LOWTEMP FROM TEMP T2
WHERE T1.DAY=T2.DAY−1))
FROM TEMP T1 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, it would be useful to have a sequence function that automatically determines the distance, in rows, between the current row and the most recent row in which a search condition was true. In this sense, this would be a sort of inverse operation to the sequence functions discussed above, returning the effective offset of the nearest previous row that satisfies a specified search condition.
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 a Rows Since sequence function, Rows Since (search condition). A query normalizer includes a Rows Since function normalizer for normalizing the Rows Since sequence function.
The Rows Since function normalizer parses the search condition of the Rows Since function to identify each reference to information from a previously access row and converts each such identified reference into an Offset sequence function, Offset(argument, index). The argument of the Offset sequence function is a specified function of the identified information from a previously accessed row of the table. The previously accessed row has a position that is index rows before the current row referenced by the cursor for the table.
The query compiler places the resulting normalized search condition in a search loop that traverses successively earlier rows in the table until it finds a row that satisfies the search condition.
During execution of the query, while the cursor for a table is pointing to a current row, each of the Offset functions in the normalized query is used to access information from a previously accessed row. However, repositioning the cursor for the table to access that information would require a change in context and thus an relatively large demand on the resources of the system executing the query.
Each of the Offset sequence functions in the normalized 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 each Offset sequence function is executed, information from a previous is accessed without having to change the cursor position for the table.
REFERENCES:
patent: 5918225 (1999-06-01), White 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 rows since sequence function... 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 rows since sequence function..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for computing rows since sequence function... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444052