Measuring the inconsistency degree of a knowledge base can help us to deal with inconsistencies. Several inconsistency measures have been given under different multi-valued semantics, including 4-valued semantics, 3-valued semantics, LPm and Quasi Classical semantics. In this paper, we first carefully analyze the relationship between these inconsistency measures by showing that the inconsistency degrees under 4-valued semantics, 3-value semantics, LPm are the same, but different from the one based on Quasi Classical semantics. We then consider the computation of these inconsistency measures and show that computing inconsistency measurement under multi-valued semantics is usually intractable. To tackle this problem, we propose two novel algorithms that respectively encode the problems of computing inconsistency degrees under 4-valued semantics (3-valued semantics, LPm) and under Quasi Classical semantics into the partial Max-SAT problems. We implement these algorithms and do experiments on some benchmark data sets. The preliminary but encouraging experimental results show that our approach is efficient to handle large knowledge bases.

We provide two approaches for explaining inconsistency in multi-context systems, where decentralized and heterogeneous system parts interact via nonmonotonic bridge rules. Inconsistencies arise easily in such scenarios, and nonmonotonicity calls for specific methods of inconsistency analysis. Both our approaches characterize inconsistency in terms of involved bridge rules: either by pointing out rules which need to be altered for restoring consistency, or by finding combinations of rules which cause inconsistency. We show duality and modularity properties, give precise complexity characterizations, and provide algorithms for computation using HEX-programs. Our results form a basis for inconsistency management in heterogeneous knowledge integration systems.

In this paper, we introduce a new class of local consistencies, called df-consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition and a mapping f that provides a covering for each relation of the considered qualitative calculus. We study the connections existing between some properties of the introduced mappings and the relative inference strength of df-consistencies. The consistency obtained by the usual closure under weak composition corresponds to the weakest element of the class, whereas df-consistencies stronger than weak composition open new promising perspectives. Interestingly, the class of df-consistencies is shown to form a complete lattice where the partial order denotes the relative strength of every two consistencies. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any "well-behaved" consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.

Maximality is a desirable property of paraconsistent logics, motivated by the aspiration to tolerate inconsistencies, but at the same time retain from classical logic as much as possible. In this paper, we introduce the strongest possible notion of maximal paraconsistency, and investigate it in the context of logics that are based on deterministic or non-deterministic three-valued matrices. We first show that most of the logics that are based on properly non-deterministic three-valued matrices are not maximally paraconsistent. Then we show that in contrast, in the deterministic case all the natural three-valued paraconsistent logics are maximal. This includes well-known three-valued paraconsistent logics like P1, LP, J3, PAC and SRM3, as well as any extension of them obtained by enriching their languages with extra three-valued connectives.

We identify three classes of four-state paraconsistent logics according to their different approaches towards the disjunctive syllogism, and investigate three representatives of these approaches: Quasi-classical logic, which always accepts this principle, Belnap's logic, that rejects the disjunctive syllogism altogether, and a logic of inconsistency minimization that restricts its application to consistent fragments only. These logics are defined in a syntactic and a semantic style, which are linked by a simple transformation. It is shown that the three formalisms accommodate knowledge minimization, and that the most liberal formalism towards the disjunctive syllogism is also the strongest among the three, while the most cautious logic is the weakest one.

The DL-Lite family of Description Logics has been designed with the specific goal of allowing for answering complex queries (in particular, conjunctive queries) over ontologies with very large instance sets (ABoxes). So far, in DL-Lite systems, this goal has been actually achieved only for relatively simple (short) conjunctive queries. In this paper we present Presto, a new query answering technique for DL-Lite ontologies, and an experimental comparison of Presto with the main previous approaches to query answering in DL-Lite. In practice, our experiments show that, in real ontologies, current techniques are only able to answer conjunctive queries of less than 7-10 atoms (depending on the complexity of the TBox), while Presto is actually able to handle conjunctive queries of up to 30 atoms. Furthermore, in the cases that are already successfully handled by previous approaches, Presto is significantly more efficient.

We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used.

Horn fragments of Description Logics (DLs) have gained popularity because they provide a beneficial trade-off between expressive power and computational complexity and, more specifically, are usually tractable w.r.t. data complexity. Despite their potential, and partly due to the intricate interaction of nominals (O), inverses (I) and counting (Q), such fragments had not been studied so far for the DLs SHOIQ and SROIQ that underly OWL 1 and 2. In this paper, we present a polynomial and modular translation from Horn-SHOIQ knowledge bases into DATALOG, which shows that standard reasoning tasks are feasible in deterministic single exponential time. This improves over the previously known upper bounds, and contrasts the known NEXPTIME completeness of full SHOIQ. Thereby, Horn-SHOIQ stands out as the first EXPTIME complete DL that allows simultaneously for O, I, and Q. In addition, we show that standard reasoning in Horn-SROIQ is 2-EXPTIME complete. Despite their high expressiveness, both Horn-SHOIQ and Horn-SROIQ have polynomial data complexity. This makes them particularly attractive for reasoning in semantically enriched systems with large data sets. A promising first step in this direction could be achieved exploiting existing DATALOG engines, along the lines of our translation.

Databases and related information systems can benefit from the use of ontologies to enrich the data with general background knowledge. The DL-Lite family of ontology languages was specifically tailored towards such ontology-based data access, enabling an implementation in a relational database management system (RDBMS) based on a query rewriting approach. In this paper, we propose an alternative approach to implementing ontology-based data access in DL-Lite. The distinguishing feature of our approach is to allow rewriting of both the query and the data. We show that, in contrast to the existing approaches, no exponential blowup is produced by the rewritings. Based on experiments with a number of real-world ontologies, we demonstrate that query execution in the proposed approach is often more efficient than in existing approaches, especially for large ontologies. We also show how to seamlessly integrate the data rewriting step of our approach into an RDBMS using views (which solves the update problem) and make an interesting observation regarding the succinctness of queries in the original query rewriting approach.

Recent years have seen the advent of large and complex ontologies, most notably in the medical domain. As a consequence, structuring mechanisms for ontologies are nowadays viewed as an indispensible tool. A basic such mechanism is the automatic decomposition of the vocabulary of an ontology into independent parts. In this paper, we study decompositions that are syntax independent in the sense that the resulting partitioning depends only on the meaning of the vocabulary items, but not on the concrete syntactic form of the axioms in the ontology. We present the first systematic investigation of decompositions of this type in the context of ontologies. Specifically, we focus on ontologies formulated in description logics and provide a variety of results that range from theorems stating the existence of unique finest decompositions to complexity results and algorithms computing decompositions. We also investigate the relationship between the existence of unique finite decompositions and a variant of the Craig interpolation property called parallel interpolation.