<jupyter_start><jupyter_text>Logik für Datenbanken - Die Armstrong AxiomeAutor: <NAME>Datum: 20.12.2021 EinleitungEs werden zwei Eingaben gemacht. Eine Liste von funktionale Abhängigkeiten und eine zusätzliche Abhängigkeit, diese soll geprüft auf Ableitbarkeit.Die Lösung verwendet Armstrong Axiome und wird als ein Regelbasiertes System implementiert.Das Program wurde mit Python 3.8.8 getestet. bis aus python-interne Module wurden keine nicht selbsgeschriebenen Module verwendet.Es wurden folgende Importe gemacht:* `from sre_constants import error`* `from typing import List`* `from re import compile`--- Armstrong AxiomeQuelle: https://de.wikipedia.org/wiki/Funktionale_Abh%C3%A4ngigkeitAxiome_von_Armstrong* TrivialitätEine Menge von Attributen bestimmt eindeutig die Werte einer Teilmenge dieser Attribute (triviale Abhängigkeit), das heißt, β ⊆ α ⇒ α → β* Erweiterung Gilt α → β , so gilt auch α γ → β γ für jede Menge von Attributen γ der Relation.* TransitivitätGilt α → β  und β → γ, so gilt auch α → γ* VereinigungGelten α → β und α → γ, so gilt auch α → β γ* ZerlegungGilt α → β γ, so gelten auch α → β und α → γ.* PseudotransitivitätGilt α → β und β γ → δ, so gilt auch α γ → δ. --- Regelbasierte SystemQuelle: https://de.wikipedia.org/wiki/Regelbasiertes_SystemRegelbasierte Systeme bestehen aus:* Einer Datenbank von Fakten, der Faktenbasis* Einer Menge von Regeln (Produktionsregeln, Geschäftsregeln), der Regelbasis (auch Business-Rule-Repository genannt)* Einem Kontrollsystem mit Regelinterpreter (auch Inferenzmaschine oder Business-Rule-Engine genannt).Die Regeln liegen in der Form: WENN … DANN … SONST--- AnsatzDer Ansatz für die Lösung verwendet die Trivialität-, Erweiterung- und Pseudotransitivitätsregel.Der Ansatz kann am besten mit einem Beispiel gezeigt werden.gegeben ist die Menge α an Attributen {A,B,C,D,E,F,G,H} und folgende Menge Y an funktionale Abhängigkeiten:* A->D* BD->ED* BC->H* D->A* H->DEF* F->B* E->C* G->HFEs soll die funktionale Abhängigkeit α "G->ABCDEFH" bewießen werden:Man nimmt an G->ABCDEFH ist wahrG->HF aus Y wird benutzt, um mithilfe der Pseudotransitivität α zu erweitern.α ist jetzt GHF->ABCDEFH.Mit der Trivialitätsregel kann die rechte Seite von α reduziert werden.α ist jetzt GHF->ABCDEH->DEF wird benutzt, um mit der Erweiterungsregel GHF->ABCDE zu erweitern.α ist jetzt GHFDE->ABCDEFMit der Trivialitätsregel wird nochmal die rechte Seite reduziert.α ist jetzt GHFDE->ABCgleicher Schritt mit D->A ergibt GHFDEA->BCgleicher Schritt mit E->C ergibt GHFDEAC->Bgleicher Schritt mit F->B ergibt GHFDEACB->Somit hat man die rechte Seite von α eliminiert.GHFDEACB-> ist wahr laut Trivialitätsregel, denn die leere Menge eine Teilmenge von {G,H,F,D,E,A,C,B}  --- Klassen AttributeEine Klasse, die ein Attribute representiert.Variablen:- id: Name vom Attribut SideEine Klasse, die eine Seite einer Funktionale Abhängigkeit representiert.Variablen:- attributes: Eine Liste von Attributen DependancyEine Klasse, die eine funktionale Abhängigkeit representiert.Variablen:- left_side: Ein Instanz der Klasse Side. Sie enthält die Attributen der linken Seite einer FD- right_side: Analog zu left_side. dieser enthält die Attributen der rechten Seite- origin: Ein optionales Argument. enthält die Stamm Dependancy, aus der diese FD abgeleitet wurde- state: ["proven", "blocked", "unknown"]. enthält den Stand der Ableitung der FD<jupyter_code>from typing import List

class Attribute:
    """A class for an Attribute of a DB Dependancy"""

    def __init__(self, _id: str) -> None:
        self.id = _id
        pass

    def __str__(self) -> str:
        return self.id

    def __repr__(self) -> str:
        return '"' + self.__str__() + '"'

    def __eq__(self, __o: object) -> bool:
        if isinstance(__o, Attribute):
            return True if __o.id == self.id else False
        return False
    
    def __hash__(self) -> int:
        return self.id.__hash__()

