A SAT-based system for consistent query answering
From MaRDI portal
Publication:2181925
DOI10.1007/978-3-030-24258-9_8zbMATH Open1441.68029arXiv1905.02828OpenAlexW2944451311MaRDI QIDQ2181925FDOQ2181925
Akhil A. Dixit, Phokion G. Kolaitis
Publication date: 20 May 2020
Abstract: An inconsistent database is a database that violates one or more integrity constraints, such as functional dependencies. Consistent Query Answering is a rigorous and principled approach to the semantics of queries posed against inconsistent databases. The consistent answers to a query on an inconsistent database is the intersection of the answers to the query on every repair, i.e., on every consistent database that differs from the given inconsistent one in a minimal way. Computing the consistent answers of a fixed conjunctive query on a given inconsistent database can be a coNP-hard problem, even though every fixed conjunctive query is efficiently computable on a given consistent database. We designed, implemented, and evaluated CAvSAT, a SAT-based system for consistent query answering. CAvSAT leverages a set of natural reductions from the complement of consistent query answering to SAT and to Weighted MaxSAT. The system is capable of handling unions of conjunctive queries and arbitrary denial constraints, which include functional dependencies as a special case. We report results from experiments evaluating CAvSAT on both synthetic and real-world databases. These results provide evidence that a SAT-based approach can give rise to a comprehensive and scalable system for consistent query answering.
Full work available at URL: https://arxiv.org/abs/1905.02828
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Database theory (68P15) Computational aspects of satisfiability (68R07)
Cited In (1)
This page was built for publication: A SAT-based system for consistent query answering
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2181925)
