基于函数依赖图的设计关系数据库模式的综合算法

本文详细讨论了函数依赖图的原理及基于函数依赖图求解ＥＫＮＦ（基本关键字范式）的数据库模式的综合算法。它对于给定的一关系数据库的一组函数依赖产生相应的ＦＤ图；基于此ＦＤ图，删除该ＦＤ图中的冗余复合节点、多余复合节点和冗余完全弧；从而得到一个ＬＲ最小ＦＤ图覆盖；并由此得出一个属于ＥＫＮＦ的较好的关系数据库模式。本文所述综合算法的时间复杂度为多项式的，因而在实践中有重要的实用价值。     

确定Fmin的一个算法

构造了一个求解最小函数依赖集Fmin的计算机算法．该算法将求解Fmin的逻辑推理过程包装在一个C 函数之中，通过运行与此函数相配套的程序，可以快速、准确地获得与所给函数依赖集F等价的Fmin从而使求解Fmin的过程方便、快捷．     

标准函数依赖覆盖集及其求解算法

对函数依赖集进行优化数据库设计的重要环节。本文对数据库模式中函数依赖的标准函数依赖覆盖集进行了研究和对其内涵进行了分析,导出了求解标准函数依赖覆盖集算法,并给出了正确性证明。     

关系数据库的K-A图设计方法

一、引理由标识码与函数依赖的定义,以及由范式与最小复盖的定义可以引出以下两个推论:推论1:在一个完全函数依赖集 F 中,若各函数依赖都有相同的左部 K,则 K 一定是关系模式 R的一个标识码。其中 U=K_F~+,K_F~+为 K 关于 F 的闭包。推论2:设 F_(min)是函数依赖集 F 的最小复盖,则在 F_(min)中按相同左部合并各函数依赖所得的关系模式都属于3NF。     

基于XML最小覆盖算法的研究

提出了两个来自XML关键字的函数依赖的最小覆盖的计算算法。第一个算法需要花费指数级别的时间代价。第二个算法需要花费输入集合的多项式时间倍,此算法有效地计算来自XML关键字的函数依赖最小覆盖的算法。     

数据库中函数依赖集的泛系分析

本文从泛系分析出发对关系数据库理论中函数依赖集的闭包的结构进行了讨论。证明了在函数依赖集与函数依赖集的闭包之间存在着一个集合;函数依赖集的闭包可由该集合直接导出。本文的后半部分讨论了全体最小覆盖集的求解方法。     

利用函数依赖图寻找关系模式的候选码

寻找关系模式的候选码是数据库设计理论中的重要问题。本文利用图论的有关知识,先构造一个关系模式的函数依赖图,然后提出函数依赖与候选码的关系,并采用逆邻接表作为它的存贮结构,利用图的广度优先搜索技术,给出了具体寻找关系模式候选码的算法。     

约束数据库中的函数依赖公理系统与设计理论

约束数据模型作为一种新的数据模型正受到广泛关注。为了约束数据库的应用，需要研究它的设计。为此本文对约束数据库中的函数依赖给出定义，并提出函数依赖的公理系统，证明了它的有效性和完备性；在此基础上完成了约束数据库设计的核心工作：把约束关系模式分解为3NF或BCNF的算法。     

面向对象数据库中的数据依赖和规范化

从分析面向对象数据库中的数据依赖着手，提出对象函数依赖概念，它反映了面向对象数据库中对象标识符，复杂对象及集合类型的特点，在对象函数依赖基础上，提出了分解为基础为模式规范化方法，并且特别引入语义相关集的概念，最后，给出类模式分解的形式化定义并证明了类模式的任一分解都是无损分解。     

关系数据库中候选码的求解

寻找关系模式的候选码是数据库设计理论中的重要问题。通过对关系数据库规范化理论的研究,利用函数依赖和图论的有关知识,分别从属性闭包和函数依赖图的角度讨论了如何求解候选码,并给出了一些具体实例。     

基于属性预扫描的不确定性函数依赖挖掘

函数依赖是关系数据库和数据建模中所需的关键约束知识。在海量数据中挖掘函数依赖时为降低噪音干扰和提高效率,该文采用带有满意度函数依赖的概念及挖掘带有满意度函数依赖的算法(MFDD),对噪音进行测度与表达,并有效挖掘得到函数依赖最小集。利用对属性散列度的测度概念,在带有满意度函数依赖的理论框架内采用3条优化策略,实现了属性预扫描算法。结果表明:基于该算法可显著提高挖掘效率。     

基于内容相关的条件函数依赖的一致性清洗方法

