Join index for relational databases

• US 6,167,399 A
• Filed: 05/05/1998
• Issued: 12/26/2000
• Est. Priority Date: 05/05/1998
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Hoang, Chi Kim
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): TRINH, WILLIAM B
• Application Number:
  US09/073,113
• Time in Patent Office: 966 Days
• Field of Search: 707/4, 707/2, 707/5, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99936 Pattern matching access

Abstract

The retrieval of data from a computerized database is optimized through the use of a join index. A denormalized base table is converted into a plurality of normalized tables and the join index for the normalized tables is created by combining one or more commonly-used columns of the normalized tables. Outer joins are used to generate the join index, instead of inner joins, so that the join index satisfies queries with fewer join conditions than the ones used to generate the join index. Each row of the join index comprises a fixed part and a repeated part. The fixed part is stored only once in each row, but the repeated part is comprised of recursive levels within each row, so that each row may contain as many repeated parts as needed. In addition, each of the repeated parts comprises a fixed part and a repeated part.

Claims

1. A method of optimizing retrieval of data from a computerized database, comprising:

(a) converting a denormalized base table containing the data into a plurality of normalized tables; and

(b) creating a join index for the normalized tables by combining one or more commonly-used columns of the normalized tables, wherein each row of the join index contains a fixed part and at least one repeated part, and each of the repeated parts contains a fixed part and a repeated part.

2. The method of claim 1 above, wherein the fixed part is stored only once in each row, but the repeated part is comprised of recursive levels within each row, so that each row may contain as many repeated parts as needed.

3. The method of claim 1 above, further comprising accessing the data using the join index in response to a query.

4. The method of claim 1 above, further comprising creating the join index by performing a join operation on the normalized tables.

5. The method of claim 4 above, further comprising creating the join index using one or more outer join operations instead of inner join operations.

6. The method of claim 5 above, wherein all rows from a first normalized table are retained in the join index regardless of whether the rows have a matching row in a second normalized table.

7. The method of claim 5 above, further comprising creating the join index using one or more full outer join operations.

8. The method of claim 7 above, wherein the join index retains data from all rows from the normalized tables.

9. The method of claim 1 above, further comprising specifying a referential constraint for one or more of the commonly-used columns between the normalized tables.

10. The method of claim 9 above, wherein the referential constraint relates to a foreign key of a first one of the normalized tables that references a primary key of a second one of the second normalized tables.

11. The method of claim 3 above, further comprising satisfying the query with data from the commonly-used columns of the join index rather than the normalized tables.

12. The method of claim 11 above, further comprising satisfying a query for data from the join index when the query specifies a join condition that is identical to the join operation used to create the join index.

13. The method of claim 11 above, further comprising satisfying the query with data from the join index when the query specifies a join condition that is a superset of the join operation used to create the join index.

14. The method of claim 11 above, further comprising satisfying a query with data from the join index when the query specifies a join condition that has fewer join conditions than the join operation used to create the join index.

15. An apparatus for optimizing retrieval of data from a computerized database, comprising:

(a) a computer having one or more electronic storage devices connected thereto, wherein the data is stored on one or more of the electronic storage devices;

(b) means, performed by the computer, for converting a denormalized base table containing the data into a plurality of normalized tables; and

(c) means, performed by the computer, for creating a join index for the normalized tables by combining one or more commonly-used columns of the normalized tables, wherein each row of the join index contains a fixed part and at least one repeated part, and each of the repeated parts contains a fixed part and a repeated part.

16. The apparatus of claim 15 above, wherein the fixed part is stored only once in each row, but the repeated part is comprised of recursive levels within each row, so that each row may contain as many repeated parts as needed.

17. The apparatus of claim 15 above, further comprising means for creating the join index by performing a join operation on the normalized tables.

18. The apparatus of claim 17 above, further comprising means for creating the join index using one or more outer join operations instead of inner join operations.

19. The apparatus of claim 18 above, wherein all rows from a first normalized table are retained in the join index regardless of whether the rows have a matching row in a second normalized table.

20. The apparatus of claim 18 above, further comprising means for creating the join index using one or more full outer join operations.

21. The apparatus of claim 20 above, wherein the join index retains data from all rows from the normalized tables.

22. The apparatus of claim 15 above, further comprising means for specifying a referential constraint for one or more of the commonly-used columns between the normalized tables.

23. The apparatus of claim 22 above, wherein the referential constraint relates to a foreign key of a first one of the normalized tables that references a primary key of a second one of the second normalized tables.

24. The apparatus of claim 15 above, further comprising means for accessing the data using the join index in response to a query.

25. The apparatus of claim 24 above, further comprising means for satisfying the query with data from the commonly-used columns of the join index rather than the normalized tables.

26. The apparatus of claim 25 above, further comprising means for satisfying a query for data from the join index when the query specifies a join condition that is identical to the join operation used to create the join index.

27. The apparatus of claim 25 above, further comprising means for satisfying the query with data from the join index when the query specifies a join condition that is a superset of the join operation used to create the join index.

28. The apparatus of claim 25 above, further comprising means for satisfying a query with data from the join index when the query specifies a join condition that has fewer join conditions than the join operation used to create the join index.

29. A data structure stored in a memory for use by a computer program executed by a computer, the data structure comprising a join index for a plurality of normalized tables, wherein each row of the join index comprises a fixed part and a repeated part.

30. The data structure of claim 29 above, wherein the fixed part is stored only once in each row, but the repeated part is comprised of recursive levels within each row, so that each row may contain as many repeated parts as needed.

31. A program storage device, readable by a computer, tangibly embodying one or more instructions executable by the computer to perform method steps for optimizing retrieval of data from a computerized database, the method comprising:

(a) converting a denormalized base table containing the data into a plurality of normalized tables; and

(b) creating a join index for the normalized tables by combining one or more commonly-used columns of the normalized tables, wherein each row of the join index contains a fixed part and at least one repeated part, and each of the repeated parts contains a fixed part and a repeated part.

32. The program storage device of claim 31 above, wherein the fixed part is stored only once in each row, but the repeated part is comprised of recursive levels within each row, so that each row may contain as many repeated parts as needed.

33. The program storage device of claim 31 above, further comprising creating the join index by performing a join operation on the normalized tables.

34. The program storage device of claim 33 above, further comprising creating the join index using one or more outer join operations instead of inner join operations.

35. The program storage device of claim 34 above, wherein all rows from a first normalized table are retained in the join index regardless of whether the rows have a matching row in a second normalized table.

36. The program storage device of claim 34 above, further comprising creating the join index using one or more full outer join operations.

37. The program storage device of claim 36 above, wherein the join index retains data from all rows from the normalized tables.

38. The program storage device of claim 31 above, further comprising specifying a referential constraint for one or more of the commonly-used columns between the normalized tables.

39. The program storage device of claim 38 above, wherein the referential constraint relates to a foreign key of a first one of the normalized tables that references a primary key of a second one of the second normalized tables.

40. The program storage device of claim 31 above, further comprising accessing the data using the join index in response to a query.

41. The program storage device of claim 40 above, further comprising satisfying the query with data from the commonly-used columns of the join index rather than the normalized tables.

42. The program storage device of claim 41 above, further comprising satisfying a query for data from the join index when the query specifies a join condition that is identical to the join operation used to create the join index.

43. The program storage device of claim 41 above, further comprising satisfying the query with data from the join index when the query specifies a join condition that is a superset of the join operation used to create the join index.

44. The program storage device of claim 41 above, further comprising satisfying a query with data from the join index when the query specifies a join condition that has fewer join conditions than the join operation used to create the join index.