class Side:
    """A Side of a functional DB Dependancy"""

    def __init__(self, attributes: List[Attribute]) -> None:
        self.attributes = attributes

    def __str__(self) -> str:
        return "".join([a.id for a in self.attributes])
        

    def __repr__(self) -> str:
        return '"' + self.__str__() + '"'
    
    def __eq__(self, __o: object) -> bool:
        if isinstance(__o, Side):
            if self.attributes in __o.attributes and __o.attributes in self.attributes:
                return True
        return False

class Dependacy:
    """A functional DB Dependacy.
    Has a right and a left side."""

    def __init__(
        self, left_side: Side, right_side: Side, origin=None, state="unknown"
    ) -> None:  # FIXME: origin could be multiple dependancies
        self.left_side = left_side
        self.right_side = right_side
        self.origin = origin
        self.state=state

    def __str__(self) -> str:
        return f"{str(self.left_side)}->{str(self.right_side)}"

    def __repr__(self) -> str:
        return '"' + self.__str__() + '"'

    def __eq__(self, __o: object) -> bool:
        if isinstance(__o, Dependacy):
            if self.left_side.attributes == __o.left_side.attributes and\
                self.right_side.attributes == __o.right_side.attributes:
                return True
        return False<jupyter_output><empty_output><jupyter_text>FunktionenIm nächsten Teil sind die Funktionen implementiert.<jupyter_code>def fd_blocked_test(d,  *kwards, **kwargs):
    "checks if the state of a dependancy is blocked"
    return True if d.state == "blocked" else False

def fd_blocked_action(d,  *kwards, **kwargs):
    "reports that the dependancy can't be derived"
    print(d, "Can't be derived")
    return d

def fd_proven_test(d,  *kwards, **kwargs):
    "checks if the state of the dependancy is proven"
    return True if d.state == "proven" else False

def fd_proven_action(d,  *kwards, **kwargs):
    "reports that the dependancy has been proven"
    print(d, " Has been proven")
    return d


def has_trivial(d: Dependacy, *kwards, **kwargs) -> bool:
    "Checks the triviality Armstrong Axiome. Returns True if d has trivial attributes"
    for l_a in d.left_side.attributes:
        if l_a.id in [x.id for x in d.right_side.attributes]: #FIXME: The need to check for id smells like bad design!!
            return True


def remove_trivial(d: Dependacy, *kwards, **kwargs) -> Dependacy:
    "removes trivial attributes from d's right side"
    new_r_side = Side([])
    for r_a in d.right_side.attributes:
        if not r_a.id in [x.id for x in d.left_side.attributes]:
            new_r_side.attributes.append(r_a)
    return Dependacy(d.left_side, new_r_side, d)


def already_exists(d: Dependacy, d_list:List[Dependacy], *kwards, **kwargs) -> Dependacy:
    "returns true if d is present in d_list"
    for owned_dependacy in d_list:
        if d == owned_dependacy:
            return True
    return False

def set_proven(d: Dependacy, *kwards, **kwargs) -> Dependacy:
    "sets the state of d to proven"
    return Dependacy(d.left_side, d.right_side, d.origin, state="proven")




def rightside_empty(d:Dependacy, d_list:List[Dependacy], *kwards, **kwargs):
    "Checks if the right_side of d is empty"
    if len(d.right_side.attributes) == 0:
        return True
    return False


def is_stuck(d, d_list, *kwards, **kwargs):
    """Returns True if none of the attributes on the left_side of d can determine any new attributes"""
    ls_d = set(d.left_side.attributes)
    for x in d_list:
        ls_x = set(x.left_side.attributes)
        rs_x = set(x.right_side.attributes)
        if ls_d.issuperset(ls_x):
            if len(rs_x.difference(ls_d))>0:
                return False
    return True

def set_blocked(d, d_list, *kwards, **kargs):
    """Sets d.state to blocked"""
    return Dependacy(d.left_side, d.right_side, d.origin, state="blocked")



def can_prove_something(d, d_list, *kwards, **kwargs):
    """Returns True if any of the attributes on the left_side of d can determine atleast one new attribute"""
    ls_d = set(d.left_side.attributes)
    for x in d_list:
        ls_x = set(x.left_side.attributes)
        rs_x = set(x.right_side.attributes)
        if ls_d.issuperset(ls_x):
            if len(rs_x.difference(ls_d))>0:
                return True
    return False

