Klausur-Fragen

[system]

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[immoartl]

Klausur-Fragen

@Braindump 2006

Kann man die Länge der Restliste – also wie viele Elemente noch folgen – einer verketteten Liste mit einer SQL-Anweisung erhalten? Wenn ja, angeben wie, wenn nein, begründen.

Nachdem ich über WITH RECURSIVE (SQL99 glaub ich) gestolpert bin, weiß ich zumindest, dass es geht.
Allerdings haben wir das in der Vorlesung nie gemacht, und mir fällt grad beim besten Willen nicht ein, wie man’s ohne die Rekursion hinbekommen könnte…

@Braindump 2006

Definition Menge

Einen Haufen Axiome wollen sie ja wohl nicht… Aber was sonst?!

[andy]

---

@immoartl

@Braindump 2006

Kann man die Länge der Restliste – also wie viele Elemente noch folgen – einer verketteten Liste mit einer SQL-Anweisung erhalten? Wenn ja, angeben wie, wenn nein, begründen.

Nachdem ich über WITH RECURSIVE (SQL99 glaub ich) gestolpert bin, weiß ich zumindest, dass es geht.
Allerdings haben wir das in der Vorlesung nie gemacht, und mir fällt grad beim besten Willen nicht ein, wie man’s ohne die Rekursion hinbekommen könnte…

Hoho: wir bilden die transitive Hülle der Nachfolger-Relation und zählen einfach ab.
Schätze sie wollen hören das es mit „unserm SQL-Wissen“ nicht geht. Haben sie in der Übung nicht sowieso mal behauptet das „unser SQL“ nicht turingvollständig ist?

@immoartl

@Braindump 2006

Definition Menge

Einen Haufen Axiome wollen sie ja wohl nicht… Aber was sonst?!

Wahrscheinlich das was sie uns in der Übung an „Mengeneigenschaften“ verkaufen wollten.
Dürfte einfach irgendwas in die Richtung keine Reihenfolge, keine Duplikate und sonst nur intuitiv-motiviertes Abgezappel („wir hatten Mengenlehre in der Grundschule, ey!“) gewesen sein. (mit Vorbehalt: ich interpretiere das als „bring your own ZFC“-Party ;P)

[immoartl]

---

@andy

Hoho: wir bilden die transitive Hülle der Nachfolger-Relation und zählen einfach ab.

Naja, man kann schon beweisen, dass TC im „normalen“ SQL nicht geht, aber das macht hier http://www.cs.wisc.edu/~cs784-1/ahoUllman.pdf 1 1/2 Seiten Anhang aus… Also ist das wohl auch nicht gemeint mit „Begründung“…

[andy]

---

Hehe, aber gut zu wissen.

Hätte jetzt einfach flapsig gesagt das wir nicht rekursiv absteigen bzw schleifen können und man kann die Länge von verketteten Listen ohne Zusatzinfo nur dadurch rauskriegen das man alle Pointer abläuft und mitzählt. Zusammengefasst also: für jeder Algorithmus in “linearem” SQL existiert ne maximale Listenlänge ab der er die Listenlänge nicht mehr bestimmten kann.

[anTonyS]

anderes Thema, neue Frage

• Planoperatoren, Relationale Algebra:
.
.
.
Diese SQL-Anweisung sollte in Planoperatoren überführt werden. Das eine mal direkt, dass andere mal sollte man das ganze optimiert angeben.

Mir würde ja jetzt nur einfallen, dass man (unoptimiert) kartesisches Produkt und Selektion macht und einmal (optimiert (?)) einen Join. Lieg ich damit richtig?
Hat jemand eine Idee für die Bonusaufgabe?

[TheFlow]

---

@anTonyS

• Planoperatoren, Relationale Algebra:
.
.
.
Diese SQL-Anweisung sollte in Planoperatoren überführt werden. Das eine mal direkt, dass andere mal sollte man das ganze optimiert angeben.

Mir würde ja jetzt nur einfallen, dass man (unoptimiert) kartesisches Produkt und Selektion macht und einmal (optimiert (?)) einen Join. Lieg ich damit richtig?
Hat jemand eine Idee für die Bonusaufgabe?

