{'fraction_non_alphanumeric': 0.033413839191502336, 'fraction_numerical': 0.008769667268506576, 'mean_word_length': 4.653234358430541, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Truth Discovery on Inconsistent Relational Data

: In this era of big data, data are often collected from multiple sources that have different reliabilities, and there is inevitable conﬂict with respect to the various information obtained when it relates to the the same object. One important task is to identify the most trustworthy value out of all the conﬂicting claims, and this is known as truth discovery. Existing truth discovery methods simultaneously identify the most trustworthy information and source reliability degrees and are based on the idea that more reliable sources often provide more trustworthy information, and vice versa. However, there are often semantic constrains deﬁned upon relational database, which can be violated by a single data source. To remove violations, an important task is to repair data to satisfy the constrains, and this is known as data cleaning. The two problems above may coexist, but considering them together can provide some beneﬁts, and to the authors knowledge, this has not yet been the focus of any research. In this paper, therefore, a schema-decomposing based method is proposed to simultaneously discover the truth and to clean the data, with the aim of improving accuracy. Experimental results using real world data sets of notebooks and mobile phones, as well as simulated data sets, demonstrate the effectiveness and efﬁciency of our proposed method.


Introduction
Big data provide abundant valuable information but a number of inherent challenges, one of the most serious of these is dealing with the poor quality of data that are often dirty and inconsistent [1] . Even for domains such as flight and stock, which people consider to be highly reliable, a large amount of inconsistency has been observed in data collected from multiple sources [2] . One example is the incorrect news that United Airlines was filing for a second bankruptcy, which sent shares tumbling before the error could be corrected [3] . Decisions based on inconsistent data often result in serious consequences: incorrect flight information may cause passengers to miss flights; errors in stock data may cause financial losses for shareholders; and wrong diagnoses based on incorrect medical measurements are life threatening. Inconsistencies are typically identified as being violations of data dependencies, such as functional dependencies and conditional functional dependencies. In this respect, two main research areas are committed to solving inconsistency problems, truth discovery, and data cleaning, and the following sections provide a detailed presentation of these areas.

Truth discovery
It is important that big data are obtained from multiple sources, but due to low reliability of the sources, it is inevitable that inconsistent values will occur for the same object. This kind of inconsistency violates the primary key constraint (a special case of Functional Dependencies, FDs).
For many years, the truth discovery community has been researching how to obtain the most trustworthy information [4][5][6][7][8][9][10][11][12][13][14] . One common framework used is to estimate the reliability degrees of the sources and determine the most trustworthy claims alternately and iteratively. This means that to determine truths based on the reliability degrees estimated, greater confidence is given to higher degree sources, and based on the truths estimated, sources providing a larger number of correct values are believed to be more reliable. The process is repeated iteratively, until a stopping criterion is met (for example, the maximum number of iterations or no further changes). The intuition behind this framework is that sources that are more reliable often provide more information that is more trustworthy, and that when a source provides consistently trustworthy information it is considered to be more reliable. Within this framework, various studies have adopted different calculation details or have focused on more specified conditions, such as the relationship between sources, relationship between objects, multiple true values, heterogeneous data, and long-tail phenomena.

Data cleaning
To automatically improve data quality, it is necessary to define data quality rules that determine how to detect and repair errors, and the use of data dependencies (integrity constraints) is the natural choice in this respect [1] . Classical FDs [15] were the first class of dependencies to be introduced, and these are almost as old as the relational database model. However, for data errors to be captured more proficiently, Conditional Functional Dependencies (CFDs) were proposed [16] as an extension of classical FDs, and these incorporate patterns of semantically related data values. Dependencies may be violated when data contain errors, and detecting the errors is tractable [17,18] .
A common heuristic way of removing errors once they have been detected is to instigate a repair involving the use of a modified database, which satisfies the dependencies and uses the least number of updates with respect to the original dirty one. This type of problem is known as the "data cleaning problem". It is intractable, and several methods have been proposed aimed at determining a near optimum repair [19][20][21][22] or a set of repair samples [23,24] . In addition to FDs and CFDs, several other extensions have been proposed, such as extended conditional functional dependencies [25] and conditional dependencies with built-in predicates [26] , and new types of rules have been proposed, such as editing rules [27] , fixing rules [28] , differential dependencies [29] , and comparable dependencies [30] . However, as FDs and CFDs are the most common data quality rules, and they have attracted the most research attention, only these two types of rules are considered in this paper; and the others will be considered in future work.

Problems inherent in previous methods
Truth discovery and data cleaning research groups have provided considerable and valuable research results. However there are several drawbacks remaining that require exploration, and those that are related to this study are presented as follows: • In most truth discovery methods, all sources start with uniform weights prior to the iteration process. A considerable decrease in performance can result when most sources are unreliable, and therefore, it is extremely important to improve the initialization of source reliability [31] .
• In truth discovery, it is common that only a few sources claim for an object, and the discovered values thus have low confidences.
• When dependencies are available, the output of truth discovery methods may still violate the dependencies. A straightforward solution would be to clean the result by these dependencies; however, this may replace some correct answers with incorrect ones.
• The tie phenomenon and cost based data cleaning methods are heuristic and may result in more than one optimum repairs, which means the same number of updates are required in the repairs. This then requires user feedback to determine which one is right, and such an operation involves a nonautomatic cleaning process.
• The errors contained in data do not always violate the dependencies; therefore, the data cleaning methods cannot even detect these errors, let alone fix them. The authors have observed two problems coexisting in many real-world applications. For example, on an online shopping web site, several sellers may provide conflicting information about the same product, and information from one single seller may violate some dependencies. In another example, systems are developed to extract product specifications on the web (e.g., Ref. [32]), and a product often contains many attributes and dependency relationships between the attributes.
In addition, specifications are collected from a large number of web sites that can be considered as data sources, and which have different reliability degrees.
Both truth discovery and data cleaning methods were studied to improve data quality, and when considered together, these methods can complement each other. For example, a source that provides data that are determined to be extremely inconsistent is therefore less reliable and should be initialized with low weight. When the score of a candidate value in truth discovery is associated with the cost in data cleaning, the cost of the data type changes from an integer to a real value, which can eliminate the tie phenomenon. To the author's knowledge, no previous studies have yet taken advantage of using these benefits from both methods.

Proposed SDTD method
To resolve these problems and exploit the benefits of using both methods, a Schema-Decomposing based Truth Discovery (SDTD) framework is considered, which directly provides results satisfying the dependencies. The initial pre-processing step decomposes claim-tuples into a set of source-key-value triples, which is the input of the truth discovery framework and uses certain decomposing rules related to the dependencies. Each source is initialized with a weight depending on the inconsistent values it provides. The truth discovery iterating process is almost analogous to that used in previous work; however, in this paper dependencies are considered when calculating value scores. After iterations are finished, a post-processing step joins the key-value pairs back into relational tuples, which satisfies the dependencies directly. Another benefit of schema-decomposing is that the claim numbers of some of the objects are greatly increased, and the results determined are more confidential. In summary, this paper makes the the following contributions: • An SDTD framework is proposed, which seamlessly combines the disciplines of truth discovery and data cleaning. Several benefits can be obtained when using this framework.
• An adequate set of decomposing rules are introduced. According to the rules, all (conditional) FDs are considered, and each claim-tuple can be decomposed into source-key-value triples.
• Dependencies are considered when calculating the scores of candidate values, and more accurate values can be determined.
• In this study, experiments are conducted using two real world data sets and synthetic data sets. The results demonstrate the effectiveness and efficiency of the proposed method. The remainder of this paper is set out as follows: related research is summarized in Section 2; Section 3 provides a running example to demonstrate our motivation behind this study; Section 4 formulates the problem, the proposed method is derived and analyzed; in Section 5, various experiments are conducted on real world data sets and synthetic data sets to validate the effectiveness and efficiency of the proposed method; and Section 6 presents the conclusions. Bohannon et al. [19] modeled the cleaning problem based on cost and provided an effective heuristic algorithm using value modification, and Wijsen [21] proposed a theoretical framework that considers update-based repairing, in which the problem of constructing nucleus (a single database that yields consistent answers to a class of queries without the need for query rewriting) has been studied. More recently, research groups have focused on user participation. For example, Yakout et al.
developed a data cleaning system GDR that allows user's guidance [33] , and studied the problem of guided data repair [34] where updates are completed in a group-manner.
Xie et al. [35] presented a data cleaning framework that combines data quality rules (CFDS, CINDS, and MDs) with user feedback through an interactive process. Recently, an interactive, deterministic, and declarative data cleaning system, Falcon, was presented [36] , which encourages users to explore data, identify possible problems, and develop updates to fix them. Falcon focuses on addressing the challenge of finding a set of SQL update queries that is minimal in size, and it also fixes a large number of errors. Cai et al. [37] proposed a collective inference model of sanitizing data, to prevent social network users from attacks. They also constructed a data-sanitization strategy that can optimize the tradeoff between data utility and privacy in Ref. [38].
Miao et al. [39,40] studied the insertion propagation problem with functional dependency, plenty of analysis is provided and complexities results are obtained. In Ref. [41], an iterated local least squares imputation method is proposed to estimate the missing values in microarray gene expression data. There are also studies concerning the currency problem of dynamic data, such as Ref. [42].
Other data cleaning research is not covered here due to space limitation, but comprehensive and systematical summaries can be found in the latest survey [43] .

Truth discovery
When the concept of truth discover was first proposed [4] , the aim was to determine the truth with respect to conflicting web information. Galland et al. [6] explored techniques based on corroboration and introduced three fix point algorithms corresponding to the different levels of complexity in an underlying probabilistic model. Pasternack and Roth [7] proposed a method, in which prior knowledge was translated into propositional constraints that are integrated into each round of the truth discovery process; however, the use of linear programming to solve the problem is very time consuming. A similar study [44] introduced a new, generalized, fact-finding framework that can incorporate additional information, such as uncertainty, when extracting information that is claimed in documents, such as the attributes of the sources, the degrees of similarity among claims, and the degrees of certainty expressed by sources in the truth discovery process. Furthermore, objects have been clustered together [45] , and the truth discovery task is analyzed in a clustering manner. Another study [46] presented, for the first time, a Bayesian interpretation of the basic mechanism used in truth discovery with information networks, and a maximum likelihood estimation approach for truth discovery in social sensing has been proposed [11] . Observations provided by humans can be modeled as binary variables, and the truth discovery task is formulated as a maximum likelihood estimation problem, and solved by an EM algorithm. Truth discovery has been used [13] to resolve conflicts in heterogeneous data (objects with heterogeneous attributes), by truth discovery. And a confidence-aware approach for truth discovery has been proposed [14] , in which accuracy was improved by reducing the influence of low confidence sources (where lowconfidence means that the sources provide very few claims). Furthermore, situations that have been studied in which more than one value can be true for one object, for example, the authors of a book and the actors in the movie of the book [9,47] .
Other studies (e.g., Refs. [5,48,49]) have also focused on the relationship between sources, for example, where one source copies information from another source, and research has also been aimed at selecting with high-quality sources to reduce costs and improve the accuracy of truth discovery methods [50,51] .
Other groups have been committed to determining truths using probabilistic graphical model-based methods. For example, a Bayesian probabilistic approach, GTM, has been proposed that was designed for continuous data type [10] . The same research group also proposed LTM [9] at almost the same time, which is a probabilistic graphical model considering two types of errors under scenarios of multiple truths: false positives and false negatives. A further study used a probabilistic model of Ref. [12], where the source reliability had different semantic meanings in different settings: it could indicate the probability of a source asserting the truth, or the probability of a source both knowing and telling the truth, or even the probability of a source intending to tell the truth.
The latest survey [31] provides more comprehensive introduction to truth discovery.

A Motivating Running Example
On a shopping web site, many sellers (data sources) advertise a supply of the same product (an object). Usually, sellers also provide specifications about their goods, which include several to tens of attributes. There are often dependencies between these attributes, and careless sellers may provide wrong information which may violate these dependencies. This situation relates to traditional truth discovery. However, there are dependencies defined on the attributes which can be violated, making it also a data cleaning problem.
For example, on a real-world online shopping web site, two sellers (or sources), s 1 and s 2 , provide information about three phone models: (Huawei) Honor7, (Huawei) Mates, and (Sony) Z3. For simplicity, three representative attributes are considered, i.e., Central Processing Unit model (CPU for short), number of cores (#Core), and frequency. In addition to the key dependencies (the phone models are the key), there are two other FDs between these attributes: • φ 1 ≡ CP U → #Core indicates that phones with the same CPU model must contain the same number of cores.
• φ 2 ≡ CP U → F requency indicates that phones with the same CPU model must also have an equal frequency. Claims and ground truths are listed in Tables 1 and 2, respectively (where Snapdragon is abbreviated to Dragon to save space), and wrongly claimed values are underlined.
In a traditional truth discovery framework, s 1 and s 2 are initialized with uniform weights. With a probability of 0.5, or even higher in some methods because s 1 provides more claims than s 2 , the wrong value 4 will win out as Honor7's core number, which is undesirable. Meanwhile, only s 1 claims on Mates, which will result in a low confidence, especially when the only claiming source is of low reliability. Possible results of the truth discovery · · · · · · · · · · · · · · · · · · · · · · · · · · · methods are shown in Table 3, where the first two tuples violate φ 1 . To resolve this inconsistency, one can either change 4 in the first tuple into 8, or change 8 in the second tuple into 4, which introduces a tie and may return a wrong answer. Furthermore, the tuple for Z3 contains two wrong values and does not violate the dependencies. Therefore, the wrong values will not be detected, even though s 2 does claim correct values on Z3. This example illustrates the problems faced when resolving data inconsistency and will be employed as a running example in the following sections to illustrate the method proposed in this paper.

Preliminaries and problem definitions
Several important terms are introduced in this section, and the truth discovery problem in relational data is then defined.
Definition 1 Let O be a set of objects, where each object is a thing or a type of things. A is a set of concerned attributes of the objects. An entry is an object-attribute pair, and each entry should be identified by an identifier (key or eid) and should be assigned with a value as the truth. Values about the same object can be seen as a relational tuple.
In Table 2 for example, Honor7, Mates, and Z3 are objects (phone models), and CPU, #Core, and Frequency · · · · · · · · · · · · are attributes. The entry corresponding to Mates and CPU, which can be denoted as Mates [CPU] or Mates.CPU, is assigned with a value Kirin935 as the truth, meaning that Mates is equipped with the CPU Kirin935. There are 3 corresponding tuples describing the objects. Definition 2 Let S be a set of sources (i.e., a set of data providers) and C a set of claims, each of which is triple ⟨s, k, v⟩, meaning that the source, s, claims a value, v, on entry with key, k. Sources often provide claims in the form of tuples, and tuples from all sources are organized as a claim table, CT . Different sources have differing degrees of reliability, which are reflected in the differing sources.
For example, in Table 1 there are two sources, s 1 and s 2 , providing five claim-tuples for the three objects. Note that sources can conflict with each other, for instance, s 1 and s 2 claim that the frequencies of Z3 are 2.7 GHz and 2.5 GHz, respectively. However, only one of the conflicting values actually agrees with the ground truth.
Definition 3 (Refer to Ref. [15] where A i ∈ A and B ∈ A. The brackets can be omitted when there is only one attribute on the left (resp. right).
The semantic of φ is that for any two tuples, t 1 and t 2 , one of the following conditions should be satisfied, The instinctive understanding is that if any two tuples are equal on the left-hand side attribute of φ, they should also be equal on the right-hand side attribute. In this paper, for any tuple, t ∈ CT , we say that entry t [B] is covered by φ if t[A i ] ̸ = null for i = 1, 2, · · · , l. In the running example, there are two FDs CP U → #Core, CP U → F requency. In Table 1, all entries relating to the attributes #Core and F requency are covered because there are no null values. The first two tuples together violate CP U → #Core, because they are equal for CP U but differ with respect to the number of cores.
Definition 4 (Refer to Ref. [16]) A CF D ϕ is of the form where each of A i , B ∈ A, and v i is either a constant value or an unnamed variable ' '. The semantic of ϕ is that for any two tuples, t 1 and t 2 , one of the following conditions should be satisfied, does not hold, t 1 and t 2 are not equal for The instinctive understanding is that if any two tuples are conditionally equal on the left-hand side attribute of ϕ, they should also be equal on the right-hand side attribute, and they should have corresponding values. For any tuple, t, that matches the left-hand side of ϕ, in this paper we say that entry t[A] is covered by ϕ.
The truth discovery task relating to inconsistent relational data is then formally defined.
Definition 5 Given claim table, CT , about attributes in mathcalA for objects in O provided by sources in S, along with a set Σ of FDs and CFDs, the goal is to determine the most trustworthy values for each object, o, while satisfying all the dependencies in Σ .

Schema-Decomposing based Truth Discovery (SDTD) framework
The straightforward method for determining truths relating to each entry, and for cleaning the results according to Σ , has been shown in the previous problems. In this paper, an SDTD framework is considered, where the problem becomes a classical truth discovery problem (except that the initial weights and truth values require more elaborate calculations). This method requires an initial pre-processing step. Each claim-tuple is decomposed into several source-keyvalue triples, using certain decomposing rules with respect to the dependencies. The aim of this is to consider the left-hand values with respect to a dependency of a virtual object and the right-hand value as the claimed value. After decomposition, a set of source-key-value triples is obtained, on which a truth discovery algorithm is conducted. In the claims obtained, it is possible for one source to claim different values for the same (virtual) object; therefore, the initial source weights and truth values in each iteration need to be carefully determined to provide highly accurate results. After conducting the truth discovery process, a post-processing step joins the keyvalue pairs into relational tuples, which directly satisfies the dependencies in most real-world situations.
We now discuss several key points within the SDTD framework in detail.

Decomposing rules
The functional dependency φ ≡ X → A means that tuples with the same values for X should be equal for A, where X is a set of attributes. This semantic happens to coincide with truth discovery settings, where the same object should hold the same value. In this respect, we consider extracting source-key-value triples from the claim-tuples according to the FDs using Rule 1: • Rule 1. For each functional dependency, φ, decompose CT to obtain a new table, T φ , using the projection operation, as where X is the set of attributes on the left-hand side of φ, and for A on the right-hand side.
, all tuples that match the embedded constant values should hold the same value for B whenever they are equal on the left-hand side attributes. Similar to Rule 1, source-key-value triples from the matched tuples according to the CFDs are extracted using Rule 2.
• Rule 2. For each conditional functional dependency decompose CT to obtain a new table, T ϕ , using the selection and projection operations, where B c1 , · · · , B cn are attributes embedded with constant values, v c1 , · · · , v cn , respectively. In addition, if ϕ in Rule 2 is embedded with a constant value for the right-hand side attribute, A, it is claimed to be a correct key-value pair. Rule 3 is employed to represent the same semantic as follows: where v 0 is a constant value, construct a single tuple, t ϕ , as shown in Table 4, and insert it into T ϕ , where B c1 , · · · , B cm are attributes in ϕ bound with constant values v c1 , · · · , v cm , and ssid is a virtual super source, which always provides true Table 4 Single tuple constructed from ϕ.
values. As some entries may not be covered by any dependency, Rule 4 is introduced to deal with these as follows: •  Table 5 to Table 8).
All tuples in these tables can be seen as ⟨sid, key, value⟩ triples: the sids can be obtained directly;    the value corresponds to the last attribute, which is usually the right-hand side attribute; and all the other attributes are combined as keys. To identify which attributes do the values that constitute the key come from, it is necessary to consider the attribute names as part of the key. For example, the key corresponding to the first tuple in Table 6 would be "CPU.Kirin935; Frequency.2.2GHz".

Determining source weights
The basic idea with all truth discovery methods is that sources have different reliability levels, and that higher weights should be assigned to sources that are more reliable. In this paper, the probability of a source, s, of giving correct values is estimated as its weight. At the beginning of the iterations, almost all the existing truth discovery methods start with uniform source weights. In our setting, a single source may provide self-conflicting data, which indicates the source has low reliability. With the self-conflictions, source weights can be initialized more elaborately.
For example in Table 5, s 1 claims two different values, 4 and 8, for the core number of Kirin935, and no more than one of these can be correct. The upper bound of number correct claims provided by source s over key k is where N s,k,v is the number of claims provided by s for k with a value v. Equation (1) means that if the super source claims that v is the absolute true value of k, the upper bound represents the number of correct claims. However, if the super source provides no truth value for k, the selfconflicting value that has the most votes is assumed to be true. The initial weight of source s can be estimated according to the upper bounds as The denominator is the total claims provided by s and the numerator is the maximum possible number of correct ones. Obviously, all weights are in [0, 1], and sources providing less-conflicting values gain higher upper bounds, as well as higher weights. In particular, if a source provides no self-conflictions and always agrees with the super source, it will be initialized with the highest weight, 1.0. The situation improves during iterations because estimated truths become available. If the estimated value of the key, k, in the i-th iteration is denoted by v (i) k , the source weights in the i-th iteration can be then naturally estimated by i.e., the probability of source s providing correct claims.

Determining truths
With the source weights (or probabilities of providing correct values) previously estimated, a probabilistic model is analyzed to determine the truths. By providing the claim table, CT , the true values can be estimated according to conditional probabilities. For a single claim ⟨s, k, v⟩ in CT , the probability of v being correct, denoted as P k,v , can be directly assigned with the probability of s providing correct values, i.e., w s . However, in our settings, it is possible to have multiple conflicting claims from the same source over the same key, and if a claim is involved in a conflict, its probability of being correct should be reduced. If source, s, provides N s,k claims over key k, among which N s,k,v claims are with value v, k is composed of m attributes, as shown in Table 9. In the condition where s provides a correct value, the probability of the claim ⟨s, k, v⟩ being correct is naturally estimated by voting, i.e., P {⟨s, k, v⟩ is correct|s gives a true value on k} = N s,k,v /N s,k (4) under the intuition that the value that has more votes is more likely to be correct. In the condition that the claims giving v are incorrect, it is possible for v or a 1 , · · · , a m to be wrong. It is assumed that all the m+1 values have an equal probability of being incorrect, therefore, it can be inferred approximately that With Eq. (4) and Eq. (5), when values claimed by s Table 9 Claims provided by s over k.
Claim id Sid Key Value over k conflict with each other, the probability of each value involved being correct should be multiplied by a discount factor, where m is the number of attributes in key k. Note that the discount factor depends on the claim table, CT , and the set Σ of dependencies only, which means it is sufficient to calculate it just once before the iterations. The discount factor is of the largest value, 1, when s provides no conflicting values for key, k. However, if there are conflicting values, the discount factor is strictly less than 1.
It is worth noting that when the super-source claims a value on k, the discount factor can be calculated more accurately (however, the derivation is similar and is omitted here).
When an entry, e, is involved in more than one conflict, its probability of being correct should be discounted multiple times as where k is the key identifying e. Equation (7) estimates the probability of v being correct in the (i + 1)-th iteration.
Consider key, k, and candidate values v 1 , v 2 , · · · , v c , if it is assumed that there is no relationship between sources as where v * k denotes the true value of key k, and the conditional probability is abbreviated as P {CT |v * k = v} for convenience. According to Bayesian formula, the posteriori probabilities can be derived as We assume that no previous knowledge is available, and priori probability equals for all candidate values, therefore, The value with the highest posterior probability is thus selected as the truth, or equally

Composition process
When truth discovery iterations are terminated, a relational table, T c , is constructed from all truth pairs of the form ⟨k, v⟩.
The value for each tuple on attribute A can be filled using the estimated set T * of truths, along with the corresponding object, o. In the decomposing process, every entry value is guaranteed to be covered by a rule. If it is covered by Rule 4, then the entry value can be directly set as the discovered v * k where k = o.A, and if it is covered by Rules 1−3, then all corresponding lefthand values should be filled in advance. The composition process is illustrated as the Fill procedure, as shown in Algorithm 1.
In our settings, it is assumed that each attribute is in the right-hand side of one dependency at most, and that there are no cycles in the depending relationships that can be satisfied in most real-world situations. When these assumptions hold, each entry's value can be determined by exactly one key, and no conflicts occur in the composition process. Other general cases will be considered in future work.

Algorithm flow
Several key points have already been described. This subsection summarizes the overall flow for the proposed SDTD method, shown in Algorithm 2, and this comprises the following three main steps, Step 1: Preprocess. SDTD first computes discount factors for entries according to Eq. (6) (line 1) and then Algorithm 1 F ill(Tc, o, A, Σ , T is already filled then 2: return 3: if There is a dependency X → A ∈ Σ then 4: for Each attribute B ∈ X do 5: F ill (Tc, o, B, Σ , T * ) 6: Compose key k by values on X and A 7: else 8: Compose key k by o and the attribute A 9: Fill o[A] in Tc with value v * k , which can be found in T * 10: return decomposes relational tuples into triple-formed claims according to the four decomposing rules (lines 2−11).
The true values are then iteratively estimated and source weights are updated until a stopping criterion is met (lines 13−19). Step

Practical issues
Several practical issues should be considered in the SDTD framework.
Null values are very common in the database community due to incompleteness. In the decomposing process, if a null value occurs in the right-hand side of a for Each tuple t ∈ T C do 4: Generate claim c according to Rule 1 or Rule 2 respectively with ϕ on t 5: Add c into claim set C 6: if ϕ is a constant CFD then 7: Generate claim c according to Rule 3 with ϕ on t 8: Add c into claim set C 9: for Each uncovered entry do 10: Create claim c according to Rule 4 on t 11: Add c into claim set C 12: Initialize source weights according to Eq. (1) and Eq. (2) 13: repeat 14: for Each claim ⟨s, k, v⟩ ∈ C do 15: Compute its relative probability of being true according to Eq. dependency, then the generated triple should be discarded because it provides no valuable information. If a null value occurs in the left-hand side of a dependency, the generated triple should also be discarded, because it creates an uncertain key-value that causes problems in the iterating process. In the second case, the right-hand side value becomes uncovered and should be dealt with using Rule 4, which then ensures complete answers in the final result.
Only categorial attributes have been discussed in this paper; however, numeric values can be easily integrated into our framework. A numeric valued attribute seldom occurs in the left-hand side of a dependency, (if it does, it can be treated as a categorial attribute). In the truth discover iterations, the source weights can be calculated more carefully if numeric values are available, and true numeric values can be computed as weighted averages among multiple sources.
In Eq. (12), it is very possible that P (i) s,k,v equals 0 or 1, and that it causes invalid numbers. To solve this problem, a bounded interval is imposed on the probability, and where ϵ is a positive value close to zero, which is set as 0.01 in our experiments. Finally, when calculating the discount factors and estimating the values, if the super source claims a value on the key, the calculations should be adjusted accordingly; as this is intuitive, formal discussions are omitted here.

Experiment
This section analyzes the performance of our method using two real world data sets and synthetical data sets. The results show that when data cleaning and truth discovery tasks are simultaneously considered, a superb data quality can be obtained when dealing with relational data, which violates dependencies provided by multiple sources.

Experiment setup
All experiments were conducted using JAVA and performed on a Dell desktop with an Octa-Core Intel i7 3.60 GHz CPU, 8 GB of memory, a 1 TB SATA disk, and with Windows 7 as the underlying operating system.

Data sets
Experiments were conducted on both real-world data and synthetic data.
The real-world data set contains two subsets: Notebooks and Phones, which are obtained from one of the most popular shopping web sites. Many shops (sources) sell various products (objects) and list their corresponding specifications (attributes) to customers. The statistical information of the two subsets is listed in Table 10. For simplicity, only several attributes are provided for the two data sets. The Notebooks data set contains three attributes: scr res (screen resolution), scr rate (aspect ratio), and scr type (screen type: wide or standard), and there are two dependencies between the attributes: scr res → scr rate and scr rate → scr type. Meta data of the Phone data set can be found in Section 3. To ensure correctness, all ground truths were collected manually from corresponding official web sites; however, although we made our best efforts to collect ground truths that were as complete as possible, only a small portion of these were available, as shown in Table 10. However, the data provided are suitable for use in an accuracy evaluation.
In the synthetic data sets, 500 sources provided claims on 10 000 (or ranging from 10 000 to 100 000 in the scalability test) objects. For each object, o, five sources (on average) were randomly selected to claim on o; therefore, there were a total of approximately 50 000 claim-tuples (ranging from 50 000 to 500 000). The claiming inaccuracy (or error rate) of each source was a random value of a wellknown distribution, Beta(α, β), because it is the most common that is continuous and defined with an interval [0, 1]. By varying α and β, expectation of the source inaccuracy ranges from 1% to 10%.

Baseline methods
The proposed method is compared with two latest algorithms, CRH [13] and CATD [14] , as well as the simple VOTE, where the value with the highest number of votes is regarded as the truth. Because these three methods only enabled truth discovery, a cleaning process [19] was appended to them, and three new methods, CRH+Clean, CATD+Clean, and VOTE+Clean, were obtained.
For all iteration-based methods, a global threshold (defaulted 3) of the number of iterations was used for consideration of fairness.

Assumptions validation
In this subsection, several assumptions that inspired our study are validated on two real world data sets.

Self-conflictions of sources
In our settings, an important assumption is that tuples from a single data source may violate some dependencies; this is validated in Fig. 1. Each data source is represented by a point, where the x-coordinate is the number of claims provided, and the y-coordinate is the number of conflicting values among the claims. Both of the real world data sets contained self-conflictions, and a source was more likely to contain self-conflictions when it provided more claims. Therefore, by obtaining the self-conflicting information, initial weights of the sources could be assigned more wisely.

Tie phenomenon
The number of ties is significant with respect to the uniform source-weight initialization, because the first iteration is a simple voting process. Ties play a very unstable role in truth discovery because more than one value has an equal probability of being selected as the true value. In Fig. 2, the tie phenomenon is illustrated  more intuitively. Each point stands for an entry, where the x-coordinate is the number of candidate values of the entry, and the y-coordinate is the number of ties. The tie phenomenon is obvious, particularly in the Phones data set.

Claim numbers before and after decomposition
This study has discussed that when very few sources provide claims on an entry, the discovered truth has a low confidence. Our schema-decomposing based framework can solve this problem to some extent. The number of claims made for each entry before and after decomposition can be counted, and Fig. 3 shows the distribution of the number of claims. It can also be seen that most entries are claimed by very few sources. By decomposition, our method decreases the number of entries that provide few claims by about 75%, and some entries with a larger number of claims are created (note that this is plotted using logarithmic coordinates).

Results
This subsection presents experimental results relating to effectiveness and efficiency.

Accuracy
The accuracy of all methods used with real world data sets is listed in Table 11. Results show that methods that did not employ a cleaning process performed badly, particularly on Notebooks, whereas the cleaning process significantly improved the accuracy to a certain extent. Of all the methods evaluated, SDTD performs the best with both Notebooks and Phone data sets. Accuracy was evaluated for synthetic data sets, using different expectations of source-inaccuracy. To obtain results with a higher confidence, each test was conducted on synthetic data sets for 10 times, and the average value was used as the final result. From Fig. 4, it is evident that the SDTD performs well, even when the sources have  different degrees of reliability.

Convergence rates
One of the important features of a good truth discovery method is its convergence rate, and this was evaluated here using real world data sets. Table 12 lists the relative changes of the different methods in each iteration, and it can be seen that CATD and SDTD converge fast while CRH keeps changing (because it gives two different sets of results in turn).

Scalability
Section 4.2 shows that the running-time of the proposed SDTD framework is linear with respect to the number of Table 12 Relative changes in each iteration. claim tuples. Its scalability is validated by varying the number of objects (doing so caused a linear increase in the number of claims). The average running times are shown to be scattered in Fig. 5, which reflects 10 running times for each scale with the synthetic data sets. From this, it is obvious that the data provide a good fit with linear regression (the red line), with a Pearson Correlation of 0.9894.

Conclusion
This paper studies the truth discovery problem with relational data and (conditional) FDs. There are several problems inherent in the use of both truth discovery and data cleaning, and a framework is established that considers both methods. A schema-decomposing based method is then proposed that discovers true values among sources with different reliability degrees, and the output truths directly satisfy the given dependencies. Experiments using both real and synthetic data sets validate the effectiveness and efficiency of the proposed method.
In future work, more sophisticated situations will be considered to include, but will not be limited to, the use of a greater number of general dependency cases (in this paper, no cycle between dependencies is assumed, and every attribute is covered by no more than one dependency). In addition, differential dependencies will be considered, as will the use of more data quality constraining types, such as editing rules and fixing rules.