欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

范式理论的程序设计(七)

程序员文章站 2022-05-08 11:29:20
...

关于数据库范式理论的程序设计 - NormalFormUtils

这里我使用的工具类全部都是使用接口,public interface NormalFormUtils extends FcUtils 是关于范式的判定、分解的工具。这里要介绍的内容和代码都非常多

Utils工具的继承关系

范式理论的程序设计(七)

NormalFormUtils接口

这部分内容由于之前写的代码涉及到其他的内容,所以这里重写了几次,做了很多的删减,后面或许会再补充其他内容。

BCNF的判定

1. 算法描述
范式理论的程序设计(七)

2. 算法代码

    /**
     * 描述:找到一个Ri中违反BCNF的函数依赖
     * @param fds 函数依赖集
     * @param attributeRi R分解后的Ri属性集
     * @return FunctionalDependency或者null
     */
    default FunctionalDependency violateBCNF(Collection<FunctionalDependency> fds, String attributeRi) {
        //(1)计算Ri中属性的每一个子集(即字符的组合) α,确保α+(在Pattern下的属性闭包)
        //计算Ri属性的所有子集
        final Collection<String> combinations = combination(attributeRi);
        for (CharSequence combination : combinations) {
            //计算α+
            final String closure = calcClosure(combination.toString(), fds);

            //(2)满足则Ri属于BCNF的条件
            //α+要么不含 (Ri-α)的任何属性
            final boolean empty = isEmpty(intersect(closure, except(attributeRi, combination)).toString());

            //要么包含Ri的所有属性
            final boolean contains = contains(closure, attributeRi);

            if (empty || contains) continue;
            //一定存在α → (α+ - α) ∩ Ri 违反BCNF
            final FunctionalDependency fd = new FunctionalDependency(combination, intersect(except(closure, combination), attributeRi));
            System.err.println("[" + attributeRi + "]中" + fd + "违反BCNF...................");
            return fd;
        }
        return null;
    }

BCNF的分解

1. 算法描述
如果直接将关系模式R按照该算法进行分解,那么该算法与计算F+没什么区别。所以该算法应该用于R分解为多个Ri后,如果有些Ri不满足BCNF再用该算法分解。后面会有利用正则覆盖Fc对R进行3NF分解,分解得到的多个Ri。如果要的到BCNF,这时候就可以使用该算法对这些Ri进行分解。
范式理论的程序设计(七)

2. 算法代码

    /**
     * 描述:R分解为多个BCNF
     * @param fds 函数依赖F
     * @param attributeR R的属性集
     * @return Set<String> 满足BCNF的Ri.....
     */
    default Set<String> decomposeBCNF(Collection<FunctionalDependency> fds, String attributeR) {
        //result = {R}
        final Set<String> decomposeBCNF = new HashSet<>();
        decomposeBCNF.add(attributeR);

        boolean done = true;
        while (done) {
            //用于标记本次迭代中是否有违反BCNF的Ri,(没有则为null,会使得done为false)
            String loop = null;

            for (String Ri : decomposeBCNF) {
                //找到违反BCNF的函数依赖
                final FunctionalDependency violate = violateBCNF(fds, Ri);
                if (violate != null) {
                    //如果Ri上确实存在,不属于BCNF函数依赖
                    //将其分解为两个Ri,(α ∪ β)和(Ri - β)
                    final String[] strings = decomposeRi(Ri, violate);
                    decomposeBCNF.add(strings[0]);
                    decomposeBCNF.add(strings[1]);
                    System.err.println(Ri + "违反BCNF,分解为" + strings[0] + "和" + strings[1]);
                    loop = Ri;
                    break;
                }
            }
            if (loop != null) decomposeBCNF.remove(loop);
            done = (loop != null);
        }
        //移除冗余关系
        deDuplicateRi(decomposeBCNF);
        return decomposeBCNF;
    }
    /**
     * 描述:将不满足BCNF的R分解R0...Ri
     * @param attributeRi Ri的属性集
     * @param fd 违反BCNF的函数依赖
     * @return 分解后的集合
     */
    default String[] decomposeRi(String attributeRi, FunctionalDependency fd) {
        //分解成两个
        final String[] decomposeAfter = new String[2];
        //第一个:(α ∪ β)
        decomposeAfter[0] = union(fd.getLeft(), fd.getRight()).toString();
        //第二个:(Ri - (β-α))
        decomposeAfter[1] = except(attributeRi, except(fd.getRight(), fd.getLeft())).toString();
        return decomposeAfter;
    }
    /**
     * 描述:3NF、BCNF分解中,移除属性集相互包含中较小的属性集
     *      例如: 属性有 CA, ABC,就移除CA
     * @param Ris 属性集
     */
    default void deDuplicateRi(Collection<String> Ris) {
        //将分解后的Ri...排序,转为数组存储
        final String[] array = Ris.stream()
                .sorted(Comparator.comparingInt(String::length))
                .toArray(String[]::new);
        //判断属性集大的是否包含比起属性集更小的集合
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (contains(array[i], array[j])) {
                    //若包含,直接异常更小的那个Ri
                    Ris.remove(array[j]);
                    System.out.println("合并[" + array[i] + "]与[" + array[j] + "]为[" + array[i] + "]");
                }
            }
        }
    }

