Quantifying Uncertainty in Aggregate Queries over Integrated Datasets

The ideas in this paper are highly related to the concept of “reverse data management” proposed by Meliou et al. (meliou2011reverse, ; meliou2012tiresias, ). Meliou et al. argue that as data grow in complexity, analysts will increasingly want to know not what their data currently says but what changes have to happen to the dataset to force a certain outcome. Such how-to analyses are useful in debugging, understanding sensitivity, as well as planning for future data. Meliou et al. build on a long line of what-if analysis and data provenance research, which study simulating hypothetical updates to a database and understanding how query results might change  (deutch2013caravan, ; buneman2001and, ).

We find that there is a gap in the literature when it comes to data integration problems, which are generally not easily expressible in standard relational algebra (halevy2006data, ). One decade ago, there was some interest in uncertainty management for data integration (magnani2010survey, ). While these papers have been successful in the confines of inference and approximation, they do not concern themselves with quantifying the uncertainty propogated to downstream query results. Similar to (liang2020fast, ), we find that quantifying extremal behavior of aggregate queries is substantially more objective than parameterizing an entire probability distribution.

In the confines of data integration, there has been considerable efforts in entity matching techniques (entity-res-dataset-origin-2010, )(moma-dataset-ref, )(dedoop-dataset-ref, )(learning-based-dataset-ref, ). However, these papers also do not consider ways in which we can quantify uncertainty in query outcomes of integrated datasets. Our paper makes use of the datasets that these papers have used, and we expand on the idea of how we can create hard bounds for quantified uncertainty in the downstream query result.

This unevenness of uncertainty is an instance of an often under-appreciated statistical phenomenon called heteroscedasticity. Formally, heteroscedasticity happens when the variability of the random disturbance is different across elements of the vector. The database equivalent is where different rows (or more generally different query predicates) have wildly different levels of certainty of their values. Kaufman suggests that about twice as many articles should be testing and correcting for data heteroscedasticity than they currently do  (kaufman2013heteroskedasticity, ). Kaufman calls for action to care more about heteroscedasticity by pointing out that it is more common than it is usually recognized by researchers.

Now, we will introduce a formal problem statement that will guide the remainder of the technical discussion. Every table has a set of identifying attributes and measurement attributes. Identifying attributes describe the entity a row refers to, and measurement attributes describe a quantifiable property of the entity. For example, let $R$ be a relation over the attributes $A$, the attribute set can be decomposed into $R[A_{id}\cup A_{measurement}]$. If $\mathcal{U}$ denotes a universe of real-world entities, there exists a mapping between each row to a corresponding real-world entity through the identifying attribute:

where $\Pi$ denotes the standard projection operator. In our example dataset, the real-world entities are actual products that the company sells. The Product_Tag is an identifying attribute that corresponds to some real-world entity, and the N_Complaints attribute is a measurement.

Existing frameworks have made initial progress towards such problems problem (potti2015daq, ; liang2020fast, ), but they are limited in how they handle queries across multiple tables. DAQ (potti2015daq, ) defines a concept of upper and lower relations to bound the result of uncertain aggregates. Associated with each cell in a table is a range of possible values, and these ranges can be propagated through aggregate queries. One could use an approach inspired by DAQ to estimate $l$ and $u$.

For example, first we would construct the following sets for each row $r$ of the base table:

This is the set of $s$ rows that match with the chosen $r$. For every attribute in $b\in B$, one can calculate:

for each $r$, and assume that categorical attributes are dictionary encoded. If we did this for each row $r$ this would create table over attributes $A$ and $B$ with value ranges on each $B$ value. Using an algorithm like the one in (potti2015daq, ), one can compute an upper bound and lower bound for all SUM,COUNT, and AVG queries with predicates.

The set $\Psi(r,s)$ can be thought of as defining a graph over the entities in $R$ and $S$. Let $V_{R},V_{S}$ be defined as the set of all identifying tuples from both $R$ and $S$ respectively.

We can define a bipartite graph between these sets where an edge exists if there exists an $r[A_{id}],s[B_{id}]\in\Psi(r,s)$.

Every valid augmentation can described as a subgraph of this bipartite graph where each $v_{s}\in V_{S}$ has an edge to at most one $v_{r}\in V_{R}$. Such a subgraph is called an unbalanced assignment, i.e., assigning a $v_{s}$ to a $v_{r}$. The existence of such subgraphs gets to the essence of the coupling problem shown by the example in the previous section. If we match one pair $r[A_{id}],s[B_{id}]$ of identifying tuples, it affects how we can match others. Double counting happens because we don’t appropriately account for this.

