Skip to Content

TU Wien Fakultät für Informatik KBS Knowledge-Based Systems Group
Top-level Navigation: Current-level Navigation:

Path: KBS > research > projects > hybridkb >

Tools: Drucken

Reasoning in Hybrid Knowledge Bases

supported by the Austrian Science Funds (FWF) under project number P20840.


Project team

Motivation and Background

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.

Goal of the project

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.





Franz Baader, Diego Calvanese, Deborah L. McGuinness, Daniele Nardi, and Peter F. Patel-Schneider. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge University Press, United Kingdom, 2003.
Grigoris Antoniou, Carlos V. Damasio, Benjamin Grosof, Ian Horrocks, Michael Kifer, Jan Maluszynski, Peter F. Patel-Schneider. Combining rules and ontologies. A survey. Cambridge University Press, United Kingdom, 2003.
Deborah L. Mcguinness and Frank van Harmelen. OWL web ontology language overviews. W3C recommendation, W3C, 2004.
Peter F. Patel-Schneider, Pat Hayes and Ian Horrocks. OWL Web Ontology Language semantics and abstract syntax -- W3C recommendation. Technical report. World Wide Web Consortium, February 2004.
Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of Databases. Addison-Wesley, 1995.
Jeff Z. Pan and Enrico Franconi, Sergio Tessaris and Giorgos Stamou, Vassilis Tzouvaras, Luciano Serafini and Ian Horrocks and Birte Glimm. Specification of Coordination of Rule and Ontology Languages. The Knowledge Web project, 2004.
Riccardo Rosati. Integrating ontologies and rules: Semantic and computational issues. Reasoning Web, Springer, 2006.
Thomas Eiter, Giovambattista Ianni, Axel F. Polleres, Roman Schindlauer, and Hans Tompits. Reasoning with Rules and Ontologies. Lecture Notes in Computer Science. Reasoning Web, Springer, 2006.
Thomas Eiter. Answer set programming for the semantic web (tutorial). Proceedings 23th International Conference on Logic Programming, 2007.
Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri and Francesco Scarcello. The DLV System for Knowledge Representation and Reasoning. ACM Transactions on Computational Logic (TOCL), 2006.
Patrik Simons, Ilkka Niemelä and Timo Soininen. Extending and Implementing the Stable Model Semantics. Artificial Intelligence, 2002.
Martin Gebser, Benjamin Kaufmann, Andre Neumann and Torsten Schaub. Clasp: A conflict-driven answer set solver. LPNMR, Springer, 2007.
Asparagus homepage. Since 2005.

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist die Fakultät für Informatik an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.