corollarytheorem corollary exampletheorem example definitiontheorem definition
propositiontheorem proposition lemmatheorem lemma conjecturetheorem conjecture
tcb@breakable

# Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-V
(Technical Report)

Roee Shraga, Renée J. Miller  Northeastern UniversityBoston, MA, USA
<EMAIL_ADDRESS>
(2022)

###### Abstract.

In multi-user environments in which data science and analysis is
collaborative, multiple versions of the same datasets are generated. While
managing and storing data versions has received some attention in the research
literature, the semantic nature of such changes has remained under-explored.
In this work, we introduce Explain-Da-V, a framework aiming to explain changes
between two given dataset versions. Explain-Da-V generates _explanations_ that
use _data transformations_ to explain changes. We further introduce a set of
measures that evaluate the validity, generalizability, and explainability of
these explanations. We empirically show, using an adapted existing benchmark
and a newly created benchmark, that Explain-Da-V generates better explanations
than existing data transformation synthesis methods.

††copyright: acmcopyright††journalyear: 2022††conference: ; ††booktitle:
;††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

PVLDB Reference Format:
PVLDB, XX(XX): XXX-XXX, 2023.
doi:XX.XX/XXX.XX ††This work is licensed under the Creative Commons BY-NC-ND
4.0 International License. Visit https://creativecommons.org/licenses/by-nc-
nd/4.0/ to view a copy of this license. For any use beyond those covered by
this license, obtain permission by emailing<EMAIL_ADDRESS>Copyright is held
by the owner/author(s). Publication rights licensed to the VLDB Endowment.
Proceedings of the VLDB Endowment, Vol. XX, No. XX ISSN 2150-8097.
doi:XX.XX/XXX.XX

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/shraga89/ExplainDaV.

##  1\. Introduction

Data is one of the most important ingredients in any decision making process.
The amount and size of data is growing and datasets are being reused for
multiple analyses. Data may be stored in different systems (e.g., data lakes
(Nargesian et al., 2019)), vary in their formats, and may or may not contain
metadata. Data projects often involve multiple users that work on datasets
conjointly or independently, creating different data versions. Accordingly,
_data versioning_ becomes an important ingredient in data management (Bhardwaj
et al., 2015). Nevertheless, even if versions are well managed (Bhattacherjee
et al., 2015), the documentation may be superficial, e.g., embedded in
filenames, which can be very inadequate. In addition, the collaboration itself
may not be structured or properly managed and each user may perform different,
often _undocumented_ processing steps on data (Kery et al., 2017, 2018; Kery
et al., 2019; Hohman et al., 2020; Zhang et al., 2020). For example, some
users may clean the data by removing rows or columns if they have duplicated
or missing information. Other users extract features, transforming the current
data to create new columns.

Current tools have limited data versioning support (Kery et al., 2017).
Generally speaking, data, as opposed to code, may be less documented (Kery et
al., 2019; Zhang et al., 2020) and data changes, even if documented, are
rarely accompanied by useful descriptions, making it difficult to understand
them (Hohman et al., 2020). Within a close collaboration group, a notebook
containing transformation code may be shared, but between organizations this
is rarely done. Consider, for example, the many versions of important datasets
shared on open data portals (home of the U.S. Government’s open data, 2020;
Data, 2020a, b) where transformations are generally not shared. The lack of
sufficient version documentation results in reduced reproducibility and trust
among users using the data (Kery et al., 2018; Zhang et al., 2020). While
managing and storing data versions has received attention in literature
(Bhattacherjee et al., 2015; Bhardwaj et al., 2015; Huang et al., 2017; Yilmaz
et al., 2018; Schüle et al., 2021), the semantic nature of such changes has
remained under-explored. We motivate our work using the following example.

(a) Dataset version created by UserA

(b) Dataset version created by UserB

Figure 1. Example dataset versions about movies created by two users.
Attribute names are provided in Example 1.

###### Example 1.

Figure 1 presents two dataset versions about movies. We discard the column
names from the figure to illustrate a realistic (data lake) scenario. For
readability, a0 is a tuple id, a1 represents the movie title, a2 measures the
movie runtime in minutes, a3 assigns a rating to the movie, and a4 provides
the genre of the movie. For convenience of presentation, lets assume that the
table on the bottom (Figure 1(b)) was created by UserB as a derivation of the
table on the top (Figure 1(a)) that was created by UserA. Even properly naming
the tables, e.g., Table 1(a) as data1_v1.csv and Table 1(b) as data1_v2.csv,
or knowing that Table 1(b) is derived from Table 1(a) (Bhardwaj et al., 2015),
does not help UserA to get a _semantic_ understanding of what UserB changed in
the table or, more importantly, what data processing steps UserB has
performed.

Example 1 illustrates the need for a semantic understanding of a new dataset
version. Aiming to fill this gap, this work provides the setup and new
solution to _explain_ the semantic changes between two dataset versions.
Specifically, our goal is to _automatically_ explain (in a simple user
friendly way) the steps leading from one version of dataset to the other. For
example, how was column a6 in Figure 1(b) created? or why was the fourth row
in Figure 1(a) deleted? Note that the changer’s intent, which is subjective,
cannot be truly reverse engineered. Our objective is to provide the other user
an accurate explanation, e.g., a set of functions, that describes the changes.
Following this goal, we return to our motivating example.

###### Example 2 (cont.).

Figure 2 illustrates an annotated version of Figure 1(b), that explains the
changes. In other words, Figure 2 reverse engineers the changes made by UserB
in a way that a user can understand. Specifically, UserB cleaned the rows that
contain NaN values (in this case m4) and extracted numerical features. The
certification of the movie, given in parenthesis in a1, was extracted to
create a5 and the column a6 converts the units of a2, the runtime of the
movie, from minutes to hours. Since the range of movie ratings (a3) is
limited, UserB also discretized the values to create four rating classes in
column a7. Aiming to examine the effect of title length (an effect found for
paper citations (Deng, 2015)) within the domain of movies, UserB added column
a8 that provides the length of titles from a1.

Figure 2. An interpretation of the changes between the dataset versions given
in Figure 1. The columns are colored based on their origin (e.g., a5 is blue
because it originates from the blue a1) and annotated column transformations
are given at the bottom. The annotated row transformation is given on the
right, in this case removing a row, which is also illustrated by diagonal
stripes over the row.

As illustrated in Example 1, there are a variety of possible transformations
(e.g., multiplying/dividing the values of a numeric column, e.g., a3, by a
constant), potentially creating an infinite possible number of changes to a
dataset. These changes can be vertical (changing columns) or horizontal
(changing rows), they can add information (adding columns/rows) or remove
information (removing columns/rows) and they can involve different data types,
e.g., textual to numeric (a1 to a8) or numeric to categorical (a3 to a7). In
addition, a user may also change a cell in the table, e.g., replacing the NaN
value in row m4 by 146.25 (the mean value of the other values in the column),
or perform a full-table operation, e.g., transposing the table. Transformation
discovery methods are used for multiple data management tasks including fuzzy
joins (Zhu et al., 2017), data wrangling (Bogatu et al., 2019), entity
consolidation (Deng et al., 2019) and more (Jin et al., 2017; He et al., 2020;
Abedjan et al., 2016; Harris and Gulwani, 2011) mainly focusing on textual
(text-to-text) transformations and consider the transformed values (rather
than the transformation itself). Our method mainly focuses on data versioning,
for which, the transformations themselves, as a means of explaining changes
among different dataset versions, is the main interest. Our resolved
transformations also cover transformations that involve, among others, numeric
transformations. The term “explanation” became quite common recently and may
be associated with multiple meanings. For example, both El Gebaly et al. (El
Gebaly et al., 2014) and Kim et al. (Kim et al., 2020) use data summaries as
explanations. Explain3D (Wang and Meliou, 2019), which shares a similar
context to ours, explains dataset disagreements with syntactic provenance-
based and value-based modification mappings. In this work the main component
of an explanation is a transformation that explains change. This paper makes
the following contributions.

(1) Semantic Data Versioning Definition: we define and solve a novel problem
of semantic data versioning by explaining the changes between two dataset
versions.
(2) Vertical and Horizontal Data Transformation Resolution Across Different
Data Types: we present a solution to the problem of semantic data versioning
that examines both vertical (adding/removing columns) and horizontal
(adding/removing rows) transformations that involve multiple data types.
(3) Semantic Data Versioning Metrics: we provide a set of evaluation measures
to examine the quality of explanations in terms of validity, generalizablity,
and explainability.
(4) Semantic Data Versioning Benchmark: we introduce a new data versioning
benchmark composed of 5 version-sets including 342 different dataset versions
representing a total of 1702 changes.111Code and benchmark are publicly
available (git, 2022).
(5) Empirical Evaluation: our experiments show that Explain-Da-V performs
better than multiple baselines on both our new version benchmark and on an
existing data science pipeline benchmark (Aut, 2022a). We analyze the impact
of different components of our solution on performance.

In this paper, we assume two tables are given where one is known to have been
derived from the other (i.e., is a version it) and we know a match between the
attributes and tuples the two tables share. This work focuses on “internal”
additions, deletions, or modifications (modeled as deletions followed by
additions). External additions, e.g., finding joinable tables (Zhu et al.,
2019) and joining them with a table to create a new version, are reserved for
future work.

##  2\. Related Work

We are, to the best of our knowledge, the first to address the semantic aspect
of data versioning. Yet, related research exists ranging from synthesizing
data transformations to exploring data change.

###  2.1. Data Versioning

Data versioning research mainly focus on developing version managers to
decrease the need for storing many versions of large datasets (Nargesian et
al., 2019). For example, DataHub provides a git-like interface to manage,
store, recreate, and retrieve versions using a directed version graph
(Bhardwaj et al., 2015). Follow-up research further studied the trade-off
between recreation and storage in a principled way analyzing six different
settings (Bhattacherjee et al., 2015). Recently, Schüle et al. presented
TardisDB (Schüle et al., 2021), an SQL extension to support version
management. TardisDB uses named branches over tables, to monitor table
versions and track their modification history. In contrast, we focus on the
semantic aspects of data versioning, zooming in on explaining the semantic
differences between dataset versions. Schema versioning has also been studied
(Roddick, 1995). Although schemata may change over time (Snodgrass et al.,
2008), which provides semantic hints to data change, we assume metadata is not
always complete and may be ambiguous (Nargesian et al., 2019). Hence, we focus
only on the versioning of the data itself.

Multiple methods find or discover related tables (Das Sarma et al., 2012;
Chapman et al., 2020) (e.g., joinable (Zhu et al., 2019) and unionable
(Nargesian et al., 2018; Khatiwada et al., 2023)). While different versions of
a table may be related and found using these methods, our work assumes that
the discovery has already been done and aims at providing a semantic
explanation for the differences between versions.

###  2.2. Data Change, Difference, and Integration

We assume that some match between the attributes and tuples of the versions is
given. This assumption is rooted in many years of data integration research,
exploring attribute matching (schema matching) (Rahm and Bernstein, 2001;
Shraga et al., 2020), tuple matching (entity resolution) (Elmagarmid et al.,
2006; Li et al., 2020), and others (Bellatreche and Wrembel, 2013; Miller,
2018; Khatiwada et al., 2022). Earlier works looked into change and copy
detection in structured data (Chawathe et al., 1996; Chawathe and Garcia-
Molina, 1997), which was later extended also to semi-structured documents such
as XML (Nierman and Jagadish, 2002; Cobena et al., 2002; Wang et al., 2003).

Acknowledging data change, Bleifuß et al. (Bleifuß et al., 2018) envision
systems that can interactively explore such change. They present a model of
what changed, where, when and how, using what they call a change-cube to
monitor the history of changes over time using methodologies such as time-
series clustering (Bornemann et al., 2018). DBChEx (Bleifuß et al., 2019) is a
tool to explore data and schema change using a set of exploration primitives.
While similar in nature, this line of work focuses mainly on how to _explore_
change aiming to answer questions such as “How many changes have there been in
recent minutes?” and “How old are the entities in table Y? When were they last
updated?” (Bleifuß et al., 2018, 2019). Our work focuses on local changes
between versions and _how_ the changes were performed (which transformations
were applied?), e.g., how did UserB create the table in Figure 1(b) from
Figure 1(a). Another related research area is explaining query answers (Roy et
al., 2015; Miao et al., 2019). Given a query and a database, they explain
query answers using the tuples in the given database, e.g., using provenance
(Cheney et al., 2009). We, in contrast, explain dataset changes using data
transformations. While changes can be thought of as a set of queries,
explanations for queries that involve non-trivial transformations (e.g.,
adding a5 in Example 1) cannot be explained only using the tuples.

###  2.3. Data Transformation By Example

The final related line of research we cover aims to automatically transform
data. Largely, given input and output tables (datasets) or their subsets
(examples), the goal of such approaches is to find a transformation (program)
such that if it is applied over the input we get the output. It is worth
noting that earlier work has referred to this problem as query reverse
engineering (Tran et al., 2014; Orvalho et al., 2020), which is roughly the
same idea, i.e., finding a query that generates the output using the input.
This line of work can be divided into two main groups.

The first group is rooted in a paradigm called programming-by-example (PBE)
(Jin et al., 2017; Singh, 2016; Zhu et al., 2017; Jin et al., 2019; Harris and
Gulwani, 2011; Bogatu et al., 2019; Singh and Gulwani, 2012; Gao et al.,
2018), where the goal is to synthesize a program that manipulates a given
input to get a given output. To do so, methods design different search spaces
(operators to be applied over the input) and apply different search
algorithms. For example, Foofah (Jin et al., 2017) creates a search space
using operators such as drop (delete a column) and split (separate a column by
some delimiter) and search the space using A* heuristic search. Clx (Jin et
al., 2019) also introduces string patterns such as regular expressions to the
search space and tokenizations. Data Diff (Sutton et al., 2018) applies a
search approach to “patch” transformations, summarizing distribution changes,
including one numeric patch (operator) supporting linear transformations with
pre-defined (randomly selected) parameters. Muller et al. describes
differences between relational databases with what they call “update distance”
(Müller et al., 2006) using a similar searching approach. Finally, Bogatu et
al. introduced functional dependencies to navigate the search space (Bogatu et
al., 2019), which we also use in our work.

