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

这里我使用的工具类全部都是使用接口，public interface FcUtils extends ClosureUtils是关于正则覆盖的计算实现算法。

Utils工具的继承关系

FcUtils接口

import com.ruoxing.dbs.bean.FunctionalDependency;
import java.util.Collection;
import java.util.HashSet;
/** * @author :ruoxing * @type :Interface * @date :2018-05-25 01:03 星期五 * @description :正则覆盖Fc的实现 */
public interface FcUtils extends ClosureUtils {
}

正则覆盖（canonical cover）

1. Fc的定义描述

2. Fc的算法描述

3. Fc的代码描述

    /** * 描述:函数依赖集合Collection<FunctionalDependency>的正则覆盖 * @param fds Collection<FunctionalDependency> * @return Collection<FunctionalDependency> Fc */
    default Collection<FunctionalDependency> canonicalCover(Collection<FunctionalDependency> fds) {
        final Collection<FunctionalDependency> fc = unionLeft(fds);
        //左边无关检测
        removeLeft(fc);
        //System.out.println("左边无关检测:" + fc);

        //右边无关检测
        removeRight(fc);
        //System.out.println("右边无关检测:" + fc);

        //去重复
        return unionLeft(fc);
    }

4. 测试代码

canonicalCover（）具体实现

1. 左边无关检测

    /** * 描述:检测移除Fc中依赖的左边,的无关属性(递归实现) * @param fds Fc */
    default void removeLeft(Collection<FunctionalDependency> fds) {
        //获取依赖中左边属性个数大于1的依赖
        final FunctionalDependency[] array = fds
                .stream()
                .filter(fd -> fd.getLeft().length() > 1)
                .toArray(FunctionalDependency[]::new);
        if (array.length == 0) return;

        for (FunctionalDependency fd : array) {
            final CharSequence sequence = fd.getLeft();
            for (int i = 0; i < sequence.length(); i++) {
                //如果发现某个属性无关,将该属于从该依赖的左边移除
                if (extraneousAttributeLeft(fds, fd, sequence.charAt(i))) {
                    fd.setLeft(except(fd.getLeft(), "" + sequence.charAt(i)));
                    removeLeft(fds);
                    return;
                }
            }
        }
    }

2. 右边无关检测

    /** * 描述:检测移除Fc中依赖的右边,的无关属性(递归实现) * @param fds Fc */
    default void removeRight(Collection<FunctionalDependency> fds) {
        final FunctionalDependency[] array = fds.toArray(new FunctionalDependency[0]);
        for (FunctionalDependency fd : array) {
            final CharSequence sequence = fd.getRight();
            for (int i = 0; i < sequence.length(); i++) {
                if (extraneousAttributeRight(fds, fd, sequence.charAt(i))) {
                    //如果右边只有一个属性且无关,直接移除该依赖
                    if (fd.getRight().length() == 1) {
                        fds.remove(fd);
                    } else {
                        //如果有多个属性的其中一个无关,则在右边中移除该属性
                        fd.setRight(except(fd.getRight(), "" + sequence.charAt(i)));
                    }
                    removeRight(fds);
                    return;
                }
            }
        }
    }

3. 合并左边相同的函数依赖

/** * 描述:用于正则覆盖中,合并左边相同的依赖 * @param fds Collection<FunctionalDependency> * @return Collection<FunctionalDependency> */
    default Collection<FunctionalDependency> unionLeft(Collection<FunctionalDependency> fds) {
        final Collection<FunctionalDependency> fc = new HashSet<>();
        //先合并左边相同的依赖
        for (FunctionalDependency fd : fds) {
            final FunctionalDependency[] include = includeLeft(fc, fd);
            if (include == null) {
                fc.add(fd);
            } else {
                fc.remove(include[0]);
                fc.add(include[1]);
                System.out.println("将合并["+ fd +"]" + "与[" + include[0]+ "]为[" + include[1]+ "]");
            }
        }
        return fc;
    }

removeLeft（），removeRight（）移除无关属性和includeLeft（）检查左部依赖的实现

1. 属性A是否在α→β右部无关

    /** * 描述:A是否是无关属性 * @param fds 依赖集F * @param fd 依赖α→β * @param A 属性A∈β * @return 是否无关 */
    default boolean extraneousAttributeRight(Collection<FunctionalDependency> fds,
                                             FunctionalDependency fd,
                                             Character A) {

        //获取F' = (F - {α→β}) ∪ {α → (β-A)}
        Collection<FunctionalDependency> dependencies = new HashSet<>(fds);
        dependencies.remove(fd);
        dependencies.add(new FunctionalDependency(fd.getLeft(), except(fd.getRight(), "" + A)));

        //在F'下计算α+
        final String closure = calcClosure(fd.getLeft().toString(), dependencies);
        //如果闭包包含A,则indexOf >= 0
        final int indexOf = closure.indexOf(A);
        final boolean extraneous = indexOf >= 0;

        //输出测试信息
        if (extraneous) System.out.println(A + "在[" + fd + "]的右边是无关的....");
        return extraneous;
    }

