
\section{VCA for Hierarchical Data}

This section extends statistical and union composition to hierarchy-aware comparisons.
Given two views $V_1=R_1(Q_1(D))$ and $V_2=R_2(Q_2(D))$ and a hierarchy $H$,
we will define the semantics for statistical composition $\odot$ and union composition $\cup$.

Our examples will be based on the visualizations in \Cref{f:calendar}, which builds on the hierarchy and data in \Cref{f:hierarchy}.  The calendar chart renders daily profits over all geographies and products, while the bar chart renders average monthly profits for toy products.    The goal is to define composition for any combination of comparisons between  visualization's labeled subviews (\circled{1} to \circled{4}).


\begin{figure}[htpb]
  \centering
  \includegraphics[width=.85\columnwidth]{figs/calendar}
  \caption{A hierarchical calendar visualization that renders daily profits, and a bar chart that renders average monthly profits.   All labeled subviews correspond to hierarchy levels that are comparable in \sysh. }
  \label{f:calendar}
\end{figure}


\subsection{Safety}

To begin, we must extend \sys's safety rules to allow hierarchy-aware comparisons.
For space constraints, we focus on the case where both view's schemas ($A_1$, $A_2$) have the same number of dimensions,
as this is the core challenge.

$A_1$ and $A_2$ are safe to compose if there exists a bijective mapping:
$$\{ (a_i,a_j)  | a_i\in A_1, a_j\in A_2, a_i=a_j \lor \red{a_i\mapsto_H a_j \lor a_j\mapsto_H a_i} \}$$
Where $a_i\mapsto a_j$ given a directed path from $a_i$ to $a_j$ in $H$.
This relaxes \sys's rules so $a_i$ can map to $a_j$ if one is an ancestor of the other.


We also define $a_i{\sim}a_j$ to denote that the value of $a_i$ (e.g., "California") functionally determines $a_j$ (e.g., "USA") or vice versa.
If $a_i\mapsto a_j$, we can translate $a_i$ into $a_j$.
Consider $block\mapsto nation$ in \Cref{f:hierarchy}. We can translate block 1 to ``USA'' by 
joining $T_2$ and $T_3$ so that both attributes are in the same table, and then simply lookup 
the \texttt{Nation} attribute value.


\subsection{Statistical Composition $\odot$}

In \sys, $V^*=V_1\odot_{op} V_2$ matches rows in $Q_1$ and $Q_2$ using a join and computes a new measure $Q_1.y\ op\ Q_2.y$.  Extending $\odot$ to hierarchical data presents two challenges.  

First, it potentially requires reaggregating data in one of the views in order to compute the new measure.  
For instance, \circled{4}$\ominus$\circled{3} in \Cref{f:calendar}, which computes the difference between average monthly toy profits and overall daily profits.  The views are safe to compare, because \texttt{day}$\mapsto$\texttt{month}. However, we need to reaggregate the daily profits to the month granularity, and the specific aggregation function may depend on the application needs.    
For this reason, we extend statistical composition $\odot_{op,reagg}$ to take an additional $reagg()$ parameter for reaggregation.
$reagg$ defaults to $Q_2$'s aggregation function if not specified (e.g., $\odot_{op}$, $\ominus$).

Second, $\odot$ is asymmetric, and reaggregation is not always necessary nor desired.  
For instance, \circled{3}$\ominus$\circled{4} subtracts e.g., March's profits from each day's profits in March.   

For these reasons, we define $\odot_{op,reagg}$ under two cases based on whether or not reaggregation is required.
To simplify the discussion, we assume that $A_1$ is identical to $A_2$, except for a single pair of attributes $a_1\in A_1$ and $a_2\in A_2$, where $a_1\mapsto a_2$ or $a_2\mapsto a_1$.


\subsubsection{Case 1: $a_1\mapsto a_2$}

