Consistent Query Answering of Conjunctive Queries under Primary Key Constraints

Autor/in	Pema, Enela
Titel	Consistent Query Answering of Conjunctive Queries under Primary Key Constraints
Quelle	(2014), (204 Seiten) PDF als Volltext Verfügbarkeit Ph.D. Dissertation, University of California, Santa Cruz
Sprache	englisch
Dokumenttyp	gedruckt; online; Monographie
ISBN	978-1-3038-4242-9
Schlagwörter	Hochschulschrift; Dissertation; Databases; Integrity; Reliability; Online Searching; Search Strategies; Difficulty Level; Heuristics; Programming; Computation; Computer Science Education; Syntax; Information Retrieval + Suchen Sie Ihr Suchwort? Thesis; Dissertations; Academic thesis; Datenbank; Integrität; Reliabilität; Online-Recherche; Suchstrategie; Schwierigkeitsgrad; Heuristik; Programmierung; Computer science lessons; Informatikunterricht
Abstract	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.] (As Provided).
Anmerkungen	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
Erfasst von	ERIC (Education Resources Information Center), Washington, DC
Update	2020/1/01