Wie wird ein Join ausgeführt? Beispiel: R(A,D), S(B,C); Gesucht R[A=B]S · einfach und ineffizient: für jedes Tupel in R mit A=a wird S durchsucht nach B=a · mit Sekundärindex: Index weist jedem a die Tupelmenge in S mit B=a zu · mit Sortierung: R und S werden sortiert (bezgl. A bzw. B), dann werden R und S parallel durchlaufen. Wie sind die verschiedenen Normalformen definiert und wie kann man sie anschaulich erklären? 1.NF: Die Attributwerte sind unteilbar. (d.h. keine mengenwertigen Attribute) 2.NF: Jedes Nichtschlüsselattribut A von R ist voll funktional abhängig von jedem Schlüssel S von R (und nicht nur von Teilen des Schlüssels) 3.NF: Für alle implizierten Abhängigkeiten S® A mit A Ï S gilt: S enthält einen Schlüssel oder A ist Schlüsselattribut(d.h. es gibt keine Abhängigkeiten zwischen Nichtschlüsselattributen einer Relation) BCNF (Boyce Codd Normalform): Für jede funktionale Abhängigkeit S® A gilt: S enthält einen Schlüssel für R. (d.h. es gibt keine Abhängigkeit zwischen Nichtschlüsselattributen und Schlüsseln) Wie erfolgt die Optimierung von Abfragen? Was ist bei Projektionen zu beachten? · Selektionen möglichst früh vornehmen um die Ergebnismenge klein zu halten · Zusammenfassung von Selektionen zu komplexen Selektionen da dies die Zahl der Zugriffe auf die Daten minimal hält. · Bei Projektionen zuerst diejenigen Attribute nehmen, die keine Eliminierung von Duplikaten erfordern, dann möglichst früh (also wenn mindestens ein Schlüssel des Relationenschemas erhalten bleibt), sonst möglichst spät. · Suche nach gemeinsamen Teilbäumen im Operatorbaum und Vereinigung dieser Bäume (Blätter: Relationen, innere Knoten Operationen, Selektion, Join, Projektion) · Joins möglichst spät · Optimierung auf physischer Ebene: Ausnutzung von Sekundärindizes (Invertierung), Sortierung, Speicherstruktur der Datenbanktabellen Wie kann man Verbindung zwischen Sätzen unterstützen? · durch Invertierung (Erzeugung von Indizes). · durch Listen und Ringe Die zu verbindenden Sätze werden in Listenstrukturen abgelegt. (schwierig bei n:m Beziehungen) · durch variable Zeigerfelder An jeden Satz wird eine Zeigerfeld variabler Länge angehängt, mit dessen Hilfe auf die zu verbindenden Sätze verwiesen wird. · durch Kettsätze Bei n:m Beziehungen zwischen Sätzen wird ein neuer Satztyp eingeführt in dem jedes Beziehungspaar durch einen Satzeintrag repräsentiert wird Wie werden Tupeladressen berechnet? Der Datenmanager fordert Tupel mit bestimmten Attributwerten an, die Adressen werden über Indizes vom Zugriffsmanager bestimmt. Was muß man bei der Ausführung von SQL-Anfragen tun? · Optimierung der Anfrage · Transformation in konzeptuelles und internes Schema · Beschaffen der benötigten Sätze und Transformation in externes Schema; Realisierung durch Datenmanager (Mengenschnittstelle); Zugriffsmanager (Ein- Tupel-Schnittstelle); Systempuffer(Cache)Manager (Seitenschnittstelle) Wie erfolgt die Adressierung für physische Sätze? Man unterscheidet physische, seitenbezogene, logische Adressierung. Die Adresse besteht aus zwei Komponenten: Adresse der Datei und Position innerhalb der Seite. Der Zugriffsmanager ermittelt die benötigte Seite , diese wird vom Systempuffermanager angefordert, der diese bei Bedarf durch einen Betriebssystemaufruf vom Externspeicher anfordert. Wie werden relationale Datenbanken implementiert? Schichten eines DB-Systems? · Datenmanager: Mengenschnittstelle, Übersetzt und optimiert die Anfragen, Integritäts- und Zugriffskontrolle · Zugriffsmanager: 1-Tupel-Schnittstelle, Einfügen/Löschen/Suchen/ Ändern von Tupeln, Operatoren für Schemata, Transaktionsmanagement · Systempuffermanager: Seitenschnittstelle (bei Bedarf Anforderung von neuen Seiten vom Betriebssystem; pinned pages (Seiten die im Cache sind und nicht beliebig in die DB geschrieben werden dürfen), forced output (Seiten müssen ‘durchgeschrieben’ werden)) Aufgaben eines DBMS: · Definition einer DB · Aufnehmen, Verändern, Löschen, Selektieren (Abrufen) von Daten · Prüfung und Sicherstellung der Integrität · Recovery nach Systemabstürzen · Koordination mehrerer Benutzer · Datenschutz · Bearbeitung von Anfragen: Transformation externes-konzeptuelles-internes Schema · Kommunikation mit dem Betriebssystem · Steuerung des Systempuffers (DB-Cache) · Übergabe der Daten und von Statusinformationen (z.B. in User Working Area). Formulieren Sie bitte eine Abfrage in Relationenalgebra und in Relationenkalkül! Relationenalgebra: ANGEST[Name=’Meier’][Gehalt] Relationenkalkül: {ANGEST.Gehalt|ANGEST.Name=’Meier’} Was bedeutet funktionale Abhängigkeit? Sei R(A1,...,An), X,Y Í {A1,...,An} Y ist voll funktional abhängig von X: X® Y: es gibt keine Relation vom Typ R in der 2 Tupel denselben Wert für X aber verschiedene Werte für Y haben (==wenn 2 Tupel denselben Wert für X haben, dann haben sie auch denselben Wert für Y). Fd-Menge=Menge der funktionalen Abhängigkeiten (funcional dependencies); F+=Closure von F=Menge der funktionalen Anhängigkeiten die von F impliziert werden. Wozu dienen Normalformen? Normalformen dienen der Vermeidung von Anomalien und zur Vermeidung von Redundanz. Beispiel: LIEFER(Lieferant, Artikel,Adresse, Preis) Einfüge-Anomalie: Lieferant ohne Artikel (bisher keine Lieferung) kann nicht berücksichtigt werden. Lösch-Anomalie: Löschen eines Artikels führt möglicherweise auch zum Verlust des Lieferanten. Änderungsanomalie: Bei einer Preisänderung eines Artikels muß die ganze Relation durchsucht werden Wohin wird SQL übersetzt? SQL wird direkt vom Datenmanager interpretiert. Wozu benötigt man Tupelvariablen? Tupelvariablen sind immer dann nötig , wenn der Verbund einer Relation mit sich selbst gebildet werden soll. (siehe 2.3.10) oder dann, wenn bei einem Join von zwei verschiedenen Tabellen Attribute mit gleichen Namen auftreten. Anders ausgedrückt: Immer dann wenn innerhalb einer Abfrage verschiedene Tupel derselben Relation betrachtet werden, braucht man Tupelvariable. Wie stellt man einen Join zwischen einer Relation mit sich selbst dar? Diese Auto-Join genannte Operation gelingt mit Hilfe der Verwendung von Tupelvariablen: Relationenkalkül: RANGE ANGEST X RANGE ANGEST Y {Y.Name| (X.Gehalt > Y.Gehalt) Ù (X.Name = Y.Vorgesetzter)} Relationenalgebra: Y[Y.Gehalt > X.Gehalt][X.Name = Y.Vorgesetzter]X [Y.Name] SQL: SELECT Y.Name FROM Angest X, Angest Y WHERE X.Name = Y.Vorgesetzter AND Y.Gehalt > X.Gehalt Wie stellt man den Natural Join in SQL und in Relationenalgebra dar? Seien S(s1,..,sn,a1,..,am) und R(r1,..,rk,a1..am) Relationen mit gleichen Attributennamen a1..am die sowohl in S als auch in R vorkommen. · SQL: Select S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk Where S.a1=R.a1,..,A.am=R.am · Relationenalgebra: R NATJOIN S:=(RxS)[S.a1=R.a1,..,A.am=R.am][S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk] Wie stellt man den Join in SQL dar? Seien R(A1,.....,An) und S(B1,....,Bm) Relationen. In Relationenalgebra: R[Ai=Bj]S In SQL: SELECT A1,.....,An,B1,....,Bm FROM R, S WHERE Ai=Bj Was ist die teuerste Operation der Relationenalgebra? Der unqualifizierte Join ist die teuerste Operation, denn er ergibt das kartesische Produkt zweier Mengen und bildet somit bei zwei Tabellen der Mächtigkeiten n und m eine neue Relation der Mächtigkeit nm. Was ist das Ergebnis einer Selektion/Projektion auf einer Relation? Wiederum ein Relation. Wie werden Entitätstypen und Beziehungen in relationalen Datenbanken dargestellt? Beide werden als Relationenschemata dargestellt. Sind Abfrageergebnisse im Voraus beweisbar? Bei der Relationenalgebra ist eine sichere Bestimmung des Ergebnisses möglich, da konstruktive Regeln verwendet werden. Welche Abfragemöglichkeiten gibt es? · Relationenalgebra: Definiert Operationen auf Relationen, die neue Relationen erzeugen. Grundoperationen: Vereinigung , Mengendifferenz, kartesisches Produkt, Selektion (Auswahl bestimmter Tupel), Projektion(Auswahl bestimmter Spalten) Weitere Operationen: Join, Natural Join. Beispiel: (ANGEST[ANGNR=ANGNR]ANG_PRO)[PNR=17][NAME] · Relationenkalkül: Durch ein Prädikat (eine Bedingung) wird die Menge der gewünschten Tupel beschrieben; Beispiel: {t|q}, dabei ist t eine Liste von Attributnamen, q: Prädikat, z.B. {ANGEST.WOHNORT|ANGEST.BERUF=’Programmierer’} Welche Unterschiede gibt es zwischen Relationenalgebra und Relationenkalkül? Die Relationenalgebra stellt konstruktive Regeln zur Erzeugung neuer Relationen bereit, hier insbesondere die Grundoperationen (Vereinigung, Differenz, kart. Produkt, Selektion, Projektion) und zusätzlich die Operationen Join und Nat. Join. Der Relationenkalkül dagegen arbeitet mit deskriptiven Regeln. Mit seiner Hilfe wird die Menge der bei einer Abfrage gewünschten Tupel beschrieben indem eine Bedingung angegeben wird, die die Tupel erfüllen müssen. Was ist das relationale Datenmodell? Daten werden als Relationen (entsprechen Tabellen, Entitätsmengen) dargestellt; Zeile entspricht Entity, Spalte entspricht Attribut, Schlüssel: minimale Attributmenge die ein Tupel RÍ D1 x D2 x .... x Dn; Di: Domains, identifiziert. Relationsschema R(A1,....,An) spezifiziert eine Relation R mit den Attributen A1,....,An; jedem Attribut Ai ist ein Wertebereich dom(Ai) zugeordnet. Wie ist ein B-Baum definiert? Die Knoten eines B-Baumes sind Speicherblöcke gleicher Länge: Für einen B-Baum der Ordnung k gilt je Block mind. k, max 2k Sätze (außer der Wurzel); jeder Satz besteht aus einem Schlüssel K und einem Nichtschlüssel Teil W; Schlüssel sind aufsteigend sortiert; innerer Knoten mit m Schlüsseln hat m+1 Söhne; alle Blätter haben dieselbe Höhe h, e.g. alle Pfadlängen von der Wurzel zu den Blättern sind gleich. Wie sieht ein Index aus? Ein Index ist eine Abbildung einer Attributkombination auf Satzzeiger. DB-Tabelle A besitzt einen Index für Attributkombination B ó Tabelle A ist invertiert bezüglich B. Indextabelle: Tabelle mit Einträgen der Form (Attributwert, Zeigerliste). Indexsequentielle Organisation: mehrstufiger Index (=Index für Index); Einfügen: bei nicht dichtem Index Speicherreserve, ggf. Überlaufbereich (‘overflow pages’), in bestimmten Abständen ist eine Reorganisation nötig Wie erfolgt die Bearbeitung eines DML-Befehls? · Interpretation durch das DBMS · Ermittlung der zugehörigen konzeptuellen Beschreibung · Transformation auf internes Schema/ Ermittlung der Zugriffspfade/Queryoptimierung · Ermittlung der Datenseite (Page) · prüfen ob Seite im Systempuffer(Cache) enthalten ggf. Anforderung vom Betriebssystem · Transformation der gelesenen Daten durch das externe Schema und Bereitstellung in der UWA (user work area) des Anwendungsprogramms · Bereitstellung von Statusinformation Wie werden Operationen auf Entitätsmengen im ER-Diagramm dargestellt? Beziehungen zwischen Entities: B(E1,E2,...,Ek), Beziehungen sind meist zweistellig Wie werden Entitätsmengen und Beziehungen im ER-Diagramm dargestellt? Entitätsmengen: Rechtecke; Beziehungen: Rauten + Kanten, die die beteiligten Entitätsmengen verbinden. Wie heißt das Modell für die konzeptuelle Ebene? ER-Modell: Entity (Entitätsmenge): Unterscheidbares Objekt der Realwelt, z.B. Projekt, Kunde, Mitarbeiter (Entität: lat. das Dasein eines Dinges gegenüber seiner Wesenheit) Relationship (Beziehung): z.B. istMitarbeiterVon. Attributierter Beziehungstyp: Attribute werden einer Beziehung zugeordnet. Jeder Entitätstyp besitzt Attribute, z.B. Mitarbeiter: name, pers_nr .... Schlüssel: Attributmenge um eine Entität zu identifizieren. Komplexität von Beziehungstypen: 1:1 (z.B. verheiratet), 1:n (ist Chef von), n:m (Student belegt Kurs) Beschreiben Sie das Schichtenmodell eines Datenbanksystems! Sogenanntes Dreischichtenmodell: · konzeptuelle Ebene: logische Gesamtsicht, Zusammenfassung der Daten und ihrer Beziehungen auf logischer Ebene, Integritätsbedingungen, Beschreibung durch einen Datenbeschreibungssprache (data description Language = DDL) · interne Ebene: physische Datenorganisation; Aufbau der Sätze , Zugriffsmethoden für Sätze, Indizes, Verkettungen, interne Repräsentation der Daten - Speicherstruktur · externe Ebene: View für die/den Benutzer, Bearbeitung der Daten durch Datenmanipulationssprache (data manipulation language = DML) Was versteht man unter Datenunabhängigkeit? Darunter versteht man die Unabhängigkeit von Anwendungsprogramm und Daten. Unter logischer Datenunabhängigkeit versteht man die Isolierung der Anwendung von Änderungen des konzeptuellen Modells (es ist keine Änderung der Anwendung beim Einfügen eines zusätzlichen Attributes oder eines Beziehungstyps nötig). Physische Datenunabhängigkeit hingegen bedeutet die Isolierung der Anwendung von der physischen Datenorganisation d.h. dem internen Modell (Hash, B-Tree, Heap oder z.B. Anlegen von Indizes - Dateninversion) Welche Änderungen im konzeptuellen Schema wirken sich auf die Anwendungsprogramme aus und welche nicht: Einfügen eines Attributes, Einfügen eines Entitätstyps, Änderung des Wertebereichs eines Attributes von Integer in Real? Nur die Wertebereichsänderung wirkt sich aus. Die übrigen Änderungen wirken sich wegen der Datenunabhängigkeit zwischen Daten und Anwendung nicht aus. Was ist eine Datenbank und was unterscheidet sie von einem Filesystem? Eine Datenbank ist eine integrierte Ansammlung von Daten, die allen Benutzern eines Anwendungsbereiches als gemeinsame Basis aktueller Information dient. Mit Integration ist hier gemeint, daß die Daten entsprechend den natürlichen Zusammenhängen der Realwelt strukturiert sind und daß bestimmte Aspekte der Realwelt modelliert werden. Die Nutzung erfolgt durch viele Benutzer (die jeweils eine individuelle Sicht auf die Daten erhalten). Die Kontrolle liegt komplett beim DBMS. Bei der traditionellen Datenverwaltung mit Filesystemen definiert jeder Anwender seine eigenen Dateien (mit Sätzen die Felder enthalten). Daraus resultiert Redundanz, dadurch teures Update und Daten-Programmabhängigkeit, Inkonsistenzen sind sehr wahrscheinlich, insgesamt ist dieser Ansatz sehr inflexibel. Bei einer Datenbank hingegen erfolgt die Verwaltung der Daten zentral und es wird eine Unabhängigkeit der Daten von den Anwendungsprogrammen erreicht. Relationenalgebra: Durch welche Grundoperationen kann man den Join ausdrücken? Kreuzprodukt + Selektion Was kennzeichnet die 1. NF? Jedes Attribut ist unjteilbar (und ist v.a. nicht selbst eine Relation) Was kennzeichnet die 2. NF? Jedes Nicht-Schlüsselattribut ist von jedem Schlüssel voll funktional abhängig. Welche Anomalie vermeidet die 2. NF? Eine Lösch-Anomalie Was kennzeichnet die 3. NF? Es gibt keine Funktionale Abhängigkeit X -> A sodass X Nichtschlüssel und A Nichtschlüsselattribut ist. (Oder: Kein Attribut ist von einem anderen Attribut oder einer Menge anderer AAAttribute abhängig ausser von den Schlüsselattributen) Was kennzeichnet die BCNF (Boyce-Codd-Normalform)? Eine Relation ist in BCNF, wenn für jede Funktionale Abhängigkeit X -> A X einen Schlüssel enthält. Wie kann man eine Relation, die eine Normalform nicht erfüllt, in eine Relation überführen, die eine Normalform erfüllt? Durch Zerlegung. Welche Basisoperationen hat die Relationenalgebra? Vereinigung A u B Differenz A - B Kreuzprodukt A x B Projektion A[a,..] Selektion A[a=b, ...] Welche Operationen kennt die Relationenalgebra über die Basisoperationen hinaus? Umbenennung A(aa<-a) Join A[a=b]B (= sei Theta) Natural Join A NATJOIN B