If the attribute $a_1$ is finer granularity than $a_2$, then we do not need to perform reaggregation.  
Thus we define the output view $V^*=V_1\odot_{op,reagg} V_2$ as follows:
\begin{align*}
  Q^* &= \pi_{A_{gb}, Q_1.y\ op\ Q_2.y\to y }\left(Q_1 \mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin}_{joinp{\land Q_1.a_1{\sim}Q_2.a_2}} Q_2  \right) \\
  R^* &= R_1\\
  A'_{gb} &= A_{gb} - \{a_1, a_2\} \\
  joinp &= \land_{a\in A'_{gb}} Q_1.a = Q_2.a
\end{align*}
where $A_{gb}$ are the grouping dimension attributes in $Q_1$. 
{\it joinp} is identical to the join conditions in the definition in \Cref{ss:algebra_stat},
but only for the attributes that are identical in $Q_1$ and $Q_2$. 
The join also checks that the value of $a_1$ functionally determines the value of $a_2$.

\begin{example}
  Alice compares the difference between daily profits and monthly toy profits, so
  specifies \circled{3}$\ominus$\circled{4}, which results in \Cref{f:calendar}(b).
  The join condition only matches rows where translating $Q_1.day$ into its month is equal to corresponding $Q_2.month$.
  Each day's profit is reduced by that month's average profits. For instance,
  January 1st's profits is reduced by the average January profit.
\end{example}

\subsubsection{Case 2: $a_2\mapsto a_1$}

If the attribute $a_1$ is coarser than $a_2$, then we need to reaggregate the data in $V_2$.  Recall that queries have the form $Q_i = \gamma_{A^i_{gb}, f(a_y)\to y}(\sigma_{p}(D))$.
We define the output view $V^*$ as follows:
\begin{align*}
  Q^* &= \pi_{A^1_{gb}, Q_1.y\ op\ Q'_2.y\to y}(Q_1\mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin}_{A^1_{gb}} Q'_2) \\
  Q'_2 &= \gamma_{A^{1}_{gb}, reagg(a_y)\to y}(\sigma_p(D)) \\
  R^* &= R_1
\end{align*}
The main idea is to reaggregate $Q_2$ at the same granularity as $Q_1$ (by using its grouping attributes $A^1_{gb}$), and then perform statistical composition as normal.  
We reaggregate the base table $D$ rather than the output of $Q_2$ to avoid potentially misleading statistics such as the average of averages.

\begin{example}
  Alice now compares the difference between monthly toy profits with the daily profits, so specifies \circled{4}$\ominus$\circled{3} (\Cref{f:calendar}(c)).
  To compute this, \sysh first aggregates e.g., March's profits using $avg$, and then subtracts the average profits from March's toy profits.  
\end{example}





\subsection{Union Composition $\cup$}
Although $\cup$ was a symmetric operator in \sys, it is asymmetric in \sysh.
This is because union composition requires two definitions based on the need for reaggregation.
Using the same notations and assumptions as above, we define $V^* = V_1\cup_{qid,a}V_2$ under two cases. 
$qid$ is a query identifier, $a$ is an available visual attribute.  


\subsubsection{Case 1: $a_1\mapsto a_2$}

In the first case, $V_2$ is rendered as a coarser granularity than $V_1$,
so we duplicate each record in $Q_2$ for each matching record in $Q_1$.
For instance, $\circled{3}\cup\circled{4}$ will duplicate January's average profits for each day in January.
This is accomplished by defining $Q'_2$, which performs a left outer join, so that there is one output row for every unique value of $a_1$ in $Q_1$.  
We then keep the attributes in $A_1$ so that $Q'_2$ has the same schema as $Q_1$.
\begin{align*}
  Q'_2 &= \pi_{A_1}(\pi_{a_1}(Q_1) \mathbin{\ojoin\mkern-5.8mu\Join}_{a_1{\sim}a_2} Q_2)\\
  Q^* & = \pi_{*, \hl{qid}}(Q_1) \cup \pi_{*, \hl{qid}}(Q_2) \\
  R^* &= \{qid\to\hl{$a$}\} \cup R_1 \hspace{2em} s.t. \ a \textrm{ is an unmapped vis attr}
\end{align*}


\subsubsection{Case 2: $a_2\mapsto a_1$}

In the second case, $V_2$ is at a finer granularity than $V_1$, so
we reaggregate its data to $V_1$'s granularity.  
This is similar to the reaggregation procedure for statistical composition, and also
requires a $reagg()$ function, which defaults to the aggregation function in $Q_1$.
\begin{align*}
  Q^* & = \pi_{*, \hl{qid}}(Q_1) \cup \pi_{*, \hl{qid}}(Q'_2) \\
  Q'_2 &= \gamma_{A^{2'}_{gb}, reagg(a_y)\to y}(\sigma_p(D)) \\
  A^{2'}_{gb} &= A^2_{gb} - \{a_2\} \cup \{a_1\}\\
  R^* &= \{qid\to\hl{$a$}\} \cup R_1 \hspace{2em} s.t. \ a \textrm{ is an unmapped vis attr}
\end{align*}




\section{\sys for Database-oriented Visual Analytics}
\label{s:algebra}

This section defines the semantics of \sys for visual analytics. We first define view tables as SQL group-by aggregation queries, and then define the operator semantics---specifically, the data transforms and visual mappings of the output view given the operator inputs.   Please refer to next section  for diagrams and screenshots of the interaction designs to express these operators.

\subsection{View Definition}

As described in \Cref{ss:vcaoverview} we model a view as $V_i = R_i(T_i)$.
In visual analytic systems, $T_i$ is typically the output of a transformation query $Q_i(D)$ over an input database table $D$.  Our algebra will be defined over such queries.  Let $D(a_1,\ldots,a_n)$ contain $n$ attributes and $A_D = [a_1,\ldots,a_n, a_y]$ denote its schema, where $a_y$ is the measure, and the rest are dimensions.
$Q_i$ is responsible for all data processing and transformation (e.g., grouping, filtering, joining with other tables), so that rendering simply maps each result row to a mark rendered in the view.    The separation of data transformation and
presentation allows each to be defined and changed independently.


\subsubsection{Query Transformation}\label{ss:algebra-query}
\input{content/relalgtable}

Most visual analytic systems~\cite{Stolte2000PolarisAS,dice2014,Gray2004DataCA,Chaudhuri1997AnOO,Pahins2017HashedcubesSL} are based on {\it group-by aggregation queries} that filter the input
table using a predicate $p$, group records by a set of attributes $A_{gb}$, and compute an aggregated statistic $f_i(a_y)$:
  \begin{lstlisting}[
    caption={},
    captionpos=b,
    basicstyle=\small\ttfamily,
    frame=,
    mathescape=true,
    escapeinside={@}{!} ]
  $Q_i$ = SELECT @$A_{gb}$!, @$f(a_y)\to y$!  FROM D [WHERE @$p$!] GROUP BY @$A_{gb}$!
  \end{lstlisting}
  \noindent For example, VizQL is a layout algebra for creating faceted, layered charts from relational databases whose statements are translated into group-by aggregation queries~\cite{stolte03thesis}.  \Cref{a:vizql} describes how VizQL statements are expressible as operands in \sys.  

SQL is verbose and difficult to symbolically manipulate, so we will use the equivalent relational algebra statements (\Cref{t:relalg}):

  $$Q_i = \gamma_{A_{gb}, f(a_y)\to y}(\sigma_{p}(D))$$

\noindent $\sigma$ keeps rows that satisfy predicate $p$, $\gamma$ groups rows by a subset of the dimensions $A_{gb}$ and computes  $f(a_y)$ for each group.  

\begin{figure*}
   \centering
   \includegraphics[width=\linewidth]{algebra_ops}
   \vspace{-2em}
   \caption{Examples of View Composition Algebra operations over views of flight delay statistics.  
     The algebra enables comparison and composition of visualization views.  
     (a) difference between SFO and OAK delay statistics by date,
     (b) the sum of delays by date,
     (c) union composition of SFO and OAK delays,
     (d) difference between 1D SFO delays and a 0D delay constant,
     (e) difference between a 2D heat map of delays per city, date, and a 1D view of El Paso delays,
     (f) fit linear models to extrapolate AM and PM delay trends. 
   }
 	\label{f:algebra_ops}
\end{figure*}



\subsubsection{Visual Mapping}

Each output record of $Q_i$ is mapped to one mark.  
Given the view's mark type $K$, $R_i$ maps 
attributes in the query result to visual attributes  (e.g., x, y, color) valid for the mark type $K$. 
Let $A_{Q_i}$ be the attributes in $Q_i$, and $A_K$ be the set of visual attributes for $K$.  $R_i$ is defined as:
$$R_i = \{K\to mark\} \cup \{ a_q\to a_v | a_q\in A_{Q_i} \land a_v\in A_K \}$$
Each visual attribute can be referenced at most once, and not all query attributes need to be mapped.  Let $A_{R_i}$ denote the visual attributes that have been mapped in $R_i$.

Our algebra incorporates Gleicher et al.'s three design strategies for visual comparison (juxtaposition, superposition, and explicit encoding)~\cite{gleichercompare} depending on the operator.  The user can then use existing mechanisms to reconfigure the output view's visual mappings or recommend alternative mappings~\cite{Mackinlay2007ShowMA,Moritz2019FormalizingVD,Lin2020DzibanBA}, since they are well-supported in visual analysis systems.








\subsection{Binary View Composition}


A binary operator takes views $V_1$ and $V_2$ as input and returns a new view $V^* = R^*\left( Q^* \right) $.  
The statistical operator $\odot_\phi$ derives new statistics from the input views' measures, and
the union operator $\cup_\phi$ merges their data into the same view, and the operator parameter $\phi$ is described below.
\Cref{f:algebra_ops}(a-c) illustrate these binary operators.
Recall that the input views are compatible if the measures are compatible and the set of dimensions are the same.  We will relax the latter requirement in \Cref{sss:schema} to support compositions such as \Cref{f:algebra_ops}(d,e).

\subsubsection{Statistical Composition $\odot$}
\label{ss:algebra_stat}

$V^*=V_1\odot_{op} V_2$ joins rows from $Q_1$ and $Q_2$ and computes a new measure $Q_1.y\ op\ Q_2.y$ from the two views' measures:
\begin{align*}
  Q^* &= \pi_{A_{gb}, Q_1.y\ op\ Q_2.y\to y }\left(Q_1 \mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin}_{A_{gb}} Q_2  \right) \\
  R^* &= R_1
\end{align*}
$Q^*$ first computes the outer join between $Q_1$ and $Q_2$ by matching records from each query 
whose grouping attributes  $A_{gb}$ have the same values.  
An outer join ensures that rows in either table have at least one output row even if there is no match.
Since the input queries, by definition, were grouped on $A_{gb}$, we are guaranteed exactly one output row for each group in $Q_1$ and $Q_2$.  Finally, $\pi$ copies the join attributes, computes $Q_1.y\ op\ Q_2.y$, and renames it as $y$.


$op$ is defined as ``$-$'' by default, however any binary arithmetic function is allowed.
As shorthand, $\oplus$ and $\ominus$ denote $\odot_+$ and $\odot_-$, respectively.
$\odot_{op}$ is symmetric iff $y_1\ op\ y_2 = y_2\ op\ y_1$.

There is one special case where the right operand $V_2$ is handled differently 
than described above.  If a grouping attribute $a\in A_{gb}$ 
only contains a single unique value in $Q_2$'s output,
we remove $a$ from $Q_2$'s grouping attributes.
This is so dimension attributes that do not encode any data variation 
do not affect the semantics of the operator.  
This case is then handled as nonexact schema composition (\Cref{sss:schema}).


