Database repairs with answer set programming

Abstract

Integrity constraints play an important part in database design. They are what allow databases to store accurate information, since they impose some properties that must always hold. However, none of the existing Database Management Systems allows the specification of new integrity constraints if the information stored is already violating these new integrity constraints. In this dissertation, we developed DRSys, an application that allows the user to specify integrity constraints that he wishes to enforce in the database. If the database becomes inconsistent with respect to such integrity constraints, DRSys returns to the user possible ways to restore consistency, by inserting or deleting tuples into/from the original database, creating a new consistent database, a database repair. Also, since we are dealing with databases, we want to change as little information as possible, so DRSys offers the user two distinct minimality criteria when repairing the database: minimality under set inclusion or minimality under cardinality of operations. We approached the database repairing problem by using the capacity of problem solving offered by Answer Set Programming (ASP), which benefits from the simple specification of problems, and the existence of “Solvers” that solve those problems in an efficient manner. DRSys is a database repair application that was built on top of the database management system PostgreSQL. Furthermore, we developed a graphical user interface, to aid the user in the whole process of defining new integrity constraints and in the process of database repairing. We evaluate the performance and scalability of DRSys, by presenting several tests in different situations, exploring particular features of it as well, in order to understand the scalability of DRSys.