http://www.inf.unibz.it/~calvanese/teaching/2010-10-ESSLLI-DL-QA/
22nd European Summer School in Logic Language and Information
ESSLLI 2010
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
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:
- Correspondence between DLs and data modeling formalisms, and discussion
on how DLs can be adopted as conceptual layer to access data.
- 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.
- 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:
- discuss a spectrum of such DLs (from the one corresponding to OWL2-QL
to DL-Lite_bool, EL, and fragments of Horn-SHIQ);
- concentrate on the problem of answering database-like queries, but
also consider other reasoning tasks (ranging from standard DL
reasoning, to forms of "metareasoning");
- cover various reasoning approaches and techniques.
Prerequisites
- Basic knowledge of the following topics, as taught at the BSc level of a
computer science curriculum:
- propositional and first-order logic,
- databases (relational model and SQL),
- theory of computation (Turing Machines, P, NP), although we will
briefly overview the required notions in the course.
- Knowledge of description logics is a plus but not required. We will
introduce all necessary notions about DLs in the course.
Outcome
At the end of the course, the participants will:
- have learned about a new application area of logic, viz., knowledge
representation in data management systems;
- have understood the relationships and differences between query answering
in databases and query answering in the presence of ontologies;
- be familiar with the state-of-the-art methods and techniques of query
evaluation via a high level conceptual interface, the corresponding
description logics and fragments of the web ontology language OWL.
Course Overview (with slides to download)
- Lec. 1: Introduction and
background -
D. Calvanese
-
- Ontology-based data management
- Brief introduction to computational complexity
- Query answering in databases
- Querying databases and ontologies
- Lec. 2: Lightweight description
logics -
M. Zakharyaschev
-
- Introduction to description logics [12]
- DLs for conceptual data modeling: the DL-Lite family [1,2,3]
- The EL family of tractable description logics [4,5,6]
- Lec. 3: Query answering in
the DL-Lite family -
D. Calvanese
-
- Query answering in description logics [2,3]
- Lower bounds for description logics beyond DL-Lite [1,2,3]
- Reasoning and query answering by rewriting [2,3]
- Lec. 4: The combined approach
to query answering -
M. Zakharyaschev
-
- Query answering in DL-Lite: data completion [7,8]
- Query rewriting in EL [9]
- Lec. 5: Linking
ontologies to relational data -
D. Calvanese
-
- The impedance mismatch problem [10,3]
- Query answering in Ontology-Based Data Access systems [10,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.
home page of Diego Calvanese
Last modified:
Tuesday, 1-Oct-2013 12:51:49 CEST