Taming primary key violations to query large inconsistent data via ASP

DOI10.1017/S1471068415000320MaRDI QIDQ4593009zbMATH OpenDBLPWikidataFDO

Authors F. Ricca, G. Terracina, M. Manna

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.06103

zbMATH Keywords

inconsistent databasesconsistent query answeringASP

Mathematics Subject Classification ID

Logic programming (68N17) Database theory (68P15)

Abstract: Consistent query answering over a database that violates primary key constraints is a classical hard problem in database research that has been traditionally dealt with logic programming. However, the applicability of existing logic-based solutions is restricted to data sets of moderate size. This paper presents a novel decomposition and pruning strategy that reduces, in polynomial time, the problem of computing the consistent answer to a conjunctive query over a database subject to primary key constraints to a collection of smaller problems of the same sort that can be solved independently. The new strategy is naturally modeled and implemented using Answer Set Programming (ASP). An experiment run on benchmarks from the database world prove the effectiveness and efficiency of our ASP-based approach also on large data sets. To appear in Theory and Practice of Logic Programming (TPLP), Proceedings of ICLP 2015.

Recommendations

• Answer sets for consistent query answering in inconsistent databases
• scientific article; zbMATH DE number 1696773
• Consistent query answering via ASP from different perspectives: theory and practice
• Database Theory - ICDT 2005
• First-order query rewriting for inconsistent databases

Cites work

• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 1954112 (Why is no real title available?)
• scientific article; zbMATH DE number 2085288 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• A dichotomy in the complexity of consistent query answering for queries with two atoms
• Answer sets for consistent query answering in inconsistent databases
• Anytime computation of cautious consequences in answer set programming
• Consistent query answering via ASP from different perspectives: theory and practice
• First-order query rewriting for inconsistent databases
• Knowledge Representation, Reasoning and Declarative Problem Solving
• Logic Programming
• Minimal-change integrity maintenance using tuple deletions

Cited in

(9)

• Consistent query answering via ASP from different perspectives: theory and practice
• ASP and subset minimality: enumeration, cautious reasoning and MUSes
• Paracoherent answer set computation
• Consistent query answering for primary keys in Datalog
• Cautious reasoning in ASP via minimal models and unsatisfiable cores
• A logic-based framework leveraging neural networks for studying the evolution of neurological disorders
• Combining answer set programming and domain heuristics for solving hard industrial problems (application paper)
• Partial compilation of ASP programs
• The External Interface for Extending WASP

Describes a project that uses

Uses Software

• Gringo

This page was built for publication: Taming primary key violations to query large inconsistent data via ASP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593009)