\begin{example}
\Cref{f:algebra_ops}(a) subtracts \texttt{OAK} daily delays from \texttt{SFO} daily delays.  
Since the queries for both views group by \texttt{date, src}, a naive composition
will join the two datasets on $A_{gb}=[date,src]$ and none of the rows will match.
In contrast, dropping \texttt{src} from the join condition is needed compare each \texttt{SFO} day to the correspoding day in \texttt{OAK}.
\end{example}

\subsubsection{Union Composition $\cup$}

Union $V^* = V_1\cup_{qid,a}V_2$ composes the marks from both views into the same output view:
\begin{align*}
  Q^* & = \pi_{*, \hl{qid}}(Q_1) \cup \pi_{*, \hl{qid}}(Q_2) \\
  R^* &= \{qid\to\hl{$a$}\} \cup R_1 \hspace{2em} s.t. \ a \in A_K - A_{R_1}
\end{align*}
Each query $Q_i$ is augmented to track a unique identifier $qid$, so that rows from each query can be distinguished in $Q^*$.  $R^*$ additionally maps $qid$ to a visual attribute $a$ that is not already mapped in $R_1$.

By default, $qid$ is defined based on an internal identifier for the input view. However, it can be any value that uniquely identifies the view.  For instance, if the input views are part of a faceted visualization, then $qid$ may be each view's facet title.   By default, $a$ uses existing perceptual effectiveness orderings~\cite{cleveland1984graphical,Stolte2000PolarisAS} to choose the most effective ordinal visual attribute that is available.

Union composition will juxtapose (as in \Cref{f:algebra_ops}(c)) or superimpose (as in \Cref{f:teaser}(b)) the input marks based on their mark type.  If the mark fills the area between the measure value and 0 (e.g., bar charts, area charts), then the marks in the output view are juxtaposed to avoid overlapping them.  In contrast, line and scatterplot marks are simply superimposed atop each other.

\subsection{Statistical Composition with Nonexact Schemas}
\label{sss:schema}

\Cref{f:algebra_ops}(d,e) are examples where the two views do not have identical query schemas.
They measure the difference between a bar chart and a constant value, or between a heat map and a bar chart.   
We now relax the safety rules for statistical composition $\odot_{op}$ to cases where the set of grouping attributes $A_{gb}^1$ in $Q_1$ 
is a strict super set of $A_{gb}^2$ in $Q_2$. 
\begin{align*}
  Q^* &= \pi_{A_{gb}^1, Q_1.y\ op\ Q_2.y\to y }(Q_1 \mathbin{\ojoin\mkern-5.8mu\Join}_{A_{gb}^2} Q_2)\\
  R^* &= R_1
\end{align*}
$Q^*$ is defined over the {\it left} outer join of 
$Q_1$ and $Q_2$.  This join ensures that rows in $Q_1$ are preserved in the join
result, but rows in $Q_2$ that do not have a join match are not in the output.
We chose this because composition of views with different schemas is not 
symmetric---$V_1$ is transformed by matching data in $V_2$, but not vice versa.

How $A^2_{gb}$ is defined for $Q_2$ affects the semantics of the operator.  If $Q_2$ does not have any grouping attributes---it only contains a metric attribute---then every mark in $V_1$ will be composed with every metric value in $V_2$.  However, if $Q_2$ contains a \texttt{date} dimension, then each mark in $V_1$ will only be composed with the metric values in $V_2$ that have the same \texttt{date}.
Finally, note that the join condition is with respect to the smaller set of 
grouping attributes in $Q_2$,
whereas the attributes preserved in the query output are from $Q_1$.


\begin{example}
\Cref{f:algebra_ops}(d) composes a 1D view of SFO delays ($V_1$) with a 0D view ($V_2$) 
consisting of a single delay constant.
Their grouping attributes correspond to $A_{gb}^1=[date]$ and $A_{gb}^2=\emptyset$.
$V_1\ominus V_2$ subtracts the constant from each row in $Q_1$.
\end{example}

\begin{example}
\Cref{f:algebra_ops}(e) composes a 2D heat map of delays by city$\times$date ($V_1$)
with a 1D bar chart of El Paso delays by date ($V_2$).  Their grouping attributes are $A_{gb}^1=[date, city]$ and $A_{gb}^2=[date]$, and the resulting view removes El Paso's 
delays from each city's delays.
\end{example}


\subsection{View Decomposition}\label{ss:decompose}

It is often useful to decompose components of a view (values, marks, groups) into one or more stand-alone views that contain a subset of the input view's rows and attributes.  The new views can then be used as operands for further composition, or manipulated for further analysis.  To this end, we define 2 decomposition operators based on interactions often used during view manipulation and coordination.   

The {\it extract} operator $\downarrow(V, p) = R(\sigma_p(Q))$ creates a single new view based on a subset of rows in $V$ that match predicate $p$.  If $p$ is not specified, it defaults to $true$, which is equivalent to creating a copy of $V$.  $\downarrow$ can be used to create a standalone view that renders a selected subset of marks, similar to coordinated overview-detail visualizations.   $\downarrow$ can also be used to e.g., extract marks from different views and then juxtapose them using $\cup$.  

The {\it explode} operator $\Xi_{A_e}(V)$ generates a set of views (a viewset), with one view for each group defined by the attributes $A_e$.   Explode is similar to facetting, which is traditionally used when creating new views from raw data.  In contrast, $\Xi$ is directly applied to existing views, including views derived from previous manipulations or compositions.  The query for each output view first filters by the group, and then drops the explode attributes $A_e$; the visual mapping drops any mappings from $A_e$:
\begin{align*}
  \mathbb{Q}^* &= \{\pi_{\neg A_e}(\sigma_{A_e=vals}(Q)) | vals \in \gamma_{A_e}(Q)  \}\\
  R^* &= \{a\to a_v | a\to a_v\in R \land a\not\in A_e \}\\
  \mathbb{V}^* &= \{ R^*(Q^*) | Q^* \in \mathbb{Q}^* \}\\
      \neg A_e &= A_{gb} - A_e
\end{align*}




\subsection{Composing Viewsets}\label{ss:viewsets}

We now extend composition to a {\it viewset} containing $n$ views 
$\mathbb{V} = \{V_1,\ldots,V_n\}$.  
Following our safety rules, all views in $\mathbb{V}$ have identical schemas, and
their queries  have the same grouping attributes $A_{gb}$.  

\subsubsection{Viewset Statistical Composition $\odot$}

When statistically composing a viewset $V^* = \odot_{f^*}(\mathbb{V})$, 
the purpose is to derive new statistics from the underlying data of each of the views,
rather than compare any individual pair of views in the viewset.
For this reason, we first union the {\it preaggregated} data from each query, and then
{\it reaggregate} the union.  
These semantics differ from binary statistical composition, which composes the aggregated measures from each input query.

We first rewrite each $Q_i$ as $\gamma_{A_{gb}, f(a)\to y}(q_i)$, 
where $q_i$ represents any filtering, join, and projection
operations that $Q_i$ performs prior to grouping and aggregation ($\gamma$).
This does not change the semantics of $Q_i$, but allows us to refer to $q_i$ in the definition above.
\begin{align*}
  Q^* &= \gamma_{A_{gb}, \hl{$f^*(a)$}\to y}\left(q_1 \cup \ldots \cup q_n  \right) \\
  R^* &= R_1
