Ebook: Description Logic Rules

Formal models of domain-specific knowledge abound in science and technology. It is desirable that such models can be managed, exchanged, and interpreted in computer systems, and the term “ontology” was coined to refer to the respective modelling artefacts.

A prominent application field for ontologies is the Semantic Web where the Web Ontology Language OWL is the predominant modelling language. The formal semantics of OWL is largely based on the description logic (DL) family of knowledge representation formalisms that are well-suited for terminological modelling. Rule-based knowledge representation languages, in contrast, have a stronger focus on modelling relationships between instances. Both perspectives are relevant in applications but the combination of rules and DLs turns out to be difficult, since vital computational properties such as decidability are lost easily.

The subject of this work is to advance the development of hybrid DL rule languages based on first-order Horn rules. Reasoning for SWRL – the combination of DLs with (first-order) datalog – is known to be undecidable, and we identify DL Rules as a novel class of decidable SWRL fragments that is closely related to DLs. New decidability results for DLs with role constructors let us include simple role conjunction and concept products into DL Rules. DL Rules are further extended with DL-safe variables to arrive at DL+safe rules. The latter generalise DL Rules and the known approaches of DL-safe rules and role-safe recursive CARIN.

This leads to expressive DL rule languages with high computational complexities, motivating the study of more restricted languages. We introduce Horn DLs to generalise the known DL Horn-SHIQ, and show that many of these DLs exhibit high reasoning complexities in spite of their low data complexity. DLP has been proposed as a logic in the “expressive intersection” of DLs and datalog. We question the meaning of this description, and develop formal design criteria for DLP that let us specify the largest datalog-expressible fragment of description logics.

Combining these insights, we arrive at a new tractable DL rule language ELP which extends both DLP and the light-weight DL EL⁺⁺, although the union of these languages is intractable. ELP incorporates DL Rules and a form of DL+safe rules, and we present a reasoning procedure based on a direct reduction to datalog that preserves the structure of rules. This also lets us derive a new datalog-based inferencing procedure for the DL SROEL(,×) which extends EL⁺⁺.

This work advances the understanding of the relationship of rules and description logics, leading to concrete new knowledge representation formalisms of practical relevance. DL+safe rules constitute one of the broadest classes of decidable SWRL fragments known today. ELP provides a tractable DL rule language that generalises the novel light-weight ontology languages OWL RL and OWL EL as standardised by W3C, and that has been adopted as the basis for the WSML-DL v2.0 dialect of the Web Service Modeling Language. Our work also suggests new rule-based implementation methods for supporting these languages based on a single inferencing algorithm.

Acknowledgements. Working at AIFB gave me the opportunity to co-author two textbooks, a W3C standard, and a piece of software that is actually used – and to still engage in the research that led to this work. The unique environment that made this possible has largely been shaped and maintained by the efforts of Prof. Dr. Rudi Studer, and I wish to sincerely thank him.

I am grateful to Prof. Dr. Peter H. Schmitt for an inspiringly thorough review of this work that included many insightful observations and helpful hints.

The research reported herein had not been possible without my supervisors and co-authors Prof. Dr. Pascal Hitzler and Dr. Sebastian Rudolph. I warmly thank Pascal for support and inspiration throughout my studies, and Sebastian for extensive afternoon discussions, insightful comments, and audacious puns.

I wish to thank all colleagues and former colleagues at “Semantic Karlsruhe” for providing such an inspiring and enjoyable atmosphere. Moreover, I am indebted to numerous people with whom I have had the opportunity to discuss my research over the years, including the members of ReaSIG in Karlsruhe, and the DL-istas in Oxford and Manchester. I further thank all the good anonymous reviewers for their diligence and dedication – you know who you are.

Apologies for not listing everybody by name! Many of you have provided me with valuable feedback and invaluable advice. It is a pleasure to work with you.

Special thanks are due to Prof. Dr. Carsten Lutz, Dr. Bijan Parsia, and Prof. Dr. Ulrike Sattler for helpful words of advice on research in general, and on “getting your PhD done” in particular.

Much of my time outside research has been spent on developing Semantic MediaWiki, and I wish to thank everyone who has supported me in this task, especially all contributors, bug reporters, and support providers. Again, I must apologise for not listing all your names! Yaron Koren did an amazing job in keeping the project going while I was completely immersed in this work.

I will not thank Denny Vrandečić for his incurable optimism – which he cannot change anyway – but for letting me crush into his office to engage him in afternoon-filling discussions about research, the universe, and everything, as well as for the work he took from me while I was writing my thesis.

Thanks are due to my family and friends for understanding and supporting my commitment to my work. I thank my parents for too many things to list here.

All of my work is dependent upon the unconditional love and support from my wife Anja.

Markus Krötzsch

Karlsruhe, March 2010