¹Department of Computer Science and Technology, Hunan University of Humanities, Science and Technology, Loudi, 417000, China
²School of Computer Science, The University of Adelaide, SA 5005, Australia
³Department of Electronics and Information Engineering, Loudi Vocational and Technical College, Loudi, 417000, China

---

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.

Index Terms—relational database, inconsistent data; consistent query answer, first-order logic, query rewriting

[PDF]

Cite: Dong Xie, Xinbo Chen, Yan Zhu, "Tackling Polytype Queries in Inconsistent Databases: Theory and Algorithm," Journal of Software vol. 7, no. 8, pp. 1861-1866, 2012.