CSc 8710. Deductive Databases and Logic Programming
Fall 2005, Tuesday/Thursday 7.15 to 8.55 PM, Room: 303 ALC (Aderhold Learning Center)
CRN: 86514

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 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.
  2. Notes/papers will be provided
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, relational calculus, non-recursive Datalog, SQL, JDBC)
    • Mathematical Logic (propositional and predicate logic, model theory)
  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
  4. Data Mining
    • Association Rules
    • Classification/Clustering
    • Web Mining

Last date to withdraw: 14 October, 2005 (Friday).

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/22/2005