对有效发现匹配依赖项方法的若干研究

R.Santhya¹, S.Latha¹, Prof.S.Balamurugan¹, S.Charanyaa²

印度泰米尔纳德邦哥印拜陀，Kalaignar Karunanidhi理工学院IT系
高级软件工程师大型机技术前，Larsen & Tubro (L&T)信息技术，金奈，泰米尔纳德邦，印度

摘要

本文详细介绍了文献中流行的有效发现匹配依赖项的各种方法。匹配依赖关系(MDs)的概念最近被提出用于指定对象识别的匹配规则。与条件的功能依赖类似，MDs也可以应用于各种数据质量应用程序，例如检测完整性约束的违反。考虑了从给定的数据库实例中发现匹配依赖项的相似约束的问题。这次调查将促进信息挖掘领域的大量研究。

关键字

数据匿名化，匹配依赖关系，对象，相似约束，信息挖掘。

介绍

近年来，向公众公布敏感数据的需求急剧增长。最近几天，由于大量的Ã¢Â′Â dirtyÃ¢Â′Â数据起源于不同的数据库社区，数据质量的保存急剧上升。由于人与机器的各种错误，这些数据经常包含重复、不一致和冲突。除了处理大量数据的成本外，人工检测和删除Ã¢Â′Â dirtyÃ¢Â′Â数据肯定是不现实的，因为人工提出的清理方法可能会再次引入不一致。因此，数据依赖关系在关系数据库设计中被广泛应用，以建立完整性约束。因此，保护个人隐私和确保社交网络数据的效用也成为一个具有挑战性和有趣的研究课题。本文从匹配依赖关系和文献中提出的可能解决方案以及匹配依赖关系的有效性对攻击进行了研究。

挖掘大型数据库中项目集之间的关联规则

本文提出了一种有效的生成数据库中所有项之间表示关联规则的算法。对数据的过去事务分析是提高或增加数据质量的方法之一。购物篮数据是指不包含顾客所购买的每件产品的详细信息的数据，而是包含一段时间内的购买信息，特别是关于数据质量的信息。购物篮数据存储关于每笔交易所购买商品的信息。根据数据增量的质量可以对其进行决策。为了提高数据的质量，应该注意所购买的项目。这个数据库系统下行的原因是，它不会为愿意利用信息的用户提供所需的功能。本文介绍了在具有最小置信度的项目集中挖掘庞大的篮子数据类型事务的关联规则的问题。作者将规则挖掘问题分解为两个问题

1)找到minsupport，这是一个项目的组合，它具有高于阈值的分数事务支持。这也可以称为大项目集，重置的所有不符合阈值的组合称为小项目集。

2)假设Y是大型项目集，如果项目集Y很大，那么Y的每个子集也很大，因此我们使用第一个问题的结果。假设C是一个置信度因子，如果比值大于C，则该规则满足置信度因子C。所有由Y推导出来的规则必须满足支持度约束，因为Y满足支持度约束。模板算法用于查找大型项目集。

用于预测的邻域依赖性

在本文中，作者引入了邻域依赖(ND)的概念，其显式规律为:Ã¢Â ' Â:人口规模和收入相似的家庭，往往拥有相似的汽车，incomeÃ¢Â ' Â '。理性地说，这个东西的识别将被用于预测的目的。作者还实现并测试了一种挖掘NDs的算法。在p邻域法中，为了识别未知值，发现的NDs是有用的。

数据质量概念、方法和技术

在本文中，作者系统地介绍了与数据质量相关的一系列问题。它描述了数据质量参数的细节，比如精度，完整性和一致性。关于它们在数据类型中的重要性的信息，如联邦数据，web数据或依赖时间的数据。不同的数据类别基于频率技术，核心数据质量研究的方法，相关领域，如数据挖掘，统计数据分析和机器学习。作者总结了解决质量问题的工具和实用方法的批判性比较。

使用匹配依赖项和匹配函数进行数据清理和查询应答

