warning: the course material has been
recently completely revised. The bibliography and the reference
material have been updated; most slides were rewritten. Slides of
modules 5 and 6 are still to be revised. (March 2002)
lecturer: Enrico
Franconi, Faculty of Computer Science, Free University of
BozenBolzano, Italy
prerequisites: basic Mathematical Logics course
course description:

The main effort of the research in knowledge representation is
providing theories and systems for expressing structured knowledge and
for accessing and reasoning with it in a principled way. In this
course we will study Description Logics (DL), an important powerful
class of logicbased knowledge representation languages (see www.dl.kr.org). The emphasis
will be on a rigorous approach to knowledge representation and
building ontologies. After an original review of the relevant concepts
on computational logics, the course will start with an introduction to
ObjectOriented representations in Information Systems and Artificial
Intelligence, which serve as the main motivations for studying DL. DL
will be introduced with its simplest formalization; the computational
properties and algorithms of the so called structural DL will be
analyzed. Then, the course considers propositional DL: we will study
the computational properties and the reasoning with tableaux
calculus. In the second part of the course, we will consider advanced
topics such as the representation of knowledge bases and ontologies,
and the connections of DL with Modal Logics and First Order Logic. The
last module of the course will analyze the connections of DL with
database theory.
course material:
 Students are expected to read and study during the course
all the material marked as basic reading; the rest of the
material is optional but recommended anyway. Most papers can be
downloaded from this page. Students without a strong background in
classical logic are warmly suggested to review before the beginning of
the course the basic concepts of classical logic in one of the books
suggested for module 1.
 part A: basics
 module 1: A review of Computational
Logics
 slides:
 material:
 Any
basic handbook on mathematical logic:
 J. Kelly. The Essence of Logic. Prentice Hall, 1997.
(The simplest book to learn the basics of logic;
chapters 1, 2, (4), 6, (7) and 8)
 A. Galton. Logic for Information Technology. Wiley,
1990. (Simple but too verbose; chapters 1 to 6)
 H. Enderton. A Mathematical Introduction to
Logic. Academic Press, 2001. (A rigorous book; chapters
1 and 2 up to 2.6)
 H. D. Ebbinghaus, J. Flum, W. Thomas. Mathematical
Logic. SpringerVerlag, 1984. (A rigorous book;
chapters 1, 2 and 3)
 E. Mendelson. Introduction to Mathematical
Logic. Chapman and Hall, 1997. (Not my favourite;
chapters 1 and 2)
 module 2: Structural Description
Logics
 slides:
 material:

D. Nardi, R. J. Brachman. An Introduction to Description
Logics. In the Description Logic Handbook, edited by
F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi,
P.F. PatelSchneider,
Cambridge University Press, 2002, pages 544.

H. J. Levesque and R. J. Brachman. Expressiveness and tractability
in knowledge representation and reasoning. Computational
Intelligence journal 3, 7893 (1987).

B. Nebel. Reasoning and
Revision in Hybrid Representation Systems. Lecture Notes
in Artificial Intelligence 422, SpringerVerlag,
1990. Chapters 1  6.
 module 3: Propositional Description
Logics
 slides:
 material:

F. Baader, W. Nutt. Basic
Description Logics. In the
Description Logic Handbook, edited by F. Baader, D. Calvanese,
D.L. McGuinness, D. Nardi, P.F. PatelSchneider, Cambridge
University Press, 2002, pages 47100.
 Donini,
F., Lenzerini, M., Nardi, D., Schaerf, A., `Reasoning in
Description Logics', in: Principles of Knowledge
Representation and Reasoning, edited by G. Brewka; Studies in
Logic, Language and Information, CLSI Publications, pp
193238, 1996.

F. Baader and U. Sattler. An Overview of Tableau
Algorithms for Description Logics. Studia Logica, 69:540,
2001
 D.
Calvanese, G. De Giacomo, M. Lenzerini, and
D. Nardi, `Reasoning
in expressive description logics', in: A. Robinson and
A. Voronkov, editors, Handbook of Automated
Reasoning. Elsevier Science Publishers (NorthHolland),
Amsterdam, 2001, pages 15811634.

