www.comlab.ox.ac.uk/people/boris.motik/index.html

# Publication List of Boris Motik

## In Journals

Giorgio Stefanoni, Boris Motik, Markus Krötzsch, and Sebastian Rudolph. The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases. Journal of Artificial Intelligence Research, 51:645–705, 2014.
@Article{smkr14complexity-CQs-EL,
author = "Giorgio Stefanoni and Boris Motik and Markus Kr{\"o}tzsch and Sebastian Rudolph",
title = "{The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases}",
journal = "Journal of Artificial Intelligence Research",
volume = "51",
pages = "645--705",
year = "2014",
}

OWL 2 EL is a popular ontology language that supports role inclusions—axioms of the form ${S_1 \cdots S_n \ISA S}$ that capture compositional properties of roles. Role inclusions closely correspond to context-free grammars, which was used to show that answering conjunctive queries (CQs) over OWL 2 EL knowledge bases with unrestricted role inclusions is undecidable. However, OWL 2 EL inherits from OWL 2 DL the syntactic regularity restriction on role inclusions, which ensures that role chains implying a particular role can be described using a finite automaton (FA). This is sufficient to ensure decidability of CQ answering; however, the FAs can be worst-case exponential in size so the known approaches do not provide a tight upper complexity bound. In this paper, we solve this open problem and show that answering CQs over OWL 2 EL knowledge bases is PSPACE-complete in combined complexity (i.e., the complexity measured in the total size of the input). To this end, we use a novel encoding of regular role inclusions using bounded-stack pushdown automata—that is, FAs extended with a stack of bounded size. Apart from theoretical interest, our encoding can be used in practical tableau algorithms to avoid the exponential blowup due to role inclusions. In addition, we sharpen the lower complexity bound and show that the problem is PSPACE-hard even if we consider only role inclusions as part of the input (i.e., the query and all other parts of the knowledge base are fixed). Finally, we turn our attention to navigational queries over OWL 2 EL knowledge bases, and we show that answering positive, converse-free conjunctive graph XPath queries is PSPACE-complete as well; this is interesting since allowing the converse operator in queries is known to make the problem \EXPTIME-hard. Thus, in this paper we present several important contributions to the landscape of the complexity of answering expressive queries over description logic knowledge bases.
Birte Glimm, Ian Horrocks, Boris Motik, Giorgos Stoilos, and Zhe Wang. HermiT: An OWL 2 Reasoner. Journal of Automated Reasoning, 53(3):245–269, 2014.
@Article{ghmsw14HermiT,
author = "Birte Glimm and Ian Horrocks and Boris Motik and Giorgos Stoilos and Zhe Wang",
title = "{HermiT: An OWL 2 Reasoner}",
journal = "Journal of Automated Reasoning",
year = "2014",
volume = "53",
number = "3",
pages = "245--269",
}

This system description paper introduces the OWL 2 reasoner HermiT. The reasoner is fully compliant with the OWL 2 Direct Semantics as standardised by the World Wide Web Consortium (W3C). HermiT is based on the hypertableau calculus, and it supports a wide range of standard and novel optimisations that improve the performance of reasoning on real-world ontologies. Apart from the standard OWL 2 reasoning task of entailment checking, HermiT supports several specialised reasoning services such as class and property classification, as well as a range of features outside the OWL 2 standard such as DL-safe rules, SPARQL queries, and description graphs. We discuss the system's architecture, and we present an overview of the techniques used to support the mentioned reasoning tasks. We further compare the performance of reasoning in HermiT with that of FaCT++ and Pellet—two other popular and widely used OWL 2 reasoners.
František Simančík, Boris Motik, and Ian Horrocks. Consequence-Based and Fixed-Parameter Tractable Reasoning in Description Logics. Artificial Intelligence, 209:29–77, 2014.
@Article{smh14consequence-FPT,
author = "Franti{\v{s}}ek Siman{\v{c}}{\'i}k and Boris Motik and Ian Horrocks",
title = "{Consequence-Based and Fixed-Parameter Tractable Reasoning in Description Logics}",
journal = "Artificial Intelligence",
year = "2014",
volume = "209",
pages = "29--77",
}

In this paper we investigate the consequence-based algorithms that are nowadays commonly used for subsumption reasoning with description logic ontologies, presenting the following novel results. First, we present a very general consequence-based reasoning algorithm that can be instantiated so as to capture the essential features of the known algorithms. Second, we use this algorithm to develop a novel framework for a quantitative and parametric analysis of the complexity of subsumption reasoning in description logic ontologies. Our approach is based on the notion of a decomposition—a graph-like structure that, roughly speaking, summarizes the models relevant during ontology reasoning. We identify width and length as decomposition parameters that determine the "level'' of combinatorial reasoning. We prove that, when parameterized by a decomposition, our consequence-based algorithm runs in time that is fixed-parameter tractable in width and length. Third, we briefly discuss how length and width characterize the behavior of tableau algorithms. Fourth, we show that the width and length of existing ontologies are reasonably small, which, we believe, explains the good performance of consequence-based algorithms in practice. We thus obtain a sound foundation for a practical implementation of ontology reasoners, as well as a way to analyze the reasoners' performance.
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies. Journal of Artificial Intelligence Research, 47:741–808, 2013.
@Article{ghkkmmw13acyclicity-journal,
author = "Bernardo Cuenca Grau and Ian Horrocks and Markus Kr{\"o}tzsch and Clemens Kupke and Despoina Magka and Boris Motik and Zhe Wang",
title = "{Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies}",
journal = "Journal of Artificial Intelligence Research",
volume = "47",
pages = "741--808",
year = "2013",
}

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (\MFA) and model-summarising acyclicity (\MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that \MFA and \MSA generalise most of these notions. Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are \MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.
Bernardo Cuenca Grau and Boris Motik. Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach. Journal of Artificial Intelligence Research, 45:197–255, 2012.
@Article{gm12ibq-journal,
author = "Bernardo Cuenca Grau and Boris Motik",
title = "{Reasoning over Ontologies with Hidden Content: The Import-by-Query Approach}",
journal = "Journal of Artificial Intelligence Research",
volume = "45",
pages = "197--255",
year = "2012",
}

There is currently a growing interest in techniques for hiding parts of the signature of an ontology $\hid{\KB}$ that is being reused by another ontology $\vis{\KB}$. Towards this goal, in this paper we propose the import-by-query framework, which makes the content of $\hid{\KB}$ accessible through a limited query interface. If $\vis{\KB}$ reuses the symbols from $\hid{\KB}$ in a certain restricted way, one can reason over ${\vis{\KB} \cup \hid{\KB}}$ by accessing only $\vis{\KB}$ and the query interface. We map out the landscape of the import-by-query problem. In particular, we outline the limitations of our framework and prove that certain restrictions on the expressivity of $\hid{\KB}$ and the way in which $\vis{\KB}$ reuses symbols from $\hid{\KB}$ are strictly necessary to enable reasoning in our setting. We also identify cases in which reasoning is possible and we present suitable import-by-query reasoning algorithms.
Bernardo Cuenca Grau, Boris Motik, Giorgos Stoilos, and Ian Horrocks. Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice. Journal of Artificial Intelligence Research, 43:419–476, 2012.
@Article{gmsh12completeness-guarantees,
author = "Bernardo Cuenca Grau and Boris Motik and Giorgos Stoilos and Ian Horrocks",
title = "{Completeness Guarantees for Incomplete Ontology Reasoners: Theory and Practice}",
journal = "Journal of Artificial Intelligence Research",
volume = "43",
pages = "419--476",
year = "2012",
}

To achieve scalability of query answering, the developers of Semantic Web applications are often forced to use incomplete OWL 2 reasoners, which fail to derive all answers for at least one query, ontology, and data set. The lack of completeness guarantees, however, may be unacceptable for applications in areas such as health care and defence, where missing answers can adversely affect the application's functionality. Furthermore, even if an application can tolerate some level of incompleteness, it is often advantageous to estimate how many and what kind of answers are being lost. In this paper, we present a novel logic-based framework that allows one to check whether a reasoner is complete for a given query $\Q$ and ontology $\T$—that is, whether the reasoner is guaranteed to compute all answers to $\Q$ w.r.t. $\T$ and an arbitrary data set $\A$. Since ontologies and typical queries are often fixed at application design time, our approach allows application developers to check whether a reasoner known to be incomplete in general is actually complete for the kinds of input relevant for the application. We also present a technique that, given a query $\Q$, an ontology $\T$, and reasoners $R_1$ and $R_2$ that satisfy certain assumptions, can be used to determine whether, for each data set $\A$, reasoner $R_1$ computes more answers to $\Q$ w.r.t. $\T$ and $\A$ than reasoner $R_2$. This allows application developers to select the reasoner that provides the highest degree of completeness for $\Q$ and $\T$ that is compatible with the application's scalability requirements. Our results thus provide a theoretical and practical foundation for the design of future ontology-based information systems that maximise scalability while minimising or even eliminating incompleteness of query answers.
Birte Glimm, Ian Horrocks, Boris Motik, Rob Shearer, and Giorgos Stoilos. A Novel Approach to Ontology Classification. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 14:84–101, 2012.
@Article{ghms12ontology-classification,
author = "Birte Glimm and Ian Horrocks and Boris Motik and Rob Shearer and Giorgos Stoilos",
title = "{A Novel Approach to Ontology Classification}",
journal = "Journal of Web Semantics: Science, Services and Agents on the World Wide Web",
volume = "14",
pages = "84--101",
year = "2012",
}

Ontology classification—the computation of the subsumption hierarchies for classes and properties—is a core reasoning service provided by all OWL reasoners known to us. A popular algorithm for computing the class hierarchy is the so-called Enhanced Traversal (ET) algorithm. In this paper we present a new classification algorithm that attempts to address certain shortcomings of ET and improve its performance. Apart from classification of classes, we also consider object and data property classification. Using several simple examples, we show that the algorithms commonly used to implement these tasks are incomplete even for relatively weak ontology languages. Furthermore, we show that property classification can be reduced to class classification, which allows us to classify properties using our optimised algorithm. We implemented all our algorithms in the OWL reasoner HermiT. The results of our performance evaluation show significant performance improvements on several well-known ontologies.
Boris Motik. Representing and Querying Validity Time in RDF and OWL: A Logic-Based Approach. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 12–13:3–21, 2012.
@Article{m12validity-time,
author = "Boris Motik",
title = "{Representing and Querying Validity Time in RDF and OWL: A Logic-Based Approach}",
journal = "Journal of Web Semantics: Science, Services and Agents on the World Wide Web",
volume = "12--13",
pages = "3--21",
year = "2012",
}

RDF(S) and OWL 2 can currently represent only static information. In practice, however, the truth of statements often changes with time. Semantic Web applications often need to represent such changes and reason about them. In this paper we present a logic-based approach for representing validity time in RDF(S) and OWL 2. Unlike the existing proposals, our approach is applicable to nondeterministic entailment relations and/or entailment relations that involve existential quantification, such as the OWL 2 Direct Entailment and the OWL 2 RDF-Based Entailment. We also present an extension of SPARQL that can be used to query temporal RDF(S) and OWL 2. Moreover, we present a general query evaluation algorithm that can be used with all entailment relations used in the Semantic Web. Finally, we present two optimizations of the algorithm that are applicable to entailment relations characterized by a set of deterministic rules, such RDF(S) and OWL 2 RL/RDF Entailment.
Boris Motik and Riccardo Rosati. Reconciling Description Logics and Rules. Journal of the ACM, 57(5):1–62, 2010.
@Article{mr10mknf-rules,
author = "Boris Motik and Riccardo Rosati",
title = "{Reconciling Description Logics and Rules}",
journal = "Journal of the ACM",
volume = "57",
number = "5",
pages = "1--62",
year = "2010",
}

Description logics (DLs) and rules are formalisms that emphasize different aspects of knowledge representation: whereas DLs are focused on specifying and reasoning about conceptual knowledge, rules are focused on nonmonotonic inference. Many applications, however, require features of both DLs and rules. Developing a formalism that integrates DLs and rules would be a natural outcome of a large body of research in knowledge representation and reasoning of the last two decades; however, achieving this goal is very challenging and the approaches proposed thus far have not fully reached it. In this paper, we present a hybrid formalism of \MKNFplus knowledge bases, which integrates DLs and rules in a coherent semantic framework. Achieving seamless integration is nontrivial, since DLs use an open-world assumption, while the rules are based on a closed-world assumption. We overcome this discrepancy by basing the semantics of our formalism on the logic of minimal knowledge and negation as failure (MKNF) by Lifschitz. We present several algorithms for reasoning with \MKNFplus knowledge bases, each suitable to different kinds of rules, and establish tight complexity bounds.
Boris Motik, Rob Shearer, and Ian Horrocks. Hypertableau Reasoning for Description Logics. Journal of Artificial Intelligence Research, 36:165–228, 2009.
@Article{msh09hypertableau,
author = "Boris Motik and Rob Shearer and Ian Horrocks",
title = "{Hypertableau Reasoning for Description Logics}",
journal = "Journal of Artificial Intelligence Research",
year = "2009",
volume = "36",
pages = "165--228",
}

We present a novel reasoning calculus for the description logic SHOIQplus—a knowledge representation formalism with applications in areas such as the Semantic Web. Unnecessary nondeterminism and the construction of large models are two primary sources of inefficiency in the tableau-based reasoning calculi used in state-of-the-art reasoners. In order to reduce nondeterminism, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. In order to reduce the size of the constructed models, we introduce anywhere pairwise blocking. We also present an improved nominal introduction rule that ensures termination in the presence of nominals, inverse roles, and number restrictions—a combination of DL constructs that has proven notoriously difficult to handle. Our implementation shows significant performance improvements over state-of-the-art reasoners on several well-known ontologies.
Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. Tractable Query Answering and Rewriting under Description Logic Constraints. Journal of Applied Logic, 8(2):151–232, 2009.
@Article{pumh09rewriting,
author = "H{\'e}ctor P{\'e}rez-Urbina and Boris Motik and Ian Horrocks",
title = "{Tractable Query Answering and Rewriting under Description Logic Constraints}",
journal = "Journal of Applied Logic",
year = "2009",
volume = "8",
number = "2",
pages = "151--232",
}

Answering queries over an incomplete database w.r.t. a set of constraints is an important computational task with applications in fields as diverse as information integration and metadata management in the semantic Web. Description Logics (DLs) are constraint languages that have been extensively studied with the goal of providing useful modeling constructs while keeping the query answering problem decidable. For many DLs, query answering under constraints can be solved via query rewriting: given a conjunctive query $Q$ and a set of DL constraints $\tbox$, the query $Q$ can be transformed into a datalog query $Q_\tbox$ that takes into account the semantic consequences of $\tbox$; then, to obtain answers to $Q$ w.r.t. $\tbox$ and some (arbitrary) database instance $\abox$, one can simply evaluate $Q_\tbox$ over $\abox$ using existing (deductive) database technology, without taking $\tbox$ into account. In this paper, we present a novel query rewriting algorithm that handles constraints modeled in the DL \ELHIOneg and use it to show that answering conjunctive queries in this setting is PTime-complete w.r.t. data complexity. Our algorithm deals with various description logics of the \EL and \DLlite families and is worst-case optimal w.r.t. data complexity for all of them.
Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, and Ulrike Sattler. Representing Ontologies Using Description Logics, Description Graphs, and Rules. Artificial Intelligence, 173(14):1275–1309, 2009.
@Article{mghs09graphs-journal,
author = "Boris Motik and Bernardo Cuenca Grau and Ian Horrocks and Ulrike Sattler",
title = "{Representing Ontologies Using Description Logics, Description Graphs, and Rules}",
journal = "Artificial Intelligence",
year = "2009",
volume = "173",
number = "14",
pages = "1275--1309",
}

Description logics (DLs) are a family of state-of-the-art knowledge representation languages, and their expressive power has been carefully crafted to provide useful knowledge modeling primitives while allowing for practically effective decision procedures for the basic reasoning problems. Recent experience with DLs, however, has shown that their expressivity is often insufficient to accurately describe structured objects—objects whose parts are interconnected in arbitrary, rather than tree-like ways. DL knowledge bases describing structured objects are therefore usually underconstrained, which precludes the entailment of certain consequences and causes performance problems during reasoning. To address this problem, we propose an extension of DL languages with description graphs—a knowledge modeling construct that can accurately describe objects with parts connected in arbitrary ways. Furthermore, to enable modeling the conditional aspects of structured objects, we also extend DLs with rules. We present an in-depth study of the computational properties of such a formalism. In particular, we first identify the sources of undecidability of the general, unrestricted formalism. Based on that analysis, we then investigate several restrictions of the general formalism that make reasoning decidable. We present practical evidence that such a logic can be used to model nontrivial structured objects. Finally, we present a practical decision procedure for our formalism, as well as tight complexity bounds.
Boris Motik, Ian Horrocks, and Ulrike Sattler. Bridging the Gap Between OWL and Relational Databases. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 7(2):74–89, 2009.
@Article{mhs09owl-dbs,
author = "Boris Motik and Ian Horrocks and Ulrike Sattler",
title = "{Bridging the Gap Between OWL and Relational Databases}",
journal = "Journal of Web Semantics: Science, Services and Agents on the World Wide Web",
year = "2009",
volume = "7",
number = "2",
pages = "74--89",
}

Despite similarities between the Web Ontology Language (OWL) and schema languages traditionally used in relational databases, systems based on these languages exhibit quite different behavior in practice. The schema statements in relational databases are usually interpreted as integrity constraints and are used to check whether the data is structured according to the schema. OWL allows for axioms that resemble integrity constraints; however, these axioms are interpreted under the standard first-order semantics and not as checks. This often leads to confusion and is inappropriate in certain data-centric applications. To explain the source of this confusion, in this paper we compare OWL and relational databases w.r.t. their schema languages and basic computational problems. Based on this comparison, we extend OWL with integrity constraints that capture the intuition behind similar statements in relational databases. We show that, if the integrity constraints are satisfied, they need not be considered while answering a broad range of positive queries. Finally, we discuss several algorithms for checking integrity constraint satisfaction, each of which is suitable to different types of OWL knowledge bases.
Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, Bijan Parsia, Peter Patel-Schneider, and Ulrike Sattler. OWL 2: The next step for OWL. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 6(4):309–322, 2008.
@Article{ghmppss08next-steps,
author = "Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Bijan Parsia and Peter Patel-Schneider and Ulrike Sattler",
title = "{OWL 2: The next step for OWL}",
journal = "Journal of Web Semantics: Science, Services and Agents on the World Wide Web",
year = "2008",
volume = "6",
number = "4",
pages = "309--322",
}

Since achieving W3C recommendation status in 2004, the Web Ontology Language (OWL) has been successfully applied to many problems in computer science. Practical experience with OWL has been quite positive in general; however, it has also revealed room for improvement in several areas. We systematically analyze the identified shortcomings of OWL, such as expressivity issues, problems with its syntaxes, and deficiencies in the definition of OWL species. Furthermore, we present an overview of OWL 2—an extension to and revision of OWL that is currently being developed within the W3C OWL Working Group. Many aspects of OWL have been thoroughly reengineered in OWL 2, thus producing a robust platform for future development of the language.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Deciding Expressive Description Logics in the Framework of Resolution. Information & Computation, 206(5):579–601, 2008.
@Article{hms08deciding,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Deciding Expressive Description Logics in the Framework of Resolution}",
journal = "Information \& Computation",
year = "2008",
volume = "206",
number = "5",
pages = "579--601",
}

