|
Logische Grundlagen der Datenbanktheorie (LGruDat)7.5 ECTS (englische Bezeichnung: Logical Foundations of Database Theory)
Modulverantwortliche/r: Tadeusz Litak Lehrende:
Tadeusz Litak
Start semester: |
WS 2013/2014 | Duration: |
1 semester | Cycle: |
jährlich (WS) |
Präsenzzeit: |
56 Std. | Eigenstudium: |
169 Std. | Language: |
Deutsch und Englisch |
Lectures:
Empfohlene Voraussetzungen:
It is recommended to finish the following modules before starting this module:
Grundlagen der Logik und Logikprogrammierung (SS 2013)
Inhalt:
We will discuss the theoretical foundations of databases, starting with the underlying data model. We will focus mostly on various flavours of the relational model (calculus vs. algebra, named vs. unnamed variant etc.) and its real-life SQL incarnation, but other models, in particular semistructured databases and their real-life XML incarnation will also get their share of attention. We will investigate the connection between databases and finite model theory and overview some most interesting results in the field. Logical issues in the design of database query languages, in particular expressive completeness, but also questions of decidability and complexity will be of particular importance. Same applies to the use of logical tools for database-theory purposes, from Ehrenfeucht-Fraisse games to Herbrand structures.
Lernziele und Kompetenzen:
- Wissen
- The students will learn basic notions and results of finite model theory, with particular attention to notions and theorems relevant for database theory and essential characteristics of expressivity, decidability and complexity. As prerequisites, we will also recall and overview basics of SQL, relational algebra or XML query/navigation languages like XQuery and XPath.
- Verstehen
- The students will be able to summarize and prove major results of finite model theory and related areas relevant from the database point of view. Examples include equivalences between relational calculus and relational algebra, named and unnamed perspective, expressive completeness of relational calculus and similar results for XPath and XML query languages.
The students will be able to explain the deep difference between finite and infinite model theory, by using 0-1 laws or by showing the failure of most preservation theorems. - Anwenden
- The students will be able to use basic tools of finite model theory (and related areas relevant from a database point of view), such as Ehrenfeucht-Fraisse games or Herbrand structures.
The students will use preservation theorems of Rosen or Rossman to characterize expressive power of logics over finite structures. - Analysieren
- The students will be able to determine, e.g., whether a given SQL-like or XPath-like query is expressible over all finite models (or restricted subclasses of structures) in a chosen language.
- Evaluieren (Beurteilen)
- The best students, having gained a deep understanding of finite model theory, will be able to examine and evaluate choices involved in the design of basic database query languages, with particular attention to the criterion of expressive completeness and contrasting expressive power of a given language with its computational complexity.
- Erschaffen
- Making the right design choices is an important skill whenever the need arises to develop a new domain-specific language. One can think of database query languages just as an excellent case study given their omnipresence in everyday life.
Literatur:
Leonid Libkin, Elements of Finite Model Theory, Springer 2012 Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995. Heinz-Dieter Ebbinghaus, Jörg Flum, Finite Model Theory, Springer 1995 Serge Abiteboul, Peter Buneman, Dan Suciu: Data on the Web : From Relations to Semistructured Data and XML. Morgan Kaufmann 1999 Supplementary reading on databases: Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom, Database Systems: The Complete Book, Prentice-Hall 2008.
Jeffrey D. Ullman, Jennifer Widom, First Course in Database Systems, Prentice Hall 2008
Raghu Ramakrishnan and Johannes Gehrke, Database Management Systems, McGraw-Hill 2007
Weitere Informationen:
www: http://www8.informatik.uni-erlangen.de/ws13:lgrudat
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Informatik (Master of Science)
(Po-Vers. 2010 | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsmodul Theoretische Informatik)
- Informatik (Master of Science)
(Po-Vers. 2010 | Wahlpflichtbereich | Säule der softwareorientierten Vertiefungsrichtungen | Vertiefungsmodul Datenbanksysteme)
Studien-/Prüfungsleistungen:
Logische Grundlagen der Datenbanktheorie (Prüfungsnummer: 102249)
(englischer Titel: Logical Foundations of Database Theory)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet
- Anteil an der Berechnung der Modulnote: 100.0 %
- weitere Erläuterungen:
Die Übungsleistungen (Bearbeitung von Übungsaufgaben) gehen zu 50% in die Note der mündlichen Prüfung mit ein.
- Erstablegung: WS 2013/2014, 1. Wdh.: SS 2014 (nur für Wiederholer)
|
|
|