%0 Conference Paper
%B International World Wide Web Conference (WWW2011)
%D 2011
%T A Better Uncle For OWL - Nominal Schemas for Integrating Rules and Ontologies
%A Markus Krotzsch
%A Frederick Maier
%A Adila Alfa Krisnadhi
%A Pascal Hitzler
%K Datalog
%K Description Logic
%K Semantic Web Rule Language
%K SROIQ
%K tractability
%K Web Ontology Language
%X We propose a description-logic style extension of OWL 2 with nominal schemas which can be used like 'variable nominal classes' within axioms. This feature allows ontology languages to express arbitrary DL-safe rules (as expressible in SWRL or RIF) in their native syntax. We show that adding nominal schemas to OWL 2 does not increase the worst-case reasoning complexity, and we identify a novel tractable language SROELV_3(⊓, X) that is versatile enough to capture the lightweight languages OWL EL and OWL RL.
%B International World Wide Web Conference (WWW2011)
%I Proceedings of the 20th International World Wide Web Conference (WWW2011)
%C New York
%G eng
%0 Conference Paper
%D 2011
%T Nominal Schemas for Integrating Rules and Description Logics
%A Markus Krotzsch
%A Frederick Maier
%A Adila Alfa Krisnadhi
%A Pascal Hitzler
%X We propose an extension of SROIQ with nominal schemas which can be used like Âvariable nominal conceptsÂ within axioms. This feature allows us to express arbitrary DL-safe rules in description logic syntax. We show that adding nominal schemas to SROIQ does not increase its worst-case reasoning complexity, and we identify a family of tractable DLs SROELVn that allow for restricted use of nominal schemas.
%G eng
%0 Book
%D 2010
%T Foundations of Semantic Web Technologies
%A Pascal Hitzler
%A Markus Krotzsch
%A Sebastian Rudolph
%K foundations of semantic web
%K foundations of semantic web technologies
%G eng
%0 Book
%D 2009
%T Foundations of Semantic Web Technologies
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%G eng
%0 Conference Paper
%B Approximate OWL Instance Retrieval with Screech
%D 2008
%T Approximate OWL Instance Retrieval with Screech
%A Sebastian Rudolph
%A Markus Krotzsch
%A Tuvshintur Tserendorj
%A Pascal Hitzler
%X With the increasing interest in expressive ontologies for the Semantic Web, it is critical to develop scalable and efficient ontology reasoning techniques that can properly cope with very high data volumes. For certain application domains, approximate reasoning solutions, which trade soundness or completeness for increased reasoning speed, will help to deal with the high computational complexities which state of the art ontology reasoning tools have to face. In this paper, we present a comprehensive overview of the SCREECH approach to approximate instance retrieval with OWL ontologies, which is based on the KAON2 algorithms, facilitating a compilation of OWL DL TBoxes into Datalog, which is tractable in terms of data complexity. We present three different instantiations of the Screech approach, and report on experiments which show that the gain in efficiency outweighs the number of introduced mistakes in the reasoning process.
%B Approximate OWL Instance Retrieval with Screech
%G eng
%0 Conference Paper
%B International Conference, RR 2008
%D 2008
%T Approximate OWL-Reasoning with Screech
%A Sebastian Rudolph
%A Markus Krotzsch
%A Tuvshintur Tserendorj
%A Pascal Hitzler
%X Applications of expressive ontology reasoning for the Semantic Web require scalable algorithms for deducing implicit knowledge from explicitly given knowledge bases. Besides the development of more efficient such algorithms, awareness is rising that approximate reasoning solutions will be helpful and needed for certain application domains. In this paper, we present a comprehensive overview of the Screech approach to approximate reasoning with OWL ontologies, which is based on the KAON2 algorithms, facilitating a compilation of OWL DL TBoxes into Datalog, which is tractable in terms of data complexity.We present three different instantiations of the Screech approach, and report on experiments which show that a significant gain in efficiency can be achieved.
%B International Conference, RR 2008
%I Second International Conference, RR 2008
%C Karlsruhe, Germany
%P 165-180
%8 10/2008
%G eng
%0 Conference Paper
%B 11th European Conference on Logics in Artificial Intelligence (JELIA)
%D 2008
%T Cheap Boolean Role Constructors for Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We investigate the possibility of incorporating Boolean role constructors on simple roles into some of today's most popular description logics, focussing on cases where those extensions do not increase complexity of reasoning. We show that the expressive DLs SHOIQ and SROIQ, serving as the logical underpinning of OWL and the forthcoming OWL 2, can accommodate arbitrary Boolean expressions. The prominent OWL-fragment SHIQ can be safely extended by safe role expressions, and the tractable fragments EL++ and DLP retain tractability if extended by conjunction on roles, where in the case of DLP the restriction on role simplicity can even be discarded.
%B 11th European Conference on Logics in Artificial Intelligence (JELIA)
%C Dresden, Germany
%P 362-374
%8 09/2008
%G eng
%0 Conference Paper
%B The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
%D 2008
%T Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We propose a novel method for reasoning in the description logic SHIQ. After a satisfiability preserving transformation from SHIQ to the description logic ALCIb, the obtained ALCIb Tbox T is converted into an ordered binary decision diagram (OBDD) which represents a canonical model for T. This OBDD is turned into a disjunctive datalog program that can be used for Abox reasoning. The algorithm is worst-case optimal w.r.t. data complexity, and admits easy extensions with DL-safe rules and ground conjunctive queries.
%B The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
%I The Semantic Web - ISWC 2008, 7th International Semantic Web Conference
%C Karlsruhe, Germany
%P 435-450
%G eng
%0 Conference Paper
%B 18th European Conference on Artificial Intelligence, ECAI
%D 2008
%T Description Logic Rules
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We introduce description logic (DL) rules as a new rule-based formalism for knowledge representation in DLs. As a fragment of the Semantic Web Rule Language SWRL, DL rules allow for a tight integration with DL knowledge bases. In contrast to SWRL, however, the combination of DL rules with expressive description logics remains decidable, and we show that the DL SROIQ - the basis for the ongoing standardisation of OWL 2 - can completely internalise DL rules. On the other hand, DL rules capture many expressive features of SROIQ that are not available in simpler DLs yet. While reasoning in SROIQ is highly intractable, it turns out that DL rules can be introduced to various lightweight DLs without increasing their worst-case complexity. In particular, DL rules enable us to significantly extend the tractable DLs EL++ and DLP.
%B 18th European Conference on Artificial Intelligence, ECAI
%C Patras, Greece
%P 80-84
%8 07/2008
%G eng
%0 Conference Paper
%B ELP: Tractable Rules for OWL 2
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Markus Krotzsch
%A Sebastian Rudolph
%A Pascal Hitzler
%X We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role.We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP.While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
%B ELP: Tractable Rules for OWL 2
%G eng
%0 Report
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role. We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP. While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
%B ELP: Tractable Rules for OWL 2
%G eng
%0 Generic
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Markus Krotzsch
%A Sebastian Rudolph
%A Pascal Hitzler
%X We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role.We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP.While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
%G eng
%0 Generic
%D 2008
%T Expressive Tractable Description Logics based on SROIQ Rules
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We introduce description logic (DL) rules as a new rule-based formalism for knowledge representation in DLs. As a fragment of the Semantic Web Rule Language SWRL, DL rules allow for a tight integration with DL knowledge bases. In contrast to SWRL, however, the combination of DL rules with expressive description logics remains decidable, and we show that the DL SROIQ - the basis for the ongoing standardisation of OWL 2 - can completely internalise DL rules. On the other hand, DL rules capture many expressive features of SROIQ that are not available in simpler DLs yet. While reasoning in SROIQ is highly intractable, it turns out that DL rules can be introduced to various lightweight DLs without increasing their worst-case complexity. In particular, DL rules enable us to significantly extend the tractable DLs EL++ and DLP.
%G eng
%0 Book
%D 2008
%T Semantic Web. Grundlagen
%A Sebastian Rudolph
%A York Sure
%A Markus Krotzsch
%A Pascal Hitzler
%G eng
%0 Conference Paper
%B Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%D 2008
%T Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We present a new algorithm for reasoning in the description logic SHIQ, which is the most prominent fragment of the Web Ontology Language OWL. The algorithm is based on ordered binary decision diagrams (OBDDs) as a data structure for storing and operating on large model representations. We thus draw on the success and the proven scalability of OBDD-based systems. To the best of our knowledge, we present the very first algorithm for using OBDDs for reasoning with general Tboxes.
%B Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%G eng
%0 Generic
%D 2008
%T Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X We present a new algorithm for reasoning in the description logic SHIQ, which is the most prominent fragment of the Web Ontology Language OWL. The algorithm is based on ordered binary decision diagrams (OBDDs) as a data structure for storing and operating on large model representations. We thus draw on the success and the proven scalability of OBDD-based systems. To the best of our knowledge, we present the very first algorithm for using OBDDs for reasoning with general Tboxes.
%G eng
%0 Conference Paper
%B The 22nd AAAI Conference on Artficial Intelligence
%D 2007
%T Complexity Boundaries for Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X Horn description logics (Horn-DLs) have recently started to attract attention due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for TBox reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn-DLs. While the combined complexity for many Horn-DLs turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning.
%B The 22nd AAAI Conference on Artficial Intelligence
%C Vancouver, British Columbia, Canada
%G eng
%0 Generic
%D 2007
%T Complexity of Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X Horn description logics (Horn-DLs) have recently started to attract attention due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for TBox reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn-DLs. While the combined complexity for many Horn-DLs turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning.
%G eng
%0 Conference Paper
%B 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%D 2007
%T Conjunctive Queries for a Tractable Fragment of OWL 1.1
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X Despite the success of the Web Ontology Language OWL, the development of expressive means for querying OWL knowledge bases is still an open issue. In this paper, we investigate how a very natural and desirable form of queries-namely conjunctive ones-can be used in conjunction with OWL such that one of the major design criteria of the latter-namely decidability-can be retained. More precisely, we show that querying the tractable fragment EL++ of OWL 1.1 is decidable. We also provide a complexity analysis and show that querying unrestricted EL++ is undecidable.
%B 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%I The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%C Busan, Korea
%P 310-323
%8 11/2007
%G eng
%0 Conference Paper
%B International Conference on Web Reasoning and Rule Systems, RR2007
%D 2007
%T Efficient OWL Reasoning with Logic Programs - Evaluations
%A Sebastian Rudolph
%A Markus Krotzsch
%A Michael Sintek
%A Denny Vrandecic
%A Pascal Hitzler
%X We report on efficiency evaluations concerning two different approaches to using logic programming for OWL [1] reasoning and show, how the two approaches can be combined. Introduction. Scalability of reasoning remains one of the major obstacles in leveraging the full power of the Web Ontology Language OWL [1] for practical applications. Among the many possible approaches to address scalability, one of them concerns the use of logic programming for this purpose. It was recently shown that reasoning in Horn-SHIQ [2-4] can be realised by invoking Prolog systems on the output of the
%B International Conference on Web Reasoning and Rule Systems, RR2007
%C Innsbruck, Austria
%P 370-373
%G eng
%0 Conference Paper
%B ICCS 2007
%D 2007
%T Quo Vadis, CS? - On the (non)-impact of Conceptual Structures on the Semantic Web
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X Conceptual Structures is a field of research which shares abstract concepts and interests with recent work on knowledge representation for the Semantic Web. However, while the latter is an area of research and development which is rapidly expanding in recent years, the former fails to participate in these developments on a large scale. In this paper, we attempt to stimulate the Conceptual Structures community to catch the Semantic Web train.
%B ICCS 2007
%C Sheffield, UK
%G eng
%0 Conference Paper
%D 2006
%T On the Complexity of Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X Horn-*SHIQ* has been identified as a fragment of the description logic *SHIQ* for which inferencing is in PT_{IME} with respect to the size of the ABox. This enables reasoning with larger ABoxes in situations where the TBox is static, and represents one approach towards tractable description logic reasoning. In this paper, we show that reasoning in Horn-*SHIQ*, in spite of its low datacomplexity, is E_{xp}T_{IME}-hard with respect to the overall size of the knowledge base. While this result is not unexpected, the proof is not a mere modification of existing reductions since it has to account for the restrictions of Hornness. We establish the result for Horn-*FLE*, showing that Hornness does not simplify TBox reasoning even for very restricted description logics. Moreover, we derive a context-free grammar that defines Horn-*SHIQ* in a simpler and more intuitive way than existing characterisations.
%I Second Workshop OWL - Experiences and Directions, OWLED2006
%G eng
%0 Conference Paper
%B the Second International Conference on Rules and Rule Markup Languages for the Semantic Web, RuleML2006
%D 2006
%T How to Reason with OWL in a Logic Programming System
%A M. Krotzsch
%A D. Vrandecic
%A M. Sintek
%A Pascal Hitzler
%X Logic programming has always been a major ontology modeling paradigm, and is frequently being used in large research projects and industrial applications, e.g., by means of the F-Logic reasoning engine OntoBroker or the TRIPLE query, inference, and transformation language and system. At the same time, the Web Ontology Language OWL has been recommended by the W3C for modeling ontologies for the web. Naturally, it is desirable to investigate the interoperability between both paradigms. In this paper, we do so by studying an expressive fragement of OWL DL for which reasoning can be reduced to the evaluation of Horn logic programs. Building on the KAON2 algorithms for transforming OWL DL into disjunctive Datalog, we give a detailed account of how and to what extent OWL DL can be employed in standard logic programming systems. En route, we derive a novel, simplified characterization of the supported fragment of OWL DL.
%B the Second International Conference on Rules and Rule Markup Languages for the Semantic Web, RuleML2006
%C Athens, Georgia
%P 17-26
%G eng
%0 Conference Paper
%B 14th International Conference on Conceptual Structures, ICCS 2006
%D 2006
%T Querying Formal Contexts with Answer Set Programs
%A M. Krotzsch
%A Pascal Hitzler
%X Recent studies showed how a seamless integration of formal concept analysis (FCA), logic of domains, and answer set programming (ASP) can be achieved. Based on these results for combining hierarchical knowledge with classical rule-based formalisms, we introduce an expressive common-sense query language for formal contexts. Although this approach is conceptually based on order-theoretic paradigms, we show how it can be implemented on top of standard ASP systems. Advanced features, such as default negation and disjunctive rules, thus become practically available for processing contextual data.
%B 14th International Conference on Conceptual Structures, ICCS 2006
%C Aalborg, Denmark
%P 260-273
%G eng
%0 Generic
%D 2005
%T Category Theory in Ontology Research: Concrete Gain from an Abstract Approach
%A Markus Krotzsch
%A Marc Ehrig
%A York Sure
%X The focus of research on representing and reasoning with knowledge traditionally has been on single speciÃ¯Â¬Âcations and appropriate inference paradigms to draw conclusions from such data. Accordingly, this is also an essential aspect of ontology research which has received much attention in recent years. But ontologies introduce another new challenge based on the distributed nature of most of their applications, which requires to relate heterogeneous ontological speciÃ¯Â¬Âcations and to integrate information from multiple sources. These problems have of course been recognized, but many current approaches still lack the deep formal backgrounds on which todays reasoning paradigms are already founded. Here we propose category theory as a well-explored and very extensive mathematical foundation for modelling distributed knowledge. A particular prospect is to derive conclusions from the structure of those distributed knowledge bases, as it is for example needed when merging ontologies.
%G eng
%0 Conference Paper
%D 2005
%T DLP Isn't So Bad After All
%A York Sure
%A Rudi Studer
%A Markus Krotzsch
%A Peter Haase
%A Pascal Hitzler
%X We discuss some of the recent controversies concerning the DLP fragment of OWL. We argue that it is a meaningful fragment and can serve as a basic interoperability layer between OWL and logic programming-based ontology languages.
%G eng
%0 Conference Paper
%B DLP Isn't So Bad After All
%D 2005
%T DLP Isn't So Bad After All
%A Pascal Hitzler
%A York Sure
%A Rudi Studer
%A Markus Krotzsch
%A Peter Haase
%B DLP Isn't So Bad After All
%G eng
%0 Conference Paper
%B 13th International Conference on Conceptual Structures, ICCS '05
%D 2005
%T Morphisms in Context
%A Markus Krotzsch
%A Guo-Qiang Zhang
%A Pascal Hitzler
%X Morphisms constitute a general tool for modelling complex relationships between mathematical objects in a disciplined fashion. In Formal Concept Analysis (FCA), morphisms can be used for the study of structural properties of knowledge represented in formal contexts, with applications to data transformation and merging. In this paper we present a comprehensive treatment of some of the most important morphisms in FCA and their relationships, including dual bonds, scale measures, infomorphisms, and their respective relations to Galois connections. We summarize our results in a concept lattice that cumulates the relationships among the considered morphisms. The purpose of this work is to lay a foundation for applications of FCA in ontology research and similar areas, where morphisms help formalize the interplay among distributed knowledge bases.
%B 13th International Conference on Conceptual Structures, ICCS '05
%C Kassel, Germany
%P 223-237
%G eng
%0 Conference Paper
%D 2005
%T What Is Ontology Merging? - A Category-Theoretical Perspective Using Pushouts
%A York Sure
%A Markus Krotzsch
%A Marc Ehrig
%A Pascal Hitzler
%X In this paper we explain how merging of ontologies is captured by the pushout construction from category theory, and argue that this is a very natural approach to the problem. We study this independent of a specific choice of ontology representation language, and thus provide a sort of blueprint for the development of algorithms applicable in practice. For this purpose, we view category theory as a universal 'meta specification language' that enables us to specify properties of ontological relationships and constructions in a way that does not depend on any particular implementation. This can be achieved since the basic objects of study in category theory are the relationships between multiple ontological specifications, not the internal structure of a single knowledge representation. Categorical pushouts are already considered in some approaches to ontology research (Jannink et al. 1998; Schorlemmer, Potter, & Robertson 2002; Goguen 2005; Kent 2005) and we do not claim our treatment to be entirely original. Still we have the impression that the potential of category theoretic approaches is by far not exhausted in todays ontology research. For our particular case the treatment will focus on the ontology merging, for which we will give both intuitive explanations and precise definitions. This reflects our belief that, at the current stage of research, it is not desirable to fade out the mathematical details of the categorical approach completely, since the interfaces to current techniques in ontology research are not yet available to their full extent. We will also keep this treatment rather general, not narrowing the discussion to specific formalisms - this added generality is one of the strengths of category theory. A long version of this paper with a tutorial character is available from the first author's homepage.
%I 20th National Conference on Artificial Intelligence, AAAI-05
%G eng