首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 156 毫秒
1.
FD集最优覆盖多项式时间求解算法的研究   总被引:1,自引:0,他引:1  
本文在详细分析了FD集的最小覆盖和最优覆盖的结构特性基础上,提出并讨论了一个最小覆盖成为最优覆盖的条件及一个最优覆盖珠属性集构成的特点,相应的引理和定理。最后给出一个求FD集最优覆盖的多项式时间算法。  相似文献   

2.
杨智应 《现代计算机》1997,(5):12-14,33
本文主要给出了关系数据模型中两个重要概念属性集闭包及FD集闭包的若干性质及其相互关系。  相似文献   

3.
LR最小替换集求解算法研究   总被引:2,自引:0,他引:2  
文中对D.Maier提出的关于关系数据库中的LR最小集的结构进行了分析,提出了一个比“LR最小集”更为简化的FD集的覆盖-LR最小替换集。给出了一个求LR最小替换集的多项式时间算法。修正了D.Maier在其文中给出的一个FD集为最优覆盖的必要条件。  相似文献   

4.
本文引入了广义FD路和外部闭包的概念,将它们应用于函数依赖集的无冗余覆盖计算,有效地减少了计算的闭包个数.并在此基础上提出了一个新的3NF合成算法,将常用的3NF合成算法中的2次无冗余覆盖计算合并为1次,显著地减少了计算闭包总个数.  相似文献   

5.
建立了基于覆盖理论的模糊S-粗糙集模型,并讨论其性质。在覆盖单向S-粗集x的最小描述的基础上,给出了x的最大描述的定义。给出了覆盖模糊S-粗集上 、下近似算子定义,讨论了算子的基本性质,证明了覆盖S-粗糙集模型下所有模糊集的下近似构成一个模糊拓扑,并得到模糊单向S-粗集X相对于覆盖单向S-粗集和覆盖约简单向S-粗集的上下近似分别相等。  相似文献   

6.
本文定义了基于覆盖广义粗集的模糊性度量,给出一种度量表示并讨论此种模糊性度量的性质;定义了正负域覆盖广义粗集的模糊度,并通过一个具体实例给出直观解释。  相似文献   

7.
本文讨论了空值环境下的NFD-NMVD混合强保持依赖基的定义和求解算法,并讨论了算法的有效性完备性,给出了NFD-NMVD混合推导公理,强保持集属性闭包的求解算法,从而解决了NFD-NMVD混合情况下的强保持逻辑蕴涵问题。  相似文献   

8.
文中基于属性集关于函数依赖集的闭包,并采用模式矩阵,给出了一个从函数依赖集综合出3NF模式的算法。该算法不用Armstrong公理进行烦琐的推导,与Bernstein算法相比,较为简单且易于实现。  相似文献   

9.
数据库模式分解为满足P3及无α环的条件   总被引:4,自引:0,他引:4  
文中讨论了当某一个属于FD集F的最小归并依赖集具有某些性质时,属于FD集F的任意最小归并依赖集同样具有相同性质;还给出了广义左部冲突、广义右部冲突等概念。在此基础上给出并证明了无内部冲突的数据库模式分解为满足P3及无α环性质的充要条件,和有内部冲突的数据库模式分解为满足P3及无α环性质的必要条件。  相似文献   

10.
正负域覆盖广义粗集及其运算公理化   总被引:3,自引:1,他引:3  
针对覆盖广义粗集边界过于粗糙及运算公理化定义难以得到的不足,论文提出了正负域覆盖广义粗集的概念,讨论了覆盖正负域的性质。证明了正负域覆盖广义粗集对不明确的概念可给出更清晰的描述。通过引进覆盖等价的概念,给出了给定论域上任意集在不同覆盖下具有相同正负域覆盖广义粗集的充要条件。最后给出了正负域运算的公理化定义。  相似文献   

11.
一种求解全部候选关键字的快速替换算法   总被引:4,自引:0,他引:4  
本文通过分析文献(2,3)中所提出的求解关系模式全部候选关键字的替换算法,找出了它们的共同缺陷,即算法每搜索一趟产生的后继候选关键字太少,要想求出全部候选关键字,需经过很多趟的搜索。在此基础上,提出了对替换算法从减少每一趟搜索中需要检查的FD个数和增加每一趟搜索产生的后继候选关键字两方面进行改进的基本思想。然后,以EF(X)为研究对象,讨论了实现这种改进思想的具体方法,并给出了相应的快速替换算法及  相似文献   

