INCREMENTAL SCHEMA CONSISTENCY VALIDATION ON GEOGRAPHIC FEATURES

• US 20150154243A1
• Filed: 12/20/2010
• Published: 06/04/2015
• Est. Priority Date: 12/20/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Danaher, John
• Granted Patent: US 9,158,803 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Aspects of the invention relate generally to updating interconnected feature data stored in a repository while maintaining highly consistent views of the data. More specifically, aspects relate to updating some features in bulk while providing for incremental updates for others which are not completely independent of the bulk edits. Features which may be updated incrementally may contain references to other features and may be validated on an as-needed basis. These “incremental” features may also be associated with “backreferences,” which link two features together and are used in the validation process. For example, where feature A contains a link to feature B and feature B does not also include a link to feature A, if any edits are performed on feature B, a backreference may direct the server to determine whether the references in A are still consistent with the edits to B before the edit goes into a live state.

Claims

1. A computer-implemented method for validating edits to features stored in a partition of a repository which allows for incremental edits to the features, the method comprising:

storing a plurality of features in the partition of the repository, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features;

editing, by a processor, a first feature of the plurality of features by making one or more edits to obtain an edited first feature;

identifying a reference associated with the edited first feature, the reference identifying a second feature of the plurality of features;

determining, by the processor, a relationship type based on the edited first feature and the reference, the relationship type being associated with a set of requirements;

determining, by the processor, whether the one or more edits affect a relationship of the edited first feature with the second feature based on the relationship type;

when the one or more edits are determined to affect the relationship, retrieving the referenced feature;

determining, by the processor, whether the edited first feature and the referenced second feature satisfy the set of requirements; and

when the edited first feature and the referenced feature are determined to satisfy the set of requirements, validating the edited first feature.

2. The method of claim 1, further comprising rejecting the edited feature if the one or more edits do not satisfy the set of requirements.

3. The method of claim 1, further comprising:

identifying a set of code based on the relationship type; and

determining whether the one or more edits could affect the second feature based on the set of code.

4. The method of claim 3, further comprising determining if the edited first feature and the referenced feature satisfy the set of requirements based on the set of code.

5. The method of claim 1, wherein the relationship type is a bidirectional relationship type between the edited first feature and the referenced feature.

6. The method of claim 1, wherein the second feature includes a reference to the first feature.

7. The method of claim 1, wherein the referenced feature is retrieved from the repository.

8. The method of claim 1, wherein the one or more edits to the first feature are included in an editing transaction and the referenced feature is an edited feature included in the editing transaction.

9. A computer-implemented method for acting on backreferences to features stored in a partition of a repository which allows for incremental edits to the features, the method comprising:

storing a plurality of features in the partition of the repository, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features;

editing, by a processor, a first feature of the plurality of features by making one or more edits to obtain an edited feature;

identifying a unidirectional reference associated with the edited feature, the unidirectional reference identifying a second feature of the plurality of features;

determining a unidirectional relationship type based on a type of the edited feature and a type of the second feature;

identifying a backreference action to be taken based on the unidirectional relationship type and the one or more edits, wherein the backreference action is selected from the group consisting of adding, dropping, and keeping; and

performing, by the processor, the backreference action.

10. A computer-implemented method for validating edits to features stored in a partition of a repository which allows for incremental edits to the features, the method comprising:

storing a plurality of features in the partition of the repository, each feature of the plurality of features being associated with a feature identifier, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features;

editing, by a processor, a first feature of the plurality of features by making one or more edits to obtain an edited feature associated with a feature ID which is the same as the feature ID of the first feature;

accessing a table listing a plurality of backreferences, each backreference being associated with the feature identifier associated with a referred to feature, a feature identifier associated with a referring feature, and a backreference type associated with a set of requirements;

identifying one of the plurality of backreferences associated with a referred to feature ID which is the same as the feature ID of the first feature;

determining, by the processor, whether the one or more edits affect the referring feature associated with the identified one of the plurality of backreferences based on the backreference type associated with the identified one of the plurality of backreferences;

