Ranking database query results using probabilistic models from information retrieval

US 7,383,262 B2
Filed: 06/29/2004
Issued: 06/03/2008
Est. Priority Date: 06/29/2004
Status: Expired due to Fees

First Claim

Patent Images

1. A method for ranking results of a present database query comprising:

accessing a specified attribute value from the present database query;

accessing one or more unspecified attribute values from a workload, wherein the workload includes attribute values associated with one or more previous database queries including the specified attribute value;

calculating a global atomic quantity for each of the one or more unspecified attribute values in a database, each global atomic quantity representing an unconditional importance level of its respective unspecified attribute value;

calculating a conditional atomic quantity for each of the one or more unspecified attribute values in the database, each conditional atomic quantity representing a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value; and

ranking result tuples of the present database query based on the global atomic quantities and the conditional atomic quantities, wherein the ranking result tuples comprises;

calculating a conditional score for each tuple in the database;

calculating a global score for each tuple in the data base; and

using conditional scores and global scores, calculating a ranking score for each result tuple of the present database query that includes the specified attribute value;

wherein the calculating a conditional score comprises calculating a conditional score according to;

$CondScore = \frac{\prod_{z \in t} p (x \rangle z, W)}{\prod_{z \in t} p (x \rangle z, D)};$ andwherein the calculating a global score comprises calculating a global score according to;

$GlobScore = \frac{\prod_{z \in t} p (z | W)}{\prod_{z \in t} p (z | D)}$ wherein t is a tuple that contains a specified attribute value from the present database query, x is a specified attribute value from the present database query, z is an unspecified attribute value from the present database query, W is a workload of the database, and D is data in the database.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A system and methods rank results of database queries. An automated approach for ranking database query results is disclosed that leverages data and workload statistics and associations. Ranking functions are based upon the principles of probabilistic models from Information Retrieval that are adapted for structured data. The ranking functions are encoded into an intermediate knowledge representation layer. The system is generic, as the ranking functions can be further customized for different applications. Benefits of the disclosed system and methods include the use of adapted probabilistic information retrieval (PIR) techniques that leverage relational/structured data, such as columns, to provide natural groupings of data values. This permits the inference and use of pair-wise associations between data values across columns, which are usually not possible with text data.

Citations

27 Claims

1. A method for ranking results of a present database query comprising:
- accessing a specified attribute value from the present database query;
  
  accessing one or more unspecified attribute values from a workload, wherein the workload includes attribute values associated with one or more previous database queries including the specified attribute value;
  
  calculating a global atomic quantity for each of the one or more unspecified attribute values in a database, each global atomic quantity representing an unconditional importance level of its respective unspecified attribute value;
  
  calculating a conditional atomic quantity for each of the one or more unspecified attribute values in the database, each conditional atomic quantity representing a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value; and
  
  ranking result tuples of the present database query based on the global atomic quantities and the conditional atomic quantities, wherein the ranking result tuples comprises;
  
  calculating a conditional score for each tuple in the database;
  
  calculating a global score for each tuple in the data base; and
  
  using conditional scores and global scores, calculating a ranking score for each result tuple of the present database query that includes the specified attribute value;
  
  wherein the calculating a conditional score comprises calculating a conditional score according to;
  
  $CondScore = \frac{\prod_{z \in t} p (x \rangle z, W)}{\prod_{z \in t} p (x \rangle z, D)};$ andwherein the calculating a global score comprises calculating a global score according to;
  
  $GlobScore = \frac{\prod_{z \in t} p (z | W)}{\prod_{z \in t} p (z | D)}$ wherein t is a tuple that contains a specified attribute value from the present database query, x is a specified attribute value from the present database query, z is an unspecified attribute value from the present database query, W is a workload of the database, and D is data in the database.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
- - 2. The method as recited in claim 1, wherein the calculating a global atomic quantity is selected from the group comprising:
    - calculating a database global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the database; and
      
      calculating a workload global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the workload.
  - 3. The method as recited in claim 1, wherein the calculating a conditional atomic quantity is selected from the group comprising:
    - calculating a database conditional atomic quantity that represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the database; and
      
      calculating a workload conditional atomic quantity that represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the workload.
  - 4. The method as recited in claim 1, further comprising:
    - building a conditional list of all tuples in the database and ordering tuples in the conditional list by descending conditional scores; and
      
      building a global list of all tuples in the database and ordering tuples in the global list by descending global scores.
  - 5. The method as recited in claim 4, wherein calculating a ranking score for a result tuple comprises:
    - retrieving a conditional score for the result tuple from the conditional list;
      
      retrieving a global score for the result tuple form the global list; and
      
      multiplying the global score and the conditional score.
  - 6. The method as recited in claim 1, wherein the calculating a ranking score comprises calculating a ranking score according to:
