Datenbanksysteme1

Question 1

Begriff

Accepted Answer

• Mathematik: Prädikatenkalkül – Formeln wie {x | xεN Λ x3> 0 Λ x3 < 1000} • Anwendung solcher Formeln für DB-Anfragen – Bezugnahme auf DB-Relationen im Bedingungsteil: (x1, y1, z1) ε Mitarbeiter, t1 ε Abteilungen – Terme werden gebildet aus Variablen, Konstanten usw. – Atomare Formeln aus Prädikaten der Datentypen:=, <, >, ≤, usw. – Atomare Formeln können mit logischen Operatoren zu komplexen Formeln zusammengefasst werden: F1 ΛF2, F1 ν F2, ¬F1, Ξx: F1, FürAllex: F1 • Bsp: Finde alle Großstädte in Bayern: {t | Städte(t) Λ t[Land] = Bayern Λt[SEinw] ≥ 500.000} Hinweis: Städte(t) gleichbedeutend mit t ε Städte

Question 2

Unterschied zur Rel. Algebra

Accepted Answer

• Relationale Algebra ist prozedurale Sprache: – Ausdruck gibt an, unter Benutzung welcher Operationen das Ergebnis berechnet werden soll – WIE • Relationen-Kalkül ist deklarativeSprache: – Ausdruck beschreibt, welche Eigenschaften die Tupel der Ergebnisrelation haben müssen ohne eine Berechnungsprozedur dafür anzugeben – WAS • Es gibt zwei verschiedene Ansätze: – Tupelkalkül: Variablen sind vom Typ Tupel – Bereichskalkül: Variablen haben einfachen Typ

Question 3

Der Tulpenkalkül

Accepted Answer

• Man arbeitet mit – Tupelvariablen:t – Formeln:ψ(t) – Ausdrücken: {t | ψ(t)} • Idee: Ein Ausdruck beschreibt die Menge aller Tupel, die die Formel ψ erfüllen (wahr machen) • Ein Kalkül besteht immer aus – Syntax: Wie sind Ausdrücke aufgebaut? – Semantik: Was bedeuten die Ausdrücke?

Question 4

Tupelvariablen

Accepted Answer

• Tupelvariablen haben ein definiertes Schema: – Schema(t) = (A1: D1, A2: D2, ...) – Schema(t) = R1 (t hat dasselbe Schema wie Relation) • Für Zugriff auf die Komponenten –t[A] oder t.A für einen Attributnamen A ε Schema(t) – oder auch t[1], t[2] usw. • Tupelvariable kann in einer Formel ψ freioder gebunden auftreten (s.unten)

Question 5

Atome drei Arten von Atomen

Accepted Answer

• Es gibt drei Arten von Atomen: –R(t) R ist Relationenname, tTupelvariable. lies: t ist ein Tupel von R –t.AΘs.B tbzw. s sind zwei Tupelvariablen mitpassenden Attributen. lies: t.Asteht in Beziehung Θ zu ... – t.AΘc tist Tupelvariable und ceine passendeKonstante Θ Vergleichsoperator: Θε{= , < ,> , ≤, ≥, ≠}

Question 6

Formeln

Accepted Answer

Der Aufbau von Formeln ψ ist rekursiv definiert: • Atome: Jedes Atom ist eine Formel. Alle vorkommenden Variablen sind frei • Verknüpfungen: Sind ψ1 und ψ2 Formeln, dann auch: ¬ψ1 nicht (ψ1Λψ2) und (ψ1νψ2) oder Alle Variablen behalten ihren Status. • Quantoren: Ist ψ eine Formel, in der t als freieVariableauftritt, sind auch Formeln... (Ξt)(ψ) es gibt ein t, für das ψ (fürAlle t)(ψ) für alle t gilt ψ die Variable t wird gebunden

Question 7

Ausdruck (Anfrage)

Accepted Answer

• Ein Ausdruck des Tupelkalküls hat die Form {t | ψ(t)} • In Formel ψist t die einzige freie Variable

Question 8

Semantik

Accepted Answer

Bedeutung, die einem korrekt gebildeten Ausdruck durch eine Interpretation zugeordnet wird: Syntax →Intepretation Sematik Tupelvariablen → konkrete Tupel Formeln → true, false Ausdrücke → Relationen