Hollunder, B., Nutt, W., `Subsumption Algorithms for
Concept Languages', DFKI report, RR9004, Saarbruecken
Germany, 1990; extended version of a previously published
paper in proc. ECAI'90, pp 348353.

Schaerf, A., `Reasoning
with individuals in concept languages', Data and Knowledge
Engineering, Vol 13(2), pp 141176, 1994.

F. Donini. Complexity of
Reasoning. In the
Description Logic Handbook, edited by F. Baader, D. Calvanese,
D.L. McGuinness, D. Nardi, P.F. PatelSchneider, Cambridge
University Press, 2002, pages 101141.
 part B: advanced topics
 module 4: Description Logics and Knowledge
Bases
 slides:
 material:
 Brachman,
R., McGuinness, D., PatelSchneider, P., Resnick, L., Borgida,
A.. Living with
CLASSIC: When and how to use a KLONElike language. In:
Principles of Semantic Networks, edited by John Sowa, Morgan
Kaufmann, 1991, pages 401456.

A. Borgida, R. J. Brachman. Conceptual Modelling with Description
Logics. In the Description Logic Handbook, edited by
F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi,
P.F. PatelSchneider,
Cambridge University Press, 2002, pages 359381.
 module 5: Description Logics and
Logics
 slides:
 material:
 A.
Borgida, `On the relative
expressive power of Description Logics and Predicate
Calculus', Artificial Intelligence 82 (1996) 353367.
 K.
Schild, `A correspondence
theory for terminological logics: preliminary report',
IJCAI91, pp 466471, October 1991.

B. Nebel and G. Smolka. Attributive Description
Formalisms... and the rest of the world. In C. Rollinger
O. Herzog, editor, Text Understanding in LILOG, LNAI
546. SpringerVerlag, Berlin, Germany, 1991, pages 439452.

D. Nardi, U. Sattler, D. Calvanese, R. Molitor. Relationships with other
formalisms. In the Description Logic Handbook, edited
by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi,
P.F. PatelSchneider, Cambridge University Press, 2002, pages
142183.
 module 6: Description Logics and
Databases
 slides:
 material:

A. Borgida, M. Lenzerini, R. Rosati. Description Logics for Databases. In
the Description Logic Handbook, edited by F. Baader, D. Calvanese,
D.L. McGuinness, D. Nardi, P.F. PatelSchneider, Cambridge
University Press, 2002, pages 472494.
 A.
Borgida, `Description
Logics in Data Management', IEEE Transactions on Knowledge
and Data Engineering vol.7, No. 5, October 1995, pages 671682.

D. Calvanese, M. Lenzerini, D. Nardi, `Description Logics for
Conceptual Data Modeling', Logics for Databases and
Information Systems, J. Chomicki and G. Saake eds., Kluwer,
1998, pages 229263.
 K.
Schild, `Tractable
reasoning in a universal description logic', Proceedings of
1st Workshop KRDB'94, Saarbrücken, Germany, September
2022, 1994.
 Buchheit,
M., Jeusfeld, M., Nutt, W., Staudt, M., `Subsumption between Queries to
ObjectOriented Databases', Information Systems, pp 3354,
January 1994.
useful links:
 The official Description Logics
page
 The Description
Logic Handbook: Theory, Implementation and Applications. Cambridge
University Press, 2002. ISBN
0521781760. Edited by F. Baader, D. Calvanese, D. McGuinness,
D. Nardi, P. F. PatelSchneider.
Contributors: D. Nardi, R.J. Brachman, F. Baader, W. Nutt,
F.M. Donini, U. Sattler, D. Calvanese, R. Molitor, G. De Giacomo,
R. Kuesters, F. Wolter, D.L. McGuinness, P.F. PatelSchneider,
R. Moeller, V. Haarslev, I. Horrocks, A. Borgida, C. Welty,
A. Rector, E. Franconi, M. Lenzerini, R. Rosati.