7. The method as recited in claim 4, further comprising:
- maintaining the conditional list and the global list in database tables; and
  
  enabling retrieval of tuples from the database tables through indexes in the database tables.
8. The method as recited in claim 7, wherein the enabling retrieval includes enabling retrieval of tuples one-by-one in order of decreasing score and enabling retrieval of tuples by random access.
9. The method as recited in claim 4, wherein:
- building a conditional list comprises creating a conditional list table that includes an attribute name column, an attribute value column, a tuple identification column, and a conditional score column; and
  
  whereinbuilding a global list comprises creating a global list table that includes an attribute name column, an attribute value column, a tuple identification column, and a global score column.

10. One or more computer-readable storage media storing computer-executable instructions that, when executed on one or more processors, perform a method for ranking results of a present database query, the method comprising:
- accessing a specified attribute value from the present database query;
  
  accessing one or more unspecified attribute values from a workload, wherein the workload includes attribute values associated with one or more previous database queries including the specified attribute value;
  
  calculating a global atomic quantity for each of the one or more unspecified attribute values in a database, each global atomic quantity representing an unconditional importance level of its respective unspecified attribute value;
  
  calculating a conditional atomic quantity for each of the one or more unspecified attribute values in the database, each conditional atomic quantity representing a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value; and
  
  ranking result tuples of the present database query based on the global atomic quantities and the conditional atomic quantities, wherein the ranking result tuples comprises;
  
  calculating a conditional score for each tuple in the database;
  
  calculating a global score for each tuple in the database; and
  
  using conditional scores and global scores, calculating a ranking score for each result tuple of the present database query that includes the specified attribute value;
  
  wherein the calculating a conditional score comprises calculating a conditional score according to;
  
  $CondScore = \frac{\prod_{z \in t} p (x \rangle z, W)}{\prod_{z \in t} p (x \rangle z, D)};$ andwherein the calculating a global score comprises calculating a global score according to;
  
  $GlobScore = \frac{\prod_{z \in t} p (z | W)}{\prod_{z \in t} p (z | D)}$ wherein t is a tuple that contains a specified attribute value from the present database query, x is a specified attribute value from the present database query, z is an unspecified attribute value from the present database query, W is a workload of the database, and D is data in the database.
- View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 25, 26, 27)
- - 11. The one or more computer-readable storage media as recited in claim 10, wherein the calculating a global atomic quantity is selected from the group comprising:
    - calculating a database global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the database; and
      
      calculating a workload global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the workload.
  - 12. The one or more computer-readable storage media as recited in claim 10, wherein the calculating a conditional atomic quantity is selected from the group comprising:
    - calculating a database conditional atomic quantity that represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the database; and
      
      calculating a workload conditional atomic quantity tat represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the workload.
  - 13. The one or more computer-readable storage media as recited in claim 10, wherein the one or more computer-readable storage media further store computer-executable instructions for:
    - building a conditional list of all tuples in the database and ordering tuples in the conditional list by descending conditional scores; and
      
      building a global list of all tuples in the database and ordering tuples in the global list by descending global scores.
  - 14. The one or more computer-readable storage media as recited in claim 13, wherein calculating a ranking score for a result tuple comprises:
    - retrieving a conditional score for the result tuple from the conditional list;
      
      retrieving a global score for the result tuple form the global list; and
      
      multiplying the global score and the conditional score.
  - 15. The one or more computer-readable storage media as recited in claim 10, wherein the calculating a ranking score comprises calculating a ranking score according to:
16. The one or more computer-readable storage media as recited in claim 13, wherein the one or more computer-readable storage media further store computer-executable instructions for:
- maintaining the conditional list and the global list in database tables; and
  
  enabling retrieval of tuples from the database tables through indexes in the database tables.
17. The one or more computer-readable storage media as recited in claim 16, wherein the enabling retrieval includes enabling retrieval of tuples one-by-one in order of decreasing score and enabling retrieval of tuples by random access.
18. The one or more computer-readable storage media as recited in claim 13, wherein:
- building a conditional list comprises creating a conditional list table that includes an attribute name column, an attribute value column, a tuple identification column, and a conditional score column; and
  
  whereinbuilding a global list comprises creating a global list table that includes an attribute name column, an attribute value column, a tuple identification column, and a global score column.