在本文中，作者提出了MDs作为数据清洗和实体解析的判定规则。质量约束是基于精确模型理论语义的成熟的陈述性约束。它在具有经典完整性约束的数据库中起着主要作用。在本文中，作者研究了它们与同一领域的相似关系的相互作用，从而引入了实例之间的部分支配顺序。它允许在信息内容的基础上比较它们，并应用于一组查询答案。在考虑所有概念的同时，作者为所提供的脏实例定义了干净实例的类。脏实例是预期的和可接受的实例，可以在强制匹配依赖项后获得。chase like用于定义干净的实例，这些实例依次强制执行MDs。这种追逐过程将提高属于支配秩序的信息内容。脏数据库发布的概念是查询的干净答案，它是由查询答案的信息内容形式的下限和上限组成的一对。作者还从支配顺序的角度研究了单调查询的内涵，以及如何将单调查询放宽为单调查询，从而在原有查询的基础上提供更多的信息。引入支配单调关系查询语言，利用域的格论结构，提出了一个开放的问题，在基于关系语言的公共关系和相似关系的查询松弛条件下，对信息不完整或部分有序域的查询数据库进行了探索。

信息集成中的自适应名称匹配

在本文中，作者指出，识别大约重复的数据库记录将引用同一个实体是信息集成的必要条件。然后作者比较和结合所描述的方法，也学习文本相似度量的名称匹配。

依赖推理的可行性和性能研究

在本文中，作者描述了函数依赖推断的实用性。虽然在数据库设计过程中需要一个工具来帮助指定逻辑依赖关系，但在自动数据库设计的情况下，这个问题就出现了。作者在本文中得出结论，对于实际的实例关系，频繁地实现依赖推理函数将导致可接受的交互响应时间。

用于数据清理的条件函数依赖关系

在这篇文章中，作者提到了最近的讽刺说，脏数据每年花费美国企业数十亿美元，并且还计算出，在一个数据仓库dw项目中，一个劳动密集型和复杂的过程占了30%-80%的开发时间。这些突出的原因是必须使用工具来清理数据，以自动检测和删除数据中的不一致和错误。本文介绍了CFDs，说明了CFDs可以将语义数据导向数据清洗的基础。为了将不一致识别为违反cfd，作者开发了基于SQL的技术。修复和一致的查询答案是这里主要关注的两个主题。修复(Repair)用于寻找与原数据库一致且与原数据库有细微差异的其他数据库。

在不增加复杂性的情况下增加CFDS的表达性

本文提出了一种扩展的价差合约，它是价差合约的延伸。在价差合约中，我们无法检测到价格上涨的不一致性，但在ecfd中，我们能够捕捉到实践中出现的不一致性。ecfd根据分离和不相等指定了语义上重新关联的值的模式。eCFD可以通过考虑在有限属性集上定义的关系模式来定义，并且对于每个属性，都表示域。采用批量检测算法查找eCFD中的违规集。此外，还开发了BATCH DETECT、INC DETECT等增量检测算法。这两种算法将产生SQL查询来查找违规。BATCHDETECT生成SQL查询和更新语句，用于检测模式约束违反。与BATCH DETECT算法类似，INC DETECT也生成SQL查询，查找违反模式约束的变化，并维护辅助关系，以便重用之前的计算。该INC DETECT算法旨在减少为发现违规而进行的不必要的重新计算。作者还建议今后的工作方向是开发消除eCFD违规和修复数据的算法，以及从数据样本中自动发现eCFD的有效方法。

使用条件扩展依赖关系

在本文中，作者引入了一类条件包含依赖(CINDs)，它是传统包含依赖(INDs)的扩展，通过强制组合相关数据值来实现。在本文中，作者证明了所提出的CINDs不仅用于清洗数据，而且还用于上下文模式匹配。本文的第一个贡献是提出了cind的概念。CIND被定义为由IND和模式表组成的一对，模式表强制组合语义相关的数据值。

第二个贡献是关于cind的推理技术。在这种情况下，首先必须检查cind是否一致而没有任何冲突。与cind相关的其他决策问题是隐含问题，用于决定一组cind是否包含另一组cind。pspace完备是传统ind的含义。第三个贡献是关于cind和cfd相互作用的调查。如果cind和cfd在一起，则本文还讨论了一致性问题。第四个贡献包含了一套算法，用于检查CFDs和cind的一致性。

作者得出的结论是，cind与cfd一起可能会导致清洁数据和寻找高质量模式匹配的有前途的工具。作者提出了未来的工作，通过考虑添加cind的无环性等假设，是否可以获得更好的复杂性结果。

