unterschiedliche logisch Beziehungen in einer DB-Tabelle speichern

[wKovacs]

Hallo,

ich habe gerade wohl einen Konten im Kopf und hoffe jemand kann mich in die richtige Richtung weisen.

Mein Problem:

Ich habe eine Liste von Weiterbildungskursen (nennen wir sie KursA bis KursZ) in einer Tabelle abgelegt. Einige diese Kurse haben Vorraussetzungen aus einer Kombination von anderen Kursen.

Beispiel: KursA ODER (KursB UND KursC)

Diese Beziehungen können pro Kurs unterschiedlich sein, nicht nur unterschiedliche Anzahl an Alternativen (ODER) sondern auch Kombinationen (UND).

Ich versuche einen Weg zu finden, diese Beziehungen in einer Tabelle abzubilden.

etwa:

dabei ist "fürKurs" ein Fremdschlüssel der entweder auf die Kurstabelle verweist oder auf sich selbst.

fürKurs	Bed1	verknüpfung	bed2
KursK	KursA	oder	2
2	KursB	und	KursC

Nun habe ich 2 Probleme die ich aktuell sehe:

A wie unterscheide ich, auf welche Tabelle sich der Fremdschlüssel bezieht, mal ganz davon abgesehen, wie kann ich eine Spalte auf 2 Tabellen referenzieren lassen

B Mit diesem Entwurf kann ich sowas wie KursA UND (KursB ODER (KursC UND KursD) ODER KursE) nicht abbilden.

Ich gehe davon aus, das schon der Ansatz falsch ist. 😕

Dagegen vermute (hoffe) ich, dass es ähnliche Probleme häufiger gibt und es eine Lösung gibt. Bisher war ich nur noch nicht in der Lage sie zu finden. Falls jemand einen Lösungsansatz hat oder auch nur einen Link zu relevanten Lesestoff (auch englisch) wäre ich sehr dankbar!

Vielen Dank

wKovacs

[Email]

Interessante Aufgabe. Ich würde die Lösung mit Bitoperatoren für UND//OR angehen. Hierfür muss für jeden Kurstype ein numerischer Basiswert aus dem Dualsystem überlegt werden und zwar so daß die Verknüpfung einen eindeutigen Wert ergibt aus dem die darin enthaltenen Kurstypen erkenntlich sind.

MFG

[Email]

Interessante Aufgabe. Ich würde die Lösung mit Bitoperatoren für UND//OR angehen. Hierfür muss für jeden Kurstype ein numerischer Basiswert aus dem Dualsystem überlegt werden und zwar so daß die Verknüpfung einen eindeutigen Wert ergibt aus dem die darin enthaltenen Kurstypen erkenntlich sind.

Ansatz mit 4 Kursen:

1 1 1 1
| | | |_ Kurs A
| | |
| | |_Kurs B
| |
| |_ Kurs C
|
|_ Kurs D

Magister = 2^0 + 2^1 + 2^2 + 2^3 (alle Kurse)
Bachelor = A + B oder A + C
Beginner = A
HI = D oder C

usw.

So ergeben sich numerische Werte die eindeutig beschreiben welche Kurse belegt sein müssen für einen bestimmten Abschluss. Wobei diese Werte logisch veknüpft werden können.

Anders ausgedruückt: Gibt den Kursen numerische Wertigkeiten dann kannst Du damit rechnen.

Denke an die Skalierbarkeit!

Also ich finde die Idee richtig gut.

[Camping_RIDER]

Aloha ;)

Also ich finde die Idee richtig gut.

Fast genauso gut wie eine relationale Datenbank mit geclusterten Daten zu füttern. Weil sich das so gut mit Parameter-Kontrollstrukturen auswerten lässt. Aber wirklich nur fast so gut.

Grüße,

RIDER

[Camping_RIDER]

Aloha ;)

Zunächst: wenn du das vorstehende Geschwurbel nicht verstanden hast, denk dir nichts dabei. Manch Lösung eines genialen Geistes ist für solche wie uns einfach unverständlich.

etwa:

dabei ist "fürKurs" ein Fremdschlüssel der entweder auf die Kurstabelle verweist oder auf sich selbst.

fürKurs	Bed1	verknüpfung	bed2
KursK	KursA	oder	2
2	KursB	und	KursC

