c++ - 表示函数依赖的数据结构

Question

我在考虑如何将函数依赖表示为数据结构。

(数据库关系模式的)功能依赖将一组属性映射到一组属性。例如。在 {A, B} -> {C, D} 中，属性 C 和 D 在功能上依赖于 A 和 B。

这里我可以想到四种可能的情况:

1. {A} -> {B}(两个单一属性)
2. {A, B} -> {C}(一组属性意味着单个属性)
3. {A} -> {B, C}(单个属性表示一组属性)
4. {A, B} -> {C, D}(一组属性隐含一组属性)

我的第一个方法是一个简单的两个成员类:

class attribute
{
    string name;
    set<attribute*> dependent_on;
}

这适用于像 (1) 这样的函数依赖，但不适用于 (2) - (4) - 我认为。事实上，我可以分解 (3)，但我看不出有什么方法可以用这样的类来表示 (2) 和 (4)。

我必须保留 C 和 D 在功能上依赖于 A 和 B 的信息，所以我必须创建一个类，如 attributegroup 其中一组属性映射到一组属性。例如:

class attributegroup
{
    set<attribute*> members;
    set<attribute*> dependent_on;
}

所以实际上我可以将单个属性简单地表示为只有一个成员的 attributegroup。但我认为这不是最好的方法。

感谢任何帮助/想法:)

Answer 1

我不会在属性中存储依赖关系:

include <iostream>
#include <map>
#include <vector>

struct Attribute;
typedef std::vector<Attribute> Attributes;
struct Attribute {
    char name;
    operator Attributes () const { return Attributes{ 1, *this }; }
};

inline bool operator < (const Attribute& a, const Attribute& b) {
    return a.name < b.name;
}

inline bool operator < (const Attributes& a, const Attributes& b) {
    return std::lexicographical_compare(
        a.begin(), a.end(),
        b.begin(), b.end());
}

inline std::ostream& operator << (std::ostream& stream, const Attributes& attributes) {
    for(const auto& a: attributes) {
        std::cout << a.name;
    }
    return stream;
}

typedef std::multimap<Attributes, Attributes> AttributeDependencies;
typedef AttributeDependencies::value_type AttributeDependency;

int main(int argc, const char* argv[]) {
    Attribute a {'A'};
    Attribute b {'B'};
    Attribute c {'C'};
    Attribute d {'D'};

    AttributeDependencies dpendencies;
    dpendencies.insert(AttributeDependency(a, b));
    dpendencies.insert(AttributeDependency(Attributes{a, b}, c));
    dpendencies.insert(AttributeDependency(a, Attributes{b, c}));
    dpendencies.insert(AttributeDependency(Attributes{a, b}, Attributes{c, d}));
    for(const auto& d: dpendencies) {
        std::cout << '{' << d.first << "} -> {" << d.second << "}\n";
    }
    return 0;
}

注意:std::map 可能是正确的容器，但 std::multimap 适合示例数据。