Bin mir bei der Frage auch nicht ganz sicher, aber ich hätte es im ersten Teil auch so gemacht wie du, also: CROSS(…) → SEL(…) → PROJ(…). (Sind das überhaupt „Planoperatoren“? In den Folien habe ich dazu kein gescheites Beispiel gefunden.). Optimiert wäre dann halt: JOIN(…) → SEL(…) → PROJ(…). Und die SQL-Abfrage würde ich dann auch direkt mit [m]…JOIN fahrzeuge f ON k.pid = f.pid…[/m] machen. Keine Ahnung, ob das das ist, was die hören wollten, aber was anderes fällt mir dazu nicht ein.

Jetzt hätte ich auch noch eine Frage zu den „Zeigen sie“-Aufgaben: Uns wurden die Regeln ja nur ohne Beweis „hingeworfen“ und intuitiv sind sie ja auch klar und ich könnte das auch wort- und skizzenreich begründen. Aber „zeigen sie“ heißt für mich irgendwie nicht „erklären sie irgendwie“, also wie soll ich das zeigen?

[andy]

---

@TheFlow

@anTonyS

• Planoperatoren, Relationale Algebra:
.
.
.
Diese SQL-Anweisung sollte in Planoperatoren überführt werden. Das eine mal direkt, dass andere mal sollte man das ganze optimiert angeben.

Mir würde ja jetzt nur einfallen, dass man (unoptimiert) kartesisches Produkt und Selektion macht und einmal (optimiert (?)) einen Join. Lieg ich damit richtig?
Hat jemand eine Idee für die Bonusaufgabe?

Bin mir bei der Frage auch nicht ganz sicher, aber ich hätte es im ersten Teil auch so gemacht wie du, also: CROSS(…) → SEL(…) → PROJ(…). (Sind das überhaupt „Planoperatoren“? In den Folien habe ich dazu kein gescheites Beispiel gefunden.). Optimiert wäre dann halt: JOIN(…) → SEL(…) → PROJ(…). Und die SQL-Abfrage würde ich dann auch direkt mit [m]…JOIN fahrzeuge f ON k.pid = f.pid…[/m] machen. Keine Ahnung, ob das das ist, was die hören wollten, aber was anderes fällt mir dazu nicht ein.

Also zu optimiert hätte ich auf jeden Fall mal gesagt das die ganzen Selects (Geburtsjahr und Fahrzeugtyp oder was das war) zuerst müssen um beim Join dann kleinere Relationen zu haben und vllt sogar vor dem Join auf jeweils Name und PID runterprojezieren das man da schon schön kleine Tupel hat.

Hier mal dummer Pseudocode:

Scan über kleine Relation (sei hier mal oBdA Fahrzeuge angenommen)
für jeden Satz in Fahrzeuge:
  wenn Fahrzeugtyp nicht passt, diesen Satz überspringen
  auf (Fahrzeug.PID, Fahrzeug.Name) runterprojezieren
  Scan über Personen
  für Satz in Personen:
    wenn Geburtsjahr nicht passt, continue
    auf (Personen.PID, Personen.Name) runterprojezieren, für folgende Schleifendurchläufe cachen
    wenn Person.PID=Fahrzeug.PID auf jeweils Name runterprojezieren und in Ergebnis aufnehmen

entsprechend in Pseudo-SQL dann:

select kunde.Name, fahrzeug.Name
from ((select pid, name from kunden where kunden.geburtsjahr ...) as kunde) join
         ((select pid,name from fahrzeuge where fahrzeug.typ = ...) as fahrzeug) on kunde.pid=fahrzeug.pid

@TheFlow

Jetzt hätte ich auch noch eine Frage zu den „Zeigen sie“-Aufgaben: Uns wurden die Regeln ja nur ohne Beweis „hingeworfen“ und intuitiv sind sie ja auch klar und ich könnte das auch wort- und skizzenreich begründen. Aber „zeigen sie“ heißt für mich irgendwie nicht „erklären sie irgendwie“, also wie soll ich das zeigen?

IIRC waren die ganzen „Beweise“ bloss Definition über Mengen einsetzen, (fast schon trivial) umformen, wieder Definition rückgängig machen.
Auf welche Aufgabe beziehst du dich denn konkret?

[anTonyS]

---

@andy

entsprechend in Pseudo-SQL dann:

select kunde.Name, fahrzeug.Name
from ((select pid, name from kunden where kunden.geburtsjahr ...) as kunde) join
         ((select pid,name from fahrzeuge where fahrzeug.typ = ...) as fahrzeug) on kunde.pid=fahrzeug.pid

