supported by the Austrian Science Funds (FWF) under project number P20840.
Description logics (DLs) [baader2003] are a family of knowledge representation (KR) languages designed to represent knowledge with a complex structure. Nowadays they are widely accepted as prominent formalisms for constructing ontologies, which are conceptualizations of an application domain that can later be shared by various task-specific applications. Ontologies describe the concepts of the domain in terms of hierarchies of classes of domain objects and the relationships between such classes, called properties [antoniou2003]. In the Semantic Web, ontologies are intended to describe and structure complex Web resources, making them readily available for automated agents [mcguinness2004]. The World Wide Web Consortium (W3C) proposed the Web Ontology Languages (OWL), which are based on DLs, as a standard for constructing these ontologies [patel2004].
DLs were specifically designed for domain conceptualization and their standard reasoning services, like consistency testing, were tailored for supporting ontology development. As a consequence, they provide rather limited means for accessing the information in the ontologies [mcguinness2004]. Currently, to make use of an ontology, the developer has to design his own application-specific access methods and technology.
The major efforts towards declarative ontology access embrace rule-based languages as a viable interface for accessing ontologies and reasoning over them. Rule languages are of great importance in several fields. In databases, these languages and their implementations are accepted as efficient and yet sufficiently expressive means for querying data repositories [abiteboul1995]. Rule languages also play a very important role in Artificial Intelligence, mainly as tools for declarative problem solving. Most attempts to allow access to DL ontologies via rule languages resort to Datalog and its extensions, which, apart from sufficient expressive power, have highly optimized implementations available, e.g.,DLV [leone2006], Smodels [simons2002], clasp [gebser2007], see [asparagus2005]. Roughly, a Datalog query, or a program, is a set of function-free Horn rules that describe relations in terms of other relations. The semantics of a Datalog program, known as minimal model semantics, is given by the minimal extension of an input relational database that complies with the descriptions specified by the rules of the program. The possibility of using recursion when defining relations, combined with the minimal model semantics, allow Datalog to express some properties that cannot be expressed in DLs and even in full firstorder logic, e.g., transitive closure. When recursion is prohibited, Datalog boils down to standard (unions of) select-project-join (SQL) queries, which can be evaluated using highly optimized relational database engines.
Integrating DLs and rule-based languages in the so called hybrid languages has become a important research topic in recent years (see e.g., [antoniou2003, franconi2004, rosati2006, eiter2006, eiter2007] for surveys and references). These languages aim at providing the best features of both DLs and rule languages: allow to capture complex structures of information, and provide expressive means to access it in a declarative way.
Hybrid languages are intended to be very powerful tools for knowledge representation and reasoning. Providing such tools, however, requires the implementation of powerful systems that support reasoning over hybrid knowledge bases. This will not be possible until many challenges are overcome. The project is motivated by two major challenges, which are fundamental for overcoming the rest of them:
A first main goal of this project is the second challenge, and to research novel reasoning techniques which allow for efficient reasoning in hybrid languages. In both the fields of rule based languages and in DLs, many years of research have led to the development of highly optimized systems that support efficient reasoning, even in quite expressive languages. The reuse of these technologies in the context of hybrid knowledge bases would be very beneficial, but has been little explored.
Achieving this goal can only be done on the basis of results for the first challenge, which leads to the second main goal, namely a deep understanding of the computational complexity of hybrid languages. Here, an in-depth study of the sources of complexity of hybrid languages will support the identification of restricted fragments of hybrid languages that provide a good trade-off between computational complexity and expressive power. Indeed, identifying a sublanguage which is sufficiently expressive for a specific context and that still exhibits a good computational behavior may be one of the most promising ways to achieve efficient reasoning in particular application domains.
Accomplishment of this goal in turn naturally requires to understand the semantic relationship between the various hybrid formalisms and other well-established knowledge representation languages, which may be exploited for translation-based approaches that reduce, at least partially, reasoning in one hybrid language to reasoning in another language with existing efficient implementations. This leads us to the third main goal, which is to clarify the relationships between the formalisms regarding their expressiveness in detail.
As major contributions, the expected project outcomes will be a detailed picture of the computational properties of selected hybrid formalisms, an understanding of their expressive relationships and capabilities, and novel reasoning methods and techniques which break ground for efficient reasoning in hybrid formalisms.
Dr. Megyhn Bienvenu
Laboratoire de Recherche en Informatique
Prof. Dr. Diego Calvanese
Faculty of Computer Science
Free University of Bozen-Bolzano
Prof. Dr. Georg Gottlob
Department of Computer Science
Prof. Dr. Giovambattista Ianni
Dipartimento di Matematica e Informatica
Universita' della Calabria
Prof. Dr. Nicola Leone
Dipartimento di Matematica
Università della Calabria
Prof. Dr. Carsten Lutz
Department of Computer Science
Prof. Dr. Sebastian
Institute of Artificial Intelligence
Technische Universität Dresden
Prof. Dr. Yi-Dong Shen
State Key Laboratory of Computer Science
Institute of Software
Chinese Academy of Sciences
Prof. Dr. Yisong Wang
School of Computer Science and Information
Prof. Dr. Jia-Huai You
Department of Computing Science
University of Alberta
Prof. Dr. Mingyi Zhang
Guizhou Academy of Sciences, Guiyang