Advancement: Consistent Query Answering via Satisfiability Solving

Speaker Name: 
Akhil Dixit
Speaker Title: 
PhD Candidate
Speaker Organization: 
Computer Science and Engineering
Start Time: 
Thursday, October 10, 2019 - 10:00am
Location: 
Engineering 2, Room 280

Abstract:

An inconsistent database is a database that violates one or more integrity constraints, such as functional dependencies. Managing inconsistent databases is an old, but recurring, problem that often arises in real-world applications. Consistent Query Answering (CQA) is a principled approach to give semantics to queries over inconsistent databases; this semantics is called the consistent answers of queries, and involves the notion of database repairs. Consistent answers can be computationally hard, even for simple classes of database queries and integrity constraints. As a result, despite several attempts, no comprehensive and scalable CQA system exists today. We present CAvSAT, an open-source system for consistent query answering. It leverages a set of natural reductions from CQA to variants of Boolean Satisfiability (SAT), and uses modern SAT-solving technology to compute the consistent answers. Our preliminary experimental results provide evidence that SAT-solving can be a promising approach towards building a comprehensive and scalable CQA system that has the potential to be adopted as a principled alternative to data cleaning.

Event Type: 
Adancement/Defense
Advisor: 
Professor Phokion G. Kolaitis