We denote the maximization problem $GA_{max}$ and the minimization problem $GA_{min}$. These core subroutines in our result interval estimation algorithm. Let’s now try to understand when these optimization problems are meaningful. Suppose, we have a candidate set $\Psi$ and contained in this candidate set is the correct matching $M^{*}$ between the tables $R$ and $S$. $M^{*}$ can be thought of as subgraph of $\Psi$. For any weighting function, let $\mathcal{W}(M^{*})$ be:

It follows that:

This proposition gives us an understanding of when it is possible to bound the range of values a sum of weights could take. Namely, it is only possible if the true matching is contained in the candidate set. This is less a statement of assumption and more a statement of semantics:

This proposition is true for all weighting functions and we will show the an individual query processing instance can be represented as a specific weighting function.

The asymmetry between false positives and false negatives creates another issue. Notice that the primary constraint is of the form $\forall s\in S:\sum_{r\in R}x_{r,s}$. In a sense, this constrains the number of $s$’s that can match with an $r$ but not the reverse. While this is notionally true based on our definitions, it can lead to serious robustness issues.

Consider the real data from the Amazon-Google product matching dataset. While the candidate set matches most products nearly one-to-one, some products match with nearly 120 others. The imprecision in the candidate set can create implausible assignment scenarios where hundreds of different $S$ entities match with a single one in $R$. Similar to the concept of regularization in machine learning, we need to constrain the optimization problem to penalize degenerate solutions that might occur in highly skewed candidate sets. We add a constraint of the following form that limits the in-degree of each $r$ in final the assignment to a value $N$:

Note that the addition of this constraint may make the optimal matching “invalid” as some of the entities in $S$ may not be matched with entities in $R$. But, it is a crucial knob for the user to control the resilience to skew. One can think of $N$ as analogous to the probability in a statistical confidence interval: the higher the probability the more conservative the intervals are. $N$ serves a similar function.

The lines that we have drawn restricting this problem space are crucial. In fact, even slightly more complex versions of this problem become computationally hard. The key issue is that while bipartite matching (and its constrained variants in this paper) can be solved in polynomial time, tripartite matching is NP-Complete  (karp1972reducibility, ). For example, if one were to relax the problem statement to allow for base tables that are not de-duplicated such a matching could arise. In this case, we would have to enforce that that not only is there a functional dependency between the entities in $S$ and $R$, but also within $R$ the matchings are consistent to rows that refer to the same entity. Solving the joint problem is NP-Complete, and the most reasonable heuristic is to first de-duplicate $R$ and then proceed with the interval calculations.

In our framework, users define candidate matches with a simple API: a similarity measure between entities in $R$ and $S$, and a threshold. This API is sufficient to generate a set of candidate matches $\Psi$. Some entity matching frameworks leverage “blocking”, which subdivides a dataset into blocks before similarity comparisons. This information is also easy to integrate into the framework and would simply remove edges from $\Psi$. Finally, the user specifies a $N$ which is the maximum number of rows in the augmenting table that could match with rows in the base table.

First, we will construct the bounds for SUM and COUNT queries. Once the candidate set of matches $\Psi$ is constructed and the constraint $N$ is known, result interval calculation for SUM/COUNT queries is relatively straight-forward. We simply define the graph weights from the previous section based on the query.

Let $r$ be a row in $R$ and s be a grouped set of rows with the same identifying attribute in $S$. We can think of this pairing as a hypothetical sub-table with rows:

Over this sub-table, we can apply the user-specified SQL predicate, which will return a subset of those pairings $pred(r\times\textbf{s})$. Let’s define the following quantities:

• •

  $\text{sum}(r,\textbf{s})$ The total SUM of the SQL aggregation attribute over $pred(r\times\textbf{s})$.

• •

  $\text{count}(r,\textbf{s})$ The total COUNT of the SQL aggregation attribute over $pred(r\times\textbf{s})$.

For COUNT queries, the weighting $W(r,\textbf{s})$ is .

For SUM queries, the weighting $W(r,\textbf{s})$ is defined as:

The solution to the equations 1 and 2 calculate upper and lower bounds for SUM and COUNT queries. This can be directly seen from the formulas in the equations. The objective function optimizes a sum over edge weights, and both SUM/COUNT queries can be expressed as a sum. Thus, the result finds the minimum and maximum sum of weights over all unbalanced matchings. This is equivalent to finding the minimum/maximum value of SUM/COUNT queries over all valid augmentations contained in the candidate set.

Furthermore, since this section describes how to deal with the multiplicity in $S$ rows, we’ll remove the boldface notation s for brevity in the following discussion (with the assumption that it is handled in the same way).

