基于词嵌入的元组级数据溯源方法.pdf

收稿日期:2023-01-18摇 摇 摇 摇 摇 摇 修回日期:2023-05-23基金项目:国家自然科学基金资助项目(61902222);东北石油大学优秀中青年科研创新团队培育基金(KYCXTDQ202101)作者简介:杨摇 彬(1996-),女,硕士研究生,研究方向为软件工程、数据分析、数据治理等;通讯作者:高俊涛(1979-),男,博士,副教授,CCF会员(F4854M),软件工程专委委员,研究方向为软件工程、过程建模、自动机学习等。基于词嵌入的元组级数据溯源方法杨摇 彬1,高俊涛1,王志宝1,李摇 菲2,马摇 强2,江树涛1(1.东北石油大学 计算机与信息技术学院,黑龙江 大庆 163318;2.黑龙江八一农垦大学 信息与电气工程学院,黑龙江 大庆 163319)摘摇 要:在信息爆炸时代,数据量与日剧增,使用数据挖掘技术可挖掘其内在联系,但前提是所使用的数据正确无误,否则其后的一切工作将毫无意义。数据溯源技术可帮助数据分析人员快速定位到错误数据的来源和加工过程,减少错误数据的分析时间和难度,对数据质量控制与可信管理具有重要价值。现有的元组级数据溯源方法存在存储开销大和溯源效率低的问题,文章使用词嵌入技术改进元组级数据溯源方法。首先,研究元组向量化编码机制,依据元组向量相似度识别元组溯源关系;其次,提出基于属性重要性的优化算法提高溯源的精确率;再次,引入近似最近邻搜索和元组过滤优化机制降低溯源时间复杂度;最后,采用有向无环图展示元组数据的溯源关系。实验结果表明,该方法精确率较高、时间复杂度较低、存储消耗较少,能够有效改进元组级数据溯源方法。关键词:结构化数据;数据溯源;元组向量;相似度比较;词嵌入中图分类号:TP311.13;TP391摇 摇 摇 文献标识码:A摇 摇 摇 摇 摇 摇 文章编号:1673-629X(2023)12-0049-09doi:10.3969/j.issn.1673-629X.2023.12.007A Tuple-level Data Lineage Approach Based on Word EmbeddingYANG Bin1,GAO Jun-tao1,WANG Zhi-bao1,LI Fei2,MA Qiang2,JIANG Shu-tao1(1.School of Computer and Information Technology,Northeast Petroleum University,Daqing 163318,China;2.School of Information and Electrical Engineering,Heilongjiang Bayi Agricultural University,Daqing 163319,China)Abstract:In the era of information explosion,the volume of data is increasing day by day,and data mining technology can be used toexplore its inner connection,but only if the data used is correct,otherwise all the subsequent work will be meaningless.Data lineage tech鄄nology can help data analysts quickly locate the source and processing process of erroneous data,reduce the time and difficulty ofanalyzing erroneous data,and has important value for data quality control and trustworthy management.The existing tuple-level datalineage methods have the problems of high storage overhead and low lineage efficiency,and we use word embedding technology toimprove the tuple-level data lineage methods.Firstly,the tuple vectorization encoding mechanism is investigated and tuple lineage rela鄄tionships based on the similarity of tuple vectors is identified.Secondly,an optimization algorithm based on attribute importance isproposed to improve the precision of lineage.Thirdly,the approximate nearest neighbor search and tuple filtering optimization mechanismis used to reduce the lineage time complexity.Finally,a directed acyclic graph is used to show the lineage relationships of tuple data.Theexperiment shows that the proposed method has higher lineage precision,lower time complexity and less storage consumption,and can ef鄄fectively improve the tuple-level data lineage method.Key words:structured data;data lineage;tuple vectors;similarity comparison;word embedding0摇 引摇 言在大数据时代下数据生成规模激增,原生数据经过多次复制、迁移、集成、抽取等操作后形成海量派生数据,使数据来源及衍生路径表现出多样化、复杂化的特点1。若原生数据的来源模糊不清,则会极大程度地影响派生数据的可靠性2。数据溯源技术能够监控与评估数据质量,有助于定位错误根因,追踪错误路径,还可以对数据进行安全管控,能够帮助企业确定字段敏感信息。数据的可靠性和安全性是有效决策的基础,为加强数据质量,由此产生了数据溯源技术3。第 33 卷摇 第 12 期2023 年 12 月摇 摇 摇 摇 摇 摇 摇 摇 摇 摇计 算 机 技 术 与 发 展COMPUTER TECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇 摇Vol.33摇 No.12Dec.摇 2023目前数据溯源在溯源理论、溯源模型以及方法实践上都开展了研究工作,但仍有不足,标注法的实现需要为元组保存完整的半环多项式(即标注),由于通过查询产生的元组依赖于先前查询的元组,导致半环多项式的数量大量增长,存在存储空间爆炸的问题。因此,国外学者 Leybovich M 等4提出基于词嵌入的元组级数据溯源方法,该方法有效避免存储数据标注。文中主要贡献如下:(1)在元组向量化编码机制的基础上给出属性重要性优化算法,解决词嵌入方法中溯源精确率低的问题。(2)引入近似最近邻搜索算法后又给出元组过滤优化策略,解决时间消耗长溯源效率低的问题。1摇 相关工作目前在数据溯源研究中主要有以下几方面工作。从溯源概念上,Lanter5首次提出“Data Lineage冶用以描述目标数据的来源转化过程。Cui 等6从关系代数角度出发,定义了 View Data Lineage 用来标识数据仓库视图中目标数据的源数项集。Buneman 等7进一步将数据溯源进行分类,提出了 why 溯源和 where 溯源。Green 等8以半环多项式的形式提出了 how 溯源。从溯源粒度上,数据溯源被分为 3 个不同层次,第 1 层次是表级的数据溯源,其目标是获得目标表与源表之间的转换,是一种粗粒度的数据溯源;第 2 层次是字段级(列)的数据溯源,其目标是获得源表字段和目标表字段之间的属性映射关系,它是表级溯源的细化;第 3 层次是元组级(行)的数据溯源,其目标是获得目标表元组的源元组集合,是一种细粒度的数据溯源9。从溯源模型上,W3C 发布的 PROV10是目前为止最成功的模型,成为数据溯源史上的里程碑。此后,围绕 PROV,专家学者对各个领域进行深入更深层次的研究。Niu X 等11将 PROV 引入关系数据库,将溯源信息存储成 PROV-JSON 的形式进行数据溯源。燕杨月12将 PROV 应用到物联网数据场景,实现对物联网起源信息的描述。杨斐斐等13对 PROV 进行扩展,构建了面向数据融合的溯源模型冥PROV-Semi。从溯源方法上,林悦邦14和张苒15等对支持全特性查询语言的逆置函数溯源方法进行研究。逆置函数法是指在计算时通过逆向查询或构造逆向函数对查询求逆,求逆的结果就是目标数据的源数据。其优点是只需存储少量的元数据就可实现数据溯源;缺点是具有一定局限性,需要提供逆置函数(并不是所有的函数都具有可逆性)和相对应的验证函数。LeybovichM 等4,16和 Hofmann F A 等17提出一种数据溯源的近似总结方法,其优点是可应用于派生数据更为膨胀的海量数据场景;缺点是以丢失一些信息为代价压缩表 示 溯 源 信 息。Pierre Senellar 等18-19开 发 的ProvSQL 系统20利用标注法实现元组级数据溯源。标注法是指记录数据的出处、产生过程、流转信息等作为数据标注,通过查询目标数据的标注来获得数据的溯源信息。其优点是实现简单,且容易管理;缺点是需要详细记录所有的数据转换信息,会出现元数据多于原始数据的情况。在实际应用中,细粒度形式的溯源信息标注通常会产成大容量存储,如何优化关系数据库下的溯源方法,成为亟待破解的难题21。2摇 溯源定义及问题描述2.1摇 元组级数据溯源定义 1(元组级数据溯源):令 T=Q(T1,T2,Tm)为将查询(Q)应用于表 T1,T2,Tm的查询结果元组集,对于 坌t沂T,都有 Q-1(t)=,则称 T*1,T*2,T*m为元组(t)的源数据,即对产生元组(t)有贡献的数据元组集合(S)6。其中,T*1,T*2,T*m是 T1,T2,Tm的最大 子集,则有:(1)Q(T*1,T*2,T*m)=t;(2)坌T*i:坌t*沂 T*i:Q(T*1,t*,T*m)屹堙。2.2摇 问题描述该文的主要内容是:研究元组级数据溯源方法,为数据库管理系统(DBMS)中元组的存在提供解释。即给定一个查询(Q)和查询输出的数据元组集合(T),在来源表中找出对产生每个元组(t 沂 T)有贡献的源数据元组集合(S)。示例 1:SQL 语句示例用来帮助理解元组级数据溯源定义。Q:摇 摇 摇INSERT INTO results(title,rating,timestamp)SELECT m.title,r.rating,r.timestampFROM ratings r,movies mWHERE m.movieId=r.movieIdAND r.userId=4;摇 摇表 1(a)为执行语句 Q 后获得的查询结果表(results),每个元组包含 userId 为4 的用户观看的电影名,所 给 评 分 及 评 价 时 间。表 1(b)为 评 价 表(ratings),每个元组包含有关用户表达的电影偏好的信息(0 5 星评分)。表 1(c)为电影表(movies),每个元组包含有关电影的基本信息。通过分析可以得到,表 1(a)中标注为 q1的元组由表1(b)中标注为 r1的源元组和表1(c)中标注为 m1的源元组结合形成,如图1 所示,以此实现元组(q1)的一次溯源。05摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷表 1摇 数据统计表表名摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 字段摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇ratingtimestamptitle(a)查询结果表(results)31573944252Toy Story(1995)q13.51573938415Star Wars:Episode IV-A New Hope(1977)q241573938898Pulp Fiction(1994)q3(b)用户评价表(ratings)userIdmovieIdtimestamprating4115739442523r1426015739384153.5r2429615739388984r3(c)电影表(movies)movieIdtitlegenres1Toy Story(1995)Animation|Children|Comedy|Fantasym12Jumanji(1995)Adventure|Children|Fantasym23Grumpier Old Men(1995)Comedy|Romancem3Animation|Children|Comedy|FantasyToy Story(1995)1157394425214r13titleratingratingsmoviesresultsuserIdmovieIdratingtimestampmovieIdtitlegenres1573944252Toy Story(1995)3m1q1timestamp图 1摇 元组(q1)的溯源过程描述摇 摇 同理,可以对目标元组(q2,q3,q4)直至 qn进行溯源。并且可以对元组(r1,m1)向上溯源,最终形成一个有向无环图,即全链路数据溯源关系图。3摇 元组级数据溯源方法该文在 ProvEmb4的基础上增加了精确率优化机制和搜索效率优化机制,设计了一种基于词嵌入技术的元组级数据溯源改进方法(ProvEmb-X),其想法受生物学“基因冶的启发,使寻找元组的源数据类似于通过 DNA 查找其前辈。3.1摇 方法框架图 2 为文中方法的研究框架,该方法支持范围广泛的非聚合 SQL 查询。输入数据是执行 SQL 后的查询结果元组集(即目标元组),输出数据是为该条元组返回其源元组 id,目的是对目标元组集中的每一条元组进行溯源。基本方法首先是通过一组向量来代表每个元组。其次,通过计算源表元组向量与目标元组向量的相似度,来识别溯源关系。再次,对仅依赖相似度比较导致相似的元组间可能没有溯源关系的问题,给图 2摇 ProvEmb-X 方法框架15摇 第 12 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 杨摇 彬等:基于词嵌入的元组级数据溯源方法出优化方案提高精确率,并对溯源效率进行优化以减少时间消耗。最后,与基于词嵌入的数据溯源方法(ProvEmb)进行对比,验证文中方法的优化效果。该方法具有以下特点:(1)该方法适合大规模数据集。通过分析 SQL 语句来精准定位所需要的数据库表,即便是派生数据更为膨胀的海量数据场景,仍可以快速过滤无用数据。(2)该方法支持复杂的数据变换。可解决范围广泛的非聚合 SQL 查询的数据溯源问题,通过解析 SQL语句中的连接、选择、分组、投影、集合和排序操作获取查询结果字段(目标字段)与数据库源表字段的对应关系,进而应用到方法中的属性重要性优化机制。(3)该方法可实现自动化溯源。无论是纯手工收集的标注法,还是基于 SQL 的半自动标注法,都需要进行人工标注的工作。文中方法可实现自动化,提高溯源效率。3.2摇 元组向量化编码机制该文在元组向量化编码机制中进行目标元组向量和源表元组向量的两部分编码。该文使用 NLP 技术,词向量通过预训练的多语言词嵌入模型在基础文本上获得。文中元组向量化编码机制与 ProvEmb 不同的是,ProvEmb 是将元组中的每个列的文本组合起来形成一条没有语义的句子后进行词嵌入,该文是直接将每个元组中不同列的文本进行词嵌入后再组合,为后续属性重要性优化机制提高溯源精确率做准备。算法1 为元组向量生成算法。算法 1:元组向量生成算法(TPVEC)输入:预训练的词嵌入模型(ST),输入数据表(Ti)输出:为 Ti中的每个元组(t)计算其元组向量(vectort)并存在 tuplevector 中1.摇list vectort摇/存储每列文本的词向量2.摇list tuplevector 摇/存储生成的元组向量集3.摇for t 沂 Ti.tuples do摇/遍历 Ti中的每个元组4.vectort=create(t)摇/调用对 t 构造元组向量方法5.tuplevector.append(vectort)6.end for7.摇return tuplevector8.摇function create(t)摇/定义构造元组向量方法9.摇 摇 摇 摇 list wordvector10.摇 摇 摇list tuplevector11./w 是 t 中的每列文本,为构造 wordvector 列表12.摇 摇 摇wordvector=ST(w)w 沂 t13.摇 摇 摇vectort=weight(wordvector)14.摇return vectort示例 2:基于算法 1 的元组向量构造示例如下:设w寅1,w寅2,w寅3,w寅4沂 R2为元组(t)中的每列文本向量:w寅1=11摇w寅2=-0.51摇w寅3=-11摇w寅4=0.5-1通过算法 1 生成的元组向量(t寅=00.5),但此时 weight=1 生成的元组向量不具备元组特征,在精确率方面会有损失,下文将给出优化机制。4摇 溯源方法优化机制由于仅依赖目标元组向量与源元组向量的相似性,会出现两者间并无溯源关系,却还是错误地将该元组识别为溯源结果的情况。因此,该文提出了改进方案,通过以下 4 个步骤使算法在溯源精确率和效率上有较大的提升。(1)使用局部敏感哈希算法(LSH)提高溯源效率。(2)通过解析查询语句中 FROM 条件直接定位源表,初次过滤无关元组集合。(3)利用时间戳过滤目标元组的派生元组,再次过滤无关元组集合。(4)对于元组中的关键属性,采用加强其特征再组合的方式,形成独有的遗传密码“基因冶,从而提高溯源精确率。4.1摇 近似最近邻搜索在进行实验时发现,暴力穷举式扫描对源表元组向量和目标元组向量进行相似度比较时,时间复杂度为 O(dN),当数据的维度(d)以及数据的规模很大时,巨大的计算量与存储需求使得该搜索方式难以在效率上满足需求。针对此问题,为满足大规模数据场景下的最近邻搜索任务需求,该文采用局部敏感度哈希算法(LSH)进行高维向量近似最近邻搜索(ANN),在损失一定精度的条件下,能够有效平衡精度与资源消耗,以更快的搜索速度和更少的内存负载得到查询项的近似精确甚至精确的搜索结果。LSH 的基本思想是将原高维空间的点都映射至 1 个或多个哈希表的不同位置(桶),原高维空间内距离较近的点会以较大概率映射至同一桶内,从而可直接在该桶内搜索元素,大大提高搜索效率。当哈希函数(h)满足以下两个条件,称 h 为局部敏感哈希函数22:(1)如果 L(q1,q2)d2,则 Ph(q1)=h(q2)逸 p2。条件(1)保证 2 个相似点以较高概率被映射进同一个哈希桶;条件(2)保证 2 个不相似的点以较低概率映射进同一个哈希桶。其中,d1,d2,p1,p2是给定的常数,d1 t.timestamp8.摇 摇摇摇摇/调用构造元组向量方法,将 t 作为参数传入9.摇 摇 摇 摇 摇 摇vectort=create(t)摇10.摇 摇 摇 摇 摇 摇 摇tuplevector.append(vectort)11.摇 摇 摇end if12.摇end for13.end for14.return tuplevector(1)跟踪元组的创建时间戳。淤如 果 元 组(t)被 直 接 插 入 到 DB,则 t.timestamp 是其插入时间。于 如 果 元 组(t)是 通 过 查 询 计 算 的,则 t.timestamp 是查询的执行时间。(2)当将一个元组(t)与一组其他元组(T)进行比较时,该文在计算元组向量生成之前进行判断:如果 t.timestamp t.timestamp(t沂 T),则 t比 t 更新,并且不能成为其源元组的一部分。4.3摇 属性重要性优化机制由于 TPVEC 生成的元组向量不具备其本身特征,因此会导致溯源结果的精确率不高。为提高精确率,对数据库表结构进行研究发现,某些属性可能比其他属性更重要。例如,主键、外键或者是某些参与了数据库查询的重要属性。这意味着可以通过给这些属性的词向量赋予较高权重的方法来加强此元组向量的特征,进而提高相似度匹配的精确率。该文通过解析 SQL 语句的方式寻找真正参与SQL 运算的源属性和目标属性。解析 SQL 语句的主要步骤为:首先,对 SQL 查询语句进行词法分析和语法分析得到抽象语法树。然后,遍历以 Root 为节点的抽象语法树,得到 INSERT INTO target_table(target_attribute_list)目标表(目标属性)、SelectList 源属性、FromClause 源表,再遍历 WhereClause 没有聚合函数的选择操作、GroupClause 分组操作、HavingClause 有聚合函数的选择操作、SortClause 排序操作等节点,从中获得目标属性和源属性的对应关系,以此来为目标属性和源属性的词向量加大权重。titleratingtimestampmovieIdtitleuserIdmovieIdratingresultstimestampatitleratingtimestampmovieIdtitleresultsmoviesuserIdmovieIdratingratingstimestamptitleratingtimestampresultsbmoviesratings图 3摇 属性权重获取流程以示例 1 所示的查询语句为例,遍历抽象语法树后得到的可视化关系如图 3(a)所示。由图 3(b)可知结果表(results)中 title 来自于 movies 表,rating 和35摇 第 12 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 杨摇 彬等:基于词嵌入的元组级数据溯源方法timestamp 来自于 ratings 表。因此在 movies 表中元组向量生成时,应该为 title 赋予比 movies 表中其他属性要高的权重,说明 title 更能代表 movies 中元组的特征。同样,results 中的 title 权重也要加大。因此对每个属性进行词嵌入,将词向量加权平均生成元组向量后,再计算相似度从而提高匹配的精确率。权重计算公式如下所示(对于 坌wi都有 0 臆 wi臆 1):(1)moviesvectort=w1伊 movieId+w2伊 title摇(w1 w2,w1 w3且 w1+w2+w3=1)在 ratings 表中的元组向量生成时,需要为 rating和 timestamp 赋予较高的权重,且 results 表中也要加大其对应的权重,权重计算公式如下所示(对于 坌wi都有 0 臆 wi臆 1):(1)ratingsvectort=w1伊 userId+w2伊 movieId+w3伊rating+w4伊 timestamp(w3=w4 w1,w3=w4 w2且w1+w2+w3+w4=1)(2)resultsvectort=w1伊 title+w2伊 rating+w3伊timestamp(w1 w2=w3且 w1+w2+w3=1)算法 3 为属性权重获取算法,该算法结合深度优先搜索的思想,递归调用 visit 方法获取目标表属性和源表属性的对应关系用 attribute_r_list 存放,即应赋予高权重的重要属性。后执行算法 1(TPVEC),并更改由算法 3(PREUP)生成的重要属性的 weight 值。算法 3:属性权重获取算法(PREUP)输入:数据库语句(Q)输出:目标表属性与源表属性的对应关系 attribute_r_list1.Procedure AnalyzeDatalineage(Q)2.List results_r_list摇/存放目标表的表名和目标属性的关系3.List source_r_list摇/存放源表表名和源表属性的关系4.List attribute_r_list摇/存放目标表属性和源表属性的关系5.QT 饮 generateSQLAST(Q);摇/根据语句(Q),生成抽象语法树(QT)6.Function visit(r)摇/对根节点为 r 的抽象语法树(QT)进行遍历7.if R(r)屹 堙 then8.String results_table摇/初始化,定义变量 string 型9.String source_table10.String results_attribute11.摇摇 for c in childs do/对节点进行类型判断12.摇 摇 摇 摇/如果节点 c 是结果表类型13.摇 摇 摇 摇If Type(c)=RESULTS TABLE then14.results_table 饮 c/记录结果表表名15.摇 摇 摇 摇Else if Type(c)=RESULTS ATTRIBUTE then16.摇 摇 摇 摇 摇 摇/建立目标表表名与目标表属性的关系17.results_r_list 饮(results_table,c)18.摇 摇 摇 摇Else if Type(c)=SOURCE TABLE then19.source_table 饮 c/记录源表表名20.摇 摇 摇 摇Else if Type(c)=SOURCE ATTRIBUTE then21.摇 摇 摇 摇 摇 摇/建立源表表名与源表属性的关系22.摇 摇 摇 摇 摇 摇source_r_list 饮(source_table,c)23.摇 摇 摇 摇 摇 摇/建立目标表属性与源表属性的关系24.attribute_r_list 饮(results_attribute,c)25.摇 摇 摇 摇Else if R(r)屹 堙 then26.visit(c)27.摇 摇 摇 摇 End if28.摇摇 End for29.End if30.Return attribute_r_list综上所述,文中方法在第 1 阶段元组过滤优化机制时,FROM 过滤源表的时间复杂度为 O(m),共 m个源表,每个表有 k 个元组 n 个属性。时间戳过滤元组的时间复杂度为 O(ikm),表示进行 ikm次比较,i 为目标元组数,m为 FROM 过滤后的源表数量;在第 2 阶段属性重要性优化机制的时间复杂度为O(max(mn+j+1),n为遍历抽象语法树得到的源表的重要属性,j为遍历抽象语法树得到的目标表的重要属性(j 为目标表的所有属性);在第 3 阶段元组向量生成时的时间复杂度为 O(ij+knm),k为时间戳过滤后得到的元组;在第 4 阶段近似近邻搜索的时间复杂度为 O(ij)。因此,ProvEmb-X 的时间复杂度为 O(max(mkn+imk),而ProvEmb 为 O(max(mkn+imk),mkn远远小于 mkn。由此可知,文中方法能够有效降低时间复杂度。5摇 实摇 验基于提出的 ProvEmb-X 元组级数据溯源方法,在3 种不同的数据集上进行实验,并与精确溯源系统ProvSQL20进行对比,验证 ProvEmb-X 的精确率;与ProvEmb4进行对比,验证 ProvEmb-X 的优化效果;最后展示对比实验结果。实验环境为:Intel(R)Core(TM)i7,16 GB 内存,Windows 10 操作系统。5.1摇 实验数据MovieLens 数据集描述 MovieLens 电影23推荐系统网站中人们对电影的喜爱程度,数据集中的每部电影都有一个唯一标识符 movieId。固井作业数据集来自中国石油冀东油田公司实际固井数据,数据集中的每个井筒都有唯一标识符 wellbore_id。Olist 电子商务数据集24来自巴西市场上最大的百货商店 Olist,数据集中的每个订单都有一个唯一标识符 order_id。数据集统计信息如表 2 所示。45摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 计算机技术与发展摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 第 33 卷表 2摇 数据集统计信息数据集中文表名英文表名属性数量元组数量Movielens电影表movies32 000评分表ratings410 000标签表tags41 048 575固井作业固井基础数据表dr_ops_cement_info4822 440注水泥基本信息表dr_ops_cement_info3221 683井筒表cd_wellbore35 424Olist 电子商务商品订单数据表olist_order_items_dataset7112 652订单数据表olist_orders_dataset899 443客户数据表olist_customers_dataset599 443商品数据表olist_products_dataset932 9535.2摇 实验结果及分析5.2.1摇 精确率对比(1)精确率评价指标。ProvSQL 是基于标注的方法,由 Pierre Senellart 等人开发的开源项目,支持范围广泛的非聚合 SQL 查询,是目前为止较为精确的数据溯源系统。因此,该文使 用 公 式(2)来 计 算 实 验 结 果 的 精 确 率,ApproxLineage(t)是该文实验结果元组的集合。Ex鄄actLineage(t)是由 ProvSQL 系统返回的关于 t 的精确源元组集合。Precision(t)代表返回的近似溯源结果与精确溯源结果的重合占比,该文将所得到的重合占比结果作为精确率的评价指标。Precision(t)=ApproxLineage(t,n)疑 ExactLineage(t)ApproxLineage(t,n)(2)(2)精确率优化消融实验。在 3 种数据集上分别对 70 条 SQL 语句的查询结果进行溯源,将平均精确率作为实验结果。由表 3 的精确率对比结果可知,ProvEmb-X 在 3种数据集上的精确率均优于 ProvEmb(baseline)。在Movielens 数据集和 Olist 电子商务数据集上的精确率优化效果不如固井作业数据集明显,是由于固井作业数据集中属性数量较多,由 w/o PREUP 与完整的ProvEmb-X 相差 0.07 左右可以看出,PREUP 算法在极大程度地发挥作用提高精确率。由图 4(a)的增长情况也可得知 PREUP 算法表现较好。最终结果显示,在 Movielens 数据集上精确率整体提高了 2.35%,在固井作业数据集上精确率提高了 10.08%,在 Olist 电子商务数据集上精确率提高了 3.53%。表 3摇 消融实验结果方法Movielens数据集固井作业数据集Olist 电子商务数据集精确率对比ProvEmb0.852 400.763 510.834 15w/o FROM0.864 130.835 630.842 78w/o TPFIL0.865 320.843 180.851 86w/o PREUP0.854 960.791 410.841 56ProvEmb-X0.875 850.864 320.869 43溯源效率对比ProvEmb2.974.353.07w/o FROM2.764.272.93w/o TPFIL2.613.842.69w/o LSH2.643.922.84ProvEmb-X2.583.772.665.2.2摇 溯源效率对比(1)溯源效率评价指标。该文将单条元组的溯源消耗时间作为溯源效率的评价指标,单位为分钟。(2)溯源效率优化消融实验。在 3 种数据集上分别对 70 条 SQL 语句的查询结果进行溯源,最后将单条平均耗时作为实验结果。由表 3 溯源效率对比结果可知,ProvEmb-X 在 3种数据集上的时间消耗均小于 ProvEmb。由 w/oFROM 与完整的 ProvEmb-X 差值得知“FROM 定位冶表现最为突出,其次是 LSH 算法。图 4摇 对比实验结果55摇 第 12 期摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 杨摇 彬等:基于词嵌入的元组级数据溯源方法由图 4(b)的 4 次对比实验可知,ProvEmb 的穷举式扫描对所有元组都进行元组向量生成,计算量巨大导致消耗时间也相对较长。因此,使用 FROM+LSH算法将范围固定在少部分相关元组中。但是在实验中发现耗时仍然过大,继而使用 TPVEC+LSH+TPFIL 算法过滤非源数据的元组,再次缩短时间消耗。最终结果显示,在 Movielens 数据集上耗时减少了 13.13%,在固井作业数据集上减少了 13.33%,在 Olist 电子商务数据集上减少了 13.36%。5.2.3摇 存储开销对比该文采用计算 ProvSQL/ProvEmb(-X)相对比例的方式,对比标注法与词嵌入法的存储开销,等于 1 代表存储开销一样,小于 1 代表词嵌入法开销大,大于 1代表标注法开销大,计算结果如表 4 所示。由结果可知标注法与词嵌入法的存储比较相差较小,是因为文中实验设备能力有限,实验数据体量相对较小且 SQL语句数量较少,导致数据标注占用的存储空间不大,若是在大规模数据集上则会有较大的差异。且 ProvEmb-X 的存储开销比 ProvEmb 稍高,是由于在属性重要性优化机制阶段对解析 SQL 语句得到的 JSON 进行了存储。表 4摇 存储开销相对比例方法Movielens数据集固井作业数据集Olist 电子商务数据集ProvEmb1.141.221.35ProvEmb-X1.091.181.315.2.4摇 溯源结果展示该文只对表 1(a)中 tid=8 的元组 results(MontyPythons Life of Brian(1979),3.5,1 573 944 005)进行溯源结果展示。由于文章篇幅限制,在相关表中各取相似度排名较高的前 7 个元组,并对其在 ProvSQL中进行比较,最终实验结果如表 5 所示。其中,results表中 tid=8 的元组的直系源数据是由 movies 表中 tid=1 053 的元组和 ratings 表中 tid=817 的元组组合而成。其他元组为 tid=8 的元组的间接源元组,如图 5 所示,可以清晰地展现 tid=8 的流转路径。表 5摇 results 表中 tid=8 实验结果n来源表tid相似度值排序是否是源元组1movies1 0530.999 999 940 395 355 2是2movies6 6840.784 715 116 024 017 3是3movies5 9920.772 588 431 835 174 6是4movies1 1080.714 576 542 377 471 9是5movies2 6960.713 405 609 130 859 4是续表 5n来源表tid相似度值排序是否是源元组6movies5 0140.702 540 755 271 911 6是7movie