System for determining queries to locate data objects

• US 10,642,805 B1
• Filed: 12/12/2016
• Issued: 05/05/2020
• Est. Priority Date: 12/12/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Masse, James Edward
• Primary Examiner(s): Featherstone, Mark D
• Assistant Examiner(s): Halm, Kweku William
• Application Number:
  US15/376,084
• Time in Patent Office: 1,240 Days
• 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/24534 Query rewriting; Transformation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes

Abstract

Described are techniques for automatically generating queries based on user input selecting one or more data objects. The parameters of the data objects may be used to generate an initial query. One or more parameters may be removed from the initial query to form an intermediate query. The parameters that are removed may be determined based on pruning data, which may indicate the frequency of the parameters within a data store and the likelihood that the parameters may be changed. The resulting intermediate query may be tested, then stored if the intermediate query locates the selected data objects. This process may be repeated until no additional parameters may be removed without causing the query to fail to locate the selected data objects. An output indicating the final query and at least a portion of the intermediate queries may be provided responsive to the user input.

Claims

1. A system comprising:

one or more memories storing computer-executable instructions; and

one or more hardware processors to execute the computer-executable instructions to;

receive first user input indicative of a plurality of data objects stored within a data store, wherein each data object of the plurality of data objects is associated with a respective set of parameters;

determine the respective sets of parameters associated with each data object of the plurality of data objects;

generate an initial query including each parameter of the respective sets of parameters, wherein the initial query has a first count of parameters;

determine correspondence between the respective sets of parameters and pruning data indicative of a first importance metric that indicates a rate of occurrence of a first parameter within the data store and a second importance metric that indicates a rate of occurrence of a second parameter within the data store;

determine that the first importance metric deviates from a first threshold importance metric;

remove the first parameter from the initial query to form an intermediate query, wherein the intermediate query has a second count of parameters that is less than the first count;

determine that querying the data store using the intermediate query locates each data object of the plurality of data objects;

determine that the second importance metric deviates from a second threshold importance metric;

remove the second parameter from the intermediate query to form a final query, wherein the final query has a third count of parameters that is less than the second count;

determine that querying the data store using the final query locates the plurality of data objects; and

output a user interface indicating the initial query, the intermediate query, and the final query.

2. The system of claim 1, further comprising computer-executable instructions to:

determine, based on the pruning data, particular parameters of the plurality of data objects having importance metrics that deviate from an initial threshold metric;

wherein the computer-executable instructions to determine the respective sets of parameters associated with each data object of the plurality of data objects and to generate the initial query exclude the particular parameters having importance metrics that deviate from the initial threshold metric.

3. The system of claim 1, further comprising computer-executable instructions to:

determine a size of the intermediate query to be less than a threshold size;

wherein the intermediate query is included in the user interface based on the size of the intermediate query being less than the threshold size.

4. The system of claim 1, further comprising computer-executable instructions to:

determine correspondence between one or more third parameters and the pruning data, wherein the one or more third parameters differ from the first parameter and the second parameter;

add the one or more third parameters to the final query to form a reconstituted query that is different from the initial query and the intermediate query; and

include the reconstituted query in the user interface.

5. A method comprising:

receiving user input indicating at least one data object within a data store, wherein the at least one data object is associated with a plurality of parameters;

determining the plurality of parameters associated with the at least one data object;

generating a first query including at least a subset of the plurality of parameters, wherein application of the first query to the data store locates the at least one data object, and wherein the first query includes a first count of parameters;

determining correspondence between the at least a subset of the plurality of parameters and pruning data;

based on the pruning data, removing at least a first parameter from the first query to form a second query, wherein the second query includes a second count of parameters that is less than the first count;

determining that application of the second query to the data store locates the at least one data object;

based on the pruning data, removing at least a second parameter from the second query to form a third query, wherein the third query includes a third count of parameters that is less than the second count;

determining that application of the third query to the data store locates the at least one data object; and

outputting data indicative of one or more of the first query, the second query, or the third query.

6. The method of claim 5, wherein the pruning data includes importance metrics associated with the plurality of parameters, the importance metrics indicative of a rate of occurrence of particular parameters of the plurality of parameters within the data store, the method further comprising:

determining that one or more importance metrics for the at least a first parameter deviate from a threshold importance metric; and

selecting the at least a first parameter for removal from the first query based on the one or more importance metrics deviating from the threshold importance metric.

