Automatically ranking answers to database queries

• US 20040002973A1
• Filed: 06/28/2002
• Published: 01/01/2004
• Est. Priority Date: 06/28/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chaudhuri, Surajit, Das, Gautam, Gionis, Aris
• Granted Patent: US 7,251,648 B2
• Time in Patent Office: Days
• US Class Current: 707/7
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method for automatically ranking database records by relevance to a given query. A similarity function is derived from data in the database and/or queries in a workload. The derrived similarity function is applied to a given query and records it in the database to rank the records. The records are returned in a ranked order.

Claims

1. A method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) deriving a similarity function from at least one of data in a database and a workload of queries;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

2. The method of claim 1 wherein said similarity function is derived only from at least one of data in said database and said workload of queries.

3. The method of claim 1 wherein said given query is a conjunctive condition.

4. The method of claim 1 wherein the similarity function corresponds to an inverse frequency of attribute values in records of the database.

5. The method of claim 1 wherein the similarity function corresponds to an inverse frequency of catagorical attribute values in records of the database and an inverse frequency of numeric attribute values that is determined by considering a frequency of numeric attribute values specified in the given query and nearby numeric attribute values in the database.

6. The method of claim 1 wherein the similarity function ranks a first record having a same similarity score as a second record higher than the second record when values in the first record for attributes that are not specified in said given query occur more frequently in the database than corresponding attribute values in the second record.

7. The method of claim 1 wherein the similarity function includes a cosine similarity between attributes specified in the given query and the database records.

8. The method of claim 1 wherein the similarity function corresponds to a frequency an attribute value is specified in queries in a workload.

9. The method of claim 1 wherein similarity function corresponds to a frequency a catagorical attribute value is specified in queries in a workload and a frequency a numeric attribute value and nearby numeric attribute values are specified in queries in the workload.

10. The method of claim 1 wherein the similarity function assigns an importance weight to an attribute based on a frequency at which the attribute is specified by queries in the workload.

11. The method of claim 1 wherein the similarity function ranks a first record having a same similarity score as a second record higher than the second record when values in the first record for attributes that are not specified in said given query occur more frequently in the workload queries than corresponding attribute values in the second record.

12. The method of claim 1 further comprising filtering the returned records using said given query when a condition of the given query includes an inflexible condition to remove records that do not satisfy the inflexible condition.

13. The method of claim 1 wherein said given query is an inflexible conjunctive condition and the returned records are filtered using said conjunctive condition to remove records that do not satisfy the given query.

14. The method of claim 1 wherein database records and said similarity function are provided to a top-K algorithm that returns a top-K number of records in said ranked order.

15. The method of claim 14 wherein a threshold algorithm is used to return the top-K results.

16. A method for automatically ranking data records in a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) determining a frequency of occurrence of attribute values in the database;

b) ranking records that include attribute values that frequently occur in the database higher than records that include attribute values that occur rarely in the database; and

c) returning the records in a ranked order.

17. A method for automatically ranking data records in a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) determining a frequency of occurrence of attribute values in the given workload;

b) ranking records that include attribute values that frequently occur in the workload higher than records that include attribute values that occur rarely in the workload; and

c) returning the records in a ranked order.

18. A method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) deriving an inverse document frequency similarity function from the data records in a database;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

19. A method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) deriving a query frequency similarity function from the queries in the workload;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

20. A method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) deriving a similarity function that corresponds to an inverse frequency of attribute values in records of the database and a frequency an attribute value is specified in queries in a workload;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

21. A computer readable medium having computer executable instructions stored thereon for performing a method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) deriving a similarity function from at least one of data in a database and a workload of queries;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

22. The computer readable medium of claim 21 wherein said similarity function is derived only from at least one of data in said database and and said workload of queries.

23. The computer readable medium of claim 21 wherein said given query is a conjunctive condition.

24. The computer readable medium of claim 21 wherein the similarity function corresponds to an inverse frequency of attribute values in records of the database.

25. The computer readable medium of claim 21 wherein the similarity function corresponds to an inverse frequency of catagorical attribute values in records of the database and an inverse frequency of numeric attribute values that is determined by considering a frequency of numeric attribute values specified in the given query and nearby numeric attribute values in the database.

26. The computer readable medium of claim 21 wherein the similarity function ranks a first record having a same similarity score as a second record higher than the second record when values in the first record for attributes that are not specified in said given query occur more frequently in the database than corresponding attribute values in the second record.

27. The computer readable medium of claim 21 wherein the similarity function includes a cosine similarity between attributes specified in the given query and the database records.

28. The computer readable medium of claim 21 wherein the similarity function corresponds to a frequency an attribute value is specified in queries in a workload.

29. The computer readable medium of claim 21 wherein similarity function corresponds to a frequency a catagorical attribute value is specified in queries in a workload and a frequency a numeric attribute value and nearby numeric attribute values are specified in queries in the workload.

30. The computer readable medium of claim 21 wherein the similarity function assigns an importance weight to an attribute based on a frequency at which the attribute is specified by queries in the workload.

31. The computer readable medium of claim 21 wherein the similarity function ranks a first record having a same similarity score as a second record higher than the second record when values in the first record for attributes that are not specified in said given query occur more frequently in the workload queries than corresponding attribute values in the second record.

32. The computer readable medium of claim 21 further comprising filtering the returned records using said given query when a condition of the given query includes an inflexible condition to remove records that do not satisfy the inflexible condition.

33. The computer readable medium of claim 21 wherein said given query is an inflexible conjunctive condition and the returned records are filtered using said conjunctive condition to remove records that do not satisfy the given query.

34. The computer readable medium of claim 21 wherein database records and said similarity function are provided to a top-K algorithm that returns a top-K number of records in said ranked order.

35. The computer readable medium of claim 34 wherein a threshold algorithm is used to return the top-K results.

36. A computer readable medium having computer executable instructions stored thereon for performing a method of automatically ranking data records in a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) determining a frequency of occurrence of attribute values in the database;

b) ranking records that include attribute values that frequently occur in the database higher than records that include attribute values that occur rarely in the database; and

c) returning the records in a ranked order.

37. A computer readable medium having computer executable instructions stored thereon for performing a method for automatically ranking data records in a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) determining a frequency of occurrence of attribute values in the given workload;

b) ranking records that include attribute values that frequently occur in the workload higher than records that include attribute values that occur rarely in the workload; and

c) returning the records in a ranked order.

38. A computer readable medium having computer executable instructions stored thereon for performing, a method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, the method comprising:

a) deriving an inverse document frequency similarity function from the data records in a database;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

39. A computer readable medium having computer executable instructions stored thereon for performing, a method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) deriving a query frequency similarity function from the queries in the workload;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.

40. A computer readable medium having computer executable instructions stored thereon for performing a method for automatically ranking data records by relevance to a query on a database wherein the database has data records arranged in one or more database tables, and wherein the database has a given workload comprising a set of queries, the method comprising:

a) deriving a similarity function that corresponds to an inverse frequency of attribute values in records of the database and a frequency an attribute value is specified in queries in a workload;

b) applying the similarity function to a given query and records in the database to determine a similarity between the given query and said records;

c) ranking said records based on said similarity between said given query and said records; and

d) returning said records in a ranked order.