In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for DLs, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for (conjunctive) query answering over DL-Lite ontologies, by adopting abductive reasoning, that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning taskswe consider existence and recognition of an explanation, and relevance and necessity of a certain assertion for an explanation. We characterize the computational complexity of these problems for subset minimal and cardinality minimal explanations.

We define generalized ontology-based production systems (GOPSs), which formalize a very general and powerful combination of ontologies and production systems. We show that GOPSs capture and generalize many existing formal notions of production systems. We introduce a powerful verification query language for GOPSs, which is able to express the most relevant formal properties of production systems previously considered in the literature. We establish a general sufficient condition for the decidability of answering verification queries over GOPSs. Then, we define Lite-GOPS, a particular class of GOPSs based on the use of a light-weight ontology language (DL-Llite_A), a light-weight ontology query language (EQL-Lite(UCQ)), and a tractable semantics for updates over Description Logic ontologies. We show decidability of all the above verification tasks over Lite-GOPSs, and prove tractability of some of such tasks.

In ontology-based data access (OBDA), ontologies are used as an interface for querying instance data. Since in typical applications the size of the data is much larger than the size of the ontology and query, data complexity is the most important complexity measure. In this paper, we propose a new method for investigating data complexity in OBDA: instead of classifying whole logics according to their complexity, we aim at classifying each individual ontology within a given master language. Our results include a P/coNP-dichotomy theorem for ontologies of depth one in the description logic ALCFI, the equivalence of a P/coNP-dichotomy theorem for ALC/ALCI-ontologies of unrestricted depth to the famous dichotomy conjecture for CSPs by Feder and Vardi, and a non-P/coNP-dichotomy theorem for ALCF-ontologies.

We study (i) uniform interpolation for TBoxes that are formulated in the description logic EL and (ii) approximations of TBoxes formulated in more expressive languages. In both cases, we give model-theoretic characterizations based on simulations and cartesian products, and we develop algorithms that decide whether interpolants and approximations exist. We present a uniform approach to both problems, based on a novel amorphous automaton model called EL automata (EA). Using EAs, we also establish a simpler proof of the known result that conservative extensions of EL-TBoxes can be decided in ExpTime.

The key idea is that RDBMSs in practice appears to indicate only that answering data, 'stored in a standard relational database management real-world queries over real-world databases turns out to be system (RDBMS), can be queried through an OWL 2 QL tractable. As rewritings can turn a standard query to something ontology via a simple rewriting mechanism, i.e., by rewriting'out of this world,' a first rule of thumb could be as follows: the query into an SQL query that is then answered by the rewritten query should look similar to the original the RDBMS, without any changes to the data' (

The EL family of description logics (DLs) has been designed to provide a restricted syntax for commonly used DL constructors with the goal to guarantee polynomial complexity of reasoning. Yet, polynomial complexity does not always mean that the underlying reasoning procedure is efficient inpractice. In this paper we consider a simple DL ELO from the EL family that admits nominals, and argue that existing polynomial reasoning procedures for ELO can be impractical for many realistic ontologies. To solve the problem, we describe an optimization strategy in which the inference rules required for reasoning with nominals are avoided as much as possible. The optimized procedure is evaluated within the reasoner ELK and demonstrated to perform well in practice.

We consider the setting of ontological database access, where an A-box is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a T-box Σ formulated in DL-Lite or Linear Datalog+/-. It is well-known that (Σ, q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog+/- or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of Σ and q . This gives rise to the interesting question whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate (Σ, q ) into a polynomially sized equivalent nonrecursive Datalog program P.

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 materialisationbased OWL 2 DL reasoners may be practically feasible.

While query answering in the presence of description logic (DL) ontologies is a well-studied problem, questions of static analysis such as query containment and query optimization have received less attention. In this paper, we study a rather general version of query containment that, unlike the classical version, cannot be reduced to query answering. First, we allow a restriction to be placed on the vocabulary used in the instance data, which can result in shorter equivalent queries; and second, we allow each query its own ontology rather than assuming a single ontology for both queries, which is crucial in applications to versioning and modularity. We also study global minimization of queries in the presence of DL ontologies, which is more subtle than for classical databases as minimal queries need not be isomorphic.

The dynamic nature of ontology development has motivated the formal study of ontology evolution problems. This paper presents a logical framework that enables fine-grained investigation of evolution problems at a deductive level. In our framework, the optimal evolutions of an ontology O are those ontologies O′ that maximally preserve both the structure of O and its entailments in a given preservation language. We show that our framework is compatible with the postulates of Belief Revision, and we investigate the existence of optimal evolutions in various settings. In particular, we present first results on TBox-level revision and contraction in the EL and FL0 families of Description Logics.