Answering AVG queries are a little more complicated since they are not neatly expressed as sums of weights, with the objective being:

where $sgn$ is the sign function. We use a simple trick to estimate average queries by upper and lower bounding this objective. Essentially, we consider calculating the result intervals for an equivalent SUM query, we bound the maximum and minimum value that the denominator could take at attainment.

The proof of this proposition is contained in the appendix. This proposition shows that the AVG query can be answered with a scaled version of the SUM query. Thus, experimentally, we focus our efforts SUM and COUNT queries knowing that AVG queries are essentially the same.

Beyond their absolute interpretations, result intervals are also useful in relative terms. One can compare result intervals from different query predicates to understand how uncertainty is distributed through a dataset. Suppose we have a table $\hat{M}$ which is the final valid augmentation that a user chooses, and let $q(\hat{M})$ be a nominal query result that is the result of an aggregate query over the final matching. Let $(l,u)$ denote a result interval calculated using the procedures mentioned in the paper.

The relative error in a query result is $rel(q)=\frac{u-l}{q(\hat{M})}$. This metric normalizes for the fact that some queries have naturally higher results than others. Using this metric, different queries can be compared in terms of their relative errors, e.g., $rel(q_{1})>rel(q_{2})$. This is an instrumental tool to understanding potential systematic biases that might arise from data integration.

To show how all of this estimation works, we will work through a simple but illustrative numerical example. Let’s consider the dataset described in the introduction. We construct a set of candidate matches using a Jaccard Similarity threshold of 0.3. This results in graph with the following adjacency matrix, where rows are base table entities and columns are augmenting table entities.

Queries are processed as weighted graphs over such a matrix. Consider the query:

This query would generate the following weighted graph, described as its adjacency matrix:

A valid augmentation assigns all $S$ entities to only one $R$ entity. We can easily see that the following assignment is a maximizer: ’StarGazer Premier Pro -¿ StarGazer Premier Pro’, ’StarGazer -¿ StarGazer Premier Pro’, ’StarGazer Academic -¿ StarGazer Academic’, ’Extended Warranty -¿ Extended Warranty’. The maximizer has a SUM of 84. Likewise, we can see that the minimizer is an assignment: ’StarGazer Premier Pro -¿ StarGazer Premier Pro’, ’StarGazer -¿ StarGazer Academic’, ’StarGazer Academic -¿ StarGazer Academic’, ’Extended Warranty -¿ Extended Warranty’. The minimizer is a valid augmentation because every $S$ is assigned along an edge in the original adjacency matrix. The minimizer has a value of $33$.

We consider real-life datasets, which have a ground truth matching, in our experiments so that we can compare actual numbers to our interval calculations  ¹¹1Please see following for access to used datasets: https://dbs.uni-leipzig.de/research/projects/object_matching/benchmark_datasets_for_entity_resolution. All the datasets are “title” matching datasets like our example, and we use a Jaccard similarity metric. It should be noted that the similarity metric can be any similarity metric provided by the user because the specific similarity metric is not the point of our experiments. For our purposes, Jaccard similarity is an appropriate similarity metric for all real data sources that have been used. The table below shows statistics information relevant for our investigation about the real datasets.

The following algorithms give us alternative result interval estimates.

In our first set of experiments, we explore result interval calculation on the real datasets.

Next, we dig deeper into the relationship between the result interval length and the failure-to-bound rate. The GA algorithm is guaranteed to bound the result if the candidate set contains the ground truth matching. This is often hard to achieve in practice without making a permissive candidate set that errs on the side of false positives. On the other hand, such false positives can easily lead to extreme result interval estimates.

The matching constraint allows one to control the sensitivity to extreme results. However, with the constraint, we are no longer guaranteed to bound the true result. Intuitively, the tighter the intervals the more likely a failure happens. Figure 5A illustrates in the Google-Amazon product matching case for the SUM query. As, we make the matching constraint stricter the interval size drops but the failure-to-bound rate increases. This relationship is not unlike those in statistical confidence intervals (e.g., $\pm 10$ with $95\%$ probability).

There is also an interesting relationship when one considers how query selectivity affects these metrics. Figure 5 plots the result interval length and the failure to bound rate as a function of query selectivity. We apply predicates of different average selectivity to the Google-Amazon SUM query. As the queries become more selective, the failure-to-bound rate increases. This is because no candidate set is perfect, and those errors can get cancelled out for less selective queries.

