Implementa gli algoritmi visti a lezione e condividi il tuo codice 🧪

[CuriousCI]

Un buon esercizio può essere quello di provare a implementare con il tuo linguaggio preferito gli algoritmi visti a lezione! Condividi il tuo codice in questa discussione usando ``` per indicare un blocco di codice

```linguaggio
qui ci va il codice!
```

[CuriousCI]

Intanto pubblico le implementazioni pulite che sono riuscito a scrivere in maniera pulita. Ho implementato tutti gli algoritmi visti a lezione, ma devo sistemare il codice per la looseless-join e per la decomposizione 👀

use std::collections::{BTreeSet, HashMap};

pub type Attribute = char;
pub type Set<T> = BTreeSet<T>;
pub type Tuple<T> = HashMap<Attribute, T>;
pub type Schema = Set<Attribute>;
pub type Decomposition = Set<Schema>;
pub type Dependency = (Schema, Schema);

#[macro_export]
macro_rules! set {
    () => { Set::new() };
    ($($x:expr),+ $(,)?) => { Set::from([$($x),+]) };
}

pub fn powerset(set: &Set<Attribute>) -> Set<Set<Attribute>> {
    let mut powerset = set![set![]];

    for attribute in set.clone() {
        for subset in powerset.clone() {
            powerset.insert(&subset | &set![attribute]);
        }
    }

    powerset
}

pub fn closure(attributes: Set<Attribute>, dependencies: &Set<Dependency>) -> Set<Attribute> {
    let dependents: Set<Attribute> = dependencies
        .iter()
        .filter_map(|(x, y)| x.is_subset(&attributes).then_some(y.clone()))
        .flatten()
        .collect();

    if dependents.is_subset(&attributes) {
        attributes
    } else {
        closure(&attributes | &dependents, dependencies)
    }
}

pub fn superkeys(schema: &Schema, dependencies: &Set<Dependency>) -> Set<Set<Attribute>> {
    powerset(schema)
        .into_iter()
        .filter(|subset| closure(subset.clone(), dependencies).is_superset(&schema))
        .collect()
}

pub fn keys(schema: &Schema, dependencies: &Set<Dependency>) -> Set<Set<Attribute>> {
    let superkeys = superkeys(schema, dependencies);

    superkeys
        .clone()
        .into_iter()
        .filter(|superkey| {
            !superkeys
                .iter()
                .any(|other| other.is_subset(superkey) && other != superkey)
        })
        .collect()
}

pub fn is_schema_3nf(schema: &Schema, dependencies: &Set<Dependency>) -> bool {
    let keys = keys(schema, dependencies);

    dependencies.iter().all(|(x, y)| {
        keys.iter()
            .any(|key| x.is_superset(key) || y.is_subset(key))
    })
}

pub fn preserves_dependencies(
    decomposition: &Decomposition,
    dependencies: &Set<Dependency>,
) -> bool {
    dependencies.iter().all(|(x, y)| {
        let mut closure_g = x.clone();

        loop {
            let determinants = decomposition
                .iter()
                .flat_map(|subschema| &closure(&closure_g & subschema, dependencies) & subschema)
                .collect();

            if closure_g.is_superset(&determinants) {
                break;
            }

            closure_g.extend(determinants);
        }

        y.is_subset(&closure_g)
    })
}

pub fn generate_3nf_decomposition(schema: &Schema, dependencies: &Set<Dependency>) -> Set<Schema> {
    let keys = keys(schema, &dependencies);
    let mut f: Set<Dependency> = set![];

    // Step 1

    for (x, y) in dependencies.clone() {
        for attribute in y {
            f.insert((x.clone(), set![attribute]));
        }
    }

    // Step 2

    for (x, y) in f.clone() {
        let mut subsets: Vec<_> = powerset(&x).into_iter().collect();
        subsets.sort_by_key(|s| s.len());

        for subset in subsets {
            if y.is_subset(&closure(subset.clone(), &f)) {
                f.remove(&(x, y.clone()));
                f.insert((subset, y));
                break;
            }
        }
    }

    // Step 3

    for (x, y) in f.clone() {
        let mut f_diff = f.clone();
        f_diff.remove(&(x.clone(), y.clone()));

        if y.is_subset(&closure(x, &f_diff)) {
            f = f_diff;
        }
    }

    // Decomposition

    let mut decomposition: Set<Schema> = f.iter().map(|(x, y)| x | y).collect();

    let missing = schema - &f.iter().flat_map(|(x, y)| x | y).collect();
    if !missing.is_empty() {
        decomposition.insert(missing);
    }

    // TODO: add key

    decomposition
}

[CuriousCI]

Implementazioni alternative degli algoritmi visti a lezione

Warning

Alcuni li ho revisionati da quando ho fatto questo post, appena possibile caricherò le nuove versioni

$(X)^+_F$

def clousure(R, F, X):
    S = { A ∈ R | Y → V ∈ F ∧ Y ⊆ Z ∧ A ∈ V }

    if S ⊆ X:
        return X

    return closure(R, F, X ∪ S)

$\rho$ preserva $F$

def preserves_dependencies(R, F, ρ):
    for X → Y ∈ F:
        if Y ⊈ closure_G(R, F, X, ρ):
            return false

    return true

$(X)^+_G$

def clousure_G(R, F, X, ρ):
    S = ∅
    for P ∈ ρ:
        S = S ∪ (closure(R, F, X ∩ P) ∩ P)

    if S ⊆ X:
        return X 

    return closure_G(R, F, X ∪ S)

$\rho$ ha un join senza perdita

def has_looseless_join(R, F, ρ):
    while !(r has a line with all 'a') or (r has not changed):
        for X → Y ∈ F:
            for t1, t2 in r:
                if t1[X] = t2[X] and t1[Y] != t2[Y]:
                    for A ∈ Y:
                        if t1[A] = a:
                            t2[A] = t1[A]
                        else:
                            t1[A] = t2[A]

    return ∃ a line with all 'a' in r

algoritmo di decoposizione

def decomposition(R, F: minimal cover):
    S = ∅
    ρ = ∅

    for A ∈ R | ∄ X → Y ∈ F : A ∈ XY:
        S = S ∪ {A}

    if S != ∅:
        R = R - S
        ρ = ρ ∪ {S}

    if ∃ X → Y ∈ F | XY = R:
        ρ = ρ ∪ {R}
    else:
        for X → A ∈ F:
            ρ = ρ ∪ {XA}