We present a decision procedure for the description logic SHIQ based on the basic superposition calculus, and show that it runs in exponential time for unary coding of numbers. To derive our algorithm, we extend basic superposition with a decomposition inference rule, which transforms conclusions of certain inferences into equivalent, but simpler clauses. This rule can be used for general first-order theorem proving with any resolution-based calculus compatible with the standard notion of redundancy.
Yevgeny Kazakov and Boris Motik. A Resolution-Based Decision Procedure for SHOIQ. Journal of Automated Reasoning, 40(2–3):89–116, 2008.
@Article{km07shoiq-journal,
author = "Yevgeny Kazakov and Boris Motik",
title = "{A Resolution-Based Decision Procedure for SHOIQ}",
journal = "Journal of Automated Reasoning",
year = "2008",
volume = "40",
number = "2--3",
pages = "89--116",
}

We present a resolution-based decision procedure for the description logic SHOIQ—the logic underlying the Semantic Web ontology language OWL-DL. Our procedure is goal-oriented, and it naturally extends a similar procedure for SHIQ, which has proven itself in practice. Extending this procedure to SHOIQ using existing techniques is not straightforward because of nominals, number restrictions, and inverse roles—a combination known to cause termination problems. We overcome this difficulty by using the basic superposition calculus extended with custom simplification rules.
Boris Motik. On the Properties of Metamodeling in OWL. Journal of Logic and Computation, 17(4):617–637, 2007.
@Article{motik07metamodeling-journal,
author = "Boris Motik",
title = "{On the Properties of Metamodeling in OWL}",
journal = "Journal of Logic and Computation",
year = "2007",
volume = "17",
number = "4",
pages = "617--637",
}

A common practice in conceptual modeling is to separate the conceptual from the data model. Although very intuitive, this approach is inadequate for many complex domains, in which the borderline between the two models is not clear-cut. Therefore, OWL-Full, the most expressive of the Semantic Web ontology languages, allows us to combine the conceptual and the data model by a feature we refer to as metamodeling. In this paper, we show that the semantics of metamodeling adopted in OWL-Full leads to the undecidability of basic inference problems due to the free usage of the built-in vocabulary. Based on this result, we propose two alternative semantics for metamodeling: the contextual and the HiLog semantics. We present several examples showing how to use the latter semantics to axiomatize the interaction between concepts and metaconcepts. Finally, we show that SHOIQD—the description logic underlying OWL-DL—is still decidable when extended with metamodeling under either semantics.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Reasoning in Description Logics by a Reduction to Disjunctive Datalog. Journal of Automated Reasoning, 39(3):351–384, 2007.
@Article{hms07reasoning,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Reasoning in Description Logics by a Reduction to Disjunctive Datalog}",
journal = "Journal of Automated Reasoning",
year = "2007",
volume = "39",
number = "3",
pages = "351--384",
}

As applications of description logics proliferate, efficient reasoning with knowledge bases containing many assertions becomes ever more important. For such cases, we developed a novel reasoning algorithm that reduces a SHIQ knowledge base to a disjunctive datalog program while preserving the set of ground consequences. Queries can then be answered in the resulting program while reusing existing and practically proven optimization techniques of deductive databases, such as join-order optimizations or magic sets. Moreover, we use our algorithm to derive precise data complexity bounds: we show that SHIQ is data complete for NP, and we identify an expressive fragment of SHIQ with polynomial data complexity.
Boris Motik, Ulrike Sattler, and Rudi Studer. Query Answering for OWL-DL with Rules. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 3(1):41–60, 2005.
@Article{mss05query-journal,
author = "Boris Motik and Ulrike Sattler and Rudi Studer",
title = "{Query Answering for OWL-DL with Rules}",
journal = "Journal of Web Semantics: Science, Services and Agents on the World Wide Web",
year = "2005",
volume = "3",
number = "1",
pages = "41--60",
}

Both OWL-DL and function-free Horn rules are decidable fragments of first-order logic with interesting, yet orthogonal expressive power. A combination of OWL-DL and rules is desirable for the Semantic Web; however, it might easily lead to the undecidability of interesting reasoning problems. Here, we present a decidable such combination where rules are required to be DL-safe: each variable in the rule is required to occur in a non-DL-atom in the rule body. We discuss the expressive power of such a combination and present an algorithm for query answering in the related logic SHIQ extended with DL-safe rules, based on a reduction to disjunctive programs.
Raphael Volz, Steffen Staab, and Boris Motik. Incrementally Maintaining Materializations of Ontologies Stored in Logic Databases. Journal of Data Semantics II, 3360:1–34, 2005. LNCS, Springer.
@Article{vsm05incrementally,
author = "Raphael Volz and Steffen Staab and Boris Motik",
title = "{Incrementally Maintaining Materializations of Ontologies Stored in Logic Databases}",
journal = "Journal of Data Semantics II",
year = "2005",
volume = "3360",
note = "LNCS, Springer",
pages = "1--34",
}

This article presents a technique to incrementally maintain materializations of ontological entailments. Materialization consists in precomputing and storing a set of implicit entailments, such that frequent and/or crucial queries to the ontology can be solved more efficiently. The central problem that arises with materialization is its maintenance when axioms change, viz. the process of propagating changes in explicit axioms to the stored implicit entailments. par When considering rule-enabled ontology languages that are operationalized in logic databases, we can distinguish two types of changes. Changes to the ontology will typically manifest themselves in changes to the rules of the logic program, whereas changes to facts will typically lead to changes in the extensions of logical predicates. The incremental maintenance of the latter type of changes has been studied extensively in the deductive database context and we apply the technique proposed in [30] for our purpose. The former type of changes has, however, not been tackled before. par In this article we elaborate on our previous papers [32, 33], which extend the approach of [30] to deal with changes in the logic program. Our approach is not limited to a particular ontology language but can be generally applied to arbitrary ontology languages that can be translated to Datalog programs, i.e. such as O-Telos, F-Logic [16] RDF(S), or Description Logic Programs [34].
Alexander Maedche, Boris Motik, and Ljiljana Stojanovic. Managing multiple and distributed ontologies on the Semantic Web. VLDB Journal, 12(4):286–302, 2003.
@Article{mms03managing,
author = "Alexander Maedche and Boris Motik and Ljiljana Stojanovic",
title = "{Managing multiple and distributed ontologies on the Semantic Web}",
journal = "VLDB Journal",
year = "2003",
volume = "12",
number = "4",
pages = "286--302",
}

In traditional software systems, significant attention is devoted to keeping modules well separated and coherent with respect to functionality, thus ensuring that changes in the system are localized to a handful of modules. Reuse is seen as the key method in reaching that goal. Ontology-based systems on the Semantic Web are just a special class of software systems, so the same principles apply. In this article, we present an integrated framework for managing multiple and distributed ontologies on the Semant ic Web. It is based on the representation model for ontologies, trading off between expressivity and tractability. In our framework, we provide features for reusing existing ontologies and for evolving them while retaining the consistency. The approach is implemented within KAON, the Karlsruhe Ontology and SemanticWeb tool suite.
Alexander Maedche, Boris Motik, Ljiljana Stojanovic, Rudi Studer, and Raphael Volz. Ontologies for Enterprise Knowledge Management. IEEE Intelligent Systems, 18(2):26–33, 2003.
@Article{mmssv03ontologies,
author = "Alexander Maedche and Boris Motik and Ljiljana Stojanovic and Rudi Studer and Raphael Volz",
title = "{Ontologies for Enterprise Knowledge Management}",
journal = "IEEE Intelligent Systems",
volume = "18",
number = "2",
year = "2003",
pages = "26--33",
}

Alexander Maedche and Boris Motik. Repräsentations- und Anfragesprachen für Ontologien—eine Übersicht. Datenbank-Spektrum, 6:43–53, 2003. In German.
@Article{mm03db-spektrum,
author = "Alexander Maedche and Boris Motik",
title = "{Repr{\"a}sentations- und Anfragesprachen f{\"u}r Ontologien---eine {\"U}bersicht}",
journal = "Datenbank-Spektrum",
year = "2003",
volume = "6",
note = "In German",
pages = "43--53",
}

Semantik spielt in vielen Anwendungsgebieten eine wichtige Rolle. Eines der Anwendungsgebiete von semantischen Modellen ist die Informationsintegration, in welcher heterogene Informationsquellen zusammengeführt werden. Dieser Beitrag gibt eine Einführung und Übersicht über den aktuellen Stand im Bereich der Repräsentations- und Anfragesprachen für semantische Modelle und stellt den Karlsruher Ansatz KAON zur Ontologierepräsentation und -anfrage vor.

## In Conferences

Michael Benedikt, George Konstantinidis, Giansalvatore Mecca, Boris Motik, Paolo Papotti, Donatello Santoro, and Efthymia Tsamoura. Benchmarking the Chase. In Floris Geerts, editor, Proc. of 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017)), Raleigh, NC, USA, May 14–19 2017. ACM. To appear.
@InProceedings{bkmmpst17becnhmarking-chase,
author = "Michael Benedikt and George Konstantinidis and Giansalvatore Mecca and Boris Motik and Paolo Papotti and Donatello Santoro and Efthymia Tsamoura",
title = "{Benchmarking the Chase}",
booktitle = "Proc. of 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017))",
editor = "Floris Geerts",
month = "May 14--19",
year = "2017",
publisher = "ACM",
xpages = "480--497",
note = "To appear",
}

The chase is a family of algorithms used in a number of data management tasks, such as data exchange, answering queries under dependencies, query reformulation with constraints, and data cleaning. It is well established as a theoretical tool for understanding these tasks, and in addition a number of prototype systems have been developed. While individual chase-based systems and particular optimizations of the chase have been experimentally evaluated in the past, we provide the first comprehensive and publicly available benchmark—test infrastructure and a set of test scenarios—for evaluating chase implementations across a wide range of assumptions about the dependencies and the data. We used our benchmark to compare chase-based systems on data exchange and query answering tasks with one another, as well as with systems that can solve similar tasks developed in closely related communities. Our evaluation provided us with a number of new insights concerning the factors that impact the performance of chase implementations.
Anthony Potter, Boris Motik, Yavor Nenov, and Ian Horrocks. Distributed RDF Query Answering with Dynamic Data Exchange. In Paul T. Groth, Elena Simperl, Alasdair J. G. Gray, Marta Sabou, Markus Krötzsch, Freddy Lécué, Fabian Flöck, and Yolanda Gil, editors, Proc. of the 15th Int. Semantic Web Conf., Part I (ISWC 2016), volume 9981 of LNCS, pages 480–497, Kobe, Japan, October 17–21 2016. Springer.
@InProceedings{pmnh16distributed-RDF-query,
author = "Anthony Potter and Boris Motik and Yavor Nenov and Ian Horrocks",
title = "{Distributed RDF Query Answering with Dynamic Data Exchange}",
booktitle = "Proc. of the 15th Int. Semantic Web Conf., Part I (ISWC 2016)",
editor = "Paul T. Groth and Elena Simperl and Alasdair J. G. Gray and Marta Sabou and Markus Kr{\"o}tzsch and Freddy L{\'e}cu{\'e} and Fabian Fl{\"o}ck and Yolanda Gil",
month = "October 17--21",
year = "2016",
publisher = "Springer",
series = "LNCS",
volume = "9981",
pages = "480--497",
}

Evaluating joins over RDF data stored in a shared-nothing server cluster is key to processing truly large RDF datasets. To the best of our knowledge, the existing approaches use a variant of the data exchange operator that is inserted into the query plan statically (i.e., at query compile time) to shuffle data between servers. We argue that such approaches often miss opportunities for local computation, and we present a novel solution to distributed query answering that consists of two main components. First, we present a query answering algorithm based on dynamic data exchange, which exploits data locality to maximise the amount of computation on a single server. Second, we present a partitioning algorithm for RDF data based on graph partitioning whose aim is to increase data locality. We have implemented our approach in the RDFox system, and our performance evaluation suggests that our techniques outperform the state of the art by up to an order of magnitude in terms of query evaluation times, network communication, and memory use.
Robert Piro, Yavor Nenov, Boris Motik, Ian Horrocks, Peter Hendler, Scott Kimberly, and Michael Rossman. Semantic Technologies for Data Analysis in Health Care. In Paul T. Groth, Elena Simperl, Alasdair J. G. Gray, Marta Sabou, Markus Krötzsch, Freddy Lécué, Fabian Flöck, and Yolanda Gil, editors, Proc. of the 15th Int. Semantic Web Conf., Part II (ISWC 2016), volume 9982 of LNCS, pages 400–417, Kobe, Japan, October 17–21 2016. Springer.
@InProceedings{pnmhhkr16semantic-health-care,
author = "Robert Piro and Yavor Nenov and Boris Motik and Ian Horrocks and Peter Hendler and Scott Kimberly and Michael Rossman",
title = "{Semantic Technologies for Data Analysis in Health Care}",
booktitle = "Proc. of the 15th Int. Semantic Web Conf., Part II (ISWC 2016)",
editor = "Paul T. Groth and Elena Simperl and Alasdair J. G. Gray and Marta Sabou and Markus Kr{\"o}tzsch and Freddy L{\'e}cu{\'e} and Fabian Fl{\"o}ck and Yolanda Gil",
month = "October 17--21",
year = "2016",
publisher = "Springer",
series = "LNCS",
volume = "9982",
pages = "400--417",
}

A fruitful application of Semantic Technologies in the field of healthcare data analysis has emerged from the collaboration between Oxford and Kaiser Permanente a US healthcare provider (HMO). US HMOs have to annually deliver measurement results on their quality of care to US authorities. One of these sets of measurements is defined in a specification called HEDIS which is infamous amongst data analysts for its complexity. Traditional solutions with either SAS-programs or SQL-queries lead to involved solutions whose maintenance and validation is difficult and binds considerable amount of resources. In this paper we present the project in which we have applied Semantic Technologies to compute the most difficult part of the HEDIS measures. We show that we arrive at a clean, structured and legible encoding of HEDIS in the rule language of the RDF-triple store RDFox. We use RDFox's reasoning capabilities and SPARQL queries to compute and extract the results. The results of a whole Kaiser Permanente regional branch could be computed in competitive time by RDFox on readily available commodity hardware. Further development and deployment of the project results are envisaged in Kaiser Permanente.
Andrew Bate, Boris Motik, Bernardo Cuenca Grau, František Simančík, and Ian Horrocks. Extending Consequence-Based Reasoning to SRIQ. In Chitta Baral, James P. Delgrande, and Frank Wolter, editors, Proc. of the 15th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2016), pages 187–196, Cape Town, South Africa, April 25–29 2016.
@InProceedings{bmcgsh16consequence-based-SHIQ,
author = "Andrew Bate and Boris Motik and Bernardo {Cuenca Grau} and Franti{\v{s}}ek Siman{\v{c}}{\'i}k and Ian Horrocks",
title = "{Extending Consequence-Based Reasoning to $\mathcal{SRIQ}$}",
booktitle = "Proc. of the 15th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2016)",
editor = "Chitta Baral and James P. Delgrande and Frank Wolter",
address = "Cape Town, South Africa",
month = "April 25--29",
year = "2016",
pages = "187--196",
}

Consequence-based calculi are a family of reasoning algorithms for description logics (DLs), and they combine hypertableau and resolution in a way that often achieves excellent performance in practice. Up to now, however, they were proposed for either Horn DLs (which do not support disjunction), or for DLs without counting quantifiers. In this paper we present a novel consequence-based calculus for \SRIQ—a rich DL that supports both features. This extension is non-trivial since the intermediate consequences that need to be derived during reasoning cannot be captured using DLs themselves. The results of our preliminary performance evaluation suggest the feasibility of our approach in practice.
Yavor Nenov, Robert Piro, Boris Motik, Ian Horrocks, Zhe Wu, and Jay Banerjee. RDFox: A Highly-Scalable RDF Store. In Marcelo Arenas, Óscar Corcho, Elena Simperl, Markus Strohmaier, Mathieu d'Aquin, Kavitha Srinivas, Paul T. Groth, Michel Dumontier, Jeff Heflin, Krishnaprasad Thirunarayan, and Steffen Staab, editors, Proc. of the 14th Int. Semantic Web Conf. (ISWC 2015), volume 9367 of LNCS, pages 3–20, Bethlehem, PA, USA, October 11–15 2015. Springer.
@InProceedings{npmhwb15RDFox-scalable,
author = "Yavor Nenov and Robert Piro and Boris Motik and Ian Horrocks and Zhe Wu and Jay Banerjee",
title = "{RDFox: A Highly-Scalable RDF Store}",
booktitle = "Proc. of the 14th Int. Semantic Web Conf. (ISWC 2015)",
editor = "Marcelo Arenas and {\'O}scar Corcho and Elena Simperl and Markus Strohmaier and Mathieu d'Aquin and Kavitha Srinivas and Paul T. Groth and Michel Dumontier and Jeff Heflin and Krishnaprasad Thirunarayan and Steffen Staab",
month = "October 11--15",
year = "2015",
publisher = "Springer",
series = "LNCS",
volume = "9367",
pages = "3--20",
}

We present RDFox—a main-memory, scalable, centralised RDF store that supports materialisation-based parallel datalog reasoning and SPARQL query answering. RDFox uses novel and highly-efficient parallel reasoning algorithms for the computation and incremental update of datalog materialisations with efficient handling of \sameAs. In this system description paper, we present an overview of the system architecture and highlight the main ideas behind our indexing data structures and our novel reasoning algorithms. In addition, we evaluate RDFox on a high-end SPARC T5-8 server with 128 physical cores and 4TB of RAM. Our results show that RDFox can effectively exploit such a machine, achieving speedups of up to 87 times, storage of up to 9.2 billion triples, memory usage as low as 36.9 bytes per triple, importation rates of up to 1 million triples per second, and reasoning rates of up to 6.1 million triples per second.
Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. Combining Rewriting and Incremental Materialisation Maintenance for Datalog Programs with Equality. In Qiang Yang and Michael Wooldridge, editors, Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI 2015), pages 3127–3133, Buenos Aires, Argentina, July 25–31 2015. AAAI Press.
@InProceedings{mnph15incremental-BF-sameAs,
author = "Boris Motik and Yavor Nenov and Robert Piro and Ian Horrocks",
title = "{Combining Rewriting and Incremental Materialisation Maintenance for Datalog Programs with Equality}",
booktitle = "Proc. of the 24th Int. Joint Conf. on Artificial Intelligence (IJCAI 2015)",
editor = "Qiang Yang and Michael Wooldridge",
month = "July 25--31",
year = "2015",
publisher = "AAAI Press",
pages = "3127--3133",
}

Materialisation precomputes all consequences of a set of facts and a datalog program so that queries can be evaluated directly (i.e., independently from the program). Rewriting optimises materialisation for datalog programs with equality by replacing all equal constants with a single representative; and incremental maintenance algorithms can efficiently update a materialisation for small changes in the input facts. Both techniques are critical to practical applicability of datalog systems; however, we are unaware of an approach that combines rewriting and incremental maintenance. In this paper we present the first such combination, and we show empirically that it can speed up updates by several orders of magnitude compared to using either rewriting or incremental maintenance in isolation.
Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm. In Blai Bonet and Sven Koenig, editors, Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015), pages 1560–1568, Austin, TX, USA, January 25–30 2015. AAAI Press.
@InProceedings{mnph15incremental-BF,
author = "Boris Motik and Yavor Nenov and Robert Piro and Ian Horrocks",
title = "{Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm}",
booktitle = "Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015)",
editor = "Blai Bonet and Sven Koenig",
month = "January 25--30",
year = "2015",
publisher = "AAAI Press",
pages = "1560--1568",
}