3NF的分解

1. 算法描述

范式理论的程序设计(七)
2. 算法代码

    /**
     * 描述:分解为3NF
     * @param fds Collection<FunctionalDependency> 依赖集
     * @param attributeR R的属性集
     * @return    Set<String> 分解后满足3NF的Ri集合
     */
    default Set<String> decompose3NF(Collection<FunctionalDependency> fds, String attributeR) {
        //计算其Fc
        final Collection<FunctionalDependency> Fc = canonicalCover(fds);
        //根据Fc分解:Fc的每一个函数依赖称为一个Pattern(模式)Ri;
        final Set<String> decompose3NF = decomposeFDS(Fc);
        final String attributeFD = attributionSequence(fds);
        //如果每个Ri都不包含R的候选键,那么增加一个Ri(=R的任一候选键)
        //(1)attributeFD中不存在的属性
        final String noExist = except(attributeR, attributeFD).toString();
        if (!isEmpty(noExist)) {
            final String candidateKey = calcCandidateKey(attributeR, fds).get(0);
            decompose3NF.add(candidateKey);
            //System.out.println("noExist" + "属性不存在,添加候选键[" + candidateKey + "]");
        }
        //移除冗余关系
        deDuplicateRi(decompose3NF);
        return decompose3NF;
    }
    /**
     * 描述:分解FDS
     * @param fds Collection<FunctionalDependency> 函数依赖集
     * @return Collection<String> 函数依赖集分解得到的模式R0...Ri
     */
    default Set<String> decomposeFDS(Collection<FunctionalDependency> fds) {
        final Set<String> Ris = new HashSet<>();
        fds.forEach(fd -> Ris.add(fd.attributions()));
        return Ris;
    }

根据Fc(或3NF分解),再BCNF的分解

1. 算法描述
先计算正则覆盖Fc,将Fc转化为一个3NF分解,再将该3NF中违反BCNFRi继续分解。

2. 算法代码

    /**
     * 描述:R分解为多个BCNF
     * @param fds 函数依赖F
     * @param attributeR R的属性集
     * @return Set<String> 满足BCNF的Ri.....
     */
    default Set<String> decomposeBCNFByFc(Collection<FunctionalDependency> fds, String attributeR) {
        final Set<String> decomposeBCNF = decompose3NF(fds, attributeR);
        boolean done = true;
        while (done) {
            //用于标记本次迭代中是否有违反BCNF的Ri,(没有则为null,会使得done为false)
            String loop = null;
            for (String Ri : decomposeBCNF) {
                //找到违反BCNF的函数依赖
                final FunctionalDependency violate = violateBCNF(fds, Ri);
                if (violate != null) {
                    //如果Ri上确实存在,不属于BCNF函数依赖
                    //将其分解为两个Ri,(α ∪ β)和(Ri - β)
                    final String[] strings = decomposeRi(Ri, violate);
                    decomposeBCNF.add(strings[0]);
                    decomposeBCNF.add(strings[1]);
                    System.err.println(Ri + "违反BCNF,分解为" + strings[0] + "和" + strings[1]);
                    loop = Ri;
                    break;
                }
            }
            if (loop != null) decomposeBCNF.remove(loop);
            done = (loop != null);
        }
        deDuplicateRi(decomposeBCNF);
        return decomposeBCNF;
    }

测试用例(Junit)

import com.ruoxing.dbs.bean.FunctionalDependency;
import com.ruoxing.dbs.util.NormalFormUtils;
import org.junit.Test;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

/**
 * 描述:NormalFormUtils
 */
public class Test6 implements NormalFormUtils {
}

1. 用例

    @Test
    public void test01() {
        Set<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("AB","D"));
        F.add(new FunctionalDependency("C","DE"));
        F.add(new FunctionalDependency("BC","EG"));
        F.add(new FunctionalDependency("AD","BG"));
        //Fc=[AB→D, AD→BG, BC→G, C→DE]
        System.out.println("------------------------------");
        final Set<String> decompose3NF = decompose3NF(F, "ABCDEG");
        System.out.println("3NF分解=" + decompose3NF);
        System.out.println("------------------------------");
        final Set<String> decomposeBCNF = decomposeBCNF(F, "ABCDEG");
        System.out.println("BCNF分解=" + decomposeBCNF);
    }

范式理论的程序设计(七)

2. 结果

    @Test
    public void test02() {
        Set<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("BC","D"));
        F.add(new FunctionalDependency("CD","AE"));
        F.add(new FunctionalDependency("AG","CE"));
        F.add(new FunctionalDependency("AB","GE"));
        System.out.println("------------------------------");
        final Set<String> decompose3NF = decompose3NF(F, "ABCDEG");
        System.out.println("3NF分解=" + decompose3NF);
        System.out.println("------------------------------");
        //final Set<String> decomposeBCNF = decomposeBCNF(F, "ABCDEG");
        final Set<String> decomposeBCNF = decomposeBCNFByFc(F, "ABCDEG");
        System.out.println("BCNF分解=" + decomposeBCNF);
    }

范式理论的程序设计(七)