<reponame>codeaudit/imputedb
\section{Motivating Example}
An epidemiologist at the CDC is tasked with an 
exploratory analysis of data collected from individuals across
a battery of exams. In particular, she is interested in exploring
the relationship between income and the immune system,
controlling for factors such as weight and gender.

The epidemiologist is excited
to get a quick and accurate view into the data. However,
the data has been collected through CDC surveys (see~\Cref{subsec:datasets}),
and there is a significant amount of missing data across all
relevant attributes. 

Before she can perform her queries, the epidemiologist must develop a strategy
for handling missing values. She currently has two options:
(1) she could drop records that have missing values in relevant fields,
(2) she could use a traditional imputation package on her entire dataset. Both of these
approaches have significant drawbacks. For the query pictured in~\Cref{fig:example-query}, 
(1) drops 1492 potentially relevant tuples,
while from her experience, (2) has proven to take too long. The epidemiologist needs a more complete picture
of the data, so (1) is insufficient, and for this quick exploratory analysis, (2)
is infeasible.

She can run her queries immediately and finish her report if
she uses \ProjectName{}, which takes standard SQL and automatically performs the imputations
necessary to fill in the missing data.
An example query is shown in~\Cref{fig:example-query}.

\begin{figure}
  \captionsetup{labelfont=bf}
\begin{lstlisting}[language=SQL]
SELECT income, AVG(white_blood_cell_ct)
FROM demo, exams, labs
WHERE gender = 2 AND 
      weight >= 120 AND
      demo.id = exams.id AND 
      exams.id = labs.id
GROUP BY demo.income
\end{lstlisting}
\caption{A typical public health query on CDC's NHANES data.}
\label{fig:example-query}
\end{figure}

\begin{figure}
  \captionsetup{labelfont=bf}
  \begin{subfigure}{\columnwidth}
    \Tree
  [.$\pi_{\text{income, AVG(white\_blood\_cell\_ct)}}$
    [.$g_{\text{income, AVG(white\_blood\_cell\_ct)}}$
      [.\colorbox{pink}{$\mu_{\text{demo.income}}$}
        [.$\bowtie_{\text{exams.id} = \text{demo.id}}$
          [.\colorbox{pink}{$\mu_{\text{labs.white\_blood\_cell\_ct}}$}
            [.$\bowtie_{\text{exams.id} = \text{labs.id}}$
              [.$\sigma_{\text{exams.weight} \geq 120}$ 
                [.\colorbox{pink}{$\mu_{\text{exams.weight}}$} exams ] 
              ] 
              labs 
            ]
          ]
        [.$\sigma_{\text{demo.gender} = 2}$ demo ]
      ] 
    ] 
  ] 
  ]
  \caption{A quality-optimized plan for the query in~\Cref{fig:example-query}.}
\label{fig:quality-plan}
\end{subfigure}
  \begin{subfigure}{\columnwidth}
\vspace{1em}
\Tree
  [.$\pi_{\text{income, AVG(white\_blood\_cell\_ct)}}$
    [.$g_{\text{income, AVG(white\_blood\_cell\_ct)}}$
      [.\colorbox{pink}{$\delta_{\text{demo.income, labs.white\_blood\_cell\_ct}}$}
        [.$\bowtie_{\text{exams.id} = \text{labs.id}}$
          [.$\bowtie_{\text{demo.id} = \text{exams.id}}$
            [.$\sigma_{\text{demo.gender} = 2}$ demo ]
            [.$\sigma_{\text{exams.weight} \geq 120}$ [.\colorbox{pink}{$\delta_{\text{exams.weight}}$} exams ] ] ] labs ] ] ] ]
\caption{A performance-optimized plan for the query in~\Cref{fig:example-query}.}
\label{fig:fast-plan}
\end{subfigure}
\vspace{1em}

\caption{The operators $\sigma$, $\pi$, $\bowtie$, and $g$ are the standard relational selection, projection, join, and group-by/aggregate, $\mu$ and $\delta$ are specialized imputation operators (\Cref{sec:operators}), and
can be mixed throughout a plan. The imputation operators are highlighted.}
\label{fig:example-plans}
\end{figure}

\subsection{Planning with \ProjectName{}}
The search space contains plans with varying performance and imputation quality
characteristics, as a product of the multiple possible locations for imputation.
The user can influence the final plan selected by \ProjectName{}
through a trade-off parameter $\alpha \in [0, 1]$, where low $\alpha$ 
prioritizes the quality of the query results and high $\alpha$ prioritizes performance.

For the query in~\Cref{fig:example-query}, \ProjectName{} generates
several plans on an optimal frontier. \Cref{fig:quality-plan} shows a quality-optimized plan that uses the \textit{Impute} operator $\mu$,
which employs a reference imputation strategy to fill in missing values rather than dropping tuples.
It waits to impute \verb|demo.income| until after the final join has taken place, though other imputations take place earlier on in the plan, some before filtering and join operations.
Imputations are placed to maximize ImputeDB's estimate of the quality of the overall results.
On the other hand, \Cref{fig:fast-plan} shows a performance-optimized plan that uses the \textit{Drop} operator $\delta$ instead of filling in missing values.
However, it is a significant improvement over dropping all tuples with missing data in any field, as it only drops tuples with missing values in attributes which are referenced by the rest of the plan. In both cases, only performing
imputation on the necessary data yields a query that is much faster
than performing imputation on the whole dataset and then executing
the query.

\subsection{\ProjectName{} Workflow}
Now that the epidemiologist has \ProjectName{}, she can explore
the dataset using SQL. She begins by choosing a value for $\alpha$ and can adjust it up or
down until she is satisfied with her query runtime. This iterative approach gives her 
immediate feedback.

\review{
As an alternative strategy, the analyst can start by executing her query with $\alpha=1$ and
incrementally reducing $\alpha$, as long as execution of the query completes acceptably quickly.
\ProjectName{}'s planning algorithm can also produce a set of plans with optimal
time-quality trade-offs, which allows the user to adjust her choice of $\alpha$ to select from these plans.
}

Tens of queries later, our epidemiologist has a holistic view of the data and she has the information that she needs to construct a tailored imputation model for her queries of interest.

%This approach allows her to maximize the query result quality, while
%maintaining an acceptable runtime.
%
%%She indicates her preference for performance or for accuracy by providing a configuration parameter $\alpha$ to ImputeDB in addition to her query.
%%$\alpha$ is a dimensionless parameter in $[0,1]$, and it indicates the relative importance of the quality of query results and of query performance.
%So, a high $\alpha$ results in a fast query plan that may compromise accuracy, while a low $\alpha$ results in a high quality query plan that may take longer to run.
%In our intended workflow, the analyst picks a value of $\alpha$ and incrementally increases it to increase query result quality until the query takes too long to run.
%Fig.~\ref{fig:quality-plan} and Fig.~\ref{fig:fast-plan} show plans for the example query in Fig.~\ref{fig:example-query} when optimizing for quality and performance, respectively.

%1 - How great life is with the project
% - intended work flow



%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End:
