MC315 Expert Systems and Deductive Databases

Next: MC316 Parallel and Distributed Up: Year 3 Previous: MC314 Mathematics and Computer

MC315 Expert Systems and Deductive Databases

Credits: 20

Convenor: Dr. N. Measor

Semester: 2

Prerequisites:	essential: MC103, MC104, MC111, MC115, MC213
Assessment:	Continuous assessment: 30%	Three hour exam in May/June: 70%

Lectures:	36	Classes:	24
Tutorials:	12	Private Study:	78
Labs:	none	Seminars:	none
Project:	none	Other:	none
Total:	150

Explanation of Pre-requisites

Students on this module will need basic knowledge of programming, computer science mathematics, and information systems. This knowledge is supplied by the modules MC103, MC104, MC111, and MC115.

They also need some experience of Logic and Elementary Prolog, as supplied by MC213, Applied Logic.

Course Description

An expert system is a knowledge-based program which imitates the behaviour of a human expert in some problem domain. Expert systems have increased in popularity over the years, and have been used in such areas as medical diagnosis, mineral exploration, computer system design, and financial credit control.

The expert systems which we consider on this module are based on rules. This gives the connection with the idea of a deductive database, which extends the relational model by adding rules.

Aims

The module introduces students to the main principles underlying expert system technology. The more advanced features of the Prolog language are presented so that Prolog can be used to implement expert systems. The module also presents the relational model for databases and their query languages, and explains how this model can be extended to incorporate an intensional element defined by means of rules in the style of Prolog -- this is the extension from relational to deductive databases.

By the end of the module students will be able to construct simple rule-based expert systems in Prolog, and will be familiar with the semantics of deductive databases and their query languages.

Objectives

To be able to use the more advanced procedural aspects of Prolog.
To be able to design expert systems and implement them in Prolog.
To understand the fundamental concepts of Deductive Databases.

Transferable Skills

The ability to devise a knowledge representation scheme in a given domain.
The ability to implement a rule-based system for a given problem domian.
An understanding of integrity constraints and query evaluation for deductive databases.

Syllabus

Resumé of elementary Prolog: facts and rules, recursion, resolution, unification, SLD trees; list processing in Prolog; a worked example: the London underground; search strategies and cut; system predicates; arithmetic in Prolog; negation as finite failure; constraints on the search space: cycle detection and depth limitation; expert system concepts; production system concepts; implementing production systems and the explanatory interface in Prolog; dealing with uncertainty: certainty fators, implementing certainty factors in Prolog, alternative approaches.

The relational model of databases, relational calculus; model-theoretic account of integrity constraints; model-theoretic account of relational calculus queries; relational algebra, equivalence between relational algebra and relational calculus, query valuation in relational databases; the proof-theoretic account of databases, queries, and integrity constraints; deductive database concepts, hierarchical, definite, and stratified databases, extension of model-theoretic and proof-theoretic accounts to dbs; query evaluation in hierarchical databases; query evaluation in definite databases: computing the least Herbrand model, associated fixpoint theorems.

Reading list

Essential:

I. Bratko, Prolog, Programming for Artificial Intelligence, 2nd edition, Addison-Wesley.

Background:

Peter Jackson, Introduction to Expert System, Addison-Wesley.

L. Sterling and E. Shapiro, The Art of Prolog, 2nd edition, M.I.T.

T. Van Le, Techniques of Prolog Programming, Wiley.

Background:

A. Thayse et al., From Standard Logic to Logic Programming, Wiley.

A. Thayse et al., From Modal Logic to Deductive Databases, Wiley.

A. Thayse et al., From Natural Language Processing to Logic for Expert Systems, Wiley.

Details of Assessment

The coursework for the continuous assessment consists of three worksheets:

1.: Advanced Prolog programming, including search strategies (laboratory based work).
2.: Expert Systems: Production Systems, Control Strategies, User Interface (laboratory based work).
3.: Deductive Database (this sheet is purely theoretical).

The written Midsummer examination contains six questions, and the best four questions will be taken into account in determining the mark. The examination will test candidates' knowledge of both theoretical and practical issues.

Next: MC316 Parallel and Distributed Up: Year 3 Previous: MC314 Mathematics and Computer

S. J. Ambler
11/20/1999