The second group focuses on creating transformation repositories from external
sources such as Web Forms, Knowledge Bases (Abedjan et al., 2016; Özmen et
al., 2021), GitHub and Stackoverflow (He et al., 2018; He et al., 2020).
Transform Data by Example (TDE) (He et al., 2018), instead of searching
through a space of pre-defined possible operations, creates a search engine
where transformation functions are crawled from GitHub and Stackoverflow.
Instead of applying heuristic search such as A*, TDE ranks candidate functions
to find relevant functions. TDE was later extended to allow transformation
search based on patterns (He et al., 2020). DataXFormer (Abedjan et al., 2016)
and Proteus (Özmen et al., 2021) create a repository of tables from which
desired output values can be extracted.

A similar line of research revolves around resolving data preparation and
analysis transformations (Bavishi et al., 2019; Yan and He, 2020; Yang et al.,
2021). AutoPandas (Bavishi et al., 2019) focuses on Pandas library (Pan, 2022)
and aims to synthesize a program using pandas functions. Auto-pipeline (Yang
et al., 2021) extends the “by-example” paradigm to “by-target”, meaning that
the output the user provides is not necessarily aligned with the input and can
require table-reshaping operations (e.g., group by). Auto-pipeline comes in
two variations, namely, search (which is equivalent, yet extended to what is
described above) and deep reinforcement learning. The former can be a
candidate baseline for our approach. The latter requires training data which
we assume does not exist in our setting.

In contrast to PBE and query reverse engineering, we do not focus on matching
input to output. Rather than looking only at success rates (is the
transformation valid), our search is guided by the principle of creating
valid, generalizable, and explainable transformations. In our approach, these
transformations can be multi-dimensional (adding/removing attributes/tuples)
and address multiple data-types (e.g., numeric, categorial, and text
transformations). While our string-based transformation resolution is based on
an extended Foofah, we also support numeric transformations using explainable
machine-learning algorithms to _fit the appropriate transformation_ rather
than searching a very large space of possible transformations. We go beyond
Foofah to support text-to-numeric transformations (e.g., measuring the length
of a string) and text cleaning operations (e.g., stopword removal and
lemmatization).

##  3\. Semantic Data Versioning

A dataset is denoted by a table $T$, composed of a set of attributes
$T_{A}=\\{A_{1},\dots,A_{n}\\}$ and tuples $T_{r}=\\{r_{1},\dots,r_{m}\\}$.
Each tuple is defined as $r_{i}=\langle r_{i0},r_{i1},\dots,r_{in}\rangle$,
such that $r_{i0}$ is the tuple identifier and $r_{ij}$ ($j\neq 0$) is a value
assigned to the attribute $A_{j}$ in the tuple $r_{i}$. Often we may have two
datasets and know one was derived from the other but the actual transformation
code or documentation has been lost (Kery et al., 2017, 2018; Kery et al.,
2019; Hohman et al., 2020; Zhang et al., 2020). In what follows, we address
the problem of explaining the changes between two dataset versions.

Given two dataset versions, $T$ and $T^{\prime}$, we assume the latter, wlog,
is a _derived table_ , i.e., a user changed the table $T$ and as a result
obtained the table $T^{\prime}$ with
$T^{\prime}_{A}=\\{A^{\prime}_{1},\dots,A^{\prime}_{n}\\}$ and tuples
$T^{\prime}_{r}=\\{r^{\prime}_{1},\dots,r^{\prime}_{m}\\}$. We assume that an
alignment between $T_{A}$ and $T^{\prime}_{A}$ (attribute-match, denoted
$\Sigma_{A}$) is given and that tuples in $T$ and $T^{\prime}$ with the same
identifier ($r_{0i}$ and $r^{\prime}_{0i}$) are assumed to represent the same
real world entity. An attribute $A_{i}\in T$ (or $A^{\prime}_{j}\in
T^{\prime}$) is considered unmatched if it does not appear in $\Sigma_{A}$. A
record $r_{i}\in T$ (or $r^{\prime}_{j}\in T^{\prime}$) is considered
unmatched if there is no record in $T^{\prime}$ (respectively, $T$) with the
same identifier.

Given an attribute-match $\Sigma_{A}$, we define the changes between the two
dataset versions to be explained using a three symbols notation. The first
refers to whether the dataset is the left-hand one (L) or the right-hand
(revised) one (R), the second to whether it is the matched ($\nabla$) or
unmatched (unmatched is also called delta ($\Delta$)), and the third refers to
attributes (A) or tuples (r). Specifically, $L\Delta_{A}$(left-hand delta
attributes) and $L\nabla_{A}$(left-hand matched attributes) are the set of
unmatched (delta) and matched (consistent) attributes in $T$, respectively.
Similarly, $R\Delta_{A}$ and $R\nabla_{A}$ are the unmatched and matched
attributes in $T^{\prime}$. Using these sets, we create _projected_ tuples.
Let $r_{j}$ be a tuple of table $T$, the projected tuple is given by
$\pi_{L\nabla_{A}}[r_{j}]$, projecting out non-matching attributes. Given such
projected tuples, we can define similar sets for tuples, namely
$L\Delta_{r}$(left-hand delta tuples), $R\Delta_{r}$(right-hand delta tuples),
$L\nabla_{r}$(left-hand consistent tuples) and $R\nabla_{r}$(right-hand
consistent tuples). We summarize this notation in Table 1. Intuitively, we are
interested in explaining the deltas between the datasets, i.e., $L\Delta_{A}$,
$R\Delta_{A}$, $L\Delta_{r}$, and $R\Delta_{r}$.

###### Example 1.

Given the dataset versions in Figures 1(a) ($T$) and 1(b) ($T^{\prime}$), the
attribute-match is simply given by aligning the columns headers (e.g., a2
$\leftrightarrow$ a2). The tuple ids are given under a0 (e.g., m1
$\leftrightarrow$ m1). The following are the change sets: $L\Delta_{A}$=
$\emptyset$ (no removed columns), $R\Delta_{A}$= {a5, a6, a7, a8} (four added
attributes), $L\Delta_{r}$= {m4} (one removed tuple), and $R\Delta_{r}$=
$\emptyset$ (no added tuples).

###  3.1. Change Explanations

We use the term _explanation_ to refer to a user friendly way to interpret a
change between two relations. Intuitively, an explanation is a transformation
$\mathcal{P}$ from an origin $\mathcal{O}$ to a goal $\mathcal{G}$. Formally,
an explanation $\mathcal{E}$ is defined with respect to a _goal_ $\mathcal{G}$
with a name $\mathcal{G}_{name}$ and an associated relation
$\mathcal{G}_{relation}$ it represents. As the goal, the origin is also
associated with a name ($\mathcal{O}_{name}$) and a relation
($\mathcal{O}_{relation}$). A transformation $\mathcal{P}$ is an expression
that transforms the origin relation $\mathcal{O}_{relation}$ into the goal
relation $\mathcal{G}_{relation}$. The origin relation may also be empty. A
formal definition is as follows

###### Definition 2 (Explanation ($\mathcal{E}$)).

Let $\mathcal{G}$ be a goal. An _explanation_
$\mathcal{E}_{\mathcal{G}}=(\mathcal{O},\mathcal{P})$ of $\mathcal{G}$ is
composed of an origin $\mathcal{O}$ and a transformation $\mathcal{P}$, such
that $\mathcal{G}_{relation}=\mathcal{P}(\mathcal{O}_{relation})$.

###  3.2. Explaining Dataset Changes

We focus on two _orientations_ of explanations, namely, _vertical_
explanations and _horizontal_ explanations. We further distinguish between
_removal_ and _addition_ explanations. Modifications can be modeled as a
removal followed by an addition. Explanation types differ in the type of
relations that the origin and the goal represent.

The goal ($\mathcal{G}_{relation}$) and origin ($\mathcal{O}_{relation}$)
relations are defined with respect to versions $T$ or $T^{\prime}$.
Specifically, the relations $\mathcal{O}_{relation}$ and
$\mathcal{G}_{relation}$ can be a projection (subset of attributes) or
selection (subset of tuples) over either $T$ or $T^{\prime}$. In vertical
explanations (adding or removing attributes), the associated goal and origin
names ($\mathcal{G}_{name}$ and $\mathcal{O}_{name}$) are the projected
attributes. For horizontal explanations (adding or removing tuples),
$\mathcal{G}_{name}$ and $\mathcal{O}_{name}$ correspond to the set of tuple
ids in the subset. When clear from context, we refer to the goal and the
origin by their names.

Table 1. Notations used in the paper. The changes $L\Delta_{A}$, $L\nabla_{A}$, $L\Delta_{r}$, and $L\nabla_{r}$ are defined wrt the left-hand table $T$. The right-hand notation can be obtained by replacing $T$ with $T^{\prime}$ below. | Notation | Meaning
---|---|---
Basic | $T$ | Left-hand dataset
$T^{\prime}$ | Right-hand (revised) dataset
$T_{A}$ | The attribute set of dataset $T$
$T_{r}$ | The tuple set of dataset $T$
Changes | $L\Delta_{A}$ | The set of unmatched attributes in T
| $\\{A_{i}:A_{i}\in T_{A}\wedge\nexists A^{\prime}_{j}\in
T^{\prime}:(A_{i},A^{\prime}_{j})\in\Sigma_{A}\\}$
$L\nabla_{A}$ | The set of matched attributes in T
|  $T_{A}\setminus$ $L\Delta_{A}$
$L\Delta_{r}$ | The set of unmatched tuples in T
| $\\{\pi_{L\nabla_{A}}[r_{j}]:r_{j}\in T_{r}\wedge\nexists r^{\prime}_{i}\in
T:r_{0i}=r^{\prime}_{0i}\\}$
$L\Delta_{r}$ | The set of matched tuples in T
|  $\\{\pi_{L\nabla_{A}}[r_{j}]:r_{j}\in T_{r}\\}\setminus$$L\Delta_{r}$

###### Example 3.

Recall the versions in Figures 1(a) ($T$) and 1(b) ($T^{\prime}$). An example
explanation for a goal $\mathcal{G}=(a6,\pi_{a6}[T^{\prime}])$ is composed of
an origin $\mathcal{O}=(a2,\pi_{a2}[T])$ and a transformation
$\mathcal{P}=\pi_{a2}[T]\div 60$, which is tuple-based, i.e., divide each
tuple in $\pi_{a2}[T]$ by 60. When clear from context, we denote this
explanation as $\mathcal{E}_{a6}=(a2,a2\div 60)$.

Recalling the change sets, we aim to find vertical addition explanations for
$L\Delta_{A}$, vertical removal explanations for $R\Delta_{A}$, horizontal
addition explanations for $L\Delta_{r}$, and horizontal removal explanations
for $R\Delta_{r}$. An explicit problem definition, that relies on the quality
of explanations is provided in Section 7.2.

###### Example 4.

Recall the versions of Figure 1, annotated changes in Figure 2, and
$L\Delta_{A}$, $R\Delta_{A}$, $L\Delta_{r}$, and $R\Delta_{r}$, defined in
Example 1. A possible set of explanations to explain the changes is as follows

  * $\mathbf{\mathcal{E}_{a5}}$

$=(a1,$ extract(a1, ‘(.*?)’)$)$

  * $\mathbf{\mathcal{E}_{a6}}$

$=(a2,a2\div 60)$

  * $\mathbf{\mathcal{E}_{a7}}$

$=\left(a3,\begin{cases}4,&\text{if }9\leq a3\\\ 3,&\text{if }8\leq a3<9\\\
2,&\text{if }7\leq a3<8\\\ 1,&\text{otherwise}\end{cases}\right)$

  * $\mathbf{\mathcal{E}_{a8}}$

$=(a1,$ len(a1)$)$

  * $\mathbf{\mathcal{E}_{m4}}$

$=(\emptyset,$ has_NaN$)$

Most of the explanations are self-explanatory (as they should be). Interesting
cases are $\mathcal{E}_{a5}$, that extracts value in parenthesis. Another
example is the horizontal explanation $\mathcal{E}_{m4}$, for which the origin
is an empty set and the tuple was removed due to a NaN (null equivalent)
value. Although the goal is $m4$, the transformation we find is one that
removes $m4$ and no other tuples.

Explain-Da-V is a data-driven222Data-driven reflects that we only use data
values (we do not use meta-data). method composed of four parts corresponding
to adding/removing attributes/tuples. We first describe our core explanation
methods (Section 4), which are then utilized to explain vertical (Section 5)
and horizontal changes (Section 6).

##  4\. Core Semantic Explanation Methods

Our core explanation methods rely on fitting an appropriate explanation
methodology to data types we find in the origin $\mathcal{O}$ and the goal
$\mathcal{G}$. Rather than the traditional database attribute types (strings,
integers, floats, etc.), given the nature of our analysis, we look into ML
feature types (Shah et al., 2021). We focus on three main types, namely,
_Numeric_ , _Categorical_ and _Textual_ (mixed types are considered textual),
which characterizes the core changes Explain-Da-V covers.333Explain-Da-V can
be easily extended to support additional types such as dates. Aiming to
resolve a high variety of changes, we develop methods that are built on top of
different types of origin sets using multiple approaches that exploit the type
of change. Accordingly, Explain-Da-V can be applied over any pair of versions,
regardless of how far apart the versions are (meaning how many transformations
have been applied). If an explanation is not found for a specific change, it
is declared idiopathic (unexplained).

Note that among the different changes, the vertical additions are the most
common and complex and, thus, the presented methods mostly address such a
scenario. Specifically, for the presentation of methods, we assume the goal as
a single attribute (a right-hand attribute to be explained) with its data
values. Also, given a goal, finding its origin is not straight forward. For
the moment, assume the origin is the original left-hand table $T$. We discuss
a method to “find” an origin, given a goal, in Section 4.6.

###  4.1. Numeric Change Explanations

Whenever we need to explain a numeric goal using an origin that contains
numeric data, we position the problem as _regression_ in which the origin
relation tuples are treated as independent variables and the goal relation
tuples as dependent variables. Aiming at explainable transformations, we build
on top of linear regression (Burkart and Huber, 2021). To reduce model
complexity and prevent over-fitting (Thrampoulidis et al., 2015), we
experiment with Lasso and Ridge regularization.

###### Example 1.

A numeric transformation is given in Figure 1(b), where explaining a6 can be
resolved by fitting a regressor $\frac{1}{60}\cdot a2$.

Not all numeric transformations can be covered by a linear function.
Accordingly, to allow richer, more flexible, numeric transformations, we
_extend_ the feature space (i.e., the origin) by generating additional
features. Note that while these extensions are motivated by commonly used data
science and engineering operations (Kuhn and Johnson, 2019), they do not (and
cannot) cover every possible transformation.