Question 9

Semantik

Accepted Answer

Bedeutung, die einem korrekt gebildeten Ausdruck durch eine Interpretation zugeordnet wird: Syntax →Intepretation Sematik Tupelvariablen → konkrete Tupel Formeln → true, false Ausdrücke → Relationen

Question 10

Belegung von Variablen

Accepted Answer

• Gegeben: – eine Tupelvariable t mit Schema(t) = (D1, D2, ...) – eine Formel ψ(t), in der tfrei vorkommt – ein beliebiges konkretes Tupel r(d.h. mit Werten). Es muß nicht zu einer Relation der Datenbank gehören • Bei der Belegung wird jedes freie Vorkommen von t durch rersetzt. Insbesondere wird t.A durch den Attributwert von r.A ersetzt. • Man schreibt: ψ(r | t)

Question 11

Interpretation von Formeln

Accepted Answer

Interpretation I(ψ) analog zu syntaktischem Aufbau – Anm: Alle Variablen sind durch konkrete Tupel belegt • Atome: –R(r): I(R(r)) = true ↔ r ist in R enthalten –ci Θcj: I(ci Θ cj) = true ↔ der Vergleich ist erfüllt • Logische Operatoren: –¬ψ: I(¬ψ) = true ↔I(ψ) = false –ψ1 Λ ψ2: I(ψ1 Λ ψ2)= true ↔I(ψ1)=true und I(ψ2)=true –ψ1 ν ψ2: I(ψ1 ν ψ2)=true ↔ I(ψ1)=true oder I(ψ2) = true

Question 12

Sichere Ausdrücke

Accepted Answer

• Mit den bisherigen Definitionen ist es möglich, unendliche Relationen zu beschreiben: – Schema(t) = {String, String} – {t | t.1 = t.2 } – Ergebnis: {(A,A),(B,B),...,(AA,AA),(AB,AB),...} • Probleme: – Ergebnis kann nicht gespeichert werden – Ergebnis kann nicht in endlicher Zeit berechnet werden • Definition: Ein Ausdruck heißt sicher, wenn jede Tupelvariable nur Werte einer gespeicherten Relation annehmen kann, also positiv in einem Atom R(t) vorkommt.

Question 13

Der Bereichskalkül

Accepted Answer

• Tupelkalkül: Tupelvariablen t(ganze Tupel) • Bereichskalkül: Bereichsvariablen x1:D1, x2:D2, ...für einzelne Attribute (Bereich=Wertebereich=Domäne) Ein Ausdruckhat die Form:{x1, x2, ... | ψ(x1, x2, ...)} Atome haben die Form: –R1 (x1, x2, ...): Tupel (x1, x2, ...) tritt in Relation R1 auf –xΘy: x,yBereichsvariablen bzw. Konstanten Formeln analog zum Tupelkalkül

Question 14

Query By Example

Accepted Answer

• Beruht auf dem Bereichskalkül • Ausdrücke nicht wie in SQL als Text • Dem Benutzer wird am Bildschirm ein Tabellen-Gerüst angeboten, das mit Spezial-Editor bearbeitet werden kann • Nach Eintrag von Werten in das Tabellengerüst (Anfrage) füllt das System die Tabelle • Zielgruppe: Gelegentliche Benutzer Sprachelemente: – Kommandos, z.B. P.(print), I.(insert), D.(delete) ... – Bereichsvariablen (beginnen mit ‘_‘): _x, _y – Konstanten (Huber, Milch) – Vergleichsoperatoren und arithmetische Operatoren – Condition-Box: Zusätzlicher Kasten zum Eintragen einer Liste von Bedingungen (AND, OR, kein NOT)

Question 15

Umsetzung einer QBE-Anfrage

Accepted Answer

(ohne Negation) • Erzeuge für alle Attribute Ai aller vorkommenden Tabellen-Zeilen der Anfrage eine Bereichsvariable xi • Steht bei Attribut Ai das Kommando P.dann schreibe xi zu den freien Variablen ({... xi, ... | ...}),sonst binde xi mit einem Ξ-Quantor ({... | Ξ..., xi, ...}) • Binde alle Variablen der Anfrage mit einem Ξ-Quantor

Question 16

Quantoren und Subqueries in SQL

