Taming primary key violations to query large inconsistent data via ASP. Issue 4 (3rd September 2015)

• Record Type: Journal Article
• Authors: MANNA, MARCO; RICCA, FRANCESCO; TERRACINA, GIORGIO
• Editors: Eiter, Thomas; Toni, Francesca
• Is Part Of: Theory and practice of logic programming. Volume 15:Issue 4/5(2015)
• Page Start: 696
• Page End: 710
• Publication Date: 2015-09-03
• Subjects: Inconsistent Databases, -- Consistent Query Answering, -- ASP; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068415000320
• Languages: English
• ISSNs: 1471-0684

Abstract

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.