NotesFAQContact Us
Collection
Advanced
Search Tips
ERIC Number: ED568335
Record Type: Non-Journal
Publication Date: 2014
Pages: 204
Abstractor: As Provided
Reference Count: N/A
ISBN: 978-1-3038-4242-9
ISSN: N/A
Consistent Query Answering of Conjunctive Queries under Primary Key Constraints
Pema, Enela
ProQuest LLC, Ph.D. Dissertation, University of California, Santa Cruz
An inconsistent database is a database that violates one or more of its integrity constraints. In reality, violations of integrity constraints arise frequently under several different circumstances. Inconsistent databases have long posed the challenge to develop suitable tools for meaningful query answering. A principled approach for querying inconsistent databases is the consistent query answering framework. The approach suggests that the inconsistent database is left as-is, and inconsistencies are handled at query time by considering all possible repairs of the inconsistent database. In this dissertation, we study consistent query answering for conjunctive queries and primary key constraints. For this class, the problem can be coNP-complete in data complexity. We study heuristics for efficiently computing the consistent answers. Our heuristics model the consistent query answering problem with Binary Integer Programming (BIP). We develop EQUIP, a system for computing the consistent answers, which relies on fast BIP solvers to compute the consistent answers. We carry out an extensive experimental investigation that validates the effectiveness of our approach, and shows that EQUIP scales well to large databases. In addition, we study data complexity of consistent query answering, aiming to delineate the boundary between tractability and intractability. We establish a dichotomy on the data complexity of consistent answers for queries with two atoms, by giving a syntactic condition based on which, one can precisely determine the complexity as being either in P, or coNP-complete. For acyclic and self-join free conjunctive queries, we prove sufficient conditions for tractability and intractability of consistent answers. Moreover, for this class, we conjecture that there exists a dichotomy, and give a criterion for determining the complexity of each instance of the class. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]
ProQuest LLC. 789 East Eisenhower Parkway, P.O. Box 1346, Ann Arbor, MI 48106. Tel: 800-521-0600; Web site: http://www.proquest.com/en-US/products/dissertations/individuals.shtml
Publication Type: Dissertations/Theses - Doctoral Dissertations
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A