Datalog-based systems often materialise all consequences of a datalog program and the data, allowing users' queries to be evaluated directly in the materialisation. This process, however, can be computationally intensive, so most systems update the materialisation incrementally when input data changes. We argue that existing solutions, such as the well-known Delete/Rederive (DRed) algorithm, can be inefficient in cases when facts have many alternate derivations. As a possible remedy, we propose a novel Backward/Forward (B/F) algorithm that tries to reduce the amount of work by a combination of backward and forward chaining. In our evaluation, the B/F algorithm was several orders of magnitude more efficient than the DRed algorithm on some inputs, and it was never significantly less efficient.
Boris Motik, Yavor Nenov, Robert Piro, and Ian Horrocks. Handling owl:sameAs via Rewriting. In Blai Bonet and Sven Koenig, editors, Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015), pages 231–237, Austin, TX, USA, January 25–30 2015. AAAI Press.
@InProceedings{mnph15owl-sameAs-rewriting,
author = "Boris Motik and Yavor Nenov and Robert Piro and Ian Horrocks",
title = "{Handling owl:sameAs via Rewriting}",
booktitle = "Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015)",
editor = "Blai Bonet and Sven Koenig",
month = "January 25--30",
year = "2015",
publisher = "AAAI Press",
pages = "231--237",
}

Rewriting is widely used to optimise \sameAs reasoning in materialisation based OWL 2 RL systems. We investigate issues related to both the correctness and efficiency of rewriting, and present an algorithm that guarantees correctness, improves efficiency, and can be effectively parallelised. Our evaluation shows that our approach can reduce reasoning times on practical data sets by orders of magnitude.
Giorgio Stefanoni and Boris Motik. Answering Conjunctive Queries over EL Knowledge Bases with Transitive and Reflexive Roles. In Blai Bonet and Sven Koenig, editors, Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015), pages 1611–1617, Austin, TX, USA, January 25–30 2015. AAAI Press.
@InProceedings{sm15transitive-reflexive-EL-CQ,
author = "Giorgio Stefanoni and Boris Motik",
title = "{Answering Conjunctive Queries over EL Knowledge Bases with Transitive and Reflexive Roles}",
booktitle = "Proc. of the 29th AAAI Conf. on Artificial Intelligence (AAAI 2015)",
editor = "Blai Bonet and Sven Koenig",
month = "January 25--30",
year = "2015",
publisher = "AAAI Press",
pages = "1611--1617",
}

Answering conjunctive queries (CQs) over \el knowledge bases (KBs) with complex role inclusions is \pspace-hard and in \pspace in certain cases; however, if complex role inclusions are restricted to role transitivity, a tight upper complexity bound has so far been unknown. Furthermore, the existing algorithms cannot handle reflexive roles, and they are not practicable. Finally, the problem is tractable for acyclic CQs and $\mathcal{ELH}$, and \np-complete for unrestricted CQs and \elho KBs. In this paper we complete the complexity landscape of CQ answering for several important cases. In particular, we present a practicable \np algorithm for answering CQs over \elhso KBs—a logic containing all of OWL 2 EL, but with complex role inclusions restricted to role transitivity. Our preliminary evaluation suggests that the algorithm can be suitable for practical use. Moreover, we show that, even for a restricted class of so-called arborescent acyclic queries, CQ answering over \el KBs becomes \np-hard in the presence of either transitive or reflexive roles. Finally, we show that answering arborescent CQs over \elho KBs is tractable, whereas answering acyclic CQs is \np-hard.
Boris Motik, Yavor Nenov, Robert Piro, Ian Horrocks, and Dan Olteanu. Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems. In Carla E. Brodley and Peter Stone, editors, Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI 2014), pages 129–137, Québec City, Québec, Canada, July 27–31 2014. AAAI Press.
@InProceedings{mnpho14parallel-materialisation-RDFox,
author = "Boris Motik and Yavor Nenov and Robert Piro and Ian Horrocks and Dan Olteanu",
title = "{Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems}",
booktitle = "Proc. of the 28th AAAI Conf. on Artificial Intelligence (AAAI 2014)",
editor = "Carla E. Brodley and Peter Stone",
month = "July 27--31",
year = "2014",
publisher = "AAAI Press",
pages = "129--137",
}

We present a novel approach to parallel materialisation (i.e., fixpoint computation) of datalog programs in centralised, main-memory, multi-core RDF systems. Our approach comprises an algorithm that evenly distributes the workload to cores, and an RDF indexing data structure that supports efficient, mostly' lock-free parallel updates. Our empirical evaluation shows that our approach parallelises computation very well: with 16 physical cores, materialisation can be up to 13.9 times faster than with just one core.
Pierre Chaussecourte, Birte Glimm, Ian Horrocks, Boris Motik, and Laurent Pierre. The Energy Management Adviser at EDF. In Harith Alani, Lalana Kagal, Achille Fokoue, Paul Groth, Chris Biemann, Josiane Xavier Parreira, Lora Aroyo, Natasha Noy, Chris Welty, and Krzysztof Janowicz, editors, Proc. of the 12th Int. Semantic Web Conf. (ISWC 2013), In-Use Track, volume 8219 of LNCS, pages 49–64, Sydney, NSW, Australia, October 21–25 2013. Springer.
@InProceedings{cghmp13energy-EDF,
author = "Pierre Chaussecourte and Birte Glimm and Ian Horrocks and Boris Motik and Laurent Pierre",
title = "{The Energy Management Adviser at EDF}",
booktitle = "Proc. of the 12th Int. Semantic Web Conf. (ISWC 2013), In-Use Track",
editor = "Harith Alani and Lalana Kagal and Achille Fokoue and Paul Groth and Chris Biemann and Josiane Xavier Parreira and Lora Aroyo and Natasha Noy and Chris Welty and Krzysztof Janowicz",
month = "October 21--25",
year = "2013",
publisher = "Springer",
series = "LNCS",
volume = "8219",
pages = "49--64",
}

The EMA (Energy Management Adviser) aims to produce personalised energy saving advice for EDF's customers. The advice takes the form of one or more tips', and personalisation is achieved using semantic technologies: customers are described using RDF, an OWL ontology provides a conceptual model of the relevant domain (housing, environment, and so on) and the different kinds of tips, and SPARQL query answering is used to identify relevant tips. The current prototype provides tips to more than 300,000 EDF customers in France at least twice a year. The main challenges for our future work include providing a timely service for all of the 35 million EDF customers in France, simplifying the system's maintenance, and providing new ways for interacting with customers such as via a Web site.
Bernardo Cuenca Grau, Boris Motik, Giorgios Stoilos, and Ian Horrocks. Computing Datalog Rewritings Beyond Horn Ontologies. In Francesca Rossi, editor, Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI 2013), pages 832–838, Beijing, China, August 3–9 2013.
@InProceedings{gmsh13beyond-horn,
author = "Bernardo {Cuenca Grau} and Boris Motik and Giorgios Stoilos and Ian Horrocks",
title = "{Computing Datalog Rewritings Beyond Horn Ontologies}",
booktitle = "Proc. of the 23rd Int. Joint Conf. on Artificial Intelligence (IJCAI 2013)",
editor = "Francesca Rossi",
month = "August 3--9",
year = "2013",
pages = "832--838",
}

Rewriting-based approaches for answering queries over an OWL 2 DL ontology have so far been developed mainly for Horn fragments of OWL 2 DL. In this paper, we study the possibilities of answering queries over non-Horn ontologies using datalog rewritings. We prove that this is impossible in general even for very simple ontology languages, and even if $Ptime = NP$. Furthermore, we present a resolution-based procedure for $\SHI$ ontologies that, in case it terminates, produces a datalog rewriting of the ontology. We also show that our procedure necessarily terminates on $\Bool$ ontologies—an extension of OWL 2 QL with transitive roles and Boolean connectives.
Giorgio Stefanoni, Boris Motik, and Ian Horrocks. Introducing Nominals to the Combined Query Answering Approaches for EL. In Marie desJardins and Michael L. Littman, editors, Proc. of the 27th AAAI Conf. on Artificial Intelligence (AAAI 2013), pages 1177–1183, Bellevue, WA, USA, July 14–18 2013.
@InProceedings{smh13nominals-combined,
author = "Giorgio Stefanoni and Boris Motik and Ian Horrocks",
title = "{Introducing Nominals to the Combined Query Answering Approaches for $\mathcal{EL}$}",
booktitle = "Proc. of the 27th AAAI Conf. on Artificial Intelligence (AAAI 2013)",
editor = "Marie desJardins and Michael L. Littman",
month = "July 14--18",
year = "2013",
pages = "1177--1183",
}

So-called combined approaches answer a conjunctive query over a description logic ontology in three steps: first, they materialise certain consequences of the ontology and the data; second, they evaluate the query over the data; and third, they filter the result of the second phase to eliminate unsound answers. Such approaches were developed for various members of the DL-Lite and the EL families of languages, but none of them can handle ontologies containing nominals. In our work, we bridge this gap and present a combined query answering approach for \elho—a logic that contains all features of the OWL 2 EL standard apart from transitive roles and complex role inclusions. This extension is nontrivial because nominals require equality reasoning, which introduces complexity into the first and the third step. Our empirical evaluation suggests that our technique is suitable for practical application, and so it provides a practical basis for conjunctive query answering in a large fragment of OWL 2 EL.
Despoina Magka, Boris Motik, and Ian Horrocks. Modelling Structured Domains Using Description Graphs and Logic Programming. In Elena Simperl, Philipp Cimiano, Axel Polleres, Óscar Corcho, and Valentina Presutti, editors, Proc. of the 9th Extended Semantic Web Conference (ESWC 2012), volume 7295 of LNCS, pages 330–344, Heraklion, Greece, May 27–31 2012. Springer.
@InProceedings{mmh12dgs-and-lp,
author = "Despoina Magka and Boris Motik and Ian Horrocks",
title = "{Modelling Structured Domains Using Description Graphs and Logic Programming}",
booktitle = "Proc. of the 9th Extended Semantic Web Conference (ESWC 2012)",
editor = "Elena Simperl and Philipp Cimiano and Axel Polleres and {\'O}scar Corcho and Valentina Presutti",
month = "May 27--31",
year = "2012",
publisher = "Springer",
series = "LNCS",
volume = "7295",
pages = "330--344",
}

Although OWL 2 is widely used to describe complex objects such as chemical molecules, it cannot represent structural' features of chemical entities (e.g., having a ring). A combination of rules and description graphs (DGs) has been proposed as a possible solution, but it still exhibits several drawbacks. In this paper we present a radically different approach that we call Description Graph Logic Programs. Syntactically, our approach combines DGs, rules, and OWL 2 RL axioms, but its semantics is defined via a translation into logic programs under stable model semantics. The result is an expressive OWL 2 RL-compatible formalism that is well suited for modelling objects with complex structure.
Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, and Zhe Wang. Acyclicity Conditions and their Application to Query Answering in Description Logics. In Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith, editors, Proc. of the 13th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2012), pages 243–253, Rome, Italy, June 10–14 2012.
@InProceedings{ghkkmmw12acyclicity,
author = "Bernardo {Cuenca Grau} and Ian Horrocks and Markus Kr{\"o}tzsch and Clemens Kupke and Despoina Magka and Boris Motik and Zhe Wang",
title = "{Acyclicity Conditions and their Application to Query Answering in Description Logics}",
booktitle = "Proc. of the 13th Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR 2012)",
editor = "Gerhard Brewka and Thomas Eiter and Sheila A. McIlraith",
month = "June 10--14",
year = "2012",
pages = "243--253",
}

Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a key problem in knowledge representation and databases. This problem can be solved using the chase (aka materialisation) algorithm; however, CQ answering is undecidable for general existential rules, so the chase is not guaranteed to terminate. Several acyclicity conditions provide sufficient conditions for chase termination. In this paper, we present two novel such conditions—model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA)—that generalise many of the acyclicity conditions known so far in the literature. Materialisation provides the basis for several widely-used OWL 2 DL reasoners. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2 DL; furthermore, some systems go beyond OWL 2 RL, but they provide no termination guarantees. In this paper we investigate whether various acyclicity conditions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 DL ontologies are MSA, and that the facts obtained via materialisation are not too large. Thus, our results suggest that principled extensions to materialisation-based OWL 2 DL reasoners may be practically feasible.
Boris Motik, Ian Horrocks, and Su Myeon Kim. Delta-Reasoner: A Semantic Web Reasoner for an Intelligent Mobile Platform. In Alain Mille, Fabien L. Gandon, Jacques Misselis, Michael Rabinovich, and Steffen Staab, editors, Proc. of the 21st Int. World Wide Web Conference (WWW 2012), Industry Track, pages 63–72, Lyon, France, April 16–20 2012.
@InProceedings{mhk12delta-reasoner,
author = "Boris Motik and Ian Horrocks and Su Myeon Kim",
title = "{Delta-Reasoner: A Semantic Web Reasoner for an Intelligent Mobile Platform}",
booktitle = "Proc. of the 21st Int. World Wide Web Conference (WWW 2012), Industry Track",
editor = "Alain Mille and Fabien L. Gandon and Jacques Misselis and Michael Rabinovich and Steffen Staab",
month = "April 16--20",
year = "2012",
pages = "63--72",
}

To make mobile device applications more intelligent, one can combine the information obtained via device sensors with background knowledge in order to deduce the user's current context, and then use this context to adapt the application's behaviour to the user's needs. In this paper we describe \Dreasoner, a key component of the Intelligent Mobile Platform (IMP), which was designed to support context-aware applications running on mobile devices. Context-aware applications and the mobile platform impose unusual requirements on the reasoner, which we have met by incorporating advanced features such as incremental reasoning and continuous query evaluation into our reasoner. Although we have so far been able to conduct only a very preliminary performance evaluation, our results are very encouraging: our reasoner exhibits sub-second response time on ontologies whose size significantly exceeds the size of the ontologies used in the IMP.
Giorgos Stoilos, Bernardo Cuenca Grau, Boris Motik, and Ian Horrocks. Repairing Ontologies for Incomplete Reasoners. In Lora Aroyo, Chris Welty, Harith Alani, Jamie Taylor, Abraham Bernstein, Lalana Kagal, Natasha Fridman Noy, and Eva Blomqvist, editors, Proc. of the 10th Int. Semantic Web Conf. (ISWC 2011), volume 7031 of LNCS, pages 681–696, Bonn, Germany, October 23–27 2011. Springer.
@InProceedings{sgmh11repairing,
author = "Giorgos Stoilos and Bernardo Cuenca Grau and Boris Motik and Ian Horrocks",
title = "{Repairing Ontologies for Incomplete Reasoners}",
booktitle = "Proc. of the 10th Int. Semantic Web Conf. (ISWC 2011)",
editor = "Lora Aroyo and Chris Welty and Harith Alani and Jamie Taylor and Abraham Bernstein and Lalana Kagal and Natasha Fridman Noy and Eva Blomqvist",
month = "October 23--27",
year = "2011",
publisher = "Springer",
series = "LNCS",
volume = "7031",
pages = "681--696",
}

The need for scalable query answering often forces Semantic Web applications to use incomplete OWL 2 reasoners, which in some cases fail to derive all answers to a query. This is clearly undesirable, and in some applications may even be unacceptable. To address this problem, we investigate the problem of repairing' an ontology $\T$—that is, computing an ontology $\R$ such that a reasoner that is incomplete for $\T$ becomes complete when used with $\T \cup \R$. We identify conditions on $\T$ and the reasoner that make this possible, present a practical algorithm for computing $\R$, and present a preliminary evaluation which shows that, in some realistic cases, repairs are feasible to compute, reasonable in size, and do not significantly affect reasoner performance.
Boris Motik. Representing and Querying Validity Time in RDF and OWL: A Logic-Based Approach. In Peter F. Patel-Schneider, Yue Pan, Pascal Hitzler, Peter Mika, Lei Zhang, Jeff Z. Pan, Ian Horrocks, and Birte Glimm, editors, Proc. of the 9th Int. Semantic Web Conf. (ISWC 2010), volume 6496 of LNCS, pages 550–565, Shanghai, China, November 7–11 2010. Springer.
@InProceedings{m10validity-time,
author = "Boris Motik",
title = "{Representing and Querying Validity Time in RDF and OWL: A Logic-Based Approach}",
booktitle = "Proc. of the 9th Int. Semantic Web Conf. (ISWC 2010)",
editor = "Peter F. Patel-Schneider and Yue Pan and Pascal Hitzler and Peter Mika and Lei Zhang and Jeff Z. Pan and Ian Horrocks and Birte Glimm",
month = "November 7--11",
year = "2010",
publisher = "Springer",
series = "LNCS",
volume = "6496",
pages = "550--565",
}

RDF(S) and OWL 2 currently support only static ontologies. In practice, however, the truth of statements often changes with time, and Semantic Web applications often need to represent such changes and reason about them. In this paper we present a logic-based approach for representing validity time in RDF and OWL. Unlike the existing proposals, our approach is applicable to entailment relations that are not deterministic, such as the Direct Semantics or the RDF-Based Semantics of OWL 2. We also extend SPARQL to temporal RDF graphs and present a query evaluation algorithm. Finally, we present an optimization of our algorithm that is applicable to entailment relations characterized by a set of deterministic rules, such RDF(S) and OWL 2 RL/RDF entailment.
Birte Glimm, Ian Horrocks, Boris Motik, and Giorgos Stoilos. Optimising Ontology Classification. In Peter F. Patel-Schneider, Yue Pan, Pascal Hitzler, Peter Mika, Lei Zhang, Jeff Z. Pan, Ian Horrocks, and Birte Glimm, editors, Proc. of the 9th Int. Semantic Web Conf. (ISWC 2010), volume 6496 of LNCS, pages 225–240, Shanghai, China, November 7–11 2010. Springer.
@InProceedings{ghms10classification,
author = "Birte Glimm and Ian Horrocks and Boris Motik and Giorgos Stoilos",
title = "{Optimising Ontology Classification}",
booktitle = "Proc. of the 9th Int. Semantic Web Conf. (ISWC 2010)",
editor = "Peter F. Patel-Schneider and Yue Pan and Pascal Hitzler and Peter Mika and Lei Zhang and Jeff Z. Pan and Ian Horrocks and Birte Glimm",
month = "November 7--11",
year = "2010",
publisher = "Springer",
series = "LNCS",
volume = "6496",
pages = "225--240",
}

Ontology classification—the computation of subsumption hierarchies for classes and properties—is one of the most important tasks for OWL reasoners. Based on the algorithm by Shearer and Horrocks \cite{Rob09a}, we present a new classification procedure that addresses several open issues of the original algorithm, and that uses several novel optimisations in order to achieve superior performance. We also consider the classification of (object and data) properties. We show that algorithms commonly used to implement that task are incomplete even for relatively weak ontology languages. Furthermore, we show how to reduce the property classification problem into a standard (class) classification problem, which allows reasoners to classify properties using our optimised procedure. We have implemented our algorithms in the OWL HermiT reasoner, and we present the results of a performance evaluation.
Birte Glimm, Ian Horrocks, and Boris Motik. Optimized Description Logic Reasoning via Core Blocking. In Jürgen Giesl and Reiner Hähnle, editors, Proc. of the 5th Int. Joint Conf. on Automated Reasoning (IJCAR 2010), volume 6173 of LNCS, pages 457–471, Edinburgh, UK, July 16–19 2010. Springer.
@InProceedings{ghm10core-blocking,
author = "Birte Glimm and Ian Horrocks and Boris Motik",
title = "{Optimized Description Logic Reasoning via Core Blocking}",
booktitle = "Proc. of the 5th Int. Joint Conf. on Automated Reasoning (IJCAR 2010)",
editor = "J{\"u}rgen Giesl and Reiner H{\"a}hnle",
month = "July 16--19",
year = "2010",
publisher = "Springer",
series = "LNCS",
volume = "6173",
pages = "457--471",
}