22. The system as recited in claim 10, wherein the one or more computer-readable storage media further store computer-executable instructions for:
- building a conditional list of all tuples in the database and ordering tuples in the conditional list by descending conditional scores; and
  
  building a global list of all tuples in the database and ordering tuples in the global list by descending global scores.
23. The system as recited in claim 22, wherein calculating a ranking score for a result tuple comprises:
- retrieving a conditional score for the result tuple from the conditional list;
  
  retrieving a global score for the result tuple form the global list; and
  
  multiplying the global score and the conditional score.
25. The system as recited in claim 22, wherein the one or more computer-readable storage media further store computer-executable instructions for:
- maintaining the conditional list and the global list in database tables; and
  
  enabling retrieval of tuples from the database tables through indexes in the database tables.
26. The system as recited in claim 25, wherein the enabling retrieval includes enabling retrieval of tuples one-by-one in order of decreasing score and enabling retrieval of tuples by random access.
27. The system as recited in claim 22, wherein:
- building a conditional list comprises creating a conditional list table that includes an attribute name column, an attribute value column, a tuple identification column, and a conditional score column; and
  
  whereinbuilding a global list comprises creating a global list table that includes an attribute name column, an attribute value column, a tuple identification column, and a global score column.

19. A system comprising:
- one or more processors; and
  
  one or more computer-readable storage media storing computer-executable instructions that, when executed on the one or more processors, perform a method for ranking results of a present database query, the method comprising;
  
  accessing a specified attribute value from the present database query;
  
  accessing one or more unspecified attribute values from a workload, wherein the workload includes attribute values associated with one or more previous database queries including the specified attribute value;
  
  calculating a global atomic quantity for each of the one or more unspecified attribute values in a database, each global atomic quantity representing an unconditional importance level of its respective unspecified attribute value;
  
  calculating a conditional atomic quantity for each of the one or more unspecified attribute values in the database, each conditional atomic quantity representing a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value; and
  
  ranking result tuples of the present database query based on the global atomic quantities and the conditional atomic quantities, wherein the ranking result tuples comprises;
  
  calculating a conditional score for each tuple in the database;
  
  calculating a global score for each tuple in the database; and
  
  using conditional scores and global scores, calculating a ranking score for each result tuple of the present database query that includes the specified attribute value;
  
  wherein the calculating a conditional score comprises calculating a conditional score according to;
  
  $CondScore = \frac{\prod_{z \in t} p (x \rangle z, W)}{\prod_{z \in t} p (x \rangle z, D)};$ andwherein the calculating a global score comprises calculating a global score according to;
  
  $GlobScore = \frac{\prod_{z \in t} p (z | W)}{\prod_{z \in t} p (z | D)}$ wherein t is a tuple that contains a specified attribute value from the present database query, x is a specified attribute value from the present database query, z is an unspecified attribute value from the present database query, W is a workload of the database, and D is data in the database.
- View Dependent Claims (20, 21, 24)
- - 20. The system as recited in claim 19, wherein the calculating a global atomic quantity is selected from the group comprising:
    - calculating a database global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the database; and
      
      calculating a workload global atomic quantity that represents a frequency of occurrence of an unspecified attribute value within the workload.
  - 21. The system as recited in claim 19, wherein the calculating a conditional atomic quantity is selected from the group comprising:
    - calculating a database conditional atomic quantity that represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the database; and
      
      calculating a workload conditional atomic quantity that represents a conditional importance level of an association between each of the one or more unspecified attribute values and the specified attribute value within the workload.
  - 24. The system as recited in claim 19, wherein the calculating a ranking score comprises calculating a ranking score according to:

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Microsoft Technology Licensing LLC (Microsoft Corporation)
Original Assignee
Microsoft Corporation
Inventors
Das, Gautam, Weikum, Gerhard, Hristidis, Vagelis, Chaudhuri, Surajit
Primary Examiner(s)
Vo; Tim
Assistant Examiner(s)
SANDERS, AARON J

Application Number

US10/879,450
Publication Number

US 20050289102A1
Time in Patent Office

1,435 Days
Field of Search

707/3
US Class Current

1/1
CPC Class Codes

G06Q 30/0603 Catalogue ordering

G06Q 50/16 Real estate

Ranking database query results using probabilistic models from information retrieval

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

Citations

27 Claims

Specification

Solutions

Use Cases

Quick Links

Ranking database query results using probabilistic models from information retrieval

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

Citations

27 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links