cse233--Database Theory

CSE 233

Database Theory

Spring 2022

Instructor: Victor Vianu
Email: vianu@ucsd.edu
Phone: 858-534-6227
Lecture: Tuesday and Thursday 5:00-6:20pm (CSE 2154)
Office hours: Tuesday, Thursday 6:30-7:30pm (CSE 4238)

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.

Text: Foundations of Databases
by S. Abiteboul, R. Hull, V. Vianu, Addison-Wesley, 1995.
Online version

Another useful reference:
L. Libkin: Elements of Finite Model Theory, Springer 2004
Online version

Homeworks

Homework 1 due April 14 (in class).
Latex source

Homework 2 due April 26 (in class).
Latex source

Homework 3 due May 5 (in class).
Latex source

Homework 4 due May 17 (in class) extended to May 19
Latex source

Homework 5 due May 31 (in class)
Latex source

Take-home final exam

pdf, latex
Please email the pdf to me as soon as you are done, but no later than Sunday, June 5, 11:59pm. Have fun !

Piazza We will be using Piazza for class discussion. All class materials will continue to be posted on this class web page (not Piazza). Find our Piazza class page here and go to Q&A to post or answer questions. Please make sure you are registered.

Slides and other resources
Introduction
SQL review
Syntax and semantics of relational calculus
Datalog-neg

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

Impact of order Ch. 17.4

Nondeterministic languages Ch. 17.4, p.453

Highly expressive languages Ch. 18

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
Impact of order	Ch. 17.4
Nondeterministic languages	Ch. 17.4, p.453
Highly expressive languages	Ch. 18

Integrity of Scholarship You are assumed to be familiar with the UCSD Policy on Integrity of Scholarship and the course policy as described here. All students en in this course implicitly agree to abide by the policies described in this document. If you have any questions about these policies, be sure to discuss them with me.