State of the art reasoners for expressive description logics, such as those that underpin the OWL ontology language, are typically based on highly optimized implementations of (hyper)tableau algorithms. Despite numerous optimizations, certain ontologies encountered in practice still pose significant challenges to such reasoners, mainly because of the size of the model abstractions that they construct. To address this problem, we propose a new blocking technique that tries to identify and halt redundant construction at a much earlier stage than standard blocking techniques. An evaluation of a prototypical implementation in the HermiT reasoner shows that our technique can dramatically reduce the size of constructed model abstractions and reduce reasoning time.
Bernardo Cuenca Grau and Boris Motik. Pushing the Limits of Reasoning over Ontologies with Hidden Content. In Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Proc. of the 12th Int. Conference on Principles of Knowledge Representation and Reasoning (KR 2010), pages 200–210, Toronto, ON, Canada, May 9–13 2010. AAAI Press.
@InProceedings{gm10pushing-ibq,
author = "Bernardo Cuenca Grau and Boris Motik",
title = "{Pushing the Limits of Reasoning over Ontologies with Hidden Content}",
booktitle = "Proc. of the 12th Int. Conference on Principles of Knowledge Representation and Reasoning (KR 2010)",
editor = "Fangzhen Lin and Ulrike Sattler and Miroslaw Truszczynski",
month = "May 9--13",
year = "2010",
publisher = "AAAI Press",
pages = "200--210",
}

There is currently a growing interest in techniques for hiding parts of the signature of an ontology $\hid{\KB}$ that is being reused by another ontology $\vis{\KB}$. Towards this goal, \citeA{ijcai09-paper} recently proposed the import-by-query framework, which makes the content of $\hid{\KB}$ accessible through a limited query interface. If $\vis{\KB}$ reuses the symbols from $\hid{\KB}$ in a certain restricted way, one can reason over ${\vis{\KB} \cup \hid{\KB}}$ by accessing only $\vis{\KB}$ and the query interface. In this paper, we map out the landscape of the import-by-query problem. We show that certain restrictions of our original framework are strictly necessary to make reasoning possible, we propose extensions that overcome some of the expressivity limitations, we present several novel reasoning algorithms, and we outline the limitations of the new framework.
Héctor Pérez-Urbina, Ian Horrocks, and Boris Motik. Efficient Query Answering for OWL 2. In Abraham Bernstein, David R. Karger, Tom Heath, Lee Feigenbaum, Diana Maynard, Enrico Motta, and Krishnaprasad Thirunarayan, editors, Proc. of the 8th Int. Semantic Web Conference (ISWC 2009), volume 5823 of LNCS, pages 489–504, Chantilly, VA, USA, October 25–29 2009. Springer.
@InProceedings{puhm09query-OWL2,
author = "H{\'e}ctor P{\'e}rez-Urbina and Ian Horrocks and Boris Motik",
title = "{Efficient Query Answering for OWL 2}",
booktitle = "Proc. of the 8th Int. Semantic Web Conference (ISWC 2009)",
editor = "Abraham Bernstein and David R. Karger and Tom Heath and Lee Feigenbaum and Diana Maynard and Enrico Motta and Krishnaprasad Thirunarayan",
month = "October 25--29",
year = "2009",
publisher = "Springer",
series = "LNCS",
volume = "5823",
pages = "489--504",
}

The QL profile of OWL 2 has been designed so that it is possible to use database technology for query answering via query rewriting. % : a % query is first transformed into a union of conjunctive queries % (i.e., an SQL query) using the conceptual part of the ontology and % then the evaluation of the rewritten query is delegated to the % database where the instance data resides. % In our previous work we % presented a rewriting algorithm that can deal with various % description logics of the \DLlite and \EL families—the bases for % the QL and EL profiles of OWL 2. Our algorithm exhibits % "pay-as-you-go'' behavior: in the case of \DLliteR, it produces a % union of conjunctive queries. We present a comparison of our resolution based rewriting algorithm % algorithm scaled down to \DLliteR with the standard %rewriting algorithm proposed by Calvanese et al., implementing both and conducting % We implemented both algorithms and conducted an empirical evaluation using ontologies and queries derived from realistic applications. The results indicate that our algorithm produces significantly smaller rewritings in most cases, which could be important for practicality in realistic applications.
Bernardo Cuenca Grau, Boris Motik, and Yevgeny Kazakov. Import-by-Query: Ontology Reasoning under Access Limitations. In Craig Boutilier, editor, Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI 2009), pages 727–733, Pasadena, CA, USA, July 11–17 2009.
@InProceedings{cgmk09ibq,
author = "Bernardo Cuenca Grau and Boris Motik and Yevgeny Kazakov",
title = "{Import-by-Query: Ontology Reasoning under Access Limitations}",
booktitle = "Proc. of the 21st Int. Joint Conf. on Artificial Intelligence (IJCAI 2009)",
editor = "Craig Boutilier",
month = "July 11--17",
year = "2009",
pages = "727--733",
}

To enable ontology reuse, the Web Ontology Language (OWL) allows an ontology $\vis{\KB}$ to import an ontology $\hid{\KB}$. To reason with such a $\vis{\KB}$, a reasoner needs physical access to the axioms of $\hid{\KB}$. For copyright and/or privacy reasons, however, the authors of $\hid{\KB}$ might not want to publish the axioms of $\hid{\KB}$; instead, they might prefer to provide an oracle that can answer a (limited) set of queries over $\hid{\KB}$, thus allowing $\vis{\KB}$ to import $\hid{\KB}$ "by query.'' In this paper, we study import-by-query algorithms, which can answer questions about ${\vis{\KB} \cup \hid{\KB}}$ by accessing only $\vis{\KB}$ and the oracle. We show that no such algorithm exists in general, and present restrictions under which importing by query becomes feasible.
Boris Motik and Ian Horrocks. OWL Datatypes: Design and Implementation. In Amit P. Sheth, Steffen Staab, Mike Dean, Massimo Paolucci, Diana Maynard, Timothy Finin, and Krishnaprasad Thirunarayan, editors, Proc. of the 7th Int. Semantic Web Conference (ISWC 2008), volume 5318 of LNCS, pages 307–322, Karlsruhe, Germany, October 26–30 2008. Springer.
@InProceedings{mh08datatypes,
author = "Boris Motik and Ian Horrocks",
title = "{OWL Datatypes: Design and Implementation}",
booktitle = "Proc. of the 7th Int. Semantic Web Conference (ISWC 2008)",
editor = "Amit P. Sheth and Steffen Staab and Mike Dean and Massimo Paolucci and Diana Maynard and Timothy Finin and Krishnaprasad Thirunarayan",
month = "October 26--30",
year = "2008",
publisher = "Springer",
series = "LNCS",
volume = "5318",
pages = "307--322",
}

We analyze the datatype system of OWL and OWL 2, and discuss certain nontrivial consequences of its definition, such as the extensibility of the set of supported datatypes and complexity of reasoning. We also argue that certain datatypes from the list of normative datatypes in the current OWL 2 Working Draft are inappropriate and should be replaced with different ones. Finally, we present an algorithm for datatype reasoning. Our algorithm is modular in the sense that it can handle any datatype that supports certain basic operations. We show how to implement these operations for number and string datatypes.
Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, and Ulirke Sattler. Representing Structured Objects using Description Graphs. In Gerhard Brewka and Jérôme Lang, editors, Proc. of the 11th Int. Joint Conf. on Principles of Knowledge Representation and Reasoning (KR 2008), pages 296–306, Sydney, NSW, Australia, August 16–19 2008. AAAI Press.
@InProceedings{mghs08description-graphs,
author = "Boris Motik and Bernardo Cuenca Grau and Ian Horrocks and Ulirke Sattler",
title = "{Representing Structured Objects using Description Graphs}",
booktitle = "Proc. of the 11th Int. Joint Conf. on Principles of Knowledge Representation and Reasoning (KR 2008)",
editor = "Gerhard Brewka and J{\'e}r{\^o}me Lang",
month = "August 16--19",
year = "2008",
publisher = "AAAI Press",
pages = "296--306",
}

State-of-the-art ontology languages are often not sufficiently expressive to accurately represent domains consisting of objects connected in a complex way. As a possible remedy, in our previous work we have proposed an extension of ontology languages with description graphs. In this paper, we extend this formalism by allowing for multiple graphs that can be combined in complex ways, thus obtaining a powerful language for modeling structured objects. By imposing a particular acyclicity restriction on the relationships between the graphs, we ensure that checking satisfiability of knowledge bases expressed in our language is decidable. We also present a practical reasoning algorithm.
Boris Motik and Ian Horrocks. Individual Reuse in Description Logic Reasoning. In Alessandro Armando, Peter Baumgartner, and Gilles Dowek, editors, Proc. of the 4th Int. Joint Conf. on Automated Reasoning (IJCAR 2008), volume 5195 of LNAI, pages 242–258, Sydney, NSW, Australia, August 12–15 2008. Springer.
@InProceedings{mh08reuse,
author = "Boris Motik and Ian Horrocks",
title = "{Individual Reuse in Description Logic Reasoning}",
booktitle = "Proc. of the 4th Int. Joint Conf. on Automated Reasoning (IJCAR 2008)",
editor = "Alessandro Armando and Peter Baumgartner and Gilles Dowek",
month = "August 12--15",
year = "2008",
publisher = "Springer",
series = "LNAI",
volume = "5195",
pages = "242--258",
}

Tableau calculi are the state-of-the-art for reasoning in description logics (DL). Despite recent improvements, tableau-based reasoners still cannot process certain knowledge bases (KBs), mainly because they end up building very large models. To address this, we propose a tableau calculus with individual reuse: to satisfy an existential assertion, our calculus nondeterministically tries to reuse individuals from the model generated thus far. We present two expansion strategies: one is applicable to the DL \ELOH and gives us a worst-case optimal algorithm, and the other is applicable to the DL SHOIQ. Using this technique, our reasoner can process several KBs that no other reasoner can.
Thanh Tran Duc, Peter Haase, Boris Motik, Bernardo Cuenca Grau, and Ian Horrocks. Metalevel Information in Ontology-Based Applications. In Dieter Fox and Carla P. Gomes, editors, Proc. of the 23rd AAAI Conf. on Artificial Intelligence (AAAI 2008), pages 1237–1242, Chicago, IL, USA, July 13–17 2008. AAAI Press.
@InProceedings{dhmgh08-metalevel-information,
author = "Thanh Tran Duc and Peter Haase and Boris Motik and Bernardo Cuenca Grau and Ian Horrocks",
title = "{Metalevel Information in Ontology-Based Applications}",
booktitle = "Proc. of the 23rd AAAI Conf. on Artificial Intelligence (AAAI 2008)",
editor = "Dieter Fox and Carla P. Gomes",
month = "July 13--17",
year = "2008",
publisher = "AAAI Press",
pages = "1237--1242",
}

Applications of Semantic Web technologies often require the management of metalevel information—that is, information that provides additional detail about domain-level information, such as provenance or access rights policies. Existing OWL-based tools provide little or no support for the representation and management of metalevel information. To fill this gap, we propose a framework based on metaviews—ontologies that describe facts in the application domain. We have implemented our framework in the KAON2 reasoner, and have successfully applied it in a nontrivial scenario.
Boris Motik, Bernardo Cuenca Grau, and Ulrike Sattler. Structured Objects in OWL: Representation and Reasoning. In Jinpeng Huai, Robin Chen, Hsiao-Wuen Hon, Yunhao Liu, Wei-Ying Ma, Andrew Tomkins, and Xiaodong Zhang, editors, Proc. of the 17th Int. World Wide Web Conference (WWW 2008), pages 555–564, Beijing, China, April 21–25 2008. ACM Press.
@InProceedings{mgs08structured-objects,
author = "Boris Motik and Bernardo Cuenca Grau and Ulrike Sattler",
title = "{Structured Objects in OWL: Representation and Reasoning}",
booktitle = "Proc. of the 17th Int. World Wide Web Conference (WWW 2008)",
editor = "Jinpeng Huai and Robin Chen and Hsiao-Wuen Hon and Yunhao Liu and Wei-Ying Ma and Andrew Tomkins and Xiaodong Zhang",
month = "April 21--25",
year = "2008",
publisher = "ACM Press",
pages = "555--564",
}

Applications of semantic technologies often require the representation of and reasoning with structured objects—that is, objects composed of parts connected in complex ways. Although OWL is a general and powerful language, its class descriptions and axioms cannot be used to describe arbitrarily connected structures. An OWL representation of structured objects can thus be underconstrained, which reduces the inferences that can be drawn and causes performance problems in reasoning. To address these problems, we extend OWL with description graphs, which allow for the description of structured objects in a simple and precise way. To represent conditional aspects of the domain, we also allow for SWRL-like rules over description graphs. Based on an observation about the nature of structured objects, we ensure decidability of our formalism. We also present a hypertableau-based decision procedure, which we implemented in the HermiT reasoner. To evaluate its performance, we have extracted description graphs from the GALEN and FMA ontologies, classified them successfully, and even detected a modeling error in GALEN.
Christine Golbreich, Matthew Horridge, Ian Horrocks, Boris Motik, and Rob Shearer. OBO and OWL: Leveraging Semantic Web Technologies for the Life Sciences. In Karl Aberer, Key-Sun Choi, Natasha Fridman Noy, Dean Allemang, Kyung-Il Lee, Lyndon J. B. Nixon, Jennifer Golbeck, Peter Mika, Diana Maynard, Riichiro Mizoguchi, Guus Schreiber, and Philippe Cudré-Mauroux, editors, Proc. of the 6th Int. Semantic Web Conference (ISWC 2007), volume 4825 of LNCS, pages 169–182, Busan, Korea, November 11-15 2007. Springer.
@InProceedings{ghhms07obo-and-owl,
author = "Christine Golbreich and Matthew Horridge and Ian Horrocks and Boris Motik and Rob Shearer",
title = "{OBO and OWL: Leveraging Semantic Web Technologies for the Life Sciences}",
booktitle = "Proc. of the 6th Int. Semantic Web Conference (ISWC 2007)",
editor = "Karl Aberer and Key-Sun Choi and Natasha Fridman Noy and Dean Allemang and Kyung-Il Lee and Lyndon J. B. Nixon and Jennifer Golbeck and Peter Mika and Diana Maynard and Riichiro Mizoguchi and Guus Schreiber and Philippe Cudr{\'e}-Mauroux",
month = "November 11-15",
year = "2007",
publisher = "Springer",
series = "LNCS",
volume = "4825",
pages = "169--182",
}

OBO is an ontology language that has often been used for modeling ontologies in the life sciences. Its definition is relatively informal, so, in this paper, we provide a clear specification for OBO syntax and semantics via a mapping to OWL. This mapping also allows us to apply existing Semantic Web tools and techniques to OBO. We show that Semantic Web reasoners can be used to efficiently reason with OBO ontologies. Furthermore, we show that grounding the OBO language in formal semantics is useful for the ontology development process: using an OWL reasoner, we detected a likely modeling error in one OBO ontology.
Boris Motik, Rob Shearer, and Ian Horrocks. Optimized Reasoning in Description Logics using Hypertableaux. In Frank Pfenning, editor, Proc. of the 21st Conference on Automated Deduction (CADE-21), volume 4603 of LNAI, pages 67–83, Bremen, Germany, July 17–20 2007. Springer.
@InProceedings{msh07optimized,
author = "Boris Motik and Rob Shearer and Ian Horrocks",
title = "{Optimized Reasoning in Description Logics using Hypertableaux}",
booktitle = "Proc. of the 21st Conference on Automated Deduction (CADE-21)",
editor = "Frank Pfenning",
month = "July 17--20",
year = "2007",
publisher = "Springer",
series = "LNAI",
volume = "4603",
pages = "67--83",
}

We present a novel reasoning calculus for Description Logics (DLs)—knowledge representation formalisms with applications in areas such as the Semantic Web. In order to reduce the nondeterminism due to general inclusion axioms, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. To prevent the calculus from generating large models, we introduce "anywhere" pairwise blocking. Our preliminary implementation shows significant performance improvements on several well-known ontologies. To the best of our knowledge, our reasoner is currently the only one that can classify the original version of the GALEN terminology.
Boris Motik, Ian Horrocks, and Ulrike Sattler. Bridging the Gap Between OWL and Relational Databases. In Carey L. Williamson, Mary Ellen Zurko, Peter F. Patel-Schneider, and Prashant J. Shenoy, editors, Proc. of the 16th International World Wide Web Conference (WWW 2007), pages 807–816, Banff, AB, Canada, May 8–12 2007. ACM Press.
@InProceedings{mhs07bridging,
author = "Boris Motik and Ian Horrocks and Ulrike Sattler",
title = "{Bridging the Gap Between OWL and Relational Databases}",
booktitle = "Proc. of the 16th International World Wide Web Conference (WWW 2007)",
editor = "Carey L. Williamson and Mary Ellen Zurko and Peter F. Patel-Schneider and Prashant J. Shenoy",
month = "May 8--12",
year = "2007",
publisher = "ACM Press",
pages = "807--816",
}

Schema statements in OWL are interpreted quite differently from analogous statements in relational databases. If these statements are meant to be interpreted as integrity constraints (ICs), OWL's interpretation may seem confusing and/or inappropriate. Therefore, we propose an extension of OWL with ICs that captures the intuition behind ICs in relational databases. We discuss the algorithms for checking IC satisfaction for different types of knowledge bases, and show that, if the constraints are satisfied, we can disregard them while answering a broad range of positive queries.
Boris Motik and Riccardo Rosati. A Faithful Integration of Description Logics with Logic Programming. In Manuela M. Veloso, editor, Proc. of the 20th Int. Joint Conference on Artificial Intelligence (IJCAI 2007), pages 477–482, Hyderabad, India, January 6–12 2007. Morgan Kaufmann Publishers.
@InProceedings{mr07dl-and-lp,
author = "Boris Motik and Riccardo Rosati",
title = "{A Faithful Integration of Description Logics with Logic Programming}",
booktitle = "Proc. of the 20th Int. Joint Conference on Artificial Intelligence (IJCAI 2007)",
editor = "Manuela M. Veloso",
month = "January 6--12",
year = "2007",
publisher = "Morgan Kaufmann Publishers",
pages = "477--482",
}

Integrating description logics (DL) and logic programming (LP) would produce a very powerful and useful formalism. However, DLs and LP are based on quite different principles, so achieving a seamless integration is not trivial. In this paper, we introduce hybrid MKNF knowledge bases that faithfully integrate DLs with LP using the logic of Minimal Knowledge and Negation as Failure (MKNF) \cite{DBLP:conf/ijcai/Lifschitz91}. We also give reasoning algorithms and tight data complexity bounds for several interesting fragments of our logic.
Boris Motik, Ian Horrocks, Riccardo Rosati, and Ulrike Sattler. Can OWL and Logic Programming Live Together Happily Ever After? In Isabel F. Cruz, Stefan Decker, Dean Allemang, Chris Preist, Daniel Schwabe, Peter Mika, Michael Uschold, and Lora Aroyo, editors, Proc. of the 5th Int. Semantic Web Conference (ISWC 2006), volume 4273 of LNCS, pages 501–514, Athens, GA, USA, November 5–9 2006. Springer.
@InProceedings{mhs06happily,
author = "Boris Motik and Ian Horrocks and Riccardo Rosati and Ulrike Sattler",
title = "{Can OWL and Logic Programming Live Together Happily Ever After?}",
booktitle = "Proc. of the 5th Int. Semantic Web Conference (ISWC 2006)",
editor = "Isabel F. Cruz and Stefan Decker and Dean Allemang and Chris Preist and Daniel Schwabe and Peter Mika and Michael Uschold and Lora Aroyo",
month = "November 5--9",
year = "2006",
publisher = "Springer",
series = "LNCS",
volume = "4273",
pages = "501--514",
}

