所以再过几个小时就要考《数据库系统概论》了，看书看到一半手痒了，就把书上的两个算法用C++实现了一遍，这两个算法是

• 求属性集X在U上的函数依赖集F的闭包
• 求给定函数依赖集F的最小覆盖

详细的算法都写在注释里了～

//
//  main.cpp
//  数据库系统概论——函数依赖
//
//  Created by Ryza 2016/6/29.
//  Copyright © 2016[data deleted]. All rights reserved.
//

#include <iostream>
#include <iterator>
#include <map>
#include <string>
#include <set>
#include <vector>

using namespace std;

/**
 *  @brief  求属性集X在U上的函数依赖集F的闭包
 *
 *  @param  X 属性集X
 *  @param  U 属性集U
 *  @param  F 函数依赖集F
 *
 *  @return 属性集X在U上的函数依赖集F的闭包
 */
set<string> f_closure(const set<string>& X, const set<string>& U, const map<set<string>, vector<set<string>>>& F);

/**
 *  @brief  求给定函数依赖集F的最小覆盖
 *
 *  @param  U 属性集U
 *  @param  F 函数依赖集F
 *
 *  @return 函数依赖集F的最小覆盖
 */
map<set<string>, vector<set<string>>> f_minimal(const set<string>& U, const map<set<string>,vector<set<string>>>& F);

int main(int argc, const char * argv[]) {
#pragma mark
#pragma mark - 求属性集X在U上的函数依赖集F的闭包

    // U = {A, B, C, D, E}
    set<string> U{"A", "B", "C", "D", "E"};

    // F = {AB->C, B->D, C->E, EC->B, AC->B}
    map<set<string>, vector<set<string>>> F{
        {{"A", "B"}, {{"C"}}},
        {{"B"},      {{"D"}}},
        {{"C"},      {{"E"}}},
        {{"E", "C"}, {{"B"}}},
        {{"A", "C"}, {{"B"}}}
    };

    // X = AB
    set<string> X{"A", "B"};

    // 求X = AB在U上的函数依赖集F的闭包
    set<string> closure = f_closure(X, U, F);
    copy(closure.cbegin(), closure.cend(), ostream_iterator<string>(cout, " "));
    cout<<'\n';

#pragma mark
#pragma mark - 求给定函数依赖集F的最小覆盖

    // S<U, F>
    // U = {Sno, Sdept, Mname, Cno, Grade}
    U = {"Sno", "Sdept", "Mname", "Cno", "Grade"};

    // F = {
    //      Sno -> Sdept, Sno -> Mname,
    //      Sdept -> Mname,
    //      (Sno, Cno) -> Grade,
    //      (Sno, Sdept) -> Sdept
    // }
    F = {
            {{"Sno"},         {{"Sdept"}, {"Mname"}}},
            {{"Sdept"},       {{"Mname"}}},
            {{"Sno", "Cno"},  {{"Grade"}}},
            {{"Sno", "Sdept"},{{"Sdept"}}},
    };
    map<set<string>, vector<set<string>>> minimal = f_minimal(U, F);
    for_each(minimal.cbegin(), minimal.cend(), [&](const pair<set<string>, vector<set<string>>>& fm) {
        const set<string>& X = fm.first;
        const vector<set<string>>& Y = fm.second;

        for_each(Y.cbegin(), Y.cend(), [&](const set<string>& Yi) {
            copy(X.cbegin(), X.cend(), ostream_iterator<string>(cout, " "));
            cout<<"-> "<<*Yi.begin()<<'\n';
        });
    });
    return 0;
}

set<string> f_closure(const set<string>& X, const set<string>& U, const map<set<string>, vector<set<string>>>& F) {
    // 1. 令X(0) = X
    vector<set<string>> closure = {X};

    bool find = true;
    while (find) {
        // 2. 求B, 这里B = {A|(∃V)(∃W)((V->W ∈ F) ∧ (V ⊆ X(i)) ∧ (A ∈ W))}
        set<string> B;
        const set<string>& Xi = closure.back();
        for_each(F.cbegin(), F.cend(), [&](const pair<set<string>, vector<set<string>>>& FD) {
            const set<string>& V = FD.first;
            const vector<set<string>>& W = FD.second;

            if (all_of(V.cbegin(), V.cend(), [&](const string& v) -> bool {
                if (Xi.find(v) == Xi.end()) return false;
                return true;
            })) {
                for_each(W.cbegin(), W.cend(), [&](const set<string>& Wi) {
                    copy(Wi.cbegin(), Wi.cend(), inserter(B, B.begin()));
                });
            }
        });

        // 3. X(i+1) = B ∪ X(i)
        set<string> Xi1 = Xi;
        copy(B.cbegin(), B.cend(), inserter(Xi1, Xi1.begin()));

        // 4. 判断X(i+1) = X(i)
        if (Xi1 == Xi || Xi == U) {
            // 5. 如果X(i+1) 与 X(i)相等或X(i) = U
            //    则X(i)就是X在U上的函数依赖集F的闭包, 算法终止
            find = false;
        } else {
            // 6. 若X(i+1) 与 X(i)不相等
            //    则返回第二步
            closure.emplace_back(Xi1);
        }
    }
    return closure.back();
}