\end{align*}
$Q^*$ first unions all $q_i$ before grouping by $A_{gb}$ and 
computing the aggregation function \hl{$f^*\left(  \right)$}.  
We do this to ensure that aggregate statistics are always computed over the input data, 
and so users do not inadvertantly compute e.g., averages of averages, 
which can easily lead to misinterpretation. 
Common aggregations include \texttt{min}, \texttt{max}, \texttt{avg}, \texttt{std}, and \texttt{count}, however any 
numeric aggregation function (e.g., $\frac{avg(delay)}{max(delay)}$ is acceptable.
We use $f^*\left(  \right) $ to distinguish the parameter from the non-aggregation function 
$h\left(  \right)$ used in binary composition and the aggregation $f\left( \right)$ in the input
queries.

We also generalize the special case in binary statistical composition to every view in the viewset.   
If a grouping attribute $a$ has
a single unique value in {\it every} view's query result, then it is removed from 
$A_{gb}$ when computing the group by in $Q^*$.
For instance, if the user highlights a set of marks in a chart, and wants to summarize
their measures, then each mark is treated like a separate view, and their grouping attributes are
all dropped (since there is a single group in each ``view'').
If this is not done, the output in the example would be the same set of marks---effectively a noop.
We illustrate this interaction in \Cref{ss:iact_nary}.


\subsubsection{Viewset Union Composition $\cup$}

The union operator $V^*=\cup_{qid,a_t}(\mathbb{V})$ directly extends the 
binary union operator by extending and unioning all queries in the viewset.  
Similarly, \hl{$qid$} maps to an available visual attribute $a$.
\begin{align*}
  Q'_i &= \pi_{Q_i.*, \hl{qid}}(Q_i(D))\hspace{2em}\forall i\in[1,n]\\
  Q^* & = Q'_1 \cup \ldots \cup Q'_n \\
  R^* &= \{qid\to\hl{$a$}\} \cup R_1\hspace{2em} s.t. \ a \in A_K - A_{R_1}
\end{align*}



\subsubsection{Viewset-View Composition}

We can now define composition of viewsets and views, whose output is a new viewset.  Below, $\circ$ denote any binary operator:
\begin{align*}
  \mathbb{V} \circ V &= \{ V_i \circ V | V_i\in\mathbb{V} \}\\
  V \circ \mathbb{V} &= \{ V \circ V_i | V_i\in\mathbb{V} \}\\
  \mathbb{V}_1 \circ \mathbb{V}_2 &= \{ V_i \circ V_j | V_i\in\mathbb{V}_1, V_j\in\mathbb{V}_2 \}
\end{align*}


\subsection{Learning and Composing Model Views}

Oftentimes two views may not neatly compose because the {\it values} of the grouping attributes do not match.  
For instance, suppose $V_1$ renders delays on even days while $V_2$ renders  delays on odd days.  
Although $V_1\ominus V_2$ is safe, the resulting view
is uninformative because there are no matching dates in the join.
For this reason, the unary {\it lift} operator $\uparrow_{M,A_d, A_c}(V)$ fits a model $M$ to the data in view $V$ and returns a {\it model view}:  
\begin{align*}
  Q^* &= \gamma_{\hl{$A_c$}, train_{\hl{$M$}}(\hl{$A_d$},y)}\left(Q \right) \\
  R^* &= \{a\to a_v |  a\to a_v\in R \land a\in \hl{$A_c$}\cup \hl{$A_d$} \}\hspace{2em} s.t. \ \hl{$A_d, A_c$} \subseteq A_{gb}
\end{align*}
In the above, $Q^*$ groups the output of $Q$ by $A_c$, and for each group, trains a model $M$ that uses $A_d$ as features to predict the measure $y$.  In effect, the operator trains the model $M(A_d, y | A_c)$.
$R^*$ only keeps mappings in $R$ related to the features $A_d$ or conditioned attributes $A_c$.
We require that $A_d$ and $A_c$ are part of $V$'s grouping attributes, and $A_d$ contains only quantitative attributes that can be used as numeric features in the model.  


\begin{example}
  In \Cref{f:algebra_ops}(f), $\uparrow_{linear,[date],[ampm]}(V)$ fits two linear regression models, one for AM and one for PM.  Each model uses \texttt{date} and an intercept term to predict the average delay.  
\end{example}

Models are a compact representation of an infinite-sized relation, however
 charts render finite sets of rows.
In order to render a model view, we sample the domain of $A_d$ and predict
the $y$ value for each sample in each group as defined by $A_c$.  
The results are used as the ``query result'' and rendered as normal.
As a heuristic, we sample $20$ equi-distant values from the domain of each attribute in $A_d$; if there are many attributes in $A_d$, we scale down the samples per attribute so the total number of samples does not exceed $1000$.

\subsubsection{Composing a View and Model View}

A major use case for model views is to aid comparisons
between views that would otherwise not share join values.  
We define the composition  $V_1\circ V_M$ 
of a view $V_1$ and model view $V_M$ as follows, where $\circ$ is any binary composition operator and the usual safety rules apply:
\begin{align*}
  Q_M' &=  \pi_{A_{gb}^1, M(Q_1.A_d)\to y}\left( Q_1 \bowtie_{A_c} Q_M \right) \\
  V_M' &= R_M(Q_M')\\
  V^* &= V_1 \circ V_M'
\end{align*}
At a high level, we use the models in $V_M$ to predict the $y$ value for each
row in $Q_1$.  To do so, we need to match the appropriate model $M$ for each $Q_1$ row.  We do this using an inner join on $A_c$, which emits a join result only if there is a match.    This is to avoid the case when a model has not been trained for the specific $A_c$ values for a row in $Q_1$; we emit a warning with the number of such rows.   Each join result projects the grouping attributes $A_{gb}^1$ from $Q_1$ along with the predicted $y$ value.     If $\circ$ is symmetric, then $V_M\circ V_1 = V_1\circ V_M$.

\subsubsection{Composing Two Model Views}

In order to compose two model views, we follow the same procedure as rendering a model view.  We sample from $A_d$, and use the samples to generate predictions from both model views.  The results are treated as query results and the normal composition operator is applied.



\subsection{Properties of the Algebra}

The operators are closed---operator outputs can be inputs to other operators---except in one case.
The nary statistical composition operator assumes that the input views' queries in canonical form  $\gamma_{A, f()}(q)$, where $q$ does not contain any aggregation operators.  All operators return views with canonical queries, except for binary statistical composition $\ominus(V_1, V_2)$, whose output query structure is $\pi(Q_1\mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin} Q_2)$.   In this case, aggregation happens before the join ($\mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin}$) and projection ($\pi$), and in general cannot be rewritten into canonical form.

\input{content/visql.tex}

\section{Implementation}

Implemented in ES6, renders charts using vega-lite, generates SQL queries executed in a database (currently SQLite or Google BigQuery). 

\subsection{Rendering}
Simple rules.

\section{Overview}  
\label{s:overview}

This section provides an overview of the view composition algebra (\sys), its relationship with data integration, and its safety properties.


\subsection{Overview}\label{ss:vcaoverview}

This subsection presents the main operators in \sys, and how a view (operand) is modeled.  Note that we do not consider layout-oriented composition (e.g., organizing views side by side) since it is well-studied~\cite{Chen2020CompositionAC} and already widely supported in practice.

\input{content/tables.tex}
\begin{figure}[th]
  \centering
  \vspace{-1em}
  \includegraphics[width=.4\columnwidth]{viewtypes}
  \vspace{-1em}
  \caption{Bar chart of left-most table in \Cref{t:viewtypes}.  Its views include  the chart, a constant value, mark(s), and grouping attribute(s). }
  \label{f:viewtypes}
\end{figure}


\stitle{Operands:} 
A {\it view} traditionally refers to an entire chart.  In contrast, \sys defines view as the output of $R(T)$, where $T$ is a table (a raw table or a SQL query result) and $R$ is a visual encoding specification from a subset of $T$'s data attributes to visual attributes.  For example, \Cref{f:viewtypes} illustrates a bar chart that renders table \circled{1} in \Cref{t:viewtypes}, where $R$ is encodes \texttt{Date} to the x-axis, \texttt{src} to color, and the measure \texttt{Delay} to the y-axis.   We call $T$'s attributes its {\it schema}.   Similar to VizQL~\cite{Stolte2000PolarisAS}, the attributes in $T$ are either dimensions (used for filtering, grouping, and database joins) or measures (used to compute statistics); for ease of discussion, we will assume that each table contains a single measure.    The data rows in $T$ are mapped 1-to-1 into rendered marks in the view, and any computations and transformations necessary have already been applied to produce $T$ (in other words, $T$ is the output of a query).   Any part of the visualization that conforms to this definition as a {\it view}.   