Logic programming (LP) is often seen as a way to overcome several shortcomings of the Web Ontology Language (OWL), such as the inability to model integrity constraints or perform closed-world querying. However, the open-world semantics of OWL seems to be fundamentally incompatible with the closed-world semantics of LP. This has sparked a heated debate in the Semantic Web community, resulting in proposals for alternative ontology languages based entirely on logic programming. To help resolving this debate, we investigate the practical use cases which seem to be addressed by logic programming. In fact, many of these requirements have already been addressed outside the Semantic Web. By drawing inspiration from these existing formalisms, we present a novel logic of hybrid MKNF knowledge bases, which seamlessly integrates OWL with LP. We are thus capable of addressing the identified use cases without a radical change in the architecture of the Semantic Web.
Boris Motik and Ulrike Sattler. A Comparison of Reasoning Techniques for Querying Large Description Logic ABoxes. In Miki Hermann and Andrei Voronkov, editors, Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2006), volume 4246 of LNCS, pages 227–241, Phnom Penh, Cambodia, November 13–17 2006. Springer.
@InProceedings{ms06kaon2,
author = "Boris Motik and Ulrike Sattler",
title = "{A Comparison of Reasoning Techniques for Querying Large Description Logic ABoxes}",
booktitle = "Proc. of the 13th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2006)",
editor = "Miki Hermann and Andrei Voronkov",
month = "November 13--17",
year = "2006",
publisher = "Springer",
series = "LNCS",
volume = "4246",
pages = "227--241",
}

Many modern applications of description logics (DLs) require answering queries over large data quantities, structured according to relatively simple ontologies. For such applications, we conjectured that reusing ideas of deductive databases might improve scalability of DL systems. Hence, in our previous work, we developed an algorithm for reducing a DL knowledge base to a disjunctive datalog program. To test our conjecture, we implemented our algorithm in a new DL reasoner KAON2, which we describe in this paper. Furthermore, we created a comprehensive test suite and used it to conduct a performance evaluation. Our results show that, on knowledge bases with large ABoxes but with simple TBoxes, our technique indeed shows good performance; in contrast, on knowledge bases with large and complex TBoxes, existing techniques still perform better. This allowed us to gain important insights into strengths and weaknesses of both approaches.
Yevgeny Kazakov and Boris Motik. A Resolution-Based Decision Procedure for SHOIQ. In Ulrich Furbach, John Harrison, and Natarajan Shankar, editors, Proc. of the 3rd Int. Joint Conference on Automated Reasoning (IJCAR 2006), volume 4130 of LNAI, pages 662–667, Seattle, WA, USA, August 17–20 2006. Springer.
@InProceedings{km06shoiq,
author = "Yevgeny Kazakov and Boris Motik",
title = "{A Resolution-Based Decision Procedure for SHOIQ}",
booktitle = "Proc. of the 3rd Int. Joint Conference on Automated Reasoning (IJCAR 2006)",
editor = "Ulrich Furbach and John Harrison and Natarajan Shankar",
month = "August 17--20",
year = "2006",
publisher = "Springer",
series = "LNAI",
volume = "4130",
pages = "662--667",
}

We present a resolution-based decision procedure for the description logic SHOIQ—the logic underlying the Semantic Web ontology language OWL-DL. Our procedure is goal-oriented, and it naturally extends a similar procedure for SHIQ, which has proven itself in practice. Applying existing techniques for deriving saturation-based decision procedures to SHOIQ is not straightforward due to nominals, number restrictions, and inverse roles—a combination known to cause termination problems. We overcome this difficulty by using the basic superposition calculus, extended with custom simplification rules.
Stephan Grimm, Boris Motik, and Chris Preist. Matching Semantic Service Descriptions with Local Closed-World Reasoning. In York Sure and John Domingue, editors, Proc. of the 3rd European Semantic Web Conference (ESWC 2006), volume 4011 of LNCS, pages 575–589, Budva, Montenegro, June 11–14 2006. Springer.
@InProceedings{gmp06matching,
author = "Stephan Grimm and Boris Motik and Chris Preist",
title = "{Matching Semantic Service Descriptions with Local Closed-World Reasoning}",
booktitle = "Proc. of the 3rd European Semantic Web Conference (ESWC 2006)",
editor = "York Sure and John Domingue",
month = "June 11--14",
year = "2006",
publisher = "Springer",
series = "LNCS",
volume = "4011",
pages = "575--589",
}

Semantic Web Services were developed with the goal of automating the integration of business processes on the Web. The main idea is to express the functionality of the services explicitly, using semantic annotations. Such annotations can, for example, be used for service discovery—the task of locating a service capable of fulfilling a business request. In this paper, we present a framework for annotating Web Services using description logics (DLs), a family of knowledge representation formalisms widely used in the Semantic Web. We show how to realise service discovery by matching semantic service descriptions, applying DL inferencing. Building on our previous work, we identify problems that occur in the matchmaking process due to the open-world assumption when handling incomplete service descriptions. We propose to use autoepistemic extensions to DLs (ADLs) to overcome these problems. ADLs allow for non-monotonic reasoning and for querying DL knowledge bases under local closed-world assumption. We investigate the use of epistemic operators of ADLs in service descriptions, and show how they affect DL inferences in the context of semantic matchmaking.
Boris Motik. On the Properties of Metamodeling in OWL. In Yolanda Gil, Enrico Motta, Richard V. Benjamins, and Mark Musen, editors, Proc. of the 4th Int. Semantic Web Conference (ISWC 2005), volume 3729 of LNCS, pages 548–562, Galway, Ireland, November 6–10 2005. Springer.
@InProceedings{m05metamodeling,
author = "Boris Motik",
title = "{On the Properties of Metamodeling in OWL}",
booktitle = "Proc. of the 4th Int. Semantic Web Conference (ISWC 2005)",
editor = "Yolanda Gil and Enrico Motta and Richard V. Benjamins and Mark Musen",
month = "November 6--10",
year = "2005",
publisher = "Springer",
series = "LNCS",
volume = "3729",
pages = "548--562",
}

A common practice in conceptual modeling is to separate the intensional from the extensional model. Although very intuitive, this approach is inadequate for many complex domains, where the borderline between the two models is not clear-cut. Therefore, OWL-Full, the most expressive of the Semantic Web ontology languages, allows combining the intensional and the extensional model by a feature we refer to as metamodeling. In this paper, we show that the semantics of metamodeling adopted in OWL-Full leads to undecidability of basic inference problems, due to free mixing of logical and metalogical symbols. Based on this result, we propose two alternative semantics for metamodeling: the contextual and the HiLog semantics. We show that SHOIQ — a description logic underlying OWL-DL — extended with metamodeling under either semantics is decidable. Finally, we show how the latter semantics can be used in practice to axiomatize the logical interaction between concepts and metaconcepts.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Data Complexity of Reasoning in Very Expressive Description Logics. In Leslie Pack Kaelbling and Alessandro Saffiotti, editors, Proc. of the 19th Int. Joint Conference on Artificial Intelligence (IJCAI 2005), pages 466–471, Edinburgh, UK, July 30–August 5 2005. Morgan Kaufmann Publishers.
@InProceedings{hms05data,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Data Complexity of Reasoning in Very Expressive Description Logics}",
booktitle = "Proc. of the 19th Int. Joint Conference on Artificial Intelligence (IJCAI 2005)",
editor = "Leslie Pack Kaelbling and Alessandro Saffiotti",
month = "July 30--August 5",
year = "2005",
publisher = "Morgan Kaufmann Publishers",
pages = "466--471",
}

Data complexity of reasoning in description logics (DLs) estimates the performance of reasoning algorithms measured in the size of the ABox only. We show that, even for the very expressive DL SHIQ, satisfiability checking is data complete for NP. For applications with large ABoxes, this can be a more accurate estimate than the usually considered combined complexity, which is ExpTime-complete. Furthermore, we identify an expressive fragment, Horn-SHIQ, which is data complete for P, thus being very appealing for practical usage.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. A Decomposition Rule for Decision Procedures by Resolution-based Calculi. In Franz Baader and Andrei Voronkov, editors, Proc. of the 11th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2004), volume 3452 of LNAI, pages 21–35, Montevideo, Uruguay, March 14–18 2005. Springer.
@InProceedings{hms04decomposition,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{A Decomposition Rule for Decision Procedures by Resolution-based Calculi}",
booktitle = "Proc. of the 11th Int. Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR 2004)",
editor = "Franz Baader and Andrei Voronkov",
month = "March 14--18",
year = "2005",
publisher = "Springer",
volume = "3452",
series = "LNAI",
pages = "21--35",
}

Resolution-based calculi are among the most widely used calculi for theorem proving in first-order logic. Numerous refinements of resolution are nowadays available, such as e.g. basic superposition, a calculus highly optimized for theorem proving with equality. However, even such an advanced calculus does not restrict inferences enough to obtain decision procedures for complex logics, such as SHIQ. In this paper, we present a new decomposition inference rule, which can be combined with any resolution-based calculus compatible with the standard notion of redundancy. We combine decomposition with basic superposition to obtain three new decision procedures: (i) for the description logic SHIQ, (ii) for the description logic ALCHIQb, and (iii) for answering conjunctive queries over SHIQ knowledge bases. The first two procedures are worst-case optimal and, based on the vast experience in building efficient theorem provers, we expect them to be suitable for practical usage.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Reducing SHIQ- Description Logic to Disjunctive Datalog Programs. In Didier Dubois, Christopher A. Welty, and Mary-Anne Williams, editors, Proc. of the 9th Int. Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pages 152–162, Whistler, Canada, June 2–5 2004. AAAI Press.
@InProceedings{hms04reducing,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Reducing $\mathcal{SHIQ}^-$ Description Logic to Disjunctive Datalog Programs}",
booktitle = "Proc. of the 9th Int. Conference on Principles of Knowledge Representation and Reasoning (KR 2004)",
editor = "Didier Dubois and Christopher A. Welty and Mary-Anne Williams",
month = "June 2--5",
year = "2004",
publisher = "AAAI Press",
pages = "152--162",
}

As applications of description logics proliferate, efficient reasoning with large ABoxes (sets of individuals with descriptions) becomes ever more important. Motivated by the prospects of reusing optimization techniques from deductive databases, in this paper, we present a novel approach to checking consistency of ABoxes, instance checking and query answering, w.r.t. ontologies formulated using a slight restriction of the description logic SHIQ. Our approach proceeds in three steps: (i) the ontology is translated into first-order clauses, (ii) TBox and RBox clauses are saturated using a resolution-based decision procedure, and (iii) the saturated set of clauses is translated into a disjunctive datalog program. Thus, query answering can be performed using the resulting program, while applying all existing optimization techniques, such as join-order optimizations or magic sets. Equally important, the resolution-based decision procedure we present is for unary coding of numbers worst-case optimal, i.e. it runs in ExpTime.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Reasoning in Description Logics with a Concrete Domain in the Framework of Resolution. In Ramon López de Mántaras and Lorenza Saitta, editors, Proc. of the 16th European Conference on Artificial Intelligence (ECAI 2004), pages 353–357, Valencia, Spain, August 22–27 2004. IOS Press.
@InProceedings{hms04concrete,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Reasoning in Description Logics with a Concrete Domain in the Framework of Resolution}",
booktitle = "Proc. of the 16th European Conference on Artificial Intelligence (ECAI 2004)",
editor = "Ramon L{\'o}pez de M{\'a}ntaras and Lorenza Saitta",
month = "August 22--27",
year = "2004",
publisher = "IOS Press",
pages = "353--357",
}

In description logics, concrete domains are used to model concrete properties such as weight, name, or age, having concrete values such as integers or strings, with built-in predicates, such as <= or =. Until now, reasoning with concrete domains has been studied predominantly in the context of tableaux and automata calculi. In this paper, we present a general approach for concrete domain reasoning in the resolution framework. We apply this approach to devise an optimal decision procedure for SHIQD, the extension of SHIQ with a restricted form of concrete domains, serving as the logical underpinning of the web ontology language OWL-DL.
Boris Motik, Ulrike Sattler, and Rudi Studer. Query Answering for OWL-DL with Rules. In Sheila A. McIlraith, Dimitris Plexousakis, and Frank van Harmelen, editors, Proc. of the 3rd Int. Semantic Web Conference (ISWC 2004), volume 3298 of LNCS, pages 549–563, Hiroshima, Japan, November 7–11 2004. Springer.
@InProceedings{mss04dl-safe,
author = "Boris Motik and Ulrike Sattler and Rudi Studer",
title = "{Query Answering for OWL-DL with Rules}",
booktitle = "Proc. of the 3rd Int. Semantic Web Conference (ISWC 2004)",
editor = "Sheila A. McIlraith and Dimitris Plexousakis and Frank van Harmelen",
month = "November 7--11",
year = "2004",
publisher = "Springer",
volume = "3298",
series = "LNCS",
pages = "549--563",
}

Both OWL-DL and function-free Horn rules\footnote{Throughout this paper, we use "rules" and "clauses" synonymously, following \cite{HoPa04a}.} are decidable logics with interesting, yet orthogonal expressive power: from the rules perspective, OWL-DL is restricted to tree-like rules, but provides both existentially and universally quantified variables and full, monotonic negation. From the description logic perspective, rules are restricted to universal quantification, but allow for the interaction of variables in arbitrary ways. Clearly, a combination of OWL-DL and rules is desirable for building Semantic Web ontologies, and several such combinations have already been discussed. However, such a combination might easily lead to the undecidability of interesting reasoning problems. Here, we present a decidable such combination which is, to the best of our knowledge, more general than similar decidable combinations proposed so far. Decidability is obtained by restricting rules to so-called DL-safe ones, requiring each variable in a rule to occur in a non-DL-atom in the rule body. We show that query answering in such a combined logic is decidable, and we discuss its expressive power by means of a non-trivial example. Finally, we present an algorithm for query answering in SHIQD extended with DL-safe rules based on the reduction to disjunctive datalog.
Gábor Nagypál and Boris Motik. A Fuzzy Model for Representing Uncertain, Subjective, and Vague Temporal Knowledge in Ontologies. In Robert Meersman, Zahir Tari, and Douglas C. Schmidt, editors, Proc. of the 2003 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2003), volume 2888 of LNCS, pages 906–923, Catania, Italy, November 3–7 2003. Springer.
@InProceedings{nm03fuzzy,
author = "G{\'a}bor Nagyp{\'a}l and Boris Motik",
title = "{A Fuzzy Model for Representing Uncertain, Subjective, and Vague Temporal Knowledge in Ontologies}",
booktitle = "Proc. of the 2003 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2003)",
editor = "Robert Meersman and Zahir Tari and Douglas C. Schmidt",
month = "November 3--7",
year = "2003",
publisher = "Springer",
series = "LNCS",
volume = "2888",
pages = "906--923",
}

Time modeling is a crucial feature in many application domains. However, temporal information often is not crisp, but is uncertain, subjective and vague. This is particularly true when representing historical information, as historical accounts are inherently imprecise. Similarly, we conjecture that in the Semantic Web representing uncertain temporal information will be a common requirement. Hence, existing approaches for temporal modeling based on crisp representation of time cannot be applied to these advanced modeling tasks. To overcome these difficulties, in this paper we present fuzzy interval-based temporal model capable of representing imprecise temporal knowledge. Our approach naturally subsumes existing crisp temporal models, i.e. crisp temporal relationships are intuitively represented in our system. Apart from presenting the fuzzy temporal model, we discuss how this model is integrated with the ontology model to allow annotating ontology definitions with time specifications.
Raphael Volz, Steffen Staab, and Boris Motik. Incremental Maintenance of Materialized Ontologies. In Robert Meersman, Zahir Tari, and Douglas C. Schmidt, editors, Proc. of the 2003 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2003), volume 2888 of LNCS, pages 707–724, Catania, Italy, November 3–7 2003. Springer.
@InProceedings{vsm03incremental,
author = "Raphael Volz and Steffen Staab and Boris Motik",
title = "{Incremental Maintenance of Materialized Ontologies}",
booktitle = "Proc. of the 2003 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2003)",
editor = "Robert Meersman and Zahir Tari and Douglas C. Schmidt",
month = "November 3--7",
year = "2003",
publisher = "Springer",
series = "LNCS",
volume = "2888",
pages = "707--724",
}

This paper discusses the incremental maintenance of materialized ontologies in a rule-enabled Semantic Web. Materialization allows to speed up query processing by explicating the implicit entailments which are sanctioned by the semantics of an ontology. The complexity of reasoning with the ontology is thereby shifted from query time to update time. We assume that materialization techniques will frequently be important to achieve a scalable Semantic Web, since read access to ontologies is predominant. Central to materialization are maintenance techniques that allow to incrementally update a materialization when changes occur. par We present a novel solution that allows to cope with changes in rules and facts. To achieve this we extend a known approach for the incremental maintenance of views in deductive databases. We show how our technique can be employed for a broad range of existing Web ontology languages, such as RDF/S and subsets of OWL and present a first evaluation.
Alexander Maedche, Boris Motik, Ljiljana Stojanovic, Rudi Studer, and Raphael Volz. An infrastructure for searching, reusing and evolving distributed ontologies. In Proc. of the 12th International World Wide Web Conference (WWW 2003), pages 439–448, Budapest, Hungary, May 20–24 2003. ACM Press.
@InProceedings{mmssv03infrastructure,
author = "Alexander Maedche and Boris Motik and Ljiljana Stojanovic and Rudi Studer and Raphael Volz",
title = "{An infrastructure for searching, reusing and evolving distributed ontologies}",
booktitle = "Proc. of the 12th International World Wide Web Conference (WWW 2003)",
month = "May 20--24",
year = "2003",
publisher = "ACM Press",
pages = "439--448",
}

The vision of the Semantic Web can only be realized through proliferation of well-known ontologies describing different domains. To enable interoperability in the Semantic Web, it will be necessary to break these ontologies down into smaller, well-focused units that may be reused. Currently, three problems arise in that scenario. Firstly, it is difficult to locate ontologies to be reused, thus leading to many ontologies modeling the same thing. Secondly, current tools do not provide means for reusing existing ontologies while building new ontologies. Finally, ontologies are rarely static, but are being adapted to changing requirements. Hence, an infrastructure for management of ontology changes, taking into account dependencies between ontologies is needed. In this paper we present such an infrastructure addressing the aforementioned problems.
Raphael Volz, Daniel Oberle, Steffen Staab, and Boris Motik. KAON SERVER — A Semantic Web Management System. In Alternate Track Proc. of the 12th International World Wide Web Conference (WWW 2003), Budapest, Hungary, May 20–24 2003. ACM Press.
@InProceedings{vosm03kaonserver,
author = "Raphael Volz and Daniel Oberle and Steffen Staab and Boris Motik",
title = "{KAON SERVER --- A Semantic Web Management System}",
booktitle = "Alternate Track Proc. of the 12th International World Wide Web Conference (WWW 2003)",
month = "May 20--24",
year = "2003",
publisher = "ACM Press",
}

The growing use of ontologies in applications creates the need for an infrastructure that allows developers to more easily combine different software modules like ontology stores, editors, or inference engines towards comprehensive ontology-based solutions. We call such an infrastructure Ontology Software Environment. The article discusses requirements and design issues of such an Ontology Software Environment. In particular, we present this discussion in light of the ontology and (meta)data standards that exist in the Semantic Web and present our corresponding implementation, the KAON SERVER.
Boris Motik, Alexander Maedche, and Raphael Volz. A Conceptual Modeling Approach for Semantics-Driven Enterprise Applications. In Robert Meersman and Zahir Tari, editors, Proc. of the 2002 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2002), volume 2519 of LNCS, pages 1082–1099, Irvine, CA, USA, 2002. Springer.
@InProceedings{mmv02conceptual,
author = "Boris Motik and Alexander Maedche and Raphael Volz",
title = "{A Conceptual Modeling Approach for Semantics-Driven Enterprise Applications}",
editor = "Robert Meersman and Zahir Tari",
booktitle = "Proc. of the 2002 Int. Conference on Ontologies, Databases and Applications of SEmantics (ODBASE 2002)",
year = "2002",
publisher = "Springer",
series = "LNCS",
volume = "2519",
pages = "1082--1099",
}