基于条件函数依赖提出了一种内容相关的条件函数依赖,并给出基于内容相关的条件函数依赖的一致性清洗方法.通过分析条件函数依赖之间的关系,将相关联的条件函数依赖合并组成内容相关的条件函数依赖.内容相关的条件函数依赖可以检测多条件值下的数据一致性问题并提供可用于一致性修复的参考值.同时,提出了一种一致性修复的代价模型.模型参考内容相关的条件函数依赖对应元组的实际情况进行修复,实现代价最优,同时保证数据一致性.通过在两组真实数据集上进行试验测试,证明提出的基于内容相关的条件函数依赖的一致性清洗方法能够准确地检测数据的一致性问题并加以修复.     

模糊关系数据库系统中的函数依赖与多值依赖

用模糊关系数据模型来描述不分明的模糊数据是关系数据库理论发展中的一个重要的新课题。本文用模糊等价关系及其隶属函数来描述模糊函数依赖与多值依赖,看出经典数据依赖是模糊数据依赖的特例。并且证明相应于Armstrong公理的一套模糊数据依赖的推理规则是正确、完备的。     

Functional Dependencies and Its Axiom System in XML

According to the analysis of existing complicated functional dependencies constraint, we conclude the conditions of defining functional dependency in XML, and then we introduce the concept of the node value equality. A new path language and a new definition of functional dependencies in XML （XFD） are proposed XFD includes the relative XFD and the absolute XFD, in which absolute key and relative key are the particular cases. We focus on the logical implication and the closure problems, and propose a group of inference rules. Finally, some proofs of the correctness and completeness are given. XFD is powerful on expressing functional dependencies in XML causing data redundancy, and has a complete axiom system.     

基于Vague关系数据模型的数据依赖

基于提出的Vague关系数据模型和Vague集之间的相似度量,研究了Vague关系数据库中的数据依赖问题,给出了Vague函数依赖(VFDs)和Vague多值依赖(VMVDs)的定义及其相应的推理规则.该规则类似于经典关系数据库中函数依赖和多值依赖的Armstrong公理系统,称之为Vague公理系统.并对Vague公理系统的有效性和完备性进行了证明.同时还给出了VFDs满意度的概念及计算VFDs满意度的公式.     

Fast Computation of Sparse Data Cubes with Constraints

For a data cube there are always constraints between dimensions or among attributes in a dimension,such as functional dependencies.We introduce the problem that when there are functional dependencies,how to use them to speed up the computation of sparse data cubes.A new algorithm CFD (Computation by Functional Dependencies) is presented to satisfy this demand.CFD determines the order of dimensions by considering cardinalities of dimensions and functional dependencies between dimensions together,thus reduce the number of partitions for such dimensions.CFD also combines partitioning from bottom to up and aggregate computation from top to bottom to speed up the computation further.CFD can efficiently compute a data cube with hierarchies in a di-mension from the smallest granularity to the coarsest one.     

XML的函数依赖

为了表达引起数据冗余的XML函数依赖,研究了XML中存在的复杂的多种形式的函数依赖约束,提出了一种DTD的路径语言,对于导航和定位XML文档的内容具有较强的表达能力.提出了一套XML模式及文档的形式化描述方法,进而提出了一种XML函数依赖(XFD)的定义.与以前的XML函数依赖的定义进行比较,展示了XFD可以表达更多的XML上存在的函数依赖,可以概括以前的基于路径表达式定义的XML函数依赖的约束能力.     

XML函数依赖

函数依赖在关系数据库中起着基本的作用,尤其是用在完整性约束和数据库设计方面。近年来已定义了XML上的函数依赖。本文采用了一种新的定义方式,即在树元组上定义函数依赖,同时给出了函数依赖的推理规则。     

依赖推导算法的研究

本文根据函数依赖成立的条件，给出了在关系ｒ中单属性左部属性集的求解算法，进而出了在给定关系中成立的函数依赖集的一个覆盖。     

Boyce—Codd范式的判定与分解

给定关系模式Ｒ和函数依赖集Ｆ，当Ｘ为Ｒ的一个真子集时，判定Ｘ关于Ｆ是否为Ｂｏｙｃｅ－Ｃｏｄｄ范式（以下简记为ＢＣＮＦ）是ＮＰ完全的，这一问题的难点在于Ｆ在Ｘ上投影的计算，本文给出了计算函数依赖集投影的一个实用算法，将其用于ＢＣＮＦ的判定，并在此基础上建立了ＢＣＮＦ的一个无损分解算法。