hüfungsteitnehmer Prüfungsternin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 1999 66113 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Eirzelprüfung: Rechnerarchitektur,Datenb.,Betriebssys. Anzahl der gestelltenThemen(Aufgaben): 2 Anzahlder DruckseitendieserVorlaee: 9 Bitte wenden! Frühjatrr t999 Eirzelpnifungsnummer:66113 Seite:2 Thema Nr. I SämtlicheTeilaufgabensind zu bearbeiten! Teilaufgabe 1: Betriebssystemeund Systemprogrammierung a) Virtuelte Adressen (i) Wann tritt ein Seitenfehler(pagefault) aufl (ii) BeschreibenSie die Aktionen, die dasBetriebssystemnachAuftreten einesSeitenfehlersausführen muss! b) Plattenspeicherzugriffe Welche Kriterien sind bei der Auswahl einer Plattenspeicher-Zugriffsstrategie zu beachten? c) Dateisystem (r) Was sind die wesentlichenAufgabenehes Dateisystems? (ii) Erläutem Sie die folgendenBegriffe und ihren Zusammenhang an Hand einesder Betriebssysteme:Unix, Windows oder NT - (iii) Datei Katalog (Directory) baumförmiger Namensraum Pfad in diesem Namensraum Partition GebenSie einenÜberblick über die wesentlichenDateiattribute(in dem von Ihnen gewählten Betriebssystem).Wie werdendieseDateiattributeverwaltetund was ist jeweils ihre Funlcion? FortsetzungnächsteSeite! Frühjahr L999 Einzelprüfungsnummer : 661L3 Seite:3 Teilaufg abe 2 z Datenbanksysteme a) Relationales Modell (i) RelationalesDatenmodell Nennen und erläuternSie kurz die drei grundlegendenrelationalenOperatoren! Erläutern Sie informell die Begriffe: Schlüsselkandidat,Prirnärschlüssel,Fremdschlüsselund referentielleInteerität! (ii) sQl-Anfragen Für den Einkauf in einer Maschinenfabrik wird foigende Datenbank zur Verwaltung der Beständeverwendet: LIEFERAIIT (Namg" Firrren sitz, Ansprechpartner) TEIL (Teil-Id, Bezeichnung) LIEHERUNG @, Lieferdatum, sttickzahl) Die Primärschlüsseider Relationen sind unterstrichen.Lieferant-Id in LIEFERUNG ist Fremdschlüsselzu Name in LIEFERANT. Teil-Id in LIEFERTING ist Fremdschlüssel zu Teil-Id in TEIL. Formulieren Sie die folgenden Datenbankoperationenin sel-. Welche Lieferanten haben ihren Firmensitz inErlangen, Nürnberg oder Fürth ? Wie sind die Bezeichnüngen der Teile, bei denen eine Liefemng weniger als 10 Sräck umfasste? was bedeutetumgangssprachlichfolgende Anfrage: selectlf.Name from Lieferant if, Lieferung lg, Teil t where lf.Name = lg.Lieferant-Id and t.Teil-Id = lg.Teil-Id and t.Bezeichung= 'Bolzen' and lg.Stückzahi> 1000 FortsezungnächsteSeite! Frühjahr 1999 Einzelprüfungsnummer: 66113 Seite:4 b) Normalisierung einer Relation (i) Aus welchen Gründen wird eine Relation normalisiert? (ü) Definieren Sie kurz die Eigenschaften einer Relation in erster. zweiter und dritter Normaiform? (iii) Bringen Sie die folgende Relation Verkäufe(Anr.Bezeichnung,Verkäufer (Verkäufername, Geburtstag, Geschäft , Geschäftsflihrer, Anzatrt) ) in die erste,zweite und dritte Normalform. Verkäufe Aqr Bezeichnung 47tr Video x Verkäufer fferkäufername Geburtstag F. Meier 12.t2.50 Television Geschäft Geschafts- Anzahl) führer Maier 22 Maier 11 Maier ) Maier 17 2000 H. Müller 0 1 . 0 i . 5 5 Television 2000 471 2 Radio y F. Huber 1 0 . 1 0 . 6 0 Television 2000 4713 Monitorz H. Anton 02.42.65 H. Nie 08.08.70 Compu Television 2000 Schmidt 100 F.Immer 09.a9.75 Compu Schmidt 3t 100 c) Transalitionsko ruept (i) (ü) Transakrionseigensöhaften Benennen und erläutern Sie die klassischen Eigenschaften, d.ie von Datenbanktransaktiongefordert werden ! einer Recovery Im Datenbankbereichkönnen 4 klassischeFehlerartenunterschiedenwerden. BeschreibenSie die Fehlerartenund die Recoverymaßnatrmen,die notwendig werden, um die Transaktionseigenschaftensicherzustellen. (iil) hotokollierung Zur Sicherung der Transaktionseigenschaftenmuss das Datenbanksystem Protokollinformationen sammeln, die zur Wiederherstellung der Datenbank im Fehlerfalt dienen. Die dabei verwendeten Protokollierungsverfahren werden in physische und logische Protokollierverfatren eingeteilt. CharakterisierenSie beide Verfahren kurz und beschreiben Sie die jeweiligen Vor- und Nachteile. FortsetzungnächsteSeite! Früt{atr L999 Eirzelprüfungsnumme r : 66It3 Seite:5 Teilaufgabe3: Rechner-und Kommunikationsarchitektur a) Lokale Netze (i) Die Schicht2 desISOiOSl-Referenzmodells wird bei lokalenNetzenin zweiUnterschichren unterteilt. Wie heißendie zwei Schichten? (ii) warum ist es sinnvoll, zwei unterschichtenzu haben? (iii) Welchessind die Standard-Dienste der einen,welchesdie Standard-Dienste der anderen Schicht? b) Kooperation durch Nachrichtenaustausch (i) (ii) Bei der Übermittlungvon NachrichtenkönneneineReihevon Fehlernpassieren,die zu einer VerfälschungdesInhaltsoder gar nrm Verlust der Gesamtnachricht führen. Um welcheFehlerhandeltes sichhierbei? Nachdem ein lj.bermittlungsfehler erkannt wird, wird die Korrektur normalerweise durch die Wiederholungder Nachricht erreicht. WelcheMechanismenkennenSie. um die Wiederholung der Nachricht auszulösen? BeschreibenSie kurz, wie die Mechanismenarbeiten. (iü) wenn die Konununikationszeitenin einemNetzwerk schwanken,kann espassieren,dass Nachrichtensich gegenseitigüberholen.WelcheMechanismenkann man benutzen,um dieses Problemzu lösen? Erläutern Sie knappdie grundsätzlichenPrinzipiender Verfahren. -6 Frühjatrr1999 Einzelpnifungsnummer : 66113 Seite:6 Ihema Nr. 2 Sämtliche Teilaufgaben sind zu bearbeiten! Teilaufgabe 1: Normalformen Gegeben sei die folgende relationale Datenb ank Buch, in der die Bücher und Autoren eines Verlagesverwaltet werden. JedesBuch hat eine eindeutige Numm er (BNr). Ein Buch kann von mehrerenAutoren verfal3twerden und wird einem bestimmten Gebiet zugeordnet.JederAutor ist durch seineNummer (Anr) eindeutig bestimmt. Im Attäbut Fnrwerden die Bücher eines Autors fortlaufend durchnumeriert. Neben dem Datum werden die Anzaht derSeiten und der Preiseines Buchesbei jeder Auflage neu fesrgelegt. Axr Autor Titel Auflase Gebiet i 1 Lattg Datenbanlsysteme 1 DBS 1 t996 448 68,- 1 2 Reiter Datenbanlsysteme i DBS I L t996 448 68,- 2 I Lang OODB 1 DBS 2 1994 356 1 Dedos Deductive Databases 1 DBS 1 1991 414 62,'/0,- J Dedos Deductive Databases 2 DBS 1995 435 75,- Lattg Programmierungin C 1 PRO 1 ., 1998 267 58,- 1 PRO 2 1997 236 49,- I KI J 1999 567 87,- h 'l 5 Ä Fnr Datum Seiten heis + I 5 1 Dedos 6 J Dedos L 1 Lang OODB 2 DBS 2 1997 425 60,- 7 4 Meyer Einfährung in die Informatik 1 ALL I 1993 347 36,- 8 5 Reiter Infonnatik tr 1 ALL 1 1993 198 15,- 8 5 Reiter Informatik II ) ALL 1 r996 270 2L,- Reiter Infonnatik tr ALL 1 I r 1997 LJJ ALL 2 1996 896 136,- ALL 2 1996 896 136,- 8 Logic hogramming Expertensysteme 9 5 Reiter Lexikon Informatik I 9 .+ Meyer Lexikon Infonnatik 1 t I a) Beschreiben Sie kurz, welche Redundanzen (i) bei mehreren Auflagen und (ü) bei mehreren Autoren eines Buches in der Datenbank vorhanden sind. b) Welche Typen von Anomalien können bei diesem Relationenschemaauftreten? Geben Sie jeweils ein Beispiel an. c) Geben Sie für obige Datenbank alle vollen funktionalen Abheingigkeitenan. d) Zeigen Sie anhaad eines Beispiels, dassdie obige Datenbank die dritte Normalform verletzt. e) Überfütren Sie das Schema in die dritte Normalform. Skizzieren Sie die resultierende Datenbank indem Sie die Schlüsselwerteder Tupel in die neuenTabelleneintragen. Geben Sie ein Entiry-Relationship-Diagrarnm an, das die Stnrktur des neuen Schemas erkennen lässt.One-to-many Relationships werden tr <-Odargestellt,bei many-to-many Relationshipssind die Kanten ungerichtet. s)GebenSie eine SQl-Anweisung für die Datenbank in dritter Normalfonn an, die eine Sicht auf das ursprüngliche Schema definiert. h) Erklären Sie kurz, welchen Nachteil Normalisierung allgemein frir die Anfragebearbeirunghat. Fortsetzung nächste Seite! Fnihjahr 1999 Einzelprüfungsnummer: 66113 Seite:7 Teilaufgabe 2: Relationale Anfragen Das folgenderelationaleSchemabeschreibteine Getränkedatenbank, in der dasAagebot verschiedenerLokale verwaltetwird. Zu jeder sorte, die eindeutigdurchdie Nummer(,snr) bestimmtist, wird derNamedesHerstellers(Hname),derSortenname(Jnarze)sowiedie kcal pro Liret (kcal-Iiter) gespeichert.Femer besitztein Herste er keine Sortenmit demselbenNamen. JedesLokal hat einenNamen(Iname) und ist mit Postleitzahl(PID rnd Ol'r in der Datenbark enthalten.Die RelationAngebotbescheibt, zu welchemPrarsein Lokal ein bestimmtesGeüänk verkauft.Der Preisbeziehtsichjeweils auf einenviertel Liter. Sone (Snr,Ilname, Sname,kcal-Iirer) Angebot(Ss, Iar, Preis) Lokal (Lar, PLZ, Ort, Lname) - a) RelationaleAnfragesprachen FormulierenSie die folgendenAnfragen in zwei der vier Anfragesprachen: rel.ationaleAlgebra, relationaler TupelkalküL,spz und euel. Beiyerwendung von ser, o dereuel sind dre Duplikate zu enffemen.Gebensie DISTINCT bzw. uNIeuE für s eLbzvr. euel nur ar, wewr Duplikate auftretenkönnen. (i) Bestimmedie Namenalier Sorten,die in MünchnerLokalen angebotenwerden. '(ii) Gibt esSortennamen,die von verschiedenen Herstellemverwendetwerden?GebenSie alle Datender entsprechenden Sortenaus. (iü)Bestimmedie Namender SortendesHerstellersXYZ, die in keinemLokal teurer ais 5.DM sind. b) Aggregatfunktionen FormulierenSie die foigendenAdragen in S@L.VerwendenSiedabeidie Aggregath:nktionen avg, count, min odermax. (1) Bestimmeden durchschnittlichenPreis,zu dem die Sortemit Nr. 27 in Mänchenangeboten wird. (i1) Bestimmefär jeden Herstelier den maximalenGehaltan kcal pro Liter aller hergestellten Sorten. (iü) Hen Schmidtsuchtin seinerUmgebun (PI-Z 80428)ein Lokal, bei demder Preis für die e Sortemit Nr. 4 unter dem MänchenerDurchschnittsprcisfih diesesGetänk liegt. Geben Sie eineListe der entsprechenden Lokale aus. FortsetzungnächsteSeite! Frtihjahr 1999 Einzelprüfungsnummer: 66113 Seite:8 Teilaufgabe3: Speicherhierarchie a) Motivieren sie die Einftihnrng von Speicherhierarchien. b) Nennen Sie die gnrndlegendeVoraussetzungfär deren sinnvolle Verwendung. c) Geben Sie eine typische Hierarchie mit den zugehörigen - 5 ------- -Jr --' und Größen- bzw. ') -- Speichertypen Zugriffszeitbereichänan. , d) Ordnen Sie Caches in die Speicherhierarchieein, falls nicht bei Beantworfung der vorigen Teilaufgabebereitserfolgt. e) Beim schreibendenZugnff auf einen Cachekann man bzgl. der Behandlung des Hauptspeichers zw ei Organisationsfonnen unterscheiden: write through: Bei jedem Schreibvorgangwird auch der Hauptspeicheraktualisiert (auch als store through bekannt). write back: Hauptspeicher nur aktualisiert, wenn nötig (auch als copy back, write later bezeichnet). Diskutieren Sie Vor- und Nachteile beider Verfatren. Benicksichtigen Sie dabei auctr Mehqprozes sor-Anlagen. f) Für den FaIl eines write miss (benötigter Block für schreibendenZugnff nicht im Cache) bestehenzweiprinzipielle Optionen: ' Write allocate.'Der Block wird in den Cachegeladenund dort geändert. ' No write allocate: Der Block wird direkt im Hauptspeichermodifi ziertund nicht in den Cache geladen. Obwohl natürlich prinzipielt beide Optionen sowohl bei write through als auch bei write back verwendet werden können, wird in der Regel jeweils eine der Optionen bevorzugt. Welche? Warum? Teilaufgabe 4: Adressierungsarten a) Welche Befehlsadressformatekennen Sie? BeschreibenSie dieseund charakterisierenSie die wesentlichenUnterschiede. b) Nennen Sie wenigstens5 Adressierungsfonnenund beschreibenSie diesegenauer. FortsetzungnächsteSeite! Fnihjatrr L999 Einzelprüfungsnummer: 661t3 Seite:9 Teilaufgabe 5: parallete Rechensysteme a) Nennen Sie die wesentlichenUnterschiedezwischeneinem SIMD- und einem MIMD-Rechner. b) Beschreiben Sie Vor- und Nachteile eines Mehqprozessorsysremsmit gemeinsamen Hauptspeicherim Vergleich zu einem solchenmit lokaien Speichernfür jeden Prozessor. c) Erläutern Sie die Unterschiedezwischen einem eng-gekoppeltenund einem lose-gekoppelten Mehrprozessorsystem.