Query answering over inconsistent knowledge bases: A probabilistic approach

• Published in: Theoretical computer science 2022-10, Vol.935, p.144-173
• Main Authors: Calautti, Marco, Greco, Sergio, Molinaro, Cristian, Trubitsyna, Irina
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Consistent query answering; Inconsistent knowledge bases; Probabilistic databases
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2022.09.005

Consistent query answering (CQA) is a widely accepted paradigm for querying inconsistent knowledge bases (KBs). A consistent answer to a query is a tuple that is an answer to the query over every repair of the KB, which is in turn a consistent KB whose extensional knowledge “minimally” differs from the original one's. This coarse-grained classification of answers into consistent and non-consistent ones lacks any information about their degree of consistency, i.e., how likely it is that a tuple is an answer to the query, when considering all the repaired KBs. To overcome this limitation, we consider a fine-grained notion of repair for KBs with equality-generating dependencies (EGDs), based on attribute-level updates, and exploit this notion to propose a probabilistic CQA approach, which associates a confidence to each answer, thereby providing more informative query answers. We first show that computing the query answer confidence is #P-hard. Then, in the light of this intractability result, we study the existence of efficient randomized, approximation schemes. In particular, we show that absolute error approximation schemes always exist in the general case, while more refined relative error approximation schemes, i.e., fully polynomial-time, randomized approximation schemes (FPRAS) exist when assuming that the constraints of the knowledge base are primary keys. Finally, we extend our framework to knowledge bases with tuple-generating dependencies (TGDs) and generalize our approximability results to the new setting, and prove additional inapproximability results.