Ja, das schaut gut aus. Dein Pseudo-SQL ist für mich eigentlich echtes SQL

@andy

@TheFlow

Jetzt hätte ich auch noch eine Frage zu den „Zeigen sie“-Aufgaben: Uns wurden die Regeln ja nur ohne Beweis „hingeworfen“ und intuitiv sind sie ja auch klar und ich könnte das auch wort- und skizzenreich begründen. Aber „zeigen sie“ heißt für mich irgendwie nicht „erklären sie irgendwie“, also wie soll ich das zeigen?

IIRC waren die ganzen „Beweise“ bloss Definition über Mengen einsetzen, (fast schon trivial) umformen, wieder Definition rückgängig machen.
Auf welche Aufgabe beziehst du dich denn konkret?

IMHO meinte TheFlow die Zeigen Sie…-Aufgaben von Braindump 2006 (1. Seite, rechte Spalte, ganz oben). Mehr, als der Verfasser des Braindumps niedergeschrieben hat, fällt mir aber auch nicht ein.

[andy]

---

@anTonyS

IMHO meinte TheFlow die Zeigen Sie…-Aufgaben von Braindump 2006 (1. Seite, rechte Spalte, ganz oben). Mehr, als der Verfasser des Braindumps niedergeschrieben hat, fällt mir aber auch nicht ein.

Dann mach ich mal exemplarisch projectA_i = project[A_i](select[P(B_i)](projectA_i ∪ B_i)) nach Skript S. 382 [hoffe die Ausführlichkeit hilft eher als das sie verwirrt ^^]:
projectA_i =(def project)=
{ projectTupleA_i | x ∈ selectP(B_i) } =(def select)=
{ projectTupleA_i | x∈R ∧ P(projectTupleB_i) } =(innere Projektion löscht sich aus)=
{ projectTupleA_i | x∈R ∧ P(projectTuple[B_i](projectTupleA_i ∪ B_i)) } =(def inneres project, äussere Projection löscht aus)=
{ projectTupleA_i | y∈projectA_i ∪ B_i ∧ P(projectTupleB_i) } =(def select)=
{ projectTupleA_i | y∈select[P(B_i)](projectA_i ∪ B_i) } =(def äusseres project)=
project[A_i](select[P(B_i)](projectA_i ∪ B_i))

[Anteru]

---

Schaut gut aus, sowas in der Art hatte ich auch mal - mir sahs nur ein wenig zu wild aus um so in der Klausur verlangt zu werden.

[andy]

---

Nachdem ich mich da jetzt noch selber verwirrt hatte, hier ein paar Tipps für die anderen “Beweise”:
Das “kartesische Produkt” (ist kein echtes, weil concat “flachklopft”, kommt eher auf Sprachprodukt aus ThI) ist assoziativ weil das concat ne monoidale Struktur erzeugt (kennt man ja als Wortverknüpfung aus ThI), also einfach auf concat runterbrechen und gut.
Der allgemeine Join ist wohl “kommutativ”, weil die Reihenfolge von Attributen in ner Relation keine echte Rolle spielt. Also könnte man das zB mit nem zusätzlichen projectTupel im Join-Prädikat machen. Wobei ich sowieso mal komisch finde das viele Quellen behaupten nur der natural join sei kommutativ, ist wahrscheinlich Definitionssache.

[immoartl]

---

@andy

Der allgemeine Join ist wohl „kommutativ“, weil die Reihenfolge von Attributen in ner Relation keine echte Rolle spielt.

Das hat mich beim Braindump-Anschauen auch schon ziemlich gestört: Ich glaube, kein Mensch käme – auch nicht bei einer Datenbank – drauf, zu sagen, dass jede beliebige Relation kommutativ ist (a < b <=> b < a ?), aber genau das ist doch die Voraussetzung dafür, dass der Join kommutativ sein kann…
Ohne irgendwelche ausdrücklichen Einschränkungen (Multimengen seh ich ja ein…) ist die Aussage meiner Meinung nach einfach falsch…

[andy]

---

Liegt wahrscheinlich einfach daran das man nicht über “Position” auf Attribute zugreifen kann/soll.
Insofern gilt nicht a<b <=> b<a sondern vielmehr BinaryRelation(LeftArg,RightArg) <=> BinaryRelation(RightArg,LeftArg) und Aussagen wie a<b sollte man vllt eher als <(LeftArg=a, RightArg=b) <=> <(RightArg=b, LeftArg=a) lesen.