COMP202P - Logic and Database Theory

This database contains the 2017-18 versions of syllabuses. Syllabuses from the 2016-17 session are available here.

Note: Whilst every effort is made to keep the syllabus and assessment records correct, the precise details must be checked with the lecturer(s).

Code COMP202P
Year 2
Prerequisites Theory I (102P) and Theory II (104P). Students will be required to implement a program in C, so some programming experience is desirable.
Term 1
Taught By Robin Hirsch (67%)
John Dowell (33%)
Aims To introduce and familiarise students with logical and mathematical inference and with database theory, the latter having an emphasis on the fundamentals of relational database systems and SQL. Students learn a number of logical inference methods for classical logics.
Learning Outcomes Students should understand how axiomatic systems can be used for propositional and predicate logic and they should understand the notions of soundness and completeness. They should also understand how propositional and predicate tableaus work. They should have familiarity with other logics, including modal and temporal logics. They should be able to analyse relational databases.

Content

Propositional and Predicate logic

  • Review of syntax and semantics.
  • Deduction and Inference.
  • Truth tables.
  • Decidability of propositional logic.

Mathematical proofs

  • Proof by contradiction.
  • Induction and structured induction.
  • Hilbert systems.
  • Axioms and inference rules for propositional logic.
  • Axioms and inference rules for predicate logic.
  • Tableau.
  • Tableau construction for propositional logic and predicate logic.
  • Soundness and completeness theorems for first order logic.
  • Semi-decidability of first order logic.

Finite computation methods

  • Finite state machines.
  • Regular languages.
  • Kleene's theorem.
  • Finite state machines with stacks.

Databases

  1. Database management systems (DBMS) and the relational database:
    • essential concepts
    • data model
    • architecture and primary functions of the DBMS
  2. SQL:
    • use of SQL as a language for database construction and data manipulation
  3. Database design:
    • a structured method for designing relational databases through
      • data modelling
      • schema specification
      • validation
      • normalisation.

Method of Instruction

Lecture presentations with associated courseworks.

Assessment

The course has the following assessment components:

  • Written Examination (2.5 hours, 95%);
  • Coursework Section (2 pieces, 5%).

To pass this course, students must:

  • Obtain an overall pass mark of 40% for all components combined;
  • Obtain a minimum mark of 30% in each component worth > 30% of the module as a whole.

Resources

Reading list available via the UCL Library catalogue.