Architecture and Implementation of Database Systems (SS 99)

Prof. R. Bayer, Ph.D.

Lectures per Week: 3
The whole course will be taught in English.

Time and Place: Wednesdays 13 - 14, S 1128
Thursdays 10 - 12, S 1128

Start: May 5, 1999

Diese Vorlesung gehört zum Hauptstudium im Bereich Informatik I und ist eine vertiefende Vorlesung zum Musterstudiengang Datenbanksysteme. Die gesamte Vorlesung wird in englischer Sprache gehalten.

Skript: entsteht inkrementell begleitend zur Vorlesung

Literature:

• Härder, T., Rahm, E.: Datenbanksysteme - Konzepte und Techniken der Implementierung, Springer-Verlag, 1999
• W. Kießling, G. Köstler: Multimedia-Kurs Datenbanksysteme, Springer Verlag 1998
• C. Date: An Introduction to Database Systems, Vol. I, II, Addison-Wesley
• J. Ullman: Principles of Database and Knowledge-Base Systems, Vol. I, II, Computer Science Press
• J. Gray, A. Reuter: Transaction Processing: Concepts and Techniques (1993), Morgan-Kauffman, San Mateo, USA
• Lockemann, P.C., Schmidt, J.W.: Datenbank-Handbuch, Springer-Verlag, 1987
• Härder, T.: Implementierung von Datenbanksystemen, Hanser-Verlag, 1978
• Mitschang, B.: Anfrageverarbeitung in Datenbanksystemen: Entwurfs- und Implementierungskonzepte, Vieweg, Reihe Datenbanksysteme, 1995
• Bernstein, P.A., Hadzilacos, V., Goodman, N.: Concurrency Control and Recovery in Database Systems, Addison-Wesley Publ. Comp., 1987
• G. Wiederhold: File Organization for Database Design, McGraw-Hill Publ. Comp, 1987
• Elmasri, R., Navathe, S.B.: Fundamentals of Database Systems, Benjamin/Cummings Publishing Company, 1994
• A. Heuer: Objektorientierte Datenbanken, Addison Wesley, 1992
• A. Kemper, A. Eickler: Datenbanksysteme, Eine Einführung, Oldenbourg 1996
• Laplante, P.: Great Papers in Computer Science, West Publ. Co., 1996

Sprechstunde:
Orleansstr. 34, Raum O108, Telefon 48095-171

Table of contents

1.  Introduction

1.1  Tasks of a DBS

1.1.1  Provide the DBS-model

1.1.2  Multiuser Mode of Operation and Transactions

1.1.3  Parallel Execution of Transactions

1.1.4  General Architecture of a DBS

1.1.5  User Requirements

1.2  File-System

        Physical Disk Storage

        Operations of PPS

        Abstract peripheral disk store: APS

        Motivation for ABS:

        File-Interface, File-System

        Architecture of File-Systems

        Tasks of the I/O-systems

        Tasks of the File-System

1.3  Unix File System

        PPS-Interface

        Block-SS

        Cache-SS

        i-Node-SS

        Directory and File-SS

2.  Representation of DB-Models

2.1  Model-Comparison

2.2  File Management

2.3  Useage of Indexes

2.4  Genuine Prefix B-Trees

3.  Query-Oprimization

3.1  Algebraic Optimization

3.2  Non-algebraic Optimization

3.2.1  Complexity of relational Algebra

3.2.2  Relations, Bags, Tables

3.3  Operator Trees

3.4  Complexity of relational Algorithms

3.5  Selecitvity of Operations

3.6  Cost Functions

3.7  TID-Algorithms

3.7.1  Selections

3.7.2  Join

4.  Parallel Transactions and Execution Control

4.1  Concept of Transaction

4.1.1  Syntax

4.1.2  Interleaving and Anomalies

4.2  Serializability

4.3  Synchronization

4.4  Synchronization and Lock Management

4.4.1  Data Struktures for Lock Management

4.4.2  Trans. Hull in O(n*m)

4.4.3  Trans. Hull on-line

4.5  Lock Modes and Synchronisazion

4.6  Lock-Hierarchies

4.7  Optimistic Synchronization

4.8  Optimistic synchronization

5.  Management of Errors and Failures

5.1  Problem Formulation

5.2  Variants of Logging

5.2.1  BFIM-page-logging

5.2.2  BFIM/AFIM-page-logging

5.2.3  Shadow Concept on phys. DB

5.2.4  Cache/Safe Method