def modify_dependancy(d:Dependacy, d_list, *kwards, **kwargs):
    """Changes d.
    uses the nested function `find_subset_dependancy(d,d_list)` to find a dependancy x (where x.left_side is a partial set of d.left_side
    and x.right_side has atleast one Attribute that is not in d.left_side)

    Which means everything that is determined using x can be determined using d.
    Using that we add x.left_side.attributes to d.left_side.attributes
    """
    def find_subset_dependacy(d:Dependacy, d_list) -> Dependacy:
        #FIXME: ALSO NEED ORIGIN
        ls_d = set(d.left_side.attributes)
        for x in d_list:
            ls_x = set(x.left_side.attributes)
            rs_x = set(x.right_side.attributes)  
            if ls_d.issuperset(ls_x) and len(rs_x.difference(ls_d))>0:
                return x
    subset_dependacy = find_subset_dependacy(d, d_list)
    new_leftside = [] + d.left_side.attributes
    for a in subset_dependacy.right_side.attributes:
        if a not in d.left_side.attributes:
            new_leftside.append(a)

    return Dependacy(Side(new_leftside), d.right_side, origin=subset_dependacy, state="unknown")<jupyter_output><empty_output><jupyter_text>RulesDie Regeln für das Produktionssystem.Folgende Regeln werden gebraucht:  CAN_PROVE_SOMETHING:In each round the rules are applied, if there are attributes that we can determine using the leftside of the FD we remove them from out rightside and add them to our  CANT_PROVE_ANYTHING:In each round the rules are applied, if there are no attributes left that we can determine using the leftside of the modified FD and the right side of the FD is still not empty. than this means we can't go any further and the FD can't be derived RIGHTSIDE_EMPTY:if the right side of the FD is empty. that means it can be derived ALREADY_EXISTS:If the FD is already known to use. we can safely set the state to proven FD_BLOCKED:the state ofdependancy gets blocked if it can't find any attributes that it can determine. in this case, it's safe to assume that it can't be derived FD_PROVEN:When state of the dependancy is set to proven. then print out that its has been proven HAS_TRIVIAL:One of the Armstrong Axiomes. If an Attribute is on both sides of the dependancy. it can be removed from the right side<jupyter_code>CAN_PROVE_SOMETHING = {
    "name" : "CAN_PROVE_SOMETHING",
    "description": """a
    In each round the rules are applied, if there are attributes that we can determine using the leftside of the FD we remove them from out rightside and add them to our leftside.""",
    "test": can_prove_something,
    "action": modify_dependancy
} 

CANT_PROVE_ANYTHING = {
    "name" : "CANT_PROVE_ANYTHING",
    "description": """in each round the rules are applied, if there are no attributes left that we can determine using the leftside of the modified FD and the right side of the FD is still not empty. than this means we can't go any further and the FD can't be derived""",
    "test": is_stuck,
    "action": set_blocked
}


RIGHTSIDE_EMPTY = {
    "name" : "RIGHTSIDE_EMPTY",
    "description": """if the right side of the FD is empty. that means it can be derived""",
    "test": rightside_empty,
    "action": set_proven
}

ALREADY_EXISTS = {
    "name" : "ALREADY_EXISTS",
    "description": """If the FD is already known to use. we can safely set the state to proven""",
    "test": already_exists,
    "action": set_proven
}


FD_BLOCKED = {
    "name" : "FD_BLOCKED",
    "description": """the state ofdependancy gets blocked if it can't find any attributes that it can determine. in this case, it's safe to assume that it can't be derived""",
    "test" : fd_blocked_test,
    "action" : fd_blocked_action
}

FD_PROVEN = {
    "name" : "FD_PROVEN",
    "description": """When state of the dependancy is set to proven. then print out that its has been proven""",
    "test": fd_proven_test,
    "action" : fd_proven_action
}

HAS_TRIVIAL = {
    "name" : "HAS_TRIVIAL",
    "description" : """One of the Armstrong Axiomes. If an Attribute is on both sides of the dependancy. it can be removed from the right side""",
    "test": has_trivial,
    "action": remove_trivial
}

RULES = (
    CAN_PROVE_SOMETHING, 
    CANT_PROVE_ANYTHING,
    RIGHTSIDE_EMPTY,
    ALREADY_EXISTS,
    FD_BLOCKED,
    FD_PROVEN,
    HAS_TRIVIAL
)<jupyter_output><empty_output><jupyter_text>Parser Parse AttributesTakes a string of the following form `"{A,B,C,D,E,F,G}"` and returns a list of attributes Parse DependancyTakes a string of the form `"AB->DE"`and returns an instance of the Dependancy class.<jupyter_code>from sre_constants import error
from typing import List
from re import compile



STRICT_MODE = True  # Turn off to stop raising errors


def parse_attributes(input_string) -> List[Attribute]:
    """Parse an input string to find attributes.
    Input string must be in the following Form:
    "{A,B,C,D,E,F,G}"
    returns a list of Attributes object
    """
    s = "{A,B,C,D,E,F,G}"

    def validate_input(input_string):
        unvalid_input = compile("\{([A-Z]\,)*([A-Z])\}")
        search_res, _ = unvalid_input.subn("", input_string)
        if search_res:
            if STRICT_MODE:
                raise error(f"Input {search_res} is invalid")
            else:
                print(f"Skipping ({input_string}) because it's invalid")
                return False
        else:
            return True

    if validate_input(input_string):
        return [Attribute(att) for att in input_string[1:-1].split(",")]


