1. Field of the Invention
The invention concerns techniques for making user tables in a database system into tracked tables on which temporal queries involving versions of rows in the tracked tables may be performed.
2. Description of Related Art
Techniques for Dealing with Time in Database Tables
There are of course many situations in which a user will include time information in a database table. A systematic discussion of the ways in which this may be done and of the difficulties that SQL, the standard language used to write queries in relational database systems, has in expressing queries involving time information may be found in Richard T. Snodgrass, Developing Time-oriented Database Applications in SQL, Morgan-Kaufmann Publishers, San Francisco, USA, 2000. Useful terminology from the Snodgrass book includes the following:
There are three fundamental temporal datatypes:                Instant: something happened at an instant of time (e.g., now, Jul. 18, 2005, when this is being written, or sometime, perhaps much later, when it is being read)        Interval: a length of time (e.g., three months)        Period: an anchored duration of time (e.g., the fall semester, Aug. 24 through Dec. 18, 1998)        
There are three fundamental kinds of time.                User-defined time: an uninterpreted time value        Valid time: when a fact was true in the reality being modeled in the table        Transaction time: when a fact was stored in the database        
These kinds of time are orthogonal: a table can be associated with none, one, two, or even all three kinds of time. The tables that are of interest for the following discussion are those associated with transaction time, which Snodgrass terms transaction-time state tables. Transaction-time state tables have the property that they can be reconstructed as of a previous date. Transaction-time state tables permit queries involving specific points in time and periods of time. Such queries are termed in the following temporal queries. Examples are:                a query to determine what versions of the table's rows were in the table as of a given date; such a query will be termed in the following an As Of query; and        a query to determine what versions of the table's rows were in the table during a given period of time; such a query will be termed in the following a versions query. In the versions query, the period of time may be specified by BETWEEN A AND B, where A and B are values that represent points in time.        
A temporal query requires temporal metadata from which the temporal query can determine the period during which a version of a row was present in the table. Various kinds of temporal metadata are of course possible; one of the simplest kinds of temporal metadata is a start value indicating when the version was added to the table and an end value indicating when the version ceased being present in the table.
Using Undo Logs for Temporal Queries
An undo log was originally a log maintained in a relational database system for the purpose of rolling back a transaction. When an operation was performed on a row during a transaction, the condition of the row prior to the modification was recorded in an entry in an undo log. The undo log entry also included temporal metadata indicating the period during which the row had been in the prior condition. If the transaction failed, the undo log entries could be used to undo the operations that had been performed up to the transaction's failure. Over time, many other uses have been found for the information in the undo log. One of the earliest was to ensure what are termed consistent reads, namely, to ensure that a field value in a record which was read during a transaction and read again during the same transaction did not change as a result of a write by another party to the field: on further reads of the field during the transaction, the field's value was read by applying undo to the current copy of the record to get the value of the field as of the start of the transaction.
A feature of Oracle@ database systems termed Flashback query took advantage of the temporal metadata contained in the undo log entry to perform temporal queries which returned versions of rows contained in the undo log. The temporal queries (either AS OF or version) were specified by means of a flashback clause in the SQL SELECT statement. A flashback query on a table worked by using the information in the undo log about versions of rows of the table to reconstruct the version of the row. For each version of the row, the version was reconstructed by applying the information in the undo log to the current version of the table. The temporal query was then applied to the set of reconstructed versions.
There were several problems with Flashback query:                There was only a limited amount of space available in the database system for the storage of the undo log; consequently, the undo log was implemented as a circular log; when the space allocated to the undo log became full of undo data, the database system overwrote the oldest undo data in the undo log with new undo data. As a consequence, temporal queries would not work where the desired versions were no longer present in the undo log.        Flashback queries could not be performed across changes in the form of a table, for example if columns were added or dropped.        
Reconstruction of row versions from the undo data was slow compared with a query on a table; further, the more undo that needed to be applied, the longer the reconstruction took.
In the following discussion, Flashback query as just described will be termed limited Flashback.
History-Enabled Tables
A known way of dealing with some of the foregoing limitations of limited Flashback is by creating history-enabled tables. When a table in a database system is history-enabled, it is associated with a history table in which the history of the rows of the history-enabled table is recorded. Each row of the history table specifies a state of a row of the history-enabled table and the period of time during which the row was in that state in the history-enabled table. The history table is modified each time a row is added, changed, or deleted in the history enabled table. Temporal queries can be done on the history table.
An embodiment of a history-enabled table is disclosed in a paper by Tal Kelley, Using Triggers to track database action history from the year 2001, which was found in Jul. 2005 at www.developerfusion.com/scripts/print.aspx?id=2413. The paper describes a technique for associating a history database table with a history-enabled database, table. A row is inserted in the history table whenever a row is inserted into the history-enabled table or an existing row in the history-enabled table is updated. The history table has columns that are equivalent to those in the history-enabled table and has additional columns that indicate the time at which the row in the history-enabled table was inserted or updated and the operation in the history-enabled table that resulted in the row being inserted in the history table. When a row is inserted in the history-enabled table, the row inserted into the history table includes the data from the history-enabled table row, the time the row was inserted in the history-enabled table, and indicates that the operation was “insert”. When a row is updated in the history-enabled table, the row that is inserted in the history table has the data from the history-enabled table row as updated, the time the row was updated in the history-enabled table, and indicates that the operation was “update”.
The rows are inserted into the history table by triggers, that is, user-written code that is automatically executed by the database system when certain events occur with regard to a table. Two of the events which may result in the execution of a trigger are the insertion of a row and the update of a row; thus, an insertion of a row in the history-enabled table results in an execution of an insert trigger that creates the row corresponding to the insertion operation in the history table; similarly, the update of a row results in an execution of an update trigger that creates the row corresponding to the update operation in the history table. The history table thus has a row for every version of every record that ever was or currently is in the history table. Consequently, not only AS OF queries, but also version queries may be made on the history table.
As may be seen from the foregoing, because rows are added to the history table as the history enabled table is modified, the queries that return past values of data are not limited to past values that are contained in the undo data. Further, because the history table need not be reconstructed but is always available in the same fashion as any other table in the database, a query on the history table takes no longer than other queries. While queries on history tables are not temporally limited by the amount of undo data as Flashback operations are, they have serious disadvantages of their own:                Because the triggers that record changes to the history-enabled table in the history table are executed each time the data in the history-enabled table changes, they affect the performance of all queries which modify the history enabled table; moreover, each execution of a trigger is the result of a single change in the history-enabled table; the operations on the history table consequently cannot be batched.        The trigger code is associated with the history-enabled table; making the table history enabled thus requires a change to the table. In many cases, making the table history enabled also involved adding data fields to the history-enabled table for the metadata required for the temporal queries on the history table.        Trigger code must be provided for each history-enabled table.        The history-enabled table cannot change its form during the period in which the history-enabled table is associated with its history table.        
What is needed is thus a way of saving the history of database objects and doing temporal queries and other Flashback operations on them which has the ease of use of Flashback queries, permits temporal queries directly on the history-enabled table, interferes minimally with execution of queries by the database system, does not require any alteration of the table whose history is being tracked, permits saving history for an unlimited period of time, can deal with changes in the form of the database table whose history is being tracked, and permits temporal queries that are substantially as fast as queries on any other table in the database. It is an object of the present invention to provide such a technique.