在多个抽象级别上搜索依赖项

本文介绍了卷起依赖的概念，它是泛化层次结构对函数依赖的扩展。本文解决的问题是，对于具有多个属性的给定关系表，表中的每个属性都将从指定的域中获取值。域值列在概化中。问题是要确定具有高置信度的上卷依赖关系。卷起依赖关系(RUD)是相同基础关系模式的两个通用模式之间的重要关系。本文研究了RUDMINE问题，即发现支持度和置信度超过一定阈值的rup。结果还表明，该问题在模式大小上是np困难的，但在元组数量上是多项式困难的。作者提出了在多维数据库设计中使用rud的工作方向。

发现数据质量规则

在本文中，作者认为脏数据是一个严重的问题，它会导致企业做出错误的决策，不充分的日常运营，浪费时间和金钱。当需要保护数据的一致性和准确性的领域约束和业务规则引入时，脏数据就会产生。

在本文中，作者提出了一种新的数据驱动工具，可以在特定组织的数据质量管理过程中使用，建议各种可能的规则，并找到适用和不适用的记录。由于数据质量规则是上下文相关的，因此作者着重于上下文相关规则的发现。作者提出了一个数据驱动的工具，它可以在提供的数据实例上识别CFDs阈值，这在数据清理和强制语义数据不一致方面很有用。提出了一种搜索近似条件规则并找出这些规则的脏例外的算法。

使用基于文本相似性的查询集成没有公共域的异构数据库

在本文中，作者提到在很多数据库中包含Ã①Â′Â name constraintsÃ①Â′Â如个人姓名、地名等。在之前的工作中，假设局部内容可以通过归一化对齐到适当的全局域。但在某些情况下，这种假设并不成立。在识别时，如果两个名称常量相同，则需要详细的世界信息。在本文中，作者否定了全局域可以很容易地建立的假设，并通过分配以自然语言文本提供的名称来代替其他的假设。然后作者提出了一个叫做WHIRL的逻辑，它明确地解释了使用向量空间模型测量的局部名称的相似性。目前，数据集成系统使用领域特定规则来规范化实体名称，并使用这些名称的规范化版本作为键。

本文表明，与基于归一化的手工编码积分方案相比，WHIRL的相似连接精度更高。提出了分布式处理WHIRL的工作方向。

提高数据质量

在本文中，作者提出了一个基于cfd的数据质量改进框架。他证明了确定最优修理和增量发现最优修理的问题都是np完全的，并针对这两个问题开发了启发式算法。为了提高数据的准确性，提出了一种统计方法，该方法可以保证找到高于预定准确率的高置信度修复。

作者提出了利用cfd和包含依赖的一致性来高效地清理现实数据，研究从数据中自动识别有用的cfd的有效方法，并探索cfd之外的条件约束。

结论及未来工作

本文详细介绍了文献中流行的各种有效发现匹配依赖项的方法。匹配依赖关系(MDs)的概念最近被提出用于指定对象识别的匹配规则。与功能依赖关系(带条件)类似，MDs也可以应用于各种数据质量应用程序，例如检测完整性约束的违反。考虑了从给定的数据库实例中发现匹配依赖项的相似约束的问题。这次调查将促进信息挖掘领域的大量研究。

参考文献

宋绍旭，陈磊，“基于相似约束的匹配依赖项的高效发现”，数据与知识工程，2013。

S. Abiteboul, R. Hull, V. Vianu，数据库基础，Addison-Wesley, 1995。

R. Agrawal, T. Imielinski, A.N. Swami，大型数据库中项目集之间的关联规则挖掘，SIGMOD会议，1993，第207 - 216页。

R. Bassée, J. Wijsen，邻域依赖预测，PAKDD, 2001，第562-567页。

C. Batini, M. Scannapieco，数据质量:概念、方法和技术，以数据为中心的系统和应用，施普林格，2006。

L.E. Bertossi, S. Kolahi, L.V.S. Lakshmanan，基于匹配依赖和匹配函数的数据清洗和查询应答，ICDT,2011, pp. 268-279。

M. Bilenko, R.J. Mooney, W.W. Cohen, P. Ravikumar, S.E. Fienberg，信息集成中的自适应名称匹配，IEEE智能系统18(5)(2003)16-23。

