Collaborating Authors

Automated Reasoning in Temporal DL-Lite Artificial Intelligence

This paper investigates the feasibility of automated reasoning over temporal DL-Lite (TDL-Lite) knowledge bases (KBs). We test the usage of off-the-shelf LTL reasoners to check satisfiability of TDL-Lite KBs. In particular, we test the robustness and the scalability of reasoners when dealing with TDL-Lite TBoxes paired with a temporal ABox. We conduct various experiments to analyse the performance of different reasoners by randomly generating TDL-Lite KBs and then measuring the running time and the size of the translations. Furthermore, in an effort to make the usage of TDL-Lite KBs a reality, we present a fully fledged tool with a graphical interface to design them. Our interface is based on conceptual modelling principles and it is integrated with our translation tool and a temporal reasoner.

Querying Inconsistent Description Logic Knowledge Bases under Preferred Repair Semantics

AAAI Conferences

Recently several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. Most of these semantics rely on the notion of a repair, defined as an inclusion-maximal subset of the facts (ABox) which is consistent with the ontology (TBox). In this paper, we study variants of two popular inconsistency-tolerant semantics obtained by replacing classical repairs by various types of preferred repair. We analyze the complexity of query answering under the resulting semantics, focusing on the lightweight logic DL-Lite_R. Unsurprisingly, query answering is intractable in all cases, but we nonetheless identify one notion of preferred repair, based upon priority levels, whose data complexity is "only" coNP-complete. This leads us to propose an approach combining incomplete tractable methods with calls to a SAT solver. An experimental evaluation of the approach shows good scalability on realistic cases.

How to Select One Preferred Assertional-Based Repair from Inconsistent and Prioritized DL-Lite Knowledge Bases?

AAAI Conferences

Managing inconsistency in DL-Lite knowledge bases where the assertional base is prioritized is a crucial problem in many applications. This is especially true when the assertions are provided by multiple sources having different reliability levels. This paper first reviews existing approaches for selecting preferred repairs. It then focuses on suitable strategies for handling inconsistency in DL-Lite knowledge bases. It proposes new approaches based on the selection of only one preferred repair. These strategies have as a starting point the so-called non-defeated repair and add one of the following principles: deductive closure, consistency, cardinality and priorities. Lastly, we provide a comparative analysis followed by an experimental evaluation of the studied approaches.

Explaining Inconsistency-Tolerant Query Answering over Description Logic Knowledge Bases

AAAI Conferences

The problem The need to equip reasoning systems with explanation services of querying such KBs using database-style queries (in is widely acknowledged by the DL community (see particular, conjunctive queries) has been a major focus of Section 6 for discussion and references), and such facilities recent DL research. Since scalability is a key concern, much are all the more essential when using inconsistency-tolerant of the work has focused on lightweight DLs for which query semantics, as recently argued in (Arioua et al. 2014). Indeed, answering can be performed in polynomial time w.r.t. the the brave, AR, and IAR semantics allow one to classify size of the ABox. The DL-Lite family of lightweight DLs query answers into three categories of increasing reliability, (Calvanese et al. 2007) is especially popular due to the fact and a user may naturally wonder why a given tuple was assigned that query answering can be reduced, via query rewriting, to to, or excluded from, one of these categories.

On the Complexity of Consistent Query Answering in the Presence of Simple Ontologies

AAAI Conferences

Consistent query answering is a standard approach for producing meaningful query answers when data is inconsistent. Recent work on consistent query answering in the presence of ontologies has shown this problem to be intractable in data complexity even for ontologies expressed in lightweight description logics. In order to better understand the source of this intractability, we investigate the complexity of consistent query answering for simple ontologies consisting only of class subsumption and class disjointness axioms. We show that for conjunctive queries with at most one quantified variable, the problem is first-order expressible; for queries with at most two quantified variables, the problem has polynomial data complexity but may not be first-order expressible; and for three quantified variables, the problem may become co-NP-hard in data complexity. For queries having at most two quantified variables, we further identify a necessary and sufficient condition for first-order expressibility. In order to be able to handle arbitrary conjunctive queries, we propose a novel inconsistency-tolerant semantics and show that under this semantics, first-order expressibility is always guaranteed. We conclude by extending our positive results to DL-Lite ontologies without inverse.