Polynomial Regression and Inter-relation Features: To explain polynomial
transformations, we generate additional polynomial features (Edwards, 2002)
over $\mathcal{O}$. Given a predefined degree $d$, the polynomial extension of
$\mathcal{O}$ is given by $poly(\mathcal{O})$ whose attributes correspond to
$\\{A_{i}^{2},\dots,A_{i}^{d},\forall A_{i}\in\mathcal{O}_{name}\\}$. The
extended origin relation is created on a tuple level by applying the
associated operation. For example, the attribute $A_{i}^{2}$ of the tuple
$r_{j}$ in the extended relation would get the value in attribute $A_{i}$
squared, meaning $\pi_{A_{i}}[r_{j}]^{2}$. We also introduce feature inter-
relation, that is, multiplication and division between different attribute
values in $\mathcal{O}$. Note that addition and subtraction are already
supported when using linear regression. The inter-relation extension of
$\mathcal{O}$, $inter(\mathcal{O})$ corresponds to $\\{A_{i}\cdot
A_{j},A_{i}\div A_{j}\dots,\forall A_{i},A_{j}\in\mathcal{O}\wedge A_{i}\neq
A_{j}\\}$. Also here the transformations are done on the tuple level, e.g.,
the attribute $A_{i}\cdot A_{j}$ of the tuple $r_{j}$ would get the value
$\pi_{A_{i}}[r_{j}]\cdot\pi_{A_{j}}[r_{j}]$. The extensions can also be
applied consecutively, e.g., $inter(poly(\mathcal{O}))$ to create attributes
such as $A_{i}\div A_{j}^{2}$ to resolve, for example, the BMI formula
($kg\div m^{2}$). For example, recall Figure 1 and let
$\mathcal{O}_{name}=\\{a_{2},a_{3}\\}$, the extended features using
$poly(inter(\mathcal{O}))$ with $d=2$ would be:

Figure 3. Polynomial and Inter-relation extensions over a3 and a4 Figure 1(a).

Mathematical Transformations: When generating new features over numeric data,
it is also common to use mathematical operations (Brook and Arnold, 2018).
Specifically, to support this type of explanation we generate a math extension
of $\mathcal{O}$, $math(\mathcal{O})$, with the attributes
$\\{log(A_{i}),sqrt(A_{i}),reciprocal(A_{i}),exp(A_{i}),\dots,\forall
A_{i}\in\mathcal{O}\\}$, where $sqrt(A_{i})=\sqrt{A_{i}}$,
$reciprocal(A_{i})=A_{i}^{-1}$, and $exp(A_{i})=e^{A_{i}}$. The
transformations are tuple-based, e.g., the feature $log(A_{i})$ of the tuple
$r_{j}$ in the extended relation would get the value
$log(\pi_{A_{i}}[r_{j}])$. For illustration, recall our running example, the
extended features using $math(\\{a_{2},a_{3}\\})$ would be:

Figure 4. Math extension over a3 and a4 Figure 1(a).

Global Aggregations: We also generate aggregate features. This extended set is
especially important when looking at one of the most common transformations in
machine learning, that is, (value) normalization (Zheng and Casari, 2018). We
introduce an extension of $\mathcal{O}$, $agg(\mathcal{O})$, with the
attributes $\\{sum(A_{i}),mean(A_{i}),max(A_{i}),min(A_{i})\dots,\forall
A_{i}\in$ $\mathcal{O}\\}$. Here, although assigned on a tuple level, the
extended values are computed over all the values in the attribute. For
example, the feature $sum(A_{i})$ of the tuple $r_{j}$ would get the value
$\sum_{r_{ik}\in\pi_{A_{i}(T)}}r_{ik}$. Then, if a user applies a sum
normalization over $A_{i}$, the feature-set $agg(inter(\mathcal{O}))$ that
includes the feature $A_{i}\div sum(A_{i})$ would be able to resolve and
explain this added attribute. Similarly, in the case of min-max normalization
(Zheng and Casari, 2018) the additional features of $min(A_{i})$ and
$max(A_{i})$ can be used to generate accurate explanations. Another example is
the common collaborative filtering transformation of subtracting the mean
value ($A_{i}-mean(A_{i})$) (Marlin, 2004). Recalling our running example and
let $\mathcal{O}=\\{a_{2},a_{3}\\}$, the extended features using
$agg(\mathcal{O})$ would be:

Figure 5. Aggregation extension over a3 and a4 Figure 1(a).