2. 属性A是否在α→β左部无关

    /** * 描述:A是否是无关属性 * @param fds 依赖集F * @param fd 依赖α→β * @param A 属性A∈α * @return 是否无关 */
    default boolean extraneousAttributeLeft(Collection<FunctionalDependency> fds,
                                            FunctionalDependency fd,
                                            Character A) {
        //如果α是单属性,则一定是相关的
        if (fd.getLeft().length() <= 1) return false;
        //γ = α-{A},
        final CharSequence except = except(fd.getLeft(), "" + A);
        //在F下求γ+
        final String closure = calcClosure(except.toString(), fds);
        //闭包是否包含β的所有属性
        final boolean extraneous = contains(closure, fd.getRight());
        //包含则A无关

        //输出无关信息
        if (extraneous) System.out.println(A + "在[" + fd + "]的左边是无关的....");
        return extraneous;
    }

3. 发现是否存在左边相同的依赖

    /** * 描述:用于发现是否存在左边相同的依赖 * @param fds Collection<FunctionalDependency> * @return FunctionalDependency[] */
    default FunctionalDependency[] includeLeft(Collection<FunctionalDependency> fds, FunctionalDependency dependency) {
        for (FunctionalDependency fd : fds) {
            if (fd.getLeft().toString().equals(dependency.getLeft().toString())) {
                return new FunctionalDependency[]{fd, union(fd, dependency)};
            }
        }
        return null;
    }

测试（Junit）

import com.ruoxing.dbs.bean.FunctionalDependency;
import com.ruoxing.dbs.util.FcUtils;
import org.junit.Test;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;
/** 1. 描述：测试ClosureUtils */
public class Test5 implements FcUtils {
}

1. 用例，《数据库系统概念》P195

    @Test
    public void test01() {
        final Collection<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("A","BC"));
        F.add(new FunctionalDependency("B","C"));
        F.add(new FunctionalDependency("A","B"));
        F.add(new FunctionalDependency("AB","C"));
        System.out.println("正则覆盖Fc=" + canonicalCover(F));//正则覆盖Fc=[A→B, B→C]
    }

2. 用例，《数据库系统概念》P207,习题8.7

    @Test
    public void test02() {
        final Collection<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("A","BC"));
        F.add(new FunctionalDependency("CD","E"));
        F.add(new FunctionalDependency("B","D"));
        F.add(new FunctionalDependency("E","A"));
        System.out.println("正则覆盖Fc=" + canonicalCover(F));//正则覆盖Fc=[A→BC, B→D, CD→E, E→A]
    }

3. 用例，《数据库系统概念》P209,习题8.29

    @Test
    public void test03() {
        Set<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("A","BCD"));
        F.add(new FunctionalDependency("BC","DE"));
        F.add(new FunctionalDependency("B","D"));
        F.add(new FunctionalDependency("D","A"));
        final Collection<FunctionalDependency> Fc = canonicalCover(F);
        System.out.println("正则覆盖:");
        System.out.println(Fc);
        /* C在[BC→DE]的右边是无关的.... D在[B→DE]的右边是无关的.... D在[A→BCD]的右边是无关的.... 将合并[B→D]与[B→E]为[B→DE] 正则覆盖: [A→BC, D→A, B→DE] */
    }

4. 用例，Exam（计算Fc与将R分解成3NF基本相同）

    @Test
    public void test04() {
        Set<FunctionalDependency> F = new HashSet<>();
        F.add(new FunctionalDependency("A","D"));
        F.add(new FunctionalDependency("CG","BD"));
        F.add(new FunctionalDependency("DE","AG"));
        F.add(new FunctionalDependency("BD","CE"));
        final Collection<FunctionalDependency> Fc = canonicalCover(F);
        System.out.print("正则覆盖:");
        System.out.println(Fc);
        //正则覆盖:[BD→CE, A→D, DE→AG, CG→BD]
        //Fc=F
    }

5. 用例，Exam（计算Fc与将R分解成3NF基本相同）

    @Test
    public void test05() {
        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"));
        final Collection<FunctionalDependency> Fc = canonicalCover(F);
        System.out.print("正则覆盖:");
        System.out.println(Fc);
        /* E在[AB→EG]的右边是无关的.... 正则覆盖:[BC→D, CD→AE, AB→G, AG→CE] */
    }

5. 有兴趣可以自行测试其他用例，测试用例越多越能避免特殊情况，如果有测试用例不正确的非常希望能够在评论区说明