Nun habe ich 2 Probleme die ich aktuell sehe:

A wie unterscheide ich, auf welche Tabelle sich der Fremdschlüssel bezieht, mal ganz davon abgesehen, wie kann ich eine Spalte auf 2 Tabellen referenzieren lassen

"Einfach" geht das nicht. Ich schlage daher einen leicht geänderten Ansatz vor:

ID	fürKurs	Element	verknüpfung	mit
0	KursK	KursA	oder	1
1	KursK	KursB	und	2
2	KursK	KursC	oder	Null

So ist an jeder Spalte klar, für welche Tabelle der Schlüssel gilt.

Hinweis: Ich ging jetzt mal davon aus, dass du die Angabe fürKurs an der Stelle zwingend brauchst. Es wäre im vorliegenden Datenmodell aber auch möglich, diese Spalte an der Stelle komplett rauszulassen und in einer weiteren Tabelle (zwei Spalten: fürKurs und startID) den Kurs mit dem ersten Bedingungsteil zu verknüpfen. Das hat Vorteile, unter anderem ist es Speicherplatz-effizienter und du kannst zusätzlich Eindeutigkeit bei fürKurs fordern.

B Mit diesem Entwurf kann ich sowas wie KursA UND (KursB ODER (KursC UND KursD) ODER KursE) nicht abbilden.

Doch, kannst du! Du musst die Bedingung nur gleichwertig umordnen:

KursA UND (KursB ODER (KursE ODER (KursC UND KursE)))

In deinem Beispiel war ein oder-oder drin. Das lässt sich in zwei hintereinander ausgeführte oders umschreiben. Das klappt für alle und- bzw. oder-Verknüpfungen, weil diese assoziativ und kommutativ sind.

Wie du die Eingabemöglichkeit gestaltest steht auf einem anderen Blatt, aber entweder muss deine Software vor dem Speichern umordnen oder (wahrscheinlicher) es stellt sich heraus, dass es für dich schon bei der Eingabe geschickt ist, ein solches Format zu fordern.

Ich hoffe die Idee hilft dir weiter.

Grüße,

RIDER

[Rolf B]

Hallo Camping_RIDER,

KursA UND (KursB ODER (KursE ODER (KursC UND KursE)))

Whoa - wie soll man denn das relational abbilden?

Ich habe heute nachmittag angefangen mir Gedanken zu machen und auf meinem lokalen MySQL etwas experimentiert. Das dauerte natürlich eine Weile.

Grundsätzlich sollte man, wenn man logische Ausdrücke automatisiert verarbeiten will, eine Normalform dieser Ausdrücke anstreben. Davon gibt's zwei, nämlich die disjunktive und die konjunktive Normalform (Details siehe z.B. Wikipedia). Für mich persönlich ist die diskunktive Form leichter verständlich, darum gehe ich darauf jetzt näher ein.

Disjunktive Normalform (DNF) bedeutet, dass man einige Terme hat, die Variablen durch UND verknüpfen (Konjunktion), und diese Terme durch ein ODER (Disjunktion) verknüpft. Außerdem ist es erlaubt, Variablen vor der UND-Verknüpfung zu negieren. Auf diese Weise kann man sozusagen alle Zeilen der Wahrheitstabelle, wo im Ergebnis ein TRUE steht, mehr oder weniger gedankenfrei als UND-Terme aufschreiben und diese Terme ODER verknüpfen.

Was fängt man nun damit an? Nehmen wir an, wir hätten folgende Kurse:

KursA - HTML Grundlagen
KursB - CSS Grundlagen
KursC - Großer Webentwickler-Basiskurs
KursD - Aufbaukurs GRID

Für's Beispiel soll es so sein, dass man für KursD entweder KursA und KursB gemacht haben muss, oder KursC (der beinhaltet KursA und KursB).

Das kann man so in eine Tabelle UndTerme bringen:

Gruppe  VorKurs  Erforderlich
101     KursA    1
101     KursB    1
102     KursC    1
103     KursC    0
104     KursC    0

Die Spalte Erforderlich soll angeben, ob dieser Vorkurs vorausgesetzt wird, oder ob dieser Vorkurs zu einer Nichtbelegbarkeit führen soll. Damit wird die Negierungsmöglichkeit einer Variablen abgebildet, die in der DNF vorgesehen ist. Die Gruppe 103 besagt: Wer KursC schon belegt hat, soll etwas nicht tun können.

