Query-driven repairing Ontology-mediated query answering (OMQA) is a recent approach to data access in which conceptual knowledge provided by an ontology is exploited when querying incomplete data (see [6] for a survey). As e ciency is a primary concern, signi cant research e orts have been devoted to identifying ontology languages with favorable computational properties. The DL-Lite family of description logics [8], which underlies the OWL 2 QL pro le [20], has garnered signi cant interest as it allows OMQA to be reducedto standard database query evaluation. Beyond e ciency, it is important for OMQA systems to be robust to inconsistencies stemming from errors in the data. Inspired by work on consistent query answering in databases [3], several inconsistency-tolerant semantics have been developed for OMQA, with the aim of providing meaningful answers in the presence of inconsistencies. Of particular relevance to the present paper are the brave semantics [7], which returns all query answers that have some cause (i.e. minimal consistent subset that supports the answer), and the more conservative IAR semantics [17] that requires that facts in the cause not belong to any con ict (i.e. minimal inconsistent subset). Both semantics have appealing computational properties: for most DL-Lite dialects, including DL-LiteR, conjunctive query answering is tractable in data complexity [18, 7]. While inconsistency-tolerant semantics are essential for returning useful results when consistency cannot be achieved, they by no means replace the need for tools for improving data quality. This extended abstract presents our work [5] that proposes a complementary approach that exploits user feedback about query results to identify and correct errors. We consider the following scenario: a user poses conjunctive queries against a possibly inconsistent DL-LiteR knowledge base (KB) and receives the sets of possible answers (i.e. those holding under brave semantics) and almost sure answers (those holding under IAR semantics). When examining the results, he detects some unwanted answers, which should not have been retrieved, and identi es wanted answers, which should be present. Ideally, the unwanted tuples should not be returned as possible answers, and all of the desired tuples should be found among the sure answers. A query-driven repairing problem (QRP) consists of a KB to repair and two sets of Boolean conjunctive queries that the KB should entail or not entail. A repair plan is a pair of sets of assertions to delete or add to the ABox. It addresses
all defects if the resulting KB is such that every wanted answer holds under IAR semantics and every unwanted answer does not hold under brave semantics.
There are several reasons to use queries to guide the repairing process. First,
we note that it is typically impossible (for lack of time or information) to clean
the entire dataset, and therefore reasonable to focus the e ort on the parts of
the data most relevant to users' needs. In the database arena, this
observation inspired work on integrating entity resolution into the querying process [
The problem of modifying DL KBs to ensure (non)entailments of assertions
and/or axioms has been investigated in many works, see e.g. [
If we want to avoid introducing new errors, a fully automated repairing process is impossible: we need the user to validate every assertion that is removed or added in order to remove (resp. add) only assertions that are false (resp. true). We formalize the user's knowledge by a set of models of the TBox and say that an assertion is true (resp. false) if it is true (resp. false) in every of these models, unknown otherwise. A repair plan is validatable if it removes (resp. add) only assertions that are known to be false (resp. true).
As validatable repair plans addressing all defects are not guaranteed to exist (for instance, if the user knows that some answer is wrong but cannot pinpoint which assertion is at fault), our aim will be to nd validatable repair plans that are optimal in the sense that they address as many of the defects as possible.
We compare repair plans based on the answers they satisfy, an unwanted answer being satis ed if it does not hold under brave semantics in the resulting KB, and a wanted answer being satis ed if it has a cause without any con ict and that does not contain any assertion known to be false (i.e. if it holds under IAR semantics `for a good reason'). We obtain ve preference relations, taking into account one or both criteria, combined according to the Pareto principle or the lexicographic method, and consider global or local optimality for each.
In order to gain a better understanding of the computational properties of the di erent ways of ranking repair plans, we study the complexity of deciding if a given repair plan is optimal w.r.t. the di erent criteria. Our complexity analysis reveals that the notions of global optimality based upon the preference relations that take into account both criteria have undesirable computational properties: even when provided with all relevant user knowledge, it is intractable to decide whether a given plan is optimal. Moreover, while plans globally optimal regarding unwanted (resp. wanted) answers can be interactively constructed in a monotonic fashion by removing further false assertions (resp. and adding further true assertions), building a globally optimal plan for a preference relation that involves both unwanted and wanted answers may require backtracking over answers already satis ed. For the preceding reasons, we target validatable repair plans that are both globally optimal for unwanted or wanted answers (depending which is preferred) and locally optimal for the Pareto preference. We give interactive algorithms for building such repair plans by cleaning the relevant part of the data, then inserting assertions to create causes for wanted answers that are not satis ed while preserving already satis ed answers.
For future work, when insertions are needed, it would be helpful to provide
users with suggestions of assertions to add. The framework of query abduction
[
A repair plan is deletion-only when it contains no insertion. In this simpler setting, the previously introduced notions of optimality collapse. It is possible to further assist the user by taking advantage of the fact that subsets of the ABox to remove to address all defects can be automatically identi ed, then interactively transformed into optimal repair plans. We call such subsets potential solutions.
We call an assertion relevant if it appears in a cause of some answer or in the con icts of a cause of some wanted answer. If an assertion appears in every potential solution, either it is false, or there is no validatable potential solution. We call such assertions necessarily false. If appears in no potential solution, it is necessary to keep it to retrieve some wanted answers under IAR semantics, so either it is not false, or it is not possible to satisfy all wanted answers. We call such assertions necessarily nonfalse. We believe that validating sets of necessarily (non)false assertions requires less e ort than hunting for false assertions among relevant ones. Thus we propose an algorithm for constructing an optimal deletion-only plan that exploits this idea and uses SAT encodings to compute the assertions to present to the user. Borrowing ideas from work on reducing user e ort in interactive revision, e.g. [19, 21], we use a notion of impact to determine the order of presentation of relevant assertions. We also study the complexity of the related decision problems.
We made preliminary experiments on core components of the algorithm.
We use the CQAPri benchmark [