分布式大数据不一致性检测

关系数据库中可能存在数据不一致性现象,关系数据库数据质量的一个主要问题是存在违反函数依赖情况.为找出不一致数据,需要进行函数依赖冲突检测.集中式数据库中可以通过SQL技术检测不一致情况,尽管检测效率不高;而分布式环境下不一致性检测更富有挑战性,不仅需要考虑数据的迁移,检测任务如何分配也是一个难题.在大数据背景下,上述问题更加突出.提出了一种分布式环境单函数依赖不一致性检测方法,给出了不一致性检测响应时间代价模型.为减少数据迁移量和响应时间,基于等价类对待检测数据进行预处理.由于分布式环境不一致性检测问题为NP-hard问题,多项式时间内难以得到最优解,给出了代价模型的多项式时间3/2-近似最优解.提出了一种分布式环境多函数依赖不一致性检测方法,基于最小集合覆盖理论,通过一次数据遍历,对多个函数依赖进行并行批检测,同时考虑检测过程中的负载均衡等问题.在真实和人工数据集上的实验表明：相对于传统的检测方法以及基于Hadoop的Naïve方法,所提出的检测方法检测效率有明显的提升,且扩展性能良好.     

基于内容感知发现XML条件函数依赖

针对XML函数依赖(XFD)不能充分检测XML局部数据源语义上的数据不一致,借鉴关系数据库中条件函数依赖(CFD)的概念,并根据XML自身结构和约束特性,提出了基于内容感知发现(CAD)XML条件函数依赖(XCFD),CAD使用隐藏在数据值中的内容发现局部XML文档的XCFDs,检测异构数据源中数据一致性,提高数据的质量,并给出了详细的算法,同时引入修剪规则集减少搜索点阵和候选的XCFD的数量,提高算法的效率,使得XCFD无冗余、最小化.通过案例研究表明,基于CAD方法发现的XCFD比现有XFD发现更多的函数依赖和语义约束.     

分布式数据库中冲突检测技术研究

数据冲突是数据库中数据质量中心问题之一。在集中式数据库中,基于SQL技术可以有效地检测出违背给定条件函数依赖集的元组。然而,当数据库中数据被水平或垂直划分且分布在不同站点时,检测数据冲突将面临更大的挑战,常常需要将数据从一个站点移动到另外一个站点。提出了分布式数据库中条件函数依赖冲突检测算法,该算法不仅能有效地检测出水平划分数据中条件函数依赖冲突,而且能减少数据传输。实验结果证实算法是有效的。     

一个基于粗糙集的XML函数依赖发现算法

数据依赖是数据库的一个重要概念。函数依赖是一种常见的数据依赖关系,是数据语义的重要组成部分。随着XML文档的大量出现,这一概念被引入到XML的领域中。本文在约束限制范围的基础上,给出了XML函数依赖的定义。引入粗糙集解决XML数据不完整的特点,给出XML函数依赖的判定定理。并且提出了一个发现XML文档中最小非平凡函数依赖的算法。该算法基于一致集的概念,通过不可分辨关系划分元组集减少求一致集的运算次数,使用逐层求精的算法来计算最小非平凡XML函数依赖集的左部。通过该算法得到的XML函数依赖的语义信息对数据存储模式设计、查询优化和更新异常检查来说是十分重要的。     

基于近邻传播聚类和TANE算法的高校数据中函数依赖的发现

针对高校实际数据质量检测过程中数据集存在缺失值以及发现的函数依赖个数较少且不准确的问题，提出了一种结合近邻传播（AP）聚类算法和TANE算法的高校函数依赖发现方法（APTANE）。首先，对数据集中的中文字段进行列剖析，将中文字段值用对应的数值来表示；其次，使用AP聚类算法对数据集中的缺失值进行填补；最后，使用TANE算法从处理好的数据集中自动发现出满足非平凡、最小要求的函数依赖。实验结果表明，在使用AP聚类算法对真实的高校数据集进行修复之后，相比于直接使用函数依赖自动发现算法，发现的函数依赖个数增加到了80个，经过缺失值填补后所发现的函数依赖在表示字段间关联关系时也更加准确，减少了领域专家的工作量，提升了高校数据所拥有数据的质量。     

基于水利普查数据的函数依赖关系算法