Die Zuordnung von Kurse zu UndTerme erfolgt mit einer Tabelle OderTerme, die angibt, welche Und-Gruppen für einen Kurs mit ODER verknüpft werden müssen:

Kurs    Gruppe
KursD   101
KursD   102
KursA   103
KursB   104

Wer KursD machen will, muss also Gruppe 101 oder Gruppe 102 erfüllen.

Wer KursA oder KursB machen will, muss Gruppe 103 bzw. 104 erfüllen. Die erfüllt man aber nur, wenn man KursC nicht gemacht hat. Konkret: Wer den Webentwickler-Basiskurs gemacht hat, kann HTML- oder CSS-Grundlagen nicht belegen. Das wäre für denjenigen nämlich nichts Neues mehr.

SELECT Gruppe, Vorkurs, Erforderlich
FROM   OderTerme ot JOIN UndTerme ut ON ot.gruppe = ut.gruppe
WHERE  ot.Kurs = 'KursD'

liefert dann

Gruppe  Vorkurs   Erforderlich
101     KursA     1
101     KursB     1
102     KursC     1

Das kann man nun Gruppe für Gruppe programmatisch auswerten, um für einen Kunden die Belegbarkeit zu prüfen. Oder Gruppe für Gruppe ausgeben, um dem Kunden die Kursvoraussetzungen anzuzeigen.

Oder mit SQL auswerten! Nehmen wir noch eine Tabelle hinzu, KursErfolg, in der für einen Kunden steht, welche Kurse er gemacht und bestanden hat (da würde natürlich im Reallife nicht "Rolf" stehen, sondern eine ID).

Kunde   Kurs   Bestanden
Rolf    KursA  1
Rolf    KursB  0

Diese Tabelle kann ich in das SQL einbeziehen:

SELECT Gruppe, Vorkurs, Erforderlich, Bestanden
FROM   OderTerme ot 
       JOIN UndTerme ut ON ot.gruppe = ut.gruppe
       LEFT JOIN KursErfolg ke ON ke.Kurs = ku.VorKurs
                                AND ke.Kunde = 'Rolf'
WHERE  ot.Kurs = 'KursD'

Ergebnis:

Gruppe  Vorkurs   Erforderlich   Bestanden
101     KursA     1              1
101     KursB     1              0
102     KursC     1              NULL

Die NULL in Zeile 3 erschwert die weitere Verarbeitung, darum ersetzen wir im SQL noch Bestanden durch COALESCE(Bestanden,0). Das schreibe ich jetzt nicht auf, jedenfalls wird dadurch ein nicht belegter Kurs wie Nichtbestanden behandelt. Und wir müssen Erforderlich mit Bestanden vergleichen, nur wenn es übereinstimmt, ist dieser Teil der UND-Bedingung erfüllt.

SELECT Gruppe, Vorkurs, Erforderlich=COALESCE(Bestanden,0) as Zutreffend
FROM   OderTerme ot 
       JOIN UndTerme ut ON ot.gruppe = ut.gruppe
       LEFT JOIN KursErfolg ke ON ke.Kurs = ku.VorKurs 
                                AND ke.Kunde = 'Rolf'
WHERE  ot.Kurs = 'KursD'

ergibt

Gruppe  Vorkurs   Zutreffend
101     KursA     1
101     KursB     0
102     KursC     0

Diese Treffermenge können wir nun gruppieren und aggregieren, um pro Und-Term nur noch eine Zeile zu bekommen. Ein UND ist falsch, sobald ein Teil davon falsch ist, wir müssen also MIN(Zutreffend) bilden. Das ist nur 1, wenn alle Teile des UND die 1 tragen. Den Vorkurs können wir jetzt nicht mehr ausgeben, der ist ja nicht gruppiert.

SELECT Gruppe, MIN(Erforderlich=COALESCE(Bestanden,0)) as Zutreffend
FROM   OderTerme ot 
       JOIN UndTerme ut ON ot.gruppe = ut.gruppe
       LEFT JOIN KursErfolg ke ON ke.Kurs = ku.VorKurs 
                                AND ke.Kunde = 'Rolf'
WHERE  ot.Kurs = 'KursD'
GROUP BY Gruppe