Accepted Answer

• Quantoren sind Konzept des Relationenkalküls • In relationaler Algebra nicht vorhanden • Können zwar simuliert werden: – Existenzquantor implizit durch Join und Projektion: {xεR|ΞyεS: ...} ≡ πR.*(σ... (R×S) ) – Allquantor mit Hilfe des Quotienten {xεR | für alle yεS: ...} Ξ (σ... (R×S)) ÷S • Häufig Formulierung mit Quantoren natürlicher • SQL: Quantifizierter Ausdruck in einer Subquery • Beispiel für eine Subquery select* from Kunde where exists (select...from...where...) (In Klammern Subquery) • In Where-Klausel der Subquery auch Zugriff auf Relationen/Attribute der Hauptquery • Eindeutigkeit ggf. durch Aliasnamen für Relationen (wie bei Self-Join): select* from kunde k1 where exists(select* fromKunde k2 wherek1.Adr=k2.Adr and...)

Question 17

Existenz-Quantor

Accepted Answer

• Realisiert mit dem Schlüsselwort exists • Der Ξ-quantifizierte Ausdruck wird in einer Subquery notiert. • Term truegdw. Ergebnis der Subquery nicht leer

Question 18

Allquantor

Accepted Answer

• Keine direkte Unterstützung in SQL • Aber leicht ausdrückbar durch die Äquivalenz: für alle x: ψ(x) ↔ ¬Ξx:¬ψ(x) • Also Notation in SQL: ...where not exists (select...from...where not...) • Beispiel: Die Länder, die von der SPD allein regiert werden select* fromLänder L1 where not exists (select* fromLänder L2 where L1.LName=L2.LName and not L2.Partei=‘SPD‘)

Question 19

Direkte Subquery

Accepted Answer

• An jeder Stelle in der select- und where -Klausel, an der ein konstanter Wert stehen kann, kann auch eine Subquery (select...from...where...) stehen. • Einschränkungen: – Subquery darf nur ein Attribut ermitteln (Projektion) – Subquery darf nur ein Tupel ermitteln (Selektion) • Beispiel: Dollarkurs aus Kurstabelle select Preis, Preis *(select Kurs from Devisen where DName = ‘US$‘ )as USPreis from Waren where... • Oft schwierig, Eindeutigkeit zu gewährleisten...

Question 20

Weitere Quantoren

Accepted Answer

• Quantoren bei Standard-Vergleichen in WHERE • Formen: –Ai Θall (select...from...where...) Für alle-Quantor –Ai Θsome (select...from...where...) –Ai Θ any (select...from...where...) Ξ-Quantor • Bedeutung: –Ai Θall (Subquery) ≡{...| für alle tεSubquery: Ai Θt} – ist größer als alle Werte, die sich aus Subquery ergeben • Einschränkung bezüglich Subquery: – Darf nur ein Ergebnis-Attribut ermitteln – Aber mehrere Tupel sind erlaubt Menge nicht Relation

Question 21

Subquery mit IN

Accepted Answer

• Nach dem Ausdruck Ai [not] in ... kann stehen: – Explizite Aufzählung von Werten: Ai in (2,3,5,7,11,13) – Eine Subquery:Ai in(select wert from Primzahlen where wert<=13) Auswertung: • Erst Subquery auswerten • In explizite Form (2,3,5,7,11,13) umschreiben • Dann einsetzen • Zuletzt Hauptquery auswerten

Question 22

Typische Form der Subquery

Accepted Answer

•Bei exists bzw. not exists ist für die Haupt-Query nur relevant, ob das Ergebnis die leere Menge ist oder nicht. Deshalb muss keine Projektion durchgeführt werden: select…from…where exists (select*from…) •Bei some, any, all und in ist das Ergebnis der Subqueryeine Menge von Werten (d.h. ein Attribut, mehrere Tupel), die in die Hauptquery eingesetzt werden. Deshalb muss in der Subquery eine Projektion auf genau ein Attribut durchgeführt werden:select…from…where A<=all(select B from…) •Das Ergebnis der direkten Subquery ist genau ein Wert. Projektion auf ein Attribut, Selektion eines Tupels:… whereA<= (select B from… whereSchlüssel=…)

Informatik (Subject) / Datenbanksysteme1 (Lesson)