Instructor: Dr. Leonid Libkin
E-mail: libkin@research.bell-labs.com or libkin@cs.nyu.edu.
Phone: (908) 582-7647
Office hours: Thu 7-8pm, 401 WWH

Topics: Database management systems, relational database model, formal relational query languages (relational algebra and calculus, datalog, and others), practical query language SQL, database design, dependencies and normalization, query optimization, expressiveness and complexity of languages, and one or two current topics, as time allows.

Required text: Foundations of Databases by S.Abiteboul, R.Hull and V.Vianu, Addison Wesley, 1995.

Recommended text (mostly for database design and SQL topics): A First Course in Database Systems by J.Ullman and J.Widom, Prentice Hall, 1997.

Midterm (25%)
Homeworks (35%)
Choice of final exam or term project (40%)

If you choose term project, please see the instructor during office hours.

Prerequisites: Basic knowledge of discrete mathematics, computability, complexity, logic, and programming languages. Chapter 2 in the required text should provide sufficient theoretical background.