ergibt

Gruppe  Zutreffend
101     0
102     0

Das müssen wir nun noch verODERn. Ein ODER ist wahr, sobald ein Teilterm wahr ist. Das bekommen wir mit MAX(Zutreffend) geliefert.

SELECT MAX(og.Zutreffend)
FROM (SELECT Gruppe, MIN(Erforderlich=COALESCE(Bestanden,0)) as Zutreffend
      FROM   OderTerme ot 
           JOIN UndTerme ut ON ot.gruppe = ut.gruppe
           LEFT JOIN KursErfolg ke ON ke.Kurs = ku.VorKurs 
                                    AND ke.Kunde = 'Rolf'
      WHERE  ot.Kurs = 'KursD'
      GROUP BY Gruppe) og

Das ergibt die 0 als Ergebnis. Falls Rolf KursB bestanden hätte, wäre für Gruppe 101 der Zutreffend-Wert 1 ermittelt worden, und das große SQL liefert dann 1.

Ich hoffe, ich habe beim Übertragen von meinem Spiel-MySQL ins Forum keine SQL-Fehler eingebaut. Vollziehe es mal nach, probiere auch mal aus, was passiert, wenn ein Kunde den KursC belegt hat und Du die Voraussetzungen für KursA prüfst.

Wie Du das mit einem Editor pflegst, ist natürlich noch eine ganz andere Sache...

Rolf

[Camping_RIDER]

Aloha ;)

KursA UND (KursB ODER (KursE ODER (KursC UND KursE)))

Whoa - wie soll man denn das relational abbilden?

Na, so wie ich schrieb. Ob das optimal ist kann ich nicht beurteilen. Aber möglich ist das so.

Grüße,

RIDER

[wKovacs]

Vielen Dank für die Hinweise und Vorschläge und erst recht für die aufgewendete Zeit.

Ich werde experimentieren und sehen wohin es mich führt

[Email]

Vielen Dank für die Hinweise und Vorschläge und erst recht für die aufgewendete Zeit.

Keine Ursache. Mit meinen Kochrezepten ergibt sich dieselbe Problemstellung: Anhand eines Kochrezept berechnen, welche Zutaten drin sind. Und da hab ich, dank Deines POST gestern endlich mal so richtig drüber nachgedacht wie ich das machen könnte 😉

MFG

[Rolf B]

Hallo Camping_RIDER,

sorry, hatte wohl Knöpfe auf den Augen. Klar - binäre Terme kann man als binären Baum aufbauen und per SQL rekursiv zusammensuchen. Dagegen steht dann alternativ mein Vorschlag mit der DNF und einem n-ären zweistufigen Baum, der sich ohne Rekursion auslesen lässt. Letztendlich hast Du ja nur eine Klammer mehr gesetzt (und dich bei KursD vertippt 😉)

wKovacz: KursX = KursA UND (KursB ODER (KursC UND KursD) ODER KursE)

CampRid: KursX = KursA UND (KursB ODER (KursE ODER (KursC UND KursD)))

Das sind 5 Kurse, die Wahrheitstabelle ist demnach etwas umständlicher. Der Term ist hier aber so gestaltet, dass die DNF relativ einfach zu finden ist. Man muss das UND hinter KursA nur ausmultiplizieren und bekommt (boolescher Term, UND wird nicht geschrieben und $$\lor$$ (lat. vel = oder) steht für ODER. Ein NOT würde als $$\overline{A} $$ geschrieben). Sei X die Regel für Kurs X und ABCDE die Kurse A-E. Dann sieht euer mehrstufiger Term als DNF so aus:

$$X = AB \lor ACD \lor AE$$

Im Allgemeinen ist das Finden der DNF bei verschachtelten Termen umständlicher, aber da ist auch das Schreiben des Terms umständlich, und es ist einfacher, von der Wahrheitstabelle auszugehen. Um dann aus einer Wahrheitstabelle eine optimale DNF zu bauen, gibt es Techniken (Karnaugh-Veitch-Diagramm und Quine-McCluskey Algorithmus) und bestimmt auch Tools (wobei ich gerade keins finde, das eine Wahrheitstafel als Input nimmt - seltsam).

