In this tutorial, we are going to look closely at the complexity of Description Logic (DL) reasoning. After a brief introduction to DLs and associated reasoning problems, we will review their computational worst case complexity and discuss various sources of this complexity. We will then relate all this to reasoner performance in practice and discuss various associated phenomena, in particular performance robustness. Finally, we will look into cognitive complexity, i.e., approaches to measuring how difficult reasoning is for humans, and into areas where such measurements are relevant.
The paradigm of ontology-based data access (OBDA) has recently emerged
as an exciting application of knowledge representation and reasoning
technologies in information systems. In a nutshell, the underlying
idea is to facilitate high-level access to data by separating the user
from the raw data using an ontology that provides a user-oriented
"semantic" view of the data and makes it accessible via queries
formulated solely in the language of the ontology without any
knowledge of the actual structure of the data (this property is
commonly called "physical data independence" in database literature).
The tutorial will present an overview of current approaches to OBDA and study the similarities (and differences) between OBDA and various approaches to logical and physical design in the relational model. In particular the lectures will focus on showing how advanced knowledge representation techniques accompanied by powerful reasoning algorithms and strategies yield a novel approach to the problem of answering queries formulated over a conceptual (logical) representation of knowledge by "compiling" them to efficient algorithms operating over a physical representation of the knowledge (i.e., over a choice of particular data structures). Such an approach allows applying KR technology in non-traditional settings, such as main-memory databases and embedded systems, settings in which our solutions must be competitive with hand-crafted C code in performance.
In part, the lectures will be based on "David Toman, Grant E. Weddell: Fundamentals of Physical Design and Query Compilation. Synthesis Lectures on Data Management, Morgan & Claypool Publishers 2011".
The outline for the tutorial:
- Introduction Goals and Current Practice.
- Standard OBDA approaches: Conjunctive Queries and Lite Logics.
- Physical Design and Schema Languages.
- How do we execute queries? How do we update data?
- Open Issues