杜德华，刘志刚，依赖推理的可行性和性能研究，中文信息学报，1989,pp. 635-641。

范伟，范伟杰，贾晓霞，基于条件函数依赖的数据清理方法，计算机工程学报，2007,pp. 746-755。

L. Bravo, W. Fan, F. Geerts, S. Ma，在不增加额外复杂性的情况下增加条件函数依赖的表达性，ICDE, 2008,pp。516 - 525。

范文伟，马世峰，陈建民，《条件依赖关系的扩展》，《计算机工程》，2007，第2期。

T. Calders, R.T. Ng, J. Wijsen，在多个抽象级别上搜索依赖关系，ACM数据库系统学报27(3)(2002)229-260。

蒋志强，刘志强，《数据质量规则的发现》，计算机科学进展(1)(2008)1166-1177。

W.W. Cohen，基于文本相似度的异构数据库集成，SIGMODConference, 1998, pp. 201-212。

丛国强，范文伟，贾晓霞，马生，数据质量的一致性与准确性，计算机工程，2007,pp. 315-326。

A.K. Elmagarmid, P.G. Ipeirotis, V.S. Verykios，重复记录检测:一个调查，IEEE知识与数据工程学报19(1)(2007)1 - 16。

范伟，《数据质量的相关性研究》，《计算机科学》，2008，第159-170页。

范文文，贾晓霞，李建军，马胜，记录匹配的动态约束，VLDB学报(2010)1-26。

范文伟，熊明明，条件函数依赖的发现，计算机工程学报，2009,pp. 1231-1234。

范文文，李建军，贾晓霞，马世生，记录匹配规则的推理，计算机工程，2009。

范伟，李建军，唐楠，于伟，记录匹配与数据修复的交互作用，计算机工程学报，2011,pp. 469-480。

范文伟，胡玉玉，刘建军，吴玉玉，带条件的传播函数依赖，物理学报1(1)(2008)391-407。

P.A. Flach, I. Savnik，数据库依赖发现:机器学习方法，人工智能通信12(3)(1999)139-160。

J. Gardezi, L.E. Bertossi, I. Kiringa，匹配任意属性值的依赖关系:语义、查询应答和完整性约束，LID, 2011, pp. 23-30。

C. Giannella, E.L. Robertson，关于函数依赖的近似度量，信息系统29(6)(2004)483-507。

L. Golab, H.J. Karloff, F. Korn, A. Saha, D. Srivastava，顺序依赖，ppvdb 2(1)(2009) 574-585。

L. Golab, H.J. Karloff, F. Korn, D. Srivastava, B. Yu，关于生成条件函数依赖的近最优场景，PVLDB 1(1)(2008) 376-390。

L. Gravano, P.G. Ipeirotis, N. Koudas, D. Srivastava，文本加入rdbms用于web数据集成，WWW, 2003，第90-101页。

Y. Huhtala, J. Kärkkäinen, P. Porkka, H. Toivonen，使用分区有效地发现函数和近似依赖，ICDE,1998, pp. 392-401。

Y. Huhtala, J. Kärkkäinen, P. Porkka, H. Toivonen, Tane:发现函数和近似依赖的有效算法，计算机

I.F. Ilyas, V. Markl, P.J. Haas, P. Brown, A. Aboulnaga，绳:相关性和软函数依赖的自动发现，SIGMOD会议，2004,pp. 647-658。

R.S. King, J.J. Legendre，关系数据库中函数和近似函数依赖的发现，JAMDS 7(1)(2003) 49-59。

J. Kivinen, H. Mannila，函数依赖关系的近似推断，理论计算机科学149(1)(1995)129-149。

N. Koudas, A. Saha, D. Srivastava, S. Venkatasubramanian，度量函数依赖，ICDE, 2009, pp. 1275-1278。

S. Kramer, B. Pfahringer，强部分决定的有效搜索，KDD, 1996，第371-374页。

S.E. Madnick, H. Zhu，通过有效使用数据语义提高数据质量，数据与知识工程59(2)(2006)460-475。

曼尼拉，K.-J。Räihä，关系数据库的设计，Addison-Wesley, 1992。

曼尼拉，K.-J。Räihä，从关系推断函数依赖的算法，数据与知识工程12(1)(1994)83-99。

王文杰，高维数据集的聚类算法，计算机工程，2000,pp。169 - 178。

