函数依赖图的理论及应用

本文提出函数依赖图的概念和理论,并重点应用它对关系模式候选关键字的求解问题进行了深入而系统的讨论,解决了单属性情况下候选关键字的求解问题,得到了若干新的结论。     

Matlab在求候选关键字的替换算法中的应用

在关系模式分解和规范化过程中,候选关键字的确定具有重要意义。针对该问题利用Matlab对求给定关系模式R（u,F）全部候选关键字的替换算法进行了实现,测试结果表明,给出的Matlab函数代码简洁、运行速度较快,运行结果正确、直观且易于理解。     

求关系模式所有最小基数候选关键字的一种多项式算法

本文深入分析了最小基数候选关键字在关系模式中的结构特征,提出了化简独立复合环、独立简单环、化简双部属性函数依赖图等概念.在此基础上,给出了求一个关系模式所有最小基数候选关键字集的多项式算法.     

关系模式的BCNF分解的一种新方法

传统的关系模式的BCNF分解算法必须判断“一个关系模式是否为BCNF”,该判断是一个NP-完全问题,因此传统算法缺乏实用性.本文避免这一判断,给出一个关系模式的BCNF分解的新算法,它的时间复杂性是O(kn~2)级的,其中n为模式中的属性个数,K为产生的模式个数.     

候选关键字的求解算法

本文利用关系数据库设计理论,深入研究了候选关键字与函数依赖的关系,得到了求解候选关键字的规律并提出了具体求解算法。文中有关定理拓展了文献[1]、[2]中的有关理论。     

求关系模式全部候选关键字理论和算法

本文研究了候选关键字之间的关联,定义了它们之间的等价关系,开发了直接导出和间接导出候选关键字的几个定理和从一个候选关键字导出所有候选关键字算法,并证明了它的正确性和完备性。     

计算关系数据库模式的候选关键字的一个有效算法

给出计算关系数据库模式R的候选关键字的一个有效算法,算法利用函数依赖中的属性“排列”去决定哪些是主要的,有用的;哪些属性不可被考虑,从而找出R的候选关键字。     

关系规范化中的3NF范式和BCNF范式

关系模式需符合一定的规范化要求，才能避免建立数据库时可能出现的异常现象。本文着重介绍了第三范式（3NF）与BOYCE－CODD范式（BCNF）两者之间的关系，证明了BCNF范式比3NF范式更为严格。     

与或图数据库的可达算法和寻根算法

与或图数据库是利用与或图描述数据库的关系模式 ,从而建立起新的一套数据库理论。这种数据库理论采用图论作为数学基础 ,将可达算法、搜索算法和分块算法引入关系数据库 ,来解决规范化算法中关键字求解和依赖蕴涵的问题。该文提出了利用宽度搜索、深度搜索、分块搜索和启发式搜索四种搜索算法判断依赖蕴涵问题 ,以及利用生成子图的方法求解候选关键字的问题。最后进一步证明了这些算法在复杂度上比传统算法更加优越。由此可见与或图数据库的算法更加高效直观易于编程 ,还为图论和人工智能与数据库的结合提供了可能     

关系数据库规范化应用研究

不满足BCNF的关系模式是由于需求分析中的关系冗余引起的,不满足4NF的关系模式所导致的数据冗余是可以接受的,不满足5NF的关系模式导致的异常只在使用视图时出现,所以,实际应用中关系模式满足3NF即可.     

Boyce—Codd范式的判定与分解

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

在左边是单属性的函数依赖集中寻找关系模式候选码的算法

寻找关系模式的候选码是对关系进行规范化的重要步骤。各种参考资料虽然在寻找方面介绍了各种方法,但没有给出算法的实现。本文给出利用有向图的知识寻找一个关系模式的所有候选码的算法。     

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

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

基于超图的BCNF的判定算法

利用超图来表示关系模式．定义了直接决定因素、推导．讨论了直接决定因素的性质．在此基础上给出了利用超图判定给定的关系模式是否属于ＢＣＮＦ的新算法．     

New Public-Key Cryptosystem Based on the Morphism of Polynomials Problem

During the last two decades, there has been intensive and fast development in Multivariate Public Key Cryptography(MPKC), which is considered to be an important candidate for post-quantum cryptography. However,it is universally regarded as a difficult task, as in the Knapsack cryptosystems, to design a secure MPKC scheme(especially an encryption scheme) employing the existing trapdoor construction. In this paper, we propose a new key-exchange scheme and an MPKC scheme based on the Morphism of Polynomials(MP) problem. The security of the proposed schemes is provably reducible to the conjectured intractability of a new difficult problem,namely the Decisional Multivariate Diffie-Hellman(DMDH) problem derived from the MP problem. The proposed key agreement is one of several non-number-theory-based protocols, and is a candidate for use in the post-quantum era. More importantly, by slightly modifying the protocol, we offer an original approach to designing a secure MPKC scheme. Furthermore, the proposed encryption scheme achieves a good tradeoff between security and efficiency,and seems competitive with traditional MPKC schemes.     

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

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

一种用于求解主属性的矩阵分析法

在关系数据库规范化理论中，求解后选关键字和主属性一直是一个棘手的问题。就这类问题的子类给出了一种通过依赖矩阵求出全部记属性的方法，进而得出主关键字。     

A new certificateless public key encryption scheme

Certificateless public key cryptography （CL-PKC） enjoys the advantage of identity based cryptography without suffering from its inherent key escrow problem. In this paper, a new efficient certificateless public key encryption scheme is proposed and its security can reach chosen-ciphertext （CCA2） secure in the random oracle model assuming the CDH and p-BDHI problem are difficult. A comparison shows that the efficiency of the proposed scheme is better than all known paring-based certificateless public key encryption schemes in the random oracle model.