Method and apparatus for learning probabilistic relational models having attribute and link uncertainty and for performing selectivity estimation using probabilistic relational models

• US 20020103793A1
• Filed: 08/02/2001
• Published: 08/01/2002
• Est. Priority Date: 08/02/2000
• Status: Abandoned Application

• Current Assignee: Hebrew University of Jerusalem, Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Koller, Daphne, Friedman, Nir, Taskar, Ben, Getoor, Lise, Pfeffer, Avi
• Application Number:
  US09/922,324
• Publication Number:
  US 20020103793A1
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

The invention comprises a method and apparatus for learning probabilistic models (PRM'"'"'s) with attribute uncertainty. A PRM with attribute uncertainty defines a probability distribution over instantiations of a database. A learned PRM is useful for discovering interesting patterns and dependencies in the data. Unlike many existing techniques, the process is data-driven rather than hypothesis driven. This makes the technique particularly well-suited for exploratory data analysis. In addition, the invention comprises a method and apparatus for handling link uncertainty in PRM'"'"'s. Link uncertainty is uncertainty over which entities are related in our domain. The invention comprises of two mechanisms for modeling link uncertainty: reference uncertainty and existence uncertainty. The invention includes learning algorithms for each form of link uncertainty. The third component of the invention is a technique for performing database selectivity estimation using probabilistic relational models. The invention provides a unified framework for the estimation of query result size for a broad class of queries involving both select and join operations. A single learned model can be used to efficiently estimate query result sizes for a wide collection of potential queries across multiple tables.

Claims

1. A method for estimating the selectivity of queries in a relational database, comprising the steps of:

constructing a probabilistic relational model (PRM) from said database; and

performing online selectivity estimation for a particular query.

2. The method of claim 1, wherein said PRM is constructed automatically, based solely on a data and space allocated to said PRM.

3. The method of claim 1, wherein said selectivity estimation step further comprises the step of:

said selectivity estimator receiving as inputs both said query and said PRM, and outputting an estimate for a result size of said query.

4. The method of claim 1, wherein the same PRM is used to estimate the size of a query over any subset of attributes in said database;

and wherein prior information about a query workload is not required.

5. The method of claim 1, wherein selectivity estimation is performed for select queries over a single table;

and wherein a Bayesian network is used to approximate joint distribution over an entire set of attributes in said table.

6. The method of claim 1, wherein selectivity estimation is performed for queries over multiple tables;

and wherein one or more PRMs are used to accomplish both select and join selectivity estimation in a single framework.

7. The method of claim 1, further comprising the step of:

learning PRMs with link uncertainty with a heuristic search algorithm.

8. The method of claim 7, wherein said search algorithm comprises a greedy hill-climbing search, using random restarts to escape local maxima.

9. A method for learning probabalistic relational models (PRM) having attribute uncertainty, comprising the steps of:

providing a parameter estimation task by;

inputting a relational schema that specifies a set of classes, having attributes associated with said classes and having relationships between objects in different classes;

providing a fully specified instance of said schema in the form of a training database; and

performing a structure learning task to extract an entire PRM solely from said training database.

10. The method of claim 9, said structure learning task comprising the step of specifying which structures are candidate hypotheses.

11. The method of claim 10, said structure learning task comprising the step of evaluating different candidate hypotheses relative to input data.

12. The method of claim 11, said structure learning task comprising the step of searching hypothesis space for a structure having a high score.

14. The method of claim 10, said mechanism comprising:

let μ

be a particular instantiation of Pa(X.E);

to compute C_X.E[true,μ

], use a standard database query to compute how many objects xε

O^σ

(X) have Pa(x.E);

to compute C_X.E[false,μ

], compute the number of potential entities without explicitly considering each (x₁, . . . , x_k)ε

O^I(Y₁)x·

·

·

O^I(Y_k) by decomposing the computation as follows;

let ρ

be a reference slot of X with Range[ρ

]=Y;

let Pa(X.E) be the subset of parents of X.E along slot ρ

; and

let μ

_ρ

be a corresponding instantiation;

count a number of y consistent with μ

_ρ

;

if Pa_ρ

(X.E) is empty, this count is the |O^I(Y)|;

wherein the product of these counts is the number of potential entities;

to compute C_X.E[false,μ

], subtract C_XE[true,μ

] from said number.

13. A method for learning probabalistic relational models having link uncertainty, comprising the steps of:

providing a mechanism for modeling link uncertainty; and

said mechanism computing sufficient statistics that include existence attributes without adding all nonexistent entities into a database.

15. A method for learning probabalistic relational models having link uncertainty, comprising the steps of:

providing a mechanism for modeling, link uncertainty; and

said mechanism computing sufficient statistics that include reference uncertainty, comprising the steps of;

fixing a set partition attributes ψ

[ρ

]; and

treating a variable S_ρ

as any other attribute in a PRM;

wherein scoring success in predicting a value of said attribute given a value of its parents is performed using standard Bayesian methods.