12.
Although there is a rich body of research on dependency theory, only few results concerning simple functional dependencies (FDs) have been published. In this paper, the following key results regarding simple FDs are shown. First, given an acyclic set F of simple FDs there exists exactly one canonical cover for F. Second, this uniquely determined canonical cover can be computed via transitive reduction. Third, it is shown how a uniquely determined canonical cover can be fixed in case of arbitrary simple FDs via transitive reduction.  相似文献   

13.
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.  相似文献   

14.
一个具有多时间粒度时态函数依赖集的成员籍算法   总被引:4,自引:3,他引:4  
对于具有函数依赖(FDs)约束的传统关系数据库规范化理论来说,判定一个FD是否被给定FD集所逻辑蕴涵(即成员籍问题)是非常重要的,这有助于设计有效的模式分解算法,而对于具有时态函数依赖(TFDs)约束的时态模式来说,由于多时间粒度的使用使成员籍问题的解决变得更加复杂,由此讨论了时态类型的一些特性,并提出了有限决定集的概念,基于求得属性的有限决定集,对每一个元素的左部属性集是单一属性的TFD集给出了一个有效的成员籍算法和相关的正确性证明。  相似文献   

15.
Incomplete relations are relations which contain null values, whose meaning is “value is at present unknown”. A functional dependency (FD) is weakly satisfied in an incomplete relation if there exists a possible world of this relation in which the FD is satisfied in the standard way. Additivity is the property of equivalence of weak satisfaction of a set of FDs, say F, in an incomplete relation with the individual weak satisfaction of each member of F in the said relation. It is well known that satisfaction of FDs is not additive. The problem that arises is: under what conditions is weak satisfaction of FDs additive. We solve this problem by introducing a syntactic subclass of FDs, called monodependent FDs, which informally means that for each attribute, say A, there is a unique FD that functionally determines A, and in addition only trivial cycles involving A arise between any two FDs one of which functionally determines A. We show that weak satisfaction of FDs is additive if and only if the set F of FDs is monodependent and that monodependence can be checked in time polynomial in the size of F. Received: 8 December 1993 / 9 November 1995  相似文献   

16.
具有全序时态类型集时态函数依赖集的研究   总被引:19,自引:0,他引:19  
姚春龙  郝忠孝 《软件学报》2003,14(2):247-252
好的数据库逻辑设计目标是消除数据冗余以及插入、删除和更新异常.对于时态数据库,可以通过具有多时间粒度的时态函数依赖(TFDs)约束对时态数模式进行规范化.但是由于时间维的引入和多时间粒度的使用而给数据库设计带来巨大的复杂性.一般来说,系统所能处理的和相当多的应用所涉及到的时态类型集满足全序关系,并且具有全序时态类型集的TFD集的推导规则与传统函数依赖(FDs)的Armstrong公理有着紧密的联系.通过分析TFDs与FDs之间存在的联系,利用传统FD集的相应算法,提出了成员籍、有限属性闭包等TFD集的一些重要算法.这些算法是时态数据库进一步规范化的基础.  相似文献   

17.
Two phenomena regarding succintness in dependency systems are given. In the first, a minimum system of FDs can be induced by a much smaller (log size) system of FDs over a larger set of attributes. In the second, a minimum system of FDs can be induced by a much smaller (again log size) system of FDs and MVDs over the same set of attributes.  相似文献   

18.
A database is C-Armstrong for a given set of constraints in a class C if it satisfies every constraint of the set and violates every constraint in C not implied by the set. Therefore, Armstrong databases are test data that perfectly illustrate the current perceptions about the semantics of a schema. We extend the existing theory of Armstrong relations to a toolbox of Armstrong tables. That is, we investigate structural and computational properties of Armstrong tables for the class of functional dependencies (FDs) over SQL tables. Relations are special instances of SQL tables with no duplicate rows and no null value occurrences. While FDs do not enjoy Armstrong tables, the combined class of standard FDs and NOT NULL constraints does enjoy Armstrong tables. The problem of finding an Armstrong table is shown to be precisely exponential for this combined class. However, we establish an algorithm that computes Armstrong tables with a size at most quadratic in that of a minimum-sized Armstrong table. Our resulting toolbox of Armstrong tables can be applied by data engineers to concisely visualize constraints on SQL data. Such support can lead to designs that guarantee efficient data management in practice.  相似文献   

19.
基于最大相关块的关系模式全部主属性的一种解法   总被引:1,自引:1,他引:0  
本文是把关系模式中的函依赖集进行划分,对应的属性集合构成一个相关块,再对每个相关块求其主属性,最终给出求全部主属性的多项式时间的一种算法。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号