\relax \citation{Grae93} \citation{Bato88a} \citation{Grae87b} \citation{Haas88} \citation{Ston86b} \citation{Haas88,Frey87a,Grae87b,Grae90b} \citation{Haas88} \citation{Grae90b} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {1}Introduction}{1}} \newlabel{sec:intro}{{1}{1}} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {2}Prairie: A language for rule specification}{2}} \newlabel{sec:framework}{{2}{2}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {2.1}Notation and assumptions}{2}} \newlabel{sec:notation}{{2.1}{2}} \@writefile{toc}{\protect \contentsline {paragraph}{Stored Files and Streams.}{2}} \@writefile{toc}{\protect \contentsline {paragraph}{Database Operations.}{2}} \@writefile{toc}{\protect \contentsline {paragraph}{Operator Trees.}{2}} \citation{Seli79} \citation{Dani82} \citation{Grae90b} \@writefile{lot}{\protect \contentsline {table}{\protect \numberline {1}{\ignorespaces Operators and algorithms in a centralized query optimizer and their additional parameters}}{3}} \newlabel{tab:operators}{{1}{3}} \@writefile{lot}{\protect \contentsline {table}{\protect \numberline {2}{\ignorespaces Properties of nodes in an operator tree}}{3}} \newlabel{tab:annotations}{{2}{3}} \newlabel{fig:optreeexample}{{1(a)}{3}} \newlabel{fig:accplanexample}{{1(b)}{3}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {1}{\ignorespaces Example of an operator tree and access plan}}{3}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{1(a)}{\ignorespaces An expression and its corresponding operator tree}}{3}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{1(b)}{\ignorespaces Possible access plan for operator tree in (a)}}{3}} \newlabel{fig:expexample}{{1}{3}} \@writefile{toc}{\protect \contentsline {paragraph}{Descriptors.}{3}} \@writefile{toc}{\protect \contentsline {paragraph}{Access Plans.}{3}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {2.2}Prairie optimization paradigm}{3}} \newlabel{sec:topdown}{{2.2}{3}} \newlabel{eq:generaltrule}{{1}{4}} \newlabel{fig:generaltrule}{{2(a)}{4}} \newlabel{eq:associativity}{{2}{4}} \newlabel{fig:associativity}{{2(b)}{4}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {2}{\ignorespaces T-rule}}{4}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{2(a)}{\ignorespaces General form of a T-rule}}{4}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{2(b)}{\ignorespaces Join associativity}}{4}} \newlabel{fig:trules}{{2}{4}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {2.3}Transformation rules}{4}} \newlabel{sec:trules}{{2.3}{4}} \newlabel{eq:generalirule}{{3}{4}} \newlabel{fig:generalirule}{{3(a)}{4}} \newlabel{eq:msort}{{4}{4}} \newlabel{fig:msort}{{3(b)}{4}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {3}{\ignorespaces I-rule}}{4}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{3(a)}{\ignorespaces General form of an I-rule}}{4}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{3(b)}{\ignorespaces Merge-sort sort algorithm}}{4}} \newlabel{fig:irules}{{3}{4}} \newlabel{ex:joinassociativity}{{4.}{4}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {2.4}Implementation rules}{4}} \newlabel{sec:irules}{{2.4}{4}} \citation{Das94} \newlabel{ex:mergesort}{{5.}{5}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {2.5}Null algorithm}{5}} \newlabel{sec:null}{{2.5}{5}} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {3}The P2V pre-processor}{5}} \newlabel{sec:ptov}{{3}{5}} \newlabel{eq:generalnullalg}{{5}{5}} \newlabel{fig:generalnullalg}{{4(a)}{5}} \newlabel{eq:nullsort}{{6}{5}} \newlabel{fig:nullsort}{{4(b)}{5}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {4}{\ignorespaces The ``Null'' algorithm concept}}{5}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{4(a)}{\ignorespaces General form of a ``Null'' I-rule}}{5}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{4(b)}{\ignorespaces Null sort algorithm}}{5}} \newlabel{fig:null}{{4}{5}} \citation{Das93} \citation{Blak93} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {5}{\ignorespaces The Prairie optimizer-generator paradigm. Double-boxed modules represent software generators, shaded boxes represent generated programs. The outermost double-boxed portion denotes the Prairie optimizer generator.}}{6}} \newlabel{fig:ptovmodel}{{5}{6}} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {4}Experimental results}{6}} \newlabel{sec:results}{{4}{6}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {4.1}The Texas Instruments Open OODB query optimizer}{6}} \newlabel{sec:oodb}{{4.1}{6}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {4.2}Programmer productivity}{7}} \newlabel{sec:productivity}{{4.2}{7}} \@writefile{toc}{\protect \contentsline {subsection}{\protect \numberline {4.3}Performance results using the Open OODB optimizer}{7}} \newlabel{sec:oodbexp}{{4.3}{7}} \citation{Seli79} \citation{Dani82} \newlabel{fig:Eone}{{6(a)}{8}} \newlabel{fig:Etwo}{{6(b)}{8}} \newlabel{fig:Ethree}{{6(c)}{8}} \newlabel{fig:Efour}{{6(d)}{8}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {6}{\ignorespaces Expressions used in generating queries for experiments}}{8}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{6(a)}{\ignorespaces E1}}{8}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{6(b)}{\ignorespaces E2}}{8}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{6(c)}{\ignorespaces E3}}{8}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{6(d)}{\ignorespaces E4}}{8}} \newlabel{fig:exps}{{6}{8}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {3}{\ignorespaces Queries used in experiments}}{8}} \newlabel{tab:queries}{{3}{8}} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {5}Related research}{8}} \newlabel{sec:related}{{5}{8}} \citation{Haas88} \citation{Frey87a} \citation{Grae87b} \citation{Grae90b} \newlabel{fig:q1}{{7(a)}{9}} \newlabel{fig:q2}{{7(b)}{9}} \newlabel{fig:q3}{{7(c)}{9}} \newlabel{fig:q4}{{7(d)}{9}} \newlabel{fig:q5}{{7(e)}{9}} \newlabel{fig:q6}{{7(f)}{9}} \newlabel{fig:q7}{{7(g)}{9}} \newlabel{fig:q8}{{7(h)}{9}} \@writefile{lof}{\protect \contentsline {figure}{\protect \numberline {7}{\ignorespaces Query optimization times for Q1 through Q8}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(a)}{\ignorespaces Query 1}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(b)}{\ignorespaces Query 2}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(c)}{\ignorespaces Query 3}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(d)}{\ignorespaces Query 4}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(e)}{\ignorespaces Query 5}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(f)}{\ignorespaces Query 6}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(g)}{\ignorespaces Query 7}}{9}} \@writefile{lof}{\protect \contentsline {subfigure}{\string\numberline{7(h)}{\ignorespaces Query 8}}{9}} \newlabel{fig:e4}{{7}{9}} \@writefile{toc}{\protect \contentsline {section}{\protect \numberline {6}Conclusion and future work}{9}} \newlabel{sec:conclusion}{{6}{9}} \bibstyle{plain} \bibdata{references} \bibcite{Bato88a}{1} \bibcite{Blak93}{2} \bibcite{Dani82}{3} \bibcite{Das93}{4} \bibcite{Das94}{5} \bibcite{Frey87a}{6} \bibcite{Grae90b}{7} \bibcite{Grae93}{8} \bibcite{Grae87b}{9} \bibcite{Haas88}{10} \bibcite{Seli79}{11} \bibcite{Ston86b}{12} \newlabel{sec:acknowledgments}{{6}{10}}