G. Navarro，近似字符串匹配的导览，ACM计算调查33(1)(2001)31-88。

B. Pfahringer, S. Kramer，基于压缩的部分决定的评估，KDD, 1995, pp. 234-239。

T. Scheffer，寻找交易支持最优的关联规则，智能数据分析9(4)(2005)381-395。

J.C. Schlimmer，有效的诱导决定:一个完整和系统的搜索算法，使用最优剪枝，ICML, 1993, pp.284-290。

宋松，陈良，《匹配依赖关系的发现》，《管理科学》，2009,pp. 1421-1424。

宋，陈，差异依赖:推理和发现，ACM数据库系统学报36(4)(2011)。

宋山，陈林，于培生，基于数据空间的数据依赖关系研究，计算机工程学报，2011,pp. 470-481。

U. ul Hassan, S. O' riain, E. Curry，利用匹配依赖在链接数据应用中引导用户反馈，第九届网络信息集成国际研讨会论文集，IIWeb '12, ACM，纽约，纽约，美国，2012年，第5:1-5:6页。

王宏，刘荣，基于全功能依赖的隐私保护发布微数据，数据与知识工程，70(3)(2011)249-268。

C.M. Wyss, C. Giannella, E.L. Robertson, Fastfds:一种启发式驱动的深度优先算法，用于从关系扩展抽象中挖掘功能依赖，DaWaK, 2001，第101-110页。

b .波梅亚，尼基塔·玛丽·阿布莱特，v .莫哈那普利亚，S。Balamurugan，Ã¢Â ' Â，面向对象的安全医疗数据库系统建模方法，Ã¢Â ' Â，在国际计算机、通信和信号处理会议(IC3SP)与IETEstudents论坛和数字信息和无线通信协会，SDIWC,2011,pp.2-3

杨建民，杨建民，Ã¢Â′Â -基于改进分区算法的微数据发布隐私保护算法，计算机工程学报，27 (8):pp. 366 - 366, 2013年7月

BalamuruganShanmugam, VisalakshiPalaniswami, R.Santhya, R.S.Venkatesh Ã¢Â ' Â -功能依赖敏感数据发布的隐私保护策略:A State-of-the-Art-SurveyÃ¢Â ' Â，澳大利亚基础与应用科学杂志，8(15)2014年9月。

S.Balamurugan, P.Visalakshi, v.m.p abhakaran, s.c ranyaa, S.Sankaranarayanan，“云计算环境中NP-Hard工作流调度问题的解决策略”，《澳大利亚基础与应用科学杂志》，2014年10月8日，第15期。

Charanyaa, S等，，基于图的数据匿名化中的攻击预防和处理策略调查。计算机与通信工程学报，2013,29(3):379 - 379。

Charanyaa, S.等人，数据匿名化中保护图隐私方法的某些研究。计算机与通信工程，2016,30(3):379 - 379。

Charanyaa, S.等人提出了一种新的协同k度l -多样性t -紧密度模型，用于基于图的数据匿名化。计算机与通信工程学报，2014,29(3):344 - 344。

图形数据匿名化中基于知识的攻击检测策略。。计算机与通信工程，2014,34(2):1 - 7。

张晓明，陈晓明，等，基于词频的数据匿名化序列生成算法，计算机与通信工程，2(2):3033-3040,2014。

V.M.Prabhakaran,教授。Balamurugan, s.c aranyaa，“云医疗数据保护策略的若干研究”，《国际计算机与通信工程创新研究杂志》第2卷，第10期，2014年10月

V.M.Prabhakaran,教授。Balamurugan, s.c aranyaa，“远程虚拟机安全终身PHR的研究”，国际计算机与通信工程创新研究杂志第2卷，第10期，2014年10月

V.M.Prabhakaran,教授。Balamurugan, s.c aranyaa，“在云计算中保护个人医疗保健数据的隐私”，《国际科学、工程和技术高级研究杂志》第1卷，第2期，2014年10月

P.Andrew, J.Anish Kumar, R.Santhya，教授s。刘志刚，“移动数据对象隐私保护策略的演化研究”，《计算机与通信工程》，2(2):3033-3040,2014。

P.Andrew, J.Anish Kumar, R.Santhya，教授s。刘志刚，“移动数据对象安全的若干研究”，计算机与通信工程，2(2):3033-3040,2014。

