johnz@latcs1.oz.au (John Zeleznikow) (02/28/91)
LATROBE UNIVERSITY
DEPARTMENT of COMPUTER SCIENCE
CSMKBD Knowledge Based Databases - Syllabus
******************************************************************************
Textbooks
---------
Prescribed:
----------
Ceri,S., Gottlob,G. and Tanca L. "Logic Programming and Databases",
Springer Verlag, Berlin, 1990.
Kim,W. "Introduction to Object Oriented Databases:,
MIT Press, Cambridge Massachusetts, 1990.
Mylopolous,J. and Brodie,M.L. "Readings in Artificial Intelligence and
Databases", Morgan Kaufmann, San Mateo, California, 1988.
Strongly Recommended:
--------------------
Gardarin,G. and Valduriez,P. "Relational Databases and Knowledge Bases",
Addison Wesley, Reading, Massachusetts, 1989
Ullman,J.D. "Principles of Databases and Knowledge Based Systems, Volume 1",
Computer Science Press, Rockville, Maryland, 1988.
References:
----------
Date,C.J. "Introduction to Database Systems", 5th edition
Addison Wesley, Reading, Massachusetts, 1990.
Grant,J. "Logical Introduction to Databases",
Harcourt Brace Jovanovich, Orlando, Florida, 1987.
Korth,H.F. and Silberschatz,A. "Database System Concepts, 2nd edition",
McGraw Hill, New York, New York, 1990.
Lloyd,J.W. "Foundations of Logic Programming, second edition",
Springer Verlag, Berlin, 1987
Minker,J. (ed) "Foundations of Deductive Databases and Logic Programming",
Morgan Kaufmann, Los Altos, California, 1988.
Sterling,L. and Shapiro,E. "The Art of Prolog", M.I.T. Press, Cambridge
Massachusetts, 1986.
Journals and Conference Proceedings:
-----------------------------------
Transactions on Database Systems (ACM)
Expert Database Systems Conferences (Benjamin Cummings)
SIGMOD Conferences (ACM)
VLDB Conferences (Morgan Kaufmann)
IEEE Expert
AI Magazine (AAAI)
Transactions on Knowledge and Data Engineering (IEEE)
SIGMOD RECORD
Data Engineering Newsletter
Data Engineering Conferences
and selected papers issued in class.
Assessment:
----------
2 hour examination 40 %
1 literature survey 50 %
OR 1 implementation of a 50 %
deductive database system
1 minor project 10 %
- answering queries in Prolog
Lecturer:
-------- Dr. John Zeleznikow, johnz@latcs1
Office: Physical Sciences 1, Room 308
------
Phone: 479-1003 (LaTrobe), 571-5475(Home)
-----
Office Hours: Tuesdays and Wednesdays 2-3p.m.
------------
Lectures: Wednesday 4-6p.m. in Peribols West 219
--------
Please note the introductory review session will be 4-8 on Wednesday 6 March
1991. The lectures will recommence on Wednesday 14 April 1991, with four extra
hours (between 6 and 7 p.m.), on mutually convenient Wednesdays.
SYLLABUS
********
(a) Introductory Material (for information only)
---------------------
Database Systems Terminology
----------------------------
Requirements of a Database system.
Data Manipulation Languages.
Physical Database Level.
Views.
Conceptual database level.
Schemes and Instances.
Database system architecture.
Data Definition Languages.
Data manipulation and host languages.
Object oriented vs logical approach to knowledge-based management systems.
Features of object-based systems.
Data Models for Database Systems:
--------------------------------
Data Models.
(1) The Entity-Relationship model.
Entities, entity sets, relationships, keys, is_a hierarchies.
Entity-Relationship diagrams
Functionality of relationships.
(2) The Relational model.
History.
Relations, tuples, attributes, keys.
Algebraic vs. logical notation.
Relational algebra: operations, query language.
(3) The Network Model.
Logical records, links.
Entity sets - owners, members.
DBTG Data Definition Language.
Network vs. Relational schema.
(4) The Hierarchical model.
Hierarchy, database records, virtual records.
(5) Deductive Model
First Order Predicate Calculus - interpretations and models.
Deductive Database - rules and facts.
Queries, answer substitutions, correct answer substitutions.
Dealing with negative information - Domain closure axioms and Closed world
assumption.
(6) Object Oriented Model.
Object identity, complex objects, type hierarchy.
Object structures.
Classes and methods
Operations.
Relational Query Languages
--------------------------
Relational calculus - domain calculus and tuple calculus.
Features of DMLs.
Examples : ISBL, QUEL, QBE,
SQL - in detail: the select statement, sets and subqueries, update,
delete and modify.
Designing Relational Databases - functional dependencies and normal form.
------------------------------
Functional and full functional dependencies.
Transitive relationships.
Functional dependency diagrams.
First , second and third normal forms.
Determinants.
Boyce Codd Normal Form.
Lossless decompositions.
Multi-valued dependencies.
Fourth normal form.
Convertng relations into fourth normal form in a lossless way.
Domain key normal form.
Query optimisation
------------------
Example and procedure.
Integrity and Security
----------------------
How databases can be abused.
Integrity presrvation.
Security.
Distributed Databases
---------------------
Definition and examples.
(b) Logic
-----
Propositional Calculus
Predicate Calculus
Resolution
Unification
SLD resolution
A knowledge of Prolog is presumed.
(c) Deductive Databases
-------------------
(i) Prolog and Relational Databases
Definition and examples
Prolog and DATALOG
Systems
(ii) Foundations of Datalog
Least Models
Extending Datalog with functions and negation
Stratification
(iii) Building Deductive Databases
Query Processing
Deductive Database Architectures
Integrity Constraint and Consistency Checking
Research Prototypes: LDL, Nail, Postgres, RDL1, Aditi
(d) Object Oriented Databases
-------------------------
Definitions and examples.
Object identity, complex objects, type hierarchy
Object Structures
Classes and methods
Operations
OPAL
Commercial OODBMSs
OODBMS prototypes
Extending object oriented databases to expert databases
(e) Expert Database Systems
-----------------------
Various topics including Non-monotonic logics and how to handle
incomplete information.
Building Intelligent Information Systems.
John Zeleznikow Thursday 28 February 1991