Heuristic co-identification of objects across heterogeneous information sources

• US 6,108,651 A
• Filed: 02/02/1999
• Issued: 08/22/2000
• 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): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/243,210
• Time in Patent Office: 567 Days
• Field of Search: 707/2-3, 707/4, 707/100-103, 704/3, 704/4, 704/103, 704/104
• US Class Current: 1/1
• 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 request, comprising the steps of:

receiving a query requesting information;

providing a list of fields to be queried, the list of fields including a first field from a first table and a second field from a second table;

generating a database query request using the list of fields, said database query request including a join between the first and second fields; and

wherein said query includes a conjunction of literals;

wherein each literal includes a predefined term that defines a relationship between fields in a table and a concept.

2. The method of claim 1, further comprising the steps of:

mapping each of the literals to all matching expressions, wherein the mapping indicates that the first and second fields have the same meaning.

3. The method of claim 2, further comprising the step of:

providing each literal in the query with any of a predicate that matches one of the predicates in the plurality of expressions and at least one variable.

4. The method of claim 2, further comprising the step of:

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.

5. The method of claim 4, further comprising the step of:

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

6. The method of claim 4 wherein the step of generating the database query request is performed according to the steps of:

if the variable is mapped to only one field in the binding list, then the field is placed in a SELECT clause and its corresponding table is placed in a FROM clause;

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

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

7. A heuristic engine for determining which of a plurality tables to join to retrieve information requested, said heuristic engine comprising:

means for mapping a formatted expression to a matching expression in a knowledge base;

means for determining from matching expression which tables have shared column fields;

means for generating a standard database query statement to join the shared column fields; and

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;

wherein said knowledge base comprises background domain knowledge that contains information regarding concepts that are applicable to all of the plurality of tables, and expressions that are specific to the columns of each one of the plurality of tables; and

wherein said knowledge base is a network-based heterogeneous database in which requests for information originate from a user that accesses the heuristic system through a network browser and a network server.

8. A computer-implemented method for automatically generating a database query 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:

providing a knowledge base that defines relationships between column fields in the database;

receiving a database query;

mapping each query to the knowledge base;

generating the database query request, the database query request requiring at least one join between two of the fields;

executing the database query request and receiving results from the heterogeneous database;

providing 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;

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

providing a list of literals that define relationships between column fields in the databases wherein a plurality of the literals contain implicit fields representing concepts that are implicitly referenced in the tables; and

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.

9. The method of claim 8, further comprising the step of:

providing each query literal with a query predicate.

10. The method of claim 9, further comprising the steps of:

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

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

11. The method of claim 10, further comprising the steps of:

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

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

12. A computer-implemented method for generating a database query request, comprising the steps of:

receiving a query requesting information;

providing a list of fields to be queried, the list of fields including a first field from a first table and a second field from a second table;

generating a database query request using the list of fields, said database query request including a join between the first and second fields; and

providing a plurality of expressions that communicate the concepts of each of the fields in the first and second plurality of fields.

13. The method of claim 12, further comprising the step of:

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.

14. The method of claim 13, further comprising the step of:

providing the at least one argument with any of a combination of explicit fields and implicit fields and a list of attributes that identify the predicate.