条件函数依赖(Conditional Functional Dependencies,CFDs)在数据库一致性的检测上应用广泛。为检测水利普查数据的一致性,本文针对水利普查数据特点,将普查数据分为度量、维度2部分,并对度量数据进行聚类,引入条件函数依赖的概念,同时重新定义条件函数依赖,改进发现条件函数依赖的算法(即CTANE算法);以水库工程数据为例,验证本文改进的算法能准确高效地发现水利普查数据中的条件函数依赖,为检测数据一致性做好准备。     

一种发现函数依赖集的方法及应用

介绍了一种发现最小函数依赖集的方法.这种方法基于一致集的概念,根据一致集导出最大集及其补集,然后生成最小非平凡函数依赖集.通过使用带状划分数据库减少求一致集的运算次数,使用逐层求精的算法来计算最小非平凡函数依赖集的左部.其结果可用于数据库的重新组织和设计、属性约简、聚类、关联规则提取等知识发现工作中.     

分布式环境下约束性关联规则的快速挖掘

研究人员针对单机环境提出了约束性关联规则的挖掘算法,但它们不适用于分布式环境.为此本文讨论分布式环境下约束性关联规则的快速挖掘技术,提出一种基于分布式环境的约束性关联规则快速挖掘算法DCAR,其中包括局部约束性频繁项目集挖掘算法MLFC和全局约束性频繁项目集挖掘算法MGFC.该算法根据布尔约束条件产生向导集,采用一种新的候选项集生成函数Reorder-gen,该函数通过向导集高效地产生分布式环境中满足约束条件的、数量较少且完备的候选项集,并且求解全局约束性频繁项集过程中,传送局部候选项集支持数的通信量为O(n),从而提高了算法的挖掘效率.将本文提出的算法加以实现,实验结果表明DCAR算法高效可行,其效率大约是DMA-IC算法的2-3倍.     

基于常量条件函数依赖的冲突消解算法

目前绝大部分冲突消解方法都是基于迭代计算数据源可靠度和事实可信度的机制。当数据源较少时,数据源的可靠度难于进行评估,仅凭投票来消解冲突往往会造成较大误差。针对数据源较少时的冲突消解问题,提出基于常量条件函数依赖的冲突消解算法。根据多个数据源之间的冲突,找出冲突匹配对及对应的冲突候选值集合。考虑常量条件函数依赖中具体到部分实例子集的约束关系,将常量条件函数依赖集作为先验知识,通过判断候选值是否符合常量条件函数依赖来选择正确的候选值,避免了错误数据比例较大时直接投票选择产生的误差。通过两个真实数据集上的对比实验验证了上述算法的有效性。     

一种分布式全局频繁闭项目集快速挖掘更新算法

在数据挖掘研究中,频繁闭项目集挖掘成为重要的研究方向.目前已有的频繁闭项目集挖掘算法主要针对单机环境,有关分布式环境下的全局频繁闭项目集挖掘算法的研究尚不多见.针对无共享体系结构数据水平分布的情况,提出了一种分布式快速挖掘全局频繁闭项目集增量式更新算法,算法通过对各节点候选频繁项目集进行预处理,有效地降低网络通信量,提高全局频繁闭项目集挖掘算法的效率,该算法充分利用前次挖掘结果来发现新的全局频繁闭项目集,具有较高的效率.理论分析和实验结果表明算法是有效的.     

基于条件函数依赖的数据库一致性检测研究

条件函数依赖是函数依赖在语义上的扩充,可以应用于数据清洗工作,在数据库一致性的修复上应用广泛。讨论了条件函数依赖的相关语义规则,重点研究了基于条件函数依赖对违反数据库一致性元组的检测工作,并引入置信度评价机制,对相关的检测规则进行了改进。改进后的检测方法在基于多个函数依赖的检测中显示出了优越性,使得检测工作更为精简,检测标准更加明确。     

XML函数依赖研究综述

函数依赖作为数据库规范化的基础在关系理论中起着重要的作用。近年来，XML得到广泛应用并已成为互联网上数据传输和交换的标准。由于XML半结构化的特性，使得如何定义XML函数依赖使其具有更强的描述能力，以及如何解决相应的逻辑蕴涵问题成为当今学术界所面临的挑战。针对这些问题，系统地描述了目前关于XML函数依赖的研究现状，特别是把分析的重点放在如何定义函数依赖、判断其蕴涵关系以及从XML文档中发现函数依赖等问题上。最后讨论了诸如类型化函数依赖关系等一些相关的研究方向。     

