22nd European Summer School in Logic Language and Information
9-20 August 2010, Copenhagen (Denmark)

Introductory course course in the Logic and Computation section on

Answering Queries in Description Logics:
Theory and Applications to Data Management

Diego Calvanese          Michael Zakharyaschev
KRDB Research Centre
Free University of Bozen-Bolzano, Italy
Birbeck College, London, UK

Description of the course

Description logics (DLs) provide the formal foundation for ontologies and for the standard ontology language OWL; various DLs can be put into correspondence with formalisms used for conceptual modeling in various contexts (e.g., the Entity-Relationship Model and UML Class Diagrams). By virtue of such a correspondence DLs are very well suited to represent complex domain knowledge and to act as a conceptual layer on top of traditional information sources (e.g., relational databases). The possibility to rely on such a conceptual layer is of importance in several application contexts that rely on huge amounts of data with complex interrelationships, e.g., in Data Integration, Data Exchange, the Semantic Web, Ontology-Based Data Access. In these contexts, the fundamental inference task is querying the data with expressive database inspired query languages, while fully taking into account the semantics of the ontology.

This setting poses new and challenging requirements w.r.t. efficiency of inference, which have recently led to the development of new families of DLs, such as the DL-Lite family (on which the standard OWL2-QL profile is based), the EL family, and the Horn-SHIQ family. For example, the DL-Lite family spans a broad-range of logics that, on the one hand, capture the typical constructs used in conceptual modeling formalisms, and, on the other hand, are restricted in their constructs so as to give rise to an optimal trade-off between expressive power and efficiency of reasoning over large knowledge-bases, specifically for querying large amounts of data.

In light of this premise, the course will cover the following topics:

  1. Correspondence between DLs and data modeling formalisms, and discussion on how DLs can be adopted as conceptual layer to access data.
  2. Relationships and differences between querying in traditional databases (model checking) and querying in the presence of ontologies (reasoning), and challenges arising when accessing and querying large amounts of data through an ontology.
  3. Detailed survey of the DLs designed to provide high-level conceptual interface for querying databases and the corresponding complexity results and reasoning procedures. Specifically, we will:



At the end of the course, the participants will:

Course Overview (with slides to download)

Lec. 1: Introduction and background - D. Calvanese
  1. Ontology-based data management
  2. Brief introduction to computational complexity
  3. Query answering in databases
  4. Querying databases and ontologies

Lec. 2: Lightweight description logics - M. Zakharyaschev
  1. Introduction to description logics [12]
  2. DLs for conceptual data modeling: the DL-Lite family [1,2,3]
  3. The EL family of tractable description logics [4,5,6]

Lec. 3: Query answering in the DL-Lite family - D. Calvanese
  1. Query answering in description logics [2,3]
  2. Lower bounds for description logics beyond DL-Lite [1,2,3]
  3. Reasoning and query answering by rewriting [2,3]

Lec. 4: The combined approach to query answering - M. Zakharyaschev
  1. Query answering in DL-Lite: data completion [7,8]
  2. Query rewriting in EL [9]

Lec. 5: Linking ontologies to relational data - D. Calvanese
  1. The impedance mismatch problem [10,3]
  2. Query answering in Ontology-Based Data Access systems [10,3]
  3. Demo of the QuOnto tool

Conclusions - D. Calvanese + M. Zakharyaschev

Course Material

[1] The DL-Lite family and relations. Alessandro Artale, Diego Calvanese, Roman Kontchakov, and Michael Zakharyaschev.
J. of Artificial Intelligence Research, 36:1-69, 2009.

[2] Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati.
J. of Automated Reasoning, 39(3):385-429, 2007.

[3] Ontologies and databases: The DL-Lite approach. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Antonella Poggi, Mariano Rodriguez-Muro, and Riccardo Rosati.
In Sergio Tessaris and Enrico Franconi, editors, Semantic Technologies for Informations Systems - 5th Int. Reasoning Web Summer School (RW 2009), volume 5689 of Lecture Notes in Computer Science, pages 255-356. Springer, 2009.

[4] Pushing the EL Envelope. Franz Baader, Sebastian Brandt, and Carsten Lutz.
In Proc. of the 19th Int. Joint Conf. on Artificial Intelligence (IJCAI 2005), pages 364-369, 2005.

[5] Pushing the EL Envelope Further . Franz Baader, Sebastian Brandt, and Carsten Lutz.
In Proc. of the OWLED 2008 DC Workshop on OWL: Experiences and Directions (OWLED 2008 DC), 2008.

[6] Enriching EL-Concepts with Greatest Fixpoints. Carsten Lutz, Robert Piro, and Frank Wolter.
In Proc. of the 19th European Conference on Artificial Intelligence (ECAI 2010), 2010.

[7] The Combined Approach to Query Answering in DL-Lite. Roman Kontchakov, Carsten Lutz, David Toman, Frank Wolter, and Michael Zakharyaschev.
In Proc. of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010.

[8] Improving query answering over DL-Lite ontologies. Riccardo Rosati and Alessandro Almatelli.
In Proc. of the 12th International Conference on Principles of Knowledge Representation and Reasoning (KR 2010), 2010.

[9] Conjunctive Query Answering in the Description Logic EL using a Relational Database System. Carsten Lutz, David Toman, and Frank Wolter.
In Proc. of the 21st International Joint Conference on Artificial Intelligence (IJCAI 09), 2009.

[10] Linking data to ontologies. Antonella Poggi, Domenico Lembo, Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Riccardo Rosati.
J. on Data Semantics, X:133-173, 2008.

[11] The Mastro System for Ontology-based Data Access. Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Antonella Poggi, Mariano Rodriguez-Muro, Riccardo Rosati, Marco Ruzzi, Domenico Fabio Savo.
Semantic Web Journal, 2(1):43-53, 2011.

Additional References

[12] The Description Logic Handbook: Theory, Implementation and Applications. Franz Baader, Diego Calvanese, Deborah McGuinness, Daniele Nardi, and Peter F. Patel-Schneider, 2nd edition, Cambridge University Press, 2007.

Back to home page of Diego Calvanese
Last modified: Tuesday, 1-Oct-2013 12:51:49 CEST