P.Andrew, J.Anish Kumar, R.Santhya，教授s。Balamurugan, s.c aranyaa，“保护数据对象隐私的方法研究”，《科学、工程和技术国际高级研究杂志》第1卷，第2期，2014年10月

S.Jeevitha, R.Santhya，教授s。Balamurugan, s.c aranyaa，“在云计算中保护个人医疗保健数据的隐私”，《科学、工程和技术国际高级研究杂志》第1卷，第2期，2014年10月。

K.Deepika, P.Andrew, R.Santhya, S.Balamurugan, S.Charanyaa，“敏感数据保护方法的研究”，《国际先进科学研究杂志》第1卷，第4期，2014年12月。

K.Deepika, P.Andrew, R.Santhya, S.Balamurugan, S.Charanyaa，“数据匿名化方法的调查”，《国际科学、工程与技术高级研究杂志》第1卷，第4期，2014年12月。

S.Balamurugan, S.Charanyaa，“社交网络数据安全原理”，德国，ISBN: 978-3-659-61207- 7,2014

S.Balamurugan, S.Charanyaa，《云计算调度原理》，学者出版社，德国，ISBN: 978-3-639-66950- 3,2014

S.Balamurugan, S.Charanyaa，《数据库安全原理》，学者出版社，德国，ISBN: 978-3-639-76030- 9,2014

传记

R.Santhya和S.Latha目前正在攻读B.Tech。在印度泰米尔纳德邦哥印拜陀KalaignarKarunanidhi理工学院获得信息技术学位。他们的研究领域包括网络安全、云计算和数据库安全。

balamurugan教授分别于印度泰米尔纳德邦哥印拜陀市P.S.G.理工学院获得资讯科技学士学位，及于印度泰米尔纳德邦安娜大学获得资讯科技硕士学位。他目前正在印度泰米尔纳德邦的P.S.G.技术学院攻读信息技术博士学位。目前，他在国际期刊和IEEE/ Elsevier国际会议上发表了65篇论文。他目前在印度泰米尔纳德邦哥印拜陀市Kalaignar Karunanidhi理工学院信息技术系担任助理教授，隶属于印度泰米尔纳德邦安娜大学。他是国家一级学生。他是大学一级理工硕士。印度泰米尔纳德邦安娜大学的学期考试。他曾担任印度泰米尔纳德邦哥印拜陀市PSG理工学院信息技术系IT协会联合秘书。他连续3年获得所在机构颁发的最佳期刊发表金奖和奖状。他的一些专业活动包括两个会议的邀请会议主席。 He has guided 16 B.Tech projects and 2 M.Tech. projects. He has won a best paper award in International Conference. His areas of research interest accumulate in the areas of Data Privacy, Database Security, Object Modeling Techniques, and Cloud Computing. He is a life member of ISTE,CSI. He has authored a chapter in an International Book "Information Processing" published by I.K. International Publishing House Pvt. Ltd, New Delhi, India, 978-81-906942-4-7. He is the author of 3 books titled "Principles of Social Network Data Security", ISBN: 978-3-659-61207-7, "Principles of Scheduling in Cloud Computing" ISBN: 978-3-639-66950-3, and "Principles of Database Security", ISBN: 978-3-639-76030- 9.

S.Charanyaa获得了印度泰米尔纳德邦安娜大学金奈分校的信息技术学士学位和信息技术硕士学位。她是理工学院的金牌得主。学位项目。她在各种国际期刊和会议上发表了27篇文章。她在学校的一些杰出成就包括在10年级和12年级获得学校第一名。她曾在钦奈Larsen & Turbo Infotech担任软件工程师3年，在那里她被提升为高级软件工程师，并工作了2年。她曾在不同的垂直行业工作，并在许多地方工作，包括丹麦，阿姆斯特丹，处理各种各样的客户。她也是L&T 2012年度最佳团队球员奖的获得者。她的研究兴趣集中在数据库安全、隐私保护数据库、对象建模技术和云计算领域。著有《社会网络数据安全原理》(ISBN: 978-3-659-61207-7)、《云计算调度原理》(ISBN: 978-3-639-66950-3)和《数据库安全原理》(ISBN: 978-3-639-76030-9)三本书。