DISCOVERING TOPICAL STRUCTURES OF DATABASES

• US 20090216799A1
• Filed: 02/21/2008
• Published: 08/27/2009
• Est. Priority Date: 02/21/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sismanis, John, Reinwald, Berthold, Wu, Wensheng, Manjrekar, Rajesh P.
• Granted Patent: US 7,818,323 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

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, all the limitations of which are incorporated herein by reference, wherein said representations comprise representations that are at least two of:

vector-based representations;

graph-based representations; and

similarity-based representations.

3. The method according to claim 2, all the limitations of which are incorporated herein by reference,

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.

4. The method according to claim 1, all the limitations of which are incorporated herein by reference, wherein said preliminary topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

5. The method according to claim 1, all the limitations of which are incorporated herein by reference, wherein said determining of said representative tables is based on table importance.

10. The method according to claim 1, all the limitations of which are incorporated herein by reference, wherein said topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

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

performing topical clustering of tables within said database to produce a plurality of clusterings;

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

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

outputting said topical directory.

7. The method according to claim 6, all the limitations of which are incorporated herein by reference, further comprising computing various kinds of representations for said database based on schema information and data values of said database, and

wherein said topical clustering is performed such that each of said topical clusters corresponds to one set of said tables on the same topic.

8. The method according to claim 7, all the limitations of which are incorporated herein by reference, wherein said representations comprise representations that are at least two of:

vector-based representations;

graph-based representations; and

similarity-based representations.

9. The method according to claim 8, all the limitations of which are incorporated herein by reference,

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.

11. A 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;

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.

12. The computer program storage medium according to claim 11, all the limitations of which are incorporated herein by reference, wherein said representations comprise representations that are at least two of:

vector-based representations;

graph-based representations; and

similarity-based representations.

13. The computer program storage medium according to claim 12, all the limitations of which are incorporated herein by reference,

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 computer program storage medium according to claim 11, all the limitations of which are incorporated herein by reference, wherein said preliminary topical clustering is discovered by employing one of similarity-based clustering and linkage-based clustering.

15. The computer program storage medium according to claim 11, all the limitations of which are incorporated herein by reference, wherein said determining of said representative tables is based on table importance.

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

a model builder adapted to compute various kinds of representations for said database based on schema information and data values of said database;

a plurality of base clusterers, wherein each base clusterer corresponds to one of said kinds of representations, and each base clusterer is adapted 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 adapted 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 adapted 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 adapted to arrange said representative tables by topic as a topical directory of said representative tables and output said topical directory.

17. The system according to claim 16, all the limitations of which are incorporated herein by reference, wherein said model builder is adapted to compute said representations that are at least two of:

vector-based representations;

graph-based representations; and

similarity-based representations.

18. The system according to claim 17, all the limitations of which are incorporated herein by reference,

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.

19. The system according to claim 16, all the limitations of which are incorporated herein by reference, wherein each base clusterer is adapted to perform one of similarity-based clustering and linkage-based clustering.

20. The system according to claim 16, all the limitations of which are incorporated herein by reference, wherein said representative finder is adapted to determine said representative tables based on table importance.