map<set<string>, vector<set<string>>> f_minimal(const set<string>& U, const map<set<string>,vector<set<string>>>& F) {
    map<set<string>, vector<set<string>>> minimal;
    // 1. 逐一检查F中各函数依赖FD(i): X->Y
    for_each(F.cbegin(), F.cend(), [&](const pair<set<string>, vector<set<string>>>& FD) {
        const set<string>& X = FD.first;
        const vector<set<string>>& Y = FD.second;

        for_each(Y.cbegin(), Y.cend(), [&](const set<string>& y) {
            vector<set<string>>& p = minimal[X];
            // 若Y=A(1)A(2)...A(k), k>=2
            if (y.size() > 1) {
                // 则用{X->A(j)|j=1, 2, ..., k}来取代X->Y
                for_each(y.cbegin(), y.cend(), [&](const string& Ai) {
                    p.push_back({Ai});
                });
            } else {
                p.push_back({*y.begin()});
            }
        });
    });

    // 2. 逐一检查F中各函数依赖FD(i): X->A
    map<set<string>, vector<set<string>>> check = minimal;
    for_each(check.cbegin(), check.cend(), [&](const pair<set<string>, vector<set<string>>>& FD) {
        const set<string>& X = FD.first;
        const vector<set<string>>& A = FD.second;
        vector<set<string>> t = A;

        for_each(A.cbegin(), A.cend(), [&](const set<string>& Ai) {
            for (vector<set<string>>::iterator iter = t.begin(); iter != t.end(); iter++) {
                if (*iter == Ai) {
                    t.erase(iter);

                    // 令G=F-{X->A}
                    map<set<string>, vector<set<string>>> G = minimal;
                    G[X] = t;

                    // 若A ∈ X在G上的闭包
                    set<string> XG = f_closure(X, U, G);
                    if (any_of(XG.cbegin(), XG.cend(), [&](const string& xg) -> bool {
                        if (xg == *Ai.begin()) return true;
                        return false;
                    })) {
                        // 则从F中去除此函数依赖
                        vector<set<string>>& p = minimal[X];
                        p.erase(find(p.begin(), p.end(), Ai));
                        if (p.size() == 0) {
                            minimal.erase(minimal.find(X));
                        }
                    }

                    t.insert(iter, Ai);
                }
            }
        });
    });

    // 3. 逐一取出F中各函数依赖FD(i): X->A
    check = minimal;
    for_each(check.cbegin(), check.cend(), [&](const pair<set<string>, vector<set<string>>>& FD) {
        const set<string>& X = FD.first;
        const vector<set<string>>& A = FD.second;

        // 若X=B(1)B(2)...B(m), m>=2
        if (X.size() > 1) {
            set<string> R = X;

            // 逐一考查B(i), i=1, 2, ..., m
            for_each(X.cbegin(), X.cend(), [&](const string& Bm) {
                set<string> B = X;
                auto bt = B.find(Bm);
                B.erase(bt);

                // 若A ∈ (X - B(i))在F上的闭包
                set<string> XG = f_closure(B, U, minimal);
                if (any_of(XG.cbegin(), XG.cend(), [&](const string& xg) -> bool {
                    if (xg == Bm) return true;
                    return false;
                })) {
                    // 则以X - B(i)取代X
                    minimal.erase(minimal.find(R));
                    R.erase(R.find(Bm));
                    minimal[R] = A;
                }
            });
        }
    });

    return minimal;
}
 

Reference:

• [1]王珊，萨师煊编著.数据库系统概论 第5版[M].北京：高等教育出版社.2014. p190-p194