Decomposition Condition and Algorithm of β-Acyclic in Mixed Dependency Environments Based on Line Graph
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [8]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    β-Acyclic database scheme has a number of desirable properties, but most former researches about β-acyclic are based on graph theory, without consideration on other canonical properties of database. With the concept of mixed dependency basis, this paper defines the concepts of strict conflict-free and extended strict conflict-free, and proves that decomposition satisfies lossless join, keeps dependency, β-acyclic and 4NF if and only if it is extended strict conflict-free in the mixed environment. Based on this, the paper gives the algorithm for judging strict conflict-free and β-acyclic decomposition in mixed environment, then shows that the complexity of the algorithm is linear using an example based on line graph. This conclusion can directly guide real database designing.

    Reference
    [1]Beeri, C., Fagin, R., Maier, D., et al. On the desirability of acyclic database schemes. Journal of ACM, 1983,30(3):479~513.
    [2]Fagin, R. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of ACM, 1983,30(3):514~550.
    [3]Hao Zhong-xiao, Yao Chun-long, Gao Yan. Research on the theoried concerning the join hypergraph(Ⅰ): basic concepts. Computer Research and Development, 1997,34(supplement):259~262 (in Chinese).
    [4]Hao Zhong-xiao, Gao Yan, Yao Chun-long. Research on the theoried concerning the join hypergraph(ⅠⅠ): basic theory on α-acyclic hypergraph decompositions. Computer Research and Development, 1997,34(supplement):263~270 (in Chinese).
    [5]Katsuno, H. An extension of conflict-free multivalued dependency sets. ACM Transactions on Database System, 1984,9(2):309~326.
    [6]Cheung, T.Y., Zhu, Y.Z. Recognzing different types of beta-cycles in a database scheme. Theoretical Computer Science, 1991,81(3):295~304
    [3]郝忠孝,姚春龙,高岩.连接超图的有关理论研究(Ⅰ):基本概念.计算机研究与发展,1997,34(增刊):259~262.
    [4]郝忠孝,高岩,姚春龙.连接超图的有关理论研究(ⅠⅠ):无α环分解的基本理论.计算机研究与发展,1997,34(增刊):263~270.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

刘文远,郝忠孝.基于线图的无β环混合依赖分解条件及算法.软件学报,2000,11(12):1656-1659

Copy
Share
Article Metrics
  • Abstract:3016
  • PDF: 4628
  • HTML: 0
  • Cited by: 0
History
  • Received:May 18,1999
  • Revised:September 20,1999
You are the first2045219Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063