Browse Prior Art Database

Selecting Algorithms in the Presence of Uncertainty

IP.com Disclosure Number: IPCOM000114452D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 2 page(s) / 51K

Publishing Venue

IBM

Related People

Seppi, KD: AUTHOR

Abstract

Disclosed is a method for selecting algorithms for execution in database management systems for the evaluation of user generated queries.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 58% of the total text.

Selecting Algorithms in the Presence of Uncertainty

      Disclosed is a method for selecting algorithms for execution in
database management systems for the evaluation of user generated
queries.

      Database management systems typically include a query optimizer
component.  The optimizer examines queries submitted by users to
determine the most efficient execution strategy.  Using summary
statistics from the database to be queried (or other imprecise
information) and cost models, the query optimizer can estimate the
execution cost for each potential execution strategy and then select
the
strategy with the lowest expected cost.  By using imprecise
information
the decision process within the optimizer is subject to error.

      Bayesian Decision Theory allows this error to be analyzed in a
structured process.  The cost models used in the optimizer can be
inverted and used as utility functions.  The input information can be
structured as a Bayesian prior distribution.  Since the optimizer has
at its disposal the database to which the query applies, more exact
information could be gathered and used as input to the cost models.
The value of obtaining more exact information can be ascertained
using a Bayesian approach called "pre-posterior" analysis (1).  The
result of pre-posterior analysis is the expected value (in the same
units as the utility functions) of acquiring additional information.
Since this analysis can be done BEFORE this additional informat...