def parse_dependancy(input_string) -> Dependacy:
    """Parse an input string.
    Input string must be in the following Form:
    [A-Z]+->[A-Z]+
    returns a Dependacy object
    """

    def validate_input(input_string):
        unvalid_input = compile("[A-Z]+\-\>[A-Z]+")
        search_res, _ = unvalid_input.subn("", input_string)
        if search_res:
            if STRICT_MODE:
                raise error(f"Input {search_res} is invalid")
            else:
                print(f"Skipping ({input_string}) because it's invalid")
                return False
        else:
            return True

    # TODO: Check if each side has known attributes

    def parse_left_side(input_string):
        right_side_prg = compile("[A-Z]+\-\>")
        right_side_args = right_side_prg.findall(input_string)[0][:-2]
        return Side([Attribute(arg) for arg in right_side_args])

    def parse_right_side(input_string):
        left_side_prg = compile("\-\>[A-Z]+")
        left_side_args = left_side_prg.findall(input_string)[0][2:]
        return Side([Attribute(arg) for arg in left_side_args])

    if validate_input(input_string):
        return Dependacy(parse_left_side(input_string), parse_right_side(input_string))<jupyter_output><empty_output><jupyter_text>Kontrollsystem<jupyter_code>def control_engine(d, d_list):
    while d.state == "unknown":
        for r in RULES:
            if r["test"](d, d_list):
                print(f"Rule Matched: {r['name']}")
                old_d = Dependacy(d.left_side, d.right_side, d.origin, d.state)
                d = r["action"](d, d_list)
                #
                if r["name"] == "CAN_PROVE_SOMETHING":
                    print(f"{old_d} is now {d} Because of {d.origin}")
                elif r["name"] == "CANT_PROVE_ANYTHING":
                    print(f"Can't derive any none-trivial attributes from {d.left_side}")
                    print("State set to blocked")
                elif r["name"] == "FD_PROVEN" or r["name"] == "FD_BLOCKED":
                    pass
                elif r["name"] == "RIGHTSIDE_EMPTY":
                    print("State set to proven")
                else:
                    print(f"{old_d} is now {d}")<jupyter_output><empty_output><jupyter_text>Input ValidationEine Funktion, die fehler wirft falls eine funktionale Abhängigkeit mit unbekannten Attributen eingegeben wurde<jupyter_code>def validate_input(d_list, a_list):
    """throws an error if dependancies have attributes which are not inputted into the system"""
    for d in d_list:
        for a in d.left_side.attributes:
            if not a in a_list:
                print(f"{a} is not part of the input. Please check the dependancy input again")
                raise error(f"Dependancy {d} has unknown Attribute {a}")
        for a in d.right_side.attributes:
            if not a in a_list:
                print(f"{a} is not part of the input. Please check the dependancy input again")
                raise error(f"Dependancy {d} has unknown Attribute {a}")<jupyter_output><empty_output><jupyter_text>Test runPassen Sie die Variablen Attributes und Dependancies an.Wenn Dependancies Attributen enthalten, die nicht in Attributes gibt. wird ein Fehler geworfen.<jupyter_code>ATTRIBUTES = "{A,B,C,D,E,F,G,H}"
DEPENDANCIES = [
        "A->D",
        "BD->ED",
        "BC->H",
        "D->A",
        "H->DEF",
        "F->B",
        "E->C",
        "G->HF"
        ]

a_list = parse_attributes(ATTRIBUTES)
d_list = [parse_dependancy(d) for d in DEPENDANCIES]

d = parse_dependancy("A->H")

validate_input(d_list, a_list)  
validate_input([d], a_list)     

control_engine(d, d_list)<jupyter_output>Rule Matched: CAN_PROVE_SOMETHING
A->H is now AD->H Because of A->D
Rule Matched: CANT_PROVE_ANYTHING
Can't derive any none-trivial attributes from AD
State set to blocked
Rule Matched: FD_BLOCKED
AD->H Can't be derived
{'fraction_non_alphanumeric': 0.09600631768953069, 'fraction_numerical': 0.0012973826714801444, 'mean_word_length': 3.2515587529976018, 'pattern_counts': {'":': 22, '<': 29, '<?xml version=': 0, '>': 95, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '569864', 'license': 'MIT', 'n_tokens_mistral': 5913, 'n_tokens_neox': 5710, 'n_words': 1884, 'path': 'Abgabe/Abgabe_L1_MouazTabboush.ipynb', 'repo_name': 'Mo-Official/ArmstrongAxiome', 'size': '17736'}