Since ground-truth data is very difficult to find in a real-life setting for 1 to n matches, using synthetic datasets proved to be the best way to micro-benchmark the approach. The synthetic datasets are created using the following approach: first, the user provides a base table. Then, the provided table is used as a baseline to create the second table. In the creation process of the second table, random typos are added with varying degrees (the range varies between Levenshtein distance of 1 to 3). Therefore, this dataset is generated with a known ground-truth matching and known similarity metric that relates the entities in both tables.

In order to reflect the real-life challenge of having a range of possible matchings for each distinct entry, the experiments are done with both balanced and skewed matching settings. In this context, balanced matching refers to a ground truth matching of exactly $n$ number of matches guarantee. Skewed matching refers to a 1 through $n$ number of possible matches for each entry. For the skewed matching setting, a randomly generated number between $1$ and $n$ is used in order to provide a randomized skew in the number of possible matches for each entry in the base table. Over this dataset, we run SUM queries with randomly generated predicates uniformly with a selectivity of 0.1.

Finally, the whole purpose of the proposed framework is to allow data scientists to assess uncertainty in data integration problems. We present a case study to illustrate the types of analysis that our framework would allow.

Many public health organizations recognize that, beyond focusing on and treating biological mechanisms of disease, advancing health also critically requires accounting for and striving to mitigate adverse consequences of social, environmental, behavioral, and psychological factors. To date, such factors have not been comprehensively codified and quantified in a way suitable for large-scale co-analysis/data-mining with explicitly biological or clinical data to learn new insights into factors influencing wellness or disease. We worked with researchers at the University of Chicago Medical School to organize a pilot dataset that links patient data with social factors based on GPS location data that indicates key lifestyle factors.

One such important factor is the availability of fresh food and produce near a patient’s home (shannon2014food, ). The City of Chicago maintains a dataset of all business licenses in the city ²²2https://data.cityofchicago.org/Community-Economic-Development/Business-Licenses-Current-Active/uupf-x98q. These licenses contain business activity descriptions so that one could identify stores that sell fresh food. However, these city-level classifications are not always precise.

Consider two different establishments in the dataset that sell fresh produce. One of them is tagged appropriately and the other is not.

Reconciling each one of these ambiguities by hand is extremely time-consuming. Luckily a prior dataset from 2013 exists that took a survey of such stores in Chicago (https://data.cityofchicago.org/Community-Economic-Development/Map-of-Grocery-Stores-2013/ce29-twzt). If an existing business is not appropriately tagged as a grocery store that sells fresh produce and it is contained in the old dataset, it is possibly a grocery store. Of course, the names and addresses from these two datasets do not completely align because they were collected in different time-periods.

The combination of these two datasets will be heuristic, but we can apply our proposed GA optimization framework to determine our confidence in that merging process. Here’s how it works:

• •

  Base Table. Current dataset of Chicago Business Listings that are not already tagged as grocery stores.

• •

  Augmenting Table. Prior dataset of Grocery Store Listings in Chicago.

• •

  Candidate Set. Use a Jaccard Similarity Matching over store name and address with threshold $0.7$.

• •

  Matching Cardinality Constraint. Match with at most 1 base table entity.

• •

  Query. Count the fresh fruit and produce stores in each census tract.

The result of this framework determines a range of grocery store counts per census tract. Intuitively, it gives a high estimate based on generous matchings between the augmenting table and the base table, and a low estimate by assuming they don’t match.

We can use this calculation to understand where there is uncertainty in this combined dataset and what kind of biases this uncertainty might introduce. Some census tracts will have cleaner data, and others will have more ambigious data. ”Cleaner” can either mean that the current business listings are appropriately tagged or that there are clearer matches in the prior dataset. Figure 8 illustrates the uncertainty calculations by our framework mapped across the census tracts in the city of Chicago. In fact, we found that the data quality issues were more severe in minority neighborhoods leading to more ambiguous estimates.

The key insight is that the following equality holds at both the attainment of the minimum and maximum:

That is, that every $s\in S$ is matched to one $R$.

Leveraging this insight, let’s first consider bounding the minimum. Notice the denominator of the objective function above:

Th term summation is $\textbf{sgn}(W(r,s))\cdot x_{r,s}$, which is the product of two binary variables. Both of these have to be equal to $1$ to increase the sum. Therefore,

We know both of the following expressions hold at the minimum:

Which means that:

It follows that this inequality holds for any minimizer of the SUM objective:

Leading to:

Now, let’s consider the maximum. For each $s\in S$, let $d(s)$ be the following.

$d(s)$ is equal to $1$ if there exists at least one non-zero edge, and equal to zero otherwise. At attainment of the maximum sum, the following must be true:

It can be easily seen using set intersection logic that the following must hold :

Which leads to the following inequality at every maximizer of the SUM for $d=\sum_{s\in S}d(s)$:

And finally,