7. The method of claim 5, wherein the pruning data includes changeability metrics associated with the plurality of parameters, the changeability metrics indicative of a rate of change associated with particular parameters of the plurality of parameters within the data store, the method further comprising:

determining that one or more changeability metrics for the at least a first parameter deviate from a threshold changeability metric; and

selecting the at least a first parameter for removal from the first query based on the one or more changeability metrics deviating from the threshold changeability metric.

8. The method of claim 5, further comprising:

determining a size of the second query to be less than a threshold size;

wherein the outputting of the second query and the third query is performed responsive to the size of the second query being less than the threshold size.

9. The method of claim 5, further comprising:

determining the at least a first parameter to include a count of parameters greater than a threshold count of parameters;

wherein the outputting of the second query and the third query is performed responsive to the count of parameters being greater than the threshold count of parameters.

10. The method of claim 5, further comprising:

based on the pruning data, removing at least a third parameter from the third query to form a fourth query;

determining that application of the fourth query to the data store locates one or more data objects that differ from the at least one data object; and

suppressing the fourth query from output.

11. The method of claim 5, further comprising:

receiving user input indicative of one or more of a modification or a selection of one or more of the second query or the third query to form a user query;

determining a user account associated with the user input; and

storing the user query in association with the user account.

12. The method of claim 5, further comprising:

storing the second query as pruning data; and

determining correspondence between the third query and the second query;

wherein removal of the at least a second parameter from the second query to form the third query is performed responsive to the correspondence between the third query and the second query.

13. A system comprising:

one or more memories storing computer-executable instructions; and

one or more hardware processors to execute the computer-executable instructions to;

access a first query comprising a plurality of parameters, the first query configured to locate at least one data object when applied to a data store, wherein the first query includes a first count of parameters;

determine correspondence between at least a subset of the plurality of parameters and pruning data, wherein the pruning data includes one or more of;

importance metrics associated with respective parameters, the importance metrics indicative of a rate of occurrence of particular respective parameters within the data store;

or

changeability metrics associated with the respective parameters, the changeability metrics indicative of a rate of change associated with the particular respective parameters within the data store;

based on the correspondence between the pruning data and the at least a subset of the plurality of parameters, remove at least a first parameter from the first query to form a second query, wherein the second query includes a second count of parameters that is less than the first count;

determine that application of the second query to the data store locates the at least one data object; and

generate an output including one or more of the first query or the second query.

14. The system of claim 13, further comprising computer-executable instructions to:

store the second query as pruning data;

based on the correspondence between the second query and the at least a subset of the plurality of parameters, remove at least a second parameter from the second query to form a third query;

determine that application of the third query to the data store locates the at least one data object; and

store the third query as pruning data.

15. The system of claim 14, further comprising computer-executable instructions to:

receive user input indicative of one or more of a modification or a selection of one or more of the second query or the third query to form a user query; and

store the user query in association with a user account.

16. The system of claim 13, further comprising computer-executable instructions to:

based on the correspondence between the pruning data and the at least a subset of the plurality of parameters, remove at least a second parameter from the second query to form a third query;

determine that application of the third query to the data store locates one or more data objects that differ from the at least one data object; and

suppress the third query from the output.

17. The system of claim 13, wherein the computer-executable instructions to remove the at least a first parameter from the first query include computer-executable instructions to:

remove a first set of parameters from the first query to form a modified query;

determine a first size of the modified query to be greater than a threshold size;

responsive to the first size of the modified query being greater than the threshold size, remove a second set of parameters from the modified query to form the second query; and

determine a second size of the second query to be less than the threshold size;

wherein the second query is included in the output based on the second size being less than the threshold size.

18. The system of claim 13, further comprising computer-executable instructions to:

based on the correspondence between the pruning data and the at least a subset of the plurality of parameters, remove at least a second parameter from the second query to form a third query;

determine that application of the third query to the data store locates the at least one data object;

determine that removal of one or more third parameters from the third query to form a fourth query causes application of the fourth query to the data store to locate one or more data objects that differ from the at least one data object; and

include the third query in the output.

19. The system of claim 13, further comprising computer-executable instructions to:

receive user input indicating the at least one data object;

determine the plurality of parameters associated with the at least one data object; and

generate the first query based on the plurality of parameters.

20. The system of claim 13, further comprising computer-executable instructions to:

receive user input indicative of one or more of the respective parameters, the user input indicating one or more of a preference or weight for inclusion or exclusion of the one or more of the respective parameters in the second query; and

generate at least a portion of the pruning data based at least in part on the user input.