CENG 550 : Logic and Databases
==============================
Instructor: Assoc. Prof. Ismail Hakki Toroslu
===========
Course Outline:
===============
Week 1:
-------
Relational Databases, Relational Algebra and Relational Calculus [U]
Week 2:
-------
Prepositional Logic and First Order Predicate Logic
(syntax, semantics, model and proof) [L]
Week 3:
-------
Logic Programming-Proof Theory: Unification, Resolution,
Resolution Strategies and Refutation Completeness, Theorem Proving [L]
Week 4:
-------
Logic Programming-Model Theory: Herbrand Interpretation, Herbrand's Theorem,
Alternative Semantics (Declarative, Fixpoint, Procedural) [L]
Week 5:
-------
Database Theory, Horn (Definite) Databases [C]
Week 6:
-------
HOLIDAY
Week 7:
-------
Query Processing [R]
Week 8:
-------
Mid Term Exam (in-class, open book)
Week 9:
-------
Query Evaluation Techniques for Datalog: Bottom-up approach
(Naive and Semi-Naive Algorithms) [L,U]
Week 10:
-------
Query Evaluation Techniques for Datalog: Top-down approach [L,U]
Week 11:
--------
Query Optimization: Compiled Approach (Henschen-Naqvi Technique) [HN]
Week 12:
--------
Query Optimization: Combining Bottom-up and Top-down Techniques: Magic Sets [U]
Week 13:
--------
Negation [U2]
Week 14:
--------
Student Presentations
Week 15:
--------
Project Demonstrations
Finals:
-------
Final Test (in-class, open book)
Objectives:
===========
As the name of the course implies, it is about logic and databases.
It is designed for the students who are working in the field of the
databases, especially on the database theory, and on the deductive
databases. Logic programming has contributed to the understanding of
the semantics of databases. Therefore, the tools of logic programming
can be used in order to extend the theory of the databases. The first
half of the course will be on logic, and logic programming, which are
the formal foundations of the relational and deductive databases.
The second half will be on the application of these foundations on
the deductive databases and implementation related issues related of
the deductive database management systems, such as query processing.
References:
===========
[L] J. W. Lloyd, Foundations of Logic Programming, Springer-Verlag, 1993.
[U] J. D. Ullman, Principles of Database and Knowledge-Base Systems,
Volume II, Computer Science Press, 1989.
[R] R. Reiter, Equality and Domain Closure in First Order Databases,
J. ACM, Vol. 27, No. 2, April 1980, pp.235-249
[HN] L. J. Henschen, S. A. Naqvi, On Compiling Queries in Recursive
First Order Databases, J. ACM,Vol. 31, No. 1, Jan. 1984, pp. 47-85.
[C] Class notes
[U2] J. D. Ullman, Assigning Appropriate Meaning to Database Logic With
Negation, http://www-db.stanford.edu/~ullman/pub/negation.ps
Grading:
========
Mid Term Exam: (25 %) In-class exam (Open books and notes)
Final Exam: (25 %) In-class exam (Open books and notes)
Programming Project: (25 %) Implementation of some algorithms + reports
Presentation: (25 %) 20 min. Survey presentation + reports + handouts
Some Survey Topics:
===================
Action Logic
Transaction Logic
More on Magic Sets
Disjunctive Logic Programming