when the one or more edits are determined to affect the referring feature associated with the identified one of the plurality of backreferences, retrieving the referring feature from the repository; and

determining, by the processor, whether the edited first feature and the referring feature are determined to satisfy the set of requirements associated with the backreference type associated with the identified one of the plurality of backreferences; and

when the edited first feature and the referring feature satisfy the set of requirements associated with the backreference type associated with the identified one of the plurality of backreferences, validating, by the processor, the edited first feature.

11. A computer for validating edits, the computer comprising:

memory including a repository with a partition;

a processor coupled to the memory, the processor being operable to;

store a plurality of features in the partition of the repository, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features;

edit a first feature of the plurality of features by making one or more edits to obtain an edited first feature;

identify a reference associated with the edited first feature, the reference identifying a second feature of the plurality of features;

determine a relationship type based on the edited first feature and the reference, the relationship type being associated with a set of requirements;

determine whether the one or more edits affect a relationship with the second feature based on the relationship type;

when the one or more edits are determined to affect the relationship, retrieve the referenced feature from the memory;

determine whether the edited first feature and the referenced feature satisfy the set of requirements; and

when the edited first feature and the referenced feature are determined to satisfy the set of requirements, validate the edited first feature.

12. The computer of claim 11, wherein the processor is further operable to reject the edited feature if the one or more edits do not satisfy the set of requirements.

13. The computer of claim 11, wherein the processor is further operable to:

identify a set of code based on the relationship type; and

determine whether the one or more edits could affect the second feature based on the set of code.

14. The computer of claim 13, wherein the processor is further operable to determine if the edited first feature and the referenced feature satisfy the set of requirements based on the set of code.

15. The computer of claim 11, wherein the relationship type is a bidirectional relationship type between the edited first feature and the referenced feature.

16. The computer of claim 11, wherein the second feature includes a reference to the first feature.

17. The computer of claim 11, wherein the referenced feature is retrieved from the repository.

18. The computer of claim 11, wherein the one or more edits to the first feature are included in an editing transaction and the referenced feature is an edited feature included in the editing transaction.

19. A computer for validating edits, the computer comprising:

memory including a repository with a partition;

a processor coupled to the memory, the processor being operable to;

store a plurality of features in the partition of the repository, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features;

edit a first feature of the plurality of features by making one or more edits to obtain an edited feature;

identify a unidirectional reference associated with the edited feature, the unidirectional reference identifying a second feature of the plurality of features;

determine a unidirectional relationship type based on a type of the edited feature and a type of the second feature;

identify a backreference action to be taken based on the unidirectional relationship type and the one or more edits, wherein the backreference action is selected from the group consisting of adding, dropping, and keeping; and

perform the backreference action.

20. A computer for validating edits, the computer comprising:

memory including a repository with a partition for storing a plurality of features in the partition of the repository, each feature of the plurality of features being associated with a feature identifier, a subset of the plurality of features being associated with a reference identifying a referenced feature of the plurality of features, and the memory also storing a table listing a plurality of backreferences, each backreference being associated with the feature identifier associated with a referred to feature, a feature identifier associated with a referring feature, and a backreference type associated with a set of requirements;

a processor coupled to the memory, the processor being operable to;

edit a first feature of the plurality of features by making one or more edits to obtain an edited feature associated with a feature ID which is the same as the feature ID of the first feature;

access the table listing the plurality of backreferences;

identify one of the plurality of backreferences associated with a referred to feature ID which is the same as the feature ID of the first feature;

determine whether the one or more edits could affect the referring feature associated with the identified one of the plurality of backreferences based on the backreference type associated with the identified one of the plurality of backreferences;

when the one or more edits are determined to affect the referring feature associated with the identified one of the plurality of backreferences, retrieve the referring feature from the repository; and

determining whether the edited first feature and the referring feature satisfy the set of requirements associated with the backreference type associated with the identified one of the plurality of backreferences; and

when the edited first feature and the referring feature are determined to satisfy the set of requirements associated with the backreference type associated with the identified one of the plurality of backreferences, validate the edited first feature.