Discovering topical structures of databases

• US 7,818,323 B2
• Filed: 02/21/2008
• Issued: 10/19/2010
• Est. Priority Date: 02/21/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Wensheng, Manjrekar, Rajesh P., Sismanis, John, Reinwald, Berthold
• Primary Examiner(s): Mofiz; Apu M.
• Assistant Examiner(s): STACE, BRENT S
• Application Number:
  US12/034,964
• Publication Number:
  US 20090216799A1
• Time in Patent Office: 971 Days
• Field of Search: 707/738, 707/737, 707/736, 707/802, 707/803
• US Class Current: 707/738
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data

Abstract

A system and method for automatically discovering topical structures of databases includes a model builder adapted to compute various kinds of representations for the database based on schema information and data values of the database. A plurality of base clusterers is also provided, one for each representation. Each base clusterer is adapted to perform, for the representation, preliminary topical clustering of tables within the database to produce a plurality of clusters, such that each of the clusters corresponds to a set of tables on the same topic. A meta-clusterer aggregates results of the clusterers into a final clustering, such that the final clustering comprises a plurality of the clusters. A representative finder identifies representative tables from the clusters in the final clustering. The representative finder identifies at least one representative table for each of the clusters in the final clustering. The representative finder also arranges the representative tables by topic as a topical directory and outputs the topical directory.

Claims

1. A method for automatically discovering topical structures of at least one database comprising tables, said method comprising:

computing various kinds of representations for said database based on schema information and data values of said database, wherein said representations comprise representations that are at least two of;

vector-based representations;

graph-based representations; and

similarity-based representations;

performing preliminary topical clustering of tables within said database to produce a plurality of clusterings, such that each of said clusterings corresponds to one representation;

aggregating results of said clusterings into a final clustering, such that said final clustering comprises a plurality of topical clusters;

identifying representative tables from said topical clusters in said final clustering, wherein at least one representative table is identified for each of said topical clusters in said final clustering;

arranging said representative tables by topic as a topical directory of said representative tables; and

outputting said topical directory.

2. The method according to claim 1,

wherein in said vector-based representations, each table of said database is represented as a text document,

wherein in said graph-based representations, said database is represented as a graph, tables of said database are represented as nodes, and edges of said graph are represented as linkages between said tables, and

wherein in said similarity-based representation, said database is represented as a similarity matrix with table similarities computed from attribute values.

3. The method according to claim 1, wherein said preliminary topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

4. The method according to claim 1, wherein said determining of said representative tables is based on table importance.

5. A method for automatically discovering topical structures of at least one database comprising tables, said method comprising:

computing various kinds of representations for said database based on schema information and data values of said database, wherein said representations comprise representations that are at least two of;

vector-based representations;

graph-based representations; and

similarity-based representations;

performing topical clustering of tables within said database to produce a plurality of clusterings, wherein said topical clustering is performed such that each of said topical clusterings corresponds to one set of said tables on a same topic and such that each of said topical clusterings corresponds to one representation;

aggregating results of said clusterings into a final clustering, such that said final clustering comprises a plurality of said topical clusters;

identifying representative tables from said topical clusters in said final clustering, wherein at least one representative table is identified for each of said topical clusters in said final clustering;

arranging said topical clusters by topic as a topical directory; and

outputting said topical directory.

6. The method according to claim 5,

wherein in said vector-based representations, each table of said database is represented as a text document,

wherein in said graph-based representations, said database is represented as a graph, tables of said database are represented as nodes, and edges of said graph are represented as linkages between said tables, and

wherein in said similarity-based representation, said database is represented as a similarity matrix with table similarities computed from attribute values.

7. The method according to claim 5, wherein said topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

8. A non-transitory computer program storage medium tangibly embodying a program of instructions executable by a computer to perform a method for automatically discovering topical structures of at least one database comprising tables, said method comprising:

computing various kinds of representations for said database based on schema information and data values of said database, wherein said representations comprise representations that are at least two of;

vector-based representations;

graph-based representations; and

similarity-based representations;

performing preliminary topical clustering of tables within said database to produce a plurality of clusterings, such that each of said clusterings corresponds to one of said representations;

aggregating results of said clusterings into a final clustering, such that said final clustering comprises a plurality of said topical clusters;

identifying representative tables from said topical clusters in said final clustering, wherein at least one representative table is identified for each of said topical clusters in said final clustering;

arranging said representative tables by topic as a topical directory of said representative tables; and

outputting said topical directory.

9. The computer program storage medium according to claim 8,

wherein in said vector-based representations, each table of said database is represented as a text document,

wherein in said graph-based representations, said database is represented as a graph, tables of said database are represented as nodes, and edges of said graph are represented as linkages between said tables, and

wherein in said similarity-based representation, said database is represented as a similarity matrix with table similarities computed from attribute values.

10. The computer program storage medium according to claim 8, wherein said preliminary topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

11. The computer program storage medium according to claim 8, wherein said determining of said representative tables is based on table importance.

12. A system for automatically discovering topical structures of at least one database comprising tables, said system comprising:

a model builder, executing on a processor, configured to compute various kinds of representations for said database based on schema information and data values of said database, wherein said model builder is configured to compute said representations that are at least two of;

vector-based representations;

graph-based representations; and

similarity-based representations;

a plurality of base clusterers, wherein each base clusterer corresponds to one of said kinds of representations, and each base clusterer is configured to perform, for a corresponding representation, preliminary topical clustering of tables within said database to produce a plurality of topical clusters, such that each of said topical clusters corresponds to a set of said tables on the same topic;

a meta-clusterer configured to aggregate results of said topical clusters into a final clustering, such that said final clustering comprises a plurality of said topical clusters; and

a representative finder configured to identify representative tables from said topical clusters in said final clustering, wherein at least one representative table is identified for each of said topical clusters in said final clustering, and

wherein said representative finder is further configured to arrange said representative tables by topic as a topical directory of said representative tables and output said topical directory.

13. The system according to claim 12,

wherein in said vector-based representations, each table of said database is represented as a text document,

wherein in said graph-based representations, said database is represented as a graph, tables of said database are represented as nodes, and edges of said graph are represented as linkages between said tables, and

wherein in said similarity-based representation, said database is represented as a similarity matrix with table similarities computed from attribute values.

14. The system according to claim 12, wherein each base clusterer is configured to perform one of similarity-based clustering and linkage-based clustering.

15. The system according to claim 12, wherein said representative finder is configured to determine said representative tables based on table importance.