In recent years ontologies – shared conceptualizations of some domain – are increasingly seen as the key to further automation of information processing. Although many approaches for representing and applying ontologies have already been devised, they haven't found their way into enterprise applications. In this paper we argue that ontology-based systems lack critical technical features, such as scalability, reliability, concurrency and integration with existing data sources, as well as the support for modularization and meta-concept modeling from the conceptual modeling perspective. We present a conceptual modeling approach that balances some of the trade-offs to more easily integrate into existing enterprise information infrastructure. Our approach is implemented within KAON, the Karlsruhe Ontology and Semantic Web tool suite.
Erol Bozsak, Marc Ehrig, Siegfried Handschuh, Andreas Hotho, Alexander Maedche, Boris Motik, Daniel Oberle, Christoph Schmitz, Steffen Staab, Ljiljana Stojanovic, Nenad Stojanovic, Rudi Studer, Gerd Stumme, York Sure, Julien Tane, Raphael Volz, and Valentin Zacharias. KAON — Towards a Large Scale Semantic Web. In Kurt Bauknecht, A. Min Tjoa, and Gerald Quirchmayr, editors, Proc. of the 3rd Int. Conference on E-Commerce and Web Technologies (EC-Web 2002), volume 2455 of LNCS, pages 304–313, Aix-en-Provence, France, September 2–6 2002. Springer.
@InProceedings{behhmmossssssstvz02kaon2,
author = "Erol Bozsak and Marc Ehrig and Siegfried Handschuh and Andreas Hotho and Alexander Maedche and Boris Motik and Daniel Oberle and Christoph Schmitz and Steffen Staab and Ljiljana Stojanovic and Nenad Stojanovic and Rudi Studer and Gerd Stumme and York Sure and Julien Tane and Raphael Volz and Valentin Zacharias",
title = "{KAON --- Towards a Large Scale Semantic Web}",
editor = "Kurt Bauknecht and A. Min Tjoa and Gerald Quirchmayr",
booktitle = "Proc. of the 3rd Int. Conference on E-Commerce and Web Technologies (EC-Web 2002)",
month = "September 2--6",
year = "2002",
publisher = "Springer",
series = "LNCS",
volume = "2455",
pages = "304--313",
}

The Semantic Web will bring structure to the content of Web pages, being an extension of the currentWeb, in which information is given a well-defined meaning. Especially within e-commerce applications, SemanticWeb technologies in the form of ontologies and metadata are becoming increasingly prevalent and important. This paper introduce KAON - the Karlsruhe Ontology and Semantic Web Tool Suite. KAON is developed jointly within several EU-funded projects and specifically designed to provide the ontology and metadata infrastructure needed for building, using and accessing semantics-driven applications on the Web and on your desktop.
Alexander Maedche, Boris Motik, Nuno Silva, and Raphael Volz. MAFRA — A MApping FRAmework for Distributed Ontologies. In Asunción Gómez-Pérez and Richard V. Benjamins, editors, Proc. of the 13th Int. Conference on Knowledge Engineering and Knowledge Management (EKAW 2002), volume 2473 of LNAI, pages 235–250, Siguenza, Spain, October 1–4 2002. Springer.
@InProceedings{mmsv02mafra,
author = "Alexander Maedche and Boris Motik and Nuno Silva and Raphael Volz",
title = "{MAFRA --- A MApping FRAmework for Distributed Ontologies}",
booktitle = "Proc. of the 13th Int. Conference on Knowledge Engineering and Knowledge Management (EKAW 2002)",
editor = "Asunci{\'o}n G{\'o}mez-P{\'e}rez and Richard V. Benjamins",
month = "October 1--4",
year = "2002",
publisher = "Springer",
series = "LNAI",
volume = "2473",
pages = "235--250",
}

Ontologies as means for conceptualizing and structuring domain knowledge within a community of interest are seen as a key to realize the Semantic Web vision. However, the decentralized nature of the Web makes achieving this consensus across communities difficult, thus, hampering efficient knowledge sharing between them. In order to balance the autonomy of each community with the need for interoperability, mapping mechanisms between distributed ontologies in the Semantic Web are required. In this paper we present MAFRA, an interactive, incremental and dynamic framework for mapping distributed ontologies.
Ljiljana Stojanovic, Alexander Maedche, Boris Motik, and Nenad Stojanovic. User-Driven Ontology Evolution Management. In Asunción Gómez-Pérez and Richard V. Benjamins, editors, Proc. of the 13th Int. Conference on Knowledge Engineering and Knowledge Management (EKAW 2002), volume 2473 of LNAI, pages 285–300, Siguenza, Spain, October 1–4 2002. Springer.
@InProceedings{smms02userdriven,
author = "Ljiljana Stojanovic and Alexander Maedche and Boris Motik and Nenad Stojanovic",
title = "{User-Driven Ontology Evolution Management}",
booktitle = "Proc. of the 13th Int. Conference on Knowledge Engineering and Knowledge Management (EKAW 2002)",
editor = "Asunci{\'o}n G{\'o}mez-P{\'e}rez and Richard V. Benjamins",
month = "October 1--4",
year = "2002",
publisher = "Springer",
series = "LNAI",
volume = "2473",
pages = "285--300",
}

With rising importance of knowledge interchange, many industrial and academic applications have adopted ontologies as their conceptual backbone. However, industrial and academic environments are very dynamic, thus inducing changes to application requirements. To fulfil these changes, often the underlying ontology must be evolved as well. As ontologies grow in size, the complexity of change management increases, thus requiring a well-structured ontology evolution process. In this paper we identify a possible six-phase evolution process and focus on providing the user with capabilities to control and customize it. We introduce the concept of an evolution strategy encapsulating policy for evolution with respect to user's requirements.
Alexander Maedche, Boris Motik, Ljiljana Stojanovic, Rudi Studer, and Raphael Volz. Managing Multiple Ontologies and Ontology Evolution in Ontologging. In Mark A. Musen, Bernd Neumann, and Rudi Studer, editors, Proc. of the 17th Int. Federation for Information Processing Congress (IFIP 2002), volume 221 of IFIP Conference Proceedings, pages 51–63, Montréal, Québec, Canada, August 25–30 2002. Kluwer.
@InProceedings{mmssv02managing,
author = "Alexander Maedche and Boris Motik and Ljiljana Stojanovic and Rudi Studer and Raphael Volz",
title = "{Managing Multiple Ontologies and Ontology Evolution in Ontologging}",
editor = "Mark A. Musen and Bernd Neumann and Rudi Studer",
booktitle = "Proc. of the 17th Int. Federation for Information Processing Congress (IFIP 2002)",
month = "August 25--30",
year = "2002",
publisher = "Kluwer",
series = "IFIP Conference Proceedings",
volume = "221",
pages = "51--63",
}

Ontologging is an ontology-driven environment to enable next generation knowledge management applications building on Semantic Web technology. In this paper we first present the conceptual architecture underlying Ontologging. Second, we focus on two important challenges for ontology-based knowledge management, namely the supporting multiple ontologies and managing ontology evolution. We will provide a general approach for handling these two essential issues within the Ontologging architecture.
Boris Motik and Vlado Glavinić. Enabling Agent Architecture through an RDF Query and Inference Engine. In Proc. of the 10th Mediterranean Electrotechnical Conference (MELECON 2000), volume II, pages 762–765, Lemesos, Cyprus, May 29–31 2000.
@InProceedings{mg00enabling,
author = "Boris Motik and Vlado Glavini{\'c}",
title = "{Enabling Agent Architecture through an RDF Query and Inference Engine}",
booktitle = "Proc. of the 10th Mediterranean Electrotechnical Conference (MELECON 2000)",
month = "May 29--31",
year = "2000",
volume = "II",
pages = "762--765",
}

