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)

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

主编:王宏志

特邀副主编: 朱劼

副主编: 丁小欧

责任编辑: 齐志鑫,宋扬

编辑: 陶颖安

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

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180308G1AN0F00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券