Article Preview
TopIntroduction
In real-life applications, constraints on ER ubiquitously exist. Such constraints can be obtained from a variety of sources: background knowledge (Schewe & Wang, 2013), external data sources (Wang, Wang, Li, & Gao, 2013), domain experts, etc. Some constraints may be captured at the instance level (Tung, Han, Lakshmanan, & Ng, 2001; Wagstaf & Cardie, 2000), e.g., “PVLDB” refers to “VLDB Endowment” and vice versa. Some constraints can be specified at the schema level (Arasu, Re, & Suciu, 2009; Chaudhuri, Das Sarma, Ganti, & Kaushik, 2007; Shen, Li, & Doan, 2005), e.g., two paper records refer to two different papers if they do not have the same page number. Using constraints allow us to leverage rich domain semantics for improved ER quality. Nevertheless, constraints may not be completely satisfied by records in the underlying databases due to the existence of dirty data, missing data, exceptions, etc. In such cases, common approaches are to conduct manual reviews of conflicts, or relax the satisfaction requirement of constraints by allowing some constraints to be violated in terms of a predefined cost model. This helps to produce solutions, but often also requires expensive computational resources for finding an optimal solution. Such burden has prevented constraints from being widely applied to solve the ER problem in many application areas.
In this paper, we study the question of how to specify and use weighted constraints for performing ER tasks. We attempt to establish a unified framework that incorporates semantic capabilities (in form of weighted constraints) into existing ER algorithms to improve the quality of ER, while still being computationally efficient. A key ingredient in achieving this is to associate each constraint with a weight that indicates the confidence of domain experts on the robustness of semantic knowledge it represents. A good number of works have studied constraints in the literature of ER (Arasu et al., 2009; Chaudhuri et al., 2007; Doan, Lu, Lee, & Han, 2003; Dong, Halevy, & Madhavan, 2005; Tung et al., 2001; Wagstaf & Cardie, 2000; Schewe & Wang, 2014). However, little work has been carried out on how to deal with weighted constraints. Our work was motivated by Dedupalog (Arasu et al., 2009), a declarative framework for resolving entities using constraints without weights, and has extended the previous work (Z. Shen & Wang, 2014) by taking the interaction among multiple entity types into consideration. We believe that weights can provide useful insights concerning ambiguity or conflicting information. For instance, when two records u and v are identified as a match by a constraint and as a non-match by a constraint simultaneously, how can we decide whether (u, v) is a match or non-match? If and have the weights 0.9 and 0.6 respectively, one may decide that (u, v) should be a match since has a higher weight than.