Datenbankschemata, i.e. eine Menge von Relationen oder Datenbanktabellen, werden üblicherweise in Normalform gebracht um Einfüge-, Lösch- und Änderungsanomalien zu vermeiden. Ist ein Datenbankschema nicht in der höchsten Normalform treten automatisch alle diese Anomalien zusammen auf. Im folgenden soll ein Werkzeug präsentiert werden, das die händische Normalisierung von Datenbankschemata erleichtert bzw. vollständig automatisieren kann solange keine mehrwertigen Abhängigkeiten im Spiel sind. Sollte es keine mehrwertigen Abhängigkeiten geben, so ist ein Schema mit der BCNF bereits in der höchstmöglichen Normalform und damit bedenkenlos einsatzfähig.
Gute UML oder EER-Diagramme bilden zwischen Klassen und Relationen in BCNF oder noch höheren Normalformen ab; sind also bereits in Normalform. Auf eine korrekte Aufteilung in Klassen ist vor allem dann zu achten, wenn es mehrere prime Attribute und Schlüssel gibt und wenn Teile des Schlüssels einer Klasse zu einer anderen Relation gehören (schwache Entitäten). Das Werkzeug erlaubt es zwischen mehreren Möglichkeiten zur Normalisierung eine geeignete zu wählen.
dbschemacmd ist eine erweiterte Python-Kommandozeile. Beginnt ein Wort mit Großbuchstaben, so wird es entweder automatisch als Attributmenge oder als Menge von Abhängigkeiten interpretiert:
> s=('ABCDEFG','B->BE,B->DG,BF->AD,C->G DG->BA,G->F') > s ABCDEFG B->BDEG BF->AD C->G DG->AB G->F > closure(C,s) # cl(C,s) CFG > closure(CD,s) # cl(CD,s) ABCDEFGEin Schema ist ein Python-Tupel das aus Attributmenge (an erster Stelle) und einer Menge von Abhängigkeiten (an letzter Stelle) besteht. Attribut- und Regelmengen können auch ohne einfache Anführungszeichen geschrieben werden wobei allerdings der Beistrich durch einen Schrägstrich zu ersetzen ist; also bspw. A->B/B->C. closure (abgekürzt "cl") ist eine Funktion, die die transitive Hülle einer Attributmenge für ein Datenbankschema berechnet, das auch als einfaches Fakten-Regel System oder einfach nur als Menge von Abhängigkeiten interpretierbar ist.
dbschemacmd ist ein vollständiger Python-Interpreter, allerdings mit der Einschränkung das Variablen, Funktionen und Konstanten wie true oder false mit Kleinbuchstaben beginnen müssen. Einfache Zeichenketten, die weder Attribut- noch Abhängigkeitsmengen repräsentieren sollen, müssen immer unter doppelte statt einfachen Anführungszeichen gesetzt werden.
Kommen wir nun zur minimalen Überdeckung:
> mincoverage_more(s) # mminc(s) »0« ABCDEFG B->DEG C->G DG->AB G->F »1« ABCDEFG B->ADEG C->G DG->B G->F > minc(s,0) # mminc(s)[0], mincoverage(s,scramble=0) ABCDEFG B->DEG C->G DG->AB G->F > minc(s,1) # mminc(s)[1] ABCDEFG B->ADEG C->G DG->B G->FDie Funktion mincoverage_more (Synonym: mminc) berechnet gleich mehrere verschiedene minimale Überdeckungen und legt das Ergebnis in einem Python-Dictionary i.e. einem Key-Value Mapping ab. Als Schlüssel werden hier nur einfache Zahlen gebraucht obwohl auch Zeichenketten oder andere Konstanten erlaubt wären. mincoverage_more ist äquivalent zu mehreren Aufrufen der einfachen Funktion mincoverage oder minc mit unterschiedlichem scramble Parameter. Der Scramble-Parameter gibt die Nummer von einer aus n! Permutationen an, wobei hier nur Regeln mit mehreren Attributen auf der linken Seite permutiert werden. dbschemacmd faßt stets mehrere Regeln mit gleicher linker Seite zu einem Verbund zusammen, die dann untereinander nicht mehr permutiert werden.
Es kann sein, daß mminc/mincoverage_more nicht alle möglichen minimalen Überdeckungen liefert. Das ist insbesondere dann der Fall, wenn auf der rechten Seite unterschiedliche Mengen von Attributen in unterschiedlicher Reihenfolge weggelassen werden können. Das folgende Beispiel soll das veranschaulichen:
> bspHRTC=( 'HRTCSG', 'HR->C,C->T,HT->R,CS->G,HS->R' ); > [bspHRTC] CGHRST { C->T, CS->G, HR->C, HS->R, HT->R } > [minc(maxc(bspHRTC))] CGHRST { C->T, CS->G, HR->C, HS->T, HT->R } > [minc(maxc(bspHRTC),hints=HS->R)] CGHRST { C->T, CS->G, HR->C, HS->R, HT->R } > [maxc(bspHRTC)] CGHRST { C->T, CS->GT, CH->RT, HR->CT, HS->CGRT, HT->CR } Hier haben wir zuerst die "maximale Überdeckung", das heißt maximierte nicht reflexive rechte Seiten und ergänzte linke Seiten, dort wo die durch Rückwärtsanwendung von Regeln gewonnenen neuen linken Seiten nicht Obermenge einer bereits bestehenden linken Seite sind. Die maximale Überdeckung wird wie später noch gezeigt intern auch vom BCNF-
Haben wir die rechte Seite einmal maximiert können wir sowohl minc als auch mminc den Schlüsselwortparameter "hints" mitgeben, der besagt welche Regeln bevorzugt erhalten bleiben sollen.
Anmerkung: Damit die Ausgabe in einer Zeile erscheint haben wir statt Ausdruck [Ausdruck] geschrieben, was das Ganze in eine einelementige Liste verpackt. Listen in Python sehen wie folgt aus: [1,2,3].
Nun; kommen wir zur Schlüsselermittlung und dem 3NF Synthesealgorithums.
> sets(s) # keyBaseSets(s) {'re': 'AE', 'ua': '', 'mi': 'BDFG', 'li': 'C'} > k=keys(s); pp k; BCD { BC, CD } > verbosity=3; > a = syntesis3NF(k,s); # a = syn(s); one relation per dependency: [u'FG', u'ABDG', u'CG', u'BDEG'] union of relations with mutually dependent left side: [u'FG', u'ABDEG', u'CG'] no relation has a key; adding key CD (all keys: BC,CD) relations including key relation: [u'FG', u'ABDEG', u'CG', u'CD'] all subset relations removed: [u'FG', u'ABDEG', u'CG', u'CD'] > a FG FG { G->F } ABDEG ABDEFG { B->DEG, DG->AB } CG CFG { C->G } CD ABCDEFG { }Die Funktion keys oder lang keysTreeAlg gibt ein Tupel bestehend aus einer Zusammenfassung aller primen Attribute und einer Menge der tatsächlichen Schlüssel zurück. Der Befehl pp ("pretty print"), der auch als Funktion anwendbar ist, gibt eigentlich nur k auf der Kommandozeile aus, weil Python für Zuweisungen die Ausgabe standaradmäßig ausschaltet.
syntesis3NF oder kurz syn bringen ein Schema in dritte Normalform. Als erster Parameter darf zur Beschleunigung optional eine bereits berechnete Schlüsselmenge angegeben werden. Die Variable »verbosity« bringt viele Funktionen dazu Ausgaben über interne Berechnungsschritte zu machen; darunter keysTreeAlg, syntesis3NF und splitBCNF; ja selbst read, write und append werden dadurch mehr geschwätzig.
> verbosity=2; read aaudbi2014.dbschema read bspHRTC read bspRDT read bsp035 ... > write my.dbschema, bspHRTC, bspRDT 2 records written > append my.dbschema, bsp035 1 records written > read my.dbschema, replace=false error: could not replace bspHRTC error: could not replace bspRDT error: could not replace bsp035 3 records read. > locals().keys() [u'bsp045', 'verbosity', u'bspHRTC', u'bsp054', u'bsp055', u'bsp056', u'bsp046', u'bspRDT', 'autorepeat', u'bsp044', u'bspRED', u'bsp035']Read liest zuvor mit write oder append gespeicherte Variablen von prinzipiell beliebigem Inhalt wieder aus einer Datei ein. Die Angabe von Variablen ist optional. Erfolgt eine solche nicht werden alle lokalen Variablen außer den Systemvariablen verbosity und autorepeat geschrieben bzw. alles aus Datei eingelesen. Ob das wiedereinlesen aus einer Datei bestehende Variablen ersetzen soll sagt der replace Parameter.
Bevor wir zu splitBCNF übergehen hier der Download des dbschemacmd-Programms. Dieses sollte auf jedem Rechner funktionieren, auf dem Python installiert ist. Unter Linux und MacOS ist Python üblicherweise bereits eine vorinstallierte Systemkomponente; unter Windows kann man sich Cygwin installieren oder ActivePython probieren, obwohl das Programm unter Linux entwickelt und daher nicht mit Activestate Activepython getestet worden ist.
| dbschemacmd v1.1 | dbschemacmd: Update der ersten veröffentlichten Version. |
| dbschemacmd v1.0 | Pre-Release Version (nicht verwenden) |
| elws@ |
Bitte unterschreiben Sie die Contributor License Agreement, wenn Sie an der Entwicklung mitwirken wollen; sonst können wir Ihre Änderungen nicht in unsere über elstel.org verfügbare Version übernehmen.
python dbschemacmd.py sollte in jedem Fall funktionieren falls der dbschemacmd - Link nicht geht.Kommen wir jetzt zu einem Beispiel das nach der 3NF-Synthese noch in BCNF gebracht werden muß.
> bspHRTC=( 'HRTCSG', 'HR->C,C->T,HT->R,CS->G,HS->R' ); > syn(bspHRTC) CHRT CHRT { C->T, HR->C, HT->R } HRS CGHRST { HS->R } CGS CGST { CS->G } > splitBCNF(syntesis3NF(bspHRTC)) CHR { CH->R, HR->C } CT { C->T } HRS { HS->R } CGS { CS->G }Die besten Ergebnisse der noch experimentellen BCNF-Unterstützung bekommt man scheinbar meist dann wenn man zuerst den 3NF Synthesealgorithmus anwendet.
> verbosity=2; > splitBCNF(bspHRTC) # split(bspHRTC,heuristic=1) CGHRST: CS -> G : 1 3 C -> T : 2 2 HR -> C : 3 3 HT -> R : 3 3 splitting CGHRST along CS->G CHRST: C -> T : 2 2 HR -> C : 2 3 HT -> R : 3 3 splitting CHRST along C->T CHRS: HR -> C : 2 3 CH -> R : 3 3 splitting CHRS along HR->C HRS { HS->R } CHR { CH->R, HR->C } CT { C->T } CGS { CS->G }Für die als nächstes zu wählende Regel nimmt die hier implementierte Variante des BCNF-Split Algorithmus die Anzahl der verloren gehen würdenden Regeln aus der minimalen Überdeckung (erste Zahl) sowie eine Maßzahl für die Einfachheit der Regel (zweite Zahl). Das Ergebnis kann sich in diesem Beispiel sehen lassen.
Da es relativ viele Möglichkeiten gibt ein Schema, das nicht in BCNF ist auzusplitten, haben wir hier noch eine alternative Heuristik die statt der Einfachheit der Regel die Anzahl der verbleibenden Regeln aus der maximalen Überdeckung minimiert falls die Primärzahl der zu erhaltenden Regeln aus der minimalen Überdeckung gleich ist. Es sei angemerkt, daß das Ergebnis von splitBCNF auch von der als Ausgangsmenge angenommenen minimalen Überdeckung abhängt, die trotz fortgesetzter Maximierung und Minimierung zumindest was die rechten Seiten betrifft so gut wie möglich erhalten wird.
Weitere Ergebnisse mit derselben Heuristik zur selben minimalen Überdeckung liefert ein parameterloser Aufruf von splitBCNF. Alternativ kann man sich von iterSplitBCNF gleich einen Python-Iterator zurückgeben lassen, mit dem man über myiter.next() das jeweils nächste Ergebnis abfragen kann.
Die interne Darstellung einer Datenstruktur kann man sich mit s_repr (dbschemacmd) und repr (reines Python) anschauen. Regeln werden von dbschemacmd in sog. Verbunddarstellung verarbeitet (nicht in kanonischer Form); das heißt das alle Regeln mit selber linken Seite in einem Hash oder Dictionary gruppiert sind. Dies nicht nur aus Geschwindigkeitsgründen sondern weil es an bestimmten Stellen auch die Implementierung vereinfacht hat.
Über Feedback, Anregungen, Bug-Reports und Fixes freut sich der Autor.
informieren Sie sich über Updates für diese Webseite via rss! (Rechtsklick: mit Akregator hinzufügen)