In this paper we discuss Falcon, an interactive, deterministic, and declarative data cleaning system. Unlike traditional rule-based system, Falcon does not rely on the existence of a set of pre-de ned data quality rules, but it encourages users to explore the data, identify possible problems, and make updates to x them. The main technical challenge consists in nding a set of rules, expressed as sql update queries, that are semantically correct and that xes the largest number of errors in the data. Falcon navigates the lattice by interacting with users to gradually checking the correctness of a set of rules. We have conducted extensive experiments using both real-world and synthetic datasets to show that Falcon can e ectively communicate with users in data repairing.
We address the problem of improving the data cleaning process by involving
non-expert users as rst-class citizens, and present Falcon [
Example 1. Table 1 reports a sample real-world dataset Tdrug for experiments collected from di erent labs. Each record represents the quantity and date of a test done in a lab over a certain molecule. Errors are highlighted. Consider the following three user updates: 1: t3rLaboratorys Ð \New York", 2: t3rQuantitys Ð 100 and 3: t2rMolecules Ð \C22H28F".
There exist multiple interpretations for each update. For instance, two possible semantics behind 1 could be either reformatting all \N.Y." to \New York" as shown in Q1, or changing all Laboratory values to \New York" as shown in Q11, regardless of their original values.
Q1: UPDATE Tdrug SET Laboratory = \New York" WHERE Laboratory = \N.Y." Q11: UPDATE Tdrug SET Laboratory = \New York";
Similarly, one possible interpretation of 2, as given in Q2, is that it is speci c for Molecule and Date. Hence, it is hard to generalize this update to apply it to other tuples.
Q2: UPDATE Tdrug SET Quantity = 100 WHERE Molecule = \C24H75S6" AND Date = \12 Nov"
Update 3 is more interesting. Consider the following three interpretations. Q3 repairs errors in both t2 and t5. Q13 also repairs both t2 and t5, but additionally, it modi es t4rMolecules to \C22H28F", which is an erroneous update, since in Boston they test a di erent statin molecule. On the other hand, the tuple-speci c query Q32 only corrects t2 but misses the chance to repair t5. Q3: UPDATE Tdrug SET Mol. = \C22H28F" WHERE Mol. = \statin" AND Lab. = \Austin"; Q13: UPDATE Tdrug SET Mol. = \C22H28F" WHERE Mol. = \statin"; Q32: UPDATE Tdrug SET Mol. = \C22H28F" WHERE Mol. = \statin" AND Lab. = \Austin" AND Date = \12 Nov" AND Qt. = 200;
One may observe that there might exist a large number of sqlu queries. Indeed, this large number is not surprising, as up to thousands of precise and reliable update queries can be needed in real-world settings. However, while an update is a perfect starting point for the process of inferring the general scripts, it comes with new challenges in terms of user interactions. The search space for a new update is exponential to the number of the attributes, and domain experts cannot manually validate each of these sqlu queries. We have to assume that a budget (e.g., #-user interactions) is given for a speci c update. This dynamic behavior, together with the large search space and a budget of user capacity, prevents the use of traditional tools for interactive response, such as precomputing and caching.
Contributions. We present Falcon [
SQL Update Queries. We adopt a simple and standard language to repair the database, the language of update statements in sql (sqlu). An sqlu statement updates records in a table T on attributes A; B : : :, when some conditions hold. We restrict the language to the case where updates are done on one attribute A of table T with only boolean conjunctions:
T SET A a
boolean conjunctions
More speci cally, each boolean conjunction is of the form B is an attribute of table T and vB is a constant value. vB, where B Search Space for One Repair. Consider a repair : trAs Ð a1 that changes the value of trAs from error a to its correct value a1 with a a1. We want to generalize this action so as to repair more errors. Naturally, there exist multiple queries to interpret . Implicitly, for each query, the SET clause is A a1. Consider a boolean condition as B vB, where B could be any attribute in relation R. We adopt a closed-world assumption by only using the evidence from tuple t, the tuple that is being repaired. As a special query, we consider H as no condition being enforced in the WHERE clause. Stating in another way, it is to update all A values in T to a1.
In summary, given a repair trAs Ð a1 for tuple t in table T of relation R, the set Q of all rules for such a repair is:
T SET A a1
X trXs where X is an arbitrary subset of R, which can range from the empty set H to all attributes in R (i.e., X R). Hence, there are 2|R| possibilities of X. Problem Statement Given a repair, one wants to nd the queries that are semantically correct so as to repair the database. An sqlu query is valid if the query is semantically correct. Since we do not know which queries are valid in advance, we need to ask the user to either validate the query as semantically correct, or invalidate it otherwise. Naturally, we want to nd all valid sqlu queries and use them to repair the database. A straightforward strategy is to ask the user to check every possible query. Of course, this method is rather expensive as there could be a large number of possible queries, for which we will use containment relationships among queries to improve the search of queries. Budget repair problem. Given a set Q of sqlu queries, a table T , and a budget B for the number of interactions the user can a ord, the budget repair problem is to select B queries Q1 from Q, so as to maximize | QPQ1^validpQq T QpT q|.
Here, validpQq is a boolean function that is T (resp. F) if Q is a valid query (resp. not), and QpT q represents the set of repairs of applying query Q over T . Observe that in the above problem, given a query Q, the validity of Q is unknown, to be veri ed by the user. Such a problem is typically categorized under the framework of online algorithms, where one can process input pieceby-piece in a serial fashion, without having the entire input available. O ine problem. Its corresponding o ine variant is the following. Given as input that whether each query Q in Q is valid or not is known, how to select B queries from Q to maximize the number of repaired tuples. It is easy to see that the o ine problem of its online version (i.e., the budget repair problem) is NP-hard. When the o ine variant is NP-hard, there is no e cient algorithm for computing an optimal solution for its online algorithm. In other words, when the o ine variant is intractable, there is no hope to nd an optimal solution with the cost in a constant factor of the online variant. However, not all is lost. As will be shown later, we can organize all queries in a graphical structure, such that when the user veri es a query Q as valid or invalid, we can even generate more inputs by computing the validity of queries Q1 that are related to Q. 3
In this section, we shall present our organization of the search space, so as to enable both e cient and e ective search over the candidate rules. Rule containment. For two rules Q and Q1, we say that Q is contained by Q1, denoted by Q ¨ Q1, if for all possible database instances T over the input schema R, the result of QpT q is a subset of the result of Q1pT q. Intuitively, the rule containment captures the semantic relationship among rules. In other words, no matter which database T is used, Q will update a subset of T tuples that Q1 will update if Q ¨ Q1, since Q is more speci c than Q1. It is readily to verify that the query containment \¨" is a partial order over the set Q of all possible rules, which is re exive, antisymmetric, and transitive. For a query Q, we denote by attrpQq the set of distinct attributes in its WHERE condition. Note that for each user update, the sqlu queries have the same value constraint on the same attribute, and thus the rule containment veri cation is equivalent to a simpler condition: Q ¨ Q1 if attrpQ1q is a subset attrpQq.
A ected tuples. For each query Q and instance T , we call the tuples in QpT q a ected tuples, i.e., the tuples that Q will repair. We also call |QpT q| the a ected number of Q, relative to T . Consider Q3 and Tdrug in Example 1 for instance. The a ected tuples are Q3pTdrugq tt2; t5u, and its corresponding a ected number is |Q3pTdrugq| 2. Hence, Q is a poset on the partial order ¨ of rule containment. Moreover, consider any two rules Q and Q1. They have a greatest lower bound: the most speci c query that is contained by both Q and Q1. This query, denoted by Q ^ Q1, is the one w.r.t. attrpQq Y attrpQ1q. Also, they have a least upper bound: the most general query that contains both Q and Q1. This query, denoted by Q _ Q1, is the one w.r.t. attrpQq X attrpQ1q. Therefore, we can organize the queries in our search space as a lattice.
Query lattice. Given a repair and a database instance T , we denote by pQ; ¨q the corresponding lattice. Each node in the lattice corresponds to a query Q P Q. Each directed edge from node Q to Q1 indicates that Q ¨ Q1 (Q is contained in Q1) and |attrpQq| |attrpQ1q| 1 (with one di erent attribute). Moreover, the a ected number associated with each query is maintained in the lattice. Valid and maximal valid nodes. Given a lattice pQ; ¨q, the node relative to a rule Q is valid if it is semantically correct, thus should be executed to repair data. In our work, if the validity of a rule is unknown, we rely on the user to verify. Fortunately, if a rule Q is known to be valid, we can infer that Q1 is also valid if Q1 ¨ Q. Moreover, the node relative to a valid rule Q is maximal valid, if no Q2 is valid and Q ¨ Q2. One nice property of using a lattice is that it provides opportunities to prune nodes to be visited during traversal. Lattice pruning. If a node Q is valid, by inference, all nodes Q1 where Q1 ¨ Q are valid. On the other hand, if a node Q is invalid, by inference, all nodes Q2 where Q ¨ Q2 are invalid. The rationale behind the above inferences is that: if one query is valid, then any query that is more speci c is also valid; conversely, if it is invalid, then any query that is more general is also invalid. We denote by Q/ (i.e., above Q in the lattice) the queries that Q contains, and Q' (i.e., below Q in the lattice) the queries that contain Q. These notations naturally extend to a set of queries, Q/ and Q', such that Q/ QPQ Q/ and Q' QPQ Q'. 4
First of all, we notice that traditional traversal algorithms cannot be used to
e ciently navigate the lattice L [
Datasets. We used four real-world datasets and one synthetic dataset: Soccer,
Hospital, BUS, DBLP and Synth. More details are available in the full paper [
DFS
BFS
Ducc
Dive
CoDive
CoDive Refine -1,0
Rule Learn.
GDR
Active Learn.
Soccer Hospital Synth 10k Synth 1M DBLP BUS -1,5 Soccer Hospital Synth 10k Synth 1M DBLP BUS (a) Bene t for the various algorithms.
(b) Bene t compared with the baselines.
4)Active Learning in Lattice Traversal: We compared our methods to an active
learning variant of our lattice-based approach designed ad-hoc for this purpose.
Errors and Metrics. Since the considered datasets are clean, we introduce
noise to verify the algorithms behaviour in the cleaning process. To start, we
manually de ned a set of CFDs [
Exp-1: Lattice search algorithms. Figure 1(a) reports the bene t of each algorithm for the six datasets with a xed budget B 2. The proposed algorithms, Dive and CoDive, consistently report a positive gain, which, for CoDive, can be interpreted as a reduction of the total user interaction cost between 22% (Soccer) and 97% (BUS). The plot also reveals that one-hop algorithms fail for the budget exploration of the lattice, with the notable exception of the Hospital dataset. This results is not surprising if we look more closely at this scenario. Hospital schema has a large number of FDs with always one or two attributes in the left hand side (LHS) of the rules. This is re ected in the CFDs that we used to introduce the errors. Rules with one or two LHS attributes are at the bottom of the lattice, and this is the most favourable setting for one-hop based algorithms, since they all start from the bottom. On the other hand, when rules start to have more attributes in the LHS, more nodes must be checked to take a decision, these algorithms fail and Dive and CoDive greatly outperform them. Exp-2: Comparison to the baselines. Figure 1(b) reports a comparison of our CoDive algorithm to the four baselines discussed above. We xed a timeout of two hours for all tests. Notice that not all algorithm terminated within the timeout. This accounts for the missing bars in the chart. Our approach significantly outperforms all baselines. CoDive results are signi cantly better than those based on rule discovery. This suggests that our novel paradigm for data repairing is an improvement w.r.t. previous approaches in which quality rules are established upfront. Interestingly, this is con rmed also in the case in which rule discovery is coupled with an interactive algorithm, like GDR. In fact, the additional number of user interactions needed to run GDR brings to even lower bene t. CoDive algorithm outperforms its active learning variant. Since ActiveLearning shares the same infrastructure as CoDive, here results are better w.r.t. RuleLearning and GDR. In fact, as for CoDive, whenever it terminated also ActiveLearning was able to repair all errors. CoDive outperforms Re ne because of the less expressive language in the latter. Results con rm our intuition that using user updates to lead the discovery of rules in an incremental way yields more complete and e ective repairs than state-of-the-art rule-learning algorithms.