Vlado Glavinić and Boris Motik. Agent-Oriented Information Retrieval and Processing. In Damir Kalpić and Vesna Hljuz-Dobrić, editors, Proc. 20th Int. Conference on Information Technology Interfaces (ITI '98), pages 163–168, Pula, Croatia, June 16–19 1998.
@InProceedings{gm98agentoriented,
author = "Vlado Glavini{\'c} and Boris Motik",
title = "{Agent-Oriented Information Retrieval and Processing}",
booktitle = "Proc. 20th Int. Conference on Information Technology Interfaces (ITI '98)",
editor = "Damir Kalpi{\'c} and Vesna Hljuz-Dobri{\'c}",
month = "June 16--19",
year = "1998",
pages = "163--168",
}

Vlado Glavinić and Boris Motik. Object-Oriented Interface to MMS Services. In Proc. of the 9th Mediterranean Electrotechnical Conference (MELECON '98), volume II, pages 1375–1379, Tel-Aviv, Israel, May 18–20 1998.
@InProceedings{gm98objectoriented,
author = "Vlado Glavini{\'c} and Boris Motik",
title = "{Object-Oriented Interface to MMS Services}",
booktitle = "Proc. of the 9th Mediterranean Electrotechnical Conference (MELECON '98)",
month = "May 18--20",
year = "1998",
volume = "II",
pages = "1375--1379",
}

Vlado Glavinić and Boris Motik. On PC-Based MMS Implementations. In Proc. of the 20th Int. Convention Managing for Efficiency and Innovation (MIPRO '97), pages 193–196, Opatija, Croatia, May 19–23 1997.
@InProceedings{gm97pcbased,
author = "Vlado Glavini{\'c} and Boris Motik",
title = "{On PC-Based MMS Implementations}",
booktitle = "Proc. of the 20th Int. Convention Managing for Efficiency and Innovation (MIPRO '97)",
month = "May 19--23",
year = "1997",
pages = "193--196",
}

Vlado Glavinić and Boris Motik. G-LOTOS Visual Development Environment. In Proc. of the 8th Mediterranean Electrotechnical Conference (MELECON '96), volume I, pages 136–139, Bari, Italy, May 13–16 1996.
@InProceedings{gm96g-lotos,
author = "Vlado Glavini{\'c} and Boris Motik",
title = "{G-LOTOS Visual Development Environment}",
booktitle = "Proc. of the 8th Mediterranean Electrotechnical Conference (MELECON '96)",
month = "May 13--16",
year = "1996",
volume = "I",
pages = "136--139",
}

Boris Motik and Vlado Glavinić. On Semantic Representation of LOTOS Programs. In Damir Kalpić and Vesna Hljuz-Dobrić, editors, Proc. 17th Int. Conference on Information Technology Interfaces (ITI '95), pages 217–224, Pula, Croatia, June 13–16 1995.
@InProceedings{mg95semantic,
author = "Boris Motik and Vlado Glavini{\'c}",
title = "{On Semantic Representation of LOTOS Programs}",
booktitle = "Proc. 17th Int. Conference on Information Technology Interfaces (ITI '95)",
editor = "Damir Kalpi{\'c} and Vesna Hljuz-Dobri{\'c}",
month = "June 13--16",
year = "1995",
pages = "217--224",
}


## In Workshops

Andrew Bate, Boris Motik, Bernardo Cuenca Grau, Franti sek Siman c'ik, and Ian Horrocks. Extending Consequence-Based Reasoning to SHIQ. In Diego Calvanese and Boris Konev, editors, Proc. of the 28th Int. Workshop on Description Logics (DL 2015), volume 1350 of CEUR Workshop Proceedings, pages 34–46, Athens, Greece, June 7–10 2015.
@InProceedings{bmgsh15consequence-SHIQ,
author = "Andrew Bate and Boris Motik and Bernardo Cuenca Grau and Franti{s}ek Siman{c}'{i}k and Ian Horrocks",
title = "{Extending Consequence-Based Reasoning to $\mathcal{SHIQ}$}",
booktitle = "Proc. of the 28th Int. Workshop on Description Logics (DL 2015)",
editor = "Diego Calvanese and Boris Konev",
month = "June 7--10",
year = "2015",
series = "CEUR Workshop Proceedings",
volume = "1350",
pages = "34--46",
}

Consequence-based calculi are a family of reasoning techniques for description logics (DLs)—knowledge representation formalisms with numerous applications. Such calculi are very effective in practice because they combine hypertableau and resolution reasoning in a way that considerably reduces the number of inferences. Up to now, however, they were proposed for either Horn DLs (which do not support disjunctive reasoning), or for DLs without counting quantifiers. In this paper we present a novel consequence-based algorithm for SHIQ—a DL that supports both disjunctions and counting quantifiers. Combining the two features is nontrivial since counting quantifiers require reasoning over equality, which we handle using the framework of ordered paramodulation—a state of the art method for equational theorem proving. We thus obtain a calculus that can handle an expressive DL, while still enjoying the benefits of existing calculi.
Anthony Potter, Boris Motik, and Ian Horrocks. Querying Distributed RDF Graphs: The Effects of Partitioning. In Thorsten Liebig and Achille Fokoue, editors, Proc. of the 10th Int. Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS 2014), volume 1261 of CEUR Workshop Proceedings, pages 29–44, Riva del Garda, Trentino, Italy, October 20 2014.
@InProceedings{pmh14distributed-RDF-graphs,
author = "Anthony Potter and Boris Motik and Ian Horrocks",
title = "{Querying Distributed RDF Graphs: The Effects of Partitioning}",
booktitle = "Proc. of the 10th Int. Workshop on Scalable Semantic Web Knowledge Base Systems (SSWS 2014)",
editor = "Thorsten Liebig and Achille Fokoue",
address = "Riva del Garda, Trentino, Italy",
month = "October 20",
year = "2014",
series = "CEUR Workshop Proceedings",
volume = "1261",
pages = "29--44",
}

Web-scale RDF datasets are increasingly processed using distributed RDF data stores built on top of a cluster of shared-nothing servers. Such systems critically rely on their data partitioning scheme and query answering scheme, the goal of which is to facilitate correct and efficient query processing. Existing data partitioning schemes are commonly based on hashing or graph partitioning techniques. The latter techniques split a dataset in a way that minimises the number of connections between the resulting subsets, thus reducing the need for communication between servers; however, to facilitate efficient query answering, considerable duplication of data at the intersection between subsets is often needed. Building upon the known graph partitioning approaches, in this paper we present a novel data partitioning scheme that employs minimal duplication and keeps track of the connections between partition elements; moreover, we propose a query answering scheme that uses this additional information to correctly answer all queries. We show experimentally that, on certain well-known RDF benchmarks, our data partitioning scheme often allows more answers to be retrieved without distributed computation than the known schemes, and we show that our query answering scheme can efficiently answer many queries.
Boris Motik, Yavor Nenov, Robert Piro, Ian Horrocks, and Dan Olteanu. Parallel OWL 2 RL Materialisation in Centralised, Main-Memory RDF Systems. In Meghyn Bienvenu, Magdalena Ortiz, Riccardo Rosati, and Mantas Simkus, editors, Proc. of the 27th Int. Workshop on Description Logics (DL 2014), volume 1193 of CEUR Workshop Proceedings, pages 311–323, Vienna, Austria, July 17–20 2014.
@InProceedings{mnpho14parallel-materialisation-RDFox-DL,
author = "Boris Motik and Yavor Nenov and Robert Piro and Ian Horrocks and Dan Olteanu",
title = "{Parallel OWL 2 RL Materialisation in Centralised, Main-Memory RDF Systems}",
booktitle = "Proc. of the 27th Int. Workshop on Description Logics (DL 2014)",
editor = "Meghyn Bienvenu and Magdalena Ortiz and Riccardo Rosati and Mantas Simkus",
month = "July 17--20",
year = "2014",
series = "CEUR Workshop Proceedings",
volume = "1193",
pages = "311--323",
}

We present a novel approach to parallel materialisation (i.e., fixpoint computation) of OWL RL Knowledge Bases in centralised, main-memory, multi-core RDF systems. Our approach comprises a datalog reasoning algorithm that evenly distributes the workload to cores, and an RDF indexing data structure that supports efficient, mostly' lock-free parallel updates. Our empirical evaluation shows that our approach parallelises computation very well so, with 16 physical cores, materialisation can be up to 13.9 times faster than with just one core.
Giorgio Stefanoni, Boris Motik, and Ian Horrocks. Introducing Nominals to the Combined Query Answering Approaches for EL. In Thomas Eiter, Birte Glimm, Yevgeny Kazakov, and Markus Krötzsch, editors, Proc. of the 26th Int. Workshop on Description Logics (DL 2013), volume 1014 of CEUR Workshop Proceedings, Ulm, Germany, July 23–26 2013.
@InProceedings{smh13nominals-combined-DL,
author = "Giorgio Stefanoni and Boris Motik and Ian Horrocks",
title = "{Introducing Nominals to the Combined Query Answering Approaches for $\mathcal{EL}$}",
booktitle = "Proc. of the 26th Int. Workshop on Description Logics (DL 2013)",
editor = "Thomas Eiter and Birte Glimm and Yevgeny Kazakov and Markus Kr{\"o}tzsch",
month = "July 23--26",
year = "2013",
series = "CEUR Workshop Proceedings",
volume = "1014",
}

Ian Horrocks, Boris Motik, and Zhe Wang. The HermiT OWL Reasoner. In Ian Horrocks, Mikalai Yatskevich, and Ernesto Jimenez-Ruiz, editors, Proc. of the OWL Reasoner Evaluation Workshop (ORE 2012), volume 858 of CEUR Workshop Proceedings, Manchester, UK, July 1 2012.
@InProceedings{hmw12HermiT,
author = "Ian Horrocks and Boris Motik and Zhe Wang",
title = "{The HermiT OWL Reasoner}",
booktitle = "Proc. of the OWL Reasoner Evaluation Workshop (ORE 2012)",
editor = "Ian Horrocks and Mikalai Yatskevich and Ernesto Jimenez-Ruiz",
month = "July 1",
year = "2012",
series = "CEUR Workshop Proceedings",
volume = "858",
}

HermiT is the only reasoner we know of that fully supports the OWL 2 standard, and that correctly reasons about properties as well as classes. It is based on a novel "hypertableau'' calculus that addresses performance problems due to nondeterminism and model size—the primary sources of complexity in state-of-the-art OWL reasoners. HermiT also incorporates a number of novel optimizations, including an optimized ontology classification procedure. Our tests show that HermiT performs well compared to existing tableau reasoners and is often much faster when classifying complex ontologies.
Giorgio Stefanoni, Boris Motik, and Ian Horrocks. Small Datalog Query Rewritings for EL. In Yevgeny Kazakov, Domenico Lembo, and Frank Wolter, editors, Proc. of the 25th Int. Workshop on Description Logics (DL 2012), volume 846 of CEUR Workshop Proceedings, Rome, Italy, June 7–10 2012.
@InProceedings{smh12small-rewritings-EL,
author = "Giorgio Stefanoni and Boris Motik and Ian Horrocks",
title = "{Small Datalog Query Rewritings for EL}",
booktitle = "Proc. of the 25th Int. Workshop on Description Logics (DL 2012)",
editor = "Yevgeny Kazakov and Domenico Lembo and Frank Wolter",
month = "June 7--10",
year = "2012",
series = "CEUR Workshop Proceedings",
volume = "846",
}

Despoina Magka, Boris Motik, and Ian Horrocks. Modelling Structured Domains Using Description Graphs and Logic Programming. In Yevgeny Kazakov, Domenico Lembo, and Frank Wolter, editors, Proc. of the 25th Int. Workshop on Description Logics (DL 2012), volume 846 of CEUR Workshop Proceedings, Rome, Italy, June 7–10 2012.
@InProceedings{mmh12dgs-and-lp-dl-version,
author = "Despoina Magka and Boris Motik and Ian Horrocks",
title = "{Modelling Structured Domains Using Description Graphs and Logic Programming}",
booktitle = "Proc. of the 25th Int. Workshop on Description Logics (DL 2012)",
editor = "Yevgeny Kazakov and Domenico Lembo and Frank Wolter",
month = "June 7--10",
year = "2012",
series = "CEUR Workshop Proceedings",
volume = "846",
}

Despoina Magka, Boris Motik, and Ian Horrocks. Classifying Chemicals Using Description Graphs and Logic Programming. In Matthew Horridge and Pavel Klinov, editors, Proc. of the 9th Int. Workshop on OWL: Experiences and Directions (OWLED 2012), Heraclion, Crete, May 27–28 2012.
@InProceedings{mmh12dgs-and-lp-owled-version,
author = "Despoina Magka and Boris Motik and Ian Horrocks",
title = "{Classifying Chemicals Using Description Graphs and Logic Programming}",
booktitle = "Proc. of the 9th Int. Workshop on OWL: Experiences and Directions (OWLED 2012)",
editor = "Matthew Horridge and Pavel Klinov",
month = "May 27--28",
year = "2012",
}

Although OWL 2 is widely used to describe complex objects such as chemical molecules, it cannot represent structural' features of chemical entities (e.g., having a ring). A combination of rules and description graphs (DGs) has been proposed as a possible solution, but it still exhibits several drawbacks. In this paper we present a radically different approach that we call Description Graph Logic Programs. Syntactically, our approach combines DGs, rules, and OWL 2 RL axioms, but its semantics is defined via a translation into logic programs under stable model semantics. The result is an expressive OWL 2 RL-compatible formalism that is well suited for modelling objects with complex structure.
František Simančík, Boris Motik, and Markus Krötzsch. Fixed Parameter Tractable Reasoning in DLs via Decomposition. In Riccardo Rosati, Sebastian Rudolph, and Michael Zakharyaschev, editors, Proc. of the 24th Int. Workshop on Description Logics (DL 2011), volume 745 of CEUR Workshop Proceedings, Barcelona, Spain, July 13–16 2011.
@InProceedings{smk11dl-decomposition,
author = "Franti{\v{s}}ek Siman{\v{c}}{\'i}k and Boris Motik and Markus Kr{\"o}tzsch",
title = "{Fixed Parameter Tractable Reasoning in DLs via Decomposition}",
booktitle = "Proc. of the 24th Int. Workshop on Description Logics (DL 2011)",
editor = "Riccardo Rosati and Sebastian Rudolph and Michael Zakharyaschev",
month = "July 13--16",
year = "2011",
series = "CEUR Workshop Proceedings",
volume = "745",
}

Birte Glimm, Ian Horrocks, and Boris Motik. Optimized DL Reasoning via Core Blocking. In Volker Haarslev, David Toman, and Grant Weddell, editors, Proc. of the 23rd Int. Workshop on Description Logics (DL 2010), volume 573 of CEUR Workshop Proceedings, Waterloo, ON, Canada, May 4–7 2010.
@InProceedings{ghm10core-blocking-DL,
author = "Birte Glimm and Ian Horrocks and Boris Motik",
title = "{Optimized DL Reasoning via Core Blocking}",
booktitle = "Proc. of the 23rd Int. Workshop on Description Logics (DL 2010)",
editor = "Volker Haarslev and David Toman and Grant Weddell",
month = "May 4--7",
year = "2010",
series = "CEUR Workshop Proceedings",
volume = "573",
}

Héctor Pérez-Urbina, Ian Horrocks, and Boris Motik. Practical Aspects of Query Rewriting for OWL 2. In Rinke Hoekstra and Peter Patel-Schneider, editors, Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2009), Chantilly, VA, USA, October 23–24 2009.
@InProceedings{puhm09practical-aspects,
author = "H{\'e}ctor P{\'e}rez-Urbina and Ian Horrocks and Boris Motik",
title = "{Practical Aspects of Query Rewriting for OWL 2}",
booktitle = "Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2009)",
editor = "Rinke Hoekstra and Peter Patel-Schneider",
month = "October 23--24",
year = "2009",
}

Query answering for the QL profile of OWL 2 and a substantial fragment of the EL profile can be implemented via query rewriting: a query posed over an ontology is first rewritten using the conceptual part of the ontology and then the evaluation of the rewritten query is delegated to a (deductive) database where the instance data resides. In our previous work we presented a rewriting algorithm for OWL QL that can also deal with most of the QL profile. In order to test the likely practicality of our rewriting algorithm, we have implemented it in a query rewriting system that we call REQUIEM. A recent empirical evaluation of REQUIEM, in which we considered OWL 2 QL ontologies, indicates that it produces significantly smaller rewritings than existing approaches in most cases. However, our results suggest that typical queries over realistic ontologies can still lead to very large rewritings (e.g., containing many thousands of queries). In this paper, we describe query rewriting, briefly present the results of our evaluation, and discuss various optimization techniques aimed at reducing the size of the rewritings. Moreover, we present some preliminary results from an ongoing empirical evaluation of REQUIEM in which we consider OWL 2 EL ontologies.
Bernardo Cuenca Grau and Boris Motik. Importing Ontologies with Hidden Content. In Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors, Proc. of the 22nd Int. Workshop on Description Logics (DL 2009), volume 477 of CEUR Workshop Proceedings, Oxford, UK, July 27–30 2009.
@InProceedings{gm09ibq-EL,
author = "Bernardo Cuenca Grau and Boris Motik",
title = "{Importing Ontologies with Hidden Content}",
booktitle = "Proc. of the 22nd Int. Workshop on Description Logics (DL 2009)",
editor = "Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler",
month = "July 27--30",
year = "2009",
series = "CEUR Workshop Proceedings",
volume = "477",
}

Rob Shearer, Ian Horrocks, and Boris Motik. Exploiting Partial Information in Taxonomy Construction. In Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors, Proc. of the 22nd Int. Workshop on Description Logics (DL 2009), volume 477 of CEUR Workshop Proceedings, Oxford, UK, July 27–30 2009.
@InProceedings{shm09partial-information,
author = "Rob Shearer and Ian Horrocks and Boris Motik",
title = "{Exploiting Partial Information in Taxonomy Construction}",
booktitle = "Proc. of the 22nd Int. Workshop on Description Logics (DL 2009)",
editor = "Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler",
month = "July 27--30",
year = "2009",
series = "CEUR Workshop Proceedings",
volume = "477",
}

Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. A Comparison of Query Rewriting Techniques for DL-lite. In Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors, Proc. of the 22nd Int. Workshop on Description Logics (DL 2009), volume 477 of CEUR Workshop Proceedings, Oxford, UK, July 27–30 2009.
@InProceedings{pumh09comparison,
author = "H{\'e}ctor P{\'e}rez-Urbina and Boris Motik and Ian Horrocks",
title = "{A Comparison of Query Rewriting Techniques for DL-lite}",
booktitle = "Proc. of the 22nd Int. Workshop on Description Logics (DL 2009)",
editor = "Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler",
month = "July 27--30",
year = "2009",
series = "CEUR Workshop Proceedings",
volume = "477",
}

Boris Motik, Bernardo Cuenca Grau, Ian Horrocks, and Ulrike Sattler. Modeling Ontologies Using OWL, Description Graphs, and Rules. In Alan Ruttenberg, Ulrile Sattler, and Cathy Dolbear, editors, Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 EU), Karlsruhe, Germany, October 26–27 2008.
@InProceedings{mcghs2008graphs,
author = "Boris Motik and Bernardo Cuenca Grau and Ian Horrocks and Ulrike Sattler",
title = "{Modeling Ontologies Using OWL, Description Graphs, and Rules}",
booktitle = "Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 EU)",
editor = "Alan Ruttenberg and Ulrile Sattler and Cathy Dolbear",
month = "October 26--27",
year = "2008",
}

Rob Shearer, Boris Motik, and Ian Horrocks. HermiT: A Highly-Efficient OWL Reasoner. In Alan Ruttenberg, Ulrile Sattler, and Cathy Dolbear, editors, Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 EU), Karlsruhe, Germany, October 26–27 2008.
@InProceedings{smh08HermiT,
author = "Rob Shearer and Boris Motik and Ian Horrocks",
title = "{HermiT: A Highly-Efficient OWL Reasoner}",
booktitle = "Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 EU)",
editor = "Alan Ruttenberg and Ulrile Sattler and Cathy Dolbear",
month = "October 26--27",
year = "2008",
}

%!TEX root = paper.tex HermiT is a new OWL reasoner based on a novel "hypertableau'' calculus. The new calculus addresses performance problems due to nondeterminism and model size—the primary sources of complexity in state-of-the-art OWL reasoners. The latter is particularly important in practice, and it is achieved in HermiT with an improved blocking strategy and and an optimization that tries to reuse existing individuals rather than generating new ones. HermiT also incorporates a number of other novel optimizations, such as a more efficient approach to handling nominals, and various techniques for optimizing ontology classification. Our tests show that HermiT is usually much faster than other reasoners when classifying complex ontologies, and it is already able to classify a number of ontologies which no other reasoner has been able to handle.
Boris Motik, Rob Shearer, and Ian Horrocks. Optimizing the Nominal Introduction Rule in (Hyper)Tableau Calculi. In Franz Baader, Carsten Lutz, and Boris Motik, editors, Proc. of the 21st Int. Workshop on Description Logics (DL 2008), volume 353 of CEUR Workshop Proceedings, Dresden, Germany, May 13–16 2008.
@InProceedings{msh08rewriting,
author = "Boris Motik and Rob Shearer and Ian Horrocks",
title = "{Optimizing the Nominal Introduction Rule in (Hyper)Tableau Calculi}",
booktitle = "Proc. of the 21st Int. Workshop on Description Logics (DL 2008)",
editor = "Franz Baader and Carsten Lutz and Boris Motik",
month = "May 13--16",
year = "2008",
series = "CEUR Workshop Proceedings",
volume = "353",
}

%!TEX root = paper.tex Interactions between nominals, inverse roles, and number restrictions provide challenges to description logic reasoners, as they can make models of a knowledge base non-forest-like. The solution to this problem used by the standard tableau calculus can incur a high degree of nondeterminism and can lead to the generation of unnecessarily large models. We present a more efficient approach to handling this combination of constructs. We use this approach to extend our hypertableau calculus to SHOIQ. This approach, however, is equally applicable to traditional tableau calculi.
Boris Motik, Bernardo Cuenca Grau, and Ulrike Sattler. The Representation of Structured Objects in DLs using Description Graphs. In Franz Baader, Carsten Lutz, and Boris Motik, editors, Proc. of the 21st Int. Workshop on Description Logics (DL 2008), volume 353 of CEUR Workshop Proceedings, Dresden, Germany, May 13–16 2008.
@InProceedings{mgs08description-graphs,
author = "Boris Motik and Bernardo Cuenca Grau and Ulrike Sattler",
title = "{The Representation of Structured Objects in DLs using Description Graphs}",
booktitle = "Proc. of the 21st Int. Workshop on Description Logics (DL 2008)",
editor = "Franz Baader and Carsten Lutz and Boris Motik",
month = "May 13--16",
year = "2008",
series = "CEUR Workshop Proceedings",
volume = "353",
}

Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. Rewriting Conjunctive Queries under Description Logic Constraints. In Andrea Cali, Georg Gottlob, Laks V.S. Lakshmanan, and Davide Martinenghi, editors, Proc. of the Int. Workshop on Logic in Databases (LID 2008), Rome, Italy, May 19–20 2008.
@InProceedings{pumh08rewriting-ELHI,
author = "H{\'e}ctor P{\'e}rez-Urbina and Boris Motik and Ian Horrocks",
title = "{Rewriting Conjunctive Queries under Description Logic Constraints}",
booktitle = "Proc. of the Int. Workshop on Logic in Databases (LID 2008)",
editor = "Andrea Cal{i} and Georg Gottlob and Laks V.S. Lakshmanan and Davide Martinenghi",
month = "May 19--20",
year = "2008",
}

We consider the problems of conjunctive query answering and rewriting under Description Logic constraints. We present a query rewriting algorithm for $\ELHI$ knowledge bases, and use it to show that query answering in this setting is PTime-complete w.r.t. data complexity. We show that our algorithm is worst-case optimal for languages with data complexity of query answering ranging from \LogSpace to PTime-complete.
Héctor Pérez-Urbina, Boris Motik, and Ian Horrocks. Rewriting Conjunctive Queries over Description Logic Knowledge Bases. In Klaus-Dieter Schewe and Bernhard Thalheim, editors, Proc. of the Int. Workshop on Semantics in Data and Knowledge Bases (SDKB 2008), volume 4925 of LNCS, pages 199–214, Nantes, France, March 29 2008. Springer.
@InProceedings{pumh08rewriting-DLlite-plus,
author = "H{\'e}ctor P{\'e}rez-Urbina and Boris Motik and Ian Horrocks",
title = "{Rewriting Conjunctive Queries over Description Logic Knowledge Bases}",
booktitle = "Proc. of the Int. Workshop on Semantics in Data and Knowledge Bases (SDKB 2008)",
editor = "Klaus-Dieter Schewe and Bernhard Thalheim",
month = "March 29",
year = "2008",
publisher = "Springer",
series = "LNCS",
volume = "4925",
pages = "199--214",
}

We consider the problems of conjunctive query answering and rewriting for information integration systems in which a Description Logic ontology is used to provide a global view of the data. We present a resolution-based query rewriting algorithm for $\DLlitePlus$ ontologies, and use it to show that query answering in this setting is \NLogSpace-complete with respect to data complexity. We also show that our algorithm produces an optimal rewriting when the input ontology is expressed in the language $\DLlite$. Finally, we sketch an extended version of the algorithm that would, we are confident, be optimal for several DL languages with data complexity of query answering ranging from \LogSpace to PTime-complete.
Boris Motik, Rob Shearer, and Ian Horrocks. A Hypertableau Calculus for SHIQ. In Diego Calvanese, Enriso Franconi, Volker Haarslev, Domenico Lembo, Boris Motik, Sergio Tessaris, and Anny-Yasmin Turhan, editors, Proc. of the 20th Int. Workshop on Description Logics (DL 2007), pages 419–426, Brixen/Bressanone, Italy, June 8–10 2007. Bozen/Bolzano University Press.
@InProceedings{msh07hypertableau,
author = "Boris Motik and Rob Shearer and Ian Horrocks",
title = "{A Hypertableau Calculus for SHIQ}",
booktitle = "Proc. of the 20th Int. Workshop on Description Logics (DL 2007)",
editor = "Diego Calvanese and Enriso Franconi and Volker Haarslev and Domenico Lembo and Boris Motik and Sergio Tessaris and Anny-Yasmin Turhan",
month = "June 8--10",
year = "2007",
publisher = "Bozen/Bolzano University Press",
pages = "419--426",
}

We present a novel reasoning calculus for the Description Logic SHIQ. In order to reduce the nondeterminism due to general inclusion axioms, we base our calculus on hypertableau and hyperresolution calculi, which we extend with a blocking condition to ensure termination. To prevent the calculus from generating large models, we introduce "anywhere'' pairwise blocking. Our preliminary implementation shows significant performance improvements on several well-known ontologies. To the best of our knowledge, our reasoner is currently the only one that can classify the original version of the GALEN terminology.
Boris Motik, Ian Horrocks, and Ulrike Sattler. Adding Integrity Constraints to OWL. In Christine Golbreich, Aditya Kalyanpur, and Bijan Parsia, editors, OWL: Experiences and Directions 2007 (OWLED 2007), Innsbruck, Austria, June 6–7 2007.
@InProceedings{mhs07adding-constraints,
author = "Boris Motik and Ian Horrocks and Ulrike Sattler",
title = "{Adding Integrity Constraints to OWL}",
booktitle = "OWL: Experiences and Directions 2007 (OWLED 2007)",
editor = "Christine Golbreich and Aditya Kalyanpur and Bijan Parsia",
month = "June 6--7",
year = "2007",
}

Schema statements in OWL are interpreted quite differently from analogous statements in relational databases. If these statements are meant to be interpreted as integrity constraints (ICs), OWL's interpretation may seem confusing and/or inappropriate. Therefore, we propose an extension of OWL with ICs that captures the intuition behind ICs in relational databases. We show that, if the constraints are satisfied, we can disregard them while answering a broad range of positive queries.
Boris Motik and Ian Horrocks. Problems with OWL Syntax. In Bernardo Cuenca Grau, Pascal Hitzler, Connor Shankey, and Evan Wallace, editors, OWL: Experiences and Directions 2006 (OWLED 2006), Athens, GA, USA, November 10–11 2006.
@InProceedings{mh06problems-owl,
author = "Boris Motik and Ian Horrocks",
title = "{Problems with OWL Syntax}",
booktitle = "OWL: Experiences and Directions 2006 (OWLED 2006)",
editor = "Bernardo Cuenca Grau and Pascal Hitzler and Connor Shankey and Evan Wallace",
month = "November 10--11",
year = "2006",
}

In this paper we discuss three problems with OWL syntax that repeatedly surface in practice. The first problem is that OWL does not allow for explicit declarations—assertions that a certain class, property, or an individual exists in an ontology. This aspect of the OWL standard was often misinterpreted, which caused design errors in OWL APIs; moreover, the lack of declarations makes devising an intuitive structural consistency check for OWL ontologies difficult. The second problem is that OWL Abstract Syntax and OWL RDF syntax rely on the separation between object and data property names for disambiguation. We show that this prevents an unambiguous interpretation of certain syntactically well-formed OWL ontologies; furthermore, it makes implementing OWL parsers unnecessarily difficult. The third problem is that OWL Abstract Syntax cannot be translated into OWL RDF syntax without loss of information. We present possible solutions to these three problems, which, if adopted in OWL 1.1, would lead to a cleaner standard and would significantly simplify the implementation of OWL APIs.
Boris Motik. Description Logics and Disjunctive Datalog—More Than just a Fleeting Resemblance? In Holger Schlingloff, editor, Proc. of the 4th Workshop on Methods for Modalities (M4M-4), volume 194 of Informatik-Berichte der Humboldt-Universität zu Berlin, pages 246–265, Berlin, Germany, December 1–2 2005.
@InProceedings{m05dl-and-dd,
author = "Boris Motik",
title = "{Description Logics and Disjunctive Datalog---More Than just a Fleeting Resemblance?}",
booktitle = "Proc. of the 4th Workshop on Methods for Modalities (M4M-4)",
editor = "Holger Schlingloff",
month = "December 1--2",
year = "2005",
series = "Informatik-Berichte der Humboldt-Universit{\"a}t zu Berlin",
volume = "194",
pages = "246--265",
}

As applications of description logics (DLs) proliferate, efficient reasoning with large ABoxes (sets of individuals with descriptions) becomes ever more important. Motivated by the prospects of reusing optimization techniques of deductive databases, we developed a novel algorithm for reasoning in description logic, which reduces a DL knowledge base to a disjunctive datalog program without changing the set of relevant consequences. This allows to answer queries by applying optimization techniques, such as join-order optimizations or magic sets. The algorithm supports the very expressive logic SHIQD, so the reduction is quite technically involved. In this paper we present a simplified algorithm for the basic logic \ALC. Whereas this algorithm is much easier to understand, it is based on the same principles as the general one.
Stephan Grimm and Boris Motik. Closed World Reasoning in the Semantic Web through Epistemic Operators. In Bernardo Cuenca Grau, Ian Horrocks, Bijan Parsia, and Peter Patel-Schneider, editors, Proc. of the Workshop on OWL: Experiences and Directions (OWLED 2005), Galway, Ireland, November 11–12 2005.
@InProceedings{gm05closed,
author = "Stephan Grimm and Boris Motik",
title = "{Closed World Reasoning in the Semantic Web through Epistemic Operators}",
booktitle = "Proc. of the Workshop on OWL: Experiences and Directions (OWLED 2005)",
editor = "Bernardo Cuenca Grau and Ian Horrocks and Bijan Parsia and Peter Patel-Schneider",
month = "November 11--12",
year = "2005",
}

Peter Haase and Boris Motik. A Mapping System for the Integration of OWL-DL Ontologies. In Axel Hahn, Sven Abels, and Liane Haak, editors, Proc. of the 1st Int. ACM Workshop on Interoperability of Heterogeneous Information Systems (IHIS'05), pages 9–16, Bremen, Germany, November 4 2005. ACM Press.
@InProceedings{hm05mapping,
author = "Peter Haase and Boris Motik",
title = "{A Mapping System for the Integration of OWL-DL Ontologies}",
booktitle = "Proc. of the 1st Int. ACM Workshop on Interoperability of Heterogeneous Information Systems (IHIS'05)",
editor = "Axel Hahn and Sven Abels and Liane Haak",
month = "November 4",
publisher = "ACM Press",
year = "2005",
pages = "9--16",
}

To enable interoperability between applications in distributed information systems based on heterogeneous ontologies, it is necessary to formally define the notion of a mapping between ontologies. In this paper, we define a mapping system for OWL-DL ontologies, where mappings are expressed as correspondences between conjunctive queries over ontologies. As query answering within such a general mapping system is undecidable, we identify a decidable fragment of the mapping system, which corresponds to OWL-DL extended with DL-safe rules. We further show how the mapping system can be applied for the task of ontology integration and present a query answering algorithm.
Ullrich Hustadt and Boris Motik. Description Logics and Disjunctive Datalog—The Story so Far. In Ian Horrocks, Ulrike Sattler, and Frank Wolter, editors, Proc. of the 2005 Int. Workshop on Description Logics (DL 2005), volume 147 of CEUR Workshop Proceedings, Edinburgh, UK, July 26–28 2005.
@InProceedings{hm05dl-dd-so-far,
author = "Ullrich Hustadt and Boris Motik",
title = "{Description Logics and Disjunctive Datalog---The Story so Far}",
booktitle = "Proc. of the 2005 Int. Workshop on Description Logics (DL 2005)",
editor = "Ian Horrocks and Ulrike Sattler and Frank Wolter",
month = "July 26--28",
year = "2005",
series = "CEUR Workshop Proceedings",
volume = "147",
}

In this paper we present an overview of our recent work on the relationship between description logics and disjunctive datalog. In particular, we reduce satisfiability and instance checking in SHIQ to corresponding problems in disjunctive datalog. This allows us to apply practically successful deductive database optimization techniques, such as magic sets. Interestingly, the reduction also allows us to obtain novel theoretical results on description logics. In particular, we show that the data complexity of reasoning in SHIQ is in NP, and we define a fragment called Horn-SHIQ for which the data complexity is in P. Finally, the reduction provides a basis for query answering in an extension of SHIQ with so-called DL-safe rules.
Pascal Hitzler, Jürgen Angele, Boris Motik, and Rudi Studer. Bridging the Paradigm Gap with Rules for OWL. In Proc. of the W3C Workshop on Rule Languages for Interoperability, Washington, DC, USA, April 27–28 2005.
@InProceedings{hams05bridging,
author = "Pascal Hitzler and J{\"u}rgen Angele and Boris Motik and Rudi Studer",
title = "{Bridging the Paradigm Gap with Rules for OWL}",
booktitle = "Proc. of the W3C Workshop on Rule Languages for Interoperability",
month = "April 27--28",
year = "2005",
}

Stephan Grimm, Boris Motik, and Chris Preist. Variance in e-Business Service Discovery. In David Martin, Rubén Lara, and Takahira Yamaguchi, editors, Proc. of the ISWC 2004 Workshop on Semantic Web Services: Preparing to Meet the World of Business Applications, volume 119 of CEUR Workshop Proceedings, Hiroshima, Japan, November 8 2004.
@InProceedings{gmp04variance,
author = "Stephan Grimm and Boris Motik and Chris Preist",
title = "{Variance in e-Business Service Discovery}",
booktitle = "Proc. of the ISWC 2004 Workshop on Semantic Web Services: Preparing to Meet the World of Business Applications",
editor = "David Martin and Rub{\'e}n Lara and Takahira Yamaguchi",
month = "November 8",
year = "2004",
series = "CEUR Workshop Proceedings",
volume = "119",
}

Automating the process of B2B partner discovery and contract negotiation is expected to significantly optimise company processes. Numerous existing proposals for discovery follow the approach where service descriptions are expressed by concept expressions in description logics (DL), and description matching is performed by well-known DL inferences. However, these approaches do not always produce results one might intuitively expect, due to a gap between the formal semantics of service descriptions and human intuition. In this paper, we address this problem by analysing the connection between the modeler's intuition and formal logic used to operationalise discovery. Furthermore, we show how to correctly map the intuition into description logic constructs. Finally, we investigate different inferences used to realise service discovery.
Boris Motik, Alexander Maedche, and Raphael Volz. Optimizing Query Answering in Description Logics using Disjunctive Deductive Databases. In François Bry, Carsten Lutz, Ulrike Sattler, and Mareike Schoop, editors, Proc. of the 10th Int. Workshop on Knowledge Representation meets Databases (KRDB 2003), volume 79 of CEUR Workshop Proceedings, Hamburg, Germany, September 15–16 2003.
@InProceedings{mmv03optimizing,
author = "Boris Motik and Alexander Maedche and Raphael Volz",
title = "{Optimizing Query Answering in Description Logics using Disjunctive Deductive Databases}",
booktitle = "Proc. of the 10th Int. Workshop on Knowledge Representation meets Databases (KRDB 2003)",
editor = "Fran\c{c}ois Bry and Carsten Lutz and Ulrike Sattler and Mareike Schoop",
month = "September 15--16",
year = "2003",
series = "CEUR Workshop Proceedings",
volume = "79",
}

Motivated by the possibilities of applying deductive database technology for efficient query answering in description logics, we present a translation operator $\mu$ that transforms non-recursive ALC ontologies into a disjunctive deductive database. Contrary to our previous work, in this paper we focus on handling negation, disjunction and existential quantifiers, which cannot be handled by deductive databases in a straightforward manner. We present a performance evaluation of our approach, confirming the intuition that techniques for optimizing query answering in disjunctive deductive databases may improve query answering in description logics.
Raphael Volz, Steffen Staab, and Boris Motik. Incremental Maintenance of Dynamic Datalog Programs. In Raphael Volz, Stefan Decker, and Isabel F. Cruz, editors, Proc. of the 1st Int. Workshop on Practical and Scalable Semantic Systems (PSSS1), volume 89 of CEUR Workshop Proceedings, Sanibel Island, FL, USA, October 20 2003.
@InProceedings{vsm03incremental-ws,
author = "Raphael Volz and Steffen Staab and Boris Motik",
title = "{Incremental Maintenance of Dynamic Datalog Programs}",
editor = "Raphael Volz and Stefan Decker and Isabel F. Cruz",
booktitle = "Proc. of the 1st Int. Workshop on Practical and Scalable Semantic Systems (PSSS1)",
address = "Sanibel Island, FL, USA",
month = "October 20",
year = "2003",
series = "CEUR Workshop Proceedings",
volume = "89",
}

Alexander Maedche, Boris Motik, Nuno Silva, and Raphael Volz. MAFRA — An Ontology MApping FRAmework in the context of the Semantic Web. In Proc. of the ECAI 2002 Workshop on Knowledge Transformation for the Semantic Web (KTSW), Lyon, France, July 23 2002.
@InProceedings{mmsv02mafra-ws,
author = "Alexander Maedche and Boris Motik and Nuno Silva and Raphael Volz",
title = "{MAFRA --- An Ontology MApping FRAmework in the context of the Semantic Web}",
booktitle = "Proc. of the ECAI 2002 Workshop on Knowledge Transformation for the Semantic Web (KTSW)",
month = "July 23",
year = "2002",
}

Ontologies as means for conceptualizing and structuring domain knowledge within a community of interest are seen as a key to realize the Semantic Web vision. However, the decentralized nature of the Web makes achieving this consensus across communities difficult, thus, hampering efficient knowledge sharing between them. In order to balance the autonomy of each community with the need for interoperability, mapping mechanisms between distributed ontologies in the Semantic Web are required. In this paper we present MAFRA, an interactive, incremental and dynamic framework for mapping distributed ontologies in the Semantic Web.

## Book Contributions

Boris Motik. Resolution-Based Reasoning for Ontologies, 2nd edition. In Steffen Staab and Rudi Studer, editors, Handbook on Ontologies, International Handbooks on Information Systems, pages 529–550, 2009. Springer.
@InCollection{m09resolution-based-reasoning,
author = "Boris Motik",
title = "{Resolution-Based Reasoning for Ontologies, 2nd edition}",
booktitle = "Handbook on Ontologies",
editor = "Steffen Staab and Rudi Studer",
publisher = "Springer",
series = "International Handbooks on Information Systems",
year = "2009",
pages = "529--550",
}

We overview the algorithms for reasoning with description logic (DL) ontologies based on resolution. These algorithms often have worst-case optimal complexity, and, by relying on vast experience in building resolution theorem provers, they can be implemented efficiently. Furthermore, we present a resolution-based algorithm that reduces a DL knowledge base into a disjunctive datalog program, while preserving the set of entailed facts. This reduction enables the application of optimization techniques from deductive databases, such as magic sets, to reasoning in DLs. This approach has proven itself in practice on ontologies with relatively small and simple TBoxes, but large ABoxes.
Boris Motik, Alexander Maedche, and Raphael Volz. Ontology Representation and Querying for Realizing Semantics-Driven Applications. In Giorgos Samou and Stefanos Kollias, editors, Multimedia Content and the Semantic Web: Methods, Standards and Tools, pages 45–73, 2005. John Wiley & Sons.
@InCollection{mmv05ontology-representation,
author = "Boris Motik and Alexander Maedche and Raphael Volz",
title = "{Ontology Representation and Querying for Realizing Semantics-Driven Applications}",
booktitle = "Multimedia Content and the Semantic Web: Methods, Standards and Tools",
editor = "Giorgos Samou and Stefanos Kollias",
publisher = "John Wiley \& Sons",
year = "2005",
pages = "45--73",
}

In recent years ontologies – shared conceptualizations of some domain – are increasingly seen as the key to further advances in automation of information processing. Although many approaches for representing and querying ontologies have already been devised, they haven't found their way into enterprise applications yet. Many of them offer a high degree of expressivity, but require complicated reasoning and query answering procedures, and often lack features needed in practical applications, such as constraints and meta-concept modeling. This is compounded by the lack of critical technical features in ontology management tools, such as scalability, reliability, concurrency and the support for ontology modularization. We present an approach for ontology representation and querying that balances some of the trade-offs to more easily integrate into existing enterprise information infrastructure. In particular, we focus on efficient evaluation of queries using existing information management infrastructure, such as relational databases. Finally, we describe a prototype implementation within KAON, the Karlsruhe Ontology and Semantic Web tool suite.
Daniel Oberle, Raphael Volz, Steffen Staab, and Boris Motik. An Extensible Ontology Software Environment. In Steffen Staab and Rudi Studer, editors, Handbook on Ontologies, International Handbooks on Information Systems, pages 299–320, 2004. Springer.
@InCollection{ovsm04extensible,
author = "Daniel Oberle and Raphael Volz and Steffen Staab and Boris Motik",
title = "{An Extensible Ontology Software Environment}",
booktitle = "Handbook on Ontologies",
editor = "Steffen Staab and Rudi Studer",
publisher = "Springer",
series = "International Handbooks on Information Systems",
year = "2004",
pages = "299--320",
}

The growing use of ontologies in applications creates the need for an infrastructure that allows developers to more easily combine different software modules like ontology stores, editors, or inference engines towards comprehensive ontology-based solutions. We call such an infrastructure Ontology Software Environment. The article discusses requirements and design issues of such an Ontology Software Environment. In particular, we present this discussion in light of the ontology and (meta)data standards that exist in the Semantic Web and present our corresponding implementation, the KAON SERVER.

## Technical Reports

Boris Motik, Bernardo Cuenca Grau, and Ulrike Sattler. Structured Objects in OWL: Representation and Reasoning. Technical Report, University of Oxford, UK, 2007.
@TechReport{mgs07structured-objects-report,
author = "Boris Motik and Bernardo Cuenca Grau and Ulrike Sattler",
title = "{Structured Objects in OWL: Representation and Reasoning}",
institution = "University of Oxford",
year = "2007",
}

Applications of semantic technologies often require the representation of and reasoning with structured objects—that is, objects composed of parts connected in complex ways. Although OWL is a general and powerful language, its class descriptions and axioms cannot be used to describe arbitrarily connected structures. An OWL representation of structured objects can thus be underconstrained, which reduces the inferences that can be drawn and causes performance problems in reasoning. To address these problems, we extend OWL with description graphs, which allow for the description of structured objects in a simple and precise way. To represent conditional aspects of the domain, we also allow for SWRL-like rules over description graphs. Based on an observation about the nature of structured objects, we ensure decidability of our formalism. We also present a hypertableau-based decision procedure, which we implemented in the HermiT reasoner. To evaluate its performance, we have extracted description graphs from the GALEN and FMA ontologies, classified them successfully, and even detected a modeling error in GALEN.
Boris Motik, Ian Horrocks, and Ulrike Sattler. Integrating Description Logics and Relational Databases. Technical Report, University of Manchester, UK, 2006.
@TechReport{mhs06constraints-report,
author = "Boris Motik and Ian Horrocks and Ulrike Sattler",
title = "{Integrating Description Logics and Relational Databases}",
institution = "University of Manchester",
year = "2006",
}

In this paper, we compare description logics with relational databases with respect to their treatment of schema constraints, the languages used to express these constraints, and the approaches to query answering and constraint checking. Our analysis reveals a significant overlap between the two formalisms. Inspired by the integrity constraints of relational databases, we define a notion of integrity constraints for description logics. We analyze different possibilities for defining the semantics of the constraints. Finally, we present several algorithms for checking constraint satisfaction for description logics with varying degrees of expressivity.
Boris Motik and Riccardo Rosati. Closing Semantic Web Ontologies. Technical Report, University of Manchester, UK, 2006.
@TechReport{mr06closing-report,
author = "Boris Motik and Riccardo Rosati",
title = "{Closing Semantic Web Ontologies}",
institution = "University of Manchester",
year = "2006",
}

In this paper, we present a novel formalism of hybrid MKNF knowledge bases, which allows us to seamlessly integrate an arbitrary decidable description logic with logic programming rules. We thus obtain a powerful hybrid formalism that combines the best features of both description logics, such as the ability to model taxonomic knowledge, and logic programming, such as the ability to perform nonmonotonic reasoning. Extending DLs with unrestricted rules makes reasoning undecidable. To obtain decidability, we apply the well-known DL-safety restriction that makes the rules applicable only to explicitly named individuals, and thus trade some expressivity for decidability. We present several reasoning algorithms for different fragments of our logic, as well as the corresponding complexity results. Our results show that, in many cases, the data complexity of reasoning with hybrid MKNF knowledge bases is not higher than the data complexity of reasoning in the corresponding fragment of logic programming.
Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Reasoning for Description Logics around SHIQ in a Resolution Framework. Technical Report 3-8-04/04, FZI, Germany, 2004.
@TechReport{hms04reasoning-report,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Reasoning for Description Logics around SHIQ in a Resolution Framework}",
institution = "FZI",
number = "3-8-04/04",
year = "2004",
}

Ullrich Hustadt, Boris Motik, and Ulrike Sattler. Reducing SHIQ- Description Logics to Disjunctive Datalog Programs. Technical Report 1-8-11/03, FZI, Germany, 2004.
@TechReport{hms04reducing-report,
author = "Ullrich Hustadt and Boris Motik and Ulrike Sattler",
title = "{Reducing $\mathcal{SHIQ}^-$ Description Logics to Disjunctive Datalog Programs}",
institution = "FZI",
number = "1-8-11/03",
year = "2004",
}


## Proceedings

Bernardo Cuenca Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors. Proceedings of the 22nd International Workshop on Description Logics (DL 2009). Oxford, UK, July 27–30 2009. CEUR Workshop Proceedings. Vol. 477.
@Proceedings{dl09,
title = "{Proceedings of the 22nd International Workshop on Description Logics (DL 2009)}",
editor = "Bernardo Cuenca Grau and Ian Horrocks and Boris Motik and Ulrike Sattler",
month = "July 27--30",
year = "2009",
publisher = "CEUR Workshop Proceedings",
note = "Vol. 477",
}

Franz Baader, Carsten Lutz, and Boris Motik, editors. Proceedings of the 21st International Workshop on Description Logics (DL 2008). Dresden, Germany, May 13–16 2008. CEUR Workshop Proceedings. Vol. 353.
@Proceedings{dl08,
title = "{Proceedings of the 21st International Workshop on Description Logics (DL 2008)}",
editor = "Franz Baader and Carsten Lutz and Boris Motik",
month = "May 13--16",
year = "2008",
publisher = "CEUR Workshop Proceedings",
note = "Vol. 353",
}

Diego Calvanese, Enrico Franconi, Volker Haarslev, Domenico Lembo, Boris Motik, Sergio Tessaris, and Anni-Yasmin Turhan, editors. Proceedings of the 20th International Workshop on Description Logics (DL 2007). Brixen/Bressanone, Italy, June 8–10 2007. CEUR Workshop Proceedings. Vol. 250.
@Proceedings{dl07,
title = "{Proceedings of the 20th International Workshop on Description Logics (DL 2007)}",
editor = "Diego Calvanese and Enrico Franconi and Volker Haarslev and Domenico Lembo and Boris Motik and Sergio Tessaris and Anni-Yasmin Turhan",
month = "June 8--10",
year = "2007",
publisher = "CEUR Workshop Proceedings",
note = "Vol. 250",
}


## Books

Boris Motik and Julijan Šribar. C++ Demystified. Element, Zagreb, Croatia, 2nd edition, 2001. In Croatian.
@Book{demistificirani1,
author = "Boris Motik and Julijan {\v{S}}ribar",
title = "{C++ Demystified}",
edition = "2nd",
publisher = "Element",
year = "2001",
note = "In Croatian",
}

Boris Motik and Julijan Šribar. C++ Demystified. Element, Zagreb, Croatia, 1997. In Croatian.
@Book{demistificirani2,
author = "Boris Motik and Julijan {\v{S}}ribar",
title = "{C++ Demystified}",
publisher = "Element",
year = "1997",
note = "In Croatian",
}


## Theses

Boris Motik. Reasoning in Description Logics using Resolution and Deductive Databases. PhD Thesis, Univesität Karlsruhe (TH), Karlsruhe, Germany, January 2006.
@PhDThesis{motik06PhD,
author = "Boris Motik",
title = "{Reasoning in Description Logics using Resolution and Deductive Databases}",
school = "Univesit{\"a}t Karlsruhe (TH), Karlsruhe, Germany",
month = "January",
year = "2006",
}

Boris Motik. Improving Interaction with the Information Infrastructure Using Intelligent Agents. Master's Thesis, Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia, December 1999. In Croatian.
@MastersThesis{motik99masters,
author = "Boris Motik",
title = "{Improving Interaction with the Information Infrastructure Using Intelligent Agents}",
school = "Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia",
month = "December",
year = "1999",
note = "In Croatian",
}

Boris Motik. Integrated Development Environment for Specifying Distributed Systems. Diploma Thesis, Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia, February 1996. In Croatian.
@MastersThesis{motik96diploma,
author = "Boris Motik",
title = "{Integrated Development Environment for Specifying Distributed Systems}",
school = "Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia",
month = "February",
year = "1996",
type = "Diploma Thesis",
note = "In Croatian",
}