CODEWITHSUNDEEP
c++algorithmdata-structures
SX.
SX.

Reputation: 91

Data structure to represent functional dependencies

I'm thinking about how to represent functional dependencies in as a data structure.

A functional depdendency (of a relation schema of a database) maps a set of attributes to a set of attributes. E.g. in {A, B} -> {C, D} the attributes C and D are functional dependent on A and B.

I can think of four possible cases here:

  1. {A} -> {B} (two single attributes)
  2. {A, B} -> {C} (a set of attributes implies a single attribute)
  3. {A} -> {B, C} (a single attribute implies a set of attributes)
  4. {A, B} -> {C, D} (a set of attributes implies a set of attributes)

My first approach was a simple two member class:

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

This would work with functional dependencies like (1) but not with (2) - (4) - I think. I could decompose (3), indeed, but I see no way to represent (2) and (4) with such a class.

I have to keep the information that C and D are functional dependent on A and B, so I would have to make a class like attributegroup where a set of attributes is mapped to a set of attributes. E.g.:

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

So actually I could represent a single attribute simply as an attributegroup with only one member. But I do not think that this is the best way to do this.

Any help/thoughts appreciated :)

Upvotes: 1

Views: 980

Answers (1)

user2249683
user2249683

Reputation:

I would not store dependencies in an attribute:

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;
}

Note: A std::map might be the right container, but std::multimap fits the example data.

Upvotes: 1

Related Questions