System and method for selecting rows from dimensional databases having temporal dimention

• US 6,233,573 B1
• Filed: 12/13/1999
• Issued: 05/15/2001
• Est. Priority Date: 07/25/1997
• Status: Expired due to Term

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon.com, Inc.
• Inventors: Bender, Charles M, Bair, John
• Primary Examiner(s): CHOULES, JACK M
• Application Number:
  US09/459,716
• Time in Patent Office: 519 Days
• Field of Search: 707/1, 707/3, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method selects rows from a fact table in a dimensional database containing a fact table, a time dimension table and other dimension tables. The other dimension tables each contain rows containing a time invariant attribute to identify an item described by the row, an effective time attribute for the row, and other attributes. If an attribute for an item changes, a new row is added to the dimension table containing the time-invariant attribute for the item and current attributes for the item, without deleting or overwriting any existing rows for that item. Such dimension tables can be selected or used to create other tables using one or more time attributes of the dimension tables. The tables created can be selected or used to create still other tables using one or more time attributes of those tables. One or more of the resulting tables or one or more tables created from a resulting table are then joined to a table in the dimensional database or a table created from a table in the dimensional database.

Claims

1. One or more computer memories collectively containing a dimensional database data structure for resolving temporal queries, comprising:

a time dimension table whose rows each represent a time and are each uniquely identified by a time key;

a second dimension table whose rows each represent one state of a time-variable attribute of a particular item, each row containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item; and

a fact table whose rows each contain an item identifier identifying an item to which the row relates, such that a temporal query specifying a condition of the time-variable attribute and effective time may be resolved by using the time dimension table to identify rows of the second dimension table satisfying the condition, generating an intermediate table whose rows each contain an item identifier from an identified row of the second dimension table, and joining the intermediate table and the fact table.

2. The computer memories of claim 1 wherein the time key of each row of the second dimensional table identifies a row of the time dimension table representing a time at which the time-variable attribute value is first effective for the item.

3. The computer memories of claim 1 wherein the time key of each row of the second dimensional table identifies a row of the time dimension table representing a time at which the time-variable attribute value is last effective for the item.

4. A method in a computer system for resolving a temporal queries in a dimensional database, comprising:

receiving a temporal query specifying a condition of the time-variable attribute and effective time;

accessing the dimensional database, the dimensional database comprising a time dimension table, a second dimension table, and a fact table, the time dimension table having rows that each represent a time and are each uniquely identified by a time key, the second dimension table having rows that each represent one state of a time-variable attribute of a particular item, each row of the second dimension table containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item, the fact table having rows that each contain an item identifier identifying an item to which the row relates;

using the time dimension table to identify rows of the second dimension table satisfying the condition;

generating an intermediate table comprising rows, each of said rows comprising an item identifier from an identified row of the second dimension table; and

joining the intermediate table and the fact table.

5. A computer-readable medium whose contents cause a computer system to resolving a temporal queries in a dimensional database by:

receiving a temporal query specifying a condition of the time-variable attribute and effective time;

accessing the dimensional database, the dimensional database comprising a time dimension table, a second dimension table, and a fact table, the time dimension table having rows that each represent a time and are each uniquely identified by a time key, the second dimension table having rows that each represent one state of a time-variable attribute of a particular item, each row of the second dimension table containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item, the fact table having rows that each contain an item identifier identifying an item to which the row relates;

using the time dimension table to identify rows of the second dimension table satisfying the condition;

generating an intermediate table comprising rows, each of said rows comprising an item identifier from an identified row of the second dimension table; and

joining the intermediate table and the fact table.

6. A data processing system for satisfying a temporal query, comprising:

one or more storage devices collectively containing a dimensional database for resolving temporal queries, comprising;

a time dimension table whose rows each represent a time and are each uniquely identified by a time key,

a second dimension table whose rows each represent one state of a time-variable attribute of a particular item, each row containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item, and

a fact table whose rows each contain an item identifier identifying an item to which the row relates;

a query receiver that receives temporal queries each specifying a condition of the time-variable attribute and effective time; and

a query processing subsystem that satisfies temporal queries received by the query receiver by using the time dimension table to identify rows of the second dimension table satisfying the condition, generating an intermediate table whose rows each contain an item identifier from an identified row of the second dimension table, and joining the intermediate table and the fact table.

7. One or more computer memories collectively containing a dimensional database data structure supporting time-variable attributes, comprising:

a time dimension table whose rows each represent a time and are each uniquely identified by a time key; and

a second dimension table whose rows each represent one state of a time-variable attribute of a particular item, each row containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item;

such that the effective time of a time-variable attribute value for a particular row of the second dimension table may be determined by determining the time represented by a row of the time dimension table identified by the time key contained by that row of the second dimension table, and such that the effective times of the time-variable attribute values for a plurality of rows of the second dimension table may be determined by joining the time dimension table and the second dimension table on columns of those tables containing the time keys.

8. A data processing system for supporting time-variable attributes in a dimensional database, comprising:

one or more storage devices collectively containing a dimensional database, comprising;

a time dimension table whose rows each represent a time and are each uniquely identified by a time key, and

a second dimension table whose rows each represent one state of a time-variable attribute of a particular item, each row containing an item identifier for the item, a time-variable attribute value, and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item; and

an effective time determination subsystem that determines the effective times of the time-variable attribute values for a plurality of rows of the second dimension table by joining the time dimension table and the second dimension table on columns of those tables containing the time keys.

9. One or more computer memories collectively containing a dimensional database data structure for resolving temporal queries, comprising:

a time dimension table whose rows each represent a time and are each uniquely identified by a time key;

a second dimension table whose rows each represent one state of a time-variable attribute of a particular item, each row containing a time-variable attribute value and an surrogate attribute reflecting both the identity of the item and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value is effective for the item; and

a fact table whose rows each contain a surrogate attribute identifying an item and a time to which the row relates,

such that a temporal query specifying a condition of the time-variable attribute and effective time may be resolved by using the time dimension table to identify rows of the second dimension table satisfying the condition, generating an intermediate table whose rows each contain a surrogate attribute from an identified row of the second dimension table, and joining the intermediate table and the fact table on the surrogate attribute.

10. The computer memories of claim 9 wherein the time key of each row of the second dimensional table identifies a row of the time dimension table representing a time at which the time-variable attribute value is first effective for the item.

11. The computer memories of claim 9 wherein the time key of each row of the second dimensional table identifies a row of the time dimension table representing a time at which the time-variable attribute value is last effective for the item.

12. The computer memories of claim 9 wherein, for each row of the second dimension table, the surrogate attribute is a concatenation of an item identifier identifying an item whose state is described by the row and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value of the row is effective for the item.

13. The computer memories of claim 9 wherein, for each row of the second dimension table, the surrogate attribute is a key identifying a row of a surrogate table containing an item identifier identifying an item whose state is described by the row of the second dimension table and a time key identifying a row of the time dimension table representing a time at which the time-variable attribute value of the row of the second dimension table is effective for the item.