Email:

Phone: 858-534-6227

Lecture: Tuesday and Thursday 5:00-6:20pm (zoom link will be provided)

Office hours: Tuesday 6:30-7:30pm, Thursday 3:30 - 4:30pm (zoom)

This course will present an overview of the theory of databases. Topics include the theory of query languages, dependency theory, deductive databases, incomplete information, complex objects, and other advanced topics and research issues as time allows. Connections will be made to relevant areas in logic and complexity theory. Evaluation will be based on homework sets and a take-home final.

by S. Abiteboul, R. Hull, V. Vianu, Addison-Wesley, 1995.

Online version

L. Libkin: Elements of Finite Model Theory, Springer 2004

Online version

- Homework 1 due April 16.

Latex source

- Homework 2 due April 28.

Latex source

- Homework 3 due May 12.

Latex source - Homework 4 due May 22.
**extended to May 23**

Latex source

- Homework 5 due June 3

Latex source

Introduction

The relational model

Syntax and semantics of relational calculus

**Readings**

*All readings are from the Foundations book unless otherwise noted.*

Topic | Reading |
---|---|

Theoretical background |
Ch. 2 |

CALC |
Ch. 5.3 |

Relational algebra |
Ch. 5.1 |

Undecidability of SAT-fin |
Ch. 6.3 |

Conjunctive queries |
Ch. 4 |

Conjunctive query minimization |
Ch. 6.2 |

nr-Datalog-neg |
Ch. 5.2 |

Functional dependencies |
Ch. 8.1 |

Multivalues dependencies | Ch. 8.3 |

The Chase |
Ch. 8.4 |

Inclusion dependencies |
Ch. 9 |

Ehrenfeucht-Fraisse games |
Ch. 17.2, also Ch. 3 in Libkin |

0-1 Laws |
Ch. 17.3 (p.440), also Ch. 12 in Libkin |

Datalog |
Ch. 5 |

Datalog-neg |
Ch. 14.3, 15 |

while and while+ |
Ch. 14.1 |