Query Processing Based on Entity Resolution

Introduction

Data quality has been addressed in different areas, such as statistics, management science, and computer science(Batini & Scannapieca, 2006). Dirty data is the main reason to cause data quality. Many surveys reveal that dirty data exist in most database systems. For example, a survey (Raman, DeHoratius & Ton, 2001) reports that over 65% of the inventory records at retailer Gamma were inaccurate at the store-SKU level. The consequences of dirty data may be severe. Having uncertain, duplicate or inconsistent dirty data leads to ineffective marketing, operational inefficiencies, inferior customer relationship management, and poor business decisions. For example, it is reported (English, 1997) that dirty data in retail databases alone costs US consumers $2.5 billion a year. Therefore, several techniques have been developed to process dirty data to reduce the harm of dirty data.

Existing work on processing dirty data can be divided into two broad categories. The first category is data cleaning (Rahm & Do, 2000), which is to detect and remove errors and inconsistencies from data to improve data quality. However, data cleaning cannot clean the dirty data exhaustively and excessive. It may lead to the loss of information. Besides this, existing data cleaning techniques are generally time-consuming. Especially when the massive data is updated frequently, frequent data cleaning operation will greatly affect the efficiency of the system. Therefore, some researchers propose algorithms in the other category, to perform queries on dirty data directly and obtain query results with clean degree from the dirty data(Andritsos, Fuxman & Miller, 2006; Fuxman & Miller, 2005; Fuxman, Fazli & Miller, 2005).

Several models for dirty data management without data cleaning have been proposed (Boulos et al., 2005; Hassanzadeh & Miller, 2009; Widom, 2004). But most of these models only consider the uncertainty in values of the attributes and the quality degree of the data, without the consideration of the entities in real world and their relationships. In this paper, we focus on entity-based relational database model in which one tuple represents an entity. This model can better reflect the real world entities and their relationships.

In applications, the different representations of the same real-word entities often lead to inconsistent data, uncertain data or duplicate data, especially when multiple data sources need to be integrated (Dong, Halevy & Yu, 2009; Lenzerini, 2002). In the entity-based relational database, for the duplicate data referring to the same real-world entity, we combine these data, and for inconsistent data (or uncertain data), we endow each of them a value (we call it as quality degree) which reflects its quality. Example 1 shows this process.

• Example 1: Consider a fragment of the dirty data shown in Table 1. In this table, we can easily identify that tuples 1, 3 and 6 refer to the same entity in the real world even though their representations are different. By preforming entity resolution and combining these three tuples, we can get one entity tuple. In this process, we don’t remove any data, because we are not completely sure which value is the correct (or real) one. By this table, we can only assume the value of the attribute “Name” is more likely to be “Wal-Mart”, but we can’t deny the value “Mal-Mart” completely. So, in entity-based relational database, we reserve all possible values of attributes, which implies that the value of one attribute in a tuple may be uncertain, and it may contain multiple values. We endow possible each attribute value with a quality degree in accordance with their proportion, as shown in Table 2. In tuples 1, 3 and 6, the value “Wal-Mart” appeases twice, so the quality degree is 2/3 ≈ 0.67. Similarly, other quality degrees can be given. Then we get an entity tuple as shown in Table 2.