An extended feature-set is used to fit a regressor that assigns coefficients
for extended feature-set. A perfect regressor would be able to deal one all-
inclusive feature-set (i.e., $poly(inter(\dots(\mathcal{O})\cup
inter(poly(\dots(\mathcal{O}),\dots$); yet, since it is not realistic to
expect that (from an explainable regressor), we apply each set independently
(power-set of the extensions) and generate multiple “possible” explanations.
Section 7.4 addresses the issue of choosing among them.

Note that the transformation is “learned” (fitted) only based on the two
dataset versions $T$ and $T^{\prime}$ and no additional training data is
required. Section 5.1 discusses the main application of numeric change
explanations and illustrates it using multiple examples.

###  4.2. Categorical Change Explanations

Aiming to explain a categorical goal using an origin relation that contains
numeric, we position the problem as _classification_ , in which the tuples of
the origin relation are treated as explanatory variables and the goal relation
tuples are used as the output class labels. The output class can be binary
(e.g., is movie longer than two hours) or multi-class (e.g., a7, Example 1).
Aiming at explainability, we focus on decision trees (Burkart and Huber,
2021). Note that decision trees cover only explanations that can be
represented as disjunction of conjunctions (Mitchell, 1997). Each path from
the root to a leaf corresponds to a conjunction and the tree is the
disjunction of these conjunctions.

$False$$True$$False$$True$$False$$True$

###### Example 2.

Figure 1(b) provides an example a categorical transformation, namely, a7,
which can be resolved with the help of the following decision tree.

###  4.3. Textual Change Explanations

When the origin and/or goal are textual, we follow the PBE approach (see
Section 2.3), using a search-based solution. Specifically, we adopt an
existing framework called Foofah (Jin et al., 2017). The PBE solution is
composed of designing a space of possible operators and a search algorithm.
The search algorithm (A*, following Foofah) navigates the space of operators
using a heuristic function (based on dissimilarity of tables) that estimates
the cost of any proposed partial solution. The space is pruned to boost search
speed (Jin et al., 2017).

####  4.3.1. Textual-to-Textual

Addressing data versioning, we extend the traditional PBE operators to include
operators the cover frequent text-processing steps (Vijayarani et al., 2015),
including text lowering, lemmatization, removal of special charterers (e.g.,
punctuations and numeric values) and tokens (e.g., stop-words and html tags).
All implemented additional operators for foofah are given in our repository
(Foo, 2022a).

Unlike Foofah, we also consider textual-to-numeric and textual-to-categorical.
Note that although in recent years transformer-based models have become a
standard way to extract (latent) features from text, traditional feature
engineering over text, that is, extracting manual numeric and categorical
features from textual values, is still an important ingredient in NLP (Da San
Martino et al., 2019; Kovaleva et al., 2019; Chernyavskiy et al., 2021) and in
other research disciplines such as HCI (Cao et al., 2021) and information
management (Gkikas et al., 2022).

####  4.3.2. Textual-to-Numeric

The search space defined for resolving this kind of transformation includes a
meta-operation that counts the occurrences of some pattern $pat$ in a value
(count${}_{pat}(r_{ij})$), where $r_{ij}$ is a value in the table, see Section
3). Using this operation we can define operations such as number_of_words =
count${}_{\text{`␣'}}(r_{ij})$ and number_of_questions =
count${}_{\text{`?'}}(r_{ij})$. We also cover counting a pre-defined set of
stop-words and punctuation marks.

####  4.3.3. Textual-to-Categorical

We define a similar meta-operation for a pattern existence
(contains${}_{pat}(r_{ij})$), which is used to generate operations such as
contains_percent = contains${}_{`\%^{\prime}}(r_{ij})$.

###### Example 3.

Figure 1(b) provides an example of textual-to-textual transformation, namely,
a5, which can be resolved with the help of the foofah environment in its
original implementation. Specifically, if we consider a1 as an origin, foofah
would consider $\pi_{a1}[T]$ as input examples and $\pi_{a5}[T^{\prime}]$ as
corresponding output examples (goal in our terms) and synthesize a tuple-based
data transformation program (1) t = split(t, 0, ‘(’), (2) t = split(t, 1,
‘)’), (3) t = drop(t, 0), (4) t = drop(t, 2)
the tuple value Moana (U), for example, would be transformed as follows [Moana
, U)] $\rightarrow$[Moana , U, ] $\rightarrow$ [U, ] $\rightarrow$ U.

Resolving a8 requires Explain-Da-V’s extensions that includes textual-to-
numeric transformations (len()).

Note that Foofah aims to synthesize transformations using a given set of
example tuples, and is often able to do so using just a few examples. Our
goal, in contrast, is to generate an explanation that correctly explains a
full table transformation (a dataset version). Hence, our tremendous expansion
of the search space beyond text-to-text transformations plays a critical role.
Moreover, Section 4.6 introduces a technique that prunes the search space in
this context.

###  4.4. Categorical-encoding Change Explanations

Whenever dealing with mixed types, textual and categorical values may be
encoded. A common encoding approach, which we use here, is one-hot-encoding
(Rodríguez et al., 2018). Let $A_{i}\in\mathcal{O}$ be a textual/categorical
attribute in the origin. One-hot-encoding of this attribute generates an
additional attribute for each unique value (or category) in $A_{i}$ and
assigns a value of 1 to each tuple that corresponds to this value (category).
This addition, not only allows the resolution of this common encoding scheme,
but also a richer representation that can be used to resolve other types of
encoding (e.g., ordinal encoding) and additional transformations. Such
encodings are also commonly used in data preparation for machine learning
(Brownlee, 2022). Recalling Example 1, if a user aims to predict the rating of
a movie, extracting features such as Is_Drama or Is_Action can be beneficial
for learning.

###  4.5. Reshaping Change Explanations

Generally group-by is a table-reshaping operation (Yang et al., 2021), i.e., a
natural attribute-match and tuple-match do not exist. However, when it comes
to feature engineering, group-by can also be used to generate aggregated
features based on some other attribute. The latter is addressed in a manner
that is similar to numeric change explanations. An extended origin, similar to
Section 4.1, would be created for each numeric attribute $A_{j}\in T_{A}$ with
respect to each textual/categorical attribute $A_{i}\in\mathcal{O}$
independently or conjointly (grouping by multiple attributes). We use an SQL
syntax for clarity.

SELECT $A_{i}$, mean($A_{j}$), max($A_{j}$)…
FROM T
GROUP BY $A_{i}$

Figure 6. Group by Query

A helper query (Figure 6) can be used to generate the extended group-by
features of the numeric attribute $A_{j}\in T_{A}$ with respect to a
textual/categorical attribute $A_{i}\in\mathcal{O}$.

If more than one numeric attribute exists, it will be added to the GROUP BY
and SELECT clauses. Using this helper query, by joining it with the origin, we
obtain the additional possible attributes. Consider, for example, the
attribute a4 of Figure 1(a). The additional aggregation features would be
generated over the numeric attributes a2 and a3 and joined into the table, as
illustrated in Fig. 7. Among these, we can find the mean a2 (runtime) and a3
(rating) per a4 (genre), supporting such explanations.

Figure 7. Groupby feature extension over a3 and a4 Figure 1(a).

We also consider the reshaping scenario introduced in previous work, e.g.,
(Yang et al., 2021). Reshaping is often considered as a possible operation
that can be applied over a table throughout the search (see Section 2.3). We
introduce an alternative data-driven approach. Specifically, reshaping is
associated only with attribute-match when there is no tuple-match. We
explicitly reshape the table using the query of Figure 6 and fit a regressor
over it. Currently, Explain-Da-V does not support other reshaping
transformations such as transpose and pivot, which we intend to explore in
future work.

###  4.6. Finding the Origin

In our discussion so far, we have assumed that the origin for the
transformations $\mathcal{P}$ is the original relation $T$. However, we can
make our search more efficient if we can determine that for a specific goal,
the origin is only a portion of $T$. Accordingly, we aim to _“find the
origin”_. Different from some related literature where the input-output scope
is clear (see Section 2.3), in data versioning we do not know what was used to
derive a specifical goal. Hence, our approach first searches for an origin for
the transformation.

A naïve solution to use all available data values. For example, in the context
of adding attributes, using all attributes of $T$ as an origin, i.e.,
$\mathcal{O}=(T_{A},T)$. The problem with this method is twofold. First,
unrelated attributes may serve as noise when aiming to find a proper
transformation for the goal. For example, referring back to Example 1, aiming
to resolve a5 using all attributes (a1-a4) presents a much larger search space
than aiming to resolve it using a2. A second issue has to do with the data
types. Using a numeric change explanation (Section 4.1) may be more beneficial
than a textual change explanation (Section 4.3). For example, using a2 as an
origin to explain a5 instead of using a1 to a4.

When examining the creation of a new attribute from existing attributes, we
observe a side effect of creating a _functional dependency_ between the origin
and the new attribute (goal). For example, if two movies have the same runtime
in minutes (a2), they will have the same runtime in hours (a5), which, by
definition constructs a functional dependency between a2 and a5. Accordingly,
we use a functional dependency discovery algorithm (Papenbrock et al., 2015)
to find the origin.444In our experiments we use a discovery algorithm called
FDEP (Flach and Savnik, 1999). We find dependencies in which our goal is the
dependent set and the discovered determinant is used as the origin. Note that
there can be more than one attribute set that determines the goal and
accordingly multiple origins may be generated.

We analyze all determining attribute sets by considering each one of them as a
candidate origin. Accordingly, multiple explanations may be generated for a
goal. Section 7.4 describes how we choose among them. Specifically, we rank
the determinants by size and cardinality and, if desired, an early stop
condition can be introduced based on the size or quality of the discovered
transformation.

###### Example 4.

Recall Figure 1 and consider attribute a7 as a goal. Since the example tables
are small, any combination of attributes in {a1, a2, a3, a4} can be considered
as an origin. If no high quality explanations are found for singleton
attributes, the algorithm can consider combinations of attributes. In a larger
real example, only a few attributes or combinations of them may be an origin.

##  5\. Explaining Vertical Changes

With our arsenal of explanation methods, we now consider how to use them to
explain changes. We begin with attribute additions, after which, we describe
our approach to handling attribute removal.

###  5.1. Addition Explanations for $R\Delta_{A}$

Adding an attribute is a very common operation in data science, mainly
revolving around data preparation and feature engineering for machine learning
(ML) (Zheng and Casari, 2018). Added attributes are usually a result of
applying some transformation over the existing data. We first find the origin
(Section 4.6) an then utilize the core explanation methods (Section 4) to find
transformations that, when applied to the origin relation, generate the
desired goal relation. Figure 8 provides a sketch of the approach (left and
middle parts) and highlights its main novelties (right part) in the context of
adding attributes.

Figure 8. Explaining attribute additions

1 Input: A set of attributes to-be-explained $R\Delta_{A}$

2 Output: A set of explanations for each attribute $\mathcal{E}_{R\Delta_{A}}$

3 $\mathcal{E}_{R\Delta_{A}}$ := $\emptyset$

4 for  _$A_{i}\in R\Delta_{A}$_ do

5 $\mathcal{E}_{A_{i}}$ := $\emptyset$; $\mathcal{O}_{A_{i}}$ := _find origin_
(Section 4.6)

6 for  _$\mathcal{O}\in\mathcal{O}_{A_{i}}$_ do

7 if  _$A_{i}$ is numeric_ then

8 if  _$\mathcal{O}$ is numeric_ then

9 $\mathcal{E}^{\mathcal{O}}_{A_{i}}\leftarrow$ Numeric Explanations (Section
4.1)

10

11 else

12 $\mathcal{E}^{\mathcal{O}}_{text}\leftarrow$ Textual Explanations (Section
4.3)

13 $\mathcal{E}^{\mathcal{O}}_{encode}\leftarrow$ Encoding Explanations
(Section 4.4)

14 $\mathcal{E}^{\mathcal{O}}_{reshape}\leftarrow$ Reshaping Explanations
(Section 4.5)

15
$\mathcal{E}^{\mathcal{O}}_{A_{i}}\leftarrow\mathcal{E}^{\mathcal{O}}_{encode}\cup\mathcal{E}^{\mathcal{O}}_{reshape}$

16

17 else if  _$A_{i}$ is categorical_ then

18 if  _$\mathcal{O}$ is numeric_ then

19 $\mathcal{E}^{\mathcal{O}}_{A_{i}}\leftarrow$ Categorical Explanations
(Section 4.2)

20

21 else

22 $\mathcal{E}^{\mathcal{O}}_{text}\leftarrow$ Textual Explanations (Section
4.3)

23 $\mathcal{E}^{\mathcal{O}}_{encode}\leftarrow$ Encoding Explanations
(Section 4.4)

24 $\mathcal{E}^{\mathcal{O}}_{reshape}\leftarrow$ Reshaping Explanations
(Section 4.5)

25
$\mathcal{E}^{\mathcal{O}}_{A_{i}}\leftarrow\mathcal{E}^{\mathcal{O}}_{encode}\cup\mathcal{E}^{\mathcal{O}}_{reshape}$

26

27 else if  _$A_{i}$ is textual_ then

28 $\mathcal{E}^{\mathcal{O}}_{A_{i}}\leftarrow$ Textual Explanations (Section
4.3)

29

30
$\mathcal{E}_{R\Delta_{A}}\leftarrow\mathcal{E}_{R\Delta_{A}}\cup\mathcal{E}_{A_{i}}$

31

Return:$\mathcal{E}_{R\Delta_{A}}$

Algorithm 1 Explaining Attribute Additions

Explain-Da-V attribute addition explanation algorithm is provided in Algorithm
1. Explain-Da-V works iteratively, aiming to resolve each added attribute
(i.e., the goal $\mathcal{G}=(A_{i},\pi_{A_{i}}[T^{\prime}])$) at a time
(Lines 1-1). After a set of possible origins $\mathcal{O}_{A_{i}}$ is found
(Line 1), we utilize the core explanation methods to generate a set of
explanations $\mathcal{E}^{\mathcal{O}}_{A_{i}}$ for each origin (Lines 1-1).
For example, if a numeric origin is found for a numeric goal (Line 1),
Explain-Da-V uses the numeric explanation method (Section 4.1). Note that
multiple explanations are generated for each target, for which we introduce a
search strategy in Section 7.4. We illustrate it over Figure 9, which provides
an additional version of the table in Figure 1(a).

Figure 9. Dataset version created by UserC over Figure 1(a).

###### Example 1.

Among the new added attributes a9 and a10 are numeric (Lines 1). The attribute
a9 is a (sum) normalization of the values in a3 (normalized rating). Explain-
Da-V would first find its origins (Line 1). As in the case of a6 (see Example
4), also a9 can be determined by multiple attribute sets. Among the possible
origins, consider $\mathcal{O}=$a3. Since both a3 and a9 are numeric, Explain-
Da-V uses numeric change explanations (Line 1). Zooming in on the method
(Section 4.1), a baseline explanation will be generated by fitting a regressor
over $\mathcal{O}$. Then, different extensions will be applied over the
origin, each will be associated with an explanation by fitting a regressor.
Among the generated extensions we will find $agg(inter(\mathcal{O}))$, that
contains the feature a3$\div$sum(a3) over which a transformation
a9=a3$\div$sum(a3) will be fitted to generate an explanation
$\mathcal{E}_{a9}$ $=(a3,a3\div sum(a3))$ that will be added to
$\mathcal{E}^{\mathcal{O}}_{a9}$. Similarly, a10 is determined by multiple
attribute sets. Among them, consider $\mathcal{O}=${a2, a3}, over which the
following explanation will be generated $\mathcal{E}_{a10}$
$=(\\{a2,a3\\},60\cdot a3\div a2)$ (rating per hour) and added to
$\mathcal{E}^{\mathcal{O}}_{a10}$.

$True$$False$

###### Example 2 (cont.).

Next we look at a11, which is categorical, and for example, consider the
origin $\mathcal{O}=$a3. Accordingly, Explain-Da-V uses categorical change
explanations (Line 1) and might fit the following decision tree to explain
a11. Note that a11 might been created by applying a3¿8.5 which differs from
Explain-Da-V’s data-driven explanation. Our goal however is to provide an
accurate explanation which both are. Interestingly, if we consider a2 as an
origin we can derive a similar decision tree rooted at $a2>150$. These issues
refer to the _generalizability_ of explanations which will be discussed in
Section 7.

The added attribute a12 is textual and focuses on text cleaning. Consider an
origin $\mathcal{O}=$a1, Explain-Da-V will execute Line 1 and specifically
Section 4.3.1 which describes text-to-text transformations. The resolved
transformation includes removing punctuation marks (e.g., ‘(’) and numeric
values (‘13’) and lowering the text. Note that such a transformation requires
our extensions to Foofah and would not be accurately resolved using the
original implementation of Foofah (Jin et al., 2017). A textual-to-categorical
(Section 4.3.3) example would be to use ‘contains_multiple_words?’, in this
case the tuples m1 and m3 would get the value 1 and m2 and m5 the value 0.

Next, consider a13, which is numeric and among possible origins, consider
$\mathcal{O}=${a3,a4}, which is mixed. Explain-Da-V would turn to encoding
(Line LABEL:line:encode) and reshaping (Line LABEL:line:reshape). Consider the
latter and note that new generated features are illustrated in Figure 7.
Explain-Da-V will generate an explanation using the transformation
$1\cdot(mean(a3)\text{ }by\text{ }a4)$ with represents a group by a4 and
computing the mean of a3 (mean rating by genre).

Finally, attribute a14 is categorical and consider, a4 as an origin. In
addition to applying trying to find textual explanations (Line 1), Explain-
Da-V would also turn to encoding (Line 1) and reshaping (Line 1) explanations.
Consider the former and note that a14 is an ordinal encoding of attribute a4
(Drama$\rightarrow$1, Action$\rightarrow$2, Animation$\rightarrow$3). The
three encoded attributes, namely is_Drama, is_Action? and is_Animation? are
used to resolve a14. Note that in a real-world scenario, an attribute like a14
would not necessarily be recognized as a categorical (e.g., high cardinality
or misclassification as a numeric value). In this case Explain-Da-V would turn
to Line 1 resulting in the transformation $1\cdot$is_Drama? \+
$2\cdot$is_Action? \+ $3\cdot$is_Animation?.

###  5.2. Removal Explanations for $L\Delta_{A}$

Removing attributes is less common and usually include superficial
transformations. We treat each attribute in $L\Delta_{A}$separately as a goal.
We cover two main types of explanations for removal reflecting data cleaning
(removing duplicated and noisy attributes).

First, we examine a _table-independent_ attribute removal, which in our terms
reflects an empty origin ($\mathcal{O}=\emptyset$). Specifically, we use a
threshold to decide whether a attribute was removed because it has too many
(above a threshold) missing (NaN) values.555The threshold can be treated as an
hyper-parameter or a user-provided input. In this case an explanation for a
removed attribute $A_{i}\in L\Delta_{A}$ will be in the form of
$\mathcal{E}_{A_{i}}=(\emptyset,\text{`contains missing information'})$.
Formally, the ‘contains missing information’ can be defined as
$A_{i}=\begin{cases}\emptyset,&\text{if ratio of NaN values}>\alpha\\\
A_{i},&\text{otherwise}\end{cases}$,
where $\alpha\in[0,1]$ is some threshold.

As a second case, we look into duplicated information. A trivial explanation
can be provided for an identical attribute in $T^{\prime}$. Given a goal
$A_{i}$, the origin is some attribute $A^{\prime}_{j}\in T^{\prime}$ such that
$A^{\prime}_{j}\notin T$ and $\pi_{A_{i}}[T]=\pi_{A^{\prime}_{j}}[T^{\prime}]$
(full overlap of values). A natural extension of finding duplications is
looking into similarities between attributes. We look into two types of
similarities, measuring the overlap between attributes and if there is a one-
to-one dependency between them. Overlap is measured and, if it meets some
threshold, an explanation is generated using the overlapping attribute
$A^{\prime}_{j}$ as the origin and an ‘overlaps with $A^{\prime}_{j}$’
transformation, which is defined similar to above. We also check if some
attribute in $T^{\prime}$ determines (using a similar methodology as described
in Section 4.6) $A_{i}\in L\Delta_{A}$. Obviously many other measures of
similarity exist, which we intend to explore in future work. Finally, note
that sometimes attribute removal can be idiopathic, i.e., the user simply
removed an attribute because they are not interested in some parts of the
data.

##  6\. Explaining Horizontal Changes

We begin with the common data cleaning operation of tuple removal, after which
we discuss adding tuples.

###  6.1. Removal Explanations for $L\Delta_{r}$

Tuple removal is a very common operation in data preparation, which mainly
revolves around cleaning data. Our examination begins iteratively by looking
into each removed tuple in $L\Delta_{r}$ independently. This may, for example,
result in the horizontal explanation $\mathcal{E}_{m4}$ from Example 4.
Finally, we explore if a _predicate_ was applied to remove them all remaining
(unexplained) tuples conjointly.

As in Section 5.2, we aim to find tuples that were removed collectively in a
table-independent manner due to missing values (NaNs), see the m4 explanation
in Example 4. For table-dependent explanations, we find duplicated tuples,
which is a common result of data cleaning using entity resolution (Elmagarmid
et al., 2006; Li et al., 2020). We focus only on identical tuple removal. Note
that this strict requirement can be relaxed and any entity resolution
technique, e.g., using declarative rules (Burdick et al., 2016), can be used
to find duplicated-tuple removal explanations. Specifically, if a duplicated
tuple $r^{\prime}_{j}\in T^{\prime}$ is found for a goal tuple $r_{i}\in$
$L\Delta_{r}$, we create a horizontal explanation of the form
$\mathcal{E}_{r_{i}}=(\emptyset,\text{duplicated of }r^{\prime}_{j})$. This
transformation can be expressed as follows
$r_{i}=\begin{cases}\emptyset,&\exists r^{\prime}_{j}\in
T^{\prime}s.t.r_{i}=r^{\prime}_{j}\\\ r_{i},&\text{otherwise}\end{cases}$
Finally, outlier detectors (Z-method and IQR-method (Chandola et al., 2009;
Ting et al., 2018)) also serve as explanations for removed tuples.

Not all tuples can be explained independently, thus, for all unexplained
tuples, $L\Delta_{r}$unexplained, we aim to find a joint explanation in the
form of a predicate. Given a set of unexplained tuples, we use a categorical
explanation method (Section 4.2) to find a joint explanation. Similar to
Section 5.1, in case the origin has mixed types, a decision tree is applied
also over encoded (using categorical-encoding change explanation, Section 4.4)
attributes in the table.

(a) Dataset version created by UserD over Figure 1(a).

$True$$True$$False$$True$$False$$False$

(b) Tree

Figure 10. UserD version of Figure 1(a) and its explanation.

###### Example 1.

In the example of Figure 1(b) we present a simple example of tuple removal due
to NaN value. Figure 10(a) provides an example of applying a predicate over
the table. To resolve this predicate, Explain-Da-V will first add the one-hot-
encoded features corresponding to a4 (is_Drama?, is_Action? and
is_Animation?), then, using a decision tree, it will try to resolve the
predicate. The decision tree in Figure 10(b) will be generated.

###  6.2. Addition Explanations for $R\Delta_{r}$

The non-idiopathic addition of tuples may be a result of over-sampling
(bootstrapping). To detect such a transformation, we use a similar methodology
as in Section 6.1. Given an added tuple $r^{\prime}_{i}\in$ $R\Delta_{r}$, we
aim to find a duplicated (equal or similar) tuple $r_{j}\in T$ to create an
explanation noting that the tuple has been bootstrapped.

##  7\. Evaluating Explanations

We aim to generate user friendly explanations that capture the semantics of
changes. Specifically, the explanation (transformation) can reproduce the
change and generalize it beyond a specific setup. Aiming to assess such
semantics, we now describe how we evaluate explanations. Sometimes multiple
explanations can be generated with respect to a change. Recall Example 1 in
which we present two possible valid explanations for a11. The first decision
tree explanation is rooted at $a3>8$ and the second is rooted at $a2>150$.
Also a decision tree rooted at $a3>7.5$ is a possible (invalid) explanation.
In what follows, an important question that needs to be asked is _how to
compare (and choose among) possible explanations?_

Related work on data transformation (see Section 2.3) employ success rates
that measure whether the output was generated successfully by applying the
transformation over the input. Yang et al. also introduce a ranking measure
(MRR) over possible transformations (pipelines in their terms), which still
views the transformation as a whole (Yang et al., 2021). We claim that solely
using such a measure does not capture the true nature of the transformation,
especially when evaluating an attribute-to-attribute (Section 5.1)
transformations. To provide a more fine-grained evaluation, we evaluate both
the _validity_ and _generalizablity_ computed over the transformed values to
assess the coverage of the transformation. As we are interested in providing
explainable solutions, we also use two _explainability_ dimensions,
_conciseness_ and _concentration_.

###  7.1. Explanation Validity and Generalizablity

Attribute (vertical) addition explanations are richer than removal or tuple
transformations, so their evaluation is addressed accordingly.

Vertical Additions: We separate this evaluation into validity (_does the
generated transformation recreate the goal using the origin?_) and
generalizability (_will the generated transformation be able to recreate a
similar goal using a similar origin?_). Recall Definition 2 and the notation
of origin ($\mathcal{O}$), goal ($\mathcal{G}$), and transformation
($\mathcal{P}$). For simplicity, we denote the output of a transformation
applied to an origin relation as
$\mathcal{\hat{G}}=\mathcal{P}(\mathcal{O}_{relation})$. Validity is computed
in a tuple-based manner over value-pairs $(\hat{r}_{ij},r_{ij})$ such that
$\hat{r}_{ij}\in\mathcal{\hat{G}}$ is a transformed value corresponding to a
goal value $r_{ij}\in\mathcal{G}_{relation}$, i.e., $\hat{r}_{i0}=r_{i0}$
($r_{i0}$ is the tuple id so this means the tuples are matching, see Section
3). Explanation validity is measured as follows:

(1) $\small
Val(\mathcal{E}_{\mathcal{G}})=\frac{1}{|\mathcal{G}_{relation}|}\sum\limits_{\begin{subarray}{c}\hat{r}_{ij}\in\mathcal{\hat{G}},r_{ij}\in\mathcal{G}_{relation}:\\\
s.t.\hat{r}_{i0}=r_{i0}\end{subarray}}\mathbb{I}(\hat{r}_{ij}=r_{ij})$

where $\mathbb{I}(\hat{r}_{ij}=r_{ij})$ is an indicator returning the value 1
if the transformed value equals to the corresponding goal value and 0
otherwise. The validity can be viewed as a tuple-based success rate, i.e., the
proportion of the tuples that were successfully transformed.

###### Example 1.

Recall the vertical explanation ${\mathcal{E}}_{a9}$ $=(a3,a3\div sum(a3))$
which was created for the attribute a9 in Figure 9 (see Example 1). Also
consider an alternative vertical explanation ${\mathcal{E}^{\prime}}_{a9}$
$=(a3,a3\div 33.4)$. Both explanations would have a validity score of $1$ as
applying the corresponding transformation recreates a9 perfectly.

As illustrated in the example, validity only looks at the given dataset
versions $T$ and $T^{\prime}$, which may result in overfitting (e.g.,
selecting $a3\div 33.4$ over $a3\div sum(a3)$). Aiming to measure such
scenarios, we introduce generalizability, measuring the extent to which a
solution can explain an equivalent set of versions. Specifically,
generalizability can be measured if a pair of versions $\tilde{T}$ and
$\tilde{T}^{\prime}$ exist such that $\tilde{T}^{\prime}$ was generated as a
version of $\tilde{T}$ using the same transformations that were used to
generate $T^{\prime}$ from $T$. Let $\mathcal{\tilde{O}}$ be the origin over
$\tilde{T}$ and $\mathcal{\tilde{G}}$ the goal over $\tilde{T}^{\prime}$. The
generalizability of an explanation $Gen(\mathcal{E}_{\mathcal{G}})$ is
measured by applying $\mathcal{P}$ over $\mathcal{\tilde{O}}$ to generate
$\mathcal{\hat{\tilde{G}}}$ and is computed as in Eq. 1 over
$\mathcal{\hat{\tilde{G}}}$ and $\mathcal{\tilde{G}}$. We illustrate the
importance of generalizability using the following example.

Figure 11. Example versions for generalizability

###### Example 2.

Fig. 11 provides two dataset versions. The top table is similar to Fig. 1(a)
and the bottom table corresponds to Fig. 9 such that the same transformations
over Fig. 1(a) generates Fig. 9. Recall the explanations ${\mathcal{E}}_{a9}$
$=(a3,a3\div sum(a3))$ and ${\mathcal{E}^{\prime}}_{a9}$ $=(a3,a3\div 33.4)$.
While these two are valid, using Fig. 11, we observe that ${\mathcal{E}}_{a9}$
is also generalizable while ${\mathcal{E}^{\prime}}_{a9}$ is not.
Specifically, if we apply ${\mathcal{E}}_{a9}$ over a3 in Fig. 11 we obtain
the values of a9 in the bottom table. However, if we apply
${\mathcal{E}^{\prime}}_{a9}$, we obtain the values $0.27$, $0.23$, and $0.24$
for the records m6, m7, and m9, respectively, resulting in a $0$
generalizability.

In practical settings, generalizability can be computed when the same changes
are applied to multiple datasets, e.g., in a data pipeline such as ETL
(Vassiliadis, 2009). For our new benchmark (Section 8.1.1), we generate an
annotated _hold-out_ set, used to compute generalizability.

Other Explanations: For tuple removal, we apply a reconstruction methodology
to evaluate validation and generalizability globally. We gather all generated
explanations and apply them over $T$ and try to regenerate $T^{\prime}$. Then,
we check the overlap between the removed tuples and the tuples that are not
included in $T^{\prime}$. For example, if a a3¿8 predicate was used to explain
the removed tuples, the same predicate would be applied over $T$ and compared
to $T^{\prime}$. This overlap, i.e., the proportion of tuples that were
correctly removed using the explanations of Explain-Da-V, is used as the
overall validity of tuple removal. The generalizability is measured similar to
above using an additional dataset version pair $\tilde{T}$ and
$\tilde{T}^{\prime}$.

We also compute validity and generalizability for other explanations.
Validation and generalizability of a removed attribute or added tuple are
computed independently, i.e., a score of 1 is given if an attribute was
removed correctly or a tuple was added correctly.

###  7.2. Problem Definition

We now formally state the problem of explaining data versions. Recall the
change sets defined over the $T$ and $T^{\prime}$ (see Section 3.2).

###### Definition 3.

Given $T^{\prime}$, a version of $T$ where the goals are $L\Delta_{A}$(left-
hand delta attributes), $R\Delta_{A}$(right-hand delta attributes),
$L\Delta_{r}$(left-hand delta tuples), and $R\Delta_{r}$(right-hand delta
tuples). From a search space of possible explanations, the version explanation
problem is to find, for each goal, a set of explanations with the highest
validity.

A solution to the version explanation problem is a set of explanations that
composed come closest to producing $T^{\prime}$ from $T$. Note that with
validity alone we may have ties (as in our examples where multiple
explanations have validity 1). If we have multiple datasets (or a dataset
holdout), we can use generalizability to pick among the multiple solutions. We
may also relax Definition 3 to find solutions whose validity is within some
range of the best and then use generalizability to select among these
candidate solutions. In addition, we can use explainability (described next)
in this selection and pick explanations that a user can better understand.

###  7.3. Explanation Explainability

As motivated above, we care about the explainability of the generated
solution. We, again, mainly focus on the attribute addition transformations.
Since we use different models to generate explanations (regressors, decision
trees, and programs), we seek a common ground to measure explainability.
Inspired by Narayanan et al. (Narayanan et al., 2018) and Lakkaraju et al.
(Lakkaraju et al., 2016), who focus on decision sets, we introduce two
explainability dimensions, namely _conciseness_ , and _concentration_ , that
can be measured across different explanations types.

Explainability Conciseness: Studies show that the fewer the components in a
model and the shorter it is, the easier it is for a user to understand it
(Cruz et al., 2015; Poursabzi-Sangdeh et al., 2021). In what follows, we
measure the conciseness of the transformation as the number of components
($N_{c}$) it holds. For regression models we use the _number of coefficients_
, for decision trees we use the _number of nodes_ , and for programs we use
the _number of implementation lines_.

###### Example 4.

Consider an $exp(A_{i})$ transformation. Obviously a desired explanation would
use the $math(\cdot)$ extension (Section 4.1) to generate a valid and
generalizable explanation $(A_{i},exp(A_{i}))$ that obtains an explainability
conciseness of 1 (a sole coefficient).

An alternative explanation would use a Taylor Series over the $poly(\cdot)$
extension to generate a valid and generalizable explanation
$(A_{i},1+A_{i}+\frac{A_{i}^{2}}{2}+\frac{A_{i}^{3}}{6}+\dots)$ with an
explanability conciseness of $\frac{1}{d+1}$, where $d$ is the polynomial
degree. Note that this case also highlights the trade-off between validity (or
generalizability) and explainability. The bigger the selected degree, the
higher the validity (and generalizability) and the lower the explainability.

Explainability Concentration: While a more concise explanation is favorable,
it should also contain as few components as possible (Letham et al., 2015)
(i.e., it should be as concentrated as possible). Specifically, since humans
have a limited working memory, a solution that is grouped into fewer chunks of
information is favorable (Narayanan et al., 2018). For example, a linear
regression function is easier to understand than a polynomial regression with
reciprocal and logarithmic transformations, even if the former is longer. For
regressors, we count _the extensions that were used_ (e.g., polynomials and
math operations). For decision trees, we count _the number of internal nodes_
that represent conditions and for programs we use _the number of intermediate
transformations_. Let $N_{g}$ be the number of chunks, the explanability
concentration is then given as $1\div N_{g}$ such that a more concentrated
transformation gets a higher score.

###### Example 5.

The concentration of $(A_{i},exp(A_{i}))$ and
$(A_{i},1+A_{i}+\frac{A_{i}^{2}}{2}+\dots)$ is 0.5 (1 extension, 1 degree) and
$\frac{1}{d}$, respectively.

To highlight the difference between conciseness and concentration consider,
for example, $\mathcal{E}_{1}=A_{1}+A_{2}+5$ and
$\mathcal{E}_{2}=log(A_{1})+A_{2}^{2}\cdot A_{1}$. While $\mathcal{E}_{1}$ is
less concise ($\frac{1}{3}$ vs $\frac{1}{2}$ of $\mathcal{E}_{2}$), it is more
concentrated ($1$) than $\mathcal{E}_{2}$ ($\frac{1}{3}$) which involves two
additional extensions.

The _total explanability_ is a linear combination of conciseness and
concentration that can be defined by a user or a system.666In our experiments
we use a uniform combination.

###  7.4. On Choosing an Explanation

Explain-Da-V works iteratively, aiming to find valid explanations for each
detected change following Section 5 and Section 6. As mentioned above, for
each goal, multiple explanations can be generated, for example, if there are
multiple origins (Section 4.6) or we have more than one methodology to explain
a transformation (e.g., different extensions in Section 4.1). Explain-Da-V
chooses the most _explainable valid_ explanation for each goal.

Each independent explanation is derived in a way that optimizes some notion of
error within the respective context that is not always the same as our
definition of validity. A regressor (Section 4.1) minimizes the mean squared
errors, a PBE solution (Section 4.3) directly optimizes accuracy via search
and a decision tree (greedily) optimizes the split functions of nodes. Given a
set of explanations, we choose one as follows. (1) Find the highest validity
in the set. (2) If multiple explanations share this value, return the most
explainable based on total explainability (see Section 7.3).

Note that generalizability can not be used for explanation selection unless we
have access to a $\tilde{T}$ and $\tilde{T}^{\prime}$ (see Section 7.1).

Potentially, there can be a large number of transformations. Dealing with this
size, the explanations in a set are generated in a sorted order by the size
and cardinally of their origin (see Section 4.6). Similarly, among regression
models the explanations are sorted by the amount of extensions that were
applied (i.e., first, a model without extensions is considered). Accordingly,
we introduce an _early stop condition_ such that if an explanation meets a
predefined threshold of validity and explainability, it is returned and the
search is stopped.777In our experiments the threshold was set to .95.
Empirically, almost 70% of cases are terminated early.

##  8\. Empirical Evaluation

We now compare our performance to baselines (Section 8.2) and analyze the
components using an ablation study (Section 8.3).

###  8.1. Experimental Setup

We now detail our benchmarks, implementation, and baselines. The benchmark and
code are available in our repository (git, 2022).

####  8.1.1. Benchmarks

We design a new benchmark for the novel task of semantic data versioning,
termed Semantic Data Versioning Benchmark (SDVB), composed of five _version-
sets_. We also adopt a publicly available dataset designed by Yang et al.
(Yang et al., 2021) for a similar task of synthesizing data pipelines.

Semantic Data Versioning Benchmark (SDVB): SDVB contains a total of 342
dataset versions (136 version pairs) over five different topics, ranging in
length (number of tuples) and width (number of attributes).888Not all versions
use all original attributes. Each topic represents a _version-set_ that was
derived from a well-known seed dataset detailed in Table 2, which includes
smaller datasets (e.g., IRIS) along side bigger datasets (e.g., WINE).

Version Generation: Given a seed dataset, we revise it to generate a version
of it by first selecting a subset of change dimensions (e.g., $R\Delta_{A}$and
$L\Delta_{r}$). Then, based on the dimension, we perform a set of
transformations (some sampled and some manually created). We assure that each
of the five version-sets cover all change dimensions. Prior to version
generating, each dataset is split into $T$ and $\tilde{T}$ (80%-20%), where
the latter is a hold-out to compute generalizability. Following Section 7.1,
the same changes applied to $T$ to generate $T^{\prime}$ are applied to
$\tilde{T}$ to generate $\tilde{T}^{\prime}$.999The numbers reported in Table
2 include the hold-outs.

Finally, note that a version may be created using more than one change and, in
practice, the aforementioned number of versions is actually composed of 1,702
changes. For example, to create the 72 WINE dataset versions, a total of 681
changes were applied over the original dataset and its versions.

Table 2. Semantic Data Versioning Benchmark Details.

Topic (Name) | # of Original | # of Original | # of | # of
---|---|---|---|---
| Tuples | Attributes | Versions | Version-pairs
Movies and TV shows (IMD, 2022) (IMDB) | 1,000 | 6 | 72 | 29
NBA Players (NBA, 2022) (NBA) | 11,700 | 9 | 68 | 27
Wines Reviews (WIN, 2022) (WINE) | 129,971 | 6 | 72 | 29
Iris Flowers (IRI, 2022) (IRIS) | 150 | 5 | 58 | 22
Titanic Passengers (TIT, 2022) (TITANIC) | 891 | 6 | 72 | 29

Auto-Pipeline Benchmark (Aut, 2022a): This benchmark contains real data
pipelines extracted from Github notebooks. As we focus on dataset versions, we
filter out pipelines that include more than one table (e.g., those that use a
join). Following Yang et al. (Yang et al., 2021), we consider the “test” table
as $T$ and the “target” table as $T^{\prime}$. For a fair comparison, we run
Explain-Da-V and all baselines on all the data and do not consider
generalizability for this benchmark.

Table 3. Performance in terms of Validity (Val), Generalizability (Gen) and
average number of explanations the method chooses from (# $\mathcal{E}$). For
Explain-Da-V, we also report (in parenthesis) the proportion of explanations
with Val/Gen score of 1.

Dataset$\rightarrow$ | IMDB | NBA | WINE | IRIS | TITANIC | Auto-pipeline
---|---|---|---|---|---|---
$\downarrow$Method | Val | Gen | # $\mathcal{E}$ | Val | Gen | # $\mathcal{E}$ | Val | Gen | # $\mathcal{E}$ | Val | Gen | # $\mathcal{E}$ | Val | Gen | # $\mathcal{E}$ | Val | Gen | # $\mathcal{E}$
Foofah | .42 | .42 | 3.7 | .28 | .28 | 4.2 | .29 | .29 | 3.9 | .23 | .23 | 3.1 | .29 | .29 | 4.1 | .55 | - | 3.3
Foofah+ | .44 | .44 | 3.7 | .29 | .29 | 4.2 | .34 | .34 | 3.9 | .25 | .25 | 3.1 | .37 | .37 | 4.1 | .55 | - | 3.3
Auto-pipeline* | .44 | .44 | 3.7 | .30 | .30 | 4.2 | .33 | .33 | 3.9 | .26 | .26 | 3.1 | .37 | .37 | 4.1 | .78 | - | 3.3
Explain-Da-V |  .73 (.64) |  .60 (.56) | 6.4 |  .90 (.89) |  .79 (.69) | 7.3 |  .87 (.76) |  .81 (.59) | 6.8 |  .93 (.88) |  .83 (.76) | 8.9 |  .88 (.79) |  .77 (.68) | 7.2 |  .82 (.78) | - | 5.7
\+ over baseline | +65% | +36% |  | +202% | +167% |  | +156% | +138% |  | +254% | +217% |  | +140% | +109% |  | +5% | - |

Table 4. Foofah, Foofah+, Auto-pipeline*, and Explain-Da-V performance in
terms of Validity (Val.) and Generalizability (Gen.) for Numeric goals

Dataset$\rightarrow$ | IMDB | NBA | WINE | IRIS | TITANIC
---|---|---|---|---|---
$\downarrow$Method | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen.
Foofah | .20 | .20 | .11 | .11 | .14 | .14 | .18 | .18 | .12 | .12
Foofah+ | .20 | .20 | .15 | .15 | .16 | .16 | .21 | .21 | .24 | .24
Auto-pipeline* | .22 | .22 | .16 | .16 | .18 | .18 | .22 | .22 | .26 | .26
Explain-Da-V |  .97 (+340%) |  .85(+286%) |  .72 (+350%) |  .66 (+313%) |  .87 (+383%) |  .75 (+316%) |  .99 (+350%) |  .85 (+286%) |  .92 (+253%) |  .84 (+223%)

Table 5. Foofah, Foofah+, Auto-pipeline*, and Explain-Da-V performance in
terms of Validity (Val.) and Generalizability (Gen.) for Categorical goals

Dataset$\rightarrow$ | IMDB | NBA | WINE | IRIS | TITANIC
---|---|---|---|---|---
$\downarrow$Method | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen.
Foofah | .15 | .15 | .09 | .09 | .16 | .16 | .23 | .23 | .22 | .22
Foofah+ | .25 | .25 | .12 | .12 | .18 | .18 | .25 | .25 | .22 | .22
Auto-pipeline* | .27 | .27 | .12 | .12 | .17 | .17 | .26 | .26 | .22 | .22
Explain-Da-V |  .86 (+218%) |  .86(+218%) |  .99 (+725%) |  .87 (+625%) |  .89 (+423%) |  .78 (+358%) |  .98 (+277%) |  .91 (+250%) |  .88 (+300%) |  .83 (+277%)

Table 6. Foofah, Foofah+, Auto-pipeline*, and Explain-Da-V performance in
terms of Validity (Val.) and Generalizability (Gen.) for Textual goals

Dataset$\rightarrow$ | IMDB | NBA | WINE | IRIS | TITANIC
---|---|---|---|---|---
$\downarrow$Method | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen. | Val. | Gen.
Foofah | .50 | .50 | .48 | .48 | .44 | .44 | .33 | .33 | .47 | .47
Foofah+ | .52 | .52 | .50 | .50 | .53 | .53 | .42 | .42 | .48 | .48
Auto-pipeline* | .52 | .52 | .56 | .56 | .53 | .53 | .38 | .38 | .50 | .50
Explain-Da-V |  .62 (+19%) |  .57(+10%) |  .88 (+57%) |  .67 (+20%) |  .58 (+9%) |  .56 (+6%) |  .82 (+115%) |  .72 (+89%) |  .79 (+58%) |  .69 (+38%)

####  8.1.2. Implementation

Explain-Da-V was implemented in python, following Sections 5 and 6. Main parts
of the code are provided in our repository (git, 2022). Linear regression with
Lasso (Las, 2022) and Rigde (Rig, 2022),101010We first tried applying Lasso
and if failed we applied Rigde. regularization and decision trees (Dec, 2022)
were implemented with Scikit-learn. We extended Foofah’s python publicly
available implementation (Foo, 2022b). We use the Featuretools (Fea, 2022)
framework to generate aggregated and group by features (see Section 5.1).

####  8.1.3. Baselines

Foofah (Jin et al., 2017) is used as a PBE baseline (see Section 2.3). Foofah+
denotes Foofah with our novel extensions (e.g., textual-to-numeric, see
Section 4.3). As Auto-pipeline’s implementation is not publicly available, we
reproduced its search methodology111111Reinforcement learning requires
training data, which we assume unavailable. using Foofah’s framework by
implementing the operators provided by Yang et al. (Auto-pipeline*) (Yang et
al., 2021). Search has an exponential worst case time complexity, so we apply
a 60 second timeout for all methods following the default in Foofah (Jin et
al., 2017).121212We note that Auto-pipeline default timeout limit is an hour

We also ran AutoPandas (Bavishi et al., 2019) using their available
implementation (Aut, 2022b). AutoPandas creates a search space based on pandas
(Pan, 2022) operations and prunes the space of programs using deep learning.
Similar to the reported performance in Auto-pipeline (Yang et al., 2021),
AutoPandas performance was inferior and thus not reported. We also
experimented with SQUARES (Orvalho et al., 2020), a recent query reverse
engineering framework, and, similarly, do not report its inferior results.
Since SQUARES was designed to synthesize traditional SQL queries it can
sometimes resolve selection predicates; yet, it fails to cope with other
changes such as attributes added using transformations.

Finally, a naïve implementation of the baselines would use all of $T$ and
$T^{\prime}$ as input-output examples. However, to allow a fair comparison, we
“find the origin” (see Section 4.6) for each of the baselines and vertical
explanations are solved iteratively (each attribute at a time). For horizontal
addition explanations the tuples of $T$ are used as input and the tuples of
$T^{\prime}$ as output (similarly for horizontal removal with $T^{\prime}$ as
input and $T$ as output).

####  8.1.4. Evaluation Measures

The explanations provided by our baselines are of a single type (programs, not
regressors or decision trees), thus, in Section 8.2, we compare the Validity
(Val.) and Generalizability (Gen.) of Explain-Da-V to the baselines. Since
Explain-Da-V can return explanations that do not have a
validity/generalizability score of 1.0, we also report the proportion of such
explanations out of all output explanations. We further report the average
number of explanations (# $\mathcal{E}$) from which the method selects the
most explainable valid (see Section 7.4). We also compare and report runtimes.
Section 8.3 also uses explainability (conciseness and concentration).

###  8.2. Explain-Da-V Compared to Baselines

The comparison between Explain-Da-V and the baselines (Section 8.1.3) over the
benchmarks (Section 8.1.1) is reported in Table 6.

Explain-Da-V performs much better than the baselines mainly due to its ability
to cope with varying data types (numeric and categorical in addition to
textual). The adapted Auto-pipeline benchmark is an exception where Explain-
Da-V only performs slightly better than Auto-pipeline*. Also, even if we zoom-
in only on textual transformations (provided in a technical report (Shraga and
Miller, 2022)), Explain-Da-V still out-performs all baselines. Even when we
evaluate only the 100% valid/generalizable explanations returned by Explain-
Da-V (denoted in parenthesis in Table 6), we observe a significant
improvement. Across baselines, we observe that extending Foofah (Foofah+)
provides an average validity and generalizability boost of 9.5%, showing the
benefit of the extended search space. All methods select among multiple
explanations (# $\mathcal{E}$, see Section 8.1.4) based on multiple origins
(see Section 8.1.3). Explain-Da-V considers almost twice as many explanations
since it generates expanded origins for numeric explanations (see Section
4.1).

Comparing among version-sets, we observe that in the IRIS dataset, Explain-
Da-V obtained the best performance (.927 Val. and .831 Gen.) and the highest
improvement. For the IMDB version-set, Explain-Da-V obtained the worst
performance (.732 Val. and .602 Gen.) and lowest improvement (among the newly
suggested benchmark version-sets). IRIS is mostly composed of numeric
attributes (4 out of 5) which are solved using our numeric change explanations
(Section 4.1) and are not dealt with by the baselines. Note that accordingly,
Explain-Da-V considers almost three times as many explanations. Yet, the
numeric extensions introduced in Section 4.1 and the fact that we find the
origin helps to home in on a valid solution quite quickly (see runtime below).
The IMDB version-set, on the other hand, contains more textual attributes (5
out of 6) and involves changes that Explain-Da-V fails to solve. For example,
one of the IMDB version-sets involves a transformation that adds an attribute
containing the count of the number of genres from a Genre attribute. In the
Genre attribute, the genres are separated by a comma (e.g., Drama, Romance). A
correct transformation would, for example, count the number of commas and add
1. While finding a transformation that counts the number of commas is a
practical task for Explain-Da-V (which includes textual transformations and
aggregations), such a composition is not currently possible. Instead, the
explanation Explain-Da-V chose (most valid, see Section 7.4) uses an IMDB
Rating attribute to determine the number of genres using a decision tree with
a validity of 0.65.131313The explanation is available in the repository (exp,
2022).

Finally, we note that the performance varies with respect to the different
change dimensions. Interestingly, if we only look at vertical removals
(Section 5.2), all three baselines have a validity and generalizability score
of 1. The reason for that is their ability to discover projections (in their
terms applying a drop operation over an attribute). Although it successfully
finds these transformations, it lacks the ability to explain the semantics of
the attribute removal. Explain-Da-V, although not perfectly valid and
generalizable (.95), is more expressive in term of explaining the removal. For
example, explaining that an attribute was removed because it contains
duplicated information (see Section 5.2). When looking at tuple removal,
Explain-Da-V performs much better than the baselines. Since Auto-pipeline does
“not consider row-level filtering” (Yang et al., 2021), we recall the
comparison against SQUARES (see Section 8.1.3). Despite its focus on learning
a selection predicate, SQUARES is able to resolve cases where a predicate was
applied with 0.6 validity (Explain-Da-V obtains 0.73 over these changes). This
is because SQUARES was not able to resolve removing tuples containing NaN
values and duplicate tuples (two cases in the benchmark).

Runtime: In these experiments, excluding timeouts (see Section 8.1.3), finding
an explanation using foofah took an average of 4.9 seconds, foofah+ 12.4
seconds, Auto-pipeline* 8.1 seconds, and Explain-Da-V 2.4 seconds. A reason
for that difference is that fitting a regressor (linear time complexity) and
learning a decision tree (quadratic complexity) are more efficient than search
(exponential).

###  8.3. Explain-Da-V Ablation Study

Figure 12 provides an ablation study of Explain-Da-V. We focus on vertical
addition explanations and analyze Explain-Da-V performance without finding the
origin (W/O find origin), i.e., using $T$ as a whole to explain a given goal
and without the extensions for numeric-to-numeric transformations (W/O
extensions). We also analyze the resolved data types by applying Explain-Da-V
assuming all types are numeric (All numeric) or all textual (All textual).

(a) Validity

(b) Generalizability

(c) Conciseness

(d) Concentration

Figure 12. Ablation Study over SDVB datasets.

As illustrated in Figures 12(a) and 12(b), the full Explain-Da-V provides the
most valid and generalizable performance. Adding extensions and finding the
origin provide an average performance boost of 30% and 107%, respectively, in
terms of validity, while addressing all attribute types as numeric and textual
decreases the validity by 35% and 64%, respectively. The NBA version-set
demonstrates an interesting case. Since it contains diverse attributes of
varying types, without finding origin, Explain-Da-V obtains very low validity
and generalizability. Similarly, as mentioned above, since the IRIS version-
set mainly consists of numeric attributes, treating all attributes as textual
results in very low performance.

Examining the explainability (Figures 12(c)-12(d)), we observe that while less
valid and generalizable, explanations without extensions are more concise and
concentrated. If an origin is not found, the explanations are usually less
concise and much less concentrated. Finally, numeric explanations are more
explainable than textual explanations especially in terms of conciseness.
Limitations via Interesting Cases: Consider the NBA version-set. One vertical
addition in this dataset creates a binary attribute representing an indicator
for a “double double” performance.141414In basketball, a double-double is when
a player accumulates ten or more in two of statistical categories
https://en.wikipedia.org/wiki/Double-double. A valid and generalizable
transformation generated by Explain-Da-V returns $1$ if $A_{ast}>10$ (more
than 10 assists) simply because for each tuple $r_{i}\in T$ such that
$\pi_{A_{ast}}[r_{i}]>10$ it also happens that $\pi_{A_{pts}}[r_{i}]>10$ (more
than 10 points). While correct in the specific scenario, it does not capture
the semantics of a double double.

Another interesting case considers a square-root transformation over movie
rating ($A_{rating}$) in the IMDB version-set. Explain-Da-V generated two
valid and generalizable explanations one using the transformation
$sqrt(A_{rating})$ (using the $math$ extensions) and one using a polynomial
transformation $1.074+0.262\cdot A_{rating}-0.005\cdot A_{rating}^{2}$.
Obviously, these two transformations are different; however, if we zoom in on
the range $x\in[6,10]$ (typical ratings in IMDB), we observe that the
transformations behave almost identically. For example, a rating of 9 would be
transformed to 3 and 3.02, respectively. An illustration is given in our
repository (sqr, 2022).

##  9\. Conclusion

This work laid the groundwork for explaining semantic changes in data
versioning. Explain-Da-V, uses different types of techniques to resolve and
explain changes between a pair of dataset versions. We introduced measures to
evaluate explanations and show that Explain-Da-V performs better than multiple
baselines over an existing adapted benchmark and a newly introduced data
versioning benchmark. In future work, we intend to extend Explain-Da-V to
address additional data types, e.g., dates, and address changes that are
triggered by external data such as performing joins and unions. An additional
future challenge is to formulate the version explanation problem as a multi-
objective optimization problem that collectively optimizes validity,
generalizability, and explainability.

## References

  * (1)
  * Aut (2022a) 2022a.  Auto-pipeline benchmark.  https://gitlab.com/jwjwyoung/autopipeline-benchmarks.
  * Aut (2022b) 2022b.  AutoPandas Implementation.  https://github.com/rbavishi/autopandas.
  * Dec (2022) 2022\.  Decision Trees.  https://scikit-learn.org/stable/modules/tree.html.
  * exp (2022) 2022\.  Explanation Example.  https://github.com/shraga89/ExplainDaV/blob/main/Explanation_Example.md.
  * Fea (2022) 2022\.  Featuretools.  https://www.featuretools.com/.
  * Foo (2022a) 2022a.  Foofah Extensions (Repository).  https://github.com/shraga89/ExplainDaV/blob/main/Code/Ops_added_to_Foofah.py.
  * Foo (2022b) 2022b.  Foofah Implementation.  https://github.com/umich-dbgroup/foofah.
  * IMD (2022) 2022\.  Initial IMDB dataset.  https://www.kaggle.com/datasets/harshitshankhdhar/imdb-dataset-of-top-1000-movies-and-tv-shows.
  * IRI (2022) 2022\.  Initial IRIS dataset.  https://www.kaggle.com/uciml/iris.
  * NBA (2022) 2022\.  Initial NBA dataset.  https://www.kaggle.com/justinas/nba-players-data.
  * TIT (2022) 2022\.  Initial TITANIC dataset.  https://www.kaggle.com/competitions/titanic.
  * WIN (2022) 2022\.  Initial WINE dataset.  https://www.kaggle.com/christopheiv/winemagdata130k.
  * Las (2022) 2022\.  Lasso Regularization.  https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Lasso.html.
  * Pan (2022) 2022\.  Pandas.  https://pandas.pydata.org/.
  * git (2022) 2022\.  Repository.  https://github.com/shraga89/ExplainDaV.
  * Rig (2022) 2022\.  Rigde Regularization.  https://scikit-learn.org/stable/modules/generated/sklearn.linear_model.Rigde.html.
  * sqr (2022) 2022\.  Sqrt Example (Repository).  https://github.com/shraga89/ExplainDaV/blob/main/sqrt_example.pdf.
  * Abedjan et al. (2016) Ziawasch Abedjan, John Morcos, Ihab F. Ilyas, Mourad Ouzzani, Paolo Papotti, and Michael Stonebraker. 2016.  DataXFormer: A robust transformation discovery system. In _32nd IEEE International Conference on Data Engineering, ICDE 2016, Helsinki, Finland, May 16-20, 2016_. IEEE Computer Society, 1134–1145.  https://doi.org/10.1109/ICDE.2016.7498319
  * Bavishi et al. (2019) Rohan Bavishi, Caroline Lemieux, Roy Fox, Koushik Sen, and Ion Stoica. 2019.  AutoPandas: neural-backed generators for program synthesis.  _Proc. ACM Program. Lang._ 3, OOPSLA (2019), 168:1–168:27.  https://doi.org/10.1145/3360594
  * Bellatreche and Wrembel (2013) Ladjel Bellatreche and Robert Wrembel. 2013.  Special issue on: Evolution and versioning in semantic data integration systems.  , 57–59 pages.
  * Bhardwaj et al. (2015) Anant P. Bhardwaj, Souvik Bhattacherjee, Amit Chavan, Amol Deshpande, Aaron J. Elmore, Samuel Madden, and Aditya G. Parameswaran. 2015\.  DataHub: Collaborative Data Science & Dataset Version Management at Scale. In _Seventh Biennial Conference on Innovative Data Systems Research, CIDR 2015, Asilomar, CA, USA, January 4-7, 2015, Online Proceedings_. www.cidrdb.org.  http://cidrdb.org/cidr2015/Papers/CIDR15_Paper18.pdf
  * Bhattacherjee et al. (2015) Souvik Bhattacherjee, Amit Chavan, Silu Huang, Amol Deshpande, and Aditya Parameswaran. 2015\.  Principles of dataset versioning: Exploring the recreation/storage tradeoff. In _Proceedings of the VLDB Endowment. International Conference on Very Large Data Bases_ , Vol. 8. NIH Public Access, 1346.
  * Bleifuß et al. (2018) Tobias Bleifuß, Leon Bornemann, Theodore Johnson, Dmitri V Kalashnikov, Felix Naumann, and Divesh Srivastava. 2018.  Exploring change: A new dimension of data analytics.  _Proceedings of the VLDB Endowment_ 12, 2 (2018), 85–98.
  * Bleifuß et al. (2019) Tobias Bleifuß, Leon Bornemann, Dmitri V Kalashnikov, Felix Naumann, and Divesh Srivastava. 2019\.  DBChEx: Interactive Exploration of Data and Schema Change. In _CIDR_.
  * Bogatu et al. (2019) Alex Bogatu, Norman W. Paton, Alvaro A. A. Fernandes, and Martin Koehler. 2019.  Towards Automatic Data Format Transformations: Data Wrangling at Scale.  _Comput. J._ 62, 7 (2019), 1044–1060.  https://doi.org/10.1093/comjnl/bxy118
  * Bornemann et al. (2018) Leon Bornemann, Tobias Bleifuß, Dmitri Kalashnikov, Felix Naumann, and Divesh Srivastava. 2018\.  Data change exploration using time series clustering.  _Datenbank-Spektrum_ 18, 2 (2018), 79–87.
  * Brook and Arnold (2018) Richard J Brook and Gregory C Arnold. 2018.  _Applied regression analysis and experimental design_.  CRC Press.
  * Brownlee (2022) Jason Brownlee. 2022\.  Data preparation for machine learning.
  * Burdick et al. (2016) Douglas Burdick, Ronald Fagin, Phokion G. Kolaitis, Lucian Popa, and Wang-Chiew Tan. 2016.  A Declarative Framework for Linking Entities.  _ACM Trans. Database Syst._ 41, 3 (2016), 17:1–17:38.
  * Burkart and Huber (2021) Nadia Burkart and Marco F Huber. 2021.  A survey on the explainability of supervised machine learning.  _Journal of Artificial Intelligence Research_ 70 (2021), 245–317.
  * Cao et al. (2021) Hancheng Cao, Vivian Yang, Victor Chen, Yu Jin Lee, Lydia Stone, N’godjigui Junior Diarrassouba, Mark E Whiting, and Michael S Bernstein. 2021.  My team will go on: Differentiating high and low viability teams through team interaction.  _Proceedings of the ACM on Human-Computer Interaction_ 4, CSCW3 (2021), 1–27.
  * Chandola et al. (2009) Varun Chandola, Arindam Banerjee, and Vipin Kumar. 2009\.  Anomaly detection: A survey.  _ACM computing surveys (CSUR)_ 41, 3 (2009), 1–58.
  * Chapman et al. (2020) Adriane Chapman, Elena Simperl, Laura Koesten, George Konstantinidis, Luis-Daniel Ibáñez, Emilia Kacprzak, and Paul Groth. 2020\.  Dataset search: a survey.  _VLDB J._ 29, 1 (2020), 251–272.
  * Chawathe and Garcia-Molina (1997) Sudarshan S Chawathe and Hector Garcia-Molina. 1997.  Meaningful change detection in structured data.  _ACM SIGMOD Record_ 26, 2 (1997), 26–37.
  * Chawathe et al. (1996) Sudarshan S Chawathe, Anand Rajaraman, Hector Garcia-Molina, and Jennifer Widom. 1996.  Change detection in hierarchically structured information.  _Acm Sigmod Record_ 25, 2 (1996), 493–504.
  * Cheney et al. (2009) James Cheney, Laura Chiticariu, Wang-Chiew Tan, et al. 2009\.  Provenance in databases: Why, how, and where.  _Foundations and Trends® in Databases_ 1, 4 (2009), 379–474.
  * Chernyavskiy et al. (2021) Anton Chernyavskiy, Dmitry Ilvovsky, and Preslav Nakov. 2021\.  Transformers:“The End of History” for Natural Language Processing?. In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_. Springer, 677–693.
  * Cobena et al. (2002) Gregory Cobena, Serge Abiteboul, and Amelie Marian. 2002\.  Detecting changes in XML documents. In _Proceedings 18th International Conference on Data Engineering_. IEEE, 41–52.
  * Cruz et al. (2015) Nicole Cruz, Jean Baratgin, Mike Oaksford, and David E Over. 2015.  Bayesian reasoning with ifs and ands and ors.  _Frontiers in psychology_ 6 (2015), 192.
  * Da San Martino et al. (2019) Giovanni Da San Martino, Seunghak Yu, Alberto Barrón-Cedeno, Rostislav Petrov, and Preslav Nakov. 2019\.  Fine-grained analysis of propaganda in news article. In _Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP)_. 5636–5646.
  * Das Sarma et al. (2012) Anish Das Sarma, Lujun Fang, Nitin Gupta, Alon Halevy, Hongrae Lee, Fei Wu, Reynold Xin, and Cong Yu. 2012\.  Finding Related Tables. In _Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data_ (Scottsdale, Arizona, USA) _(SIGMOD ’12)_. Association for Computing Machinery, New York, NY, USA, 817–828.  https://doi.org/10.1145/2213836.2213962
  * Data (2020a) Canada Open Data. 2020a.  https://open.canada.ca/en/open-data
  * Data (2020b) UK Open Data. 2020b.  https://data.gov.uk/
  * Deng (2015) Boer Deng. 2015\.  Papers with shorter titles get more citations.  _Nature News_ 26 (2015).
  * Deng et al. (2019) Dong Deng, Wenbo Tao, Ziawasch Abedjan, Ahmed K. Elmagarmid, Ihab F. Ilyas, Guoliang Li, Samuel Madden, Mourad Ouzzani, Michael Stonebraker, and Nan Tang. 2019\.  Unsupervised String Transformation Learning for Entity Consolidation. In _35th IEEE International Conference on Data Engineering, ICDE 2019, Macao, China, April 8-11, 2019_. IEEE, 196–207.  https://doi.org/10.1109/ICDE.2019.00026
  * Edwards (2002) Jeffrey R Edwards. 2002\.  Alternatives to difference scores: Polynomial regression and response surface methodology.  _Advances in measurement and data analysis_ (2002), 350–400.
  * El Gebaly et al. (2014) Kareem El Gebaly, Parag Agrawal, Lukasz Golab, Flip Korn, and Divesh Srivastava. 2014.  Interpretable and informative explanations of outcomes.  _Proceedings of the VLDB Endowment_ 8, 1 (2014), 61–72.
  * Elmagarmid et al. (2006) Ahmed K Elmagarmid, Panagiotis G Ipeirotis, and Vassilios S Verykios. 2006.  Duplicate record detection: A survey.  _IEEE Transactions on knowledge and data engineering_ 19, 1 (2006), 1–16.
  * Flach and Savnik (1999) Peter A Flach and Iztok Savnik. 1999.  Database dependency discovery: a machine learning approach.  _AI Communications_ 12 (3) (1999), 139 – 160.  http://content.iospress.com/articles/ai-communications/aic182 Publisher: IOS Press.
  * Gao et al. (2018) Yihan Gao, Silu Huang, and Aditya G. Parameswaran. 2018\.  Navigating the Data Lake with DATAMARAN: Automatically Extracting Structure from Log Datasets. In _Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018_ , Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 943–958.  https://doi.org/10.1145/3183713.3183746
  * Gkikas et al. (2022) Dimitris C Gkikas, Katerina Tzafilkou, Prokopis K Theodoridis, Aristogiannis Garmpis, and Marios C Gkikas. 2022.  How do text characteristics impact user engagement in social media posts: Modeling content readability, length, and hashtags number in Facebook.  _International Journal of Information Management Data Insights_ 2, 1 (2022), 100067.
  * Harris and Gulwani (2011) William R. Harris and Sumit Gulwani. 2011.  Spreadsheet table transformations from examples. In _Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011_ , Mary W. Hall and David A. Padua (Eds.). ACM, 317–328.  https://doi.org/10.1145/1993498.1993536
  * He et al. (2018) Yeye He, Xu Chu, Kris Ganjam, Yudian Zheng, Vivek R. Narasayya, and Surajit Chaudhuri. 2018.  Transform-Data-by-Example (TDE): An Extensible Search Engine for Data Transformations.  _Proc. VLDB Endow._ 11, 10 (2018), 1165–1177.  https://doi.org/10.14778/3231751.3231766
  * He et al. (2020) Yeye He, Zhongjun Jin, and Surajit Chaudhuri. 2020.  Auto-Transform: Learning-to-Transform by Patterns.  _Proc. VLDB Endow._ 13, 11 (2020), 2368–2381.  http://www.vldb.org/pvldb/vol13/p2368-he.pdf
  * Hohman et al. (2020) Fred Hohman, Kanit Wongsuphasawat, Mary Beth Kery, and Kayur Patel. 2020.  Understanding and visualizing data iteration in machine learning. In _Proceedings of the 2020 CHI conference on human factors in computing systems_. 1–13.
  * home of the U.S. Government’s open data (2020) The home of the U.S. Government’s open data. 2020.  https://data.gov/
  * Huang et al. (2017) Silu Huang, Liqi Xu, Jialin Liu, Aaron J Elmore, and Aditya Parameswaran. 2017.  ORPHEUSDB: Bolt-on Versioning for Relational Databases.  _Proceedings of the VLDB Endowment_ 10, 10 (2017).
  * Jin et al. (2017) Zhongjun Jin, Michael R. Anderson, Michael J. Cafarella, and H. V. Jagadish. 2017.  Foofah: Transforming Data By Example. In _Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD Conference 2017, Chicago, IL, USA, May 14-19, 2017_ , Semih Salihoglu, Wenchao Zhou, Rada Chirkova, Jun Yang, and Dan Suciu (Eds.). ACM, 683–698.  https://doi.org/10.1145/3035918.3064034
  * Jin et al. (2019) Zhongjun Jin, Michael J. Cafarella, H. V. Jagadish, Sean Kandel, Michael Minar, and Joseph M. Hellerstein. 2019.  CLX: Towards verifiable PBE data transformation. In _Advances in Database Technology \- 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019_ , Melanie Herschel, Helena Galhardas, Berthold Reinwald, Irini Fundulaki, Carsten Binnig, and Zoi Kaoudi (Eds.). OpenProceedings.org, 265–276.  https://doi.org/10.5441/002/edbt.2019.24
  * Kery et al. (2017) Mary Beth Kery, Amber Horvath, and Brad Myers. 2017\.  Variolite: Supporting Exploratory Programming by Data Scientists. In _Proceedings of the 2017 CHI Conference on Human Factors in Computing Systems_. 1265–1276.
  * Kery et al. (2019) Mary Beth Kery, Bonnie E John, Patrick O’Flaherty, Amber Horvath, and Brad A Myers. 2019.  Towards effective foraging by data scientists to find past analysis choices. In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_. 1–13.
  * Kery et al. (2018) Mary Beth Kery, Marissa Radensky, Mahima Arya, Bonnie E John, and Brad A Myers. 2018.  The story in the notebook: Exploratory data science using a literate programming tool. In _Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems_. 1–11.
  * Khatiwada et al. (2023) Aamod Khatiwada, Grace Fan, Roee Shraga, Zixuan Chen, Wolfgang Gatterbauer, Renée J Miller, and Mirek Riedewald. 2023.  SANTOS: Relationship-based Semantic Table Union Search. In _SIGMOD Conference 2023_. ACM.  https://arxiv.org/pdf/2209.13589.pdf
  * Khatiwada et al. (2022) Aamod Khatiwada, Roee Shraga, Wolfgang Gatterbauer, and Renée J. Miller. 2022.  Integrating Data Lake Tables.  _Proc. VLDB Endow._ 16, 4 (2022), 932–945.  https://www.vldb.org/pvldb/vol16/p932-khatiwada.pdf
  * Kim et al. (2020) Alexandra Kim, Laks VS Lakshmanan, and Divesh Srivastava. 2020\.  Summarizing hierarchical multidimensional data. In _2020 IEEE 36th International Conference on Data Engineering (ICDE)_. IEEE, 877–888.
  * Kovaleva et al. (2019) Olga Kovaleva, Alexey Romanov, Anna Rogers, and Anna Rumshisky. 2019.  Revealing the Dark Secrets of BERT. In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_. 4365–4374.
  * Kuhn and Johnson (2019) Max Kuhn and Kjell Johnson. 2019.  _Feature engineering and selection: A practical approach for predictive models_.  CRC Press.
  * Lakkaraju et al. (2016) Himabindu Lakkaraju, Stephen H Bach, and Jure Leskovec. 2016\.  Interpretable decision sets: A joint framework for description and prediction. In _Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining_. 1675–1684.
  * Letham et al. (2015) Benjamin Letham, Cynthia Rudin, Tyler H McCormick, and David Madigan. 2015.  Interpretable classifiers using rules and bayesian analysis: Building a better stroke prediction model.  _The Annals of Applied Statistics_ 9, 3 (2015), 1350–1371.
  * Li et al. (2020) Yuliang Li, Jinfeng Li, Yoshihiko Suhara, AnHai Doan, and Wang-Chiew Tan. 2020.  Deep entity matching with pre-trained language models.  _Proceedings of the VLDB Endowment_ 14, 1 (2020), 50–60.
  * Marlin (2004) Benjamin Marlin. 2004\.  _Collaborative filtering: A machine learning perspective_.  University of Toronto Toronto.
  * Miao et al. (2019) Zhengjie Miao, Qitian Zeng, Boris Glavic, and Sudeepa Roy. 2019\.  Going beyond provenance: Explaining query answers with pattern-based counterbalances. In _Proceedings of the 2019 International Conference on Management of Data_. 485–502.
  * Miller (2018) Renée J Miller. 2018\.  Open data integration.  _Proceedings of the VLDB Endowment_ 11, 12 (2018), 2130–2139.
  * Mitchell (1997) Tom Mitchell. 1997\.  Decision tree learning.  _Machine learning_ 414 (1997), 52–78.
  * Müller et al. (2006) Heiko Müller, Johann-Christoph Freytag, and Ulf Leser. 2006.  Describing differences between databases. In _Proceedings of the 15th ACM international conference on Information and knowledge management_. 612–621.
  * Narayanan et al. (2018) Menaka Narayanan, Emily Chen, Jeffrey He, Been Kim, Sam Gershman, and Finale Doshi-Velez. 2018\.  How do humans understand explanations from machine learning systems? an evaluation of the human-interpretability of explanation.  _arXiv preprint arXiv:1802.00682_ (2018).
  * Nargesian et al. (2019) Fatemeh Nargesian, Erkang Zhu, Renée J. Miller, Ken Q. Pu, and Patricia C. Arocena. 2019\.  Data Lake Management: Challenges and Opportunities.  _Proc. VLDB Endow._ 12, 12 (aug 2019), 1986–1989.  https://doi.org/10.14778/3352063.3352116
  * Nargesian et al. (2018) Fatemeh Nargesian, Erkang Zhu, Ken Q. Pu, and Renée J. Miller. 2018.  Table Union Search on Open Data.  _Proc. VLDB Endow._ 11, 7 (mar 2018), 813–825.  https://doi.org/10.14778/3192965.3192973
  * Nierman and Jagadish (2002) Andrew Nierman and HV Jagadish. 2002.  Evaluating Structural Similarity in XML Documents.. In _webdb_ , Vol. 2. Citeseer, 61–66.
  * Orvalho et al. (2020) Pedro Orvalho, Miguel Terra-Neves, Miguel Ventura, Ruben Martins, and Vasco Manquinho. 2020\.  SQUARES: a SQL synthesizer using query reverse engineering.  _Proceedings of the VLDB Endowment_ 13, 12 (2020), 2853–2856.
  * Özmen et al. (2021) Aslihan Özmen, Mahdi Esmailoghli, and Ziawasch Abedjan. 2021\.  Combining Programming-by-Example with Transformation Discovery from large Databases. In _Datenbanksysteme für Business, Technologie und Web (BTW 2021), 19. Fachtagung des GI-Fachbereichs ,,Datenbanken und Informationssysteme” (DBIS), 13.-17. September 2021, Dresden, Germany, Proceedings_ _(LNI)_ , Kai-Uwe Sattler, Melanie Herschel, and Wolfgang Lehner (Eds.), Vol. P-311. Gesellschaft für Informatik, Bonn, 313–324.  https://doi.org/10.18420/btw2021-16
  * Papenbrock et al. (2015) Thorsten Papenbrock, Jens Ehrlich, Jannik Marten, Tommy Neubert, Jan-Peer Rudolph, Martin Schönberg, Jakob Zwiener, and Felix Naumann. 2015.  Functional Dependency Discovery: An Experimental Evaluation of Seven Algorithms.  _Proc. VLDB Endow._ 8, 10 (2015), 1082–1093.  https://doi.org/10.14778/2794367.2794377
  * Poursabzi-Sangdeh et al. (2021) Forough Poursabzi-Sangdeh, Daniel G Goldstein, Jake M Hofman, Jennifer Wortman Wortman Vaughan, and Hanna Wallach. 2021.  Manipulating and measuring model interpretability. In _Proceedings of the 2021 CHI conference on human factors in computing systems_. 1–52.
  * Rahm and Bernstein (2001) Erhard Rahm and Philip A Bernstein. 2001.  A survey of approaches to automatic schema matching.  _the VLDB Journal_ 10, 4 (2001), 334–350.
  * Roddick (1995) John F Roddick. 1995\.  A survey of schema versioning issues for database systems.  _Information and Software Technology_ 37, 7 (1995), 383–393.
  * Rodríguez et al. (2018) Pau Rodríguez, Miguel A Bautista, Jordi Gonzalez, and Sergio Escalera. 2018.  Beyond one-hot encoding: Lower dimensional target embedding.  _Image and Vision Computing_ 75 (2018), 21–31.
  * Roy et al. (2015) Sudeepa Roy, Laurel Orr, and Dan Suciu. 2015.  Explaining query answers with explanation-ready databases.  _Proceedings of the VLDB Endowment_ 9, 4 (2015), 348–359.
  * Schüle et al. (2021) Maximilian E Schüle, Josef Schmeißer, Thomas Blum, Alfons Kemper, and Thomas Neumann. 2021\.  TardisDB: Extending SQL to Support Versioning. In _Proceedings of the 2021 International Conference on Management of Data_. 2775–2778.
  * Shah et al. (2021) Vraj Shah, Jonathan Lacanlale, Premanand Kumar, Kevin Yang, and Arun Kumar. 2021.  Towards Benchmarking Feature Type Inference for AutoML Platforms. In _Proceedings of the 2021 International Conference on Management of Data_. 1584–1596.
  * Shraga et al. (2020) Roee Shraga, Avigdor Gal, and Haggai Roitman. 2020.  Adnev: Cross-domain schema matching using deep similarity matrix adjustment and evaluation.  _Proceedings of the VLDB Endowment_ 13, 9 (2020), 1401–1415.
  * Shraga and Miller (2022) Roee Shraga and Renée J. Miller. 2022.  Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-V (Technical Report).  https://github.com/shraga89/ExplainDaV/blob/main/Explain_Da_V_TR.pdf
  * Singh (2016) Rishabh Singh. 2016\.  BlinkFill: Semi-supervised Programming By Example for Syntactic String Transformations.  _Proc. VLDB Endow._ 9, 10 (2016), 816–827.  https://doi.org/10.14778/2977797.2977807
  * Singh and Gulwani (2012) Rishabh Singh and Sumit Gulwani. 2012.  Learning Semantic String Transformations from Examples.  _Proc. VLDB Endow._ 5, 8 (2012), 740–751.  https://doi.org/10.14778/2212351.2212356
  * Snodgrass et al. (2008) Richard T Snodgrass, Curtis Dyreson, Faiz Currim, Sabah Currim, and Shailesh Joshi. 2008\.  Validating quicksand: Temporal schema versioning in $\tau$XSchema.  _Data & Knowledge Engineering_ 65, 2 (2008), 223–242.
  * Sutton et al. (2018) Charles Sutton, Timothy Hobson, James Geddes, and Rich Caruana. 2018.  Data diff: Interpretable, executable summaries of changes in distributions for data wrangling. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 2279–2288.
  * Thrampoulidis et al. (2015) Christos Thrampoulidis, Samet Oymak, and Babak Hassibi. 2015\.  Regularized linear regression: A precise analysis of the estimation error. In _Conference on Learning Theory_. PMLR, 1683–1709.
  * Ting et al. (2018) Kai Ming Ting, Sunil Aryal, and Takashi Washio. 2018\.  Which Outlier Detector Should I use?. In _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 8–8.
  * Tran et al. (2014) Quoc Trung Tran, Chee-Yong Chan, and Srinivasan Parthasarathy. 2014\.  Query reverse engineering.  _The VLDB Journal_ 23, 5 (2014), 721–746.
  * Vassiliadis (2009) Panos Vassiliadis. 2009\.  A survey of extract–transform–load technology.  _International Journal of Data Warehousing and Mining (IJDWM)_ 5, 3 (2009), 1–27.
  * Vijayarani et al. (2015) S Vijayarani, Ms J Ilamathi, Ms Nithya, et al. 2015\.  Preprocessing techniques for text mining-an overview.  _International Journal of Computer Science & Communication Networks_ 5, 1 (2015), 7–16.
  * Wang and Meliou (2019) Xiaolan Wang and Alexandra Meliou. 2019.  Explain 3D: explaining disagreements in disjoint datasets.  _Proceedings of the VLDB Endowment_ 12, 7 (2019).
  * Wang et al. (2003) Yuan Wang, David J DeWitt, and J-Y Cai. 2003.  X-Diff: An effective change detection algorithm for XML documents. In _Proceedings 19th international conference on data engineering (Cat. No. 03CH37405)_. IEEE, 519–530.
  * Yan and He (2020) Cong Yan and Yeye He. 2020\.  Auto-suggest: Learning-to-recommend data preparation steps using data science notebooks. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_. 1539–1554.
  * Yang et al. (2021) Junwen Yang, Yeye He, and Surajit Chaudhuri. 2021.  Auto-pipeline: synthesizing complex data pipelines by-target using reinforcement learning and search.  _Proceedings of the VLDB Endowment_ 14, 11 (2021), 2563–2575.
  * Yilmaz et al. (2018) Gunce Su Yilmaz, Tana Wattanawaroon, Liqi Xu, Abhishek Nigam, Aaron J Elmore, and Aditya Parameswaran. 2018.  Datadiff: User-interpretable data transformation summaries for collaborative data analysis. In _Proceedings of the 2018 International Conference on Management of Data_. 1769–1772.
  * Zhang et al. (2020) Amy X Zhang, Michael Muller, and Dakuo Wang. 2020\.  How do data science workers collaborate? roles, workflows, and tools.  _Proceedings of the ACM on Human-Computer Interaction_ 4, CSCW1 (2020), 1–23.
  * Zheng and Casari (2018) Alice Zheng and Amanda Casari. 2018.  _Feature engineering for machine learning: principles and techniques for data scientists_.  ” O’Reilly Media, Inc.”.
  * Zhu et al. (2019) Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J Miller. 2019.  Josie: Overlap set similarity search for finding joinable tables in data lakes. In _Proceedings of the 2019 International Conference on Management of Data_. 847–864.
  * Zhu et al. (2017) Erkang Zhu, Yeye He, and Surajit Chaudhuri. 2017.  Auto-Join: Joining Tables by Leveraging Transformations.  _Proc. VLDB Endow._ 10, 10 (2017), 1034–1045.  https://doi.org/10.14778/3115404.3115409