CSc 8710. Deductive Databases and Logic Programming
Fall 2002, Tuesday/Thursday 7.15 to 8.55 PM, Room: 331 G (General Classroom Building)
Computer Number: 80974

Course Overview: An introduction to area of deductive databases and logic programming. Topics include: Logic programming and Prolog, Syntax of logic programs and deductive databases, Model-theoretic, Proof-theoretic and Fixpoint semantics, Operational semantics such as bottom-up evaluation and SLD-resolution techniques, Query optimization in deductive databases, Negation in deductive databases, Applications of deductive databases, Constraint checking in deductive databases.

Textbooks
  1. Logic programming and databases by Ceri, Gottlob and Tanca, Springer-Verlag, 1990. - It appears to be out of print. I will provide materials for topics covered from this book.
  2. Logic, Programming and Prolog, Ulf Nilsson and Jan Maluszynski (2nd Edition), 2000. Online Edition. Individual Chapters will be provided. To save trees, kindly print only the chapters we will cover in class. For reference, you may keep the online text with you.
  3. Oracle Programming -- A Primer by R. Sunderraman, Addison-Wesley, 1999.
Grading Policy: The grading will be based on the following components:
  1. Three exams worth 25% each
  2. Homework assignments and Programming Projects worth 25%.
The final letter grade will be determined based on the following criteria:
A 90 and above
B 80 thru 89
C 65 thru 79
D 50 thru 64
F less than 50

Detailed Course Syllabus

  1. Preliminaries:
    • Relational Databases (relational algebra, SQL, embedded-SQL, JDBC, SQLJ)
    • Logic Programming in Prolog
  2. Deductive Databases and Logic Programming--Basics:
    • Syntax of logic programs and deductive databases
    • Semantics: Model-theoretic, Proof-theoretic, Fixpoint semantics
    • Evaluation Strategies:
      • Bottom-up evaluation (Naive,Semi-Naive)
      • Top-down evaluation (SLD-resolution)
  3. Deductive Databases--Advanced Topics:
    • Query optimization
    • Negation in deductive databases
    • Applications of deductive databases
    • Constraint checking in deductive databases

Last date to withdraw: 11 October, 2002.

Academic Honesty Policy:
All work submitted for grading must be student's own work. Plagiarism will result in a score of zero on the test or assignment, or dismissal from the course.

NOTE:
This syllabus represents a general plan for the course and deviations from this plan may be necessary during the duration of the course.

Dr. Raj Sunderraman
8/20/2002