Estimating the result size of complex queries that involve selection on
multiple attributes and the join of several relations is a difficult but
fundamental task in database query processing.  It arises in cost-based
query optimization, query profiling, and approximate query answering.
In this paper, we show how probabilistic graphical models can be effectively
used for this task as an accurate and compact approximation of the joint
frequency distribution of multiple attributes across multiple relations. 
<I>Probabilistic Relational Models (PRMs)</I> are a recent development that
extends graphical statistical models such as Bayesian Networks to relational
domains.  They represent the statistical dependencies between attributes
within a table, and between attributes across foreign-key joins.  We provide
an efficient algorithm for constructing a PRM from a database, and show how
a PRM can be used to compute selectivity estimates for a broad class of
queries.  One of the major contributions of this work is a unified framework
for the estimation of queries involving both select and foreign-key join
operations. Furthermore, our approach is not limited to answering a
small set of predetermined queries; a single model can be used to
effectively estimate the sizes of a wide collection of potential
queries across multiple tables.  We present results for our approach on
several real-world databases.  For both single-table multi-attribute queries
and a general class of select-join queries, our approach produces more
accurate estimates than standard approaches to selectivity estimation,
using comparable space and time.  
<p>