Tackling polytype queries in inconsistent databases: theory and algorithm
Files
(Published version)
Date
2012
Authors
Xie, Dong
Chen, Xinbo
Zhu, Yan
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Journal article
Citation
Journal of Software, 2012; 7(8):1861-1866
Statement of Responsibility
Dong Xie, Xinbo Chen, Yan Zhu
Conference Name
Abstract
To expand query types under a set of integrity constraints for obtaining consistent answers over inconsistent databases, a computational theory is proposed based on first-order logic. According to directed join graphs of queries and their join completeness, computational complexities of CQA are PTIME if query types are key-key, nonkey-key, incomplete key-key with acyclic join. This paper presents several algorithms to tackle a large and practical class of queries, which can obtain the rewritten queries for computing consistent answers. For a rewritable initial query, a consistent identification statement is constructed based on the join graph by recursive computation; and the statement combines with the initial query to construct a new first-order rewritten query for computing consistent answers. To acyclic self-join queries, the recursive rewriting algorithm cannot eliminate inconsistent tuples, so the initial query combines with the statement that eliminates them.
School/Discipline
School of Computer Science
Dissertation Note
Provenance
Description
Access Status
Rights
© 2012 ACADEMY PUBLISHER