An approximation algorithm for querying inconsistent knowledge bases

• Published in: Intelligent systems with applications 2023-02, Vol.17, p.200146, Article 200146
• Main Authors: Alfano, Gianvincenzo, Greco, Sergio, Molinaro, Cristian, Trubitsyna, Irina
• Format: Article
• Language: English
• Subjects: Inconsistent KB; Knowledge-base systems; Medical informatics
• ISSN: 2667-3053; 2667-3053
• DOI: 10.1016/j.iswa.2022.200146

•We discuss, in an educational and easy-to-read way, a technique for repairing inconsistent clinical knowledge bases by using a more fine-grained repair primitive which updates facts rather than deleting them.•We show the notion of a universal repair, which compactly represents the whole set of possible repairs and it is useful to address the problem of computing approximate answers in inconsistent clinical knowledge bases.•We formally present a sound polynomial-time approximation algorithm for computing consistent query answers making use of universal repairs.•We provide examples showing that our approximation schema yields strictly better results than wellknown approximation approaches. Several medical applications deal with inconsistent knowledge bases, namely information that possibly violates given constraints, as they may not be enforced or satisfied. For instance, inconsistency may arise in clinical data integration, where multiple autonomous sources are integrated together: even if the sources are separately consistent, the integrated database may be inconsistent. A challenging problem in inconsistent clinical knowledge base management is extracting reliable information. The goal is to return reliable answers to queries even in the presence of inconsistent background data. In this regard, the majority of the proposals are based on the consistent query answering approach, where query answers are those obtained from all repairs, that are maximal consistent subsets of the knowledge base’s facts. We present a sound and polynomial-time approximation algorithm for solving the coNP-complete problem of consistent query answering. Our approach returns more consistent answers compared to those returned by state-of-the-art approaches, as they might discard facts including useful information.