Datalog -> Relationale Algebra

juffi
Dozentin/Dozent
Beiträge: 41
Registriert: 13. Okt 2005 17:10

Datalog -> Relationale Algebra

Beitrag von juffi »

Ein kurzer Nachtrag zur heutigen Vorlesung:

1. Die Aufzeichnung ist diesmal vollständig. :-)

2. Bezüglich der Diskussion, die sich um Folie 38 entsponnen hat, möchte ich nachtragen, dass hier meine Erklärung etwas von der auf dieser Folie gegebenen abgewichen ist und sich an der vorigen (Folie 37) orientiert hat. Ich habe erklärt (oder versucht zu erklären):
i. P1 wird aus parent(X,Z) gebildet
ii. P2 wird aus parent(Z,Y) gebildet (ist zu diesem Zeitpunkt identisch zu P1, ausser dass die Spalten anders heissen)
iii. R1 wird als Join aus P1 und P2 wird gebildet, indem die 2. Spalte von P1 mit der 1. von P2 gleichgesetzt wird. Dabei fallen alle Tupel raus, bei denen diese Bedingung nicht erfüllt werden kann. Resultat sind alle Tupel x,z,y, für die gilt, dass z einen Elternteil (x) und ein Kind (y) hat.
iv. Die Herbrand-Basis für grandfather(X,Y) wird gebildet (also eine Relation R2, in der alle möglichen Paare von Personen aus der Datenbank vorkommen)
v. Eine Relation G wird gebildet, die alle Paare x und y enthält, für die x Großmutter von y ist.
vi. R3 wird konstruiert, indem G von R1 abgezogen wird, d.h. es bleiben alle Tupel aus R1 über, die nicht auch in G vorkommen (also alle Paare von Personen, für die gilt, dass die erste nicht Großmutter der 2. ist)
vii. Diese Relation wird mit R1 gejoint (aus R1, das alle Großeltern-Eltern-Kind Tripel enhält fallen also alle raus, bei denen der Großeltern-Teil die Großmutter ist), und auf x und y projiziert.

Auf Folie 38 wird aber Schritt iv. ersetzt durch
iv-a. Die Relation R2 wird gebildet, indem nicht alle möglichen Paare (x,y) betrachtet werden, sondern nur die, die in R1 vorkommen.

Streng genommen entspricht dieser Schritt nicht der Vorgangsweise, die auf Folie 27 angegeben ist. Der Unterschied ist, im wesentlichen, dass hier das Join mit Relation R1, das dann später im Schritt vii. erfolgen wird, implizit bereits vorgezogen wird. Dadurch ergibt sich natürlich am Ende das gleiche Ergebnis, und die Berechnung ist etwas einfacher, es ist also eine durchaus sinnvolle Vorgangsweise.

Die Beobachtung der jungen Dame, die nicht meine Großmutter ist, dass man bei der auf Folie 38 gezeigten Vorgangsweise das Join im Schritt vii. nicht mehr braucht (weil es ja implizit schon vorgezogen wure), war dann aber völlig richtig (nur bei der von mir erklärten Vorgangsweise von Folie 37 bräuchte man es). Vielen Dank!

Hoffe das klärt das ein bißchen.

JF

derJan2
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 23. Mai 2012 21:37

Re: Datalog -> Relationale Algebra

Beitrag von derJan2 »

Ich fürchte, die Frage der jungen Dame, die nicht Ihre Großmutter ist, ist immer noch nicht ganz geklärt. Zumindest verwirrt mich, was Sie zu Punkt vi geschrieben haben
juffi hat geschrieben:vi. R3 wird konstruiert, indem G von R1 abgezogen wird, d.h. es bleiben alle Tupel aus R1 über, die nicht auch in G vorkommen (also alle Paare von Personen, für die gilt, dass die erste nicht Großmutter der 2. ist)
Auf der Folie steht doch, dass G von R2 (nicht von R1) abgezogen wird. Da R2 die Projektion von R1 auf x und y ist und in R1 "Großelter-Elter-Kind"-Tripel standen, müssten in R2 "Großelter-Kind"-Tupel stehen, bei denen das Geschlecht des Großelters noch nicht bestimmt ist. Weil nun G, also "Großmutter-Kind"-Tupel, von R2 abgezogen werden, müssten doch schon hier (also in R3) nur noch "Großvater-Kind"-Tupel übrig bleiben. Damit ist der Join im letzten Schritt in meinen Augen nicht mehr nötig. Das ist denke ich auch der Punkt, auf den die junge Dame, die nicht Ihre Großmutter ist, hinaus wollte.

Gruß,
derJan2

Antworten

Zurück zu „Archiv“