EntityManager：基于实体的不一致数据管理系统

不一致数据广泛存在于现实世界中。造成数据不一致的一个重要原因是，现实世界中的一个实体在不同的数据源中可能有不同的表示形式，或者实体的某一属性的值会随着时间发生变化。当数据集成时，这些相同的实体被不同的元组描述，这样在一定的约束条件下，比如主键约束，元组之间有可能产生冲突。这时，可以使用EntityManager将描述同一实体的元组组织起来，组成实体单元，并对实体进行存储和管理。

1.系统的原理

例如，在表1中，元组1、2、3代表同一个人John Smith。表上有函数依赖Phn→ Name，元组1、3，2、3互相冲突。但是实际中，J.Smith是John Smith的缩写形式，它们表示同一个人并且可以同时出现。现有的实体识别技术[1]将元组1、2、3识别为同一实体。EntityManager将其组织起来表示为表2中EID为1的实体。其中实体的组织以属性为单位，根据每个属性值出现的频度为每个属性值附加一个概率值，表示该属性值在实际中出现的频率。

表1：雇员信息的原始不一致数据

表2：雇员信息实体表

与传统的关系数据库的查询相比，以实体为存储和处理单位的实体数据查询更能满足用户的需求。假设用户要找出John Smith的信息，传统的数据查询只能返回表1中元组1、2的信息。而实体数据查询能够返回表2中eid为1的实体，该实体包含了1、2的信息，同时包含了元组3的信息。即，通过对实体数据查询，查询的结果更加完整，且返回的信息包含了各个值在现实世界中被使用的频率，对查询结果具有一定的指导意义。此外，基于实体的查询支持近似查询，返回的查询结果携带有查询结果与查询条件的近似程度，其中近似程度以概率描述。

2.系统框架

如图1所示，EntityManager系统主要包括5个模块，分别是实体识别模块、语法分析模块、查询计划模块、查询操作模块、数据索引模块。其中，实体识别模块的输入是不一致数据，通过实体识别算法，模块输出实体数据，将实体数据存储在系统中。当处理一个查询时，首先由语法分析模块分析查询的语法，之后查询计划模块优化查询，生成查询计划，最后用数据索引模块和查询处理模块执行查询计划。

图1:系统框架

3.查询模型

传统数据库的查询条件和数据库元组的匹配是精确匹配，查询的结果也是精确的，而EntityManager系统中查询模型是基于相似性匹配的近似查询模型，基于实体的查询结果是带有概率值的不确定值。不确定值的概率值来源于两个方面:一是实体属性值本身的不确定性;二是相似性匹配的匹配程度。因此，EntityManager系统定义了与传统查询模型对应的近似查询模型，主要包括近似选择、近似连接、近似聚集、近似更新以及近似分组。此外，为了方便用户的使用，EntityManager系统还设计了类似于EQL的近似查询语言。

4.查询处理

处理查询的关键在于查询操作符的实现。其中近似聚集、近似更新的实现主要依赖于其近似行的定义，基于此扫描数据库即可。近似分组的本质是计算两个属性值的相似性，而近似连接的本质也是计算两个属性值的相似性，因此可以用处理近似连接的方法处理近似分组。新的查询处理主要关注近似选择和近似连接操作。

查询算法：不同于传统的关系型数据库，EntityManager系统中选择操作和链接操作均采用近似模型。我们分别设计了基于实体的近似查询算法[4,5]和近似连接算法ES-JOIN算法[2]

索引结构：为了更加有效地处理近似选择和近似操作，EntityManager系统采用了新的索引结构。对于近似查询，我们设计了F-gram索引结构[4]，该索引保证相似的字符串被存储在同一个树节点中。同时保证了不相似的字符串被存储在不同的树节点中。对于近似连接操作，我们设计了基于实体层次和实体属性层次的双层前缀索引结构[2]，使得不相似的实体对尽早的被过滤掉。

查询优化：EntityManager系统采用的近似查询模型并不影响传统查询优化中查询计划的选择，然而，实体多属性特征及查询近似性为查询估计带来了新的挑战。针对不同的查询操作，我们设计了新的查询估计算法：包括范围查询的估计[6]和近似连接的估计算法[3,7]。

Li, Y., Wang, H., Gao, H.: Efficient entity resolution based on sequence rules. In: Shen, G., Huang, X. (eds.) CSIE 2011, Part I. CCIS, vol. 152, pp. 381–388. Springer, Heidelberg (2011)

Liu, X., Wang, H., Li, J., Gao, H.: Es-join: Similarity join algorithm based on entity. Research Report HITDB-12-001, Harbin Institute of Technology (October 2012)

Liu, X., Wang, H., Li, J., Gao, H.: Multi-similarity join order selection in entity database. Journal of Frontiers of Computer Science and Technology 6(10), 865 (2012)

Tong, X., Wang, H.: Fgram-tree: An index structure based on feature grams for string approximate search. In: Gao, H., Lim, L., Wang, W., Li, C., Chen, L. (eds.) WAIM 2012. LNCS, vol. 7418, pp. 241–253. Springer, Heidelberg (2012)

Tong, X., Wang, H., Li, J., Gao, H.: A top-k query algorithm for weighted string based on the tree structure index. In: National Database Conference of China (2012)

Zhang, Y., Yang, L., Wang, H.: Range query estimation for dirty data management system. In: Gao, H., Lim, L., Wang, W., Li, C., Chen, L. (eds.) WAIM 2012. LNCS, vol. 7418, pp. 152–164. Springer, Heidelberg (2012)

Zhang, Y., Yang, L., Wang, H.: Similarity join size estimation with threshold for dirty data. Journal of Computers 35(10), 2159–2168 (2012)

“大数据与数据科学家”公众号

主编：王宏志

特邀副主编： 朱劼

副主编： 丁小欧

责任编辑： 齐志鑫，宋扬

编辑： 陶颖安

-精彩内容，记得分享到朋友圈-