Jan Chomicki
ABSTRACT
A consistent query answer in a possibly inconsistent database is an answer which is true in every (minimal) repair of the database. We present here a practical framework for computing consistent query answers for large, possibly inconsistent relational databases. We consider relational algebra queries without projection, and denial constraints. Because our framework handles union queries, we can effectively (and efficiently) extract indefinite disjunctive information from an inconsistent database. We describe a number of novel optimization techniques applicable in this context and summarize experimental results that validate our approach.
- S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]] Google Scholar
Digital Library
- M. Arenas, L. Bertossi, and J. Chomicki. Consistent Query Answers in Inconsistent Databases. In ACM Symposium on Principles of Database Systems (PODS), pages 68--79, 1999.]] Google ScholarDigital Library
- M. Arenas, L. Bertossi, and J. Chomicki. Answer Sets for Consistent Query Answering in Inconsistent Databases. Theory and Practice of Logic Programming, 3(4--5):393--424, 2003.]] Google ScholarDigital Library
- M. Arenas, L. Bertossi, J. Chomicki, X. He, V. Raghavan, and J. Spinrad. Scalar Aggregation in Inconsistent Databases. Theoretical Computer Science, 296(3):405--434, 2003.]] Google ScholarDigital Library
- M. Arenas, L. Bertossi, and M. Kifer. Applications of Annotated Predicate Calculus to Querying Inconsistent Databases. In International Conference on Computational Logic, pages 926--941. Springer-Verlag, LNCS 1861, 2000.]] Google ScholarDigital Library
- P. Barcelo and L. Bertossi. Logic Programs for Querying Inconsistent Databases. In International Symposium on Practical Aspects of Declarative Languages (PADL), pages 208--222. Springer-Verlag, LNCS 2562, 2003.]] Google ScholarDigital Library
- L. Bertossi and J. Chomicki. Query Answering in Inconsistent Databases. In J. Chomicki, R. van der Meyden, and G. Snake, editors, Logics for Emerging Applications of Databases, pages 43--83. Springer-Verlag, 2003.]]Google Scholar
- L. Bertossi, J. Chomicki, A. Cortes, and C. Gutierrez. Consistent Answers from Integrated Data Sources. In International Conference on Flexible Query Answering Systems (FQAS), pages 71--85, Copenhagen, Denmark, October 2002. Springer-Verlag.]] Google ScholarDigital Library
- L. Bravo and L. Bertossi. Logic Programs for Consistently Querying Data Integration Systems. In International Joint Conference on Artificial Intelligence (IJCAI), pages 10--15, 2003.]] Google ScholarDigital Library
- F. Bry. Query Answering in Information Systems with Integrity Constraints. In IFIP WG 11.5 Working Conference on Integrity and Control in Information Systems, pages 113--130. Chapman & Hall, 1997.]] Google ScholarDigital Library
- A. Cali, D. Lembo, and R. Rosati. On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases. In ACM Symposium on Principles of Database Systems (PODS), pages 260--271, 2003.]] Google ScholarDigital Library
- A. Celle and L. Bertossi. Querying Inconsistent Databases: Algorithms and Implementation. In International Conference on Computational Logic, pages 942--956. Springer-Verlag, LNCS 1861, 2000.]] Google ScholarDigital Library
- J. Chomicki and J. Marcinkowski. Minimal-Change Integrity Maintenance Using Tuple Deletions. Information and Computation, 2004. To appear. Earlier version: Technical Report cs.DB/0212004, arXiv.org e-Print archive.]] Google ScholarDigital Library
- T. Eiter, W. Faber, N. Leone, and G. Pfeifer. Declarative Problem-Solving in DLV. In J. Minker, editor, Logic-Based Artificial Intelligence, pages 79--103. Kluwer, 2000.]] Google ScholarDigital Library
- T. Eiter, M. Fink, G. Greco, and D. Lembo. Efficient Evaluation of Logic Programs for Querying Data Integration Systems. In International Conference on Logic Programming (ICLP), pages 163--177, 2003.]]Google Scholar
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. In International Conference on Database Theory (ICDT), pages 207--224. Springer-Verlag, LNCS 2572, 2003.]] Google ScholarDigital Library
- A. Fuxman and R. Miller. Towards Inconsistency Management in Data Integration Systems. In IJCAI-03 Workshop on Information Integration on the Web (IIWeb-03), 2003.]]Google Scholar
- G. Greco, S. Greco, and E. Zumpano. A Logic Programming Approach to the Integration, Repairing and Querying of Inconsistent Databases. In International Conference on Logic Programming (ICLP), pages 348--364. Springer-Verlag, LNCS 2237, 2001.]] Google ScholarDigital Library
- G. Greco, S. Greco, and E. Zumpano. A Logical Framework for Querying and Repairing Inconsistent Databases. IEEE Transactions on Knowledge and Data Engineering, 15(6):1389--1408, 2003.]] Google ScholarDigital Library
- A. Y. Halevy. Answering Queries Using Views: A Survey. VLDB Journal, 10(4):270--294, 2001.]] Google ScholarDigital Library
- P. C. Kanellakis. Elements of Relational Database Theory. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume~B, chapter~17, pages 1073--1158. Elsevier/MIT Press, 1990.]] Google ScholarDigital Library
- D. Van Nieuwenborgh and D. Vermeir. Preferred Answer Sets for Ordered Logic Programs. In European Conference on Logics for Artificial Intelligence (JELIA), pages 432--443. Springer-Verlag, LNAI 2424, 2002.]] Google ScholarDigital Library
- J. Wijsen. Condensed Representation of Database Repairs for Consistent Query Answering. In International Conference on Database Theory (ICDT), pages 378--393. Springer-Verlag, LNCS 2572, 2003.]] Google ScholarDigital Library
Index Terms
- Computing consistent query answers using conflict hypergraphs
Recommendations
First-order under-approximations of consistent query answers
Consistent Query Answering (CQA) is a principled approach for answering queries on inconsistent databases. The consistent answer to a query q on an inconsistent database db is the intersection of the answers to q on all repairs, where a repair is any ...
Consistent query answering under key and exclusion dependencies: algorithms and experiments
CIKM '05: Proceedings of the 14th ACM international conference on Information and knowledge managementResearch in consistent query answering studies the definition and computation of "meaningful" answers to queries posed to inconsistent databases, i.e., databases whose data do not satisfy the integrity constraints (ICs) declared on their schema. ...
The consistency extractor system: Answer set programs for consistent query answering in databases
We describe the Consistency Extractor System (Cons Ex) that computes consistent answers to Datalog queries with negation posed to relational databases that may be inconsistent with respect to certain integrity constraints. In order to solve this task, ...
Comments