面向数据融合的多粒度数据溯源方法

面向数据融合的多粒度数据溯源方法

莫兴伟

南宁地精科技有限公司   530000

摘要随着数据量的增加,数据间的关联和交叉,需要通过数据融合来实现数据的价值最大化。然而,由于数据融合过程复杂,为清晰解释数据融合过程,建立数据融合的回溯机制十分必要。虽然对数据溯源的研究很多,但大多是面向查询和工作流的溯源研究,而面向数据融合的溯源研究很少。文中面向数据融合溯源展开研究,提出了一种支持多粒度数据溯源的方法。首先,对数据融合过程进行抽象,以实体为核心构建模式,实体和属性的语义图,将数据融合过程语义化,并提出优化的溯源信息存储模式;然后,基于语义图,分别提出了实体级和属性级的溯源查询算法,以及相应的查询优化策略;最后,通过实验证明了提出的数据溯源方法的有效性。

关键词;数据溯源;数据融合﹔多粒度

数据融合是一个复杂的数据处理过程,其典型代表包括模式对齐,实体链接,冲突解决和实体演化等操作。模式对齐解决模式元素之间的一致性问题,用于应对数据源的异构性;实体链接的关键在于实体识别,将多个命名实体映射到一个真实实体上;冲突通常是由数据源的异构性引起的,解决冲突的关键是在所有冲突的值中找到真值;实体演化用于隐含知识的发现,便于理解复杂数据。

1问题描述及总体框架

1.1问题描述

面向数据融合的多粒度数据溯源是建立针对数据融合过程的回溯机制﹐首先分析建模数据融合的过程,然后进行多粒度的溯源查询﹐目的是解决复杂的数据融合过程中的数据质量问题。本节主要介绍数据融合过程的回溯机制和多粒度溯源查询的相关描述。图1列出了本文使用的符号。多粒度溯源查询指面向实体的粗粒度溯源查询(或称实体级的粗粒度溯源查询,简称粗粒度溯源查询)和面向属性值的细粒度溯源查询(或称属性级的细粒度溯源查询,简称细粒度溯源查询)。

图1 主要符号说明

问题1(数据融合过程的回溯机制) 给定一个数据融合 过程,主要包括模式对齐、实体链接、冲突解决和实体演化。

本文通过每个阶段产生的元信息来构建实体级别和属性级别 的溯源图,并根据具体查询生成的半环多项式,从实体级和属性级两个角度回放数据融合过程。

1.2总体框架

面向数据融合的多粒度溯源框架,主要分为数据融合部分和数据溯源部分。数据融合部分将多个数据源的数据进行融合,并在融合过程中产生支持溯源的元信息。例如,通过模式对齐产生相应的模式元信息﹔通过实体链接产生相应的实体元信息;通过冲突解决产生相应的属性元信息﹔通过实体演化产生相应的演化实体的元信息。将这些元信息作为节点,形成带有一定语义的溯源图,将溯源图持久化到数据库中,形成溯源信息数据库,从而进一步实现溯源信息的多粒度查询。注:本文不讨论具体的数据融合算法,假定已知数据融合过程中产生的元信息。在此,对数据融合过程产生的元信息进行简单描述。

2实体级溯源图

本文重点关注数据融合过程中产生的元信息,仅考虑一般的数据融合的步骤,而不考虑数据融合过程中涉及的源数据的格式与类型。以两个数据库为例,通过对不同数据库进行数据融合来介绍本文模型。实体级溯源图构建的核心是将数据融合中的模式对齐、实体链接和实体演化等抽象成实体级操作,以实体为单位,记录整个数据融合的过程。实体级溯源图主要基于PROV溯源图。PROV溯源图的核心结构主要包括溯源技术通用的3部分:对象、活动以及代理。对象一般指具体的物体,也可以指抽象的概念;活动指作用于实体上的行为,该行为作用在实体上,同时可能产生新的实体;代理主要针对溯源所关注的质量及可信度等特性。在PROV的核心结构中,对象、活动和代理之间主要有7种关系。基础的关系为活动使用(Used)和产生(Wasgenerated-By)实体,同时受到代理的影响。

3 溯源模型的存储优化策略

3.1溯源图的存储优化策略

溯源信息记录了整个数据融合的过程,导致溯源信息的 存储代价很大,因此本文考虑从关系的角度对溯源图的存储

进行优化。实体级溯源图的存储优化策略以实体链接为例进 行介绍。实体级溯源图主要通过对象、活动和代理之间的关 系来表现语义性。为了实现溯源数据的查询和维护,需要对 该模型进行优化。如果直接实现该模型,则会带来巨大的存 储和查询代价,如对某一个实体进行查询时会遍历所有与实 体相关的属性和联系,从而带来不必要的代价。因此,需要对 模型进行优化,在减小代价的同时保留完整的语义信息。

3.2溯源树的层次存储优化策略

本文是基于SQL进行查询的,再对查询结果进行溯源查 询。因此,针对SQL首先会生成相应的查询树,再根据查询

树生成对应的溯源树。溯源树是基于查询树的节点存储溯源 信息,这样可以直接获得查询结果的溯源信息,即半环多项式,接着对半环多项式进行推理和演化。如图10所示,左边 的SQL语句是选取卫生合格的餐厅的经纬度信息,右边是对

应的查询树。的溯源树,对应每一个查询节点都要存储对应的溯源信息,这 样带来的存储代价过大。因此,本部分考虑溯源树的层次存 储优化策略,即只存储部分节点的信息,而不存储所有中间结 果节点的溯源信息。这样能够减小一定的存储代价,但会增大溯源查询的代价。

4多粒度溯源查询优化策略

将粗粒度溯源查询、细粒度溯源查询、多粒度溯源查询和 查询优化后的多粒度溯源查询进行对比。横轴 为数据集的大小,分别为200kB,2MB,20MB和200MB,纵轴 为溯源查询时间占基础查询时间的比例,多粒度溯源查询的 时间是将粗细两种不同粒度的溯源查询时间进行累 加。本文提出的利用三级索引的优化策略 通过在实体、数据融合过程上建立索引,缩短了查询时间。优 化之后的多粒度溯源查询的时间约占基础查询运行时间的 30%,时间缩短了近25%,可见建立的索引具有缩短时间代价的效果。

结束语

本文提出了面向数据融合的溯源框架和溯源模型,从而实现了溯源信息的多粒度查询,能够有效追溯数据的融合过程。实验证明,本文提出的溯源信息管理模型的查询时间代价和存储代价都是可以接受的。下一步将针对查询树优化以及减少半环多项式计算代价等方面进行深人研究。

参考文献：

[3].Provenance in Databases: Why, How, and Where[J].Foundations & trends in databases.2009.379-474.

[4]Cui Y.,Widom J..Lineage tracing for general data warehouse transformations[J].The VLDB Journal.2003,12(1).41-58.