Wenn das zu kompliziert ist - eine optimierte DNF ist nicht zwingend nötig. Auf sowas reiten die Schaltalgebra-Ingenieure herum, bei denen unnötige Siliziumatome oder Quadratnanometer Geld richtig teuer sind.

In den von mir vorgeschlagenen Tabellen sähe es so aus:

OderTerme

Kurs     Gruppe
KursX    201
KursX    202
KursX    203

UndTerme

Gruppe  Vor_Kurs   Erforderlich
201     KursA       1
201     KursB       1
202     KursA       1
202     KursC       1
202     KursD       1
203     KursA       1
203     KursE       1

Rolf

[Camping_RIDER]

Aloha ;)

sorry, hatte wohl Knöpfe auf den Augen. Klar - binäre Terme kann man als binären Baum aufbauen und per SQL rekursiv zusammensuchen.

Ja. Ich sagte ja auch bereits, dass mein Vorschlag halt eine Möglichkeit ist, das darzustellen, dass ich mir aber nicht sicher bin, ob das Datenmodell für eine relationale Datenbank optimal ist. Die Rekursion ist ein negativer Aspekt (denn SQL-Auswertung geht damit nicht), und...

Dagegen steht dann alternativ mein Vorschlag mit der DNF und einem n-ären zweistufigen Baum, der sich ohne Rekursion auslesen lässt.

...dein DNF-Vorschlag ist sicher besser für die relationale Datenbank optimiert. Mir leuchtet dein Vorschlag daher total ein.

Problematisch dabei ist, aber das schriebst du ja selbst, dass es ggf. ein größerer Aufwand ist, die DNF zu finden, bzw. das für einen allgemeinen Fall zu implementieren.

Man muss da halt abwägen: Möchte man die Abbildung mit Rekursion, die beim Auslesen / Anwenden nicht alleine mit SQL funktioniert, sondern beim Auslesen ein rekursives Vorgehen benötigt, oder möchte man die rekursionsfreie Abbildung, die beim Speichervorgang / Implementieren einen großen Aufwand bedeutet.

Kommt es nicht so sehr auf die Performance beim Auslesen an, z.B. weil man das nicht so häufig prüfen muss, würde ich meine Idee bevorzugen - weil sie so schön einfach und nah an der intuitiven Überlegung ist.

Kommt es hingegen auf die Performance beim Auslesen an, z.B. weil man das häufig prüfen muss, ist deine Idee zu bevorzugen - denn sie erfordert beim Implementieren Aufwand und Umgehen (du hast die Idee zwar umrissen, aber bis zum konkreten Algorithmus ist es noch ein gewisser Weg), ist aber in der Anwendung der gespeicherten Regeln sehr effizient.

Letztendlich hast Du ja nur eine Klammer mehr gesetzt (und dich bei KursD vertippt 😉)

Ups. 😀

---

TL;DR: Mir gefällt deine Lösung vom fachlichen Standpunkt sehr gut. Sie ist gut optimiert und deutlich sauberer / systematischer als meine. Implementieren würd ich sie aber nicht unbedingt wollen 😀

Grüße,

RIDER

[Email]

sorry, hatte wohl Knöpfe auf den Augen. Klar - binäre Terme kann man als binären Baum aufbauen und per SQL rekursiv zusammensuchen. Dagegen steht dann alternativ mein Vorschlag mit der DNF und einem n-ären zweistufigen Baum, der sich ohne Rekursion auslesen lässt. Letztendlich hast Du ja nur eine Klammer mehr gesetzt (und dich bei KursD vertippt 😉)

Genau! Das Ganze lässt sich linear und ohne Rekursion lösen. Allerdings braucht es dafür eine Bedingung: Die Anzahl der Kurse muss endlich sein. Eine Bedingung die sich zweifelsfrei erfüllen läßt 😉

Meine Lösung ist soweit fertig, ich werd' sie demnächst vorstellen.

MFG

[Camping_RIDER]

Aloha ;)

Genau! Das Ganze lässt sich linear und ohne Rekursion lösen.

Ja. Wie Rolf B ja bereits schrieb.

Meine Lösung ist soweit fertig, ich werd' sie demnächst vorstellen.

Du könntest, so du wirklich was beitragen willst, erläutern, inwiefern die von Rolf B's Vorschlag abweicht und warum sie an der Stelle dann optimaler ist. Ich bin gespannt.

Grüße,

RIDER