We use \Cref{f:viewtypes} and \Cref{t:viewtypes} to illustrate the above concepts.  The chart is annotated with the different types of views that can be expressed as the tables listed in \Cref{t:viewtypes}.  
For instance, the chart's input table is depicted as \circled{1}. A constant value is a single-row table with a single attribute (\circled{2}), and a mark is a row from the input table (\circled{3}). A grouping attribute rendered in the legend represents a subset of rows that match a predicate: \texttt{SFO} corresponds to the rows that match \texttt{src=SFO} (\circled{4}).  Finally, predictive models use a subset of the dimension attributes to predict a measure attribute.  For instance, \circled{5} uses \texttt{Date} and \texttt{src} to predict the expected \texttt{Delay}.  In essence, $T$ is an instance of a table sampled from the model.  


\stitle{Operators:} 
\sys defines unary, binary, and nary composition operators and two decomposition operators.  The binary operators {\it statistical composition} and {\it union composition} are respectively used to derive new statistics and superimpose/juxtapose the operands.  The nary operators generalize the binary operators to compute aggregate statistics and superimpose/juxtapose a set of views.  The unary {\it lift} operator transforms a view into a predictive model; this is useful when the views are technically safe to compose, but do not share the same attribute values.  For example, composing two views that render prices on even days and odd days is not meaningful  because each odd day does not have a counterpart to comparable against in the even days.   Lifting the even days view will interpolate its prices to odd days so that the composition produces a meaningful result.  Finally, the unary extract and explode operators are for view {\it decomposition}, where components of a view are extracted and turned into new standalone views.



\subsection{Composition as Data Integration}

Data integration~\cite{doan2012principles,batini1986comparative,Naumann2018SchemaM,batini1986comparative,christen2012data} is a research field that studies the problem of combining two (or more) tables into a single ``integrated'' table, and deals with two primary problems. {\it Schema matching} maps attributes in one schema to semantically equivalent attributes in the second schema.  For instance, which attributes in the schemas \texttt{(day, price)} and \texttt{(date, cost)} should match?    {\it Entity matching} maps  rows (i.e., entities) in one table to the ``comparable'' rows (i.e., the same entities) in the second table.  

The same two problems manifest in view composition.  Determining whether the views are composable is an instance of schema matching.  For instance, a chart of \texttt{profits} vs \texttt{losses} should clearly not be composed with a chart of \texttt{names} vs \texttt{age}. However, it would also be ambiguous to compose with a chart of \texttt{profits} vs \texttt{profits} (of different years) since it is unclear which \texttt{profits} attribute in the latter chart should be matched with \texttt{profits} in the first chart.  

Similarly, determining which marks in the input views should be compared is an instance of entity matching because each mark renders a single input row.    For example, suppose we wish to compose the chart in \Cref{f:viewtypes}, whose dates span $1-3$, with a different chart whose dates span $5-8$.  Although their schemas are identical, none of the marks in the first view can be compared with any marks in the second view because their dates do not overlap.

 In short, the schema matching problem determines whether or not composition should be allowed (safety), whereas the entity matching helps us asses whether the composed view return a meaningful result.  In SQL terminology, the former determines if a join is possible, and the latter determines if the join would return any results.    This correspondence informs our definition and data-oriented approach to safety.

\subsection{Safety and Expressiveness}
\label{ss:criteria}

When is the data from multiple views safe to compose?
Determining the answer is necessary before defining {\it how} the views can be composed.
We now define an algebra's safety and expressiveness properties, and the heuristic rules that \sys uses.



\subsubsection{Safety}
Safety is needed to avoid compositions that are ambiguous, or may mislead the user.  For instance, a chart of \texttt{delay} by \texttt{date} should not be composed with a chart of \texttt{profits} by \texttt{market}.   \sys enforces safety by only allowing compositions for which there is a unique schema matching between the views' schemas.  To do so, \sys uses the following heuristic: two views are incompatible if their schemas cannot be unambiguously matched or if their measures are incompatible.  

Two tables match if their set of dimension attributes are the same and there are no duplicate attributes to cause ambiguity.  For binary operators, the dimensions may also have a superset-subset relationship (\Cref{s:algebra}).  Using this heuristic, the views in the above example do not match because their dimensions (\texttt{date}, \texttt{market}) do not overlap.   

Two measure attributes are compatible if they are derived from the same input attribute and use compatible statistical functions (if any) as determined by our attribute-sensitive type checking rules.  A function $f(a)$ can have output type $a$, a custom type $T$, or a parameterized custom type ${T}{<}{a}{>}$.  For instance, \texttt{average(a)}, \texttt{std(a)}, \texttt{min(a)}, and \texttt{max(a)} all output the type $a$, whereas \texttt{count(a)} outputs type $count{<}{a}{>}$.  Function evaluations are compatible if their output types are the same.  For instance, \texttt{avg(delay)} is compatible with \texttt{delay} and \texttt{min(delay)}, but not with \texttt{avg(price)} nor \texttt{count(delay)}.  


\subsubsection{Expressiveness} 
Expressiveness states that views that {\it could} be composed are allowed by the algebra.   For instance, a bar chart of September \texttt{profits} by \texttt{date} should be composable with a scatterplot of October \texttt{profits} by \texttt{date}.  To achieve this, \sys uses the view's table schema rather than its visual mapping to determine view compatibility. 
Of course, there are many compositions that appear sensible to the user, but are disallowed based on our safety heuristics.   For instance, it is natural to compare a chart of \texttt{profits} with a chart of \texttt{losses} because (based on domain knowledege), we know that profits and losses are compatible.   To address this issue, we issue a warning when the user expresses an unsafe composition, and allow the user to override it in a special case: if the dimension attributes match, and the measure attributes are both numeric.
\Cref{s:discussion} discusses additional ways to expand expressiveness.



\section{Conclusion}

View Composition Algebra (\sys) is a recent formalism for composing entire of parts of visualizations to aid adhoc comparison tasks.  Users can select values, marks, legend elements, and entire charts as targets, and use composition operators to summarize or compare the targets.  
This paper extend View Composition Algebra to support comparsions between views that render data at different hierarchical granularities.  This enables users to easily compare data within spatial visualizations, between different visualizations 
We presented the formal semantics that are compatible with the underlying queries supported by visual analytic systems such as HiDE and Polaris.   We further illustrated example interactions  in the context of small multiples visualizations and spatial hierarchical visualizations. 

\section{Examples}\label{s:eval}


\sysh directly benefits from \sys's compositionality, its well-defined semantics, and that it can compare data independently of how they are visually encoded.
This section presents examples of how \sysh complements existing visual analysis systems.




\subsection{Tableau}

\sysh can enable novel comparison interactions in Tableau-like exploration interfaces.
\Cref{f:tableau} shows small multiples of a bar chart for each quarter, and each chart renders costs per month.   
For all four example interactions, the user can drag component $V_2$ in the interface over $V_1$ to express $V_1\ominus V_2$. 

\circled{A} composes Q1's bar chart with all Quarters. It aggregates the bar chart data to the quarter level (average of Q1) and subtracts that value from each quarter's average cost.     The horizontal line is the zero line.
\circled{B} drags the Q2 header to the the month attribute in the x-axis shelf.  This subtracts  Q2's average cost from all small multiples charts.  The output is the same set of small multiples, but with each bar reduced by Q2's average cost.
\circled{C} drags the Q2 label onto the Q1 bar chart.  This is akin to \circled{B}, but only for a single target bar chart.
\circled{D} drags the \texttt{Qtr} attribute in the x-axis shelf onto the \texttt{Month} attribute. This computes each quarter's average cost, and subtracts it from the corresponding quarter's bar chart.   

