Merging objects in a facts database

• US 7,567,976 B1
• Filed: 05/31/2005
• Issued: 07/28/2009
• Est. Priority Date: 05/31/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Betz, Jonathan T., Hogue, Andrew William
• Primary Examiner(s): Vital; Pierre M
• Assistant Examiner(s): Nofal; Christopher P
• Application Number:
  US11/142,740
• Time in Patent Office: 1,519 Days
• Field of Search: 705/28, 706/20, 706/50, 707/1, 707/2, 707/3, 707/100, 707/102, 710/11, 725/46
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A key attribute may be selected for a set of objects in a fact repository. A candidate attribute is identified and objects having an attribute-value pair with the candidate attribute are gathered. The candidate attribute is selected as a key attribute if the names of the gathered objects and the values of the objects for the candidate attribute satisfy predefined criteria. For instance, objects may be merged into one object if they have same or similar names and have the same value for a key attribute.

Claims

1. A computer-implemented method, comprising:

accessing a set of objects, each object having a name and a set of one or more attribute-value pairs;

identifying a candidate attribute in the attribute-value pairs;

identifying a candidate subset of the set of objects, each object of the candidate subset including a respective attribute-value pair having the candidate attribute;

selecting the candidate attribute as a key attribute of the set of objects when the attribute-value pairs in the candidate subset of objects meet predefined criteria with respect to the names of the objects in the candidate subset of objects;

identifying a first subset of the set of objects, each object in the first subset including a respective attribute-value pair having the key attribute;

identifying a second subset of the first subset, the objects in the second subset having a same value as the respective attribute-value pair having the key attribute and having a same or similar name;

merging the objects in the second subset to form a single object that includes attribute-value pairs from the objects in the second subset, including at least one attribute-value pair that has an attribute other than the key attribute; and

storing in a database information related to the selected key attribute.

2. The method of claim 1, wherein the selecting comprises:

determining, with respect to the candidate attribute, a value entropy and a name entropy based on the candidate subset of objects, wherein name entropy is a function of a respective name of each object in the candidate subset of objects; and

selecting the candidate attribute as a key attribute of the set of objects if the value entropy is below a first predefined threshold and the name entropy is below a second predefined threshold.

3. The method of claim 1, wherein the second subset includes objects having non-identical sets of attribute-value pairs.

4. The method of claim 1, wherein the objects in the second subset have same values in one or more respective attribute-value pairs having attributes other than the key attribute.

5. A computer system for processing objects, comprising:

memory;

one or more processors; and

one or more modules, stored in the memory and executed by the one or more processors, the modules having instructions;

to access a set of objects, each object having a name and a set of one or more attribute-value pairs;

to identify a candidate attribute in the attribute-value pairs;

to identify a candidate subset of the set of objects, each object of the candidate subset including a respective attribute-value pair having the candidate attribute;

to select the candidate attribute as a key attribute of the set of objects when the attribute-value pairs in the candidate subset of objects meet predefined criteria with respect to the names of the objects in the candidate subset of objects;

to identify a first subset of the set of objects, each object in the first subset including a respective attribute-value pair having the key attribute;

to identify a second subset of the first subset, the objects in the second subset having a same value in the respective attribute-value pair having the key attribute and having a same or similar name;

to merge the objects in the second subset to form a single object that includes attribute-value pairs from the objects in the second subset, including at least one attribute-value pair that has an attribute other than the key attribute; and

to store information related to the selected key attribute in a database.

6. The system of claim 5, wherein the one or more modules include instructions:

to determine, with respect to the candidate attribute, a value entropy and a name entropy based on the candidate subset of objects, wherein name entropy is a function of a respective name of each object in the candidate subset of objects; and

to select the candidate attribute as a key attribute of the set of objects if the value entropy is below a first predefined threshold and the name entropy is below a second predefined threshold.

7. The system of claim 5, wherein the second subset includes objects having non-identical sets of attribute-value pairs.

8. The system of claim 5, wherein the objects in the second subset have same values in one or more respective attribute-value pairs having attributes other than the key attribute.

9. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising instructions for:

accessing a set of objects, each object having a name and a set of one or more attribute-value pairs;

identifying a candidate attribute in the attribute-value pairs;

identifying a candidate subset of the set of objects, each object of the candidate subset including a respective attribute-value pair having the candidate attribute;

selecting the candidate attribute as a key attribute of the set of objects when the attribute-value pairs in the candidate subset of objects meet predefined criteria with respect to the names of the objects in the candidate subset of objects;

identifying a first subset of the set of objects, each object in the first subset including a respective attribute-value pair having the key attribute;

identifying a second subset of the first subset, the objects in the second subset having a same value in the respective attribute-value pair having the key attribute and having a same or similar name;

merging the objects in the second subset to form a single object that includes attribute-value pairs from the objects in the second subset, including at least one attribute-value pair that has an attribute other than the key attribute; and

storing in a database information related to the selected key attribute.

10. The computer program product of claim 9, wherein the instructions for selecting comprise instructions for:

determining, with respect to the candidate attribute, a value entropy and a name entropy based on the candidate subset of objects, wherein name entropy is a function of a respective name of each object in the candidate subset of objects; and

selecting the candidate attribute as a key attribute of the set of objects if the value entropy is below a first predefined threshold and the name entropy is below a second predefined threshold.

11. The computer program product of claim 9, wherein the second subset includes objects having non-identical sets of attribute-value pairs.

12. The computer program product of claim 9, wherein the objects in the second subset have same values in one or more respective attribute-value pairs having attributes other than the key attribute.