Indexing and searching for database records with defined validity intervals

• US 7,630,969 B2
• Filed: 08/25/2006
• Issued: 12/08/2009
• Est. Priority Date: 08/25/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Ritter, Gerd M.
• Primary Examiner(s): Robinson; Greta L
• Assistant Examiner(s): Wilcox; James J
• Application Number:
  US11/510,222
• Publication Number:
  US 20080065598A1
• Time in Patent Office: 1,201 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• 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/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A computer-implemented method of indexing an electronic database record to facilitate searching is provided, as well as a method of performing a search using the index. The method includes receiving a value for one of a start field and an end field for a database record that defines a validity range for a property. The method further includes assigning a corresponding one of multiple defined index values for the received value. There is a different index value defined for each of multiple defined consecutive ranges for the property. The assigned index value corresponds to a one of the multiple defined consecutive ranges within which the received value falls. The method also includes storing the assigned index value in association with the database record in a manner that is searchable.

Claims

1. A computer-implemented method of performing an electronic database search, the method comprising:

receiving a request to identify database records in a database that satisfy a specified condition, the records being of a type that has, for a time property, a defined validity range bounded by a value for a first attribute and a value for a second attribute, wherein the specified condition is of a type that is satisfied for a record when for a record both a first inequality condition on the first attribute value and a second inequality condition on the second attribute value are satisfied, the database permitting only one inequality condition in a scan of an index of the database;

executing a first scan of the index for the database records, the index including, for each of the records, the first attribute value for the record and an encoded value of the second attribute value for the record, the encoded value being one of multiple unique digital values for each of multiple consecutive ranges for the property within which the second attribute falls, each different unique digital value defined for each of the multiple defined consecutive ranges being a different binary code, each of the ranges comprising at least two values, the first scan identifying records for which both the inequality condition on the first attribute value and an equality condition on the encoded value for the second attribute value are satisfied;

executing a second scan of the index of the records, the second scan identifying, from among the records identified in the first scan using the inequality condition on the first attribute values and the equality condition on the encoded values for the second attribute values, records for which the inequality condition on the unencoded second attribute values is also satisfied, the equality condition on the encoded value for the second attribute filtering all records for which no value within the range corresponding to the encoded value would satisfy the inequality condition on the second attribute; and

returning data characterizing the records identified in the second scan.

2. The method of claim 1, wherein the property is a property that has a continuum of possible values.

3. The method of claim 1, wherein the second attribute is a start value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the latest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

4. The method of claim 3, wherein the first attribute is an end value field, and the inequality condition is a condition wherein the value for the end value field for a record is before a value for the property that permits the specified condition to possibly be met.

5. The method of claim 1, wherein the second attribute is an end value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the earliest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

6. The method of claim 5, wherein the first attribute is a start value field, and the inequality condition is a condition wherein the value for the start value field for a record is after a value for the property that permits the specified condition to possibly be met.

7. A computer program product tangibly embodied in a storage medium comprising program instructions that when executed perform a method of performing an electronic database search, wherein the method comprises:

receiving a request to identify database records in a database that satisfy a specified condition, the records being of a type that has, for a time property, a defined validity range bounded by a value for a first attribute and a value for a second attribute, wherein the specified condition is of a type that is satisfied for a record when for a record both a first inequality condition on the first attribute value and a second inequality condition on the second attribute value are satisfied, the database permitting only one inequality condition in a scan of an index of the database;

executing a first scan of the index for the database records, the index including, for each of the records, the first attribute value for the record and an encoded value of the second attribute value for the record, the encoded value being one of multiple unique digital values for each of multiple consecutive ranges for the property within which the second attribute falls, each different unique digital value defined for each of the multiple defined consecutive ranges being a different binary code, each of the ranges comprising at least two values, the first scan identifying records for which both the inequality condition on the first attribute value and an equality condition on the encoded value for the second attribute value are satisfied;

executing a second scan of the index of the records, the second scan identifying, from among the records identified in the first scan using the inequality condition on the first attribute values and the equality condition on the encoded values for the second attribute values, records for which the inequality condition on the unencoded second attribute values is also satisfied, the equality condition on the encoded value for the second attribute filtering all records for which no value within the range corresponding to the encoded value would satisfy the inequality condition on the second attribute; and

returning data characterizing the records identified in the second scan.

8. The computer program product of claim 7, wherein the property is a property that has a continuum of possible values.

9. The computer program product of claim 7, wherein the second attribute is a start value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the latest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

10. The computer program product of claim 9, wherein the first attribute is an end value field, and the inequality condition is a condition wherein the value for the end value field for a record is before a value for the property that permits the specified condition to possibly be met.

11. The computer program product of claim 7, wherein the second attribute is an end value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the earliest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

12. The computer program product of claim 11, wherein the first attribute is a start value field, and the inequality condition is a condition wherein the value for the start value field for a record is after a value for the property that permits the specified condition to possibly be met.

13. A computing system performing an electronic database search, the system comprising:

memory; and

one or more processors that perform operations comprising;

receiving a request to identify database records in a database that satisfy a specified condition, the records being of a type that has, for a time property, a defined validity range bounded by a value for a first attribute and a value for a second attribute, wherein the specified condition is of a type that is satisfied for a record when for a record both a first inequality, condition on the first attribute value and a second inequality condition on the second attribute value are satisfied, the database permitting only one inequality condition in a scan of an index of the database;

executing a first scan of the index for the database records, the index including, for each of the records, the first attribute value for the record and an encoded value of the second attribute value for the record, the encoded value being one of multiple unique digital values for each of multiple consecutive ranges for the property within which the second attribute falls, each different unique digital value defined for each of the multiple defined consecutive ranges being a different binary code, each of the ranges comprising at least two values, the first scan identifying records for which both the inequality condition on the first attribute value and an equality condition on the encoded value for the second attribute value are satisfied;

executing a second scan of the index of the records, the second scan identifying, from among the records identified in the first scan using the inequality condition on the first attribute values and the equality condition on the encoded values for the second attribute values, records for which the inequality condition on the unencoded second attribute values is also satisfied, the equality condition on the encoded value for the second attribute filtering all records for which no value within the range corresponding to the encoded value would satisfy the inequality condition on the second attribute; and

returning data characterizing the records identified in the second scan.

14. The system of claim 13, wherein the property is a property that has a continuum of possible values.

15. The system of claim 13, wherein the second attribute is a start value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the latest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

16. The system of claim 15, wherein the first attribute is an end value field, and the inequality condition is a condition wherein the value for the end value field for a record is before a value for the property that permits the specified condition to possibly be met.

17. The system of claim 15, wherein the second attribute is an end value field of database records, and the equality condition is a condition wherein the encoded value for the second attribute value for a record equals either the digital value corresponding to the earliest of the ranges for the property wherein the specified condition is satisfied or the digital value corresponding to any earlier ones of the ranges.

18. The system of claim 17, wherein the first attribute is a start value field, and the inequality condition is a condition wherein the value for the start value field for a record is after a value for the property that permits the specified condition to possibly be met.