\begin{figure}[htpb]
  \centering
  \includegraphics[width=\columnwidth]{figs/tableau}
  \caption{(left) Comparison interactions possible due to \sysh,  (right)
  the results of applying $\ominus$ to the interactions.}
  \label{f:tableau}
\end{figure}


\subsection{Hierarchical Visualizations in HIVE}

\Cref{f:hive} illustrates an example where the left 
view renders the HIVE statement \texttt{state(profit$\to$size)/year},
and the right view plots profit by quarter.
Logically, HIVE computes the spatial layouts one level at a time.
It first computes average price by state, and uses it to size the state-level \red{red} rectangles.
Then, for each state, it computes the average price by year and uses it to size the per-year rectangles.
Since these are all group-by aggregation queries, \sysh naturally applies.
The line chart renders price per week in NY, and \texttt{week}$\mapsto$\texttt{Year}.


\begin{figure}[htpb]
  \centering
  \includegraphics[width=.8\columnwidth]{figs/hive}
  \caption{HIVE visualization hierarchically renders year within state, line chart renders price per week.}
  \label{f:hive}
\end{figure}

We showcase three composition interactions and their outputs in \Cref{f:hive}(c).  
\bluecircled{X} drags Texas (\texttt{TX}) to the \texttt{state} component of the HIVE statement.   This will subtract Texas' 
average price from each state's price and re-render the entire spatial visualization.    Notice that TX disappears because
subtracted price is now 0, and is allocated no space.
\bluecircled{Y} drags a selection range in the line chart over the \texttt{TX} label.  This aggregates the data in the selection range to the year granularity and removes the aggregated values from the corresponding \texttt{TX} year.   Only the \texttt{TX} subset of the spatial visualization is returned.  
\bluecircled{Z} drags the selection range onto the \texttt{year} component of the HIVE statement.  This again aggregates the selected data, and subtracts it from each state's corresponding years.   The rectangles for 2001 are allocated more space in both states, however the proportions for the states do not change because the same amount is removed from both states.



\section{Introduction}\label{s:intro}

Comparison is a core task in visual analysis.
Although there are numerous guidelines to help users design effective visualizations to aid known comparison tasks, there are few formalisms that define the semantics of comparison operations in a way that can serve as the basis for a grammar of comparison interactions.  

Recent work proposed a formalism called View Composition Algebra~\cite{vca} (VCA) that enables ad hoc comparisons between any combination of marks, trends, or charts in a visualization interface.
The key idea is to model a view $V = R(Q(D))$ as a thin visual mapping function over the result of a query $Q$.  $Q$ is responsible for all data processing, aggregation, and transformations.  In this way, composition operations over multiple views such as differencing and union can be defined as expressions over the underlying queries of the views.  

For instance, \Cref{f:vca} illustrates the two core operators.  (a) computes the difference between SFO and OAK matching bars with the same days and subtracting each day's Oakland delay with the SFO delay on that day. (b) illustrates the union operation, which juxtaposes the bars for easier visua comparison.

\begin{figure}[htpb]
  \centering
  \includegraphics[width=\columnwidth]{figs/vca}
  \caption{Example \sys operations.  (a) statistical composition computes the difference between two views, and (b) union composition juxtapose or superimposes data from both views.}
  \label{f:vca}
\end{figure}

However, \sys limits comparisons to views that both render the same data attributes, or where their data attributes have a subset relationship (e.g., comparing {\it price per state} with {\it price}).  
In contrast, the majority of real-world data are hierarchical, and uses may wish to compare e.g., {\it price per state in 2000} with {\it price per county in 2001}.

To bridge this gap, we extend VCA to enables ad hoc comparisons between visualizations of hierarchical data.  We call this extension \sysh.
\sysh leverages known hierarchical relationships to enable ad hoc comparison of data at different hierarchical granularities, and we base the formalisms on functional dependencies, a core concept in the relation model~\cite{codd1983relational}.   We also illustrate applications to the hierarchical language HIVE~\cite{slingsby2009configuring} and Tableau visualizations.




\iffalse
Comparison is ubiquitous in visual data analysis, 
as a low-level perceptual task~\cite{cleveland1984graphical,Talbot2014FourEO,Heer2012InteractiveDF}
as well as a high-level task~\cite{Munzner2014VisualizationAA,gleichercompare} over a set of comparison targets.
When the comparsion tasks are known apriori, there are numerous design guidelines~\cite{Javed2012ExploringTD,gleichercompare} to help designers choose effective visual encodings and visualization designs.
However, a visualization designer cannot anticipate all of the comparisons that a user will want to perform.   

\begin{example}
  Tableau Online's example dashboard (\Cref{f:tableau})
  renders the number of incidents, problems, and requests per year in the top row, and their breakdowns in the bottom row. 
  What if the user wants to compute the incidents between 2017 and 2016?
  Or how the 2016 and 2017 incidents compare with the year-to-date hardware incidents?   
\end{example}

The user can visually estimate the comparison, but risks biased or inaccurate judgements.  The user could reconfigure the visualization for this task, but would need to context switch away from visual analysis.  Further, it requires complex data transformations and calculations are difficult for users to express~\cite{tableauhelp1,tableauhelp2,tableauhelp3,tableauhelp4} using existing visualization systems and graphical grammars.


\begin{example}
  \Cref{f:teaser}(left) shows the input data, visual encodings, and charts of the maximum and average flight delays by day from \texttt{SFO} and \texttt{OAK}, respectively.   The middle column shows the transformed data and encodings needed to express three similar comparisons: 1) subtract \texttt{OAK} from \texttt{SFO} statistics by day, 2) show \texttt{SFO} and \texttt{OAK} statistics side by side, and 3) compare \texttt{SFO}'s statistics with \texttt{OAK}'s average delay on day 2.  However, the transformations and resulting tables in each case are quite different.  The first aligns \texttt{SFO} and \texttt{OAK} statistics by day and creates separate attributes for each; the second concatenates the \texttt{SFO} and \texttt{OAK} statistics; and the third uses \texttt{SFO}'s statistics as the input table, and updates the formula in the visual mapping.
\end{example}

