Reasoning in Databases
COSC-6490-E
Winter 2001
York University

Semester: winter 2001
Course/Sect#: COSC-6490-E
Time: Mon 5:30-7:00pm
Wed 5:30-7:00pm
Location: South Ross 104
Instructor: Parke Godfrey
Office: 220 CCB
Office Hours: Mon 4:00-5:00pm
Wed 4:00-5:00pm
and by appointment
Ph#: 416-736-2100 x70128
e-mail: godfrey@cs.yorku.ca

Wecome to the Reasoning in Databases course, COSC-6490-E, for winter term 2001. Materials, instructions, and notices for the course will accumulate here over the semester.

In this course, we will study semantics, reasoning tasks, and decision problems that are relevant to database design, queries, optimization, and mining. Our focus will be on the computational complexities and decidability of, correspondences among, and implementation approaches to these tasks.

Class Bulletin Board

  • Starting Part III, Query Containment / Folding.
  • Assignment #1 due date shifted to Wednesday 11 April.

Materials

  • Syllabus
  • Papers (Sorry. Limited to cs.yorku.ca access for copyright reasons.)
  • Projects / Presentations / Reports
  • Assignments
    • Assignment #1 on logic programming and deductive database semantics
      PS, PDF
      Due Wednesday 11 April.
  • Lectures available on-line
    • Database Semantics: State-of-the-Practice versus State-of-the-Art
      (Parke Godfrey & Irina Kogan, January 2001, 19 slides)
      PS, PDF
    • Prologue to Prolog 101
      (Parke Godfrey, October 1994, 18 slides)
      PS, PDF
    • Conjunctive Queries & Containment
      Lecture notes of Jeffrey Ullman (Standford University) on Principles of Database Systems.
      (Lecture notes below mirrored from Professor Ullman's site.)
      • Introduction (8 slides)
        PS, PDF
      • Containment Tests (18 slides)
        PS, PDF
      • With Negation (17 slides)
        PS, PDF
    • View Disassembly: Addresses questions of containment of datalog without recursion in datalog
      (Parke Godfrey & Jarek Gryz, October 1998 / January 1999, 19 slides)
      PS, PDF
    • Hypergraphs
      Lecture notes of Jeffrey Ullman (Standford University) on Principles of Database Systems.
      (Lecture notes below mirrored from Professor Ullman's site.)
      • Acyclicity (12 slides)
        PS, PDF
      • Universal Relation (13 slides)
        PS, PDF
    • Cooperative Query Answering
      (Parke Godfrey, 1997 / 1999, 12 slides)
      PS, PDF
  • Code available on-line
    • miss.pl: A prolog solution for the Cannibals-and-Missionaries puzzle.
    • stones.pl: A simple prolog (Quintus) implementation for the game of stones in Assignment #1.
    • stones_eff.pl: A slightly less simple prolog (Quintus) implementation for the game of stones in Assignment #1. It is much more efficient, and it has an explainer predicate that prints the proof tree for a winning strategy.
    • contain.pl: A really old (1992!) program I wrote to do conjunctive query containment and other related tasks. Simplistic, never completed, but somewhat neat.

    For running prolog, refer to the Prologue to Prolog 101 lecture notes. The command to start Quintus Prolog around here is, surprise, prolog. To leave: ^D.

Parke Godfrey