Error-Tolerant Reasoning in the Description Logic ℰℒ Based on Optimal Repairs

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

Ontologies based on Description Logic (DL) represent general background knowledge in a terminology (TBox) and the actual data in an ABox. Both human-made and machine-learned data sets may contain errors, which are usually detected when the DL reasoner returns unintuitive or obviously incorrect answers to queries. To eliminate such errors, classical repair approaches offer as repairs maximal subsets of the ABox not having the unwanted answers w.r.t. the TBox. It is, however, not always clear which of these classical repairs to use as the new, corrected data set. Error-tolerant semantics instead takes all repairs into account: cautious reasoning returns the answers that follow from all classical repairs whereas brave reasoning returns the answers that follow from some classical repair. It is inspired by inconsistency-tolerant reasoning and has been investigated for the DL 𝓔𝓛, but in a setting where the TBox rather than the ABox is repaired. In a series of papers, we have developed a repair approach for ABoxes that improves on classical repairs in that it preserves a maximal set of consequences (i.e., answers to queries) rather than a maximal set of ABox assertions. The repairs obtained by this approach are called optimal repairs. In the present paper, we investigate error-tolerant reasoning in the DL 𝓔𝓛, but we repair the ABox and use optimal repairs rather than classical repairs as the underlying set of repairs. To be more precise, we consider a static 𝓔𝓛 TBox (which is assumed to be correct), represent the data by a quantified ABox (where some individuals may be anonymous), and use 𝓔𝓛 concepts as queries (instance queries). We show that brave entailment of instance queries can be decided in polynomial time. Cautious entailment can be decided by a coNP procedure, but is still in P if the TBox is empty.

Details

Original languageEnglish
Title of host publicationRules and Reasoning
PublisherSpringer, Berlin [u. a.]
Pages227–243
Number of pages17
ISBN (print)978-3-031-21540-7
Publication statusPublished - 26 Sept 2022
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science, Volume 13752
ISSN0302-9743

External IDs

Scopus 85145265431
ORCID /0000-0002-4049-221X/work/142247941
ORCID /0000-0002-9047-7624/work/142251261
ORCID /0000-0003-0219-0330/work/153109419

Keywords

Library keywords