Let's Make it Dirty with BART!

Abstract

In the last few years many automatic or semi-automatic data-repairing algorithms have been proposed in order to improve the quality of a given database. Due to the richness of research proposals, it is important to conduct experimental evaluations to assess each tool's potential. Bart is an open-source error-generation system conceived to support thorough experimental evaluations of these data-repairing systems. In this paper we discuss how generating errors in data is a complex problem, with several facets. We introduce the important notions of detectability and repairability of an error, that stand at the core of Bart. Then, we show how, by changing the features of errors, it is possible to in uence quite signi cantly the performance of the tools. Finally, we concretely put to work ve data-repairing algorithms on dirty data of various kinds generated using Bart, and discuss their performance.

Introduction

Data quality is a very important concern in data management. To date, many (disparate) automatic and semi-automatic data-cleaning algorithms have been proposed in the database community [ 13 ][ 12 ][ 8 ][ 5 ][ 6 ][ 4 ]. These algorithms come from di erent inspirations. Most of them are constraint-based : they assume that the target database comes with a set of data-quality rules { for example, functional dependencies (FDs) or conditional functional dependencies (CFDs) { and data is repaired to remove violations to these constraints. Others, on the contrary, do not rely on constraints, but rather on statistics-based approaches to identify suspect values or outliers and try to repair them.

Due to the richness of research proposals, it is important to conduct thorough and fair experimental evaluations to assess each tool's potential. In fact, other elds like entity resolution, record linkage, schema mapping and data exchange have worked to develop consolidated tools and benchmarks for empirically evaluating algorithms [ 14 ] [ 1 ] [ 3 ]. Thorough evaluation of data-cleaning systems requires systematic control over the amount of errors in a dataset, and over how hard these errors are to repair. Dirty datasets must be paired with a ground-truth clean dataset to enable evaluation of the quality of a repair produced by a cleaning algorithm. To support rigorous empirical evaluations, an error-generation system must be able to generate multiple dirty versions of a dataset with low user e ort, and scale to large datasets.

Bart. Bart [ 2 ][ 17 ] is the rst error-generation tool explicitly conceived to support empirical evaluations of data-repairing algorithms as per the requirements outlined above. It takes as input a clean database and a set of data-quality rules, and injects errors into the database. Rules are expressed using the powerful language of denial constraints [ 15 ] and errors can be of several kinds, such as typos, duplicated values, nulls, and outliers. We show the major components of the system in Figure 1. A user interacts with Bart by creating error-generation tasks, using a GUI or CL interface. These tasks are then interpreted by Bart's error-generation engine to create dirty versions of a clean database.

The system provides the highest possible level of control over the errorrgaemneertaetriso,n iptroaclleosws.s Aumseornsg toothcehroposae- BART BART GUI Command Line the percentage of errors, whether they Error-generation Engine want a guarantee that errors are detaencdtaebvleenupsrionvgidtehseagniveesntimcoantestorfaihnotws, DBMS Error thoaridtsit owriigllinbaeltoclreeasntosrteatthee. dBaatarbtasies CDleBan VeDVrVeDisrerDtiisroryitisrnoytioynn GenTearsaktion open-source: its codebase is available on GitHub and can be further ex- Fig. 1. Bart System Overview tended by the community to develop new features and functionalities.

Evaluation Overview. The empirical evaluation convey three primary insights about the system. (i) First, we will discuss how the ne-level control over the features of errors distinguishes Bart from previous error-generating techniques used in evaluating data-repairing systems. (ii) Then, we will discuss how the characteristics of errors may signi cantly in uence the quality of repairs generated by a system. (iii) Finally, we will demonstrate ve di erent algorithms in action on dirty data generated using Bart, to reveal new insights on their (relative) performance as the characteristics of the errors are varied by Bart.

Overall, the attendees will learn how the availability of a tool like Bart may help to level the eld and raise the bar for evaluation standards in data cleaning.

The paper is organized as follows. Section 2 introduces the main motivation for the system, and the notions of detectability and repairability of errors. SecBart: Benchmarking Algorithms for data Repairing and Translation https://github.com/dbunibas/BART tion 3 provides an overview of the system and of its main use cases. Finally, Section 4 discusses the empirical evaluation, and the main lessons that can be learned from it. 2

Concept and Motivation

Assume we are given a database about soccer players, shown in Figure 2, and we want to assess the performance of repair algorithms according to a few dataquality rules. (i) A rst FD stating that Name and Season are a key for the table: d1 : Name; Season ! Team; Stadium; Goals. (ii) And, a second FD stating that Team implies Stadium: d2 : Team ! Stadium.

We specify these rules in Bart using the language of denial constraints. Denial constraints are a very expressive language, capable of capturing most dataquality rules used for data-repairing, including FDs, CFDs, cleaning equalitygenerating dependencies, editing rules, xing rules, and ordering constraints [ 13 ]. For the sake of simplicity, here we omit the technical details about the syntax and semantics of denial constraints, and show example data-quality rules in the more familiar syntax of FDs.

To evaluate data-repair systems, we proceed as follows. (i) We start with a clean instance I , like the one in Figure 2, and the set of constraints = fd1; d2g discussed above. (ii) We inject errors by applying a set of cell changes; each cell change ch = hti:A := vi updates the value of attribute A in tuple ti to a new value v, e.g, ht1:Season := 2011-12i. By applying a set of cell changes Ch to I , we obtain a new instance Id = Ch(I ), named the dirty instance. (iii) We run a data-repairing algorithm over Id to obtain a repaired instance Irep. We measure the quality of the algorithm using precision and recall. Intuitively, we count how many changes in Ch have been restored to their original values in Irep. Further details are in the full paper [ 2 ].

We want now to emphasize how di erent ways to change the cells of the clean instance may lead to errors that show completely di erent features when considered from the perspective of a data-repairing tool. 2.1

Detectability

When evaluating a constraint-based repair algorithm, we want to make sure the errors we inject are detectable by the system in question. After all, an error that cannot be detected, cannot be repaired. To reason about detectability, we need a notion for determining whether a cell change is involved in a constraint violation. Consider the following cell change: ch1 = ht1:Season := 2012-13i that updates tuple t1 as follows:

Player Name Season Team Stadium Goals

t1 : Giovinco 2012-13 Juventus Juv.Stadium 3

This change does not introduce a violation to any of the constraints in , i.e., after the cell change the modi ed database instances does ful ll all the constraints. Therefore, any data-repairing tool that relies on the constraints to detect dirtiness in the database will not be able to detect the change. We call this an undetectable change.

More formally, a cell change ch = hti:A := vi in Ch introduces a detectable error in I for constraint dc if: (i) cell ti:A is involved in a violation with dc in instance Id, and (ii) cell ti:A was not involved in a violation with dc in instance I . Here \involved in a violation" is de ned based on the fact that a constraint can be associated with a query that returns sets of cells that cause a violation. We call this type of queries violation-detection queries. A cell is involved in a violation with a constraint dc if it is in the result of the violationdetection query for dc [ 2 ]. For example, the violation-detection query for d2 is Qd2 (i; i0; t; a; a0) = Player(i; n; s; t; a; g); Player(i0; n0; s0; t; a0; g0); a 6= a0; i 6= i0. This query returns the Team and Stadium attributes of pairs of Player tuples with the same team, but di erent stadiums. Using the tuple id's, sets of cells involved in violations can be determined based on the result of this query.

Bart allows users to control whether changes to the clean database are detectable when using the constraints in . Bart may be con gured to generate random changes, that do not need to be detectable, or errors that are guaranteed to be detectable using the constraints. Note this requires Bart to reason e ciently and holistically about a set of changes to ensure that they are detectable using a given set of constraints.

Interestingly, this latter requirement signi cantly increases the complexity of the error-generation process. In fact, generating a given number of errors in a clean database that are detectable using a set of constraints is an NPcomplete problem [ 2 ]. To deal with this complexity Bart implements several novel optimizations [ 2 ] that balance the need for control over the nature of errors and scalability.

We assume every tuple has a unique identi er that per convention is the rst attribute. Queries are expressed in a notation similar to Datalog. 2.2

Repairability

An alternative change that indeed introduces a detectable error is the following: ch2 = ht1:Season := 2014-15i. After this update, tuples t1 and t2 violate FD d1, which states that Name and Season are a key for the table:

Player Name Season Team Stadium Goals

t1 : Giovinco 2014-15 Juventus Juv.Stadium 3 t2 : Giovinco 2014-15 Toronto BMO Field 23

This change is easily detected using the constraints. Still, it is quite di cult for an automatic data-repairing algorithm to restore the database to its clean state. Notice, in fact, that after this change, the original value 2013-14 has been removed from the active domain of the dirty database. A correct repair cannot be found by any repair algorithm that uses the values in the database as the candidates for repair. Bart uses the notion of repairability of an error to characterize this aspect. In the case above, it would assign repairability 0 to change ch2. Di erent detectable changes may have quite di erent repairability values. As an example, consider now change ch3 = ht1:Stadium := Delle Alpii. The change is detectable using FD d2. In addition, the redundancy in the dirty database may be used to repair the database:

Player Name Season Team Stadium Goals

t1 : Giovinco 2013-14 Juventus Delle Alpi 3 t3 : Pirlo 2014-15 Juventus Juv.Stadium 5 t5 : Vidal 2014-15 Juventus Juv.Stadium 8

The new, dirty tuple t1 is involved in two violations to d2, one with t3, another with t5. In both cases, the change is in violation with Juv.Stadium. By a straightforward probabilistic argument, Bart would calculate a 2=3 repairability for this error, and rank it as a medium-repairability error.

Errors may have higher repairability, even 1 in some cases. Consider, for example, an additional rule d3: Team[J uventus]; Season[2013 14] ! Stadium[J uv:Stadium]. This CFD rule states unequivocably that Juventus has played its home games for season 2013{14 in the Juventus Stadium. Since this knowledge is part of the constraint, the dirty cell can easily be restored to its original, clean state. 2.3

Other Kinds of Errors

To conclude this discussion about the features of errors, we notice that the notions of detectability and repairability, that are centered around detecting violations to constraints, are not the only ones supported by Bart.

Consider, for example, change ch4 = ht1:Goals := 123i. This change is not detectable using the constraints. However, it might be detected by a statistics-based data-repairing algorithm, because it introduces an outlier into the distribution of values of the Goals attribute. Bart can be con gured in order to generate changes of this kind as well. Bart provides users with the graphical user interface shown in Figure 3 to handle error-generation tasks. An error-generation task, E is composed of four key elements: (i) a database schema S; (ii) a set of denial constraints (DCs) encoding data quality rules over S; (iii) an instance I of S that is clean with respect to ; (iv) a set of con guration parameters Conf (shown in Figure 3.1) to control the error-generation process. These parameters specify, among other things, which relations can be changed, how many errors should be introduced, and how many of these errors should be detectable. They also let the user control the degree of repairability of the errors.

Based on this, Bart supports several uses cases. The main one consists of generating a desired degree of detectable errors for each constraint. In addition, users may also specify a range of repairability values for each constraint; Bart will estimate the repairability of changes, and only generate errors with estimated repairability within that range. In addition to detectable errors, Bart may also generate random errors of several kinds: typos (e.g., `databse'), duplicated values, bogus or null values (e.g., `999', `***'). Random errors may be freely mixed with constraint-induced ones. Finally, Bart can introduce outliers in numerical attributes. Bart provides sophisticated features to analyze the characteristics of errors that are introduced in the data. It generates charts to analyze the number of errors detected by each constraint, and their estimated repairability (shown in Figure 3.3). It also o ers a versioning system, that allows users to generate di erent dirty databases for the given scenario, and compare the characteristics of their errors.

Finally, Bart o ers a exible set of metrics to measure the quality of the repairs generated by a data-repairing tool. In fact, di erent algorithms can repair data in di erent ways. For example, some algorithms can produce repairs that mark dirty cells using a variable, while others always restore the dirty instance with a constant value. Di erent metrics have been proposed and are implemented in Bart to uniformly evaluate these heterogenous changes in the data [ 4, 11 ]. 4

Empirical Evaluation

We conduct [ 17 ] an empirical evaluation of several data-repairing algorithms over dirty data generated using Bart.

We used two publicly available tools, Llunatic [ 11 ] and Nadeef [ 8 ], to run four rule-based data-repairing algorithms: (i) Greedy [ 5, 7 ]; (ii) Holistic [ 6 ]; (iii) Llunatic [ 10 ]; and (iv) Sampling [ 4 ]. In addition, we evaluated (v) SCARE [ 18 ], a statistics-based tool.

The tools were tested with several repair tasks, based on synthetic and real datasets, some of them constraint-based and some statistics-based. We brie y list them here: (i) Employees is a synthetic scenario in the full paper [ 2 ]; (ii) Customers is a synthetic scenario from Geerts et al. [ 10 ]; (iii) Tax is a synthetic scenario from Fan et al. [ 9 ]; (iv) Bus is a real-world scenario from Dallachiesa et al. [ 8 ]; and (v) Hospital is a real-world scenario used in several data-repairing papers (e.g., [ 8, 10 ]).

Datasets and constraints have been chosen to exhibit di erent characteristics. Some have high redundancy in their data. Others contain numerical attributes, and constraints containing ordering (<, >) comparisons. Some datasets have master-data [ 16 ] and CFDs, while others have only FDs. All these di erences help to validate our techniques and the tools under exam.

Notice the purpose of the evaluation was not to assess the quality of the repair algorithms, rather to show how Bart can be used to uncover new insights into the data-repairing process. Some important insights are the following.

Lesson 1: Data-repairing is not yet Mature. We expect that a wide degree

of variability in quality among all algorithms will emerge from our evaluations. This variability does not clearly emerge from evaluations reported in the literature, suggesting there is no de nitive data-repairing algorithm yet. Lesson 2: Repairability Matters. We observe di erent trends with respect to repairability. Typically, repair algorithms return very good repairs when sufcient information is available (i.e., high repairability); however, their quality tends to degrade quickly as repairability decreases.

A key observation is that repairability has a strong correlation with the quality of the repairs. In this respect, we believe it nicely captures the \hardness" of the data-repairing problem and it helps in getting a concrete intuition of the power and the limits of existing solutions.

Lesson 3: We Need to Document Our Dirty Data. We may conclude that

tools exhibit quite di erent performance on data-repairing problems of di erent nature, and the repairability is a natural proxy to characterize how \di cult" a data-repairing problem is.

In light of this and to level the eld, we believe it is crucial to have at our disposal systematic error-generation tools and to properly document the characteristics of the dirty data used in empirical evaluations of data-repairing solutions. Bart is a concrete step in this direction.

Lesson 4: Generating Errors is Hard. The problem of systematically gen

erating errors, however, is not an easy one. We will show how di erent con gurations of the error-generation task a ect the overall scalability of the system, and discuss the main optimizations that Bart relies on in order to tame the complexity of the process.

References

1. B. Alexe , W. Tan , and Y. Velegrakis . Comparing and Evaluating Mapping Systems with STBenchmark . PVLDB , 1 ( 2 ): 1468 { 1471 , 2008 .

2. P. C. Arocena , B. Glavic , G. Mecca, R. J. Miller , P. Papotti , and D. Santoro . Messing-Up with BART: Error Generation for Evaluating Data Cleaning Algorithms . PVLDB, 9 ( 2 ): 36 { 47 , 2015 .

3. M. Benedikt , G. Konstantinidis, G. Mecca , B. Motik , P. Papotti , D. Santoro , and E. Tsamoura . Benchmarking the chase . In PODS , pages 37 { 52 . ACM, 2017 .

4. G. Beskales , I. F. Ilyas , and L. Golab . Sampling the Repairs of Functional Dependency Violations under Hard Constraints . PVLDB, 3 ( 1 ): 197 { 207 , 2010 .

5. P. Bohannon , M. Flaster , W. Fan , and R. Rastogi . A Cost-Based Model and E ective Heuristic for Repairing Constraints by Value Modi cation . In SIGMOD , pages 143 { 154 , 2005 .

6. X. Chu , I. F. Ilyas , and P. Papotti . Holistic Data Cleaning: Putting Violations into Context . In ICDE , pages 458 { 469 , 2013 .

7. G. Cong , W. Fan , F. Geerts , X. Jia , and S. Ma . Improving Data Quality: Consistency and Accuracy . In VLDB , pages 315 { 326 , 2007 .

8. M. Dallachiesa , A. Ebaid , A. Eldawy , A. K. Elmagarmid , I. F. Ilyas , M. Ouzzani , and N. Tang . NADEEF: a Commodity Data Cleaning System . In SIGMOD , pages 541 { 552 , 2013 .

9. W. Fan , F. Geerts , X. Jia , and A. Kementsietsidis . Conditional Functional Dependencies for Capturing Data Inconsistencies . ACM TODS , 33 , 2008 .

10. F. Geerts , G. Mecca, P. Papotti , and D. Santoro . Mapping and Cleaning . In ICDE , pages 232 { 243 , 2014 .

11. F. Geerts , G. Mecca, P. Papotti , and D. Santoro . That's All Folks! LLUNATIC Goes Open Source . PVLDB , 7 ( 13 ): 1565 { 1568 , 2014 .

12. J. He , E. Veltri , D. Santoro , G. Li , G. Mecca , P. Papotti , and N. Tang . Interactive and deterministic data cleaning . In SIGMOD , pages 893 { 907 , 2016 .

13. I. F. Ilyas and X. Chu . Trends in cleaning relational data: Consistency and deduplication . Foundations and Trends in Databases , 5 ( 4 ): 281 { 393 , 2015 .

14. H. Kopcke, A. Thor , and E. Rahm . Evaluation of entity resolution approaches on real-world match problems . VLDB , 3 ( 1 -2): 484 { 493 , 2010 .

15. A. Lopatenko and L. Bravo . E cient Approximation Algorithms for Repairing Inconsistent Databases . In ICDE , pages 216 { 225 , 2007 .

16. D. Loshin . Master Data Management . Knowl. Integrity, Inc., 2009 .

17. D. Santoro , P. C. Arocena , B. Glavic , G. Mecca, R. J. Miller , and P. Papotti. BART in action: Error generation and empirical evaluations of data-cleaning systems . In SIGMOD , pages 2161 { 2164 , 2016 .

18. M. Yakout , L. Berti-Equille , and A. K. Elmagarmid . Don't be SCAREd: Use SCalable Automatic REpairing with Maximal Likelihood and Bounded Changes . In SIGMOD , pages 553 { 564 , 2013 .