\section{Introduction} \label{sec:intro} Query optimization \cite{Grae93} is a fundamental part of database systems. It is the process of generating an efficient access plan for a database query. Informally, an access plan is an execution strategy for a query; it is the sequence of low-level database retrieval operations that, when executed, produce the database records that satisfy the query. There are three basic aspects that define and influence query optimization: the search space, the cost model, and the search strategy. The {\em search space} is the set of logically equivalent access plans that can be used to evaluate a query. All plans in a query's search space return the same result; however, some plans are more efficient than others. The {\em cost model} assigns a cost to each plan in the search space. The cost of a plan is an estimate of the resources used when the plan is executed; the lower the cost, the better the plan. The {\em search strategy} is a specification of which plans in the search space are to be examined. Traditionally, query optimizers have been built as monolithic subsystems of a DBMS. This simply reflects the fact that traditional database systems are themselves monolithic: the algorithms used for storing and retrieving data are hard-wired and are rather difficult to change. The need to have extensible database systems, and in turn extensible optimizers, has long been recognized in systems like Genesis \cite{Bato88a}, EXODUS \cite{Grae87b}, Starburst \cite{Haas88}, and Postgres \cite{Ston86b}. Rule-based query optimizers are among the major conceptual advances that have been proposed to deal with query optimizer extensibility \cite{Haas88,Frey87a,Grae87b,Grae90b}. The extensibility translates into the ability to incorporate new operators, algorithms, cost models, or search strategies without changing the optimization algorithm. In this paper, we describe an algebraic framework called \emph{Prairie} for specifying rules in a rule-based query optimizer. Prairie is similar to other rule specification languages like Starburst \cite{Haas88} and Volcano \cite{Grae90b}, and indeed, we have based our work on Volcano to capture most of the advantages of rule-based optimizers. However, Prairie attempts to provide some key features that, we have found, simplify the effort in writing rules: \begin{enumerate} \item A framework in which users can define a query optimizer concisely in terms of a well-defined set of operators and algorithms. \emph{All} operators and algorithms are considered first-class objects, \ie \emph{any} of them can occur in any rule, and \emph{only} these operators and algorithms can appear in rules. This scheme eliminates the need for special classes of operators and algorithms, such as enforcers in Volcano and glue in Starburst, that significantly complicate rule specification. \item A framework in which users can define a list of properties to characterize the expressions generated in the optimization process. Again, the goal here is to allow the user to treat \emph{all} properties as having equal status. This is different from Volcano where the user must classify properties as logical, physical, or operator/algorithm arguments. \item A framework in which users can specify mapping functions between properties concomitantly with the corresponding rules. This contrasts with existing approaches in which mappings between properties are fragmented into multiple functions and at logically different places than the corresponding rules. Research into rule-based optimizers has revealed that property-mapping functions are a major source of user effort, so this is an important goal. \item The format (Prairie) in which users can cleanly specify rules is not necessarily the same format needed for generating efficient optimizers. Thus, there is a need for a pre-processor (written by us) that translates between these competing representations. \end{enumerate} Prairie strives for uniformity in dealing with issues that have been a source of most user effort and potential user errors. In the following sections, we present the Prairie framework. We explain how our P2V pre-processor maps Prairie rule specifications into Volcano rule specifications that can be processed efficiently. Experimental results to support this claim are given in Section~\ref{sec:results}, where we compare implementations of the Texas Instruments Open OODB query optimizer using both Prairie and Volcano. We conclude with a summary and related research.