\begin{figure}
\centering
\includegraphics[width=\columnwidth]{figs/tableaudash}
\vspace{-.2in}
\caption{Tableau Online's pre-built ServiceNow  Executive Dashboard.}
\label{f:tableau}
\end{figure}






Ad hoc comparisons are difficult to support because the comparison targets could be any combination of components in the visualization.  In the incidents line chart, potential targets include the \texttt{730} label, each line trend, or the line chart; the user could compare individual values with trends, marks within a single chart, trends between charts, or data that are visually encoded differently.
The number of possible comparisons is exponential in the number of potential targets in the visualization, and it is infeasible to create a single design that best supports all of these comparisons.  

Rather than design a single visualization up front, users should be able to directly express ad hoc comparisons during visual analysis.  For instance, the user should be able to drag the 2017 incidents trend line over the 2016 trend to compute their difference, or drag the hardware incidents bar over the incidents line chart to compare them.
To do so, a language to express visual analysis comparisons is needed.

We propose 5 desirable criteria for such a language.
{\it (1) Comparison Diversity:} support a variety of visual design strategies for comparison~\cite{gleichercompare}, namely superposition, juxtaposition, and explicit encoding of the differences.
{\it (2) Flexible Targets:} comparison targets should be any visualization component derived from data, such as constant values, marks, legend elements, or charts.
{\it (3) Design Independence:} whether targets are comparable should be independent of their visual encoding and design.  For instance, the per-category incidents in the bar chart should be comparable with the monthly incidents line chart despite their visual differences.
{\it (4) Safety:} of the possible combinations of targets, only a subset are unambiguous and semantically meaningful to compose.  For instance, \texttt{profits} and  \texttt{height} are quantitative attributes but should not be composed.  The formalism should identify comparisons between targets that are potentially unsafe, and either prevent it or warn the user.  
{\it (5) Expressiveness:} the formalism should strive to allow targets that are semantically compatible.

The latter two criteria deal with the question: {\it When are visualization data comparable?}
Traditionally, the visualization designer manually determines that data is safe to compare, and then chooses the appropriate data transformation and design strategies.  However, ad hoc comparisons require that we formalize safety and check it automatically.
The challenge is that safety is trivial to satisfy by rejecting all comparisons. 
However, widening expressiveness is nontrivial because safety depends on the visualization, dataset's semantics, and user's domain knowledge.   Thus, a comparison language must strive to maximize expressiveness while ensuring safety.

In this paper, we propose an interaction design for comparison based on a new algebraic formalism called {\it View Composition Algebra} (\sys\footnote{\sys is also short for Visual Comparison Algebra.}).  \sys defines a closed set of composition operators over visualization components that we call {\it views}\footnote{Borrowed from data management, {\it View} refers to a query result.}: values, marks, legend elements, or charts.  Existing view composition spatially organizes charts into composited visualizations~\cite{Satyanarayan2017VegaLiteAG,Chen2020CompositionAC}, whereas \sys operators combine and transform the {\it underlying data} and infer sensible visual mappings to derive new views.


\sys defines three types of view composition operators.   The first computes statistical differences or aggregate summaries of matching values from the operands (e.g., difference in delays on the same day), the second merges marks from the input views into a single output view, and the third fits statistical models to the input views.   \sys further defines decomposition operators that derive new views from components of an input view.  We further define general safety rules for each operator, and elaborate on its connection to data integration.   User interactions select comparison targets as inputs to the operators, and choose composition operators to apply.    

\begin{example}
 In \Cref{f:teaser}(right) the user drags different components of the \texttt{OAK} chart onto the \texttt{SFO} chart.  The top drags the \texttt{OAK} chart onto the \texttt{SFO} chart, and uses the $\ominus$ operator to subtract their statistics, while the middle uses $\cup$ to juxtapose their marks.  The bottom drags \texttt{OAK}'s day 2 bar onto the \texttt{SFO} chart and uses $\ominus$.   
\end{example}


The use of views as operands ensures that \sys is compatible with existing manipulation interactions such as filter, zoom, pan, and linked brushing that transform the contents of existing views.  Further, the algebraic statements in \sys are easily compiled into SQL queries that can run on large databases.  \Cref{ss:algebra-query} describes how \sys is compatible with VizQL~\cite{Stolte2000PolarisAS}, and \Cref{s:eval} shows examples of how \sys could be used alongside manipulation interactions.


If there is one takeaway message, it is that ad hoc comparison depends on data integration and transformation techniques, as well as visual design principles. \sys is a starting point in the interaction design space for view composition and comparison.   We present a design that satisfies the above 5 criteria, and is compatible with visual analytic systems based on aggregation queries or data cube~\cite{Gray2004DataCA} exploration.  Further, the algebra naturally translates into SQL queries that can execute on large databases.  The paper presents a range of examples to illustrate the benefits of a composition algebra, and we show how \sys enables novel comparisons across visual encodings, between interaction states, and multi-step comparison interactions.  The paper uses screenshots when describing the interaction design, and simplified diagrams when they are more legible.  Interactive demonstrations are viewable at \url{http://viewcompositionalgebra.github.io}.

\fi


\section{Related Work}

\subsection{Visualization Languages for Hierarchical Data}

Hierarchical structures are integral to visualization algebras such as VizQL~\cite{hanrahan2006vizql,stolte03thesis}.   VizQL defines algebraic operators over data attributes to compose small-multiple display, which are manifested as interactions to drag-and-drop attributes onto x- and y-axis ``shelves''.    
The \texttt{cross} ($Qtr\times State$) operator creates one small multiple for each combination of quarter, state values.  
However, $\times$ is not appropriate when composing attributes within a hierarchy, because not all combinations of the attribute domains will exist in the dataset.  For instance, $Qtr\times Month$ will return $(Q1,Dec)$, which will never contain data.  
The hierarchy-aware \texttt{nest} ($Qtr/Month$) operator obeys the containment relationship, and ill only return pairs  where the month is in the appropriate quarter.  

Slingsby et al.~\cite{slingsby2009configuring} define a grammar for specify spatial layouts of hierarchical data.  Much like how graphical grammars map data attributes (e.g., day, cost) to a mark's visual attributes (e.g., x- and y-positions), HIVE proposes a visual mapping from attributes in a data hierarchy to levels in a spatial hierarchy.  In addition to this mapping, users also specify the desired layout algorithm at each level of the spatial hierarchy.  
For instance, using a simplified notation, \texttt{state(profit$\to$size)/year(profit$\to$size)} creates a nested tree map; the top level uses a space filling layout sized by price, and each rectangle is further subdivided by year and sized by that year's profits (\Cref{f:hive}).     HIVE can express a rich set of spatial visualizations, including calendars, tree maps, and cartograms. 
Similar ideas were explored in product plots~\cite{wickham2011product}, and probabilistic graphical grammars~\cite{pu2020probabilistic}.

Although these languages enable users to {\it create} visualizations that are aware of hierarchies, they
do not support ad hoc {\it comparisons across} different hierarchical levels.








\subsection{Composition in Visualization Grammars}

Graphical grammars, such as ggplot2~\cite{wickham2016ggplot2}, Vega-lite~\cite{Satyanarayan2017VegaLiteAG}, and VizQL~\cite{Stolte2000PolarisAS} model visualizations as mappings from data attributes to the visual attributes of the rendered marks.  These grammars implicitly perform data transformations, such as grouping and aggregation, based on the data types.   
For instance, VizQL is a table algebra to compose facetted, multi-layer visualizations, and used to navigate multi-dimensional data cubes~\cite{Gray2004DataCA,Stolte2003MultiscaleVU}.
\sys is compatible and composable with these grammars---\sys operators can take their views as input, and emits views as output.  \sys defines unambiguous data transformations so that interaction designers can focus on design choices.  

\subsection{Design Strategies for Comparison}

Javed and Elmqvist~\cite{Javed2012ExploringTD} propose a design space for composite visualizations, describe four visual composition designs (juxtapose, superpose with and without shared axes, and nested views).  Gleicher et al.~\cite{gleichercompare} characterize comparison by the target elements being compared, and the actions to compare them.  They similarly 
 propose juxtaposition, superposition, and explicit encoding as design strategies.  
\sysh goes beyond design guidelines, and defines formal composition rules and notions of safety.



\section{Preliminaries}

How to model hierarchical data so that an algebra can symbolically manipulate it?
This section presents a model for hierarchical data based on functional dependencies, and also introduces \sys.


\subsection{Functional Dependencies and Hierarchical Data}

SQL and most query languages are grounded in the relational model~\cite{codd1983relational}.  The relational model defines a database as a set of relations.   Each relation (table) consists of a set of tuples (records) that all adhere to a schema---a list of attribute, type pairs.   
Following VizQL~\cite{Stolte2000PolarisAS} and other visualization formalisms, we assume that a table $T$'s schema $A_T$ consists of dimensions (used for filtering, grouping, and database joins) and measures (used to compute statistics); without loss of generality, we will assume that each table contains a single measure. 

\stitle{Functional Dependencies:}
The relational model defines a functional dependency constraint (FD) $X\to Y$ as a set of attributes $X$ that {\it functionally determines} the set of attributes $Y$.  In other words, if two records have the same $X$ values, they must also have the same $Y$ values.  
For instance, $zip\to state$ says that two records with the same zipcode must have the same state.  
Foriegn key references are also a special case of functional dependencies because both values are equal, thus the dependency is in both directions.  


\stitle{Hierarchies are FDs:}
Attributes in real-world data typically form a hierarchical structure. 
Hierarchies are used in multi-dimensional databases to drill-down or roll-up, and in visualization systems to zoom in or zoom out.  Visualization formalisms like VizQL~\cite{hanrahan2006vizql,stolte03thesis} rely on such hierarchies to define operators like {\it nest}.  

Hierarchies are a special case of functional dependencies.
When we say that \texttt{district} is a child of \texttt{state} in a hierarchy, 
is expressed as the FD \texttt{district}$\to$\texttt{state}.  


Thus, we define a hierarchy $H = \{F_1,\ldots,F_n\}$
as a set of FDs whose edges form a directed acyclic graph.
In contrast to a colloquial hierarchy, where edges point from coarser to finer granularities (e.g., state to county), the edges in $H$ are reversed, and point from finer to coarser granularities.   

For instance, \Cref{f:hierarchy} shows tables that contain hierarchical data.
$T_1$ stores each census block's daily \texttt{Profit}, and contains \texttt{Day}, \texttt{Month}, \texttt{Qtr}, and \texttt{Year} attributes.
$T_2$ stores the geographical data associated with each \texttt{block}, and can be joined with
$T_1$ on \texttt{block} (dotted line).
$T_3$ contains the \texttt{Nation} name, and joins with $T_2$ on \texttt{nid}.


\begin{figure}[h]
  \centering
  \includegraphics[width=0.85\columnwidth]{figs/hierarchy.pdf}
  \caption{Tables with two example hierarchies; arrows are FDs.   }
  \label{f:hierarchy}
\end{figure}


\subsection{How VCA models Views}

\sys models a view as $V_i = R_i(T_i)$, where $T_i$ is a table (a raw table or a SQL query result) and $R_i$ is a visual encoding specification from a subset of $T$'s schema to visual attributes.  
In practice, $T_i = Q_i(D)$ is the output of a query $Q_i$ over an underlying database table $D$.  
Let $D(a_1,\ldots,a_n)$ contain $n$ attributes and $A_D = [a_1,\ldots,a_n, a_y]$ denote its schema, where $a_y$ is the measure, and the rest are dimensions.  Let $A_i$ be shorthand for $A_{R_i}$.

It is important that $Q$ encapsulates {\it all} computations and transformations needed to produce $T$, and that the renderer is only responsible for visual design---mapping data rows in $T$ to marks (or other objects) in the view and performing layout.  This is because the result of comparison operators depends on knowing {\it how} $T$ is computed.

\stitle{Queries:}
\sys focuses on {\it group-by aggregation queries}  
supported by most visual analysis systems~\cite{Stolte2000PolarisAS,dice2014,Gray2004DataCA,Chaudhuri1997AnOO,Pahins2017HashedcubesSL}.  These queries filter the input table using a predicate $p$, 
group records by a set of attributes $A_{gb}$, and compute an aggregated statistic $f_i(a_y)$:
  \begin{lstlisting}[
    caption={},
    captionpos=b,
    basicstyle=\small\ttfamily,
    frame=,
    mathescape=true,
    escapeinside={@}{!} ]
  $Q_i$ = SELECT @$A_{gb}$!, @$f(a_y)\to y$!  FROM D [WHERE @$p$!] GROUP BY @$A_{gb}$!
  \end{lstlisting}

To aid symbolic manipulation, \sys analyzes the equivalent relational algebra statements (\Cref{t:relalg} for full list):

  $$Q_i = \gamma_{A_{gb}, f(a_y)\to y}(\sigma_{p}(D))$$

\noindent $\sigma$ keeps rows that satisfy predicate $p$,
$\gamma$ groups rows by a subset of the dimensions $A_{gb}$ and computes  $f(a_y)$ for each group.  


\stitle{Visual Mapping:}
Given the view's mark type $mark$, $R_i$ maps 
attributes in the query result to visual attributes  (e.g., x, y, color) valid for the mark type $K$. 
Let $A_{Q_i}$ be the attributes in $Q_i$, and $A_{mark}$ be the set of visual attributes for $mark$.  $R_i$ is defined as:
$$R_i = \{mark\to `mark'\} \cup \{ a_q\to a_v | a_q\in A_{Q_i} \land a_v\in A_{mark} \}$$
Each visual attribute can be referenced at most once, and not all query attributes need to be mapped.  


\input{content/relalgtable}

\subsection{VCA Operators}

\sys defines a library of composition operators.  For space constraints, we will focus on its two core operators:
statistical composition, which explicitly computes the difference (or another measure) between matching marks in the two compared views,
and union composition, which spatially organizes the marks in the two views to aid visual comparison.  
In general, \sys focuses on the data transformations needed to define composition, and borrows the output visual mapping from its first argument.  

\subsubsection{Statistical Composition $\odot$}
\label{ss:algebra_stat}

$V^*=V_1\odot_{op} V_2$ joins rows from $Q_1$ and $Q_2$ and computes a new measure $Q_1.y\ op\ Q_2.y$ from the two views' measures (\Cref{f:vca}(a)):
\begin{align*}
  Q^* &= \pi_{A_{gb}, Q_1.y\ op\ Q_2.y\to y }\left(Q_1 \mathbin{\ojoin\mkern-5.8mu\Join\mkern-5.8mu\ojoin}_{A_{gb}} Q_2  \right) \\
  R^* &= R_1
\end{align*}
$Q^*$ first computes the outer join between $Q_1$ and $Q_2$ by matching records from each query 
whose grouping attributes  $A_{gb}$ have the same values.  
An outer join ensures that rows in either table have at least one output row even if there is no match.
Since the input queries, by definition, were grouped on $A_{gb}$, we are guaranteed exactly one output row for each group in $Q_1$ and $Q_2$.  Finally, $\pi$ copies the join attributes, computes $Q_1.y\ op\ Q_2.y$, and renames it as $y$.


$op$ is defined as ``$-$'' by default, however any binary arithmetic function is allowed.
As shorthand, $\oplus$ and $\ominus$ denote $\odot_+$ and $\odot_-$, respectively.
$\odot_{op}$ is symmetric iff $y_1\ op\ y_2 = y_2\ op\ y_1$.


\subsubsection{Union Composition $\cup$}

Union $V^* = V_1\cup_{qid,a}V_2$ composes the marks from both views into the same output view (\Cref{f:vca}(b)):
\begin{align*}
  Q^* & = \pi_{*, \hl{qid}}(Q_1) \cup \pi_{*, \hl{qid}}(Q_2) \\
  R^* &= \{qid\to\hl{$a$}\} \cup R_1 \hspace{2em} s.t. \ a \textrm{ is an unmapped vis attr}
\end{align*}
Each query $Q_i$ is augmented to track a unique identifier $qid$, so that rows from each query can be distinguished in $Q^*$.  $R^*$ additionally maps $qid$ to a visual attribute $a$ that is not already mapped in $R_1$.







\subsection{Safety}

Since \sys operators may take arbitrary combinations of marks as input, it is possible that the user may try to compose ``incomparable'' data together.  For instance, comparing stock price per hour with average stock price is sensible (safe), but comparing stock price with trading volume is not (unsafe).   

\sys defines safety based on the ability to map table $R_1$'s 
schema $A_{R_1}$ to table $R_2$'s schema $A_{R_2}$.  
Specifically, if their measures are the same, and if there is a 
unique mapping from each dimension in $A_{R_1}$ to a dimension 
in $A_{R_2}$ (or null).  
Dimensions can be mapped if they are the same.
In short, $A_{R_2}$ is a subset of $A_{R_1}$.



Although correct, this strict definition rejects many natural comparisons.
For instance, \sys cannot compare price per hour with price per day, because \texttt{hour}
and \texttt{day} are different dimension attributes.
Similarly, \sys cannot compare votes per district with votes per state.