Approximate dependencies in database systems

Functional dependencies are the most commonly used approach for capturing real-word integrity constraints which are to be reflected in a database. There are, however, many useful kinds of constraints, especially approximate ones, that cannot be represented correctly by functional dependencies and therefore are enforced via programs which update the database, if they are enforced at all. This tends to make such constraints invisible since they are not an explicit part of the database, increasing maintenance problems and the likelihood of inconsistencies. We propose a new approach, cluster dependencies, as a way to enforce approximate dependencies. By treating equality as a fuzzy concept and defining appropriate similarity measures, it is possible to represent a broad range of approximate constraints directly in the database by storing and accessing cluster definitions. We discuss different interpretations of cluster dependencies and describe the additional data structures needed to enforce them. We also contrast them with an existing approach, fuzzy functional dependencies, which are much more limited in the kind of approximate constraints they can represent.     

Mining functional dependencies from data

In this paper, we propose an efficient rule discovery algorithm, called FD_Mine, for mining functional dependencies from data. By exploiting Armstrong’s Axioms for functional dependencies, we identify equivalences among attributes, which can be used to reduce both the size of the dataset and the number of functional dependencies to be checked. We first describe four effective pruning rules that reduce the size of the search space. In particular, the number of functional dependencies to be checked is reduced by skipping the search for FDs that are logically implied by already discovered FDs. Then, we present the FD_Mine algorithm, which incorporates the four pruning rules into the mining process. We prove the correctness of FD_Mine, that is, we show that the pruning does not lead to the loss of useful information. We report the results of a series of experiments. These experiments show that the proposed algorithm is effective on 15 UCI datasets and synthetic data.     

Closure via functional dependence simplification

In this paper, a method for computing the closure of a set of attributes according to a specification of functional dependencies of the relational model is described. The main feature of this method is that it computes the closure using solely the inference system of the SL _FD logic. For the first time, logic is used in the design of automated deduction methods to solve the closure problem. The strong link between the SL _FD logic and the closure algorithm is presented and an SL _FD simplification paradigm emerges as the key element of our method. In addition, the soundness and completeness of the closure algorithm are shown. Our method has linear complexity, as the classical closure algorithms, and it has all the advantages provided by the use of logic. We have empirically compared our algorithm with the Diederich and Milton classical algorithm. This experiment reveals the best behaviour of our method which shows a significant improvement in the average speed.     

The theory of functional and subset dependencies over relational expressions

A formal system for reasoning about functional dependencies (FDs) and subset dependencies (SDs) defined over relational expressions is described. An FD e:X → Y indicates that Y is functionally dependent on X in the relation denoted by expression e; an SD e ? f indicates that the relation denoted by e is a subset of that denoted by f. The system is shown to be sound and complete by resorting to the analytic tableaux method. Applications of the system include the problem of determining if a constraint of a subschema is implied by the constraints of the base schema and the development of database design methodologies similar to normalization.     

Functional dependencies among Boolean dependencies

In this paper, we consider functional dependencies among Boolean dependencies (BDs, for short). Armstrong relations are defined for BDs (called BD-Armstrong relations). For BDs, two necessary and sufficient conditions for the existence of BD-Armstrong relations are given. A necessary and sufficient condition for the existence of Armstrong relations for functional dependencies (FDs, for short) is given, which in some sense is more convenient than the condition given in [3]. We give an algorithm that solves the problem of deciding if two BDs imply the same set of functional dependencies. If the BDs are given in perfect disjunctive normal form, then the algorithm requires only polynomial time. Although Mannila and Räihä have shown that for some relations exponential time is needed for computing any cover of the set of FDs defined in this relation, as a consequence, we show that the problem of deciding if two relations satisfy the same set of FDs can be solved in polynomial time. Another consequence is a new correspondence of the families of functional dependencies to the families of Sperner systems. By this correspondence, the estimate of the number of databases given previously in [6] is improved. It is shown that there is a one-to-one correspondence between the closure of the FDs that hold in a BD and its so-calledbasic cover. As applications of basic covers, we obtain a representation of a key, the family of minimal keys and a representation of canonical covers.This research was supported by the Hungarian Foundation for Scientific Research, Grant Nos. OTKA 2575, 2149.