DESCRIPTION LOGICS course (original) (raw)

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 Bozen-Bolzano, 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 logic-based 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 Object-Oriented 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:
    * Introduction
    * Foundations of Propositional Logics
    * Deduction in Propositional Logics
    * Foundations of First Order Logic
    * Using First Order Logic
    * 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. Springer-Verlag, 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:
    * The need for a Logic in conceptual modelling
    * Motivations from Object-Oriented languages
    * The simplest Structural Description Logic: FL-
    * 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. Patel-Schneider, Cambridge University Press, 2002, pages 5-44.
    * H. J. Levesque and R. J. Brachman. Expressiveness and tractability in knowledge representation and reasoning. Computational Intelligence journal 3, 78-93 (1987).
    * B. Nebel. Reasoning and Revision in Hybrid Representation Systems. Lecture Notes in Artificial Intelligence 422, Springer-Verlag, 1990. Chapters 1 - 6.
  • module 3: Propositional Description Logics
    * slides:
    * Propositional Description Logics
    * 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. Patel-Schneider, Cambridge University Press, 2002, pages 47-100.
    * 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 193-238, 1996.
    * F. Baader and U. Sattler. An Overview of Tableau Algorithms for Description Logics. Studia Logica, 69:5-40, 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 (North-Holland), Amsterdam, 2001, pages 1581-1634.
    * Hollunder, B., Nutt, W., `Subsumption Algorithms for Concept Languages', DFKI report, RR-90-04, Saarbruecken Germany, 1990; extended version of a previously published paper in proc. ECAI'90, pp 348-353.
    * Schaerf, A., `Reasoning with individuals in concept languages', Data and Knowledge Engineering, Vol 13(2), pp 141-176, 1994.
    * F. Donini. Complexity of Reasoning. In the Description Logic Handbook, edited by F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider, Cambridge University Press, 2002, pages 101-141.
• part B: advanced topics
  • module 4: Description Logics and Knowledge Bases
    * slides:
    * Formalising Knowledge Bases
    * Using Knowledge Bases and Ontology Engineering
    * material:
    * Brachman, R., McGuinness, D., Patel-Schneider, P., Resnick, L., Borgida, A.. Living with CLASSIC: When and how to use a KL-ONE-like language. In: Principles of Semantic Networks, edited by John Sowa, Morgan Kaufmann, 1991, pages 401-456.
    * 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. Patel-Schneider, Cambridge University Press, 2002, pages 359-381.
  • module 5: Description Logics and Logics
    * slides:
    * Description Logics and Logics
    * material:
    * A. Borgida, `On the relative expressive power of Description Logics and Predicate Calculus', Artificial Intelligence 82 (1996) 353-367.
    * K. Schild, `A correspondence theory for terminological logics: preliminary report', IJCAI-91, pp 466-471, 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. Springer-Verlag, Berlin, Germany, 1991, pages 439-452.
    * 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. Patel-Schneider, Cambridge University Press, 2002, pages 142-183.
  • module 6: Description Logics and Databases
    * slides:
    * Description Logics and Databases
    * 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. Patel-Schneider, Cambridge University Press, 2002, pages 472-494.
    * A. Borgida, `Description Logics in Data Management', IEEE Transactions on Knowledge and Data Engineering vol.7, No. 5, October 1995, pages 671-682.
    * 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 229-263.
    * K. Schild, `Tractable reasoning in a universal description logic', Proceedings of 1st Workshop KRDB'94, Saarbrücken, Germany, September 20-22, 1994.
    * Buchheit, M., Jeusfeld, M., Nutt, W., Staudt, M., `Subsumption between Queries to Object-Oriented Databases', Information Systems, pp 33-54, 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. Patel-Schneider. 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. Patel-Schneider, R. Moeller, V. Haarslev, I. Horrocks, A. Borgida, C. Welty, A. Rector, E. Franconi, M. Lenzerini, R. Rosati.