Heuristic co-identification of objects across heterogeneous information sources

• US 5,895,465 A
• Filed: 09/09/1997
• Issued: 04/20/1999
• Est. Priority Date: 09/09/1997
• Status: Expired due to Term

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Netscape Communications Corporation (Apollo Global Management, Inc.)
• Inventors: Guha, Ramanathan V.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US08/925,632
• Time in Patent Office: 588 Days
• Field of Search: 707/4, 707/103, 707/2, 707/3
• US Class Current: 707/714
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for generating a database query language request for performing a join between a plurality of database tables including a first database table and a second database table. The first table includes a first plurality of fields and the second database table includes a second plurality of fields, where each one of the plurality of fields has a particular meaning. The method and system includes providing a plurality of expressions that communicate the meaning of the each of the fields in the first and second plurality of fields. A user then submits a query requesting information from the tables in the form of a conjunction of literals. Each of the literals are then mapped to all matching expressions to provide a list of fields to be queried. The list of fields includes a first field from the first table and a second field from the second table, such that the mapping indicates that the first and second fields have the same meaning. After mapping the literals to the expressions, the database query language request is generated using the list of fields, such that the database query language request includes a join between the first and second fields. The first and second tables are then queried using the database query language request to provide the requested information.

Claims

1. A computer-implemented method for generating a database query language request for performing a join between a plurality of database tables including a first database table and a second database table, the first table having a first plurality of fields and the second database table having a second plurality of fields, each one of the plurality of fields having a particular meaning, the method comprising the steps of:

(a) providing a plurality of expressions that communicate the meaning of each of the fields in the first and second plurality of fields;

(b) receiving a query requesting information, the query including a conjunction of literals;

(c) mapping each of the literals to all matching expressions to provide a list of fields to be queried, the list of fields including a first field from the first table and a second field from the second table, wherein the mapping indicates that the first and second fields have the same meaning; and

(d) generating the database query language request using the list of fields, such that the database query language request includes a join between the first and second fields.

2. The method of claim 1 wherein step (a) further comprises the step of:

(a1) providing each one of the plurality of expressions with a predicate and at least one argument, wherein the predicate specifies relationships between the plurality of fields in the plurality of database tables.

3. The method of claim 2 wherein step (a) further comprises the step of:

(a2) providing the at least one argument with a combination of explicit fields and implicit fields.

4. The method of claim 2 wherein step (a) further comprises the step of:

(a2) providing the at least one argument with a list of attributes that identify the predicate.

5. The method of claim 4 wherein step (b) further comprises the step of:

(b1) providing each literal in the query with a predicate that matches one of the predicates in the plurality of expressions.

6. The method of claim 5 wherein step (b) further comprises the step of:

(b2) providing each literal in the query with at least one variable.

7. The method of claim 6 wherein step (c) further comprises the step of:

(c1) generating a binding list of variables from the literals that map to fields in the first and second tables, each entry in the binding list identifying what field in the first and second table may be used to retrieve values for the corresponding variables.

8. The method of claim 7 wherein the database query language request includes a SELECT'"'"', FROM, and WHERE clause, step (d) further comprising the step of:

(d1) using each entry in the binding list as a constraint to be satisfied in the WHERE clause.

9. The method of claim 8 wherein step (d) of generating the database query language request is performed according to the steps of:

(d2) if the variable is mapped to only one field in the binding list, then the field is placed in the SELECI clause and its corresponding table is placed in the FROM clause;

(d2) if a variable maps to more than one field, then the fields to which it binds are set equal in the WHERE clause; and

(d3) if the variable is a constant, then the field to which the variable maps is set equal to the value of the constant in the WHERE clause.

10. The method of claim 9 wherein the fields in the WHERE clause include implicit fields and explicit fields, step (d) further comprising the steps of:

(d4) expanding each implicit field in the WHERE clause into one or more explicit fields from the meaning expressions by

(i) matching the implicit fields in the WHERE with the predicates in the plurality of expressions,

(ii) generating a set of possible replacement explicit fields from the explicit fields in the matching meaning expressions, and

(iii) reducing the set of possible replacement explicit fields to a set of legal replacement explicit fields by performing an intersection between the set of possible replacement explicit fields and the attributes in the matching predicates.

11. A heuristic system for automatically generating standard query language statements for performing joins across tables in a heterogeneous database, the heterogeneous database including a plurality of databases having a plurality of tables, each of the tables comprising a plurality of column fields, the heuristic system comprising:

a knowledge base comprising a set of expressions defining a particular meaning of each of the column fields in the database and the relationships between the column fields of the database;

a translator for receiving requests for information, and for translating each of the requests into a formatted expression that matches at least one of the expressions in the knowledge base; and

a heuristic engine for determining which of the tables to join to retrieve the information requested, the heuristic engine including means for mapping each formatted expression to a matching expression in the knowledge base, means for determining from the matching expressions which tables have shared column fields, and means for generating the standard database query statement to join the shared column fields.

12. A heuristic system as in claim 11 wherein the knowledge base comprises background domain knowledge that contains information regarding concepts that are applicable to all of the plurality of tables, and meaning expression that are specific to the columns of each one of the plurality of tables.

13. A heuristic system as in claim 12 wherein each of the databases is administered by a data administrator, and wherein the meaning expressions corresponding to each one of the plurality of tables is provided by the respective data administrator.

14. A heuristic system as in claim 13 wherein the knowledge base expressions are implemented in a meta content format.

15. A heuristic system as in claim 14 wherein the heterogeneous database is a network-based heterogeneous database, the requests for information originating from a user that accesses the heuristic system through a network browser and a network server.

16. A computer-implemented method for automatically generating a database query language request for performing a join across tables in a heterogeneous database, each of the tables including a plurality column fields, the method comprising the steps of:

(a) providing a knowledge base comprising a list of literals that define relationships between the column fields in the database, wherein a plurality of the literals contain implicit fields representing concepts that are implicitly referenced in the tables;

(b) receiving a database query in the form of query literals, each query literal including at least one variable;

(c) mapping each query literal to the literals in the knowledge base to provide a list of potential fields that comprise implicit fields and a first set of explicit fields that correspond to column fields from which to retrieve values for each variable in the query literal;

(d) expanding any implicit fields present in the list of potential fields into a second set of explicit fields;

(e) generating the database query language request using the first and second sets of explicit fields, the database query language request requiring at least one join between two of the explicit fields; and

(f) executing the database query language request and receiving results from the heterogeneous database.

17. The method of claim 16 wherein step (a) further comprises the step of:

(a1) providing each one of said literals with a predicate, an implicit field and an explicit field, such that the predicate represents a particular concept that is attributable to the concept represented by the corresponding implicit field, and the explicit field indicates where values for the concept represented by the predicate are stored.

18. The method of claim 17 wherein step (c) further comprises the step of:

(c1) providing each query literal with a query predicate.

19. The method of claim 18 wherein step (d) further comprises the steps of:

(d1) comparing each query predicate to the predicates in the literals in the knowledge base; and

(d1) generating a binding list of literals in the knowledge base whose predicates match query predicates.

20. The method of claim 19 wherein step (d) further comprises the steps of:

(d1) searching the knowledge base for literals that have implicit fields which match the implicit fields in the binding list; and

(d2) replacing the implicit fields with the corresponding explicit fields found in the matching literals.