Automated latent star schema discovery tool

• US 7,856,416 B2
• Filed: 04/22/2008
• Issued: 12/21/2010
• Est. Priority Date: 04/22/2008
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Hoffman, Virginia, McArdle, James M.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Spieler; William
• Application Number:
  US12/107,141
• Publication Number:
  US 20090265335A1
• Time in Patent Office: 973 Days
• Field of Search: 707/605, 707/804
• US Class Current: 707/605
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A method, computer program product, and data processing system for computer-aided design of multidimensional data warehouse schemas are disclosed. A preferred embodiment of the present invention provides a software tool for identifying a latent star schema structure within an existing database. This software tool performs a heuristic analysis of the existing database schema to locate potential keys and measurement fields. Database tables within the existing schema are scored heuristically as to their suitability as fact tables based on the key candidates and measurement fields. For each fact table, other tables from the existing schema are identified as possible dimension tables. Data from the database is then used to test the suitability of the fact tables and dimension tables. The identified fact tables and their associated dimension tables are then reported to the user to reveal a basic star schema structure, which can be used as a basis for further design.

Claims

1. A computer-performed method of discovering a latent organizational structure of a relational database, the method comprising:

selecting, by a computer, a plurality of key candidates from a plurality of relational database tables, wherein the key candidates are selected using a first set of heuristic criteria;

selecting, by the computer, one or more fact table candidates in the plurality of relational database tables based on said fact table candidates containing key candidates from the plurality of key candidates;

selecting, by the computer, one or more dimension table candidates based on the plurality of key candidates and a second set of heuristic criteria; and

presenting, by the computer to a user of the computer, the one or more fact table candidates, the key candidates, and the one or more dimension table candidates as a star schema.

2. The method of claim 1, further comprising:

selecting, by the computer, one or more measurement field candidates from the plurality of relational database tables based on a third set of heuristic criteria; and

selecting, by the computer, the one or more fact tables based on the fact table candidates containing the one or more field candidates in addition to key candidates from the plurality of key candidates.

3. The method of claim 2, wherein the third set of heuristic criteria includes a criterion wherein database table fields having numeric datatypes are favored as measurement field candidates.

4. The method of claim 1, wherein the first set of heuristic criteria includes a criterion wherein database table fields having enumerable datatypes are favored as key candidates.

5. The method of claim 1, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names containing particular pre-specified strings are favored as key candidates.

6. The method of claim 1, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names that appear in multiple tables from the plurality of relational database tables are favored as key candidates.

7. The method of claim 1, wherein the second set of heuristic criteria includes a criterion wherein a relational database table containing one of the plurality of key candidates as a field, where each value in said field appears only once in said relational database table, is favored as a dimension table candidate.

8. A computer program product in one or more tangible computer-readable storage media, comprising functional descriptive material that, when executed by a computer, causes the computer to perform actions of:

selecting a plurality of key candidates from a plurality of relational database tables, wherein the key candidates are selected using a first set of heuristic criteria;

selecting one or more fact table candidates in the plurality of relational database tables based on said fact table candidates containing key candidates from the plurality of key candidates;

selecting one or more dimension table candidates based on the plurality of key candidates and a second set of heuristic criteria; and

presenting, to a user of the computer, the one or more fact table candidates, the key candidates, and the one or more dimension table candidates as a star schema.

9. The computer program product of claim 8, comprising additional functional descriptive material that, when executed by the computer, causes the computer to perform actions of:

selecting one or more measurement field candidates from the plurality of relational database tables based on a third set of heuristic criteria; and

selecting the one or more fact tables based on the fact table candidates containing the one or more field candidates in addition to key candidates from the plurality of key candidates.

10. The computer program product of claim 9, wherein the third set of heuristic criteria includes a criterion wherein database table fields having numeric datatypes are favored as measurement field candidates.

11. The computer program product of claim 8, wherein the first set of heuristic criteria includes a criterion wherein database table fields having enumerable datatypes are favored as key candidates.

12. The computer program product of claim 8, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names containing particular pre-specified strings are favored as key candidates.

13. The computer program product of claim 8, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names that appear in multiple tables from the plurality of relational database tables are favored as key candidates.

14. The computer program product of claim 8, wherein the second set of heuristic criteria includes a criterion wherein a relational database table containing one of the plurality of key candidates as a field, where each value in said field appears only once in said relational database table, is favored as a dimension table candidate.

20. The computer program product of claim 8, wherein the second set of heuristic criteria includes a criterion wherein a relational database table containing one of the plurality of key candidates as a field, where each value in said field appears only once in said relational database table, is favored as a dimension table candidate.

15. A data processing system comprising:

at least one processor;

data storage accessible to the at least one processor;

a set of instructions in the data storage, wherein the at least one processor executes the set of instructions to perform actions of

selecting a plurality of key candidates from a plurality of relational database tables, wherein the key candidates are selected using a first set of heuristic criteria;

selecting one or more fact table candidates in the plurality of relational database tables based on said fact table candidates containing key candidates from the plurality of key candidates;

selecting one or more dimension table candidates based on the plurality of key candidates and a second set of heuristic criteria; and

presenting, to a user of the data processing system, the one or more fact table candidates, the key candidates, and the one or more dimension table candidates as a star schema.

16. The data processing system of claim 15, wherein the at least one processor executes the set of instructions to perform additional actions of:

selecting one or more measurement field candidates from the plurality of relational database tables based on a third set of heuristic criteria; and

selecting the one or more fact tables based on the fact table candidates containing the one or more field candidates in addition to key candidates from the plurality of key candidates.

17. The data processing system of claim 15, wherein the first set of heuristic criteria includes a criterion wherein database table fields having enumerable datatypes are favored as key candidates.

18. The data processing system of claim 15, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names containing particular pre-specified strings are favored as key candidates.

19. The data processing system of claim 15, wherein the first set of heuristic criteria includes a criterion wherein database table fields having names that appear in multiple tables from the plurality of relational database tables are favored as key candidates.